# Vectorization properties proof

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?

• 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 the identity when $M=E_{ij}$ and $N=E_{kl}$, where $E_{ij}$ denotes the matrix whose only nonzero element is a $1$ at the $(i,j)$-th position. Commented Jun 5, 2023 at 2:46
• I was hoping for something a bit more straightforward (like the calculation I have above) than going through a basis. Commented Jun 5, 2023 at 3:27
• Also I just tried with the basis. I just get confused with the calculations. Commented Jun 5, 2023 at 4:13

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)$$
• In your very last equality, why can you factor $\text{vec}(A)$ out (from the right)? Is it just a straight calculation? Commented Jun 5, 2023 at 4:21
• @user8469759 That is a general property of block matrix multiplication $\begin{pmatrix} &x_1^Ty \\ &\vdots \\ &x_n^T y \end{pmatrix} = \begin{pmatrix} &x_1^T \\ &\vdots \\ &x_n^T \end{pmatrix} y$ Commented Jun 5, 2023 at 4:26
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}