# bounding the sum of the entries of the inverse of a 0-1 matrix away from 1?

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&lt;1$, e.g. $$A=\left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \&bsol; 0 & 0 & 1 & 0 \&bsol; 0 & 1 & 1 & 1 \&bsol; 1 & 0 & 1 & 1 \end{array}\right), \quad A^{-1}=\left(\begin{array}{rrrr} -1 & -1 & 0 & 1 \&bsol; -1 & -1 & 1 & 0 \&bsol; 0 & 1 & 0 & 0 \&bsol; 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}$$

-
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 –  Gerhard Paseman Dec 1 '12 at 11:24
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$. –  Dima Pasechnik Dec 1 '12 at 13:58
add comment

## 1 Answer

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

-
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 –  Gerhard Paseman Nov 30 '12 at 14:27
But Noam Elkies has shown a matrix which achieves exponential sum - which disproves both readings of the conjecture. –  Felix Goldberg Nov 30 '12 at 14:45
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. –  Dima Pasechnik Nov 30 '12 at 15:48
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 –  Gerhard Paseman Nov 30 '12 at 15:48
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 –  Gerhard Paseman Nov 30 '12 at 16:00
show 7 more comments