Commutation Matrices and Matrix Transposition

Why Transposition Becomes a Permutation

Vectorizing a matrix records its entries in a fixed order. With column-wise vectorization, the first column is listed from top to bottom, followed by the second column, and so on. Transposing the matrix changes where each entry lies, so vectorizing the transpose rearranges the same entries. The commutation matrix is the permutation matrix that performs exactly this rearrangement.

This is useful whenever a matrix expression involves a transpose but the calculation is written in vector form. The key is to keep track of both dimensions: the commutation matrix for an \(m\times n\) matrix is indexed by the input dimensions \(m,n\), and it maps the vectorization of that matrix to the vectorization of its \(n\times m\) transpose.

Definition: Let \(X\) be an \(m\times n\) matrix, and let \(\operatorname{vec}(X)\) stack its columns in order. The commutation matrix \(K_{m,n}\) is the unique \(mn\times mn\) matrix satisfying

K_{m,n}\operatorname{vec}(X)=\operatorname{vec}(X^T)

for every \(m\times n\) matrix \(X\).

The word “commutation” refers to exchanging the order of the two indices attached to each entry: an entry in row \(i\), column \(j\) is moved from the position associated with \((i,j)\) to the position associated with \((j,i)\). The matrix does not change the values of the entries; it only changes their order in the vector.

Deriving the Permutation Structure

Write \(x_{ij}\) for the entry of \(X\) in row \(i\) and column \(j\). In \(\operatorname{vec}(X)\), that entry is at position \(i+(j-1)m\): there are \(j-1\) full columns before column \(j\), each containing \(m\) entries, and \(x_{ij}\) is the \(i\)th entry of column \(j\). In \(X^T\), the same entry is in row \(j\), column \(i\). Therefore, in \(\operatorname{vec}(X^T)\), it is at position \(j+(i-1)n\).

Entry formula: For \(1\leq i\leq m\) and \(1\leq j\leq n\), \(K_{m,n}\) has a 1 in row \(j+(i-1)n\), column \(i+(j-1)m\). Every other entry is 0. Thus every column and every row contains exactly one 1.

An equivalent construction uses standard basis vectors. Let \(e_i^{(m)}\) be the \(i\)th standard basis vector in \(\mathbb{R}^m\), and define \(e_j^{(n)}\) likewise. Since the \(x_{ij}\) contribution to \(\operatorname{vec}(X)\) is \(x_{ij}(e_j^{(n)}\otimes e_i^{(m)})\), and its contribution to \(\operatorname{vec}(X^T)\) is \(x_{ij}(e_i^{(m)}\otimes e_j^{(n)})\), the commutation matrix can be written as

K_{m,n} = \sum_{i=1}^{m}\sum_{j=1}^{n} \left(e_i^{(m)}(e_j^{(n)})^T\right) \otimes \left(e_j^{(n)}(e_i^{(m)})^T\right).

Each summand sends \(e_j^{(n)}\otimes e_i^{(m)}\) to \(e_i^{(m)}\otimes e_j^{(n)}\). This formula makes the rearrangement explicit; the entry formula is often quicker for building a small matrix by hand.

Theorem: The entry formula defines a unique permutation matrix \(K_{m,n}\) satisfying \(K_{m,n}\operatorname{vec}(X)=\operatorname{vec}(X^T)\) for every \(m\times n\) matrix \(X\).

Proof. In the vector \(\operatorname{vec}(X)\), the coordinate at position \(i+(j-1)m\) is \(x_{ij}\). The entry formula places that coordinate into row \(j+(i-1)n\) of the output, with coefficient 1, and places no other nonzero coefficient in that row. But row \(j\), column \(i\) of \(X^T\) is \(x_{ij}\), which occupies position \(j+(i-1)n\) in \(\operatorname{vec}(X^T)\). Thus every output coordinate agrees with \(\operatorname{vec}(X^T)\). As \((i,j)\) ranges over all matrix positions, the source positions and destination positions each range over \(1,\ldots,mn\) exactly once. Hence the matrix has exactly one 1 in each row and column and is a permutation matrix. Finally, the values of a linear map on all coordinate basis vectors determine its matrix uniquely, so no other matrix has the stated action. \(\square\)

Worked Example: Constructing \(K_{2,3}\)

Let \(X=\begin{bmatrix}a&b&c\\d&e&f\end{bmatrix}\). Then \(\operatorname{vec}(X)=[a,d,b,e,c,f]^T\), while \(\operatorname{vec}(X^T)=[a,b,c,d,e,f]^T\). The source positions of \(a,b,c,d,e,f\) are \(1,3,5,2,4,6\), respectively. Therefore, the rows of \(K_{2,3}\) select input coordinates in that order:

K_{2,3}= \begin{bmatrix} 1&0&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&0&1 \end{bmatrix}.

Multiplying gives \(K_{2,3}[a,d,b,e,c,f]^T=[a,b,c,d,e,f]^T\), as required. The matrix is \(6\times6\) because both the original matrix and its transpose have six entries. Its input is ordered as a vectorization of a \(2\times3\) matrix; its output is ordered as a vectorization of a \(3\times2\) matrix.

Inverse, Transpose, and Orthogonality

Transposing twice returns the original matrix. The corresponding statement for commutation matrices is that applying the transposition permutation for an \(m\times n\) matrix and then the one for an \(n\times m\) matrix returns the original vector.

Theorem: For positive integers \(m,n\),

K_{m,n}^T=K_{n,m}, \qquad K_{n,m}K_{m,n}=I_{mn}, \qquad K_{m,n}^{-1}=K_{n,m}.

Consequently, \(K_{m,n}\) is orthogonal: \(K_{m,n}^TK_{m,n}=I_{mn}\).

