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

From Vigyanwiki
(Created page with "{{Short description|Polynomial of the elements of a matrix}} रैखिक बीजगणित में, एक वर्ग मैट्रिक्स का स्...")
 
No edit summary
 
(6 intermediate revisions by 3 users not shown)
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> दोनों आव्युह के अधिक सामान्य फलन की विशेष स्तिथि हैं जिन्हें [[िम्मनत|अन्तर्निहित]] कहा जाता है।


== परिभाषा ==
== परिभाषा ==
एक का स्थायी {{math|''n''×''n''}} आव्यूह {{math|1=''A'' = (''a''<sub>''i,j''</sub>)}} परिभाषित किया जाता है
{{math|''n''×''n''}} आव्यूह {{math|1=''A'' = (''a''<sub>''i,j''</sub>)}} के स्थायी को इस प्रकार परिभाषित किया गया है


<math display="block"> \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.</math>
<math display="block"> \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.                                                                                           </math>
यहां का योग [[सममित समूह]] एस के सभी तत्वों σ तक फैला हुआ है<sub>''n''</sub>; यानी संख्या 1, 2, ..., एन के सभी क्रम[[परिवर्तन]] पर।
यहां का योग [[सममित समूह]] ''S<sub>n</sub>'' के सभी अवयव σ तक फैला हुआ है; यानी संख्या 1, 2, ..., ''n'' के सभी क्रम[[परिवर्तन]] पर।


उदाहरण के लिए,
इस प्रकार उदाहरण के लिए,


<math display="block">\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc,</math>
<math display="block">\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc,</math>
और
और


<math display="block">\operatorname{perm}\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh.</math>
<math display="block">\operatorname{perm}\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh.                                         </math>
के स्थायी की परिभाषा के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है।
जहाँ A के स्थायी की परिभाषा A के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है।
 
मैट्रिक्स ए के स्थायी को प्रति ए, पर्म ए, या प्रति ए द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ। मिनक आयताकार मैट्रिक्स के स्थायीकरण के लिए 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>


