Commutation matrix

In mathematics, especially in linear algebra and matrix theory, the commutation matrix is used for transforming the vectorized form of a matrix into the vectorized form of its transpose. Specifically, the commutation matrix K^(m,n) is the nm ×ばつ mn permutation matrix which, for any m ×ばつ n matrix A, transforms vec(A) into vec(A^T):

K^(m,n) vec(A) = vec(A^T) .

Here vec(A) is the mn ×ばつ 1 column vector obtain by stacking the columns of A on top of one another:

${\displaystyle \operatorname {vec} (\mathbf {A} )=[\mathbf {A} _{1,1},\ldots ,\mathbf {A} _{m,1},\mathbf {A} _{1,2},\ldots ,\mathbf {A} _{m,2},\ldots ,\mathbf {A} _{1,n},\ldots ,\mathbf {A} _{m,n}]^{\mathrm {T} }}${\displaystyle \operatorname {vec} (\mathbf {A} )=[\mathbf {A} _{1,1},\ldots ,\mathbf {A} _{m,1},\mathbf {A} _{1,2},\ldots ,\mathbf {A} _{m,2},\ldots ,\mathbf {A} _{1,n},\ldots ,\mathbf {A} _{m,n}]^{\mathrm {T} }}

where A = [A_i,j]. In other words, vec(A) is the vector obtained by vectorizing A in column-major order. Similarly, vec(A^T) is the vector obtaining by vectorizing A in row-major order. The cycles and other properties of this permutation have been heavily studied for in-place matrix transposition algorithms.

In the context of quantum information theory, the commutation matrix is sometimes referred to as the swap matrix or swap operator ^[1]

• The commutation matrix is a special type of permutation matrix, and is therefore orthogonal. In particular, K^(m,n) is equal to ${\displaystyle \mathbf {P} _{\pi }}${\displaystyle \mathbf {P} _{\pi }}, where ${\displaystyle \pi }${\displaystyle \pi } is the permutation over ${\displaystyle \{1,\dots ,mn\}}${\displaystyle \{1,\dots ,mn\}} for which

${\displaystyle \pi (i+m(j-1))=j+n(i-1),\quad i=1,\dots ,m,\quad j=1,\dots ,n.}${\displaystyle \pi (i+m(j-1))=j+n(i-1),\quad i=1,\dots ,m,\quad j=1,\dots ,n.}

• The determinant of K^(m,n) is ${\displaystyle (-1)^{{\frac {1}{4}}n(n-1)m(m-1)}}${\displaystyle (-1)^{{\frac {1}{4}}n(n-1)m(m-1)}}.
• Replacing A with A^T in the definition of the commutation matrix shows that K^(m,n) = (K^(n,m))^T. Therefore, in the special case of m = n the commutation matrix is an involution and symmetric.
• The main use of the commutation matrix, and the source of its name, is to commute the Kronecker product: for every m ×ばつ n matrix A and every r ×ばつ q matrix B,

${\displaystyle \mathbf {K} ^{(r,m)}(\mathbf {A} \otimes \mathbf {B} )\mathbf {K} ^{(n,q)}=\mathbf {B} \otimes \mathbf {A} .}${\displaystyle \mathbf {K} ^{(r,m)}(\mathbf {A} \otimes \mathbf {B} )\mathbf {K} ^{(n,q)}=\mathbf {B} \otimes \mathbf {A} .}

This property is often used in developing the higher order statistics of Wishart covariance matrices.^[2]

• The case of n=q=1 for the above equation states that for any column vectors v,w of sizes m,r respectively,

${\displaystyle \mathbf {K} ^{(r,m)}(\mathbf {v} \otimes \mathbf {w} )=\mathbf {w} \otimes \mathbf {v} .}${\displaystyle \mathbf {K} ^{(r,m)}(\mathbf {v} \otimes \mathbf {w} )=\mathbf {w} \otimes \mathbf {v} .}

This property is the reason that this matrix is referred to as the "swap operator" in the context of quantum information theory.

• Two explicit forms for the commutation matrix are as follows: if e_r,j denotes the j-th canonical vector of dimension r (i.e. the vector with 1 in the j-th coordinate and 0 elsewhere) then

