最近接触了一些克罗内克积和 Khatri-Rao Product及向量化的相关问题， 本文记录下非常重要的一个概念： 交换矩阵。

定义

在线性代数中， 有一类矩阵被称为 置换矩阵 (permutation matrix)：

对于一个正方矩阵， 每一行和每一列有且仅有一个非零元素， 就是置换矩阵。

比如：

$$\mathbf{P}=\left[\begin{array}{lll}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$$
显然， 单位阵也是一种特殊的置换矩阵。

关于置换矩阵的作用， 比如我们经常希望更换矩阵$\mathbf{A}$中行或列的排列顺序， 这样的操作可以通过对矩阵$\mathbf{A}$：

• 左乘置换矩阵， 实现对行的重新排列
• 右乘置换矩阵， 实现对列的重新排列

这很容易理解：

$$\left[\begin{array}{lll}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{l}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ {\mathbf{a}}_3\end{array}\right]=\left[\begin{array}{l}{\mathbf{a}}_1\\ {\mathbf{a}}_3\\ {\mathbf{a}}_2\end{array}\right]$$

因此， 置换矩阵就是一类实现对行列重新排列的矩阵。 而其中最常用也最特殊的， 就是 交换矩阵 commutation matrix。

对于一个$m\times n$的矩阵$\mathbf{A}$， 存在一个$mn\times mn$的置换矩阵 ${\mathbf{K}}_{mn}$, 使得${\mathbf{K}}_{mn}\mathrm{v}\mathrm{e}\mathrm{c}(\mathbf{A})=\mathrm{v}\mathrm{e}\mathrm{c}({\mathbf{A}}^T)$， ${\mathbf{K}}_{mn}$就是一个交换矩阵。

性质

常用的性质：

• $K_{mn}\mathrm{vec}(A)=\mathrm{vec}\left(A^{\mathrm{T}}\right)$， ${\mathbf{K}}_{\mathbf{n}m}\mathrm{vec}\left({\mathbf{A}}^{\mathrm{T}}\right)=\mathrm{vec}(\mathbf{A})$
• ${\mathbf{K}}_{mn}^{\mathrm{T}}{\mathbf{K}}_{mn}={\mathbf{K}}_{mn}{\mathbf{K}}_{mn}^{\mathrm{T}}={\mathbf{I}}_{mn}$
• ${\mathbf{K}}_{mn}^{\mathrm{T}}={\mathbf{K}}_{nm}$
• ${\mathbf{K}}_{mn}={\sum }_{j=1}^n\left({\mathbf{e}}_j^{\mathrm{T}}\otimes {\mathbf{I}}_m\otimes {\mathbf{e}}_j\right)$, 其中${\mathbf{e}}_j$ 是基本向量， 即只有第$j$个元素为1，其余元素均为0.

最重要的是则是他与克罗内克积的关系：
$${\mathbf{K}}_{mn}(\mathbf{A}\otimes \mathbf{B}){\mathbf{K}}_{pq}=\mathbf{B}\otimes \mathbf{A}$$

其中， $\mathbf{A}$的维度是 $n\times p$, $\mathbf{B}$的维度是 $m\times q$。

同样还有和Khatri-Rao Product的关系：

$${\mathbf{K}}_{mn}(\mathbf{A}\otimes \mathbf{B})=\mathbf{B}\otimes \mathbf{A}$$

其中， $\mathbf{A}$的维度是 $n\times p$, $\mathbf{B}$的维度是 $m\times p$。
很容易可以从克罗内克积的性质中推导出该式。

代码

附上生成${\mathbf{K}}_{mn}$的matlab代码：

function K = gen_commutation(m,n)

K = 0;
for j = 1 : n
   ej= zeros(n, 1);
   ej(j) = 1;
   K = K + (kron(kron(ej.', eye(m)), ej));
end

即，利用性质4.