15
$\begingroup$

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

$\endgroup$

5 Answers 5

19
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Great answer, thanks a lot! I do wonder if the true C is n, maybe there's some pathological matrix showing it, but the difference between n^n and c^n is less important to me. $\endgroup$
    – ifog
    Nov 21, 2011 at 20:03
  • $\begingroup$ You're welcome. The Cramer/Hadamard argument shows $C$ cannot reach $n$, but does allow $C$ as large as $\sqrt{n}$. $\endgroup$ Nov 22, 2011 at 2:26
  • $\begingroup$ I define a sequence of 0-1 matrices at mathoverflow.net/questions/11885/… , whose determinants grow like the Fibonacci. I suspect the inverse will have a large sum of absolute values of entries, and I suspect it will be hard to find a sequence that will beat it under this measure infinitely often. Related: I am looking for matrices with medium determinant which are a common minor to a set of augmented matrices whose absolute determinant values form a large interval. Gerhard "Ask Me About System Design" Paseman, 2011.11.22 $\endgroup$ Nov 22, 2011 at 22:55
  • $\begingroup$ I will stick my neck out and say exponential growth is the worst that can be expected. Although it may require transforming to -1,1 matrices, I base my suspicion on the process of computing inverse by transforming the system A I to I B by elementary row operations. Gerhard "Ask Me About System Design" Paseman, 2011.11.22 $\endgroup$ Nov 22, 2011 at 23:11
  • $\begingroup$ I reviewed my notes and saw where I had asked too much of the inverse of the matrices defined in a comment of mine above. The norm of their inverses grows roughly linearly, about n times phi is my estimate. I still stick my neck out, and suspect Noam Elkies's example will be a record holder for a while. Gerhard "Acts Before Speaking Next Time" Paseman, 2011.11.23 $\endgroup$ Nov 24, 2011 at 6:50
15
$\begingroup$

An answer is given in:

N. Alon and V. H. Vu, Anti-Hadamard matrices, coin weighing, threshold gates and indecomposable hypergraphs, J. Combinatorial Theory, Ser. A 79 (1997), 133-160.

Indeed C above is essentially sqrt n

$\endgroup$
2
  • $\begingroup$ (belated) Welcome to MO, Noga! $\endgroup$
    – Gil Kalai
    Dec 2, 2014 at 12:19
  • $\begingroup$ Incredible paper! $\endgroup$
    – BD107
    Dec 3, 2020 at 0:50
14
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Interesting. Unlike the extremal behavior, the "typical" 0-1's inverse could be probed for moderately large $n$ by Monte Carlo techniques $-$ what kind of experiment might corroborate your expectation?$$ $$ For the worst-case behavior, since the minors can grow faster than exponential one expects to get as large as $2^n$ or so by just choosing all but one row randomly and then trying all $2^n$ possibilities for the remaining row to find the one that minimizes the determinant without killing it. But that's still exponential; do you think one might get $C_n^n$ with $C_n \rightarrow\infty$? $\endgroup$ Nov 22, 2011 at 2:07
  • 1
    $\begingroup$ I would believe so, but this may be out of reach of current technology. By gaussian elimination, the determinant must be an integer multiple of $2^{n-1}$, but is believed to be otherwise unconstrained (at least for values $\ll \sqrt{(n-1)!}$). As such, if one randomly selects $n-1$ rows, then one would expect to beat $2^n$ by a factor of $K$ with probability about $1/K$ for any given $K$, assuming there is enough of a "central limit theorem" that the random sums look Gaussian. As there are $2^{n(n-1)}$ possible values for these rows, this suggests a substantial improvement over exponential. $\endgroup$
    – Terry Tao
    Nov 22, 2011 at 16:03
  • 2
    $\begingroup$ Looks like you're thinking of {$-1,1$} matrices, not {$0,1$}, but I guess you expect the same thing (without the $2^{n-1}$ complication). $\endgroup$ Nov 22, 2011 at 21:18
  • $\begingroup$ The spectrum (set of absolute determinant values) of order n -1,1 matrices was conjectured to achieve all multiples of 2^(n-1) below the Hadamard bound back in the '50's or '60's; this conjecture was shown false by Metropolis, Craigen, and others. Will Orrick has the best writeup on the spectrum topic that I have seen; there are plenty of unanswered questions. Orrick's maxdet website is a good starting point. Gerhard "Ask Me About Determinant Spectrum" Paseman, 2011.11.22 $\endgroup$ Nov 22, 2011 at 23:21
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I noticed this bound too; it applies for any upper triangular matrix with unit diagonal and off-diagonal elements of absolute value at most $1$. But to attain equality you need $-1$ entries once $k>1$. If only nonnegative entries are allowed then the best I can do is Fibonacci numbers. $\endgroup$ Nov 22, 2011 at 14:31
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ When I said 0-1 I meant values that are only 0 or 1 (binary matrix, but not over Z2). I know that in this case there's a nice bound for the determinant for example. The upper bound is what interests me more. $\endgroup$
    – ifog
    Nov 21, 2011 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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