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

Revision as of 17:10, 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 9: / Line 9: @@
 {{Main|बिरखॉफ़ पॉलीटोप}}
-<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 से कम या उसके समान होने के लिए बाध्य हैं।
+<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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 17:10, 24 July 2023

Contents

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

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

अन्य गुण

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

सामान्यीकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 17:10, 24 July 2023

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

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

अन्य गुण

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

सामान्यीकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories