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