दोगुना स्टोकेस्टिक मैट्रिक्स: Difference between revisions

Revision as of 16:39, 24 July 2023

गणित में, विशेष रूप से संभाव्यता और कॉम्बिनेटरिक्स में, एक दोगुना स्टोचैस्टिक आव्यूह (जिसे बिस्टोचैस्टिक आव्यूह भी कहा जाता है) $X=(x_{ij})$ गैर-ऋणात्मक वास्तविक संख्याओं का एक वर्ग आव्यूह है, जिसकी प्रत्येक पंक्ति और स्तंभ का योग 1 होता है, ^[1] अर्थात,

\sum _{i}x_{ij}=\sum _{j}x_{ij}=1,

इस प्रकार, दोगुना स्टोकेस्टिक आव्यूह बाएं स्टोकेस्टिक आव्यूह और दायां स्टोकेस्टिक दोनों है।^[1]^[2] वास्तव में, कोई भी आव्यूह जो बाएँ और दाएँ दोनों स्टोकेस्टिक है, वर्ग आव्यूह होना चाहिए: यदि प्रत्येक पंक्ति का योग 1 है तो आव्यूह में सभी प्रविष्टियों का योग पंक्तियों की संख्या के समान होना चाहिए, और चूँकि स्तंभों के लिए भी यही बात प्रयुक्त होती है, संख्या पंक्तियों और स्तंभों की संख्या समान होनी चाहिए.^[1]

बिरखॉफ़ पॉलीटोप

$n\times n$ दोगुना स्टोकेस्टिक मैट्रिक्स का वर्ग एक उत्तल पॉलीटोप है जिसे बिरखॉफ पॉलीटोप $B_{n}$ के रूप में जाना जाता है। कार्टेशियन निर्देशांक के रूप में मैट्रिक्स प्रविष्टियों का उपयोग करते हुए, यह $n^{2}$ -आयामी यूक्लिडियन समिष्ट के $(n-1)^{2}$ आयामी एफ़िन उप-समिष्ट में स्थित है, जो $2n-1$ स्वतंत्र रैखिक बाधाओं द्वारा परिभाषित है, जो निर्दिष्ट करता है कि पंक्ति और स्तंभ सभी बराबर हैं। (वहाँ हैं $2n-1$ अतिरिक्त बाधाओं $2n$ क्योंकि इनमें से बाधा निर्भर है, क्योंकि पंक्ति के योग का योग स्तंभ के योग के समान होना चाहिए।) इसके अतिरिक्त, सभी प्रविष्टियाँ गैर-ऋणात्मक और 1 से कम या उसके समान होने के लिए बाध्य हैं।

बिरखॉफ़-वॉन न्यूमैन प्रमेय

बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है^[3]^[4]^[5]) बताता है कि पॉलीटोप $B_{n}$ के सेट का उत्तल पतवार है $n\times n$ क्रमपरिवर्तन आव्यूह, और इसके अतिरिक्त शीर्ष (ज्यामिति)। $B_{n}$ वास्तव में क्रमपरिवर्तन आव्यूह हैं। दूसरे शब्दों में, यदि $X$ दोगुना स्टोकेस्टिक आव्यूह है, तो वहाँ मौजूद है $\theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1$ और क्रमपरिवर्तन आव्यूह $P_{1},\ldots ,P_{k}$ ऐसा है कि

X=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.

(एक्स के ऐसे अपघटन को 'उत्तल संयोजन' के रूप में जाना जाता है।) हॉल के विवाह प्रमेय पर आधारित प्रमेय का प्रमाण डबली स्टोकेस्टिक आव्यूह#बिरखॉफप्रूफ दिया गया है।

इस प्रतिनिधित्व को 'बिरखॉफ़-वॉन न्यूमैन अपघटन' के रूप में जाना जाता है, और यह अद्वितीय नहीं हो सकता है। इसे अक्सर कोनिग के प्रमेय (ग्राफ सिद्धांत) के वास्तविक-मूल्यवान सामान्यीकरण के रूप में वर्णित किया जाता है|कोनिग के प्रमेय, जहां पत्राचार ग्राफ के आसन्न आव्यूह के माध्यम से स्थापित किया जाता है।

अन्य गुण

