词条 | Doubly stochastic matrix |
释义 |
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,[1] i.e., , Thus, a doubly stochastic matrix is both left stochastic and right stochastic.[1][2] Indeed, any matrix that is both left and right stochastic must be square: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal.[1] Birkhoff polytope and Birkhoff–von Neumann theoremThe class of doubly stochastic matrices is a convex polytope known as the Birkhoff polytope . Using the matrix entries as Cartesian coordinates, it lies in an -dimensional affine subspace of -dimensional Euclidean space defined by independent linear constraints specifying that the row and column sums all equal one. (There are constraints rather than because one of these constraints is dependent, as the sum of the row sums must equal the sum of the column sums.) Moreover, the entries are all constrained to be non-negative and less than or equal to one. The Birkhoff–von Neumann theorem states that this polytope is the convex hull of the set of permutation matrices, and furthermore that the vertices of are precisely the permutation matrices. In other words, if is doubly stochastic matrix, then there exist and permutation matrices such that This representation is known as the Birkhoff–von Neumann decomposition, and it may not be unique in general. By Marcus-Ree theorem, however, there need not be more than terms in any decomposition, namely[3] In other words, while there exists a decomposition with permutation matrices, there is at least one constructible decomposition with no more than matrices. The problem of computing the representation with the minimum number of terms has been shown to be NP-hard, but some heuristics for computing it are known.[4][5] This theorem can be extended for the general stochastic matrix with deterministic transition matrices.[6] Other properties
See also
References1. ^1 2 {{Cite book|title=Markov Chains: From Theory to Implementation and Experimentation|last=Gagniuc|first=Paul A.|publisher=John Wiley & Sons|year=2017|isbn=978-1-119-38755-8|location=USA, NJ|pages=9–11}} 2. ^{{cite book|last=Marshal, Olkin|title=Inequalities: Theory of Majorization and Its Applications|year=1979|isbn=978-0-12-473750-1|pages=8}} 3. ^{{cite journal|last1=Marcus|first1=M.|last2=Ree|first2=R.|title=Diagonals of doubly stochastic matrices|journal=The Quarterly Journal of Mathematics|date=1959|volume=10|issue=1|pages=296–302|doi=10.1093/qmath/10.1.296}} 4. ^{{cite journal|last1=Dufossé|first1=Fanny|last2=Uçar|first2=Bora|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices|journal=Linear Algebra and its Applications|date=May 2016|volume=497|pages=108–115|doi=10.1016/j.laa.2016.02.023}} 5. ^{{Cite journal|last=Dufossé|first=Fanny|last2=Kaya|first2=Kamer|last3=Panagiotas|first3=Ioannis|last4=Uçar|first4=Bora|date=2018|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices|journal=Linear Algebra and its Applications|volume=554|pages=68–78|doi=10.1016/j.laa.2018.05.017|issn=0024-3795}} 6. ^{{Cite journal|last=Ye|first=Felix X.-F.|last2=Wang|first2=Yue|last3=Qian|first3=Hong|title=Stochastic dynamics: Markov chains and random transformations|journal=Discrete and Continuous Dynamical Systems - Series B|volume=21|issue=7|pages=2337–2361|doi=10.3934/dcdsb.2016050|year=2016}} 7. ^{{citation | last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden | journal = Jber. Deutsch. Math.-Verein. | page = 117 | title = Aufgabe 45 | volume = 35 | year = 1926}}. 8. ^{{citation | last = Gyires | first = B. | issue = 3–4 | journal = Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis | mr = 604006 | pages = 291–304 | title = The common source of several inequalities concerning doubly stochastic matrices | volume = 27 | year = 1980}}. 9. ^{{citation | last = Egoryčev | first = G. P. | language = Russian | location = Krasnoyarsk | mr = 602332 | page = 12 | publisher = Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz. | title = Reshenie problemy van-der-Vardena dlya permanentov | year = 1980}}. {{citation | last = Egorychev | first = G. P. | issue = 6 | journal = Akademiya Nauk SSSR | language = Russian | mr = 638007 | pages = 65–71, 225 | title = Proof of the van der Waerden conjecture for permanents | volume = 22 | year = 1981}}. {{citation | last = Egorychev | first = G. P. | doi = 10.1016/0001-8708(81)90044-X | issue = 3 | journal = Advances in Mathematics | mr = 642395 | pages = 299–305 | title = The solution of van der Waerden's problem for permanents | volume = 42 | year = 1981}}. 10. ^{{citation | last = Falikman | first = D. I. | issue = 6 | journal = Akademiya Nauk Soyuza SSR | language = Russian | mr = 625097 | pages = 931–938, 957 | title = Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix | volume = 29 | year = 1981}}. 11. ^Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
External links
1 : Matrices |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。