Inverse of sparse matrix is not generally sparse

Question

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices).

I encountered several times the web pages which states that the inverse of the sparse matrix is not usually sparse and my experience also said so. One exception can be diagonal matrices.

How theses kind of assertions can be verified?

Answer 1

First of all, as far as I know there is no precise definition of a sparse matrix. The word sparse is used for a series $(A_n)_{n\in\mathbb{N}}$ of $n\times n$ matrices whose fraction of non-zero entries converges to zero.

Consider the series of matrices $A_n$ with entries $1$ on the diagonal and on the position above the diagonal, and zero entries otherwise, that is $$A_n = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 \\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix}$$

The number of non-zero entries of $A_n$ is $n + (n-1) = 2n - 1$, so the fraction of non-zero entries is $\frac{2n - 1}{n^2}$. Since $\lim_{n\to \infty} \frac{2n-1}{n^2} = 0$, the series $A_n$ is sparse.

It's straightforward to check that all matrices $A_n$ are invertible with the inverse $A_n^{-1} = (b_{ij})$ where $$b_{ij} = \begin{cases} 0 & \text{ if }i>j\text{,}\\ 1 & \text{ if }i \leq j\text{ and }j-i\text{ even,}\\ -1 & \text{if }i \leq j\text{ and }j-i\text{ odd,} \end{cases}$$ that is $$ A_n^{-1} = \begin{pmatrix} 1 & -1 & 1 & \cdots & \pm 1 \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 1 \\ \vdots & & \ddots & \ddots & -1 \\ 0 & \cdots & \cdots & 0 & 1 \end{pmatrix}$$ The fraction of non-zero entries of $A_n^{-1}$ is $$\frac{(n^2 + n)/2}{n^2} \overset{n\to \infty}{\rightarrow} 1/2, $$ so the series $A_n^{-1}$ is not sparse.

Answer 2

The inverse of square sparse matrices is not sparse.

You can find examples in the field of graph theory. Let $\mathbb{G}(V, E)$ be an undirected connected graph. We define the adjacency matrix associated with $\mathbb{G}$ as $\bf A$ and $\bf D$ is the corresponding degree matrix $\bf D$. Let $\alpha \in (0, 1)$. Now, consider the matrix $${\bf M} := {\bf I} - \alpha {\bf D}^{-1/2} {\bf A} {\bf D}^{-1/2}.$$ Clearly, ${\bf M}$ is a sparse matrix if we assume $\mathbb{G}$ is sparse (${\bf M}$ is also symmetric positive definite!). However, one can prove that ${\bf M}^{-1}$ is totally dense matrix meaning that entries of ${\bf M}^{-1}$ are all positives. This fact is due to the following theorem (Theorem 2.7 on Page 141 of [1]):

Let ${\bf Q}$ be a $Z$-matrix and irreducible. Then $\bf Q$ is a nonsingular $M$-matrix implies ${\bf Q}^{-1} \gg 0$.

In the above theorem, ${\bf Q}^{-1} \gg 0$ means all entries of ${\bf Q}^{-1}$ are positives. You can verify that ${\bf M}$ defined above is indeed non-singular and an $M$-matrix. Since we assume, the graph is connected, the associated matrix $\bf A$ must be irreducible. So, does $\bf M$.

[1] Berman, Abraham, and Robert J. Plemmons. Nonnegative matrices in the mathematical sciences. Society for Industrial and Applied Mathematics, 1994.