How to prove this very interesting matrix identity?

Question

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

Answer 1

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.

Answer 2

It seems helpful to rewrite these matrices using Kronecker products. In particular, we have $$ \mathbf A = I_m \otimes \pmatrix{A_1 & \cdots & A_J} = \sum_{k=1}^J I_m \otimes e_k^T \otimes A_k\\ \mathbf B = I_{Jm} \otimes B = I_m \otimes I_J \otimes B \\ \mathbf A' = \pmatrix{I_m \otimes A_1 & \cdots & I_m \otimes A_J} = \sum_{k=1}^J e_k^T \otimes I_m \otimes A_k\\ \mathbf B' = \pmatrix{I_m \otimes e_1 \otimes B & \cdots & I_m \otimes e_J \otimes B} = \sum_{k=1}^J e_k^T \otimes I_m \otimes e_k \otimes B $$ where $I$ is the identity matrix, and $e_i$ is the $i$th column of the identity matrix (in this case, of the size $J$ identity matrix).

With all that said, we can now use the properties of the Kronecker product to compute $$ \mathbf {AB} = [\sum_{k=1}^J I_m \otimes e_k^T \otimes A_k][I_m \otimes I_J \otimes B]\\ = \sum_{k=1}^JI_m \otimes e_k^T \otimes (A_kB)\\ = I_m \otimes \pmatrix{A_1B & \cdots & A_JB} $$ Unfortunately, I'm having trouble performing a similar computation on the product $\mathbf{A'B'}$. However, I still think you will find this useful.

---

The column permutation that takes us from $\mathbf A$ to $\mathbf A'$ can be nicely described by $$ (e_i^{(m)} \otimes e_j^{(J)} \otimes e_k^{(n)})^TC = (e_i^{(J)} \otimes e_j^{(m)} \otimes e_k^{(n)})^T $$ and in fact, we can deduce that $C = C^{-1}$. With that in mind, it seems that you have miscalculated $\mathbf B'$. We should have $$ \mathbf B' = C \mathbf B = \mathbf B $$ So you should find that $\mathbf{AB} = \mathbf{A'B}$.