Kronecker Products and Vec Operator

The left-hand side has dimensions: $(\mathbf{A} \otimes \mathbf{B}) \in \mathbb{C}^{mp \times nq}$ and $(\mathbf{C} \otimes \mathbf{D}) \in \mathbb{C}^{nq \times rs}$, so the product is in $\mathbb{C}^{mp \times rs}$.

The right-hand side: $\mathbf{A}\mathbf{C} \in \mathbb{C}^{m \times r}$ and $\mathbf{B}\mathbf{D} \in \mathbb{C}^{p \times s}$, so $(\mathbf{A}\mathbf{C}) \otimes (\mathbf{B}\mathbf{D}) \in \mathbb{C}^{mp \times rs}$.

The dimensions match. $\checkmark$

Partition $\mathbf{A} \otimes \mathbf{B}$ into $m \times n$ blocks of size $p \times q$, and $\mathbf{C} \otimes \mathbf{D}$ into $n \times r$ blocks of size $q \times s$.

The $(i,j)$-th block (of size $p \times s$) of the product is obtained by multiplying the $i$-th block row of $\mathbf{A} \otimes \mathbf{B}$ with the $j$-th block column of $\mathbf{C} \otimes \mathbf{D}$: $$\bigl[(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D})\bigr]_{ij} = \sum_{k=1}^{n} (a_{ik}\mathbf{B})(c_{kj}\mathbf{D}) = \sum_{k=1}^{n} a_{ik} c_{kj}\, \mathbf{B}\mathbf{D} = \left(\sum_{k=1}^{n} a_{ik} c_{kj}\right) \mathbf{B}\mathbf{D}.$$

The scalar factor $\sum_{k=1}^{n} a_{ik} c_{kj}$ is precisely the $(i,j)$-th entry of $\mathbf{A}\mathbf{C}$. Therefore $$\bigl[(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D})\bigr]_{ij} = [\mathbf{A}\mathbf{C}]_{ij}\, \mathbf{B}\mathbf{D},$$ which is exactly the $(i,j)$-th block of $(\mathbf{A}\mathbf{C}) \otimes (\mathbf{B}\mathbf{D})$ (by the definition of the Kronecker product).

Since all blocks agree, we conclude $$(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D}) = (\mathbf{A}\mathbf{C}) \otimes (\mathbf{B}\mathbf{D}).\ \quad \blacksquare$$

Write $\mathbf{X} = [\mathbf{x}_1 \mid \cdots \mid \mathbf{x}_p]$. Then $\mathbf{A}\mathbf{X} = [\mathbf{A}\mathbf{x}_1 \mid \cdots \mid \mathbf{A}\mathbf{x}_p]$, so $$\text{vec}(\mathbf{A}\mathbf{X}) = \begin{pmatrix} \mathbf{A}\mathbf{x}_1 \\ \vdots \\ \mathbf{A}\mathbf{x}_p \end{pmatrix} = \begin{pmatrix} \mathbf{A} & & \\ & \ddots & \\ & & \mathbf{A} \end{pmatrix} \begin{pmatrix} \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_p \end{pmatrix} = (\mathbf{I}_p \otimes \mathbf{A})\,\text{vec}(\mathbf{X}).$$ This establishes the identity for the special case $\mathbf{B} = \mathbf{I}_p$.

Let $\mathbf{Y} = \mathbf{A}\mathbf{X}\mathbf{B}$. The $j$-th column of $\mathbf{Y}$ is $$\mathbf{y}_j = \mathbf{A}\mathbf{X}\mathbf{b}_j = \mathbf{A} \sum_{k=1}^{p} b_{kj}\,\mathbf{x}_k = \sum_{k=1}^{p} b_{kj}\,\mathbf{A}\mathbf{x}_k,$$ where $\mathbf{b}_j$ is the $j$-th column of $\mathbf{B}$ and $b_{kj}$ are its entries.

Stacking all $q$ columns: $$\text{vec}(\mathbf{Y}) = \begin{pmatrix} \mathbf{y}_1 \\ \vdots \\ \mathbf{y}_q \end{pmatrix} = \begin{pmatrix} \sum_{k=1}^{p} b_{k1}\,\mathbf{A}\mathbf{x}_k \\ \vdots \\ \sum_{k=1}^{p} b_{kq}\,\mathbf{A}\mathbf{x}_k \end{pmatrix} = \begin{pmatrix} b_{11}\mathbf{A} & b_{21}\mathbf{A} & \cdots & b_{p1}\mathbf{A} \\ b_{12}\mathbf{A} & b_{22}\mathbf{A} & \cdots & b_{p2}\mathbf{A} \\ \vdots & \vdots & \ddots & \vdots \\ b_{1q}\mathbf{A} & b_{2q}\mathbf{A} & \cdots & b_{pq}\mathbf{A} \end{pmatrix} \begin{pmatrix} \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_p \end{pmatrix}.$$ The block matrix has $(j,k)$-th block equal to $b_{kj}\mathbf{A}$. Recalling that $[\mathbf{B}^T]_{jk} = b_{kj}$, this block matrix is precisely $\mathbf{B}^T \otimes \mathbf{A}$ (by definition of the Kronecker product).