${\displaystyle \mathbf {K} ^{(r,m)}=\sum _{i=1}^{r}\sum _{j=1}^{m}\left(\mathbf {e} _{r,i}{\mathbf {e} _{m,j}}^{\mathrm {T} }\right)\otimes \left(\mathbf {e} _{m,j}{\mathbf {e} _{r,i}}^{\mathrm {T} }\right)=\sum _{i=1}^{r}\sum _{j=1}^{m}\left(\mathbf {e} _{r,i}\otimes \mathbf {e} _{m,j}\right)\left(\mathbf {e} _{m,j}\otimes \mathbf {e} _{r,i}\right)^{\mathrm {T} }.}${\displaystyle \mathbf {K} ^{(r,m)}=\sum _{i=1}^{r}\sum _{j=1}^{m}\left(\mathbf {e} _{r,i}{\mathbf {e} _{m,j}}^{\mathrm {T} }\right)\otimes \left(\mathbf {e} _{m,j}{\mathbf {e} _{r,i}}^{\mathrm {T} }\right)=\sum _{i=1}^{r}\sum _{j=1}^{m}\left(\mathbf {e} _{r,i}\otimes \mathbf {e} _{m,j}\right)\left(\mathbf {e} _{m,j}\otimes \mathbf {e} _{r,i}\right)^{\mathrm {T} }.}

• The commutation matrix may be expressed as the following block matrix:

${\displaystyle \mathbf {K} ^{(m,n)}={\begin{bmatrix}\mathbf {K} _{1,1}&\cdots &\mathbf {K} _{1,n}\\\vdots &\ddots &\vdots \\\mathbf {K} _{m,1}&\cdots &\mathbf {K} _{m,n},\end{bmatrix}},}${\displaystyle \mathbf {K} ^{(m,n)}={\begin{bmatrix}\mathbf {K} _{1,1}&\cdots &\mathbf {K} _{1,n}\\\vdots &\ddots &\vdots \\\mathbf {K} _{m,1}&\cdots &\mathbf {K} _{m,n},\end{bmatrix}},}

Where the p,q entry of n x m block-matrix K_i,j is given by

${\displaystyle \mathbf {K} _{ij}(p,q)={\begin{cases}1&i=q{\text{ and }}j=p,\0円&{\text{otherwise}}.\end{cases}}}${\displaystyle \mathbf {K} _{ij}(p,q)={\begin{cases}1&i=q{\text{ and }}j=p,\0円&{\text{otherwise}}.\end{cases}}}

For example,

${\displaystyle \mathbf {K} ^{(3,4)}=\left[{\begin{array}{ccc|ccc|ccc|ccc}1&0&0&0&0&0&0&0&0&0&0&0\0円&0&0&1&0&0&0&0&0&0&0&0\0円&0&0&0&0&0&1&0&0&0&0&0\0円&0&0&0&0&0&0&0&0&1&0&0\\\hline 0&1&0&0&0&0&0&0&0&0&0&0\0円&0&0&0&1&0&0&0&0&0&0&0\0円&0&0&0&0&0&0&1&0&0&0&0\0円&0&0&0&0&0&0&0&0&0&1&0\\\hline 0&0&1&0&0&0&0&0&0&0&0&0\0円&0&0&0&0&1&0&0&0&0&0&0\0円&0&0&0&0&0&0&0&1&0&0&0\0円&0&0&0&0&0&0&0&0&0&0&1\end{array}}\right].}${\displaystyle \mathbf {K} ^{(3,4)}=\left[{\begin{array}{ccc|ccc|ccc|ccc}1&0&0&0&0&0&0&0&0&0&0&0\0円&0&0&1&0&0&0&0&0&0&0&0\0円&0&0&0&0&0&1&0&0&0&0&0\0円&0&0&0&0&0&0&0&0&1&0&0\\\hline 0&1&0&0&0&0&0&0&0&0&0&0\0円&0&0&0&1&0&0&0&0&0&0&0\0円&0&0&0&0&0&0&1&0&0&0&0\0円&0&0&0&0&0&0&0&0&0&1&0\\\hline 0&0&1&0&0&0&0&0&0&0&0&0\0円&0&0&0&0&1&0&0&0&0&0&0\0円&0&0&0&0&0&0&0&1&0&0&0\0円&0&0&0&0&0&0&0&0&0&0&1\end{array}}\right].}

