Kronecker product and the commutation matrix

Solution 1:

Commutation matrices

Lets start with a basic example of a commutation matrix. Let $$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$$ thus $$A^T = \begin{pmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \end{pmatrix}$$ and $$\operatorname{vec}(A) = \begin{pmatrix} a_{11} \\ a_{21} \\ a_{12} \\ a_{22} \end{pmatrix}, ~~~~ \operatorname{vec}(A^T) = \begin{pmatrix} a_{11} \\ a_{12} \\ a_{21} \\ a_{22} \end{pmatrix}.$$ Thus, the commutation matrix $K(2,2)$ is $$K(2,2) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$ since $K(2,2)\operatorname{vec}(A) = \operatorname{vec}(A^T).$

For larger matrices, the commutation matrix will be more complicated, but it will be a permutation matrix. If $a_{ij}$ is the element at row $i$, column $j$ of the $n \times m$ matrix $A$, it will be in position $(j-1)n + i$ in $\operatorname{vec}(A)$. In the $m \times n$ matrix $A^T$ the element will be in row $j$, column $i$ and thus will be in position $(i-1)m + j$ in $\operatorname{vec}(A^T)$.

Note that for $i = j$ (which corresponds to the diagonal elements in a square matrix), the element will be in the same position in both $\operatorname{vec}(A)$ and $\operatorname{vec}(A^T)$.

Thus, the commutation matrix $K(n,m)$ will map the element at position $(j-1)n+i$ to the $(i-1)m + j$:th position. Thus, the $(i-1)m + j$:th row of $K(n,m)$ will have a one in the $(j-1)n+i$:th position, zero in all other places. Put another way, row $k$ will have a one at position $$((k-1) \mod m)n +\left\lfloor \frac{k-1}{m} \right\rfloor + 1.$$

Using this it is straightforward to construct any commutation matrix, e.g.:

$$K(3,2) = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$$

Properties of commutation matrices

From the formula above one can deduce that $K(n,m) = K(m,n)^T$. In particular, $K(n,n)$ is symmetric.

One can also note that $K(n,m)^{-1} = K(m,n)$. This can be seen by taking an arbitrary $n \times m$ matrix $A$. Now, of course: $$K(n,m)\operatorname{vec}(A) = \operatorname{vec}(A^T)$$ Now, $A^T$ is an $m \times n$ matrix and we get: $$K(m,n) \operatorname{vec}(A^T) = \operatorname{vec}(A).$$ Thus, the action of $K(m,n)$ is the inverse of $K(n,m)$ and the matrices are each others inverses.

Kronecker products and commutation matrices

The equation $$K(r,m)(A \otimes B)K(n,q) = B \otimes A$$ is equivalent to $$(A \otimes B)K(n,q) =K(m,r)B \otimes A$$ since $K(r,m)^{-1} = K(m,r)$. Now, pick an arbitrary $X$ and use that $$(A \otimes B) \operatorname{vec}(X) = \operatorname{vec}(BXA^T)$$ (cf. Wikipedia): $$\begin{align} (A \otimes B) K(n,q) \operatorname{vec}(X) &= (A \otimes B) \operatorname{vec}(X^T) = \operatorname{vec}(BX^TA^T) = \\ &= K(m,r) \operatorname{vec}(AXB^T) = K(m,r) (B \otimes A) \operatorname{vec}(X) \end{align}$$ which shows that $$(A \otimes B)K(n,q) =K(m,r)B \otimes A$$ since $X$ was picked arbitrarily, and hence that $$K(r,m)(A \otimes B)K(n,q) = B \otimes A$$ Q.E.D.

Solution 2:

1) The proof of this equality is in the book

J. Magnus and H. Neudecker. Matrix Differential Calculus with Applications in Statistics and Econometrics, Wiley, 1988

on p.55.

2) "To see" the matrix $K(m,n):V_{mn}\to V_{nm}$ you have to choose the base in $V_{mn}$ $$ E_{11},E_{12},\ldots,E_{mn} $$ where $E_{ij}$ is a matrix with $(i,j)^{\rm th}$ entry equals $1$ and others $0$. Since $K(m,n)E_{ij}=E_{ij}^T=E_{ji}$, the columns of $K(m,n)$ are $E_{ji}$.