13
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ A rather trivial example: orthogonal matrices ($O^{-1}=O^T$). $\endgroup$ Commented Aug 4, 2014 at 10:26
  • 2
    $\begingroup$ This question makes sense rather when $A$ is sparse. For instance, one can try to permute $A$ to a block triangular form (then it is easy to give a "bound" on the nonzero pattern of $A$). Also, almost all sparse direct solvers perform a symbolic graph analysis of $A$ prior to the actual factorization to determine the patterns of triangular factors. The sparsity pattern of $A^{-1}$ can then be obtained from the nonzero structure of the triangular factors. $\endgroup$ Commented Aug 4, 2014 at 14:30
  • $\begingroup$ Thanks. So what you are saying is that the way to approach this type of problem is to find triangular matrices. If $A$ contains block triangular matrices, will the inverse also contain block triangular matrices? Also is the reason that these sparse direct solvers search for triangular matrices is because triangular matrices are easiest to invert? $\endgroup$
    – user103828
    Commented Aug 5, 2014 at 6:41
  • $\begingroup$ @user103828 It is a possible way. Not just sparse ones but all direct solvers are based on factorizing a matrix to something what is easy to "invert", although the factors are rarely explicitly inverted (in particular in the case of sparse matrices, where the inverse would be generally dense). $\endgroup$ Commented Aug 5, 2014 at 10:03
  • 1
    $\begingroup$ Banded matrix have banded inverse. That's a generalization of triangular matrices, in some sense, and you can give a lower bound on the number of zeros. But for general sparse matrix that cannot be (easily) permuted into a banded matrix, I don't know. $\endgroup$
    – bartgol
    Commented Aug 20, 2014 at 23:49

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think the author asked "which entrees are guaranteed to be zero", not "which entrees are guaranteed to be non-zero"; you answered the latter. $\endgroup$
    – olamundo
    Commented Nov 5, 2016 at 8:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .