2
$\begingroup$

The question is basically stated in the title. Say $A$ is a sparse square matrix, then

  1. Is there any way to estimate the density of non-zero elements of $A^{-1}$? What properties of $A$ are important?
  2. Is the situation simpler when $A$ is banded, in the sense that $A_{ij}=0$ for $|i-j|>k$?

(I know that the generic answer is that the inverse of a sparse matrix is usually dense, but I want to know if this statement has a quantitative aspect, or is just a general observation)

$\endgroup$
  • 1
    $\begingroup$ It's maybe a bit late but it is worth noting that irreducible matrices (such matrices occur often in practice and many banded matrices fall in this class as well) have generally dense inverses. $\endgroup$ – Algebraic Pavel Jun 1 '17 at 14:34
1
$\begingroup$
  1. There is no known way to estimate this. The extreme case of a diagonal matrix has a diagonal inverse, but for example a tridiagonal matrix will generally have a fully dense inverse. This question touches on graph theory since a matrix can be thought of as an operator on a graph where every index corresponds to a vertex, and the entries correspond to weights between vertices, and it is the structure of the graph which will affect the sparsity of $A^{-1}$. For example, some trivial structures that can be exploited are unconnected components of the graph; this translates to (subject to suitable permutation) a partitioning of the matrix into uncoupled blocks (zero off diagonal blocks); the inverse then inherits this block structure. There are certainly more subtle structures that can be exploited.
  2. As noted above, banded-ness doesn't help you, considering the drastic difference between diagonal and tridiagonal matrices.
$\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.