3
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Oct 1 '19 at 19:33
  • 1
    $\begingroup$ @Noam: But the sum in your example is also exponentially large, as it is.a recurrence with characteristic valies $C$, $-1$, $-1$. $\endgroup$ – Ilya Bogdanov Oct 1 '19 at 20:48
  • 1
    $\begingroup$ @Ilya you're right; I noticed this a bit afterwards. $\endgroup$ – Noam D. Elkies Oct 1 '19 at 22:08
  • 1
    $\begingroup$ @NoamD.Elkies It is about the sum of the entries of $A^{-1}$, although one might also want to think about the absolute values. $\endgroup$ – Mare Oct 2 '19 at 5:55
4
$\begingroup$

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)
$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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