Vectorization properties proof

Question

On wikipedia I find the following property for the vectorization. If $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{n \times l}$ then

$$ vec(AB) = (I_l \otimes A) vec(B) = (B^T \otimes I_m) vec(A) $$

I can easily show that $vec(AB) = (I_l \otimes A) vec(B)$ Indeed

$$ vec(AB) = \left( \begin{array}{c} ABe_1 \\ ABe_2 \\ \vdots \\ ABe_n \end{array} \right) = \left( \begin{array}{cccc} A & 0 & \dots & 0 \\ 0 & A & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & A \end{array} \right) vec(B) = \left( I_n \otimes A \right) vec(B) $$

However I don't know how to to prove the other identity. I suspect is something similar to the procedure I followed but I just cannot see it.

Can you help?

Answer 1

First prove it for the case when $l = 1$ i.e. $B$ is a single column. Concretely let $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^{n \times 1}$. Then $$ (b^T \otimes I_m)\text{vec}(A) = \big(b_1I_m \ \cdots \ b_nI_m\big)\begin{pmatrix} &Ae_1 \\ &\vdots \\ &Ae_n \end{pmatrix} = b_1Ae_1 + \cdots + b_n Ae_n = Ab $$ Now consider the general case $A \in \mathbb R^{m \times n}$, $B \in \mathbb R^{n \times l}$ by noting that each $Be_j = B_{\bullet j}$ is a column: $$ \text{vec}(AB) = \begin{pmatrix} &AB_{\bullet 1} \\ &\vdots \\ &AB_{\bullet l} \end{pmatrix} =\begin{pmatrix} &(B_{\bullet 1}^T \otimes I_m)\text{vec}(A) \\ &\vdots \\ &(B_{\bullet l}^T \otimes I_m)\text{vec}(A) \end{pmatrix} = (B^T \otimes I_m)\text{vec}(A) $$

Answer 2

For any $p\times q$ matrix $X$, we use the superscripted expression $X^{p\times q}$ to stress its size when needed.

In general, we have $\operatorname{vec}(MAN)=(N^T\otimes M)\operatorname{vec}(A)$. Since both sides are bilinear in $(M,N)$, it suffices to prove this identity when $M=E_{ij}^{m_1\times m_2}$ and $N=E_{kl}^{n_1\times n_2}$, where $E_{ij} ^{m_1\times m_2} $ denotes the $m_1\times m_2$ matrix whose only nonzero element is a $1$ at the $(i,j)$-th position.

For convenience, let us use $0$-based indexing instead of $1$-based indexing. To prove the identity, let $\{e_0,e_1,\ldots,e_{m_1n_2-1}\}$ be the standard basis of $\mathbb R^{m_1n_2}$. Then $$ \begin{aligned} \left((E_{kl}^{n_1\times n_2})^T\otimes E_{ij}^{m_1\times m_2}\right)\operatorname{vec}(A^{m_2\times n_1}) &=(E_{lk}^{n_2\times n_1}\otimes E_{ij}^{m_1\times m_2})\operatorname{vec}(A^{m_2\times n_1})\\ &=E_{lm_1+i,\,km_2+j}^{n_2m_1\times n_1m_2}\operatorname{vec}(A^{m_2\times n_1})\\ &=\left(\operatorname{vec}(A^{m_2\times n_1})\right)_{km_2+j}\ e_{lm_1+i}\\ &=a_{jk}e_{lm_1+i}\\ &=\operatorname{vec}(a_{jk}E_{il}^{m_1\times n_2})\\ &= \operatorname{vec}(E_{ij}^{m_1\times m_2}A^{m_2\times n_1}E_{kl}^{n_1\times n_2}). \end{aligned} $$