दो दोहरे स्टोकेस्टिक आव्यूह का उत्पाद दोगुना स्टोकेस्टिक होता है। हालाँकि, गैर-एकवचन दोहरे स्टोकेस्टिक आव्यूह के व्युत्क्रम को दोगुना स्टोकेस्टिक होने की आवश्यकता नहीं है (वास्तव में, यदि इसमें गैर-ऋणात्मक प्रविष्टियाँ हैं तो व्युत्क्रम दोगुना स्टोकेस्टिक है)।
एक इरेड्यूसिबल एपेरियोडिक परिमित मार्कोव श्रृंखला का स्थिर वितरण समान है यदि और केवल यदि इसका संक्रमण आव्यूह दोगुना स्टोकेस्टिक है।
सिंकहॉर्न के प्रमेय में कहा गया है कि कड़ाई से सकारात्मक प्रविष्टियों वाले किसी भी आव्यूह को विकर्ण आव्यूह द्वारा पूर्व और बाद के गुणन द्वारा दोगुना स्टोकेस्टिक बनाया जा सकता है।
के लिए $n=2$ , सभी यूनिस्टोकैस्टिक आव्यूह अनइस्टोकैस्टिक आव्यूह और ऑर्थोस्टोकैस्टिक आव्यूह हैं, लेकिन बड़े के लिए $n$ यह मसला नहीं है।
वैन डेर वेर्डन का अनुमान है कि सभी के बीच न्यूनतम स्थायी (गणित)। n × n दोगुना स्टोकेस्टिक मैट्रिसेस है $n!/n^{n}$ , आव्यूह द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ समान हैं $1/n$ .^[6] इस अनुमान के प्रमाण 1980 में बी. गेयरस द्वारा प्रकाशित किए गए थे^[7] और 1981 में जी. पी. एगोरीचेव द्वारा^[8] और डी. आई. फालिकमैन;^[9] इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।^[10]

बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण

मान लीजिए कि X दोगुना स्टोकेस्टिक आव्यूह है। फिर हम दिखाएंगे कि क्रमपरिवर्तन आव्यूह P मौजूद है जैसे कि x_ij≠0 जब भी प_ij≠ 0. इस प्रकार यदि हम λ को सबसे छोटा x मानते हैं_ijएक गैर-शून्य पी के अनुरूप_ij, अंतर हम शून्य आव्यूह पर पहुंचते हैं, जिस बिंदु पर हमने मूल एक्स के समान क्रमपरिवर्तन आव्यूह का उत्तल संयोजन बनाया होगा।^[3] उदाहरण के लिए यदि $X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}$ तब

 $P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$ ,  $\lambda ={\frac {2}{12}}$ , और
 $X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}$ .

प्रमाण: द्विदलीय ग्राफ बनाएं जिसमें X की पंक्तियाँ भाग में और कॉलम दूसरे भाग में सूचीबद्ध हैं, और किस पंक्ति में i कॉलम j से जुड़ा है यदि x_ij≠ 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.

बाहरी संबंध

[:0-1] 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.

[2] Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 978-0-12-473750-1.

[hetyei-3] 3.0 ^3.1 Birkhoff's theorem, notes by Gábor Hetyei.

[caron-4] 4.0 ^4.1 R. M. Caron et al., 'Nonsquare "Doubly Stochastic" Matrices', 1996.

[jurkat-5] W. B. Jurkat and H. J. Ryser, "Term Ranks and Permanents of Nonnegative Matrices" (1967).

[6] van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.

[7] 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.

[8] 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.

[9] 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).

