स्थायी (गणित): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Polynomial of the elements of a matrix}} रैखिक बीजगणित में, एक वर्ग मैट्रिक्स का स्...")
 
No edit summary
Line 1: Line 1:
{{Short description|Polynomial of the elements of a matrix}}
{{Short description|Polynomial of the elements of a matrix}}
रैखिक बीजगणित में, एक [[वर्ग मैट्रिक्स]] का स्थाई, सारणिक के समान मैट्रिक्स का एक कार्य है। स्थायी, साथ ही निर्धारक, मैट्रिक्स की प्रविष्टियों में एक बहुपद है।<ref>{{cite journal|author=Marcus, Marvin|author2=Minc, Henryk|title=स्थायी|journal=Amer. Math. Monthly|volume=72|issue=6|year=1965|pages=577–591|url=https://maa.org/programs/maa-awards/writing-awards/permanents|doi=10.2307/2313846|jstor=2313846}}</ref> दोनों मैट्रिक्स के अधिक सामान्य कार्य के विशेष मामले हैं जिन्हें [[िम्मनत]] कहा जाता है।
रैखिक बीजगणित में, [[वर्ग मैट्रिक्स]] का स्थाई, सारणिक के समान मैट्रिक्स का कार्य है। स्थायी, साथ ही निर्धारक, मैट्रिक्स की प्रविष्टियों में बहुपद है।<ref>{{cite journal|author=Marcus, Marvin|author2=Minc, Henryk|title=स्थायी|journal=Amer. Math. Monthly|volume=72|issue=6|year=1965|pages=577–591|url=https://maa.org/programs/maa-awards/writing-awards/permanents|doi=10.2307/2313846|jstor=2313846}}</ref> दोनों मैट्रिक्स के अधिक सामान्य कार्य के विशेष मामले हैं जिन्हें [[िम्मनत]] कहा जाता है।


== परिभाषा ==
== परिभाषा ==
Line 16: Line 16:
ए के स्थायी की परिभाषा ए के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है।
ए के स्थायी की परिभाषा ए के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है।


मैट्रिक्स ए के स्थायी को प्रति ए, पर्म ए, या प्रति ए द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ। मिनक आयताकार मैट्रिक्स के स्थायीकरण के लिए Per(A) का उपयोग करता है, और जब A एक वर्ग मैट्रिक्स है तो per(A) का उपयोग करता है।<ref>{{harvtxt|Minc|1978}}</ref> मुइर और मेट्ज़लर अंकन का उपयोग करते हैं <math>\overset{+}{|}\quad \overset{+}{|}</math>.<ref>{{harvtxt|Muir|Metzler|1960}}</ref>
मैट्रिक्स ए के स्थायी को प्रति ए, पर्म ए, या प्रति ए द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ। मिनक आयताकार मैट्रिक्स के स्थायीकरण के लिए Per(A) का उपयोग करता है, और जब A वर्ग मैट्रिक्स है तो per(A) का उपयोग करता है।<ref>{{harvtxt|Minc|1978}}</ref> मुइर और मेट्ज़लर अंकन का उपयोग करते हैं <math>\overset{+}{|}\quad \overset{+}{|}</math>.<ref>{{harvtxt|Muir|Metzler|1960}}</ref>
स्थायी शब्द की उत्पत्ति 1812 में कॉची के साथ संबंधित प्रकार के फ़ंक्शन के लिए "फॉन्क्शन सिमेट्रिक्स परमानेंटेस" के रूप में हुई थी,<ref>{{Citation| last=Cauchy | first=A. L.| title=Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. |url=https://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 |journal=Journal de l'École Polytechnique |volume=10 |pages=91–169 |year=1815}}</ref> और इसका उपयोग मुइर और मेट्ज़लर द्वारा किया गया था<ref>{{harvtxt|Muir|Metzler|1960}}</ref> आधुनिक, अधिक विशिष्ट, अर्थ में।<ref>{{harvnb|van Lint|Wilson|2001|loc=p. 108}}</ref>
स्थायी शब्द की उत्पत्ति 1812 में कॉची के साथ संबंधित प्रकार के फ़ंक्शन के लिए "फॉन्क्शन सिमेट्रिक्स परमानेंटेस" के रूप में हुई थी,<ref>{{Citation| last=Cauchy | first=A. L.| title=Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. |url=https://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 |journal=Journal de l'École Polytechnique |volume=10 |pages=91–169 |year=1815}}</ref> और इसका उपयोग मुइर और मेट्ज़लर द्वारा किया गया था<ref>{{harvtxt|Muir|Metzler|1960}}</ref> आधुनिक, अधिक विशिष्ट, अर्थ में।<ref>{{harvnb|van Lint|Wilson|2001|loc=p. 108}}</ref>




== गुण ==
== गुण ==
यदि कोई स्थायी को एक मानचित्र के रूप में देखता है जो n वैक्टर को तर्क के रूप में लेता है, तो यह एक [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि वैक्टर के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अलावा, एक वर्ग मैट्रिक्स दिया गया है <math>A = \left(a_{ij}\right)</math> क्रम का n:<ref>{{harvnb|Ryser|1963|loc=pp. 25 &ndash; 26}}</ref>
यदि कोई स्थायी को मानचित्र के रूप में देखता है जो n वैक्टर को तर्क के रूप में लेता है, तो यह [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि वैक्टर के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अलावा, वर्ग मैट्रिक्स दिया गया है <math>A = \left(a_{ij}\right)</math> क्रम का n:<ref>{{harvnb|Ryser|1963|loc=pp. 25 &ndash; 26}}</ref>
* ए की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(ए) अपरिवर्तनीय है। इस संपत्ति को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स]] पी और क्यू के लिए प्रतीकात्मक रूप से पर्म(ए) = पर्म(पीएक्यू) के रूप में लिखा जा सकता है।
* ए की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(ए) अपरिवर्तनीय है। इस संपत्ति को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स]] पी और क्यू के लिए प्रतीकात्मक रूप से पर्म(ए) = पर्म(पीएक्यू) के रूप में लिखा जा सकता है।
* A की किसी एक पंक्ति या स्तंभ को एक [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) बदल जाता है,
* A की किसी पंक्ति या स्तंभ को [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) बदल जाता है,
* [[ खिसकाना ]] के तहत पर्म (ए) अपरिवर्तनीय है, यानी, पर्म (ए) = पर्म (ए)<sup>टी</sup>).
* [[ खिसकाना | खिसकाना]] के तहत पर्म (ए) अपरिवर्तनीय है, यानी, पर्म (ए) = पर्म (ए)<sup>टी</sup>).
* अगर <math>A = \left(a_{ij}\right)</math> और <math>B=\left(b_{ij}\right)</math> तब क्रम n के वर्ग आव्यूह हैं,<ref>{{harvnb|Percus|1971|loc=p. 2}}</ref> <math display="block">\operatorname{perm}\left(A + B\right) = \sum_{s,t} \operatorname{perm} \left(a_{ij}\right)_{i \in s, j \in t} \operatorname{perm} \left(b_{ij}\right)_{i \in \bar{s}, j \in \bar{t}},</math> जहां s और t {1,2,...,n} और के समान आकार के उपसमुच्चय हैं <math>\bar{s}, \bar{t}</math> उस सेट में उनके संबंधित पूरक हैं।
* अगर <math>A = \left(a_{ij}\right)</math> और <math>B=\left(b_{ij}\right)</math> तब क्रम n के वर्ग आव्यूह हैं,<ref>{{harvnb|Percus|1971|loc=p. 2}}</ref> <math display="block">\operatorname{perm}\left(A + B\right) = \sum_{s,t} \operatorname{perm} \left(a_{ij}\right)_{i \in s, j \in t} \operatorname{perm} \left(b_{ij}\right)_{i \in \bar{s}, j \in \bar{t}},</math> जहां s और t {1,2,...,n} और के समान आकार के उपसमुच्चय हैं <math>\bar{s}, \bar{t}</math> उस सेट में उनके संबंधित पूरक हैं।
* अगर <math>A</math> एक [[त्रिकोणीय मैट्रिक्स]] है, अर्थात <math>a_{ij}=0</math>, जब कभी भी <math>i>j</math> या, वैकल्पिक रूप से, जब भी <math>i<j</math>, तो इसका स्थायी (और निर्धारक भी) विकर्ण प्रविष्टियों के उत्पाद के बराबर होता है: <math display="block">\operatorname{perm}\left(A\right) = a_{11} a_{22} \cdots a_{nn} = \prod_{i=1}^n a_{ii}.</math>
* अगर <math>A</math> [[त्रिकोणीय मैट्रिक्स]] है, अर्थात <math>a_{ij}=0</math>, जब कभी भी <math>i>j</math> या, वैकल्पिक रूप से, जब भी <math>i<j</math>, तो इसका स्थायी (और निर्धारक भी) विकर्ण प्रविष्टियों के उत्पाद के बराबर होता है: <math display="block">\operatorname{perm}\left(A\right) = a_{11} a_{22} \cdots a_{nn} = \prod_{i=1}^n a_{ii}.</math>




Line 32: Line 32:


एक पंक्ति, स्तंभ या विकर्ण के साथ निर्धारक की गणना के लिए नाबालिगों द्वारा लाप्लास का विस्तार सभी संकेतों को अनदेखा करके स्थायी तक विस्तारित होता है।<ref name="Percus 1971 loc=p. 12">{{harvnb|Percus|1971|loc=p. 12}}</ref>
एक पंक्ति, स्तंभ या विकर्ण के साथ निर्धारक की गणना के लिए नाबालिगों द्वारा लाप्लास का विस्तार सभी संकेतों को अनदेखा करके स्थायी तक विस्तारित होता है।<ref name="Percus 1971 loc=p. 12">{{harvnb|Percus|1971|loc=p. 12}}</ref>
हरएक के लिए <math display="inline">i</math>,
हरएक के लिए <math display="inline">i</math>,


Line 54: Line 55:
= {} & 4(1) + 0 + 0 + 1(6) = 10.
= {} & 4(1) + 0 + 0 + 1(6) = 10.
\end{align} </math>
\end{align} </math>
दूसरी ओर, निर्धारकों की मूल गुणात्मक संपत्ति स्थायी के लिए मान्य नहीं है।<ref name="Ryser 1963 loc=p. 26">{{harvnb|Ryser|1963|loc=p. 26}}</ref> एक साधारण उदाहरण से पता चलता है कि ऐसा ही है।
दूसरी ओर, निर्धारकों की मूल गुणात्मक संपत्ति स्थायी के लिए मान्य नहीं है।<ref name="Ryser 1963 loc=p. 26">{{harvnb|Ryser|1963|loc=p. 26}}</ref> साधारण उदाहरण से पता चलता है कि ऐसा ही है।


<math display="block">\begin{align} 4 &= \operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right )\operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \\
<math display="block">\begin{align} 4 &= \operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right )\operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \\
&\neq \operatorname{perm}\left ( \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \right ) = \operatorname{perm} \left ( \begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix} \right )= 8. \end{align} </math>
&\neq \operatorname{perm}\left ( \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \right ) = \operatorname{perm} \left ( \begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix} \right )= 8. \end{align} </math>
निर्धारक के विपरीत, स्थायी की कोई आसान ज्यामितीय व्याख्या नहीं होती है; इसका उपयोग मुख्य रूप से [[साहचर्य]] में, बोसॉन ग्रीन के फ़ंक्शन (कई-शरीर सिद्धांत) के इलाज में, [[क्वांटम क्षेत्र सिद्धांत]] में ग्रीन के कार्यों और [[बोसोन नमूनाकरण]] सिस्टम की राज्य संभावनाओं को निर्धारित करने में किया जाता है।<ref>{{cite arXiv |last=Aaronson |first=Scott |date=14 Nov 2010 |title=रैखिक प्रकाशिकी की कम्प्यूटेशनल जटिलता|eprint=1011.3245|class=quant-ph }}</ref> हालाँकि, इसकी दो [[ग्राफ-सैद्धांतिक]] व्याख्याएँ हैं: एक [[निर्देशित ग्राफ]] के [[शीर्ष चक्र कवर]] के वजन के योग के रूप में, और एक [[द्विदलीय ग्राफ]] में सही मिलान के वजन के योग के रूप में।
निर्धारक के विपरीत, स्थायी की कोई आसान ज्यामितीय व्याख्या नहीं होती है; इसका उपयोग मुख्य रूप से [[साहचर्य]] में, बोसॉन ग्रीन के फ़ंक्शन (कई-शरीर सिद्धांत) के इलाज में, [[क्वांटम क्षेत्र सिद्धांत]] में ग्रीन के कार्यों और [[बोसोन नमूनाकरण]] सिस्टम की राज्य संभावनाओं को निर्धारित करने में किया जाता है।<ref>{{cite arXiv |last=Aaronson |first=Scott |date=14 Nov 2010 |title=रैखिक प्रकाशिकी की कम्प्यूटेशनल जटिलता|eprint=1011.3245|class=quant-ph }}</ref> हालाँकि, इसकी दो [[ग्राफ-सैद्धांतिक]] व्याख्याएँ हैं: [[निर्देशित ग्राफ]] के [[शीर्ष चक्र कवर]] के वजन के योग के रूप में, और [[द्विदलीय ग्राफ]] में सही मिलान के वजन के योग के रूप में।


