7
$\begingroup$

What is the sparsest matrix in $\mathbb R^{n,n}$ such that the inverse is full?

I.e. I am looking for a matrix $A\in \mathbb R^{n,n}$ with as few non-zero entries as possible, such that $A^{-1}$ has no zeros.

The best I could find was $$ A = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 & 1 \\ 0 & 1 & 1 & 0 & \cdots & 0 \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 & 1 \end{pmatrix}\in \mathbb R^{n,n}, $$ which has $2n$ non-zero entries. Its inverse is $$ A^{-1} =\frac12 \begin{pmatrix} 1 & 1 & -1 & \cdots & -1 & 1 \\ -1 & 1 & 1 & -1 & \cdots & -1 \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ & \cdots & 1 & -1 & 1 & 1 \end{pmatrix}\in \mathbb R^{n,n}. $$ Both matrices are Toeplitz matrices, I am not that great on tex-ing large matrices.

Is there a matrix of with these properties that has less than $2n$ non-zero entries. If not how could one prove that $2n$ is the best possible?

$\endgroup$
  • 1
    $\begingroup$ This might have something to do with irreducibility. An irreducible matrix cannot have less than $2n$ entries. $\endgroup$ – Algebraic Pavel Jul 3 '14 at 19:12
  • $\begingroup$ The matrix with entries $a_{ij} = \delta_{i+1,j}$ is irreducible in my opinion, is self-inverse, and has only $n$ entries. $\endgroup$ – daw Jul 3 '14 at 19:43
  • $\begingroup$ I said "might". At least when a matrix is reducible its inverse cannot have all entries nonzero. Also, I was rather considering matrices with nonzero diagonal. $\endgroup$ – Algebraic Pavel Jul 3 '14 at 19:57
5
$\begingroup$

$2n$ non-zero elements is indeed the minimum.

Suppose $A\in \mathbb R^{n,n}$ has fewer than $2n$ non-zero elements. Then there is a row $i$ containing at most one element. Since $A$ is invertible, there must be exactly one element in that row (at column $j$) that is non-zero. We can thus find permutation matrices $P,Q$ such that $$ PAQ = \left(\begin{array}{c|c} * & * \\ \hline 0& a_{ij} \end{array}\right). $$ Now, $PAQ$ is block-triangular, hence $(PAQ)^{-1}$ is block-triangular, and $A^{-1} = Q (PAQ)^{-1}P$ contains at least $n-1$ zeros.

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