Sinkhorn's theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

Theorem[edit]

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 modulo multiplying the first matrix by a positive number and dividing the second one by the same number. [1] [2]

Sinkhorn-Knopp algorithm[edit]

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]

Analogues and Extensions[edit]

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 which represents the quantum operation Φ mapping a density matrix into another,

that is trace preserving,

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

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

as well as for the adjoint,

where I denotes the identity operator.

References[edit]

  1. ^ Sinkhorn, Richard. (1964). "A relationship between arbitrary positive matrices and doubly stochastic matrices." Ann. Math. Statist. 35, 876–879. doi:10.1214/aoms/1177703591
  2. ^ Marshall, A.W., & Olkin, I. (1967). "Scaling of matrices to achieve specified row and column sums." Numerische Mathematik. 12(1), 83–90. doi:10.1007/BF02170999
  3. ^ Sinkhorn, Richard, & Knopp, Paul. (1967). "Concerning nonnegative matrices and doubly stochastic matrices". Pacific J. Math. 21, 343–348.
  4. ^ Idel, Martin; Wolf, Michael M. (2015). "Sinkhorn normal form for unitary matrices". Linear Algebra and its Applications. 471: 76–84. arXiv:1408.5728Freely accessible. doi:10.1016/j.laa.2014.12.031. 
  5. ^ Georgiou, Tryphon; Pavon, Michele (2015). "Positive contraction mappings for classical and quantum Schrödinger systems". Journal of Mathematical Physics. 56: 033301–1–24. arXiv:1405.6650Freely accessible. Bibcode:2015JMP....56c3301G. doi:10.1063/1.4915289. 
  6. ^ Gurvits, Leonid (2004). "Classical complexity and quantum entanglement". Journal of Computational Science. 69: 448–484. doi:10.1016/j.jcss.2004.06.003.