Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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} $$

share|improve this question
    
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.

share|improve this answer
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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