# Sparsity of the inverse of a non-negative matrix

Let $A \in \mathbb{R}^{b \times b}$ be a matrix with non-negative entries. Suppose that $A$ is invertible. Further suppose that all the diagonal entries of $A$ are non-null. My claim is the following: $$\text{bin}(A^{-1})=\text{bin}(A^{b-1})\,,$$ where $\text{bin}: \mathbb{R}^{b \times b}\rightarrow \{0,1\}^{b \times b}$ gives the binary sparsity pattern of $A$, in the sense that an entry of matrix $\text{bin}(A)$ is $1$ if and only if the corresponding entry of $A$ is different from $0$. For instance $$\text{bin}\left(\begin{bmatrix}1&2&0\\0&2&1\\1&0&2\end{bmatrix}^{-1}\right)=\text{bin}\left(\begin{bmatrix}1&2&0\\0&2&1\\1&0&2\end{bmatrix}^2\right)=\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}\,.$$

Notice that, by Cayley-Hamilton's theorem and the fact that the diagonal of $A$ is full, I expect any counter-example to my claim to be such that one entry of $\text{bin}(A^{-1})$ is $0$ while the same entry of $\text{bin}(A^{b-1})$ is $1$.

• Sorry, I meant that there is an entry of $bin(A^{-1})$ which is $0$ while the same entry of $bin(A^{a-1})$ is $1$. Jul 26 '18 at 15:08
• More concisely, you conjecture that if $A \in \mathbb{R}^{a \times a}_{\geq 0}$ is invertible, $A^{-1}$ has the same sparsity pattern as $A^{a-1}$. Moreover, you are asking if someone can find a counterexample in which $(A^{-1})_{ij} = 0$ and $(A^{a-1})_{ij} \neq 0$ for some $(i, j)$. Jul 26 '18 at 15:13
• Do you want $\mbox{bin}(A^{-1})$ to be equal to, less than or equal to, or greater than or equal to $\mbox{bin}(A^{b-1})$? You've described in this in different and inconsistent ways. Jul 26 '18 at 15:18
• @parsiad I additionally ask that $A$ has a full diagonal, so that the sparsity of $A$ "grows" with the powers of $A$. The counter-example I'm asking for is just a counter-example of the claim. at Rodrigo agreed. Changed it to $b \times b$ Jul 26 '18 at 15:19
$$\pmatrix{1 & 1 & 1\cr 1 & 2 & 2\cr 1 & 2 & 3}^{-1} = \pmatrix{2 & -1 & 0\cr -1 & 2 & -1\cr 0 & -1 & 1\cr}$$