# Inequality for 0-1 matrices

Given an $$n \times n$$-matrix $$A$$ with entries only $$0$$ or $$1$$ and determinant equal to $$\pm 1$$. Define the magnitude $$M_A$$ of $$A$$ as the sum of all entries of the inverse of $$A$$.

Question 0: Do we have that the sum of all entries of $$A$$ is greater than or equal to $$M_A$$ when $$A$$ additionally has all diagonal entries equal to one?

This is true for $$n \leq 4$$. One might also consider other bounds such as whether $$M_A \leq n^2$$.

Question 1: What is the maximal possible magnitude of such an $$A$$?

Question 2: What is the maximal value of the magnitude of $$A$$ in case it has additional all diagonal entries equal to $$1$$?

This is a small variant of a question asked on Math SE. The zeroth and second question is related to bounds for the magnitude of a Schurian algebra.

• Do you want the sum of the entries of $A^{-1}$ or of their absolute values? The absolute values can grow exponentially; I gave an example at mathoverflow.net/questions/157472/… which can be taken to be upper triangular by permuting the rows or columns. Oct 1, 2019 at 19:33
• @Noam: But the sum in your example is also exponentially large, as it is.a recurrence with characteristic valies $C$, $-1$, $-1$. Oct 1, 2019 at 20:48
• @Ilya you're right; I noticed this a bit afterwards. Oct 1, 2019 at 22:08
• @NoamD.Elkies It is about the sum of the entries of $A^{-1}$, although one might also want to think about the absolute values.
– Mare
Oct 2, 2019 at 5:55

The "magnitude" can grow exponentially with $$n$$, even when $$A$$ is triangular (and thus has all-$$1$$ diagonal) with no more than three $$1$$'s in each row and column.

Indeed suppose $$A_{ij} = 1$$ if and only if $$j \in \{i,i+1,i+3\}$$. Then for large odd $$n$$ the magnitude $$M_A$$ is asymptotically proportional to $$C^n$$ for some constant $$C>1$$, namely the real root $$1.46557\ldots$$ of $$C^3 = C^2 + 1$$. For example, $$n=99$$ yields a matrix with $$293$$ ones and magnitude $$4010964491506511$$. (For large even $$n$$, the magnitude becomes exponentially negative; e.g. $$n=100$$ yields a matrix with $$296$$ ones and magnitude $$-5878354170831089$$.) Exponential growth is the fastest possible for sparse matrices, because each entry of $$A^{-1}$$ is $$\pm \det A'$$ for some minor $$A'$$ of $$A$$, and Hadamard's inequality gives an exponential upper bound on $$\left|\det A'\right|$$ for sparse 0-1 matrices $$A'$$.

The above construction is an adaptation of the example I gave in this Mathoverflow answer of sparse 0-1 matrices that are invertible but have exponentially small eigenvalues, and is the same as the example I gave here of a 0-1 matrix whose inverse has exponentially large absolute sum. The magnitudes for $$n=99$$ and $$n=100$$ were computed in milliseconds using this gp code:

S(n, T) = sum(i=1,n,sum(j=1,n,T[i,j])) \\ sum of entries of n*n matrix T
M(n, A,A1) = A = matrix(n,n,i,j,(j==i+1)+(j==i+3))+1; A1 = 1/A; S(n,A1)
M(99)
M(100)


If you allow the entries of $$A$$ to be in $$\{0, \pm 1\}$$ then there is a really nice construction that shows that the sum of the entries of $$A^{-1}$$ can be exponentially large.

Let the diagonals of $$A$$ be all $$1$$'s and then make all of the entries underneath the diagonal $$-1$$ and the entries above the diagonal $$0$$. Now let $$c$$ be the first column of $$A^{-1}$$ and consider what information we get from the equation $$A \cdot A^{-1} = I$$.

Matrix multiplication tells us that the entries of $$c$$ satisfy the following recurrence $$c_i = \sum_{j < i} c_j$$ for $$i \ge 2$$ and $$c_1 = 1$$. From this, we easily see that $$c_n$$ is exponential. Furthermore, the same analysis also holds for the other columns and we get a similar behavior except the $$k$$th column has $$k$$ zeros in the beginning before this pattern of the powers of $$2$$. In conclusion, $$A^{-1}$$ has all non negative entries and the sum of all the entries of $$A^{-1}$$ is at least $$2^n$$.