Inverse of a particular sparse matrix

Question

I need to find the inverse of a sparse square matrix that has the following sparsity pattern.

$$\begin{bmatrix} * & * & * & * & * & * & * & * \\ * & * & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & * & * & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & * & * & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & * & * & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & * & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & * & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & * & * \end{bmatrix}$$

Namely, it has non-zero entries only on:

1. the main diagonal,

2. the second diagonal under the main one,

3. the first row.

Everything else is just zero. The matrix is an $n \times n$, full-rank, and well-defined matrix.

The problem I am working on actually requires more general sparse patterns, which means I will probably end up working with some approximation methods to find the inverse. But, for the pattern I have now, I would like to explore the possibility of finding an exact inverse.

Answer 1

Denote the $22$ entries of the matrix $M\in M_8(K)$, for the stars, from left to right as $a_1,a_2,\ldots ,a_{22}$. Then the determinant is given by $$ \det(M)=a_1a_{10}a_{12}a_{14}a_{16}a_{18}a_{20}a_{22} - a_{11}a_{13}a_{15}a_{17}a_{19}a_{21}a_8a_9 + a_{11}a_{13}a_{15}a_{17}a_{19}a_{22}a_7a_9 - a_{11}a_{13}a_{15}a_{17}a_{20}a_{22}a_6a_9 + a_{11}a_{13}a_{15}a_{18}a_{20}a_{22}a_5a_9 - a_{11}a_{13}a_{16}a_{18}a_{20}a_{22}a_4a_9 + a_{11}a_{14}a_{16}a_{18}a_{20}a_{22}a_3a_9 - a_{12}a_{14}a_{16}a_{18}a_2a_{20}a_{22}a_9. $$ Accordingly the inverse matrix can be computed explicitly, but it will have huge polynomials in the entries in general (divided by the determinant). Of course it can be computed by any computer algebra system. For example, the upper left entry of $M^{-1}$ is given by (a nice case) $$ \frac{a_{10}a_{12}a_{14}a_{16}a_{18}a_{20}a_{22}}{\det(M)} $$

However, I don't see an easy explicit formula for arbitrary $n\ge 8$.

Answer 2

Without going into the exact coefficients, we can find a way to construct this inverse. First apply column reduction (by right-multiplication with a matrix) to eliminate the sub-diagonal elements. We end up with the following matrix, where '$*$' still stands for a nonzero element, and '$.$' can be either zero or nonzero: $$A' = \left(\begin{matrix} * & . & . & . & . & . & . & * \\ 0 & * & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & * & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & * & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & * & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & * \end{matrix}\right) $$

Note that this column reduction consists of just $n-1$ elementary steps.

Then by row-reduction, realized by left-multiplication with elementary matrices, you can eliminate the off-diagonal nonzero entries on the first row. This matrix is of the form $$E_r = \left(\begin{matrix} 1 & . & . & . & . & . & . & * \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}\right) $$

Finally (or in an earlier step) you can scale all the diagonal entries to 1 by multiplying with a diagonal matrix $D$.

So we have found a way to construct matrices $E_r$, $E_c$ and $D$ such that $$ D E_r A E_c = I,$$ from which you can derive $$ A^{-1} = E_c D E_r.$$

Let's take $n=4$ and make it explicit, and assume for convenience that the diagonal entries are 1. $$ A = \left(\begin{matrix} 1 & a_{12} & a_{13} & a_{14} \\ a_{21} & 1 & 0 & 0 \\ 0 & a_{32} & 1 & 0 \\ 0 & 0 & a_{43} & 1 \end{matrix}\right). $$

Then we find $$ E_c = \left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -a_{43} & 1 \end{matrix}\right) \left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -a_{32} & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right) \left(\begin{matrix} 1 & 0 & 0 & 0 \\ -a_{21} & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right). $$ Then $$ A E_c = \left(\begin{matrix} b_{11} & b_{12} & b_{13} & a_{14} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right) $$ where $$b_{13} = a_{13} - a_{14} a_{43};$$ $$b_{12} = a_{12} - b_{13} a_{32};$$ $$b_{11} = 1 - b_{12} a_{21}.$$ Note that $b_{11}$ is nonzero by the assumption that the matrix has full rank. Then $$ E_r = \left(\begin{matrix} 1 & -b_{12} & -b_{13} & -a_{14} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right) $$ and finally $$ D = \left(\begin{matrix} 1/b_{11} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right). $$

The trick is to combine row and column reduction steps to get from $A$ to the identity matrix $I$ in a controlled way, i.e. by keeping the matrix sparse along the way. It turns out to be possible for this zero pattern, but it may not be as easy in general.