最近接触了一些克罗内克积和 Khatri-Rao Product及向量化的相关问题， 本文记录下非常重要的一个概念： 交换矩阵。
定义在线性代数中， 有一类矩阵被称为 置换矩阵 (permutation matrix)：
对于一个正方矩阵， 每一行和每一列有且仅有一个非零元素， 就是置换矩阵。
比如：
P = [ 1 0 0 0 0 1 0 1 0 ] \mathbf{P} =\left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right] P=⎣⎡100001010⎦⎤ 显然， 单位阵也是一种特殊的置换矩阵。
关于置换矩阵的作用， 比如我们经常希望更换矩阵 A \mathbf{A} A中行或列的排列顺序， 这样的操作可以通过对矩阵 A \mathbf{A} A：
- 左乘置换矩阵， 实现对行的重新排列
- 右乘置换矩阵， 实现对列的重新排列
这很容易理解：
[ 1 0 0 0 0 1 0 1 0 ] [ a 1 a 2 a 3 ] = [ a 1 a 3 a 2 ] \left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right]\left[\begin{array}{lll} \mathbf{a}_1 \\ \mathbf{a}_2 \\ \mathbf{a}_3 \end{array}\right] = \left[\begin{array}{lll} \mathbf{a}_1 \\ \mathbf{a}_3 \\ \mathbf{a}_2 \end{array}\right] ⎣⎡100001010⎦⎤⎣⎡a1a2a3⎦⎤=⎣⎡a1a3a2⎦⎤
因此， 置换矩阵就是一类实现对行列重新排列的矩阵。 而其中最常用也最特殊的， 就是 交换矩阵 commutation matrix。
对于一个 m × n m\times n m×n的矩阵 A \mathbf{A} A， 存在一个 m n × m n mn\times mn mn×mn的置换矩阵 K m n \mathbf{K}_{mn} Kmn, 使得 K m n v e c ( A ) = v e c ( A T ) \mathbf{K}_{mn}\mathrm{vec}(\mathbf{A}) = \mathrm{vec}(\mathbf{A}^T) Kmnvec(A)=vec(AT)， K m n \mathbf{K}_{mn} Kmn就是一个交换矩阵。
性质常用的性质：
- K m n vec ( A ) = vec ( A T ) K_{m n} \operatorname{vec}(A)=\operatorname{vec}\left(A^{\mathrm{T}}\right) Kmnvec(A)=vec(AT)， K n m vec ( A T ) = vec ( A ) \boldsymbol{K}_{\boldsymbol{n} m} \operatorname{vec}\left(\boldsymbol{A}^{\mathrm{T}}\right)=\operatorname{vec}(\boldsymbol{A}) Knmvec(AT)=vec(A)
- K m n T K m n = K m n K m n T = I m n \boldsymbol{K}_{m n}^{\mathrm{T}} \boldsymbol{K}_{m n}=\boldsymbol{K}_{m n} \boldsymbol{K}_{m n}^{\mathrm{T}}=\boldsymbol{I}_{m n} KmnTKmn=KmnKmnT=Imn
- K m n T = K n m \mathbf{K}_{m n}^{\mathrm{T}}=\mathbf{K}_{n m} KmnT=Knm
- K m n = ∑ j = 1 n ( e j T ⊗ I m ⊗ e j ) \boldsymbol{K}_{m n}=\sum_{j=1}^{n}\left(\mathbf{e}_{j}^{\mathrm{T}} \otimes \mathbf{I}_{m} \otimes \mathbf{e}_{j}\right) Kmn=∑j=1n(ejT⊗Im⊗ej), 其中 e j \mathbf{e}_{j} ej 是基本向量， 即只有第 j j j个元素为1，其余元素均为0.
最重要的是则是他与克罗内克积的关系： K m n ( A ⊗ B ) K p q = B ⊗ A \boldsymbol{K}_{m n}(\boldsymbol{A} \otimes \boldsymbol{B}) \boldsymbol{K}_{p q}=\boldsymbol{B} \otimes \boldsymbol{A} Kmn(A⊗B)Kpq=B⊗A
其中， A \mathbf{A} A的维度是 n × p n\times p n×p, B \mathbf{B} B的维度是 m × q m\times q m×q。
同样还有和Khatri-Rao Product的关系：
K m n ( A ⊗ B ) = B ⊗ A \boldsymbol{K}_{m n}(\boldsymbol{A} \otimes \boldsymbol{B}) =\boldsymbol{B} \otimes \boldsymbol{A} Kmn(A⊗B)=B⊗A
其中， A \mathbf{A} A的维度是 n × p n\times p n×p, B \mathbf{B} B的维度是 m × p m\times p m×p。 很容易可以从克罗内克积的性质中推导出该式。
代码附上生成 K m n \mathbf{K}_{mn} Kmn的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.
