A short proof of the Farahat-Mirsky refinement of Birkhoff's theorem on doubly-stochastic matrices
Published online by Cambridge University Press: 24 October 2008
Extract
A doubly-stochastic matrix is an n × n matrix with non-negative elements such that each row and each column sums to 1. A permutation matrix is the result of permuting the rows of the unit n × n matrix. Birkhoff's theorem states that the doubly-stochastic matrices constitute the convex hull of the permutation matrices. Using Birkhoff's theorem, Farahat and Mirsky (1) showed that each doubly-stochastic matrix could be expressed as a convex combination of n2 − 2n + 2 permutation matrices, though not in general of fewer. Given Birkhoff's theorem, the Farahat-Mirsky refinement can also be proved quite shortly as follows.
- Type
- Research Notes
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 57 , Issue 3 , July 1961 , pp. 681
- Copyright
- Copyright © Cambridge Philosophical Society 1961
References
REFERENCES
- 4
- Cited by