Inverse matrix and its zero entries

Let $A$ be an $N \times N$ square invertible matrix with inverse $A^{-1}$. Is it possible to know through information of $A$ alone (i.e. without actually calculating $A^{-1}$)

1. Which entries of $A^{-1}$ will be zero?
2. How many entries of $A^{-1}$ will be zero?

Are there certain matrices for which we know which entries of the inverse are zero / the number of zero entries? Can something be said probabilistically if an entry of $A^{-1}$ is zero?

For example, the inverse of an upper triangular matrix is also upper triangular so we know how many entries are zero ($N^2-N$) and which entries are zero (the upper triangle).

Solution 1:

First of all, the original poster’s example with upper triangular matrices is not exactly correct. We know certainly that lower-left $N^2 - N$ entries are zero, and (as for any invertible triangular matrix) that all $N$ diagonal entries are not zero, but we are generally ignorant about $N^2 - N$ upper-right entries. We do not have an algorithm that decides whether $(A^{-1})_{jk} = 0,\ j < k$ significantly easier than an algorithm just computing that $(A^{-1})_{jk}$.

As for square matrices in general, three comments under the question already stated that in special cases the answer might be possible. Is it possible in the general case? Henceforth I exclude the question “2.” and will consider only the problem about $(A^{-1})_{jk} = 0$ for concrete $j$ and $k$.

Let $F$ be the ground field, such as rational, real, or complex numbers. Then, $A: F^N \to F^N$ and the same for $A^{-1}$, if it is well-defined. Let $({\mathbf e}_1, {\mathbf e}_2,\ldots {\mathbf e}_N)$ be the standard basis in $F^N$ and $D^N_j \subset F^N$ be a linear hyperplane spanned of all elements of the standard basis except ${\mathbf e}_j$. In other words, $D^N_j$ consists of all $N$-vectors with $j$th coordinate equal to zero. Obviously, $$ (A^{-1})_{jk} = 0\quad \Leftrightarrow \quad A^{-1}\,{\mathbf e}_k \in D^N_j\quad \Leftrightarrow \quad {\mathbf e}_k \in A\,D^N_j$$ (from this point on I suppose that $A$ is invertible). What is the image space $A\,D^N_j$? It is the linear span of vectors $\{\ A\,{\mathbf e}_l\ |\ l=1\ldots N,\ l\ne j\ \}$. How can we check whether does ${\mathbf e}_k$ belong to $A\,D^N_j$? For a general matrix (invertible, but of otherwise no special form), by finding an appropriate linear combination of said vectors, no simpler, since we have linear span of arbitrary $N-1$ linearly independent vectors (remind that $A$ is invertible). This combination must be unique and coefficients in it shall be exactly entries $\{\ (A^{-1})_{lk}\ |\ l=1\ldots N,\ l\ne j\ \}$, that follows from the rule of matrix-by-vector multiplication: $$ A^{-1}\,{\mathbf e}_k = \sum\limits_{l=1}^N (A^{-1})_{lk}{\mathbf e}_l.$$ Although not a formal proof, the reasoning shows that we can’t find anything about an entry of the inverse matrix in a way much simpler than computing an entire column of $A^{-1}$. Of course, we can consider right multiplication of row vectors instead of left multiplication of column vectors, but this doesn’t change the conclusion that finding whether an isolated matrix entry of $A^{-1}$ is zero or not requires about $1/N$ of total $A^{-1}$ computation job.