== अनुप्रयोग ==
== अनुप्रयोग ==
Line 70: Line 71:
x_{\sigma(1)} \otimes x_{\sigma(2)} \otimes \cdots \otimes x_{\sigma(k)}
x_{\sigma(1)} \otimes x_{\sigma(2)} \otimes \cdots \otimes x_{\sigma(k)}
</math>
</math>
अगर हम विचार करें <math>\vee^k H</math> (के एक उप-स्थान के रूप में <math>\otimes^kH</math>, हिल्बर्ट रिक्त स्थान का kth टेंसर उत्पाद <math>H</math>) और आंतरिक उत्पाद को परिभाषित करें <math>\vee^kH</math> तदनुसार, हम इसके लिए पाते हैं <math>x_j,y_j \in H</math>
अगर हम विचार करें <math>\vee^k H</math> (के उप-स्थान के रूप में <math>\otimes^kH</math>, हिल्बर्ट रिक्त स्थान का kth टेंसर उत्पाद <math>H</math>) और आंतरिक उत्पाद को परिभाषित करें <math>\vee^kH</math> तदनुसार, हम इसके लिए पाते हैं <math>x_j,y_j \in H</math>
<math display="block">\langle
<math display="block">\langle
x_1 \vee x_2 \vee \cdots \vee x_k,
x_1 \vee x_2 \vee \cdots \vee x_k,
Line 86: Line 87:
{{main|Vertex cycle cover}}
{{main|Vertex cycle cover}}
कोई भी वर्ग मैट्रिक्स <math>A = (a_{ij})_{i,j=1}^n</math> शीर्ष सेट पर भारित निर्देशित ग्राफ के आसन्न मैट्रिक्स के रूप में देखा जा सकता है <math>V=\{1,2,\dots,n\}</math>, साथ <math>a_{ij}</math> शीर्ष i से शीर्ष j तक चाप के भार का प्रतिनिधित्व करना।
कोई भी वर्ग मैट्रिक्स <math>A = (a_{ij})_{i,j=1}^n</math> शीर्ष सेट पर भारित निर्देशित ग्राफ के आसन्न मैट्रिक्स के रूप में देखा जा सकता है <math>V=\{1,2,\dots,n\}</math>, साथ <math>a_{ij}</math> शीर्ष i से शीर्ष j तक चाप के भार का प्रतिनिधित्व करना।
भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध [[निर्देशित चक्र]]ों का एक संग्रह है जो ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष i का एक अद्वितीय उत्तराधिकारी होता है <math>\sigma(i)</math> चक्र आवरण में, इत्यादि <math>\sigma</math> वी पर एक क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, कोई भी क्रमपरिवर्तन <math>\sigma</math> V पर प्रत्येक शीर्ष i से शीर्ष तक चाप के साथ एक चक्र कवर से मेल खाता है <math>\sigma(i)</math>.
भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध [[निर्देशित चक्र]]ों का संग्रह है जो ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष i का अद्वितीय उत्तराधिकारी होता है <math>\sigma(i)</math> चक्र आवरण में, इत्यादि <math>\sigma</math> वी पर क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, कोई भी क्रमपरिवर्तन <math>\sigma</math> V पर प्रत्येक शीर्ष i से शीर्ष तक चाप के साथ चक्र कवर से मेल खाता है <math>\sigma(i)</math>.


