Commutation matrix explained

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 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:

\operatorname{vec}( A ) = [ A _{1,1} , \ldots, A _{m,1} , A _{1,2} , \ldots, A _{m,2} , \ldots, A _{1,n} , \ldots, A _{m,n} ] ^{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.

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

Properties

• The commutation matrix is a special type of permutation matrix, and is therefore orthogonal. In particular, K^(m,n) is equal to

P _{\pi} , where \pi is the permutation over \{ 1 , ... ,mn\} for which\pi(i + m(j -1 )) = j + n(i -1 ), i = 1 , ... ,m, j = 1 , ... ,n.

• Replacing A with A^T in the definition of the commutation matrix shows that 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,

K ^{(r,} ( A ⊗ B ) K ^{(n,} = B ⊗ 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,

K ^{(r,m)} ( v ⊗ w) = w ⊗ 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

K ^{(r,} = \sum ^{r} _{i =1} \sum ^{m} _{j =1} \left( e _{r,i} { e _{m,j} }^\right) \otimes \left(\mathbf_ ^\right)= \sum_^r \sum_^m \left(\mathbf_ \otimes \mathbf_\right) \left(\mathbf_ \otimes \mathbf_\right)^.

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

K ^{(m,n)} = \begin{bmatrix} K _{1,1} & … & K _{1,n} \\ \vdots & \ddots & \vdots\\ K _{m,1} & … & K _{m,n} , \end{bmatrix},

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

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

For example,

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].

Code

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

Python

import numpy as np

def comm_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:

1. Kronecker delta

def delta(i, j): return int(i

j)

def comm_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]

MATLAB

function P = com_mat(m, n)

% determine permutation applied by KA = reshape(1:m*n, m, n);v = reshape(A', 1, []);

% apply this permutation to the rows (i.e. to each column) of identity matrixP = eye(m*n);P = P(v,:);

R

1. Sparse matrix version

comm_mat = function(m, n)

Example

Let

A denote the following 3 x 2 matrix:A = \begin{bmatrix} 1 & 4 \ 2 & 5 \\ 3 & 6 \\ \end{bmatrix}. A has the following column-major and row-major vectorizations (respectively):v _{col} = \operatorname{vec}(A) = \begin{bmatrix} 1 \ 2 \\ 3 \\ 4 \ 5 \ 6 \ \end{bmatrix} , v _{row} = \operatorname{vec}(A ^{T} ) = \begin{bmatrix} 1 \ 4 \\ 2 \\ 5 \ 3 \ 6 \ \end{bmatrix}.

The associated commutation matrix is

K = K ^{(3,2)} = \begin{bmatrix} 1 & ⋅ & ⋅ & ⋅ & ⋅ & ⋅ \\ ⋅ & ⋅ & ⋅ & 1 & ⋅ & ⋅ \\ ⋅ & 1 & ⋅ & ⋅ & ⋅ & ⋅ \\ ⋅ & ⋅ & ⋅ & ⋅ & 1 & ⋅ \\ ⋅ & ⋅ & 1 & ⋅ & ⋅ & ⋅ \\ ⋅ & ⋅ & ⋅ & ⋅ & ⋅ & 1 \\ \end{bmatrix}, (where each ⋅ denotes a zero). As expected, the following holds:K ^{T} K = KK ^{T} = I _{6} K v _{col} = v _{row}

References

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

Notes and References

1. Book: Watrous, John. 2018. The Theory of Quantum Information. Cambridge University Press. 94.
2. von Rosen. Dietrich. 1988. Moments for the Inverted Wishart Distribution. Scand. J. Stat.. 15. 97–109.