Kronecker product and the commutation matrix

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.