2
$\begingroup$

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$.

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$
    – pulosky
    Jul 26 '18 at 15:08
  • $\begingroup$ 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)$. $\endgroup$
    – parsiad
    Jul 26 '18 at 15:13
  • $\begingroup$ 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. $\endgroup$ Jul 26 '18 at 15:18
  • $\begingroup$ @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$ $\endgroup$
    – pulosky
    Jul 26 '18 at 15:19
  • 1
    $\begingroup$ That's helpful context- I'd suggest adding it to your question. $\endgroup$ Jul 26 '18 at 15:26
4
$\begingroup$

$$ \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}$$

$\endgroup$
2
  • $\begingroup$ great, thanks a lot! $\endgroup$
    – pulosky
    Jul 26 '18 at 15:29
  • 1
    $\begingroup$ @pulosky you can accept an answer to mark your question as answered $\endgroup$
    – LinAlg
    Jul 26 '18 at 15:53

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.