यदि एक चक्र-कवर का वजन प्रत्येक चक्र में चापों के वजन के उत्पाद के रूप में परिभाषित किया गया है, तो
यदि चक्र-कवर का वजन प्रत्येक चक्र में चापों के वजन के उत्पाद के रूप में परिभाषित किया गया है, तो
<math display="block"> \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)},</math>
<math display="block"> \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)},</math>
इसका तात्पर्य यह है कि
इसका तात्पर्य यह है कि
Line 95: Line 96:


===उत्तम मिलान===
===उत्तम मिलान===
एक वर्ग मैट्रिक्स <math>A = (a_{ij})</math> इसे द्विदलीय ग्राफ के आसन्न मैट्रिक्स के रूप में भी देखा जा सकता है जिसमें शीर्ष (ग्राफ सिद्धांत) है <math>x_1, x_2, \dots, x_n</math> एक तरफ और <math>y_1, y_2, \dots, y_n</math> दूसरी ओर, साथ में <math>a_{ij}</math> शीर्ष से किनारे के भार का प्रतिनिधित्व करना <math>x_i</math> शिखर तक <math>y_j</math>. यदि वजन का पूर्ण मिलान हो <math>\sigma</math> यह मेल खाता है <math>x_i</math> को <math>y_{\sigma(i)}</math> तब, इसे मिलान में किनारों के भार के गुणनफल के रूप में परिभाषित किया गया है
एक वर्ग मैट्रिक्स <math>A = (a_{ij})</math> इसे द्विदलीय ग्राफ के आसन्न मैट्रिक्स के रूप में भी देखा जा सकता है जिसमें शीर्ष (ग्राफ सिद्धांत) है <math>x_1, x_2, \dots, x_n</math> तरफ और <math>y_1, y_2, \dots, y_n</math> दूसरी ओर, साथ में <math>a_{ij}</math> शीर्ष से किनारे के भार का प्रतिनिधित्व करना <math>x_i</math> शिखर तक <math>y_j</math>. यदि वजन का पूर्ण मिलान हो <math>\sigma</math> यह मेल खाता है <math>x_i</math> को <math>y_{\sigma(i)}</math> तब, इसे मिलान में किनारों के भार के गुणनफल के रूप में परिभाषित किया गया है
<math display="block"> \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)}.</math>
<math display="block"> \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)}.</math>
इस प्रकार A का स्थायी मान ग्राफ़ के सभी पूर्ण मिलानों के भारों के योग के बराबर है।
इस प्रकार A का स्थायी मान ग्राफ़ के सभी पूर्ण मिलानों के भारों के योग के बराबर है।
Line 104: Line 105:
गिनती के कई प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 0 और 1 हैं।
गिनती के कई प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 0 और 1 हैं।


मान लीजिए Ω(n,k) क्रम n के सभी (0, 1)-आव्यूहों का वर्ग है और प्रत्येक पंक्ति और स्तंभ का योग k के बराबर है। इस वर्ग के प्रत्येक मैट्रिक्स ए में पर्म(ए) > 0 है।<ref name="Ryser 1963 loc=p. 124">{{harvnb|Ryser|1963|loc=p. 124}}</ref> [[प्रक्षेप्य तल]]ों के आपतन मैट्रिक्स वर्ग Ω(n) में हैं<sup>2</sup> + n + 1, n + 1) n एक पूर्णांक > 1 के लिए। सबसे छोटे प्रक्षेप्य तलों के अनुरूप स्थायी की गणना की गई है। n = 2, 3, और 4 के लिए मान क्रमशः 24, 3852 और 18,534,400 हैं।<ref name="Ryser 1963 loc=p. 124"/>मान लीजिए Z, n = 2, [[फैनो विमान]] के साथ प्रक्षेप्य तल का आपतन मैट्रिक्स है। उल्लेखनीय रूप से, perm(Z) = 24 = |det (Z)|, Z के निर्धारक का निरपेक्ष मान। यह Z के एक परिसंचरण मैट्रिक्स और प्रमेय होने का परिणाम है:<ref>{{harvnb|Ryser|1963|loc=p. 125}}</ref>
मान लीजिए Ω(n,k) क्रम n के सभी (0, 1)-आव्यूहों का वर्ग है और प्रत्येक पंक्ति और स्तंभ का योग k के बराबर है। इस वर्ग के प्रत्येक मैट्रिक्स ए में पर्म(ए) > 0 है।<ref name="Ryser 1963 loc=p. 124">{{harvnb|Ryser|1963|loc=p. 124}}</ref> [[प्रक्षेप्य तल]]ों के आपतन मैट्रिक्स वर्ग Ω(n) में हैं<sup>2</sup> + n + 1, n + 1) n पूर्णांक > 1 के लिए। सबसे छोटे प्रक्षेप्य तलों के अनुरूप स्थायी की गणना की गई है। n = 2, 3, और 4 के लिए मान क्रमशः 24, 3852 और 18,534,400 हैं।<ref name="Ryser 1963 loc=p. 124"/>मान लीजिए Z, n = 2, [[फैनो विमान]] के साथ प्रक्षेप्य तल का आपतन मैट्रिक्स है। उल्लेखनीय रूप से, perm(Z) = 24 = |det (Z)|, Z के निर्धारक का निरपेक्ष मान। यह Z के परिसंचरण मैट्रिक्स और प्रमेय होने का परिणाम है:<ref>{{harvnb|Ryser|1963|loc=p. 125}}</ref>
:यदि A वर्ग Ω(n,k) में एक परिसंचरण मैट्रिक्स है तो यदि k > 3, perm(A) > |det (A)| और यदि k = 3, perm(A)=|det (A)| इसके अलावा, जब k = 3, पंक्तियों और स्तंभों को क्रमपरिवर्तित करके, A को मैट्रिक्स Z की e प्रतियों के प्रत्यक्ष योग के रूप में रखा जा सकता है और परिणामस्वरूप, n = 7e और perm(A) = 24<sup>इ</sup>.
:यदि A वर्ग Ω(n,k) में परिसंचरण मैट्रिक्स है तो यदि k > 3, perm(A) > |det (A)| और यदि k = 3, perm(A)=|det (A)| इसके अलावा, जब k = 3, पंक्तियों और स्तंभों को क्रमपरिवर्तित करके, A को मैट्रिक्स Z की e प्रतियों के प्रत्यक्ष योग के रूप में रखा जा सकता है और परिणामस्वरूप, n = 7e और perm(A) = 24<sup>इ</sup>.


स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक n-सेट {1, 2, ..., n} के लिए, मान लीजिए <math>A = (a_{ij})</math> (0, 1)-मैट्रिक्स बनें जहां ए<sub>''ij''</sub> = 1 यदि i → j को क्रमपरिवर्तन में अनुमति दी गई है और a<sub>''ij''</sub> = 0 अन्यथा. तब पर्म(ए) एन-सेट के क्रमपरिवर्तन की संख्या के बराबर है जो सभी प्रतिबंधों को पूरा करता है।<ref name="Percus 1971 loc=p. 12"/>इसके दो प्रसिद्ध विशेष मामले विक्षोभ समस्या और मेनेज समस्या का समाधान हैं: बिना किसी निश्चित बिंदु (विक्षोभ) वाले एन-सेट के क्रमपरिवर्तन की संख्या दी गई है
स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक n-सेट {1, 2, ..., n} के लिए, मान लीजिए <math>A = (a_{ij})</math> (0, 1)-मैट्रिक्स बनें जहां ए<sub>''ij''</sub> = 1 यदि i → j को क्रमपरिवर्तन में अनुमति दी गई है और a<sub>''ij''</sub> = 0 अन्यथा. तब पर्म(ए) एन-सेट के क्रमपरिवर्तन की संख्या के बराबर है जो सभी प्रतिबंधों को पूरा करता है।<ref name="Percus 1971 loc=p. 12"/>इसके दो प्रसिद्ध विशेष मामले विक्षोभ समस्या और मेनेज समस्या का समाधान हैं: बिना किसी निश्चित बिंदु (विक्षोभ) वाले एन-सेट के क्रमपरिवर्तन की संख्या दी गई है
Line 119: Line 120:


