# Are the inverses of these matrices always tridiagonal?

While putzing around with the linear algebra capabilities of my computing environment, I noticed that inverses of $n\times n$ matrices $\mathbf M$ associated with a sequence $a_i$, $i=1\dots n$ with $m_{ij}=a_{\max(i,j)}$, which take the form

$$\mathbf M=\begin{pmatrix}a_1&a_2&\cdots&a_n\\a_2&a_2&\cdots&a_n\\\vdots&\vdots&\ddots&a_n\\a_n&a_n&a_n&a_n\end{pmatrix}$$

(i.e., constant along "backwards L" sections of the matrix) are tridiagonal. (I have no idea if there's a special name for these matrices, so if they've already been studied in the literature, I'd love to hear about references.) How can I prove that the inverses of these special matrices are indeed tridiagonal?

## 1 Answer

Let $B_j$ be the $n\times n$ matrix with $1$s in the upper-left hand $j\times j$ block and zeros elsewhere. The space of $L$-shaped matrices you're interested in is spanned by $B_1,B_2,\dots,B_n$. I claim that if $b_1,\dots,b_n$ are non-zero scalars, then the inverse of $$M=b_1B_1+b_2B_2+\dots + b_nB_n$$ is then the symmetric tridiagonal matrix $$N=c_1C_1+c_2C_2+\dots+c_nC_n$$ where $c_j=b_j^{-1}$ and $C_j$ is the matrix with zero entries except for a block matrix $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ placed along the diagonal of $C_j$ in the $j$th and $j+1$th rows and columns, if $j<n$, and $C_n$ is the matrix with a single non-zero entry, $1$ in the $(n,n)$ position. The point is that $C_jB_k=0$ if $j\ne k$, and $C_jB_j$ is a matrix with at most two non-zero rows: the $j$th row is $(1,1,\dots,1,0,0,\dots)$, with $j$ ones, and if $j<n$ then the $j+1$th row is the negation of the $j$th row. So $NM=C_1B_1+\dots+C_nB_n=I$, so $N=M^{-1}$.

If one of the $b_j$'s is zero, then $M$ not invertible since it's arbitrarily close to matrices whose inverses have arbitrarily large entries.

Addendum: they're called type D matrices, and in fact the inverse of any irreducible nonsingular symmetric tridiagonal matrix is the entrywise product of a type D matrix and a "flipped" type D matrix (start the pattern in the lower right corner rather than the upper left corner). There's also a variant of this result characterising the inverse of arbitrary tridiagonal matrices. This stuff is mentioned in the introduction of this paper by Reinhard Nabben.