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?
Best Answer
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.