===सीमा ===
===सीमा ===
ब्रेगमैन-मिन्क असमानता, 1963 में एच. मिन्क द्वारा अनुमानित<ref>{{citation|first=Henryk|last=Minc|title=Upper bounds for permanents of (0,1)-matrices|journal=Bulletin of the American Mathematical Society|volume=69|issue=6|year=1963|pages=789–791|doi=10.1090/s0002-9904-1963-11031-9|doi-access=free}}</ref> और लेव एम ब्रेगमैन|एल द्वारा सिद्ध किया गया। 1973 में एम. ब्रैगमैन,<ref>{{harvnb|van Lint|Wilson|2001|loc=p. 101}}</ref> n × n (0, 1)-मैट्रिक्स के स्थायी के लिए एक ऊपरी सीमा देता है। यदि A के पास r है<sub>''i''</sub> पंक्ति i में प्रत्येक 1 ≤ i ≤ n के लिए, असमानता बताती है कि
ब्रेगमैन-मिन्क असमानता, 1963 में एच. मिन्क द्वारा अनुमानित<ref>{{citation|first=Henryk|last=Minc|title=Upper bounds for permanents of (0,1)-matrices|journal=Bulletin of the American Mathematical Society|volume=69|issue=6|year=1963|pages=789–791|doi=10.1090/s0002-9904-1963-11031-9|doi-access=free}}</ref> और लेव एम ब्रेगमैन|एल द्वारा सिद्ध किया गया। 1973 में एम. ब्रैगमैन,<ref>{{harvnb|van Lint|Wilson|2001|loc=p. 101}}</ref> n × n (0, 1)-मैट्रिक्स के स्थायी के लिए ऊपरी सीमा देता है। यदि A के पास r है<sub>''i''</sub> पंक्ति i में प्रत्येक 1 ≤ i ≤ n के लिए, असमानता बताती है कि
<math display="block">\operatorname{perm} A \leq \prod_{i=1}^n (r_i)!^{1/r_i}.</math>
<math display="block">\operatorname{perm} A \leq \prod_{i=1}^n (r_i)!^{1/r_i}.</math>


