2
$\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?

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

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Commented Aug 19, 2013 at 15:55
  • $\begingroup$ @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. $\endgroup$
    – Sungmin
    Commented Aug 19, 2013 at 16:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Aug 19, 2013 at 19:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Aug 19, 2013 at 20:32
  • 4
    $\begingroup$ The m.se post was math.stackexchange.com/questions/471136/… --- OP waited all of 4 hours before deciding no one was answering it. $\endgroup$
    – Gerry Myerson
    Commented Aug 20, 2013 at 0:10

0

Reset to default

Browse other questions tagged .