[10] Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{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>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>
-इस प्रकार, दोगुना [[स्टोकेस्टिक मैट्रिक्स]] बाएं स्टोकेस्टिक मैट्रिक्स और दायां स्टोकेस्टिक दोनों है।<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>
+इस प्रकार, दोगुना [[स्टोकेस्टिक मैट्रिक्स|स्टोकेस्टिक आव्यूह]] बाएं स्टोकेस्टिक आव्यूह और दायां स्टोकेस्टिक दोनों है।<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" />
 ==बिरखॉफ़ पॉलीटोप==
-{{Main|Birkhoff polytope}}
+{{Main|बिरखॉफ़ पॉलीटोप}}
-की कक्षा <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 से कम या उसके बराबर होने के लिए बाध्य हैं।
-== बिरखॉफ़-वॉन न्यूमैन प्रमेय ==
+<math>n\times n</math> दोगुना स्टोकेस्टिक मैट्रिक्स का वर्ग एक [[उत्तल पॉलीटोप]] है जिसे बिरखॉफ पॉलीटोप <math>B_n</math> के रूप में जाना जाता है। कार्टेशियन निर्देशांक के रूप में मैट्रिक्स प्रविष्टियों का उपयोग करते हुए, यह <math>n^2</math>-आयामी यूक्लिडियन समिष्ट के <math>(n-1)^2</math> आयामी एफ़िन उप-समिष्ट में स्थित है, जो <math>2n-1</math> स्वतंत्र रैखिक बाधाओं द्वारा परिभाषित है, जो निर्दिष्ट करता है कि पंक्ति और स्तंभ सभी बराबर हैं। (वहाँ हैं <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> [[क्रमपरिवर्तन मैट्रिक्स]], और इसके अलावा [[शीर्ष (ज्यामिति)]]। <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> ऐसा है कि
+== बिरखॉफ़-वॉन न्यूमैन प्रमेय                                                                     ==
+बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है<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>n=2</math>, सभी [[यूनिस्टोकैस्टिक मैट्रिक्स]] अनइस्टोकैस्टिक मैट्रिक्स और [[ऑर्थोस्टोकैस्टिक मैट्रिक्स]] हैं, लेकिन बड़े के लिए <math>n</math> यह मसला नहीं है।
+* के लिए <math>n=2</math>, सभी [[यूनिस्टोकैस्टिक मैट्रिक्स|यूनिस्टोकैस्टिक आव्यूह]] अनइस्टोकैस्टिक आव्यूह और [[ऑर्थोस्टोकैस्टिक मैट्रिक्स|ऑर्थोस्टोकैस्टिक आव्यूह]] हैं, लेकिन बड़े के लिए <math>n</math> यह मसला नहीं है।
-* वैन डेर वेर्डन का अनुमान है कि सभी के बीच न्यूनतम [[स्थायी (गणित)]]। {{nowrap|''n'' × ''n''}} दोगुना स्टोकेस्टिक मैट्रिसेस है <math>n!/n^n</math>, मैट्रिक्स द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ समान हैं <math>1/n</math>.<ref>{{citation
+* वैन डेर वेर्डन का अनुमान है कि सभी के बीच न्यूनतम [[स्थायी (गणित)]]। {{nowrap|''n'' × ''n''}} दोगुना स्टोकेस्टिक मैट्रिसेस है <math>n!/n^n</math>, आव्यूह द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ समान हैं <math>1/n</math>.<ref>{{citation
   | last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden
   | journal = Jber. Deutsch. Math.-Verein.
@@ Line 78: / Line 77: @@
 ==बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण==
-मान लीजिए कि 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>
+मान लीजिए कि 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>P=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}</math>, <math>\lambda = \frac{2}{12}</math>, और
@@ Line 89: / Line 88: @@
 इस बीच |<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> पंक्ति.
+अधिक स्तंभों और पंक्तियों वाले आव्यूहों का सरल सामान्यीकरण है जैसे कि 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 तक सीमित नहीं है। आर.एम. कैरन एट अल द्वारा अलग सामान्यीकरण (काफ़ी कठिन प्रमाण के साथ) सामने रखा गया है।<ref name=caron>R. M. Caron et al., 'Nonsquare "Doubly Stochastic" Matrices', 1996.</ref>
@@ Line 98: / Line 97: @@
 ==यह भी देखें==
-*स्टोकेस्टिक मैट्रिक्स
+*स्टोकेस्टिक आव्यूह
-*यूनिस्टोचैस्टिक मैट्रिक्स
+*यूनिस्टोचैस्टिक आव्यूह
 *[[बिरखॉफ़ एल्गोरिथम]]

Anonymous

Search

दोगुना स्टोकेस्टिक मैट्रिक्स: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:39, 24 July 2023

Contents

बिरखॉफ़ पॉलीटोप

बिरखॉफ़-वॉन न्यूमैन प्रमेय

अन्य गुण

बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण

सामान्यीकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

दोगुना स्टोकेस्टिक मैट्रिक्स: Difference between revisions

Revision as of 16:39, 24 July 2023

बिरखॉफ़ पॉलीटोप

बिरखॉफ़-वॉन न्यूमैन प्रमेय

अन्य गुण

बिरखॉफ़-वॉन न्यूमैन प्रमेय का प्रमाण

सामान्यीकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories