0
$\begingroup$

I want to invert a non-singular $N\times N$ block matrix $A$ where each $M\times M$ block in $A$ is a diagonal matrix. That is, I have an $N\times N$ block matrix $$ A = \begin{pmatrix} A^{11} & A^{12} & \cdots & \cdots & A^{1N} \\ A^{21} & A^{22} & & & \\ \vdots & & \ddots & & \\ \vdots & & & \ddots & \\ A^{N1} & & & & A^{NN} \end{pmatrix}, $$ where for $i,j \in \{1,\dots,N\}$, each $M\times M$ block $A_{ij}$ is of the form $$ A_{ij} = \begin{pmatrix} a_{11} & 0 & \cdots & \cdots & 0 \\ 0 & a_{22} & & & \\ \vdots & & \ddots & & \\ \vdots & & & \ddots & \\ 0 & & & & a_{MM}. \end{pmatrix} $$

A very simple explicit example where $N=3$ and $M=3$ (with the non-zero diagonals in red for clarity) would be $$ A = \begin{pmatrix} \color{red}{1} & 0 & 0 & \color{red}{2} & 0 & 0 & \color{red}{3} & 0 & 0 \\ 0 & \color{red}{2} & 0 & 0 & \color{red}{3} & 0 & 0 & \color{red}{4} & 0 \\ 0 & 0 & \color{red}{3} & 0 & 0 & \color{red}{4} & 0 & 0 & \color{red}{5} \\ \color{red}{4} & 0 & 0 & \color{red}{5} & 0 & 0 & \color{red}{6} & 0 & 0 \\ 0 & \color{red}{5} & 0 & 0 & \color{red}{6} & 0 & 0 & \color{red}{7} & 0 \\ 0 & 0 & \color{red}{6} & 0 & 0 & \color{red}{7} & 0 & 0 & \color{red}{8} \\ \color{red}{7} & 0 & 0 & \color{red}{8} & 0 & 0 & \color{red}{9} & 0 & 0 \\ 0 & \color{red}{8} & 0 & 0 & \color{red}{9} & 0 & 0 & \color{red}{0} & 0 \\ 0 & 0 & \color{red}{9} & 0 & 0 & \color{red}{0} & 0 & 0 & \color{red}{1} \\ \end{pmatrix}. $$

Is there a special formula for the inverse a matrix like this, i.e. is it possible to obtain a special explicit expression for the inverse of an $N\times N$ block matrix $A$ where each $M\times M$ block in $A$ is a diagonal matrix?

$\endgroup$
  • 1
    $\begingroup$ Permute the rows and columns of $A$ simultaneously to turn $A$ into a block-diagonal matrix. Take the inverse. Then permute back. $\endgroup$ – user1551 Oct 19 '19 at 15:28
  • $\begingroup$ @user1551 "Permute the rows and columns of $A$ simultaneously to turn $A$ into a block-diagonal matrix." How would you do that? $\endgroup$ – amsmath Oct 19 '19 at 15:35
  • $\begingroup$ @amsmath $N=2, M\in \mathbb{N}$ is straightforward using the Schur complement approach to the inverse of a $2\times 2$ block matrix. How it generalize beyond these cases is what I am unsure of. $\endgroup$ – sonicboom Oct 19 '19 at 15:35
  • $\begingroup$ It should be computationally easy to solve, using permutations and such, but it seems there will not usually be nice and simple representation. For $M=2$, link shows that it won't have a nice form even with all the $A^{ij}$ being diagonal. $\endgroup$ – Shiranai Oct 19 '19 at 15:35
  • $\begingroup$ @sonicboom Why is $M=1$ trivial? $\endgroup$ – amsmath Oct 19 '19 at 15:36
1
$\begingroup$

Since user1551 doesn't seem to show up anymore, let me make precise their idea here. Each row of your matrix follows a specific pattern. The first one starts with some entry and then $M-1$ zeros, followed by some entry and then $M-1$ zeros and so on. Let's call this Pattern(1). The next row follows Pattern(2) which is just a shifted version of Pattern(1). And so on until Pattern(M) in the $M$-th row. Then we start again with Pattern(1) in the $(M+1)$-th row. Let's now permute the rows such that we sort by patterns. So, first $N$ times Patten(1), then $N$ times Pattern(2) and so on. Then we obtain a $M\times N$ block matrix with blocks of size $N\times M$: $$ B = \begin{pmatrix} B^{11} & B^{12} & \cdots & \cdots & B^{1N} \\ B^{21} & B^{22} & & & \\ \vdots & & \ddots & & \\ \vdots & & & \ddots & \\ B^{M1} & & & & B^{MN} \end{pmatrix}. $$ Here, for any block-row $k$, $B^{k1},\ldots,B^{kN}$ all have the same form, namely each column being zero except the $k$-th. Now, let us consider the columns of $B$. They are all of the form $$ \begin{bmatrix}v_1\\ \vdots\\ v_M\end{bmatrix} $$ with each $v_j$ being an $N\times 1$-vector and only one of them is not the zero vector. Sorting the columns by pattern will then result in an $M\times M$ block-diagonal matrix with $N\times N$-matrices as entries.

$\endgroup$
  • $\begingroup$ Yes this seems correct. So we perform this process, invert the resulting block-diagonal matrix and 'unperform' the process. Recursive Schur complements could also be used (arxiv.org/pdf/1612.00001.pdf). $\endgroup$ – sonicboom Oct 19 '19 at 17:41
  • $\begingroup$ About the 'unperform' procedure: You find permutation matrices $P$ and $Q$ such that $PAQ$ has the above block-diagonal form. So $A^{-1} = Q(PAQ)^{-1}P$. $\endgroup$ – amsmath Oct 19 '19 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.