Commutation matrix

Short description: Matrix in linear algebra

Not to be confused with the commutator $AB-BA$ of two square matrices $A$ and $B$ in ring theory.

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:

$\mathrm{vec}(\mathbf{𝐀})=[{\mathbf{𝐀}}_{1,1},\dots ,{\mathbf{𝐀}}_{m,1},{\mathbf{𝐀}}_{1,2},\dots ,{\mathbf{𝐀}}_{m,2},\dots ,{\mathbf{𝐀}}_{1,n},\dots ,{\mathbf{𝐀}}_{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

Properties

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

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

• The determinant of K^(m,n) is $(-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,

${\mathbf{𝐊}}^{(r,m)}(\mathbf{𝐀}\otimes \mathbf{𝐁}){\mathbf{𝐊}}^{(n,q)}=\mathbf{𝐁}\otimes \mathbf{𝐀}.$

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

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

${\mathbf{𝐊}}^{(r,m)}(\mathbf{𝐯}\otimes \mathbf{𝐰})=\mathbf{𝐰}\otimes \mathbf{𝐯}.$

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

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

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

${\mathbf{𝐊}}^{(m,n)}=\left[\begin{array}{ccc}{\mathbf{𝐊}}_{1,1}& \cdots & {\mathbf{𝐊}}_{1,n}\\ ⋮& \ddots & ⋮\\ {\mathbf{𝐊}}_{m,1}& \cdots & {\mathbf{𝐊}}_{m,n},\end{array}\right],$

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

${\mathbf{𝐊}}_{ij}(p,q)=\{\begin{array}{ll}1& i=q\text{ and }j=p,\\ 0& \text{otherwise}.\end{array}$

For example,

${\mathbf{𝐊}}^{(3,4)}=\left[\begin{array}{cccccccccccc}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\\ 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\\ 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:

# 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 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,:);

R

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

Example

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

$A=\left[\begin{array}{cc}1& 4\\ 2& 5\\ 3& 6\\ \end{array}\right].$

$A$ has the following column-major and row-major vectorizations (respectively):

${\mathbf{𝐯}}_{\text{col}}=\mathrm{vec}(A)=\left[\begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\\ 6\\ \end{array}\right],{\mathbf{𝐯}}_{\text{row}}=\mathrm{vec}(A^{\mathrm{T}})=\left[\begin{array}{c}1\\ 4\\ 2\\ 5\\ 3\\ 6\\ \end{array}\right].$

The associated commutation matrix is

$K={\mathbf{𝐊}}^{(3,2)}=\left[\begin{array}{cccccc}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{array}\right],$

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

$K^{\mathrm{T}}K=K{K}^{\mathrm{T}}={\mathbf{𝐈}}_6$

$K{\mathbf{𝐯}}_{\text{col}}={\mathbf{𝐯}}_{\text{row}}$

References

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