2
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. Yes, for the case n=8 or any known value of n, it's pretty easy to find the inverse by Matlab. But what I'm looking for, is an answer for any given n. Either in an explicit form or using an algorithm. That's the question. $\endgroup$
    – Mokrane
    Commented Jan 1, 2022 at 11:55
  • $\begingroup$ A possible algorithm is, say, Cramer's rule, if we already have the determinant (which can be computed by an algorithm as well of course). $\endgroup$ Commented Jan 1, 2022 at 14:11
  • $\begingroup$ Oh, but this would be very costly. Moreover, this way, we're not making any use of the main property of our matrix, that is, its sparsity! $\endgroup$
    – Mokrane
    Commented Jan 1, 2022 at 17:13
  • $\begingroup$ Yes, there you are right. The determinant is "easy" because of the sparsity, though. $\endgroup$ Commented Jan 1, 2022 at 17:36
  • $\begingroup$ What Guus B did is the way I'm trying to solve it (four days now, stuck in this!). The idea is to decompose the matrix into the product of a couple of elementary matrices, then take the inverse. Unfortunately, it is still not clear to me how he did it, plus, it looks like the 4*4 example Guus B gave isn't accurate. $\endgroup$
    – Mokrane
    Commented Jan 1, 2022 at 17:45
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you very much for your answer. Trying to understand your solution. However, I'm not sure A*Ec in the 4x4 example you gave has zero entries in all the rows under the diagonal. I just calculated it, it does not work! Thanks again. $\endgroup$
    – Mokrane
    Commented Jan 1, 2022 at 17:22
  • $\begingroup$ Isn't (e.g.) element 3,1 of $AE_c$ nonzero in general? $\endgroup$
    – Luca Citi
    Commented Jan 2, 2022 at 0:11
  • $\begingroup$ I think $E_c$ needs to be much more complicated (dense lower triangular) because multiplying column 2 by $-a_{2,1}$ to get rid of $a_{2,1}$ would make the element 3,1 nonzero, therefore you need $E_{c\,3,1}=a_{2,1}a_{3,2}$ but this will make 4,1 nonzero and so you need $E_{c\,4,1}=...$ etc. $\endgroup$
    – Luca Citi
    Commented Jan 2, 2022 at 0:42
  • $\begingroup$ Yes, that's exactly what I noticed. There must be an algorithm for this. Looking up in the literature, i found a good deal of papers providing the explicit exact form of some other sparsity cases of A, like the tridiagonal matrix for example. This algorithm would work well for my matrix if there was no the upper row which is what makes this problem harder. $\endgroup$
    – Mokrane
    Commented Jan 2, 2022 at 0:57
  • $\begingroup$ Indeed, Luca Citi is right. The matrix $E_c$ is more general, but it is still a product of only a few elementary matrices. I will update my answer to correct this. $\endgroup$
    – Guus B
    Commented Jan 2, 2022 at 16:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .