Does it change numerical values?

No. A commutation matrix only permutes entries.

Yes. The commutation matrix has mn rows and mn columns even when A has different numbers of rows and columns.

Is it necessary to store all its zeros?

No. Indexing, sparse representation or array operations usually express the same transformation more efficiently.

AI Glossary / Mathematics and optimization / Intermediate

Commutation matrix

Definition

A commutation matrix is a permutation matrix that rearranges a vectorized matrix into the vectorized form of its transpose. With column-stacking vectorization, K_(m,n) vec(A)=vec(Aᵀ) for every m-by-n matrix A. It changes the order of entries without changing their values and provides a useful algebraic way to express transposition.

What it means

Vectorization turns a matrix into one long vector. Under the convention used here, its first column comes first, followed by its second column, and so on. Transposing the matrix changes which entries belong together in those columns.

The commutation matrix records the required reordering. It contains only zeros and ones, with exactly one one in each row and column. For an m-by-n input matrix it is an mn-by-mn matrix, even when the input is rectangular. Its size can therefore be much larger than the original matrix, although software rarely needs to build it densely.

How it works

An entry Aᵢⱼ appears at position i+(j−1)m in column-stacked vec(A), using one-based indexing. After transposition, the same entry appears at position j+(i−1)n in vec(Aᵀ). Put a one in the corresponding output row and input column of K; all other entries are zero.

Multiplication by K selects each input entry for its new position. Reversing the operation uses K_(n,m), which equals K_(m,n)ᵀ and is its inverse. For square input matrices, the same commutation matrix reverses the operation and is symmetric.

This algebra is useful in matrix derivatives, covariance transformations and identities involving Kronecker products. Actual implementation can use an index permutation or reshape-and-transpose operation. Always state the vectorization convention because row-stacking changes the bookkeeping.

Three practical examples

1. Matrix calculus: express the derivative of a transpose operation as a linear map between vectorized arrays, helping keep dimensions consistent in a larger calculation.

2. Statistical modeling: reorder a covariance matrix when the entries of a random matrix are vectorized under a different orientation.

3. Software interoperability: reconcile array layouts between mathematical formulas and an implementation by checking the exact element permutation rather than relying on matching vector lengths.

Think of it this way

Think of rearranging labeled cards from column-by-column reading order into row-by-row reading order. The cards retain their contents; only their places in the line change.

The analogy ends where a software operation merely changes a view or stride description without physically moving data. The mathematical permutation describes the relationship between orderings, not the memory allocation strategy or runtime cost of a particular library.

Worked example

Consider the original matrix A=[[2,5,8],[3,6,9]]. It has two rows and three columns. Column-stacking gives v=vec(A)=(2,3,5,6,8,9). Its transpose is [[2,3],[5,6],[8,9]], whose column-stacked vector is w=(2,5,8,3,6,9).

Therefore K_(2,3) selects input positions (1,3,5,2,4,6), in that order. Its rows are the corresponding six-coordinate unit row vectors. For example, its second row has a one in column 3 and zeros elsewhere, so the second output entry is v₃=5.

The inverse permutation selects positions (1,4,2,5,3,6) from w, recovering (2,3,5,6,8,9). That inverse is K_(3,2), not generally another application of K_(2,3).

Indeed, applying the original permutation twice gives (2,8,6,5,3,9), which differs from v. This demonstrates why the rectangular dimensions must swap on the return transformation. As another check, the sum of squared entries is 219 in both v and w: reordering preserves Euclidean length. These are hand-checked arithmetic and indexing results, not a claim about a library's default flattening order.

Illustrative case study

Fictional case: an analytics team imports matrix-valued sensor summaries into a statistical model. One component expects entries stacked by columns, while another uses a row-oriented flattening. Both produce vectors of the same length, so ordinary shape checks pass.

The team constructs a small labeled matrix and traces each entry through the pipeline. The resulting permutation identifies the mismatch. It updates both the mean-vector ordering and the covariance ordering together, preventing a superficial fix that would align values but leave their uncertainty attached to the wrong coordinates.

Common misconceptions and mistakes

Do not confuse the commutation matrix with a commutator AB−BA. Nor does it imply that arbitrary matrices satisfy AB=BA.

Do not assume K²=I for every rectangular-input case. The general inverse relation swaps the two dimension labels. For square inputs the same matrix does undo itself.

Do not multiply A directly by K as though their dimensions were automatically compatible. The defining relation acts on vec(A). For complex arrays, ordinary transpose also differs from conjugate transpose: this permutation alone does not conjugate any entries.

Business use

This is mainly an enabling concept for technical teams building statistical, optimization or machine-learning software. A mistaken ordering can silently corrupt a calculation while preserving dimensions and producing plausible numbers.

Document array shapes and stacking conventions at interfaces. Use small uniquely labeled examples to verify transformations. For large arrays, apply the permutation implicitly to avoid a huge dense matrix. If v has covariance Σ and w=Kv, the covariance becomes KΣKᵀ; reordering only one axis would describe a different and generally incorrect relationship.

Check your understanding

Why must the return operation in the example use K_(3,2)?

Answer: After transposition the matrix has three rows and two columns. Reversing its column-stacking transformation therefore uses the swapped dimensions, which define the inverse permutation.

Related terms

Transpose
Kronecker product
Covariance matrix
Matrix calculus
vectorisation
permutation matrix
reshape
commutator

Learn next

construct the four-by-four commutation matrix for a two-by-two input and verify that applying it twice restores the vector. Then repeat with a rectangular input and explicitly compare the forward and inverse permutations.

Sources

Sources: Changqing Xu, “Commutation matrices and Commutation tensors,” definitions and transpose identity read: https://arxiv.org/pdf/1808.04561 . Magnus and Neudecker's foundational paper was located, but the opened scan lacked extractable text: https://www.janmagnus.nl/papers/JRM005.pdf . Column-stacking and dimension conventions are stated explicitly. Examples and fictional case are original; no software execution or performance result is claimed.

Previous: Community cloud Next: Commutativity