Proof. A permutation matrix has one 1 in each row and column. Transposing it reverses each row-column assignment, so \(K_{m,n}^T\) sends the coordinate corresponding to entry \((j,i)\) of an \(n\times m\) matrix back to the coordinate for entry \((i,j)\) of an \(m\times n\) matrix. By the defining action, this is precisely \(K_{n,m}\). Alternatively, applying both sides to each coordinate basis vector gives the same result, and those basis vectors determine the matrices.

For any \(m\times n\) matrix \(X\), the defining property gives \(K_{m,n}\operatorname{vec}(X)=\operatorname{vec}(X^T)\). Applying \(K_{n,m}\) then gives \(K_{n,m}K_{m,n}\operatorname{vec}(X)=\operatorname{vec}((X^T)^T)=\operatorname{vec}(X)\). Every vector in \(\mathbb{R}^{mn}\) is \(\operatorname{vec}(X)\) for some \(m\times n\) matrix \(X\), so \(K_{n,m}K_{m,n}=I_{mn}\). This proves that \(K_{n,m}\) is the inverse of \(K_{m,n}\). Combining the inverse relation with \(K_{m,n}^T=K_{n,m}\) gives orthogonality. \(\square\)

When \(m=n\), the input and output dimensions agree, and the theorem implies \(K_{n,n}^T=K_{n,n}\) and \(K_{n,n}^2=I_{n^2}\). When \(m\ne n\), the matrices \(K_{m,n}\) and \(K_{n,m}\) are still both \(mn\times mn\), but they generally represent opposite directions between two different vectorization orders.

Worked Example: The Square Case \(K_{2,2}\)

Take \(X=\begin{bmatrix}a&b\\c&d\end{bmatrix}\). Column-wise vectorization gives \([a,c,b,d]^T\), and vectorizing the transpose gives \([a,b,c,d]^T\). Thus the second and third coordinates must be exchanged:

K_{2,2}= \begin{bmatrix} 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 0&0&0&1 \end{bmatrix}, \qquad K_{2,2} \begin{bmatrix}a\\c\\b\\d\end{bmatrix} = \begin{bmatrix}a\\b\\c\\d\end{bmatrix}.

The displayed matrix is symmetric, so \(K_{2,2}^T=K_{2,2}\). Multiplying it by itself swaps the middle coordinates twice and leaves all four coordinates unchanged, giving \(K_{2,2}^2=I_4\). This is the square-dimension instance of the inverse theorem.

Worked Example: Reversing a Rectangular Transposition

For the \(2\times3\) case, the output order is \([a,b,c,d,e,f]^T\). To return to the original \(2\times3\) column order, the \(3\times2\) commutation matrix selects coordinates \(1,4,2,5,3,6\):

K_{3,2}= \begin{bmatrix} 1&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&1&0&0&0\\ 0&0&0&0&0&1 \end{bmatrix}.

Indeed, \(K_{3,2}[a,b,c,d,e,f]^T=[a,d,b,e,c,f]^T\). Thus \(K_{3,2}K_{2,3}=I_6\). The two commutation matrices are not interchangeable: the first one expects coordinates ordered as \(\operatorname{vec}(X^T)\), while the second expects coordinates ordered as \(\operatorname{vec}(X)\).

Using the Commutation Matrix Reliably

The commutation matrix is a coordinate-conversion device. It is useful in matrix algebra when a derivation has been expressed in terms of vectorized entries but the transpose changes the order being used. It also makes an important structural fact immediate: because \(K_{m,n}\) is a permutation matrix, it preserves the Euclidean length of a vector. In particular, transposition preserves the sum of squared entries:

\|\operatorname{vec}(X^T)\|_2^2 = \|K_{m,n}\operatorname{vec}(X)\|_2^2 = \|\operatorname{vec}(X)\|_2^2.

Both sides are the sum of the squares of all entries of \(X\), in different orders. The conclusion follows because an orthogonal matrix preserves vector length, not because the entries or their positions remain fixed.

Common Mistake: Mixing Up the Dimensions

A common error is to use \(K_{n,m}\) when the input is \(\operatorname{vec}(X)\) for an \(m\times n\) matrix. The reasoning is often “the transpose has \(n\) rows and \(m\) columns, so use \(K_{n,m}\).” That uses the dimensions of the output to label the map. By definition, however, \(K_{m,n}\) takes the vectorization of an \(m\times n\) input to that of its transpose. The reversed matrix \(K_{n,m}\) performs the reverse ordering.

A second source of mistakes is assuming that the input position and output position for \(x_{ij}\) are the same. They are \(i+(j-1)m\) and \(j+(i-1)n\), respectively. Writing down those two positions before placing a 1 in the permutation matrix prevents row-column indexing errors. A useful check is to apply the proposed matrix to a vector with distinct symbols: if every symbol appears exactly once and in the order of the transposed matrix’s column-wise vectorization, the permutation is correct.

Key takeaway: \(K_{m,n}\) is the unique \(mn\times mn\) permutation matrix that converts \(\operatorname{vec}(X)\) into \(\operatorname{vec}(X^T)\). Its entries are determined by matching each element’s source and destination positions, and its inverse is \(K_{n,m}\).

Check Your Understanding

Use column-wise vectorization and the dimensions of the input matrix in each answer.

For a \(3\times2\) matrix, what are the source and destination positions of \(x_{23}\) under transposition?
What are the dimensions of \(K_{4,5}\), and what vector does it map to what vector?
Why does \(K_{m,n}^T=K_{n,m}\) imply that \(K_{m,n}\) preserves vector length?
For which dimensions is \(K_{m,n}\) necessarily symmetric? Explain using its inverse and transpose properties.
Describe the error in using \(K_{3,2}\operatorname{vec}(X)\) when \(X\) is \(2\times3\).