Prove this very interesting matrix identity

block matriceslinear algebramatrix decomposition

This is a very interesting identity but I don't know how to prove this,
note that $$A_1,\ldots,A_J,B \in \mathbb{R}^{n \times n}$$
and $m$ is the number of block diagonal in $\mathbf{A}$ ,so consider
$$
\mathbf{A} =
\begin{bmatrix}
A_1 & A_2 & \ldots &A_J & & & & \\
& & & \ddots \\
& & & & A_1 & A_2 & \ldots & A_J
\end{bmatrix} \in \mathbb{R}^{nm\times (Jnm)}$$

$$
\mathbf{B} = \begin{bmatrix}
B & & \\
& \ddots & \\
& & B
\end{bmatrix} \in \mathbb{R}^{(Jnm)\times (Jnm)}$$

$$
\mathbf{A}^\prime =
\left[\begin{smallmatrix}
A_1 & & & & A_2 & & & & \ldots & & & & A_J\\
& A_1 & & & & A_2 & & & & \ldots & & & & A_J\\
& & \ddots & & & & \ddots & & & & \ldots & & & & \ddots \\
& & & A_1 & & & & A_2 & & & & \ldots & & & & A_J
\end{smallmatrix}\right] \in \mathbb{R}^{mn\times (Jmn)}$$

$$
\mathbf{B}^\prime =
\left[\begin{smallmatrix}
\begin{bmatrix}B \\ 0\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \begin{bmatrix}0 \\ B\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \ldots & & & & \begin{bmatrix}0 \\ 0\\ \vdots \\ B \\ \end{bmatrix}\\
& \begin{bmatrix}B \\ 0\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \begin{bmatrix}0 \\ B\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \ldots & & & & \begin{bmatrix}0 \\ 0\\ \vdots \\ B \\ \end{bmatrix}\\
& & \ddots & & & & \ddots & & & & \ldots & & & & \ddots \\
& & & \begin{bmatrix}B \\ 0\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \begin{bmatrix}0 \\ B\\ \vdots \\ 0 \\ \end{bmatrix} & & & & \ldots & & & & \begin{bmatrix}0 \\ 0\\ \vdots \\ B \\ \end{bmatrix}
\end{smallmatrix}\right] \in \mathbb{R}^{Jmn\times (Jmn)}$$

It seems to be true that
$$\mathbf{AB} = \mathbf{A^\prime B^\prime}$$

what I guess might work

From $\mathbf{A}$ to $\mathbf{A}^\prime$ it is a column permutation $\mathbf{C}$, while explicitly find its inverse should give us $$\mathbf{AB} = \mathbf{A CC^{-1} B}= \mathbf{A^\prime B^\prime}$$

But it seems to me, very difficult to write down the $\mathbf{C}$

Update:

It seems that C can be written but well, I can show it is correct by hand-waving way to write it down then…

Best Answer

Let $P$ be the $nmJ\times nmJ$ matrix with $m\times J$ blocks of size $nJ\times nm$ with blocks labeled $P_{i,j}$ for $i=1,\ldots,m$ and $j=1,\ldots,J$.

Define $P_{i,j}$ to be the block matrix of $J\times J$ blocks of size $n\times n$ where the $j,i$ block is the $n\times n$ identity and all other entries are zero.

Note that each row and column of $P$ has exactly one 1. Therefore $P$ is a permutation. Moreover $A' = AP$ and $B' = P^TB$ so that $A'B' = APP^TB = AB$.

For instance, here is $P$ when $J=3$, $m=4$ $$ P = \left[ \begin{array}{cccc|cccc|cccc} I_n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & I_n & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I_n & 0 & 0 & 0 \\ \hline 0 & I_n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & I_n & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I_n & 0 & 0 \\ \hline 0 & 0 & I_n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & I_n & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I_n & 0 \\ \hline 0 & 0 & 0 & I_n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & I_n & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I_n \\ \hline \end{array} \right] $$

However, you still need to verify that $A' = AP$ and $B' = P^TA$ which requires just as much work as directly verifying that $AB = A'B'$. Note that you can just assume that $I_n = 1$ and $A_i = a_i$ since block matrix rules are the same as regular matrix rules.

Related Question