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
$\begingroup$
$\endgroup$
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
5
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.
answered Nov 21, 2011 at 16:13
-
$\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$– ifogCommented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 24, 2011 at 6:50
$\begingroup$
$\endgroup$
2
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
-
1
-
$\begingroup$
$\endgroup$
4
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).
answered Nov 22, 2011 at 0:28
-
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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 22, 2011 at 23:21
$\begingroup$
$\endgroup$
1
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.
answered Nov 22, 2011 at 12:22
-
$\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$ Commented Nov 22, 2011 at 14:31
$\begingroup$
$\endgroup$
1
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.
-
$\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$– ifogCommented Nov 21, 2011 at 13:44