Tiny VoltOverview and permutation cycles
For an elementary introduction to permutation matrices, check out this blog post.
We start with understanding the behavior of eigenvalues and eigenvectors of permutation matrices. Then we study a geometrical object, a convex polytope, whose vertices are permutation matrices. Every point inside this polytope is a doubly stochastic matrix. This geometric view leads to the Birkhoff-von Neumann theorem, which characterizes the structure of doubly stochastic matrices. It also leads to the Sinkhorn-Knopp algorithm, which can be used to find a doubly stochastic matrix from a non-negative matrix. This finally leads us to the topic of matrix scaling and culminates in the Sinkhorn distance, a metric on the space of joint probability distributions.
The chain of ideas runs: permutation → permutation cycles → spectral properties → circulant matrix, then Birkhoff polytope → doubly stochastic matrix → Birkhoff-von Neumann, and finally matrix scaling → Sinkhorn distance.
To understand the topics in this series fully, start with viewing a permutation as a product of cycles.
Permutation cycle decomposition
A permutation can be seen as a movement of an element from index to index . One can then create a partition of indices such that the movement of each element is limited to the partition it belongs to. In other words, for any element , both and are in the same partition. This partition is called a cycle.
The permutation can be seen as , one arrow per element carrying it from its old slot to its new one:
- corresponding to the partition .
- corresponding to the partition .
Reordering the columns so that each cycle sits together makes the structure visible: a then splits the -cycle on the left from the -cycle on the right.
Subsequent applications of the same permutation will result in elements shuffling within their partitions in a cyclic manner. The is the number of elements in the partition (assuming no further decomposition is possible). For example, the cycle has order 3, meaning that it will take 3 applications of the permutation to return the elements to their original positions.
Now let's use it to calculate the eigenvalues and eigenvectors of a permutation matrix.