mathematics

Sinkhorn's theorem

Sinkhorn's theorem is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Sinkhorn's theorem rather than just read about it. In short: 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 D1 and D2 with strictly positive diagonal elements such that D1AD2 is doubly stochastic.

Key takeaways

Sinkhorn's theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Sinkhorn's theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Sinkhorn's theorem from memory before moving on to harder problems.

Reference excerpt

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 D1 and D2 with strictly positive diagonal elements such that D1AD2 is doubly stochastic. The matrices D1 and D2 are unique up to multiplying the first matrix by a positive number and dividing the second one by the same number.

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. This is essentially the same as the Iterative proportional fitting algorithm, well known in survey statistics. The convergence of the Sinkhorn–Knopp algorithm has been extensively studied . Following these foundational studies, several acceleration techniques have been proposed to improve its performance, such as Arnoldi-type methods .

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. The following extension to maps between matrices is also true (see Theorem 5 and also Theorem 4.7): given a Kraus operator that represents the quantum operation Φ mapping a density matrix into another,

S ↦ Φ ( S ) = ∑ i B i S B i ∗ , {\displaystyle S\mapsto \Phi (S)=\sum _{i}B_{i}SB_{i}^{*},}

that is trace preserving,

∑ i B i ∗ B i = I , {\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 xj, for j in {0,1}, that are positive definite so that the rescaled Kraus operator

S ↦ x 1 Φ ( x 0 − 1 S x 0 − 1 ) x 1 = ∑ i ( x 1 B i x 0 − 1 ) S ( x 1 B i x 0 − 1 ) ∗ {\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,

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

as well as for the adjoint,

x 0 − 1 Φ ∗ ( x 1 I x 1 ) x 0 − 1 = I , {\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. This has been of interest in machine learning because such "Sinkhorn distances" can be used to evaluate the difference between data distributions and permutations. This improves the training of machine learning algorithms, in situations where maximum likelihood training may not be the best method.

References

Worked examples

Example 1 — a first encounter with Sinkhorn's theorem

Start with the simplest possible case. Write down what Sinkhorn's theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Sinkhorn's theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Sinkhorn's theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Sinkhorn's theorem

In research: Sinkhorn's theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Sinkhorn's theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Sinkhorn's theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Matrix theory, Theorems in linear algebra, so understanding it makes those chapters shorter.
In everyday life: Look for Sinkhorn's theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Sinkhorn's theorem” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Sinkhorn's theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Sinkhorn's theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Sinkhorn's theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Sinkhorn's theorem in simple terms?

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 D1 and D2 with strictly positive diagonal elements such that D1AD2 is doubly stocha…

Why does Sinkhorn's theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Sinkhorn's theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Sinkhorn's theorem.