दोगुना स्टोकेस्टिक मैट्रिक्स

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

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

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

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

Main article: Birkhoff polytope

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

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

बिरखॉफ-वॉन न्यूमैन प्रमेय (अक्सर बिरखॉफ प्रमेय के रूप में जाना जाता है) बताता है कि पॉलीटोप $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$. इस अनुमान के प्रमाण 1980 में बी. गेयरस द्वारा प्रकाशित किए गए थे और 1981 में जी. पी. एगोरीचेव द्वारा और डी. आई. फालिकमैन; इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।

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

मान लीजिए कि X एक दोगुना स्टोकेस्टिक मैट्रिक्स है। फिर हम दिखाएंगे कि एक क्रमपरिवर्तन मैट्रिक्स P मौजूद है जैसे कि x_ij≠0 जब भी प_ij≠ 0. इस प्रकार यदि हम λ को सबसे छोटा x मानते हैं_ijएक गैर-शून्य पी के अनुरूप_ij, अंतर हम शून्य मैट्रिक्स पर पहुंचते हैं, जिस बिंदु पर हमने मूल एक्स के बराबर क्रमपरिवर्तन मैट्रिक्स का उत्तल संयोजन बनाया होगा। उदाहरण के लिए यदि $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 तक सीमित नहीं है। आर.एम. कैरन एट अल द्वारा एक अलग सामान्यीकरण (काफ़ी कठिन प्रमाण के साथ) सामने रखा गया है।

यह भी देखें

• स्टोकेस्टिक मैट्रिक्स
• यूनिस्टोचैस्टिक मैट्रिक्स
• बिरखॉफ़ एल्गोरिथम

संदर्भ

• 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.

बाहरी संबंध

• PlanetMath page on Birkhoff–von Neumann theorem
• PlanetMath page on proof of Birkhoff–von Neumann theorem