8
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh I see, thanks for the illuminating example. Do you think there is an known ensemble(Maybe random matrix ensemble which are mostly sparse but inverse of them are not)? $\endgroup$ – Sungmin Aug 22 '13 at 3:51
  • $\begingroup$ @Sungmin So this example doesn't answer your question? Please give exact definitions of what you are looking for. $\endgroup$ – azimut Aug 22 '13 at 9:45
3
$\begingroup$

A good example is an arrow matrix, like \begin{equation*} A = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}. \end{equation*} You can check that $A^{-1}$ is dense. The LU factors of $A$ are not very sparse either.

However, it is possible to find a "sparse LU" factorization for $A$: \begin{equation*} A = PLUQ^T, \end{equation*} where $P$ and $Q$ are permutation matrices and $L$ and $U$ are sparse. You can observe this in Matlab using the lu function.

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