आव्युह A के स्थायी को प्रति A, पर्म A, या प्रति A द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ दर्शाया जाता है। मिनक आयताकार आव्युह के स्थायीकरण के लिए 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>
== गुण ==
== गुण ==
यदि कोई स्थायी को एक मानचित्र के रूप में देखता है जो n वैक्टर को तर्क के रूप में लेता है, तो यह एक [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि वैक्टर के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अलावा, एक वर्ग मैट्रिक्स दिया गया है <math>A = \left(a_{ij}\right)</math> क्रम का n:<ref>{{harvnb|Ryser|1963|loc=pp. 25 &ndash; 26}}</ref>
यदि कोई स्थायी को मानचित्र के रूप में देखता है जो n सदिश को तर्क के रूप में लेता है, तो यह [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि सदिश के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अतिरिक्त क्रम का n, वर्ग आव्युह <math>A = \left(a_{ij}\right)</math> दिया गया है :<ref>{{harvnb|Ryser|1963|loc=pp. 25 &ndash; 26}}</ref>
* की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म() अपरिवर्तनीय है। इस संपत्ति को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स]] पी और क्यू के लिए प्रतीकात्मक रूप से पर्म() = पर्म(पीएक्यू) के रूप में लिखा जा सकता है।
* A की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(A) अपरिवर्तनीय है। इस गुण को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स|क्रमपरिवर्तन आव्युह]] ''P'' और ''Q'' के लिए प्रतीकात्मक रूप से पर्म(A) = पर्म(''PAQ'') के रूप में लिखा जा सकता है।
* A की किसी एक पंक्ति या स्तंभ को एक [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) बदल जाता है,
* A की किसी पंक्ति या स्तंभ को [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) में परिवर्तित हो जाता है,
* [[ खिसकाना ]] के तहत पर्म (ए) अपरिवर्तनीय है, यानी, पर्म () = पर्म (ए)<sup>टी</sup>).
* पर्म(A) [[ खिसकाना |स्थानान्तरण]] के तहत अपरिवर्तनीय है, अर्थात, पर्म(''A'') = perm(''A''<sup>T</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>
 
 
== निर्धारकों से संबंध ==
== निर्धारकों से संबंध ==


एक पंक्ति, स्तंभ या विकर्ण के साथ निर्धारक की गणना के लिए नाबालिगों द्वारा लाप्लास का विस्तार सभी संकेतों को अनदेखा करके स्थायी तक विस्तारित होता है।<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="block">\mathbb{perm}(B)=\sum_{j=1}^n B_{i,j} M_{i,j},</math>
प्रत्येक <math display="inline">i</math> के लिए,
कहाँ <math>B_{i,j}</math> B की iवीं पंक्ति और jवें कॉलम की प्रविष्टि है, और <math display="inline">M_{i,j}</math> B की iवीं पंक्ति और jवें कॉलम को हटाकर प्राप्त सबमैट्रिक्स का स्थायी मान है।


उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए,
<math display="block">\mathbb{perm}(B)=\sum_{j=1}^n B_{i,j} M_{i,j},                                                                                                                                        </math>
जहां <math>B_{i,j}</math> ''i''th पंक्ति की प्रविष्टि है यदि <math display="inline">M_{i,j}</math> और B का ''j''th कॉलम, ''i''th पंक्ति और B के ''j''th कॉलम को घटा कर प्राप्त उपआव्युह का स्थायी है।
 
इस प्रकार से उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए,


<math display="block">\begin{align}
<math display="block">\begin{align}
Line 54: Line 52:
= {} & 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 64: Line 62:
===सममित टेंसर===
===सममित टेंसर===


[[हिल्बर्ट स्थान]]ों की सममित टेंसर शक्ति के अध्ययन में स्थायी स्वाभाविक रूप से उत्पन्न होता है।<ref>{{cite book|last1=Bhatia|first1=Rajendra|title=मैट्रिक्स विश्लेषण|date=1997|publisher=Springer-Verlag|location=New York|isbn=978-0-387-94846-1|pages=16–19}}</ref> विशेष रूप से, हिल्बर्ट स्थान के लिए <math>H</math>, होने देना <math>\vee^k H</math> निरूपित करें <math>k</math>की वें सममित टेंसर शक्ति <math>H</math>, जो टेन्सर उत्पाद#बाहरी और सममित बीजगणित का स्थान है। उस पर विशेष ध्यान दें <math>\vee^k H</math> तत्वों के सममित टेंसर#सममित उत्पाद द्वारा फैलाया गया है <math>H</math>. के लिए <math>x_1,x_2,\dots,x_k \in H</math>, हम इन तत्वों के सममित उत्पाद को परिभाषित करते हैं
[[हिल्बर्ट स्थान|हिल्बर्ट स्पेस]] की सममित टेंसर पॉवर के अध्ययन में स्थायी स्वाभाविक रूप से उत्पन्न होता है।<ref>{{cite book|last1=Bhatia|first1=Rajendra|title=मैट्रिक्स विश्लेषण|date=1997|publisher=Springer-Verlag|location=New York|isbn=978-0-387-94846-1|pages=16–19}}</ref> अतः विशेष रूप से, हिल्बर्ट स्पेस <math>H</math> के लिए <math>\vee^k H</math>, <math>H</math> की <math>k</math> सममित टेंसर पॉवर को दर्शाता है जो सममित टेंसर का स्थान है। विशेष रूप से ध्यान दें कि <math>\vee^k H</math>, <math>H</math> में अवयव के सममित उत्पादों द्वारा फैला हुआ है यदि <math>x_1,x_2,\dots,x_k \in H</math>,के लिए हम इन अवयव के सममित उत्पाद को परिभाषित करते हैं
<math display="block">
<math display="block">
x_1 \vee x_2 \vee \cdots \vee x_k =
x_1 \vee x_2 \vee \cdots \vee x_k =
Line 70: Line 68:
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> के उप-स्थान के रूप में <math>H</math> की ''k''th टेंसर पॉवर ) पर विचार करते हैं और तदनुसार <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 76: Line 74:
\rangle =
\rangle =
\operatorname{perm}\left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k</math>
\operatorname{perm}\left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k</math>
कॉची-श्वार्ज़ असमानता को लागू करने पर, हम पाते हैं <math>\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \geq 0</math>, ओर वो
कॉची-श्वार्ज़ असमानता को प्रयुक्त करने पर, हम पाते हैं कि <math>\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \geq 0</math>, और वह
<math display="block">\left|\operatorname{perm} \left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k \right|^2 \leq
<math display="block">\left|\operatorname{perm} \left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k \right|^2 \leq
\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \cdot
\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \cdot
\operatorname{perm} \left[\langle y_i,y_j \rangle\right]_{i,j = 1}^k
\operatorname{perm} \left[\langle y_i,y_j \rangle\right]_{i,j = 1}^k
</math>
</math>
===चक्र कवर===
{{main|शीर्ष चक्र कवर}}


