Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

EDIT: As suggested by Yemon Choi, it would be better to ask if there is a precise way to say that the inverses of "most" sparse matrices are not sparse.

NOTE : This was asked in math stack exchange earlier, but no one seems to answer it so I posted here too. Looking forward to great answers.:)

share|improve this question

closed as off-topic by Yemon Choi, Andrey Rekalo, David White, Andy Putman, Suvrit Aug 19 '13 at 17:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Yemon Choi, Andrey Rekalo, David White, Andy Putman, Suvrit
If this question can be reworded to fit the rules in the help center, please edit the question.

2  
You can verify these assertions by looking at examples, surely. Try a tridiagonal matrix whose non-zero entries are all 1. This question seems too basic for MathOverflow –  Yemon Choi Aug 19 '13 at 15:55
    
@YemonChoi: Yes your example can be an example. However, I am not sure how this answers my question. I can think of another example such as matrices with translation symmetry since their discrete Fourier components are all non-zero, which makes their inverse is not sparse. But they are just examples. –  Sungmin Aug 19 '13 at 16:55
1  
I deleted some more precise comments because I think I found an error in one of my bounds, so I'll just make a more general statement. The answer to this question will, of course, depend on model of a sparse matrix you are using. The simplest model (Erdos-Renyi) is that you have an $n \times n$ matrix with $N$ nonzero entries. The positions of those entries in the matrix are chosen uniformly at random, and those $N$ matrix entries are real numbers with no algebraic relations between them. –  David Speyer Aug 19 '13 at 19:05
3  
We then have the easy lemma: Let $A$ be a matrix with nonzero diagonal entries, and no algebraic relations between nonzero entries. Let $G$ be a directed graph where there is an edge $i \to j$ if $A_{ij} \neq 0$. Then $(A^{-1})_{ij}$ is nonzero if and only if there is a path $i \to \to \to \cdots \to j$ in $G$. I'd start searching on various subsets of the terms "random graph" "directed graph" "digraph" "Erdos Renyi" "strongly connected components" "transitive closure". As yet, I haven't found a paper addressing this question with those keywords, but it should be out there. –  David Speyer Aug 19 '13 at 20:32
3  
The m.se post was math.stackexchange.com/questions/471136/… --- OP waited all of 4 hours before deciding no one was answering it. –  Gerry Myerson Aug 20 '13 at 0:10