When is the inverse of a sparse matrix dense?

Question

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)

Answer 1

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.