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



Bounding the absolute sum of entries of the inverse of a  0-1 matrix
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.


