# Sparsest matrix with full inverse

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?

• This might have something to do with irreducibility. An irreducible matrix cannot have less than $2n$ entries. – Algebraic Pavel Jul 3 '14 at 19:12
• The matrix with entries $a_{ij} = \delta_{i+1,j}$ is irreducible in my opinion, is self-inverse, and has only $n$ entries. – daw Jul 3 '14 at 19:43
• 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. – Algebraic Pavel Jul 3 '14 at 19:57

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