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

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

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

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

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

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

$n\times n$ दोगुना स्टोकेस्टिक आव्यूह का वर्ग एक उत्तल पॉलीटोप है जिसे बिरखॉफ पॉलीटोप $B_{n}$ के रूप में जाना जाता है। कार्टेशियन निर्देशांक के रूप में आव्यूह प्रविष्टियों का उपयोग करते हुए, यह $n^{2}$-आयामी यूक्लिडियन समिष्ट के $(n-1)^{2}$ आयामी एफ़िन उप-समिष्ट में स्थित है, जो $2n-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}.$

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

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

अन्य गुण

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

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

मान लीजिए कि X दोगुना स्टोकेस्टिक आव्यूह है। फिर हम दिखाएंगे कि क्रमपरिवर्तन आव्यूह P उपस्थित है जैसे कि x_ij≠0 जब भी p_ij≠ 0. इस प्रकार यदि हम λ को सबसे छोटा x_ij मानते हैं एक गैर-शून्य p_ij, के अनुरूप अंतर हम शून्य आव्यूह पर पहुंचते हैं, जिस बिंदु पर हमने मूल X के समान क्रमपरिवर्तन आव्यूह का उत्तल संयोजन बनाया गया था।

उदाहरण के लिए यदि $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 में पंक्तियों से जुड़े स्तंभों के समुच्चय के रूप में परिभाषित करें। हम आकार व्यक्त करना चाहते हैं |a| और |a| x_ij के संदर्भ में दो समुच्चयों में से. A में प्रत्येक i के लिए, x के A_ij' में j से अधिक का योग 1 है, क्योंकि सभी कॉलम j जिसके लिए x_ij≠0 A में सम्मिलित हैं, और X दोगुना स्टोकेस्टिक है; इसलिए |a| x के सभी i ∈ A, j ∈ A_ij' का योग है.

इस बीच |a'| x के सभी i (चाहे A में हो या नहीं) और A' के सभी j_ij का योग है; और यह ≥ संगत योग है जिसमें i, A में पंक्तियों तक सीमित है। इसलिए |A'| ≥|a|.

इसका तात्पर्य यह है कि हॉल के मैरिज प्रमेय की नियम संतुष्ट हैं, और इसलिए हम ग्राफ़ में किनारों का समुच्चय पा सकते हैं जो X में प्रत्येक पंक्ति को पुर्णतः (विशिष्ट) कॉलम में जोड़ता है। ये किनारे क्रमपरिवर्तन आव्यूह को परिभाषित करते हैं जिनकी गैर-शून्य कोशिकाएं X में गैर-शून्य सेल्स से मेल खाती हैं।

सामान्यीकरण

अधिक स्तंभों और पंक्तियों वाले आव्यूहों का सरल सामान्यीकरण है जैसे कि i^वें पंक्ति का योग r_i के समान है (एक धनात्मक पूर्णांक), स्तंभों का योग 1 के समान है, और सभी सेल गैर-ऋणात्मक हैं (पंक्ति योगों का योग स्तंभों की संख्या के समान है)। इस रूप में किसी भी आव्यूह को 0s और 1s से बने समान रूप में आव्यूह के उत्तल संयोजन के रूप में व्यक्त किया जा सकता है। इसका प्रमाण 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