== वैन डेर वेर्डन का अनुमान ==
== वैन डेर वेर्डन का अनुमान ==
Line 174: Line 174:
  | title = Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix
  | title = Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix
  | volume = 29
  | volume = 29
  | year = 1981}}.</ref> एगोरीचेव का प्रमाण अलेक्जेंड्रोव-फेन्चेल असमानता का एक अनुप्रयोग है।<ref name=CMC487>Brualdi (2006) p.487</ref> इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।<ref>[https://mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref>
  | year = 1981}}.</ref> एगोरीचेव का प्रमाण अलेक्जेंड्रोव-फेन्चेल असमानता का अनुप्रयोग है।<ref name=CMC487>Brualdi (2006) p.487</ref> इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।<ref>[https://mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref>
 
 
== गणना ==
== गणना ==
{{main|Computing the permanent|Sharp-P-completeness of 01-permanent}}
{{main|Computing the permanent|Sharp-P-completeness of 01-permanent}}
परिभाषा का उपयोग करते हुए, स्थायी कंप्यूटिंग का भोला दृष्टिकोण अपेक्षाकृत छोटे मैट्रिक्स के लिए भी कम्प्यूटेशनल रूप से संभव नहीं है। सबसे तेज़ ज्ञात एल्गोरिदम में से एक H. J. Ryser के कारण है।<ref>{{harvtxt|Ryser|1963|loc=p. 27}}</ref> रायसर का सूत्र|राइसर की विधि समावेशन-बहिष्करण सिद्धांत पर आधारित है|समावेश-बहिष्करण सूत्र जिसे दिया जा सकता है<ref>{{harvtxt|van Lint|Wilson|2001}} [https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA108&dq=permanent+ryser&lr=#PPA99,M1 p. 99]</ref> इस प्रकार: चलो <math>A_k</math> K कॉलम को हटाकर A से प्राप्त किया जा सकता है <math>P(A_k)</math> की पंक्ति-योग का उत्पाद बनें <math>A_k</math>, और जाने <math>\Sigma_k</math> के मानों का योग हो <math>P(A_k)</math> हर संभव से अधिक <math>A_k</math>. तब
परिभाषा का उपयोग करते हुए, स्थायी कंप्यूटिंग का भोला दृष्टिकोण अपेक्षाकृत छोटे मैट्रिक्स के लिए भी कम्प्यूटेशनल रूप से संभव नहीं है। सबसे तेज़ ज्ञात एल्गोरिदम में से H. J. Ryser के कारण है।<ref>{{harvtxt|Ryser|1963|loc=p. 27}}</ref> रायसर का सूत्र|राइसर की विधि समावेशन-बहिष्करण सिद्धांत पर आधारित है|समावेश-बहिष्करण सूत्र जिसे दिया जा सकता है<ref>{{harvtxt|van Lint|Wilson|2001}} [https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA108&dq=permanent+ryser&lr=#PPA99,M1 p. 99]</ref> इस प्रकार: चलो <math>A_k</math> K कॉलम को हटाकर A से प्राप्त किया जा सकता है <math>P(A_k)</math> की पंक्ति-योग का उत्पाद बनें <math>A_k</math>, और जाने <math>\Sigma_k</math> के मानों का योग हो <math>P(A_k)</math> हर संभव से अधिक <math>A_k</math>. तब
<math display="block"> \operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k} \Sigma_k.</math>
<math display="block"> \operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k} \Sigma_k.</math>
इसे मैट्रिक्स प्रविष्टियों के संदर्भ में निम्नानुसार फिर से लिखा जा सकता है:
इसे मैट्रिक्स प्रविष्टियों के संदर्भ में निम्नानुसार फिर से लिखा जा सकता है:
<math display="block">\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.</math>
<math display="block">\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.</math>
ऐसा माना जाता है कि निर्धारक की तुलना में स्थायी की गणना करना अधिक कठिन है। जबकि निर्धारक की गणना गाऊसी विलोपन द्वारा बहुपद समय में की जा सकती है, गाऊसी विलोपन का उपयोग स्थायी की गणना के लिए नहीं किया जा सकता है। इसके अलावा, (0,1)-मैट्रिक्स के स्थायी की गणना तीव्र-पी-पूर्ण|#पी-पूर्ण है। इस प्रकार, यदि स्थायी की गणना किसी भी विधि द्वारा बहुपद समय में की जा सकती है, तो [[एफपी (जटिलता)]] = तेज-पी | # पी, जो पी = एनपी समस्या | पी = एनपी से भी अधिक मजबूत कथन है। हालाँकि, जब ''ए'' की प्रविष्टियाँ गैर-नकारात्मक होती हैं, तो स्थायी की गणना यादृच्छिक एल्गोरिथ्म बहुपद समय में [[सन्निकटन एल्गोरिथ्म]] से की जा सकती है, एक त्रुटि तक <math>\varepsilon M</math>, कहाँ <math>M</math> स्थायी और का मान है <math>\varepsilon > 0 </math> मनमाना है.<ref>{{Citation|last1= Jerrum | first1= M.|author1-link= Mark Jerrum |last2=Sinclair | first2= A.|author2-link= Alistair Sinclair|last3=Vigoda | first3= E.|title=A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries |journal=[[Journal of the ACM]] |year=2004 |volume= 51 | issue= 4|pages= 671–697 | doi=10.1145/1008731.1008738| citeseerx= 10.1.1.18.9466| s2cid= 47361920}}</ref> [[सकारात्मक निश्चित मैट्रिक्स]] के एक निश्चित सेट के स्थायी को संभाव्य बहुपद समय में भी अनुमानित किया जा सकता है: इस सन्निकटन की सबसे अच्छी प्राप्य त्रुटि है <math>\varepsilon\sqrt{M}</math> (<math>M</math> पुनः स्थायी का मान है)।<ref>{{cite journal| last1=Chakhmakhchyan|first1=Levon|last2=Cerf|first2=Nicolas|last3=Garcia-Patron|first3=Raul|title=सकारात्मक अर्धनिश्चित मैट्रिक्स के स्थायी अनुमान के लिए एक क्वांटम-प्रेरित एल्गोरिदम| journal = Phys. Rev. A|volume=96 |issue=2|pages=022329 | doi=10.1103/PhysRevA.96.022329|year=2017|bibcode=2017PhRvA..96b2329C|arxiv=1609.02416|s2cid=54194194}}</ref>
ऐसा माना जाता है कि निर्धारक की तुलना में स्थायी की गणना करना अधिक कठिन है। जबकि निर्धारक की गणना गाऊसी विलोपन द्वारा बहुपद समय में की जा सकती है, गाऊसी विलोपन का उपयोग स्थायी की गणना के लिए नहीं किया जा सकता है। इसके अलावा, (0,1)-मैट्रिक्स के स्थायी की गणना तीव्र-पी-पूर्ण|#पी-पूर्ण है। इस प्रकार, यदि स्थायी की गणना किसी भी विधि द्वारा बहुपद समय में की जा सकती है, तो [[एफपी (जटिलता)]] = तेज-पी | # पी, जो पी = एनपी समस्या | पी = एनपी से भी अधिक मजबूत कथन है। हालाँकि, जब ''ए'' की प्रविष्टियाँ गैर-नकारात्मक होती हैं, तो स्थायी की गणना यादृच्छिक एल्गोरिथ्म बहुपद समय में [[सन्निकटन एल्गोरिथ्म]] से की जा सकती है, त्रुटि तक <math>\varepsilon M</math>, कहाँ <math>M</math> स्थायी और का मान है <math>\varepsilon > 0 </math> मनमाना है.<ref>{{Citation|last1= Jerrum | first1= M.|author1-link= Mark Jerrum |last2=Sinclair | first2= A.|author2-link= Alistair Sinclair|last3=Vigoda | first3= E.|title=A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries |journal=[[Journal of the ACM]] |year=2004 |volume= 51 | issue= 4|pages= 671–697 | doi=10.1145/1008731.1008738| citeseerx= 10.1.1.18.9466| s2cid= 47361920}}</ref> [[सकारात्मक निश्चित मैट्रिक्स]] के निश्चित सेट के स्थायी को संभाव्य बहुपद समय में भी अनुमानित किया जा सकता है: इस सन्निकटन की सबसे अच्छी प्राप्य त्रुटि है <math>\varepsilon\sqrt{M}</math> (<math>M</math> पुनः स्थायी का मान है)।<ref>{{cite journal| last1=Chakhmakhchyan|first1=Levon|last2=Cerf|first2=Nicolas|last3=Garcia-Patron|first3=Raul|title=सकारात्मक अर्धनिश्चित मैट्रिक्स के स्थायी अनुमान के लिए एक क्वांटम-प्रेरित एल्गोरिदम| journal = Phys. Rev. A|volume=96 |issue=2|pages=022329 | doi=10.1103/PhysRevA.96.022329|year=2017|bibcode=2017PhRvA..96b2329C|arxiv=1609.02416|s2cid=54194194}}</ref>




==मैकमोहन का मास्टर प्रमेय==
==मैकमोहन का मास्टर प्रमेय==
{{main|MacMahon's master theorem}}
{{main|MacMahon's master theorem}}
स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी [[जनरेटिंग फ़ंक्शन]] के माध्यम से है। होने देना <math>A = (a_{ij})</math> क्रम n का एक वर्ग मैट्रिक्स बनें। बहुभिन्नरूपी जनरेटिंग फ़ंक्शन पर विचार करें:
स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी [[जनरेटिंग फ़ंक्शन]] के माध्यम से है। होने देना <math>A = (a_{ij})</math> क्रम n का वर्ग मैट्रिक्स बनें। बहुभिन्नरूपी जनरेटिंग फ़ंक्शन पर विचार करें:
<math display="block">\begin{align} F(x_1,x_2,\dots,x_n) &= \prod_{i=1}^n \left ( \sum_{j=1}^n a_{ij} x_j \right ) \\
<math display="block">\begin{align} F(x_1,x_2,\dots,x_n) &= \prod_{i=1}^n \left ( \sum_{j=1}^n a_{ij} x_j \right ) \\
&= \left( \sum_{j=1}^n a_{1j} x_j \right ) \left ( \sum_{j=1}^n a_{2j} x_j \right ) \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right). \end{align}</math>
&= \left( \sum_{j=1}^n a_{1j} x_j \right ) \left ( \sum_{j=1}^n a_{2j} x_j \right ) \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right). \end{align}</math>
का गुणांक <math>x_1 x_2 \dots x_n</math> में <math>F(x_1,x_2,\dots,x_n)</math> पर्म(ए) है.<ref>{{harvnb|Percus|1971|loc=p. 14}}</ref>
का गुणांक <math>x_1 x_2 \dots x_n</math> में <math>F(x_1,x_2,\dots,x_n)</math> पर्म(ए) है.<ref>{{harvnb|Percus|1971|loc=p. 14}}</ref>
सामान्यीकरण के रूप में, n गैर-नकारात्मक पूर्णांकों के किसी भी अनुक्रम के लिए, <math>s_1,s_2,\dots,s_n</math> परिभाषित करना:
सामान्यीकरण के रूप में, n गैर-नकारात्मक पूर्णांकों के किसी भी अनुक्रम के लिए, <math>s_1,s_2,\dots,s_n</math> परिभाषित करना:
<math display="block">\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)</math> के गुणांक के रूप में <math>x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} </math> में<math>\left ( \sum_{j=1}^n a_{1j} x_j \right )^{s_1} \left ( \sum_{j=1}^n a_{2j} x_j \right )^{s_2} \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right )^{s_n}.</math>
<math display="block">\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)</math> के गुणांक के रूप में <math>x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} </math> में<math>\left ( \sum_{j=1}^n a_{1j} x_j \right )^{s_1} \left ( \sum_{j=1}^n a_{2j} x_j \right )^{s_2} \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right )^{s_n}.</math>
Line 197: Line 196:
<math display="block">\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A) = \text{ coefficient of }x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} \text{ in } \frac{1}{\det(I - XA)},</math>
<math display="block">\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A) = \text{ coefficient of }x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} \text{ in } \frac{1}{\det(I - XA)},</math>
जहां I क्रम n पहचान मैट्रिक्स है और X विकर्ण के साथ विकर्ण मैट्रिक्स है <math>[x_1,x_2,\dots,x_n].</math>
जहां I क्रम n पहचान मैट्रिक्स है और X विकर्ण के साथ विकर्ण मैट्रिक्स है <math>[x_1,x_2,\dots,x_n].</math>
==आयताकार आव्यूह==
==आयताकार आव्यूह==
गैर-वर्ग मैट्रिक्स पर लागू करने के लिए स्थायी फ़ंक्शन को सामान्यीकृत किया जा सकता है। दरअसल, कई लेखक इसे स्थायी की परिभाषा बनाते हैं और वर्ग आव्यूहों पर प्रतिबंध को एक विशेष मामला मानते हैं।<ref>In particular, {{harvtxt|Minc|1978}} and {{harvtxt|Ryser|1963}} do this.</ref> विशेष रूप से, m×n मैट्रिक्स के लिए <math>A = (a_{ij})</math> एम ≤ एन के साथ, परिभाषित करें
गैर-वर्ग मैट्रिक्स पर लागू करने के लिए स्थायी फ़ंक्शन को सामान्यीकृत किया जा सकता है। दरअसल, कई लेखक इसे स्थायी की परिभाषा बनाते हैं और वर्ग आव्यूहों पर प्रतिबंध को विशेष मामला मानते हैं।<ref>In particular, {{harvtxt|Minc|1978}} and {{harvtxt|Ryser|1963}} do this.</ref> विशेष रूप से, m×n मैट्रिक्स के लिए <math>A = (a_{ij})</math> एम ≤ एन के साथ, परिभाषित करें
<math display="block">\operatorname{perm} (A) = \sum_{\sigma \in \operatorname{P}(n,m)} a_{1 \sigma(1)} a_{2 \sigma(2)} \ldots a_{m \sigma(m)}</math>
<math display="block">\operatorname{perm} (A) = \sum_{\sigma \in \operatorname{P}(n,m)} a_{1 \sigma(1)} a_{2 \sigma(2)} \ldots a_{m \sigma(m)}</math>
जहाँ P(n,m) n-सेट {1,2,...,n} के सभी m-क्रमपरिवर्तन का समुच्चय है।<ref>{{harvnb|Ryser|1963|loc=p. 25}}</ref>
जहाँ P(n,m) n-सेट {1,2,...,n} के सभी m-क्रमपरिवर्तन का समुच्चय है।<ref>{{harvnb|Ryser|1963|loc=p. 25}}</ref>
स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि A, m≤n के साथ एक m×n मैट्रिक्स है, तो मान लीजिए <math>A_k</math> K कॉलम को हटाकर A से प्राप्त किया जा सकता है <math>P(A_k)</math> की पंक्ति-योग का उत्पाद बनें <math>A_k</math>, और जाने <math>\sigma_k</math> के मानों का योग हो <math>P(A_k)</math> हर संभव से अधिक <math>A_k</math>. तब<ref name="Ryser 1963 loc=p. 26"/>
 
