العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolDOUBLY STOCHASTIC MATRIX
(Redirected from Birkhoff–von Neumann Theorem)
In mathematics, especially in probability and combinatorics, a 'doubly stochastic matrix'
(also called bistochastic),
is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic and right stochastic.
Such a matrix is necessarily a square matrix, by double counting. The class of ''n'' × ''n'' doubly stochastic matrices is a convex polytope in 'R'''N'' (where ''N'' = ''n''2), known as the Birkhoff polytope, ''B''''n''. Its dimension is (''n'' − 1)2, since the line sums being equal to 1 imposes 2''n'' − 1 linear constraints (not 2''n'', because if the total of all ''n'' columns is ''n'', the same must be true of the total of all ''n'' rows).
The principal fact about doubly stochastic matrices is the ''Birkhoff-von Neumann theorem''. This states that the set ''B''''n'' of doubly stochastic matrices of order ''n'' is the convex closure of the set of permutation matrices of the same order, and furthermore that the vertices (extreme points) of ''B''''n'' are precisely the permutation matrices.
★ Stochastic matrix
★ PlanetMath page on Birkhoff-von Neumann theorem
★ PlanetMath page on proof of Birkhoff-von Neumann theorem
In mathematics, especially in probability and combinatorics, a 'doubly stochastic matrix'
(also called bistochastic),
is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic and right stochastic.
Such a matrix is necessarily a square matrix, by double counting. The class of ''n'' × ''n'' doubly stochastic matrices is a convex polytope in 'R'''N'' (where ''N'' = ''n''2), known as the Birkhoff polytope, ''B''''n''. Its dimension is (''n'' − 1)2, since the line sums being equal to 1 imposes 2''n'' − 1 linear constraints (not 2''n'', because if the total of all ''n'' columns is ''n'', the same must be true of the total of all ''n'' rows).
The principal fact about doubly stochastic matrices is the ''Birkhoff-von Neumann theorem''. This states that the set ''B''''n'' of doubly stochastic matrices of order ''n'' is the convex closure of the set of permutation matrices of the same order, and furthermore that the vertices (extreme points) of ''B''''n'' are precisely the permutation matrices.
| Contents |
| See also |
| External links |
See also
★ Stochastic matrix
External links
★ PlanetMath page on Birkhoff-von Neumann theorem
★ PlanetMath page on proof of Birkhoff-von Neumann theorem
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
