Inverse of a matrix with sparse rows and columns.

Question

I understand the inverse of a sparse matrix is not necessarily sparse; however, I was wondering if there is anything to be said about the inverse of a matrix with a constant number of 1s in each of its columns and each of its rows (i.e. each of its rows and columns are also sparse).

Answer 1

The answer is no.

As a simple counterexample to this kind of idea, take any odd number $n$ and consider the (circulant) matrix $n \times n$ matrix $A$ whose entries satisfy $A_{i,j} = 1$ for $j \leq i \leq j + 1$ and $A_{1,n} = 1$, with all other entries of $A$ equal to $0$. Note that (for large $n$) $A$ is sparse with exactly $2$ non-zero entries in each row and in each column. For $n=7$, we have $$ A = \left[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 1\\1 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 1\end{matrix}\right]. $$ We find that $A^{-1}$ is not sparse; all of its entries are equal to $\pm \frac 12$. In particular, $A^{-1}$ is the circulant matrix whose first column is $\frac 12 (1,-1,1,-1,\dots,1)$. For $n=7$, we have $$ A^{-1} = \frac 12 \left[\begin{array}{rrrrrrr}1 & 1 & -1 & 1 & -1 & 1 & -1\\-1 & 1 & 1 & -1 & 1 & -1 & 1\\1 & -1 & 1 & 1 & -1 & 1 & -1\\-1 & 1 & -1 & 1 & 1 & -1 & 1\\1 & -1 & 1 & -1 & 1 & 1 & -1\\-1 & 1 & -1 & 1 & -1 & 1 & 1\\1 & -1 & 1 & -1 & 1 & -1 & 1\end{array}\right]. $$

By the way, here's a nice way to prove the inverse formula above: we can write $A = I + P$ for a permutation matrix $P$ satisfying $P^n = I$. It follows that

$$ (I + P)(I - P + P^2 - \cdots +P^{n-1}) = I + P^{n} = I + I = 2I. $$ From $(I + P)(I - P + P^2 - \cdots +P^{n-1}) = 2I$, deduce that $$ (I + P)^{-1} = \frac 12 (I - P + P^2 - \cdots +P^{n-1}). $$

---

Here's a counterexample over $\Bbb F_2^{n \times n}$. Take $n = 3k+1$ for some integer $k>0$, and take $A$ to be the circulant matrix whose first column is $(1,1,1,0,\dots,0)$. Note that $A$ has $3$ non-zero entries in each of its rows and each of its columns. The inverse of $A$ over $\Bbb F_{2\times 2}$ is the circulant matrix whose first column is $(1,0,1,1,0,1,1,\dots,0,1,1)$, for a total of $(2n+1)/3 = \lceil \frac 23 n \rceil$ non-zero entries in each row and each column.

In the case that $n = 10,$ we have $$ A = \left[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\end{matrix}\right], \\ \ \\ A^{-1} = \left[\begin{matrix}1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0\\0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1\\1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1\\1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0\\0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1\\1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1\end{matrix}\right]. $$

Answer 2

The inverse of differential operators (local) are integral operators (global). Discretize your favorite linear differential operator to get a counterexample to your conjecture.