The column vector on the right is $\text{vec}(\mathbf{X})$. Therefore $$\text{vec}(\mathbf{A}\mathbf{X}\mathbf{B}) = (\mathbf{B}^T \otimes \mathbf{A})\,\text{vec}(\mathbf{X}). \quad \blacksquare$$

Let $\mathbf{A}\mathbf{v}_i = \lambda_i \mathbf{v}_i$ and $\mathbf{B}\mathbf{w}_j = \mu_j \mathbf{w}_j$. Apply the mixed-product property (TMixed-Product Property of the Kronecker Product) with $\mathbf{C} = \mathbf{v}_i$ (an $m \times 1$ matrix) and $\mathbf{D} = \mathbf{w}_j$ (an $n \times 1$ matrix): $$(\mathbf{A} \otimes \mathbf{B})(\mathbf{v}_i \otimes \mathbf{w}_j) = (\mathbf{A}\mathbf{v}_i) \otimes (\mathbf{B}\mathbf{w}_j) = (\lambda_i \mathbf{v}_i) \otimes (\mu_j \mathbf{w}_j) = \lambda_i \mu_j \,(\mathbf{v}_i \otimes \mathbf{w}_j).$$ Since $\mathbf{v}_i \neq \mathbf{0}$ and $\mathbf{w}_j \neq \mathbf{0}$, the Kronecker product $\mathbf{v}_i \otimes \mathbf{w}_j \neq \mathbf{0}$. Therefore $\lambda_i \mu_j$ is an eigenvalue of $\mathbf{A} \otimes \mathbf{B}$ with eigenvector $\mathbf{v}_i \otimes \mathbf{w}_j$.

We have exhibited $mn$ eigenpairs $(\lambda_i \mu_j,\; \mathbf{v}_i \otimes \mathbf{w}_j)$ for $1 \leq i \leq m$, $1 \leq j \leq n$. Since $\mathbf{A} \otimes \mathbf{B} \in \mathbb{C}^{mn \times mn}$, its characteristic polynomial has degree $mn$, so it has exactly $mn$ eigenvalues (counted with algebraic multiplicity).

It remains to show that the $mn$ vectors $\{\mathbf{v}_i \otimes \mathbf{w}_j\}$ span $\mathbb{C}^{mn}$. If $\{\mathbf{v}_1, \ldots, \mathbf{v}_m\}$ are linearly independent (which holds when $\mathbf{A}$ is diagonalizable) and $\{\mathbf{w}_1, \ldots, \mathbf{w}_n\}$ are linearly independent (which holds when $\mathbf{B}$ is diagonalizable), then $\{\mathbf{v}_i \otimes \mathbf{w}_j\}_{i,j}$ forms a basis of $\mathbb{C}^{mn}$ (a standard result in multilinear algebra; the dimension count gives $mn = mn$). Thus we have found all $mn$ eigenvalues.

For the general case (including non-diagonalizable matrices), we use a continuity/density argument. The set of diagonalizable matrices is dense in $\mathbb{C}^{n \times n}$ (any matrix can be approximated arbitrarily closely by one with distinct eigenvalues, which is necessarily diagonalizable).

The characteristic polynomial $\det(\mathbf{A} \otimes \mathbf{B} - \lambda \mathbf{I}_{mn})$ is a polynomial (hence continuous) function of the entries of $\mathbf{A}$ and $\mathbf{B}$. Since the result holds on the dense set of diagonalizable pairs and eigenvalues are continuous functions of matrix entries, the result extends to all square matrices.

Alternatively, one can verify the identity on characteristic polynomials directly: $$\det(\mathbf{A} \otimes \mathbf{B} - \lambda \mathbf{I}_{mn}) = \prod_{i=1}^{m} \prod_{j=1}^{n} (\lambda_i \mu_j - \lambda),$$ which confirms that the $mn$ roots are exactly $\{\lambda_i \mu_j\}$. $\blacksquare$