# A Kronecker Product identity

I want to show the Kronecker Product identity listed on Wikipedia: \begin{align} \mathrm{vec}(AXB) =(B^T \otimes A) \mathrm{vec}(X) \\ \tag{1} \end{align} Wikipedia does not cite references for the proof for (1), and I want to verify. Before the calculation, agree with some convention. Let us denote $$a\; \mathrm{mod}\; b$$ for the remainder of $$a$$ modulo $$b$$ (so that $$9\; \mathrm{mod}\; 4 =1$$). This is unlike the usual practice, but otherwise the expression gets too verbose. Moreover let us denote the $$(i,j)$$-th entry of $$A$$ to be $$A_{i,j}$$, and $$i$$-th entry of $$v$$ to be $$v_{i}$$. Also say that $$A \in \mathbb{R}^{M \cdot N}$$ if it is a $$M$$ by $$N$$ matrix, by slightly abusing the meaning of $$\mathbb{R}$$. If we stick to only addition and multiplication, once the proof works, it works for any field.

Firstly, restate the formal definition of Kronecker product and vectorization, for later use. For $$X' \in \mathbb{R}^{N_2 \cdot N_3}$$ \begin{align} (\mathrm{vec}(X'))_{m_1} =X'_{m_1\; \mathrm{mod}\; N_1, \lceil m_1/N_1 \rceil} \\ \tag{2} \end{align}

For $$A' \in \mathbb{R}^{N_1 \cdot N_2}, B' \in \mathbb{R}^{N_3 \cdot N_4}$$, \begin{align} (A' \otimes B')_{m_1, m_2} =A'_{\lceil m_1/N_3 \rceil, \lceil m_2/N_4 \rceil} B'_{m_1\; \mathrm{mod}\; N_3, m_2\; \mathrm{mod}\; N_4} \\ \tag{3} \end{align}

Now, let $$A \in \mathbb{R}^{N_1 \cdot N_2},\; X \in \mathbb{R}^{N_2 \cdot N_3},\; B \in \mathbb{R}^{N_3 \cdot N_4},$$, We try to evaluate lhs and rhs of (1).

\begin{align} &(\mathrm{vec}(AXB))_{m_1} \\ =&(AXB)_{m_1\; \mathrm{mod}\; N_1, \lceil m_1/N_1 \rceil} \\ =&\sum_{n_2=1}^{N_2} \sum_{n_3=1}^{N_3} A_{m_1\; \mathrm{mod}\; N_1, n_2} X_{n_2, n_3} B_{n_3, \lceil m_1/N_1 \rceil} \\ \tag{4} \end{align}

\begin{align} &((B^T \otimes A) \mathrm{vec}(X) )_{m_1} \\ =&\sum_{m_2=1}^{N_2 N_3} (B^T \otimes A)_{m_1, m_2} \mathrm{vec}(X)_{m_2} \\ =&\sum_{m_2=1}^{N_2 N_3} (B^T)_{\lceil m_1/N_1 \rceil, \lceil m_2/N_2 \rceil} A_{m_1\; \mathrm{mod}\; N_1, m_2\; \mathrm{mod}\; N_2} \mathrm{vec}(X)_{m_2} \\ =&\sum_{m_2=1}^{N_2 N_3} B_{\lceil m_2/N_2 \rceil, \lceil m_1/N_1 \rceil} A_{m_1\; \mathrm{mod}\; N_1, m_2\; \mathrm{mod}\; N_2} X_{m_2\; \mathrm{mod}\; N_2, \lceil m_2/N_2 \rceil} \\ \tag{5} \end{align}

It would seem that we are close, but it is not obvious that (4) and (5) are equal. Although $$A$$'s row index $$m_1\; \mathrm{mod}\; N_1$$ and $$B$$'s column index $$\lceil m_1/N_1 \rceil$$ agree, the other do not. It is suggestive that maybe if we "sum away" $$n_2, n_3$$, we might find them to agree, but $$A,X,B$$ are all free, and we have nothing to exploit to carry out that summation.

First, it helps to note that for any column-vectors $$u,v,$$ we have $$\operatorname{vec}(uv^T) = v \otimes u$$ I think you will find proving this statement to be a useful exercise. In fact, I prefer to take the above equation to be the definition of the vectorization operator (wikipedia defines the operator as "stacking the columns").
Let $$e_1,\dots,e_n$$ denote the canonical basis (i.e. the columns of the $$n \times n$$ identity matrix). Let $$X = (x_{ij})_{i,j = 1}^{m,n}$$. We have \begin{align} \operatorname{vec}(AXB) &= \operatorname{vec}\left(A\left(\sum_{i=1}^m \sum_{j=1}^n x_{ij} e_ie_j^T\right)B\right) \\ & = \sum_{i=1}^m\sum_{j=1}^n x_{ij} \operatorname{vec}(Ae_ie_j^TB) \\ & = \sum_{i=1}^m\sum_{j=1}^nx_{ij} \operatorname{vec}([Ae_i][B^Te_j]^T) \\ &= \sum_{i=1}^m\sum_{j=1}^nx_{ij} [B^Te_j]\otimes [Ae_i] \\ &= (B^T \otimes A)\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} e_j \otimes e_i\right) \\ &= (B^T \otimes A)\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} \operatorname{vec}(e_i e_j^T)\right) \\ &= (B^T \otimes A)\operatorname{vec}\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} e_i e_j^T\right) = (B^T \otimes A)\operatorname{vec}(X) \end{align}
• Nice proof! It might be even clearer to invoke the summation convention and drop all the $\Sigma$'s. – greg Apr 21 at 19:31
• @greg Thanks. And thanks for the suggestion: while I'm sure dropping $\Sigma$s would make the proof less cluttered, I'm sure it would make the proof confusing to those unaccustomed to Einstein notation, and anyway I've never been much of a fan of that convention. Another approach I considered is proving that the statement holds for $X = e_ie_j^T$, then stating that the full result holds "by linearity". – Omnomnomnom Apr 21 at 19:59
I see! In (5), as $$m_2 =1, \dots, N_2 N_3$$, we see that $$m_2\; \mathrm{mod}\; N_2 =1, \dots N_2$$, and $$\lceil m_2/N_2 \rceil =1, \dots N_3$$, same as the numbering of $$n_2, n_3$$ respectively in (4).