Bounding the absolute sum of entries of the inverse of a 0-1 matrix - MathOverflow

Bounding the absolute sum of entries of the inverse of a 0-1 matrix

2011-11-21T13:16:40Z

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.

Does anyone know any result that can help me?

Thank you, ifog

Answer by S. Sra for Bounding the absolute sum of entries of the inverse of a 0-1 matrix

2011-11-21T13:37:57Z

Summary The answer below mentions a conjectured lower bound 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.

As far as I know, proving the following lower bound $$\|A^{-1}\|_F \ge \frac{2n}{n+1},$$ is still an open problem. Further, the conjecture states that this lower bound is achieved iff and only if $A$ is an S-matrix (which is a (0-1)-matrix). See Problem 7 in this handout for more details.

Answer by Noam D. Elkies for Bounding the absolute sum of entries of the inverse of a 0-1 matrix

2011-11-21T16:13:05Z

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$).

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.

gp code for $n=12$:

T(n) = matrix(n,n,i,j, (j==i) || (j==i+1) || (j==i+3))
T12 = T(12)
1/T12

returns

[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]

for T12 and

[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]

for its inverse.

Answer by Terry Tao for Bounding the absolute sum of entries of the inverse of a 0-1 matrix

2011-11-22T00:28:11Z

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 Rudelson and Vershynin, 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. this paper of myself and Van Vu).

Answer by David Speyer for Bounding the absolute sum of entries of the inverse of a 0-1 matrix

2011-11-22T12:22:24Z

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

Proof: Induction on $k$. The case $k=1$ is easy because $b_{i(i+1)} = - a_{i(i+1)}$. In general, $$\sum_{r=0}^k b_{i(i+r)} a_{(i+r)(i+k)} =0$$ so $$|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)}|.$$ By induction, the last is bounded by $1+1+2+4+\cdots+2^{k-2} = 2^{k-1}$, and we are done.