स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि A, m≤n के साथ m×n मैट्रिक्स है, तो मान लीजिए <math>A_k</math> K कॉलम को हटाकर A से प्राप्त किया जा सकता है <math>P(A_k)</math> की पंक्ति-योग का उत्पाद बनें <math>A_k</math>, और जाने <math>\sigma_k</math> के मानों का योग हो <math>P(A_k)</math> हर संभव से अधिक <math>A_k</math>. तब<ref name="Ryser 1963 loc=p. 26" />
<math display="block"> \operatorname{perm}(A)=\sum_{k=0}^{m-1} (-1)^{k}\binom{n-m+k}{k}\sigma_{n-m+k}.</math>
<math display="block"> \operatorname{perm}(A)=\sum_{k=0}^{m-1} (-1)^{k}\binom{n-m+k}{k}\sigma_{n-m+k}.</math>
===विशिष्ट प्रतिनिधियों की प्रणालियाँ===
===विशिष्ट प्रतिनिधियों की प्रणालियाँ===
गैर-वर्ग मैट्रिक्स के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक तरीके से उपयोग करने की अनुमति देता है। उदाहरण के लिए:
गैर-वर्ग मैट्रिक्स के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक तरीके से उपयोग करने की अनुमति देता है। उदाहरण के लिए:


आइए एस<sub>1</sub>, एस<sub>2</sub>, ..., एस<sub>''m''</sub> m ≤ n के साथ n-सेट के उपसमुच्चय (जरूरी नहीं कि अलग) हों। उपसमुच्चय के इस संग्रह की [[घटना मैट्रिक्स]] एक एम × एन (0,1)-मैट्रिक्स ए है। इस संग्रह की [[ट्रांसवर्सल (कॉम्बिनेटरिक्स)]] (एसडीआर) की संख्या पर्म (ए) है।<ref>{{harvnb|Ryser|1963|loc=p. 54}}</ref>
आइए एस<sub>1</sub>, एस<sub>2</sub>, ..., एस<sub>''m''</sub> m ≤ n के साथ n-सेट के उपसमुच्चय (जरूरी नहीं कि अलग) हों। उपसमुच्चय के इस संग्रह की [[घटना मैट्रिक्स]] एम × एन (0,1)-मैट्रिक्स ए है। इस संग्रह की [[ट्रांसवर्सल (कॉम्बिनेटरिक्स)]] (एसडीआर) की संख्या पर्म (ए) है।<ref>{{harvnb|Ryser|1963|loc=p. 54}}</ref>
 
 
==यह भी देखें==
==यह भी देखें==
*[[स्थायी गणना]]
*[[स्थायी गणना]]
*बापट-बेग प्रमेय, क्रम में स्थायी आँकड़ों का एक अनुप्रयोग
*बापट-बेग प्रमेय, क्रम में स्थायी आँकड़ों का अनुप्रयोग
*[[स्लेटर निर्धारक]], [[क्वांटम यांत्रिकी]] में स्थायी का एक अनुप्रयोग
*[[स्लेटर निर्धारक]], [[क्वांटम यांत्रिकी]] में स्थायी का अनुप्रयोग
*[[हफ़नियन]]
*[[हफ़नियन]]


==टिप्पणियाँ==
==टिप्पणियाँ==
{{Reflist|30em}}
{{Reflist|30em}}


