1
$\begingroup$

Let $A\in\mathbb{R}^{n\times n}$ be an invertible 0-1 matrix. Is it possible that the sum $a:=\sum_{i,j}(A^{-1})_{ij}$ of entries of $A^{-1}$ is not equal to 1, but exponentially close (w.r.t. $n$) to 1?

More precisely, the conjecture is that if $a\geq 1$ then either $a=1$ or $|a|\geq 1+p(n)/q(n)$, for $p$ and $q$ fixed polynomials (some other not too fast growing functions might do, too).

Remark. The condition $a\geq 1$ is not redundant, as there exist matrices $A$ with $a<1$, e.g. $$A=\left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right), \quad A^{-1}=\left(\begin{array}{rrrr} -1 & -1 & 0 & 1 \\ -1 & -1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right), \quad a=\sum_{i,j} (A^{-1})_{ij}=0. $$

An (admittedly very shaky) evidence for this is that it is true if the row sums $r_i$ of $A$ are all equal to each other. Indeed, let $\overline 1$ denote the all-1 vector. Then $a=\sum_{i=1}^n x_i$ for $x$ satisfying $Ax=\overline 1$, and $$ \overline{1}^\top Ax=\sum_i r_i x_i=\overline{1}^\top \overline{1}=n,\quad \text{implying }\quad a\geq \frac{n}{n-1} $$

$\endgroup$
2
  • $\begingroup$ Thank you for the example. In return, J - I (rotated) will give an a value of n/n-1. Gerhard "Ask Me About Binary Matrices" Paseman, 2012.12.01 $\endgroup$ Dec 1, 2012 at 11:24
  • $\begingroup$ more generally, one can take block $2k\times 2k$ matrix of form $\binom{I\ B}{0\ I}$, where $B$ is all-1 $k\times k$ block. Then the sum of the entries of its inverse is $-k^2+2k$. $\endgroup$ Dec 1, 2012 at 13:58

1 Answer 1

2
$\begingroup$

Apparently, this question had already been answered in the negative here.

$\endgroup$
12
  • 1
    $\begingroup$ My reading of the linked post is that the lower bound has been conjectured as close to 2, which is supported by looking at some order 2^k - 1 matrices. However, this poster has not made it clear if the target sum is near 1 or near n. Gerhard "Ask Me About System Design" Paseman, 2012.11.30 $\endgroup$ Nov 30, 2012 at 14:27
  • $\begingroup$ But Noam Elkies has shown a matrix which achieves exponential sum - which disproves both readings of the conjecture. $\endgroup$ Nov 30, 2012 at 14:45
  • $\begingroup$ I don't understand this answer. Elkies shows that it is possible that $a$ is exponentially big. I am asking whether $a-1$ can be positive, but exponentially small. $\endgroup$ Nov 30, 2012 at 15:48
  • 1
    $\begingroup$ But the conjecture is that a is always 1 or large. Noam has provided evidence for the poster's conjecture, but says not enough about how "small" large is. I read the poster's question as what is the closest to 1 (or n) a can become without reaching that value. Gerhard "Ask Me About System Design" Paseman, 2012.11.30 $\endgroup$ Nov 30, 2012 at 15:48
  • $\begingroup$ I can come up with examples (using k rows that add up to a row of all ones) that achieve k for any integer k from 1 to n. I imagine that one can try using row echelon manipulations to bound a away from 1. I suggest doing some small trials (of order up to 6 at least) to get some numerical evidence for what Suvrit suggested, that 2n/(n-1) is the bound you seek. Gerhard "Ask Me About System Design" Paseman, 2012.11.30 $\endgroup$ Nov 30, 2012 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.