Bounding the absolute sum of entries of the inverse of a 0-1 matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T09:36:18Z http://mathoverflow.net/feeds/question/81496 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix Bounding the absolute sum of entries of the inverse of a 0-1 matrix ifog 2011-11-21T13:16:40Z 2011-11-22T13:32:33Z <p>I have a non-singular square 0-1 matrix and I want to bound the sum of absolute values of its inverse as a function of n (or the vector 1-norm). Asymptotic results are also useful.</p> <p>Does anyone know any result that can help me?</p> <p>Thank you, ifog</p> http://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix/81498#81498 Answer by S. Sra for Bounding the absolute sum of entries of the inverse of a 0-1 matrix S. Sra 2011-11-21T13:37:57Z 2011-11-22T13:32:33Z <p><strong>Summary</strong> The answer below mentions a conjectured <strong>lower bound</strong> on the Frobenius norm of the inverse of a (0-1)-matrix. I have removed the now irrelevant simple observations that were based on matrices with real entries in $[0,1]$. Exponential upper bounds are discussed in Noam's and David's answers. The average case is described by Terry. </p> <hr> <p>As far as I know, proving the following lower bound $$\|A^{-1}\|_F \ge \frac{2n}{n+1},$$ is still an <strong>open problem</strong>. Further, the conjecture states that this lower bound is achieved iff and only if $A$ is an <em>S-matrix</em> (which is a (0-1)-matrix). See <a href="http://math.ecnu.edu.cn/~zhan/HangzhouZhan_beamerhandout.pdf" rel="nofollow">Problem 7 in this handout for more details</a>.</p> http://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix/81514#81514 Answer by Noam D. Elkies for Bounding the absolute sum of entries of the inverse of a 0-1 matrix Noam D. Elkies 2011-11-21T16:13:05Z 2011-11-21T16:18:45Z <p>The entries can grow at least exponentially. Let $T_n$ be the $n \times n$ matrix with ones on the main diagonal and first and third upper off-diagonals, and zeros elsewhere. Then $T_n$ is upper triangular of determinant $1$, but its inverse has top row $1, -1, 1, -2, 3, -4, 6, -9, 13, -19, 28, -41, \ldots$ whose absolute values satisfy the recurrence $t_m = t_{m-1}+t_{m-3}$ so the $n$-th one is asymptotically proportional to $C^n$ for some constant $C>1$ (namely $1.46557\ldots$, the real root of $C^3 = C^2 + 1$).</p> <p>Since $T_n$ is sparse, the entries of $T_n^{-1}$ can grow no faster than exponentially, as is seen by expressing them as $(n-1) \times (n-1)$ determinants (Cramer's rule) and applying Hadamard's inequality. Thus for sparse matrices $C^n$ is best possible but for the size of $C$. For a general $n \times n$ matrix with 0-1 entries and nonzero determinant, the same method gives an upper bound of $n^{(n-1)/2}$. I do not know whether the entries can actually grow faster than exponentially, i.e. faster than $C^n$ for any fixed $C$, but would not be too surprised if that's possible.</p> <p><strong>gp</strong> code for $n=12$:</p> <pre><code>T(n) = matrix(n,n,i,j, (j==i) || (j==i+1) || (j==i+3)) T12 = T(12) 1/T12 </code></pre> <p>returns</p> <pre><code>[1 1 0 1 0 0 0 0 0 0 0 0] [0 1 1 0 1 0 0 0 0 0 0 0] [0 0 1 1 0 1 0 0 0 0 0 0] [0 0 0 1 1 0 1 0 0 0 0 0] [0 0 0 0 1 1 0 1 0 0 0 0] [0 0 0 0 0 1 1 0 1 0 0 0] [0 0 0 0 0 0 1 1 0 1 0 0] [0 0 0 0 0 0 0 1 1 0 1 0] [0 0 0 0 0 0 0 0 1 1 0 1] [0 0 0 0 0 0 0 0 0 1 1 0] [0 0 0 0 0 0 0 0 0 0 1 1] [0 0 0 0 0 0 0 0 0 0 0 1] </code></pre> <p>for T12 and</p> <pre><code>[1 -1 1 -2 3 -4 6 -9 13 -19 28 -41] [0 1 -1 1 -2 3 -4 6 -9 13 -19 28] [0 0 1 -1 1 -2 3 -4 6 -9 13 -19] [0 0 0 1 -1 1 -2 3 -4 6 -9 13] [0 0 0 0 1 -1 1 -2 3 -4 6 -9] [0 0 0 0 0 1 -1 1 -2 3 -4 6] [0 0 0 0 0 0 1 -1 1 -2 3 -4] [0 0 0 0 0 0 0 1 -1 1 -2 3] [0 0 0 0 0 0 0 0 1 -1 1 -2] [0 0 0 0 0 0 0 0 0 1 -1 1] [0 0 0 0 0 0 0 0 0 0 1 -1] [0 0 0 0 0 0 0 0 0 0 0 1] </code></pre> <p>for its inverse.</p> http://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix/81561#81561 Answer by Terry Tao for Bounding the absolute sum of entries of the inverse of a 0-1 matrix Terry Tao 2011-11-22T00:28:11Z 2011-11-22T00:28:11Z <p>If one is interested in the typical answer (when the matrix is a random 0-1 matrix) rather than the worst-case answer, then the inverse behaves a lot better than exponential. Indeed, in view of the results of <a href="http://arxiv.org/abs/0802.3956" rel="nofollow">Rudelson and Vershynin</a>, it is likely that the j^th smallest singular value of the matrix has typical size $j/\sqrt{n}$. (Technically, the Rudelson-Vershynin result doesn't directly apply because the matrix is not normalised to have mean zero, but it is likely that the conclusions of that paper also apply to the off-centered case, after removing the exceptional outlier singular value of size about n/2.) Since the Frobenius norm of the inverse is the sum of negative second powers of the singular values, this Frobenius norm should then be about $O(n^{1/2})$, which implies by Cauchy-Schwarz that the $\ell^1$ norm of the inverse should be about $O(n^{3/2})$ typically. (Roughly speaking, this suggests that individual entries have size $O(n^{-1/2})$, a finding which is consistent with Cramer's rule and the limiting law for the determinant of a random 0-1 matrix (which has value about $\sqrt{(n-1)!}$ on the average, see e.g. <a href="http://arxiv.org/abs/math/0411095" rel="nofollow">this paper of myself and Van Vu</a>). </p> http://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix/81603#81603 Answer by David Speyer for Bounding the absolute sum of entries of the inverse of a 0-1 matrix David Speyer 2011-11-22T12:22:24Z 2011-11-22T12:22:24Z <p>An observation: As long as we stick to upper triangular matrices, as in Noam's answer, we can't get growth faster than $2^n$. More precisely, let $a_{ij}$ be an upper triangular $01$ matrix with $1$'s on the diagonal and let $b_{ij}$ be the inverse matrix. Then I claim that $|b_{i(i+k)}| \leq 2^{k-1}$ for all $k>0$.</p> <p>Proof: Induction on $k$. The case $k=1$ is easy because $b_{i(i+1)} = - a_{i(i+1)}$. In general, <code>$$\sum_{r=0}^k b_{i(i+r)} a_{(i+r)(i+k)} =0$$</code> so <code>$$|b_{i(i+k)}| = \left| \sum_{r=0}^{k-1} b_{i(i+r)} a_{(i+r)(i+k)} \right| \leq \sum_{r=0}^{k-1} |b_{i(i+r)}|.$$</code> By induction, the last is bounded by $1+1+2+4+\cdots+2^{k-2} = 2^{k-1}$, and we are done.</p>