कोई भी वर्ग आव्युह <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> V पर क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, V पर कोई भी क्रमपरिवर्तन <math>\sigma</math> प्रत्येक शीर्ष i से शीर्ष <math>\sigma(i)</math> तक चाप के साथ एक चक्र कवर से मेल खाता है।
{{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 तक चाप के भार का प्रतिनिधित्व करना।
भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध [[निर्देशित चक्र]]ों का एक संग्रह है जो ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष 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>
इसका तात्पर्य यह है कि
इसका तात्पर्य यह है कि
<math display="block"> \operatorname{perm}(A)=\sum_\sigma \operatorname{weight}(\sigma).</math>
<math display="block"> \operatorname{perm}(A)=\sum_\sigma \operatorname{weight}(\sigma).</math>
इस प्रकार A का स्थायी मान डिग्राफ के सभी चक्र-कवरों के भार के योग के बराबर है।
इस प्रकार A का स्थायी मान डिग्राफ के सभी चक्र-कवरों के भार के योग के समान है।


===उत्तम मिलान===
===उत्तम मिलान===
एक वर्ग मैट्रिक्स <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 का स्थायी मान ग्राफ़ के सभी पूर्ण मिलानों के भारों के योग के समान है।


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


===गणना ===
===गणना ===
गिनती के कई प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 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)-आव्यूहों का वर्ग है<ref name="Ryser 1963 loc=p. 124">{{harvnb|Ryser|1963|loc=p. 124}}</ref> [[प्रक्षेप्य तल|प्रत्येक पंक्ति]] और स्तंभ का योग k के समान है। इस वर्ग में प्रत्येक आव्युह A का पर्म''(A) > 0'' है। प्रक्षेप्य तलों के आपतन आव्युह n पूर्णांक > 1 के लिए वर्ग Ω(''n''<sup>2</sup> + ''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>.


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


<math display="block">\operatorname{perm}(J - I) = \operatorname{perm}\left (\begin{matrix} 0 & 1 & 1 & \dots & 1 \\ 1 & 0 & 1 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & 0 \end{matrix} \right) = n! \sum_{i=0}^n \frac{(-1)^i}{i!},</math>
<math display="block">\operatorname{perm}(J - I) = \operatorname{perm}\left (\begin{matrix} 0 & 1 & 1 & \dots & 1 \\ 1 & 0 & 1 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & 0 \end{matrix} \right) = n! \sum_{i=0}^n \frac{(-1)^i}{i!},</math>
जहां J सभी 1 का मैट्रिक्स n×n है और I पहचान मैट्रिक्स है, और मेनेज संख्याएं इस प्रकार दी गई हैं
जहां J सभी 1 का आव्युह n×n है और I पहचान आव्युह है, और मेनेज संख्याएं इस प्रकार दी गई हैं


<math display="block">\begin{align}
<math display="block">\begin{align}
Line 116: Line 115:
& = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!,
& = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!,
\end{align}</math>
\end{align}</math>
जहां I' (0, 1)-स्थिति (i, i + 1) और (n, 1) में गैर-शून्य प्रविष्टियों वाला मैट्रिक्स है।
जहां I' (0, 1)-स्थिति (i, i + 1) और (n, 1) में गैर-शून्य प्रविष्टियों वाला आव्युह है।


===सीमा ===
===सीमा ===
ब्रेगमैन-मिन्क असमानता, 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 में H. मिन्क द्वारा अनुमानित<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> और लेव M ब्रेगमैन L द्वारा सिद्ध किया गया। 1973 में M. ब्रैगमैन,<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>


== वैन डेर वेर्डन का अनुमान ==
== वैन डेर वेर्डन का अनुमान ==
1926 में, [[बार्टेल लिएन्डर्ट वान डेर वेर्डन]] ने अनुमान लगाया कि सभी के बीच न्यूनतम स्थायी {{nowrap|''n'' &times; ''n''}} [[दोगुना स्टोकेस्टिक मैट्रिक्स]] n<nowiki>!</nowiki>/n है<sup>n</sup>, मैट्रिक्स द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ 1/n के बराबर हैं।<ref>{{citation
चूंकि 1926 में, [[बार्टेल लिएन्डर्ट वान डेर वेर्डन]] ने अनुमान लगाया कि सभी के बीच न्यूनतम स्थायी {{nowrap|''n'' &times; ''n''}} [[दोगुना स्टोकेस्टिक मैट्रिक्स|दोगुना स्टोकेस्टिक आव्युह]] ''n''!/''n<sup>n</sup>'' है, आव्युह द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ 1/n के समान हैं।<ref>{{citation
  | last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden
  | last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden
  | journal = Jber. Deutsch. Math.-Verein.
  | journal = Jber. Deutsch. Math.-Verein.
Line 130: Line 128:
  | title = Aufgabe 45
  | title = Aufgabe 45
  | volume = 35
  | volume = 35
  | year = 1926}}.</ref> इस अनुमान के प्रमाण 1980 में बी. गेयरस द्वारा प्रकाशित किए गए थे<ref>{{citation
  | year = 1926}}.</ref> इस अनुमान के प्रमाण 1980 में B. गेयरस द्वारा प्रकाशित किए गए थे<ref>{{citation
  | last = Gyires | first = B.
  | last = Gyires | first = B.
  | issue = 3–4
  | issue = 3–4
Line 138: Line 136:
  | title = The common source of several inequalities concerning doubly stochastic matrices
  | title = The common source of several inequalities concerning doubly stochastic matrices
  | volume = 27
  | volume = 27
  | year = 1980}}.</ref> और 1981 में जी. पी. एगोरीचेव द्वारा<ref>{{citation
  | year = 1980}}.</ref> और 1981 में G. P. एगोरीचेव द्वारा<ref>{{citation
  | last = Egoryčev | first = G. P.
  | last = Egoryčev | first = G. P.
  | language = ru
  | language = ru
Line 165: Line 163:
  | title = The solution of van der Waerden's problem for permanents
  | title = The solution of van der Waerden's problem for permanents
  | volume = 42
  | volume = 42
  | year = 1981}}.</ref> और डी. आई. फालिकमैन;<ref>{{citation
  | year = 1981}}.</ref> और D. I. फालिकमैन;<ref>{{citation
  | last = Falikman | first = D. I.
  | last = Falikman | first = D. I.
  | issue = 6
  | issue = 6
Line 174: Line 172:
  | 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|स्थायी की गणना|01-स्थायी की तीव्र-पी-पूर्णता}}


 
इस प्रकार से परिभाषा का उपयोग करते हुए, स्थायी कंप्यूटिंग का भोला दृष्टिकोण अपेक्षाकृत छोटे आव्युह के लिए भी कम्प्यूटेशनल रूप से संभव नहीं है। और अधिक तीव्र ज्ञात एल्गोरिदम में से एक H. J. रायसर के कारण है।<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> मान लीजिए कि K कॉलम को घटा कर <math>A_k</math> को A से प्राप्त किया जाता है, <math>P(A_k)</math> को <math>A_k</math> की पंक्ति-योग का उत्पाद माना जाता है और <math>\Sigma_k</math> को सभी संभावित <math>A_k</math> पर <math>P(A_k)</math> के मानों का योग माना जाता है।
== गणना ==
{{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>. तब
<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)-आव्युह के स्थाई की गणना #P-पूर्ण है। इस प्रकार, यदि किसी विधि द्वारा बहुपद समय में स्थायी की गणना की जा सकती है, तो [[एफपी (जटिलता)|FP]] = #P, जो P = NP से भी अधिक स्थिर कथन है। चूंकि, जब A की प्रविष्टियाँ गैर-ऋणात्मक होती हैं, तो स्थायी की गणना लगभग संभाव्य बहुपद समय में की जा सकती है, यदि <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|मैकमोहन का मास्टर प्रमेय}}
स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी [[जनरेटिंग फ़ंक्शन]] के माध्यम से है। होने देना <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> पर्म(A) है.<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>
स्थायी और निर्धारक से संबंधित मैकमोहन का मास्टर प्रमेय है:<ref>{{harvnb|Percus|1971|loc=p. 17}}</ref>
स्थायी और निर्धारक से संबंधित मैकमोहन का मास्टर प्रमेय है:<ref>{{harvnb|Percus|1971|loc=p. 17}}</ref>
<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> के लिए m × n के साथ, परिभाषित करें  
<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 आव्युह है, तो मान लीजिए कि K कॉलम को घटा कर <math>A_k</math> को A से प्राप्त किया जाता है, मान लीजिए कि <math>P(A_k)</math> <math>A_k</math> की पंक्ति-योग का उत्पाद है और मान लीजिए कि <math>\sigma_k</math> सभी संभावित <math>A_k</math> पर <math>P(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>
 


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


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


==संदर्भ==
==संदर्भ==
Line 231: Line 221:
*{{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}}
*{{PlanetMath |urlname=VanDerWaerdensPermanentConjecture |title=Van der Waerden's permanent conjecture}}
*{{PlanetMath |urlname=VanDerWaerdensPermanentConjecture |title=Van der Waerden's permanent conjecture}}
[[Category: बीजगणित]] [[Category: लीनियर अलजेब्रा]] [[Category: मैट्रिक्स सिद्धांत]] [[Category: क्रमपरिवर्तन]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 русский-language sources (ru)]]
[[Category:Created On 19/07/2023]]
[[Category:Created On 19/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:क्रमपरिवर्तन]]
[[Category:बीजगणित]]
[[Category:मैट्रिक्स सिद्धांत]]
[[Category:लीनियर अलजेब्रा]]

Latest revision as of 13:15, 4 August 2023

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

परिभाषा

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

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

इस प्रकार उदाहरण के लिए,

और

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

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

इस प्रकार से स्थायी शब्द की उत्पत्ति 1812 में कॉची के साथ संबंधित प्रकार के फलन के लिए "फॉन्क्शन सिमेट्रिक्स परमानेंटेस" के रूप में हुई थी,[4] और इसका उपयोग मुइर और मेट्ज़लर द्वारा किया गया था[5] आधुनिक, अधिक विशिष्ट, अर्थ में किया गया था।[6]

गुण

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

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

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

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

प्रत्येक के लिए,

जहां ith पंक्ति की प्रविष्टि है यदि और B का jth कॉलम, ith पंक्ति और B के jth कॉलम को घटा कर प्राप्त उपआव्युह का स्थायी है।

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

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

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

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

अनुप्रयोग

सममित टेंसर

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

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

चक्र कवर

कोई भी वर्ग आव्युह शीर्ष समुच्चय पर भारित निर्देशित ग्राफ के आसन्न आव्युह के रूप में देखा जा सकता है , साथ शीर्ष i से शीर्ष j तक चाप के भार का प्रतिनिधित्व करना है ।

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

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

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

उत्तम मिलान

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

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

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

गणना

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

इस प्रकार से मान लीजिए Ω(n,k) क्रम n के सभी (0, 1)-आव्यूहों का वर्ग है[13] प्रत्येक पंक्ति और स्तंभ का योग k के समान है। इस वर्ग में प्रत्येक आव्युह A का पर्म(A) > 0 है। प्रक्षेप्य तलों के आपतन आव्युह n पूर्णांक > 1 के लिए वर्ग Ω(n2 + 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) = 24e.

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

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

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

सीमा

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

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

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

गणना

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

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

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

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

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

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

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

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

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

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

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

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

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

मान लीजिए कि S1, S2, ..., Sm, mn वाले n-समुच्चय के उपसमुच्चय (आवश्यक नहीं कि अलग) हों। उपसमुच्चय के इस संग्रह की घटना आव्युह एक m × n (0,1)-आव्युह A है। इस संग्रह के विशिष्ट प्रतिनिधियों (एसडीआर) की प्रणालियों की संख्या पर्म (A) है।[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

संदर्भ

अग्रिम पठन

बाहरी संबंध