दोगुना स्टोकेस्टिक मैट्रिक्स: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|A square matrix}} गणित में, विशेष रूप से संभाव्यता और साहचर्य में, एक...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|A square matrix}} | {{Short description|A square matrix}} | ||
गणित में, विशेष रूप से संभाव्यता और [[साहचर्य]] में, | गणित में, विशेष रूप से संभाव्यता और [[साहचर्य]] में, दोगुना स्टोकेस्टिक मैट्रिक्स | ||
(बिस्टोकैस्टिक मैट्रिक्स भी कहा जाता है) | (बिस्टोकैस्टिक मैट्रिक्स भी कहा जाता है) [[वर्ग मैट्रिक्स]] है <math>X=(x_{ij})</math> अऋणात्मक [[वास्तविक संख्या]]एँ, जिनकी प्रत्येक पंक्ति और स्तंभ का योग 1 होता है,<ref name=":0">{{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}}</ref> अर्थात।, | ||
:<math>\sum_i x_{ij}=\sum_j x_{ij}=1,</math> | :<math>\sum_i x_{ij}=\sum_j x_{ij}=1,</math> | ||
इस प्रकार, | इस प्रकार, दोगुना [[स्टोकेस्टिक मैट्रिक्स]] बाएं स्टोकेस्टिक मैट्रिक्स और दायां स्टोकेस्टिक दोनों है।<ref name=":0" /><ref>{{cite book|last=Marshal, Olkin|title=Inequalities: Theory of Majorization and Its Applications|url=https://archive.org/details/inequalitiestheo00olki_067|url-access=limited|year=1979|isbn=978-0-12-473750-1|pages=[https://archive.org/details/inequalitiestheo00olki_067/page/n26 8]}}</ref> | ||
वास्तव में, कोई भी मैट्रिक्स जो बाएँ और दाएँ दोनों स्टोकेस्टिक है, वर्ग मैट्रिक्स होना चाहिए: यदि प्रत्येक पंक्ति का योग 1 है तो मैट्रिक्स में सभी प्रविष्टियों का योग पंक्तियों की संख्या के बराबर होना चाहिए, और चूँकि स्तंभों के लिए भी यही बात लागू होती है, संख्या पंक्तियों और स्तंभों की संख्या बराबर होनी चाहिए.<ref name=":0" /> | वास्तव में, कोई भी मैट्रिक्स जो बाएँ और दाएँ दोनों स्टोकेस्टिक है, वर्ग मैट्रिक्स होना चाहिए: यदि प्रत्येक पंक्ति का योग 1 है तो मैट्रिक्स में सभी प्रविष्टियों का योग पंक्तियों की संख्या के बराबर होना चाहिए, और चूँकि स्तंभों के लिए भी यही बात लागू होती है, संख्या पंक्तियों और स्तंभों की संख्या बराबर होनी चाहिए.<ref name=":0" /> | ||
| Line 10: | Line 10: | ||
==बिरखॉफ़ पॉलीटोप== | ==बिरखॉफ़ पॉलीटोप== | ||
{{Main|Birkhoff polytope}} | {{Main|Birkhoff polytope}} | ||
की कक्षा <math>n\times n</math> डबली स्टोकेस्टिक मैट्रिसेस | की कक्षा <math>n\times n</math> डबली स्टोकेस्टिक मैट्रिसेस [[उत्तल पॉलीटोप]] है जिसे बिरखॉफ पॉलीटोप के नाम से जाना जाता है <math>B_n</math>. कार्टेशियन निर्देशांक के रूप में मैट्रिक्स प्रविष्टियों का उपयोग करते हुए, यह में निहित है <math>(n-1)^2</math>-आयामी एफ़िन उप-स्थान <math>n^2</math>-आयामी [[ यूक्लिडियन स्थान |यूक्लिडियन स्थान]] द्वारा परिभाषित <math>2n-1</math> स्वतंत्र रैखिक बाधाएँ निर्दिष्ट करती हैं कि पंक्ति और स्तंभ का योग 1 के बराबर है। (वहाँ हैं <math>2n-1</math> बजाय बाधाओं <math>2n</math> क्योंकि इनमें से बाधा निर्भर है, क्योंकि पंक्ति के योग का योग स्तंभ के योग के बराबर होना चाहिए।) इसके अलावा, सभी प्रविष्टियाँ गैर-नकारात्मक और 1 से कम या उसके बराबर होने के लिए बाध्य हैं। | ||
== बिरखॉफ़-वॉन न्यूमैन प्रमेय == | == बिरखॉफ़-वॉन न्यूमैन प्रमेय == | ||
बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है<ref name=hetyei/><ref name=caron/><ref name=jurkat>W. B. Jurkat and H. J. Ryser, "Term Ranks and Permanents of Nonnegative Matrices" (1967).</ref>) बताता है कि पॉलीटोप <math>B_n</math> के सेट का उत्तल पतवार है <math>n\times n</math> [[क्रमपरिवर्तन मैट्रिक्स]], और इसके अलावा [[शीर्ष (ज्यामिति)]]। | बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है<ref name=hetyei/><ref name=caron/><ref name=jurkat>W. B. Jurkat and H. J. Ryser, "Term Ranks and Permanents of Nonnegative Matrices" (1967).</ref>) बताता है कि पॉलीटोप <math>B_n</math> के सेट का उत्तल पतवार है <math>n\times n</math> [[क्रमपरिवर्तन मैट्रिक्स]], और इसके अलावा [[शीर्ष (ज्यामिति)]]। <math>B_n</math> वास्तव में क्रमपरिवर्तन मैट्रिक्स हैं। दूसरे शब्दों में, यदि <math>X</math> दोगुना स्टोकेस्टिक मैट्रिक्स है, तो वहाँ मौजूद है <math>\theta_1,\ldots,\theta_k \ge 0, \sum_{i=1}^k \theta_i = 1</math> और क्रमपरिवर्तन मैट्रिक्स <math>P_1,\ldots,P_k</math> ऐसा है कि | ||
:<math>X = \theta_1 P_1 + \cdots + \theta_k P_k. </math> | :<math>X = \theta_1 P_1 + \cdots + \theta_k P_k. </math> | ||
(एक्स के ऐसे अपघटन को 'उत्तल संयोजन' के रूप में जाना जाता है।) हॉल के विवाह प्रमेय पर आधारित प्रमेय का | (एक्स के ऐसे अपघटन को 'उत्तल संयोजन' के रूप में जाना जाता है।) हॉल के विवाह प्रमेय पर आधारित प्रमेय का प्रमाण डबली स्टोकेस्टिक मैट्रिक्स#बिरखॉफप्रूफ दिया गया है। | ||
इस प्रतिनिधित्व को 'बिरखॉफ़-वॉन न्यूमैन अपघटन' के रूप में जाना जाता है, और यह अद्वितीय नहीं हो सकता है। इसे अक्सर कोनिग के प्रमेय (ग्राफ सिद्धांत) के वास्तविक-मूल्यवान सामान्यीकरण के रूप में वर्णित किया जाता है|कोनिग के प्रमेय, जहां पत्राचार ग्राफ के आसन्न मैट्रिक्स के माध्यम से स्थापित किया जाता है। | इस प्रतिनिधित्व को 'बिरखॉफ़-वॉन न्यूमैन अपघटन' के रूप में जाना जाता है, और यह अद्वितीय नहीं हो सकता है। इसे अक्सर कोनिग के प्रमेय (ग्राफ सिद्धांत) के वास्तविक-मूल्यवान सामान्यीकरण के रूप में वर्णित किया जाता है|कोनिग के प्रमेय, जहां पत्राचार ग्राफ के आसन्न मैट्रिक्स के माध्यम से स्थापित किया जाता है। | ||
==अन्य गुण== | ==अन्य गुण== | ||
* दो दोहरे स्टोकेस्टिक मैट्रिक्स का उत्पाद दोगुना स्टोकेस्टिक होता है। हालाँकि, | * दो दोहरे स्टोकेस्टिक मैट्रिक्स का उत्पाद दोगुना स्टोकेस्टिक होता है। हालाँकि, गैर-एकवचन दोहरे स्टोकेस्टिक मैट्रिक्स के व्युत्क्रम को दोगुना स्टोकेस्टिक होने की आवश्यकता नहीं है (वास्तव में, यदि इसमें गैर-नकारात्मक प्रविष्टियाँ हैं तो व्युत्क्रम दोगुना स्टोकेस्टिक है)। | ||
* एक इरेड्यूसिबल एपेरियोडिक परिमित [[मार्कोव श्रृंखला]] का स्थिर वितरण | * एक इरेड्यूसिबल एपेरियोडिक परिमित [[मार्कोव श्रृंखला]] का स्थिर वितरण समान है यदि और केवल यदि इसका संक्रमण मैट्रिक्स दोगुना स्टोकेस्टिक है। | ||
* सिंकहॉर्न के प्रमेय में कहा गया है कि कड़ाई से सकारात्मक प्रविष्टियों वाले किसी भी मैट्रिक्स को [[विकर्ण मैट्रिक्स]] द्वारा पूर्व और बाद के गुणन द्वारा दोगुना स्टोकेस्टिक बनाया जा सकता है। | * सिंकहॉर्न के प्रमेय में कहा गया है कि कड़ाई से सकारात्मक प्रविष्टियों वाले किसी भी मैट्रिक्स को [[विकर्ण मैट्रिक्स]] द्वारा पूर्व और बाद के गुणन द्वारा दोगुना स्टोकेस्टिक बनाया जा सकता है। | ||
* के लिए <math>n=2</math>, सभी [[यूनिस्टोकैस्टिक मैट्रिक्स]] अनइस्टोकैस्टिक मैट्रिक्स और [[ऑर्थोस्टोकैस्टिक मैट्रिक्स]] हैं, लेकिन बड़े के लिए <math>n</math> यह मसला नहीं है। | * के लिए <math>n=2</math>, सभी [[यूनिस्टोकैस्टिक मैट्रिक्स]] अनइस्टोकैस्टिक मैट्रिक्स और [[ऑर्थोस्टोकैस्टिक मैट्रिक्स]] हैं, लेकिन बड़े के लिए <math>n</math> यह मसला नहीं है। | ||
| Line 76: | Line 76: | ||
| volume = 29 | | volume = 29 | ||
| year = 1981}}.</ref> इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।<ref>[http://www.mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref> | | year = 1981}}.</ref> इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।<ref>[http://www.mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref> | ||
==बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण== | ==बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण== | ||
मान लीजिए कि X | मान लीजिए कि X दोगुना स्टोकेस्टिक मैट्रिक्स है। फिर हम दिखाएंगे कि क्रमपरिवर्तन मैट्रिक्स P मौजूद है जैसे कि x<sub>ij</sub>≠0 जब भी प<sub>ij</sub>≠ 0. इस प्रकार यदि हम λ को सबसे छोटा x मानते हैं<sub>ij</sub>एक गैर-शून्य पी के अनुरूप<sub>ij</sub>, अंतर हम शून्य मैट्रिक्स पर पहुंचते हैं, जिस बिंदु पर हमने मूल एक्स के बराबर क्रमपरिवर्तन मैट्रिक्स का उत्तल संयोजन बनाया होगा।<ref name=hetyei>[https://webpages.uncc.edu/ghetyei/courses/old/F07.3116/birkhofft.pdf Birkhoff's theorem], notes by Gábor Hetyei.</ref> | ||
उदाहरण के लिए यदि <math>X=\frac{1}{12}\begin{pmatrix} 7 & 0 & 5 \\ 2 & 6 & 4 \\ 3 & 6 & 3 \end{pmatrix}</math> तब | उदाहरण के लिए यदि <math>X=\frac{1}{12}\begin{pmatrix} 7 & 0 & 5 \\ 2 & 6 & 4 \\ 3 & 6 & 3 \end{pmatrix}</math> तब | ||
<math>P=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}</math>, <math>\lambda = \frac{2}{12}</math>, और | <math>P=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}</math>, <math>\lambda = \frac{2}{12}</math>, और | ||
<math>X-\lambda P=\frac{1}{12}\begin{pmatrix} 7 & 0 & 3 \\ 0 & 6 & 4 \\ 3 & 4 & 3 \end{pmatrix}</math>. | <math>X-\lambda P=\frac{1}{12}\begin{pmatrix} 7 & 0 & 3 \\ 0 & 6 & 4 \\ 3 & 4 & 3 \end{pmatrix}</math>. | ||
''प्रमाण:'' | ''प्रमाण:'' [[द्विदलीय ग्राफ]] बनाएं जिसमें ''X'' की पंक्तियाँ भाग में और कॉलम दूसरे भाग में सूचीबद्ध हैं, और किस पंक्ति में ''i'' कॉलम ''j'' से जुड़ा है यदि ''x<sub>ij</sub>≠ 0. A को पंक्तियों का कोई भी सेट होने दें, और <i>A</i>' को ग्राफ़ में A में पंक्तियों से जुड़े स्तंभों के सेट के रूप में परिभाषित करें। हम आकार व्यक्त करना चाहते हैं |ए| और |<i>ए</i>'| x के संदर्भ में दो सेटों में से<sub>ij</sub>. | ||
A में प्रत्येक i के लिए, x के <i>A</i>' में j से अधिक का योग<sub>ij</sub>1 है, क्योंकि सभी कॉलम j जिसके लिए x है<sub>ij</sub>≠0 <i>A</i>' में शामिल हैं, और X दोगुना स्टोकेस्टिक है; इसलिए |ए| x के सभी i ∈ A, j ∈ <i>A</i>' का योग है<sub>ij</sub>. | A में प्रत्येक i के लिए, x के <i>A</i>' में j से अधिक का योग<sub>ij</sub>1 है, क्योंकि सभी कॉलम j जिसके लिए x है<sub>ij</sub>≠0 <i>A</i>' में शामिल हैं, और X दोगुना स्टोकेस्टिक है; इसलिए |ए| x के सभी i ∈ A, j ∈ <i>A</i>' का योग है<sub>ij</sub>. | ||
| Line 91: | Line 89: | ||
इस बीच |<i>ए</i>'| x के सभी i (चाहे A में हो या नहीं) और <i>A</i>' के सभी j का योग है<sub>ij</sub>; और यह ≥ संगत योग है जिसमें i, A में पंक्तियों तक सीमित है। इसलिए |<i>A</i>'| ≥|ए|. | इस बीच |<i>ए</i>'| x के सभी i (चाहे A में हो या नहीं) और <i>A</i>' के सभी j का योग है<sub>ij</sub>; और यह ≥ संगत योग है जिसमें i, A में पंक्तियों तक सीमित है। इसलिए |<i>A</i>'| ≥|ए|. | ||
इसका तात्पर्य यह है कि हॉल के विवाह प्रमेय की शर्तें संतुष्ट हैं, और इसलिए हम ग्राफ़ में किनारों का | इसका तात्पर्य यह है कि हॉल के विवाह प्रमेय की शर्तें संतुष्ट हैं, और इसलिए हम ग्राफ़ में किनारों का सेट पा सकते हैं जो एक्स में प्रत्येक पंक्ति को बिल्कुल (विशिष्ट) कॉलम में जोड़ता है। ये किनारे क्रमपरिवर्तन मैट्रिक्स को परिभाषित करते हैं जिनकी गैर-शून्य कोशिकाएं एक्स में गैर-शून्य कोशिकाओं से मेल खाती हैं। | ||
===सामान्यीकरण=== | ===सामान्यीकरण=== | ||
अधिक स्तंभों और पंक्तियों वाले आव्यूहों का | अधिक स्तंभों और पंक्तियों वाले आव्यूहों का सरल सामान्यीकरण है जैसे कि i<sup>वें</sup> पंक्ति का योग r के बराबर है<sub>i</sub>(एक धनात्मक पूर्णांक), स्तंभों का योग 1 के बराबर है, और सभी कोशिकाएँ गैर-ऋणात्मक हैं (पंक्ति योगों का योग स्तंभों की संख्या के बराबर है)। इस रूप में किसी भी मैट्रिक्स को 0s और 1s से बने समान रूप में मैट्रिक्स के उत्तल संयोजन के रूप में व्यक्त किया जा सकता है। इसका प्रमाण i को प्रतिस्थापित करना है<sup>आर द्वारा मूल मैट्रिक्स की वें</sup> पंक्ति<sub>i</sub>अलग-अलग पंक्तियाँ, प्रत्येक r से विभाजित मूल पंक्ति के बराबर<sub>i</sub>; परिणामी वर्ग मैट्रिक्स पर बिरखॉफ़ के प्रमेय को लागू करने के लिए; और अंत में r को योगात्मक रूप से पुनः संयोजित करने के लिए<sub>i</sub>एक ही i में पंक्तियाँ<sup>वें</sup> पंक्ति. | ||
उसी तरह से स्तंभों के साथ-साथ पंक्तियों को भी दोहराना संभव है, लेकिन पुनर्संयोजन का परिणाम आवश्यक रूप से 0s और 1s तक सीमित नहीं है। आर.एम. कैरन एट अल द्वारा | उसी तरह से स्तंभों के साथ-साथ पंक्तियों को भी दोहराना संभव है, लेकिन पुनर्संयोजन का परिणाम आवश्यक रूप से 0s और 1s तक सीमित नहीं है। आर.एम. कैरन एट अल द्वारा अलग सामान्यीकरण (काफ़ी कठिन प्रमाण के साथ) सामने रखा गया है।<ref name=caron>R. M. Caron et al., 'Nonsquare "Doubly Stochastic" Matrices', 1996.</ref> | ||
| Line 112: | Line 110: | ||
* [http://planetmath.org/birkhoffvonneumanntheorem PlanetMath page on Birkhoff–von Neumann theorem] | * [http://planetmath.org/birkhoffvonneumanntheorem PlanetMath page on Birkhoff–von Neumann theorem] | ||
* [http://planetmath.org/proofofbirkhoffvonneumanntheorem PlanetMath page on proof of Birkhoff–von Neumann theorem] | * [http://planetmath.org/proofofbirkhoffvonneumanntheorem PlanetMath page on proof of Birkhoff–von Neumann theorem] | ||
[[Category: मैट्रिसेस]] | [[Category: मैट्रिसेस]] | ||
Revision as of 16:20, 24 July 2023
गणित में, विशेष रूप से संभाव्यता और साहचर्य में, दोगुना स्टोकेस्टिक मैट्रिक्स (बिस्टोकैस्टिक मैट्रिक्स भी कहा जाता है) वर्ग मैट्रिक्स है अऋणात्मक वास्तविक संख्याएँ, जिनकी प्रत्येक पंक्ति और स्तंभ का योग 1 होता है,[1] अर्थात।,
इस प्रकार, दोगुना स्टोकेस्टिक मैट्रिक्स बाएं स्टोकेस्टिक मैट्रिक्स और दायां स्टोकेस्टिक दोनों है।[1][2] वास्तव में, कोई भी मैट्रिक्स जो बाएँ और दाएँ दोनों स्टोकेस्टिक है, वर्ग मैट्रिक्स होना चाहिए: यदि प्रत्येक पंक्ति का योग 1 है तो मैट्रिक्स में सभी प्रविष्टियों का योग पंक्तियों की संख्या के बराबर होना चाहिए, और चूँकि स्तंभों के लिए भी यही बात लागू होती है, संख्या पंक्तियों और स्तंभों की संख्या बराबर होनी चाहिए.[1]
बिरखॉफ़ पॉलीटोप
की कक्षा डबली स्टोकेस्टिक मैट्रिसेस उत्तल पॉलीटोप है जिसे बिरखॉफ पॉलीटोप के नाम से जाना जाता है . कार्टेशियन निर्देशांक के रूप में मैट्रिक्स प्रविष्टियों का उपयोग करते हुए, यह में निहित है -आयामी एफ़िन उप-स्थान -आयामी यूक्लिडियन स्थान द्वारा परिभाषित स्वतंत्र रैखिक बाधाएँ निर्दिष्ट करती हैं कि पंक्ति और स्तंभ का योग 1 के बराबर है। (वहाँ हैं बजाय बाधाओं क्योंकि इनमें से बाधा निर्भर है, क्योंकि पंक्ति के योग का योग स्तंभ के योग के बराबर होना चाहिए।) इसके अलावा, सभी प्रविष्टियाँ गैर-नकारात्मक और 1 से कम या उसके बराबर होने के लिए बाध्य हैं।
बिरखॉफ़-वॉन न्यूमैन प्रमेय
बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है[3][4][5]) बताता है कि पॉलीटोप के सेट का उत्तल पतवार है क्रमपरिवर्तन मैट्रिक्स, और इसके अलावा शीर्ष (ज्यामिति)। वास्तव में क्रमपरिवर्तन मैट्रिक्स हैं। दूसरे शब्दों में, यदि दोगुना स्टोकेस्टिक मैट्रिक्स है, तो वहाँ मौजूद है और क्रमपरिवर्तन मैट्रिक्स ऐसा है कि
(एक्स के ऐसे अपघटन को 'उत्तल संयोजन' के रूप में जाना जाता है।) हॉल के विवाह प्रमेय पर आधारित प्रमेय का प्रमाण डबली स्टोकेस्टिक मैट्रिक्स#बिरखॉफप्रूफ दिया गया है।
इस प्रतिनिधित्व को 'बिरखॉफ़-वॉन न्यूमैन अपघटन' के रूप में जाना जाता है, और यह अद्वितीय नहीं हो सकता है। इसे अक्सर कोनिग के प्रमेय (ग्राफ सिद्धांत) के वास्तविक-मूल्यवान सामान्यीकरण के रूप में वर्णित किया जाता है|कोनिग के प्रमेय, जहां पत्राचार ग्राफ के आसन्न मैट्रिक्स के माध्यम से स्थापित किया जाता है।
अन्य गुण
- दो दोहरे स्टोकेस्टिक मैट्रिक्स का उत्पाद दोगुना स्टोकेस्टिक होता है। हालाँकि, गैर-एकवचन दोहरे स्टोकेस्टिक मैट्रिक्स के व्युत्क्रम को दोगुना स्टोकेस्टिक होने की आवश्यकता नहीं है (वास्तव में, यदि इसमें गैर-नकारात्मक प्रविष्टियाँ हैं तो व्युत्क्रम दोगुना स्टोकेस्टिक है)।
- एक इरेड्यूसिबल एपेरियोडिक परिमित मार्कोव श्रृंखला का स्थिर वितरण समान है यदि और केवल यदि इसका संक्रमण मैट्रिक्स दोगुना स्टोकेस्टिक है।
- सिंकहॉर्न के प्रमेय में कहा गया है कि कड़ाई से सकारात्मक प्रविष्टियों वाले किसी भी मैट्रिक्स को विकर्ण मैट्रिक्स द्वारा पूर्व और बाद के गुणन द्वारा दोगुना स्टोकेस्टिक बनाया जा सकता है।
- के लिए , सभी यूनिस्टोकैस्टिक मैट्रिक्स अनइस्टोकैस्टिक मैट्रिक्स और ऑर्थोस्टोकैस्टिक मैट्रिक्स हैं, लेकिन बड़े के लिए यह मसला नहीं है।
- वैन डेर वेर्डन का अनुमान है कि सभी के बीच न्यूनतम स्थायी (गणित)। n × n दोगुना स्टोकेस्टिक मैट्रिसेस है , मैट्रिक्स द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ समान हैं .[6] इस अनुमान के प्रमाण 1980 में बी. गेयरस द्वारा प्रकाशित किए गए थे[7] और 1981 में जी. पी. एगोरीचेव द्वारा[8] और डी. आई. फालिकमैन;[9] इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।[10]
बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण
मान लीजिए कि X दोगुना स्टोकेस्टिक मैट्रिक्स है। फिर हम दिखाएंगे कि क्रमपरिवर्तन मैट्रिक्स P मौजूद है जैसे कि xij≠0 जब भी पij≠ 0. इस प्रकार यदि हम λ को सबसे छोटा x मानते हैंijएक गैर-शून्य पी के अनुरूपij, अंतर हम शून्य मैट्रिक्स पर पहुंचते हैं, जिस बिंदु पर हमने मूल एक्स के बराबर क्रमपरिवर्तन मैट्रिक्स का उत्तल संयोजन बनाया होगा।[3] उदाहरण के लिए यदि तब
, , और .
प्रमाण: द्विदलीय ग्राफ बनाएं जिसमें X की पंक्तियाँ भाग में और कॉलम दूसरे भाग में सूचीबद्ध हैं, और किस पंक्ति में i कॉलम j से जुड़ा है यदि xij≠ 0. A को पंक्तियों का कोई भी सेट होने दें, और A' को ग्राफ़ में A में पंक्तियों से जुड़े स्तंभों के सेट के रूप में परिभाषित करें। हम आकार व्यक्त करना चाहते हैं |ए| और |ए'| x के संदर्भ में दो सेटों में सेij.
A में प्रत्येक i के लिए, x के A' में j से अधिक का योगij1 है, क्योंकि सभी कॉलम j जिसके लिए x हैij≠0 A' में शामिल हैं, और X दोगुना स्टोकेस्टिक है; इसलिए |ए| x के सभी i ∈ A, j ∈ A' का योग हैij.
इस बीच |ए'| x के सभी i (चाहे A में हो या नहीं) और A' के सभी j का योग हैij; और यह ≥ संगत योग है जिसमें i, A में पंक्तियों तक सीमित है। इसलिए |A'| ≥|ए|.
इसका तात्पर्य यह है कि हॉल के विवाह प्रमेय की शर्तें संतुष्ट हैं, और इसलिए हम ग्राफ़ में किनारों का सेट पा सकते हैं जो एक्स में प्रत्येक पंक्ति को बिल्कुल (विशिष्ट) कॉलम में जोड़ता है। ये किनारे क्रमपरिवर्तन मैट्रिक्स को परिभाषित करते हैं जिनकी गैर-शून्य कोशिकाएं एक्स में गैर-शून्य कोशिकाओं से मेल खाती हैं।
सामान्यीकरण
अधिक स्तंभों और पंक्तियों वाले आव्यूहों का सरल सामान्यीकरण है जैसे कि iवें पंक्ति का योग r के बराबर हैi(एक धनात्मक पूर्णांक), स्तंभों का योग 1 के बराबर है, और सभी कोशिकाएँ गैर-ऋणात्मक हैं (पंक्ति योगों का योग स्तंभों की संख्या के बराबर है)। इस रूप में किसी भी मैट्रिक्स को 0s और 1s से बने समान रूप में मैट्रिक्स के उत्तल संयोजन के रूप में व्यक्त किया जा सकता है। इसका प्रमाण i को प्रतिस्थापित करना हैआर द्वारा मूल मैट्रिक्स की वें पंक्तिiअलग-अलग पंक्तियाँ, प्रत्येक r से विभाजित मूल पंक्ति के बराबरi; परिणामी वर्ग मैट्रिक्स पर बिरखॉफ़ के प्रमेय को लागू करने के लिए; और अंत में r को योगात्मक रूप से पुनः संयोजित करने के लिएiएक ही i में पंक्तियाँवें पंक्ति.
उसी तरह से स्तंभों के साथ-साथ पंक्तियों को भी दोहराना संभव है, लेकिन पुनर्संयोजन का परिणाम आवश्यक रूप से 0s और 1s तक सीमित नहीं है। आर.एम. कैरन एट अल द्वारा अलग सामान्यीकरण (काफ़ी कठिन प्रमाण के साथ) सामने रखा गया है।[4]
यह भी देखें
- स्टोकेस्टिक मैट्रिक्स
- यूनिस्टोचैस्टिक मैट्रिक्स
- बिरखॉफ़ एल्गोरिथम
संदर्भ
- ↑ 1.0 1.1 1.2 Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8.
- ↑ Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 978-0-12-473750-1.
- ↑ 3.0 3.1 Birkhoff's theorem, notes by Gábor Hetyei.
- ↑ 4.0 4.1 R. M. Caron et al., 'Nonsquare "Doubly Stochastic" Matrices', 1996.
- ↑ W. B. Jurkat and H. J. Ryser, "Term Ranks and Permanents of Nonnegative Matrices" (1967).
- ↑ van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
- ↑ Gyires, B. (1980), "The common source of several inequalities concerning doubly stochastic matrices", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, MR 0604006.
- ↑ Egoryčev, G. P. (1980), Reshenie problemy van-der-Vardena dlya permanentov (in Russian), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR 0602332
{{citation}}: CS1 maint: unrecognized language (link). Egorychev, G. P. (1981), "Proof of the van der Waerden conjecture for permanents", Akademiya Nauk SSSR (in Russian), 22 (6): 65–71, 225, MR 0638007{{citation}}: CS1 maint: unrecognized language (link). Egorychev, G. P. (1981), "The solution of van der Waerden's problem for permanents", Advances in Mathematics, 42 (3): 299–305, doi:10.1016/0001-8708(81)90044-X, MR 0642395. - ↑ Falikman, D. I. (1981), "Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix", Akademiya Nauk Soyuza SSR (in Russian), 29 (6): 931–938, 957, MR 0625097
{{citation}}: CS1 maint: unrecognized language (link). - ↑ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
