Series: From permutations to Sinkhorn

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.
PermutationPermutation cyclesSpectral propertiesCirculant matrixBirkhoff polytopeDoubly stochastic matrixBirkhoff-von NeumannMatrix scalingSinkhorn distance
Relationship between the concepts in this series
To understand most of these topics, it is important to be able to view a permutation as a product of cycles.
Permutation cycle decomposition
A permutation can be seen as a movement of an element x from index x_i to index x_j. One can then create a partition of indices 1, 2, ... n such that the movement of each element in limited to the partition it belongs to. In other words, for any element x, both x_i and x_j are in the same partition. This partition is called a cycle. An example is shown below:
abcdedaebc
Permutation with two cycles: (1, 2, 4)(3, 5)
The permutation \( [a,b,c,d,e] \rightarrow [d,a,e,b,c] \) can be seen as two different permutations happening concurrently:
\( [a,b,d] \rightarrow [d,a,b] \) corresponding to the partition (1, 2, 4).
\( [c,e] \rightarrow [e,c] \) corresponding to the partition (3, 5).
Subsequent applications of the same permutation will result in elements shuffling within their partitions in a cyclic manner. The order of the cycle is the number of elements in the partition (assuming no further decomposition is possible). For example, the cycle (1, 2, 4) 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.