# 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

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