==संदर्भ==
==संदर्भ==
Line 231: Line 224:
*{{citation|first=Herbert John|last=Ryser|author-link=H. J. Ryser|title=Combinatorial Mathematics|series=The Carus Mathematical Monographs #14|year=1963|publisher=The Mathematical Association of America}}
*{{citation|first=Herbert John|last=Ryser|author-link=H. J. Ryser|title=Combinatorial Mathematics|series=The Carus Mathematical Monographs #14|year=1963|publisher=The Mathematical Association of America}}
*{{citation|last1=van Lint|first1=J.H. |last2=Wilson|first2=R.M. |title=A Course in Combinatorics|publisher=Cambridge University Press|year= 2001|isbn=978-0521422604}}
*{{citation|last1=van Lint|first1=J.H. |last2=Wilson|first2=R.M. |title=A Course in Combinatorics|publisher=Cambridge University Press|year= 2001|isbn=978-0521422604}}
==अग्रिम पठन==
==अग्रिम पठन==
* {{citation|first=Marshall|last=Hall Jr.| author-link=Marshall Hall (mathematician)|title=Combinatorial Theory|edition=2nd|year=1986|publisher=John Wiley & Sons|place=New York|isbn=978-0-471-09138-7|pages=56&ndash;72}} Contains a proof of the Van der Waerden conjecture.
* {{citation|first=Marshall|last=Hall Jr.| author-link=Marshall Hall (mathematician)|title=Combinatorial Theory|edition=2nd|year=1986|publisher=John Wiley & Sons|place=New York|isbn=978-0-471-09138-7|pages=56&ndash;72}} Contains a proof of the Van der Waerden conjecture.
* {{citation|first1=M.|last1=Marcus|first2=H.|last2=Minc|title=Permanents|journal=The American Mathematical Monthly|volume=72|issue=6|year=1965|pages=577&ndash;591|doi=10.2307/2313846|jstor=2313846}}
* {{citation|first1=M.|last1=Marcus|first2=H.|last2=Minc|title=Permanents|journal=The American Mathematical Monthly|volume=72|issue=6|year=1965|pages=577&ndash;591|doi=10.2307/2313846|jstor=2313846}}
==बाहरी संबंध==
==बाहरी संबंध==
*{{PlanetMath |urlname=Permanent |title=Permanent}}
*{{PlanetMath |urlname=Permanent |title=Permanent}}

Revision as of 08:40, 24 July 2023

रैखिक बीजगणित में, वर्ग मैट्रिक्स का स्थाई, सारणिक के समान मैट्रिक्स का कार्य है। स्थायी, साथ ही निर्धारक, मैट्रिक्स की प्रविष्टियों में बहुपद है।[1] दोनों मैट्रिक्स के अधिक सामान्य कार्य के विशेष मामले हैं जिन्हें िम्मनत कहा जाता है।

परिभाषा

एक का स्थायी n×n आव्यूह A = (ai,j) परिभाषित किया जाता है

यहां का योग सममित समूह एस के सभी तत्वों σ तक फैला हुआ हैn; यानी संख्या 1, 2, ..., एन के सभी क्रमपरिवर्तन पर।

उदाहरण के लिए,

और

ए के स्थायी की परिभाषा ए के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के हस्ताक्षर (क्रमपरिवर्तन) को ध्यान में नहीं रखा जाता है।

मैट्रिक्स ए के स्थायी को प्रति ए, पर्म ए, या प्रति ए द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ। मिनक आयताकार मैट्रिक्स के स्थायीकरण के लिए Per(A) का उपयोग करता है, और जब A वर्ग मैट्रिक्स है तो per(A) का उपयोग करता है।[2] मुइर और मेट्ज़लर अंकन का उपयोग करते हैं .[3] स्थायी शब्द की उत्पत्ति 1812 में कॉची के साथ संबंधित प्रकार के फ़ंक्शन के लिए "फॉन्क्शन सिमेट्रिक्स परमानेंटेस" के रूप में हुई थी,[4] और इसका उपयोग मुइर और मेट्ज़लर द्वारा किया गया था[5] आधुनिक, अधिक विशिष्ट, अर्थ में।[6]


गुण

यदि कोई स्थायी को मानचित्र के रूप में देखता है जो n वैक्टर को तर्क के रूप में लेता है, तो यह बहुरेखीय मानचित्र है और यह सममित है (जिसका अर्थ है कि वैक्टर के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अलावा, वर्ग मैट्रिक्स दिया गया है क्रम का n:[7]

  • ए की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(ए) अपरिवर्तनीय है। इस संपत्ति को किसी भी उचित आकार के क्रमपरिवर्तन मैट्रिक्स पी और क्यू के लिए प्रतीकात्मक रूप से पर्म(ए) = पर्म(पीएक्यू) के रूप में लिखा जा सकता है।
  • A की किसी पंक्ति या स्तंभ को अदिश (गणित) s से गुणा करने पर perm(A) से s⋅perm(A) बदल जाता है,
  • खिसकाना के तहत पर्म (ए) अपरिवर्तनीय है, यानी, पर्म (ए) = पर्म (ए)टी).
  • अगर और तब क्रम n के वर्ग आव्यूह हैं,[8]
    जहां s और t {1,2,...,n} और के समान आकार के उपसमुच्चय हैं उस सेट में उनके संबंधित पूरक हैं।
  • अगर त्रिकोणीय मैट्रिक्स है, अर्थात , जब कभी भी या, वैकल्पिक रूप से, जब भी , तो इसका स्थायी (और निर्धारक भी) विकर्ण प्रविष्टियों के उत्पाद के बराबर होता है:


निर्धारकों से संबंध

एक पंक्ति, स्तंभ या विकर्ण के साथ निर्धारक की गणना के लिए नाबालिगों द्वारा लाप्लास का विस्तार सभी संकेतों को अनदेखा करके स्थायी तक विस्तारित होता है।[9]

हरएक के लिए ,

कहाँ B की iवीं पंक्ति और jवें कॉलम की प्रविष्टि है, और B की iवीं पंक्ति और jवें कॉलम को हटाकर प्राप्त सबमैट्रिक्स का स्थायी मान है।

उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए,

अंतिम पंक्ति के साथ विस्तार करते समय देता है,

दूसरी ओर, निर्धारकों की मूल गुणात्मक संपत्ति स्थायी के लिए मान्य नहीं है।[10] साधारण उदाहरण से पता चलता है कि ऐसा ही है।

निर्धारक के विपरीत, स्थायी की कोई आसान ज्यामितीय व्याख्या नहीं होती है; इसका उपयोग मुख्य रूप से साहचर्य में, बोसॉन ग्रीन के फ़ंक्शन (कई-शरीर सिद्धांत) के इलाज में, क्वांटम क्षेत्र सिद्धांत में ग्रीन के कार्यों और बोसोन नमूनाकरण सिस्टम की राज्य संभावनाओं को निर्धारित करने में किया जाता है।[11] हालाँकि, इसकी दो ग्राफ-सैद्धांतिक व्याख्याएँ हैं: निर्देशित ग्राफ के शीर्ष चक्र कवर के वजन के योग के रूप में, और द्विदलीय ग्राफ में सही मिलान के वजन के योग के रूप में।

अनुप्रयोग

सममित टेंसर

हिल्बर्ट स्थानों की सममित टेंसर शक्ति के अध्ययन में स्थायी स्वाभाविक रूप से उत्पन्न होता है।[12] विशेष रूप से, हिल्बर्ट स्थान के लिए , होने देना निरूपित करें की वें सममित टेंसर शक्ति , जो टेन्सर उत्पाद#बाहरी और सममित बीजगणित का स्थान है। उस पर विशेष ध्यान दें तत्वों के सममित टेंसर#सममित उत्पाद द्वारा फैलाया गया है . के लिए , हम इन तत्वों के सममित उत्पाद को परिभाषित करते हैं

अगर हम विचार करें (के उप-स्थान के रूप में , हिल्बर्ट रिक्त स्थान का kth टेंसर उत्पाद ) और आंतरिक उत्पाद को परिभाषित करें तदनुसार, हम इसके लिए पाते हैं
कॉची-श्वार्ज़ असमानता को लागू करने पर, हम पाते हैं , ओर वो


साइकिल कवर

कोई भी वर्ग मैट्रिक्स शीर्ष सेट पर भारित निर्देशित ग्राफ के आसन्न मैट्रिक्स के रूप में देखा जा सकता है , साथ शीर्ष i से शीर्ष j तक चाप के भार का प्रतिनिधित्व करना। भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध निर्देशित चक्रों का संग्रह है जो ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष i का अद्वितीय उत्तराधिकारी होता है चक्र आवरण में, इत्यादि वी पर क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, कोई भी क्रमपरिवर्तन V पर प्रत्येक शीर्ष i से शीर्ष तक चाप के साथ चक्र कवर से मेल खाता है .

यदि चक्र-कवर का वजन प्रत्येक चक्र में चापों के वजन के उत्पाद के रूप में परिभाषित किया गया है, तो

इसका तात्पर्य यह है कि
इस प्रकार A का स्थायी मान डिग्राफ के सभी चक्र-कवरों के भार के योग के बराबर है।

उत्तम मिलान

एक वर्ग मैट्रिक्स इसे द्विदलीय ग्राफ के आसन्न मैट्रिक्स के रूप में भी देखा जा सकता है जिसमें शीर्ष (ग्राफ सिद्धांत) है तरफ और दूसरी ओर, साथ में शीर्ष से किनारे के भार का प्रतिनिधित्व करना शिखर तक . यदि वजन का पूर्ण मिलान हो यह मेल खाता है को तब, इसे मिलान में किनारों के भार के गुणनफल के रूप में परिभाषित किया गया है

इस प्रकार A का स्थायी मान ग्राफ़ के सभी पूर्ण मिलानों के भारों के योग के बराबर है।

(0, 1) आव्यूहों के स्थायी मान

गणना

गिनती के कई प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 0 और 1 हैं।

मान लीजिए Ω(n,k) क्रम n के सभी (0, 1)-आव्यूहों का वर्ग है और प्रत्येक पंक्ति और स्तंभ का योग k के बराबर है। इस वर्ग के प्रत्येक मैट्रिक्स ए में पर्म(ए) > 0 है।[13] प्रक्षेप्य तलों के आपतन मैट्रिक्स वर्ग Ω(n) में हैं2 + n + 1, n + 1) n पूर्णांक > 1 के लिए। सबसे छोटे प्रक्षेप्य तलों के अनुरूप स्थायी की गणना की गई है। n = 2, 3, और 4 के लिए मान क्रमशः 24, 3852 और 18,534,400 हैं।[13]मान लीजिए Z, n = 2, फैनो विमान के साथ प्रक्षेप्य तल का आपतन मैट्रिक्स है। उल्लेखनीय रूप से, perm(Z) = 24 = |det (Z)|, Z के निर्धारक का निरपेक्ष मान। यह Z के परिसंचरण मैट्रिक्स और प्रमेय होने का परिणाम है:[14]

यदि A वर्ग Ω(n,k) में परिसंचरण मैट्रिक्स है तो यदि k > 3, perm(A) > |det (A)| और यदि k = 3, perm(A)=|det (A)| इसके अलावा, जब k = 3, पंक्तियों और स्तंभों को क्रमपरिवर्तित करके, A को मैट्रिक्स Z की e प्रतियों के प्रत्यक्ष योग के रूप में रखा जा सकता है और परिणामस्वरूप, n = 7e और perm(A) = 24.

स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक n-सेट {1, 2, ..., n} के लिए, मान लीजिए (0, 1)-मैट्रिक्स बनें जहां एij = 1 यदि i → j को क्रमपरिवर्तन में अनुमति दी गई है और aij = 0 अन्यथा. तब पर्म(ए) एन-सेट के क्रमपरिवर्तन की संख्या के बराबर है जो सभी प्रतिबंधों को पूरा करता है।[9]इसके दो प्रसिद्ध विशेष मामले विक्षोभ समस्या और मेनेज समस्या का समाधान हैं: बिना किसी निश्चित बिंदु (विक्षोभ) वाले एन-सेट के क्रमपरिवर्तन की संख्या दी गई है

जहां J सभी 1 का मैट्रिक्स n×n है और I पहचान मैट्रिक्स है, और मेनेज संख्याएं इस प्रकार दी गई हैं

जहां I' (0, 1)-स्थिति (i, i + 1) और (n, 1) में गैर-शून्य प्रविष्टियों वाला मैट्रिक्स है।

सीमा

ब्रेगमैन-मिन्क असमानता, 1963 में एच. मिन्क द्वारा अनुमानित[15] और लेव एम ब्रेगमैन|एल द्वारा सिद्ध किया गया। 1973 में एम. ब्रैगमैन,[16] n × n (0, 1)-मैट्रिक्स के स्थायी के लिए ऊपरी सीमा देता है। यदि A के पास r हैi पंक्ति i में प्रत्येक 1 ≤ i ≤ n के लिए, असमानता बताती है कि

वैन डेर वेर्डन का अनुमान

1926 में, बार्टेल लिएन्डर्ट वान डेर वेर्डन ने अनुमान लगाया कि सभी के बीच न्यूनतम स्थायी n × n दोगुना स्टोकेस्टिक मैट्रिक्स n!/n हैn, मैट्रिक्स द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ 1/n के बराबर हैं।[17] इस अनुमान के प्रमाण 1980 में बी. गेयरस द्वारा प्रकाशित किए गए थे[18] और 1981 में जी. पी. एगोरीचेव द्वारा[19] और डी. आई. फालिकमैन;[20] एगोरीचेव का प्रमाण अलेक्जेंड्रोव-फेन्चेल असमानता का अनुप्रयोग है।[21] इस काम के लिए, एगोरीचेव और फालिकमैन ने 1982 में फुलकर्सन पुरस्कार जीता।[22]

गणना

परिभाषा का उपयोग करते हुए, स्थायी कंप्यूटिंग का भोला दृष्टिकोण अपेक्षाकृत छोटे मैट्रिक्स के लिए भी कम्प्यूटेशनल रूप से संभव नहीं है। सबसे तेज़ ज्ञात एल्गोरिदम में से H. J. Ryser के कारण है।[23] रायसर का सूत्र|राइसर की विधि समावेशन-बहिष्करण सिद्धांत पर आधारित है|समावेश-बहिष्करण सूत्र जिसे दिया जा सकता है[24] इस प्रकार: चलो K कॉलम को हटाकर A से प्राप्त किया जा सकता है की पंक्ति-योग का उत्पाद बनें , और जाने के मानों का योग हो हर संभव से अधिक . तब

इसे मैट्रिक्स प्रविष्टियों के संदर्भ में निम्नानुसार फिर से लिखा जा सकता है:
ऐसा माना जाता है कि निर्धारक की तुलना में स्थायी की गणना करना अधिक कठिन है। जबकि निर्धारक की गणना गाऊसी विलोपन द्वारा बहुपद समय में की जा सकती है, गाऊसी विलोपन का उपयोग स्थायी की गणना के लिए नहीं किया जा सकता है। इसके अलावा, (0,1)-मैट्रिक्स के स्थायी की गणना तीव्र-पी-पूर्ण|#पी-पूर्ण है। इस प्रकार, यदि स्थायी की गणना किसी भी विधि द्वारा बहुपद समय में की जा सकती है, तो एफपी (जटिलता) = तेज-पी | # पी, जो पी = एनपी समस्या | पी = एनपी से भी अधिक मजबूत कथन है। हालाँकि, जब की प्रविष्टियाँ गैर-नकारात्मक होती हैं, तो स्थायी की गणना यादृच्छिक एल्गोरिथ्म बहुपद समय में सन्निकटन एल्गोरिथ्म से की जा सकती है, त्रुटि तक , कहाँ स्थायी और का मान है मनमाना है.[25] सकारात्मक निश्चित मैट्रिक्स के निश्चित सेट के स्थायी को संभाव्य बहुपद समय में भी अनुमानित किया जा सकता है: इस सन्निकटन की सबसे अच्छी प्राप्य त्रुटि है ( पुनः स्थायी का मान है)।[26]


मैकमोहन का मास्टर प्रमेय

स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी जनरेटिंग फ़ंक्शन के माध्यम से है। होने देना क्रम n का वर्ग मैट्रिक्स बनें। बहुभिन्नरूपी जनरेटिंग फ़ंक्शन पर विचार करें:

का गुणांक में पर्म(ए) है.[27]

सामान्यीकरण के रूप में, n गैर-नकारात्मक पूर्णांकों के किसी भी अनुक्रम के लिए, परिभाषित करना:

के गुणांक के रूप में में स्थायी और निर्धारक से संबंधित मैकमोहन का मास्टर प्रमेय है:[28]
जहां I क्रम n पहचान मैट्रिक्स है और X विकर्ण के साथ विकर्ण मैट्रिक्स है

आयताकार आव्यूह

गैर-वर्ग मैट्रिक्स पर लागू करने के लिए स्थायी फ़ंक्शन को सामान्यीकृत किया जा सकता है। दरअसल, कई लेखक इसे स्थायी की परिभाषा बनाते हैं और वर्ग आव्यूहों पर प्रतिबंध को विशेष मामला मानते हैं।[29] विशेष रूप से, m×n मैट्रिक्स के लिए एम ≤ एन के साथ, परिभाषित करें

जहाँ P(n,m) n-सेट {1,2,...,n} के सभी m-क्रमपरिवर्तन का समुच्चय है।[30]

स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि A, m≤n के साथ m×n मैट्रिक्स है, तो मान लीजिए K कॉलम को हटाकर A से प्राप्त किया जा सकता है की पंक्ति-योग का उत्पाद बनें , और जाने के मानों का योग हो हर संभव से अधिक . तब[10]

विशिष्ट प्रतिनिधियों की प्रणालियाँ

गैर-वर्ग मैट्रिक्स के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक तरीके से उपयोग करने की अनुमति देता है। उदाहरण के लिए:

आइए एस1, एस2, ..., एसm m ≤ n के साथ n-सेट के उपसमुच्चय (जरूरी नहीं कि अलग) हों। उपसमुच्चय के इस संग्रह की घटना मैट्रिक्स एम × एन (0,1)-मैट्रिक्स ए है। इस संग्रह की ट्रांसवर्सल (कॉम्बिनेटरिक्स) (एसडीआर) की संख्या पर्म (ए) है।[31]

यह भी देखें

टिप्पणियाँ

  1. Marcus, Marvin; Minc, Henryk (1965). "स्थायी". Amer. Math. Monthly. 72 (6): 577–591. doi:10.2307/2313846. JSTOR 2313846.
  2. Minc (1978)
  3. Muir & Metzler (1960)
  4. Cauchy, A. L. (1815), "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment.", Journal de l'École Polytechnique, 10: 91–169
  5. Muir & Metzler (1960)
  6. van Lint & Wilson 2001, p. 108
  7. Ryser 1963, pp. 25 – 26
  8. Percus 1971, p. 2
  9. 9.0 9.1 Percus 1971, p. 12
  10. 10.0 10.1 Ryser 1963, p. 26
  11. Aaronson, Scott (14 Nov 2010). "रैखिक प्रकाशिकी की कम्प्यूटेशनल जटिलता". arXiv:1011.3245 [quant-ph].
  12. Bhatia, Rajendra (1997). मैट्रिक्स विश्लेषण. New York: Springer-Verlag. pp. 16–19. ISBN 978-0-387-94846-1.
  13. 13.0 13.1 Ryser 1963, p. 124
  14. Ryser 1963, p. 125
  15. Minc, Henryk (1963), "Upper bounds for permanents of (0,1)-matrices", Bulletin of the American Mathematical Society, 69 (6): 789–791, doi:10.1090/s0002-9904-1963-11031-9
  16. van Lint & Wilson 2001, p. 101
  17. van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
  18. 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.
  19. Egoryčev, G. P. (1980), Reshenie problemy van-der-Vardena dlya permanentov (in русский), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR 0602332. Egorychev, G. P. (1981), "Proof of the van der Waerden conjecture for permanents", Akademiya Nauk SSSR (in русский), 22 (6): 65–71, 225, MR 0638007. 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.
  20. Falikman, D. I. (1981), "Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix", Akademiya Nauk Soyuza SSR (in русский), 29 (6): 931–938, 957, MR 0625097.
  21. Brualdi (2006) p.487
  22. Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
  23. Ryser (1963, p. 27)
  24. van Lint & Wilson (2001) p. 99
  25. Jerrum, M.; Sinclair, A.; Vigoda, E. (2004), "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", Journal of the ACM, 51 (4): 671–697, CiteSeerX 10.1.1.18.9466, doi:10.1145/1008731.1008738, S2CID 47361920
  26. Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (2017). "सकारात्मक अर्धनिश्चित मैट्रिक्स के स्थायी अनुमान के लिए एक क्वांटम-प्रेरित एल्गोरिदम". Phys. Rev. A. 96 (2): 022329. arXiv:1609.02416. Bibcode:2017PhRvA..96b2329C. doi:10.1103/PhysRevA.96.022329. S2CID 54194194.
  27. Percus 1971, p. 14
  28. Percus 1971, p. 17
  29. In particular, Minc (1978) and Ryser (1963) do this.
  30. Ryser 1963, p. 25
  31. Ryser 1963, p. 54

संदर्भ

अग्रिम पठन

बाहरी संबंध