I have a nonsingular square 01 matrix and I want to bound the sum of absolute values of its inverse as a function of n (or the vector 1norm). Asymptotic results are also useful.
Does anyone know any result that can help me?
Thank you, ifog
I have a nonsingular square 01 matrix and I want to bound the sum of absolute values of its inverse as a function of n (or the vector 1norm). Asymptotic results are also useful. Does anyone know any result that can help me? Thank you, ifog 


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 offdiagonals, 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_{m1}+t_{m3}$ 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 $(n1) \times (n1)$ 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 01 entries and nonzero determinant, the same method gives an upper bound of $n^{(n1)/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$:
returns
for T12 and
for its inverse. 


If one is interested in the typical answer (when the matrix is a random 01 matrix) rather than the worstcase 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 RudelsonVershynin 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 offcentered 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 CauchySchwarz 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 01 matrix (which has value about $\sqrt{(n1)!}$ on the average, see e.g. this paper of myself and Van Vu). 


An answer is given in: N. Alon and V. H. Vu, AntiHadamard matrices, coin weighing, threshold gates and indecomposable hypergraphs, J. Combinatorial Theory, Ser. A 79 (1997), 133160. Indeed C above is essentially sqrt n 


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^{k1}$ 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}^{k1} b_{i(i+r)} a_{(i+r)(i+k)} \right \leq \sum_{r=0}^{k1} b_{i(i+r)}.$$ By induction, the last is bounded by $1+1+2+4+\cdots+2^{k2} = 2^{k1}$, and we are done. 


Summary The answer below mentions a conjectured lower bound on the Frobenius norm of the inverse of a (01)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 Smatrix (which is a (01)matrix). See Problem 7 in this handout for more details. 

