Sinkhorn's theorem states that every square matrix with positive entries can be written in a certain standard form.

Theorem

If A is an n × n matrix with strictly positive elements, then there exist diagonal matrices D₁ and D₂ with strictly positive diagonal elements such that D₁AD₂ is doubly stochastic. The matrices D₁ and D₂ are unique modulo multiplying the first matrix by a positive number and dividing the second one by the same number.^{[1] [2]}

Sinkhorn–Knopp algorithm

A simple iterative method to approach the double stochastic matrix is to alternately rescale all rows and all columns of A to sum to 1. Sinkhorn and Knopp presented this algorithm and analyzed its convergence.^[3] This is essentially the same as the Iterative proportional fitting algorithm, well known in survey statistics.

Analogues and extensions

The following analogue for unitary matrices is also true: for every unitary matrix U there exist two diagonal unitary matrices L and R such that LUR has each of its columns and rows summing to 1.^[4]

The following extension to maps between matrices is also true (see Theorem 5^[5] and also Theorem 4.7^[6]): given a Kraus operator that represents the quantum operation Φ mapping a density matrix into another,

${\displaystyle S\mapsto \Phi (S)=\sum _{i}B_{i}SB_{i}^{*},}$

that is trace preserving,

${\displaystyle \sum _{i}B_{i}^{*}B_{i}=I,}$

and, in addition, whose range is in the interior of the positive definite cone (strict positivity), there exist scalings x_j, for j in {0,1}, that are positive definite so that the rescaled Kraus operator

${\displaystyle S\mapsto x_{1}\Phi (x_{0}^{-1}Sx_{0}^{-1})x_{1}=\sum _{i}(x_{1}B_{i}x_{0}^{-1})S(x_{1}B_{i}x_{0}^{-1})^{*}}$

is doubly stochastic. In other words, it is such that both,

${\displaystyle x_{1}\Phi (x_{0}^{-1}Ix_{0}^{-1})x_{1}=I,}$

as well as for the adjoint,

${\displaystyle x_{0}^{-1}\Phi ^{*}(x_{1}Ix_{1})x_{0}^{-1}=I,}$

where I denotes the identity operator.

Applications

In the 2010s Sinkhorn's theorem came to be used to find solutions of entropy-regularised optimal transport problems.^[7] This has been of interest in machine learning because such "Sinkhorn distances" can be used to evaluate the difference between data distributions and permutations.^[8][9][10] This improves the training of machine learning algorithms, in situations where maximum likelihood training may not be the best method.

References