For both square and rectangular matrices of m rows and n columns, the commutation matrix can be generated by the code below.

importnumpyasnp
defcomm_mat(m, n):
 # determine permutation applied by K
 w = np.arange(m * n).reshape((m, n), order="F").T.ravel(order="F")
 # apply this permutation to the rows (i.e. to each column) of identity matrix and return result
 return np.eye(m * n)[w, :]

Alternatively, a version without imports:

# Kronecker delta
defdelta(i, j):
 return int(i == j)
defcomm_mat(m, n):
 # determine permutation applied by K
 v = [m * j + i for i in range(m) for j in range(n)]
 # apply this permutation to the rows (i.e. to each column) of identity matrix
 I = [[delta(i, j) for j in range(m * n)] for i in range(m * n)]
 return [I[i] for i in v]

functionP=com_mat(m, n)
% determine permutation applied by K
A=reshape(1:m*n,m,n);
v=reshape(A',1,[]);
% apply this permutation to the rows (i.e. to each column) of identity matrix
P=eye(m*n);
P=P(v,:);

# Sparse matrix version
comm_mat=function(m,n){
i=1:(m*n)
j=NULL
for(kin1:m){
j=c(j,m*0:(n-1)+k)
}
Matrix::sparseMatrix(
i=i,j=j,x=1
)
}

Let ${\displaystyle A}${\displaystyle A} denote the following ${\displaystyle 3\times 2}${\displaystyle 3\times 2} matrix:

${\displaystyle A={\begin{bmatrix}1&4\2円&5\3円&6\\\end{bmatrix}}.}${\displaystyle A={\begin{bmatrix}1&4\2円&5\3円&6\\\end{bmatrix}}.}

${\displaystyle A}${\displaystyle A} has the following column-major and row-major vectorizations (respectively):

${\displaystyle \mathbf {v} _{\text{col}}=\operatorname {vec} (A)={\begin{bmatrix}1\2円\3円\4円\5円\6円\\\end{bmatrix}},\quad \mathbf {v} _{\text{row}}=\operatorname {vec} (A^{\mathrm {T} })={\begin{bmatrix}1\4円\2円\5円\3円\6円\\\end{bmatrix}}.}${\displaystyle \mathbf {v} _{\text{col}}=\operatorname {vec} (A)={\begin{bmatrix}1\2円\3円\4円\5円\6円\\\end{bmatrix}},\quad \mathbf {v} _{\text{row}}=\operatorname {vec} (A^{\mathrm {T} })={\begin{bmatrix}1\4円\2円\5円\3円\6円\\\end{bmatrix}}.}

The associated commutation matrix is

${\displaystyle K=\mathbf {K} ^{(3,2)}={\begin{bmatrix}1&\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &1&\cdot &\cdot \\\cdot &1&\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &1&\cdot \\\cdot &\cdot &1&\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot &1\\\end{bmatrix}},}${\displaystyle K=\mathbf {K} ^{(3,2)}={\begin{bmatrix}1&\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &1&\cdot &\cdot \\\cdot &1&\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &1&\cdot \\\cdot &\cdot &1&\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot &1\\\end{bmatrix}},}

(where each ${\displaystyle \cdot }${\displaystyle \cdot } denotes a zero). As expected, the following holds:

${\displaystyle K^{\mathrm {T} }K=KK^{\mathrm {T} }=\mathbf {I} _{6}}${\displaystyle K^{\mathrm {T} }K=KK^{\mathrm {T} }=\mathbf {I} _{6}}

${\displaystyle K\mathbf {v} _{\text{col}}=\mathbf {v} _{\text{row}}}${\displaystyle K\mathbf {v} _{\text{col}}=\mathbf {v} _{\text{row}}}

• Jan R. Magnus and Heinz Neudecker (1988), Matrix Differential Calculus with Applications in Statistics and Econometrics, Wiley.

• Linear algebra
• Matrices (mathematics)

• Articles with short description
• Short description matches Wikidata
• Articles with example Python (programming language) code
• Articles with example MATLAB/Octave code