स्थायी (गणित): Difference between revisions
No edit summary |
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> दोनों आव्युह के अधिक सामान्य फलन की विशेष स्तिथि हैं जिन्हें [[िम्मनत|अन्तर्निहित]] कहा जाता है। | ||
== परिभाषा == | == परिभाषा == | ||
{{math|''n''×''n''}} आव्यूह | {{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> | ||
यहां का योग [[सममित समूह]] ''S<sub>n</sub>'' के सभी अवयव | यहां का योग [[सममित समूह]] ''S<sub>n</sub>'' के सभी अवयव σ तक फैला हुआ है; यानी संख्या 1, 2, ..., ''n'' के सभी क्रम[[परिवर्तन]] पर। | ||
इस प्रकार उदाहरण के लिए, | इस प्रकार उदाहरण के लिए, | ||
Line 16: | Line 16: | ||
जहाँ A के स्थायी की परिभाषा A के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है। | जहाँ A के स्थायी की परिभाषा A के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है। | ||
आव्युह A के स्थायी को प्रति A, पर्म A, या प्रति A द्वारा दर्शाया जाता है, कभी-कभी तर्क के चारों ओर कोष्ठक के साथ दर्शाया जाता है। मिनक आयताकार आव्युह के स्थायीकरण के लिए Per(A) का उपयोग करता है, और जब A वर्ग आव्युह है तो per(A) का उपयोग करता है।<ref>{{harvtxt|Minc|1978}}</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 में कॉची के साथ संबंधित प्रकार के फलन | इस प्रकार से स्थायी शब्द की उत्पत्ति 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 सदिश को तर्क के रूप में लेता है, तो यह [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि सदिश के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अतिरिक्त | यदि कोई स्थायी को मानचित्र के रूप में देखता है जो n सदिश को तर्क के रूप में लेता है, तो यह [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि सदिश के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अतिरिक्त क्रम का n, वर्ग आव्युह <math>A = \left(a_{ij}\right)</math> दिया गया है :<ref>{{harvnb|Ryser|1963|loc=pp. 25 – 26}}</ref> | ||
* A की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(A) अपरिवर्तनीय है। इस गुण को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स|क्रमपरिवर्तन आव्युह]] ''P'' और ''Q'' के लिए प्रतीकात्मक रूप से पर्म(A) = पर्म(''PAQ'') के रूप में लिखा जा सकता है। | * A की पंक्तियों और/या स्तंभों के मनमाने क्रमपरिवर्तन के तहत पर्म(A) अपरिवर्तनीय है। इस गुण को किसी भी उचित आकार के [[क्रमपरिवर्तन मैट्रिक्स|क्रमपरिवर्तन आव्युह]] ''P'' और ''Q'' के लिए प्रतीकात्मक रूप से पर्म(A) = पर्म(''PAQ'') के रूप में लिखा जा सकता है। | ||
* A की किसी पंक्ति या स्तंभ को [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) में परिवर्तित हो जाता है, | * A की किसी पंक्ति या स्तंभ को [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) में परिवर्तित हो जाता है, | ||
* पर्म(A) [[ खिसकाना |स्थानान्तरण]] के तहत अपरिवर्तनीय है, अर्थात, पर्म(''A'') = perm(''A''<sup>T</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</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 33: | Line 33: | ||
<math display="block">\mathbb{perm}(B)=\sum_{j=1}^n B_{i,j} M_{i,j},</math> | <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 | जहां <math>B_{i,j}</math> ''i''th पंक्ति की प्रविष्टि है यदि <math display="inline">M_{i,j}</math> और B का ''j''th कॉलम, ''i''th पंक्ति और B के ''j''th कॉलम को घटा कर प्राप्त उपआव्युह का स्थायी है। | ||
इस प्रकार से उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए, | इस प्रकार से उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए, | ||
Line 56: | Line 56: | ||
<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> चूंकि इसकी दो [[ग्राफ-सैद्धांतिक]] व्याख्याएँ हैं: एक [[निर्देशित ग्राफ]] के [[शीर्ष चक्र कवर]] के भार के योग के रूप में और एक [[द्विदलीय ग्राफ]] में सही मिलान के भार के योग के रूप में किया जाता है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
Line 62: | 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>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 68: | 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> के उप-स्थान के रूप में <math>H</math> की ''k''th | यदि हम <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 79: | Line 79: | ||
\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|शीर्ष चक्र कवर}} | {{main|शीर्ष चक्र कवर}} | ||
कोई भी वर्ग आव्युह <math>A = (a_{ij})_{i,j=1}^n</math> शीर्ष समुच्चय | कोई भी वर्ग आव्युह <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> होता है | इस प्रकार से भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध [[निर्देशित चक्र|निर्देशित चक्रों]] का संग्रह है जो की ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष i का अद्वितीय "उत्तराधिकारी" <math>\sigma(i)</math> होता है चक्र आवरण में, इत्यादि <math>\sigma</math> V पर क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, V पर कोई भी क्रमपरिवर्तन <math>\sigma</math> प्रत्येक शीर्ष 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>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) आव्यूहों के स्थायी मान == | ||
Line 102: | Line 102: | ||
गिनती के अनल प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 0 और 1 हैं। | गिनती के अनल प्रश्नों के उत्तरों की गणना उन आव्यूहों के स्थायी मानों के रूप में की जा सकती है जिनमें प्रविष्टियों के रूप में केवल 0 और 1 हैं। | ||
इस प्रकार से मान लीजिए ''Ω(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,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>e</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>e</sup>. | ||
स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक n-समुच्चय {1, 2, ..., ''n''}, के लिए, मान लीजिए कि <math>A = (a_{ij})</math> (0, 1)-आव्युह है जहां ''a<sub>ij</sub>'' = 1 है यदि ''i'' → ''j'' | स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक 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> | ||
Line 122: | Line 122: | ||
== वैन डेर वेर्डन का अनुमान == | == वैन डेर वेर्डन का अनुमान == | ||
चूंकि 1926 में, [[बार्टेल लिएन्डर्ट वान डेर वेर्डन]] ने अनुमान लगाया कि सभी के बीच न्यूनतम स्थायी {{nowrap|''n'' × ''n''}} [[दोगुना स्टोकेस्टिक मैट्रिक्स|दोगुना स्टोकेस्टिक आव्युह]] ''n''!/''n<sup>n</sup>'' है, आव्युह द्वारा प्राप्त किया गया जिसके लिए सभी प्रविष्टियाँ 1/n के समान | चूंकि 1926 में, [[बार्टेल लिएन्डर्ट वान डेर वेर्डन]] ने अनुमान लगाया कि सभी के बीच न्यूनतम स्थायी {{nowrap|''n'' × ''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 176: | Line 176: | ||
{{main|स्थायी की गणना|01-स्थायी की तीव्र-पी-पूर्णता}} | {{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> के मानों का योग माना जाता है। | ||
<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)-आव्युह के स्थाई की गणना | इस प्रकार से यह माना जाता है कि निर्धारक की तुलना में स्थायी की गणना करना अधिक कठिन है। जबकि निर्धारक की गणना गाऊसी विलोपन द्वारा बहुपद समय में की जा सकती है, गाऊसी विलोपन का उपयोग स्थायी की गणना के लिए नहीं किया जा सकता है। इसके अतिरिक्त, (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|मैकमोहन का मास्टर प्रमेय}} | {{main|मैकमोहन का मास्टर प्रमेय}} | ||
स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी [[जनरेटिंग फ़ंक्शन|जनरेटिंग फलन]] | स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी [[जनरेटिंग फ़ंक्शन|जनरेटिंग फलन]] के माध्यम से है। मान लीजिये <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> पर्म(A) है.<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 गैर-ऋणात्मक | सामान्यीकरण के रूप में, 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> | ||
Line 194: | Line 194: | ||
जहां 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> के लिए 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-समुच्चय | जहाँ P(n,m) n-समुच्चय {1,2,...,n} के सभी m-क्रमपरिवर्तन का समुच्चय है।<ref>{{harvnb|Ryser|1963|loc=p. 25}}</ref> | ||
स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि A, m ≤ n के साथ एक m × n आव्युह है, तो मान लीजिए कि K कॉलम को घटा कर | स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि 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> | ||
===विशिष्ट प्रतिनिधियों की प्रणालियाँ=== | ===विशिष्ट प्रतिनिधियों की प्रणालियाँ=== | ||
गैर-वर्ग आव्युह के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक विधियों | गैर-वर्ग आव्युह के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक विधियों से उपयोग करने की अनुमति देता है। उदाहरण के लिए: | ||
मान लीजिए कि ''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> | मान लीजिए कि ''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> |
Revision as of 11:41, 24 July 2023
रैखिक बीजगणित में, वर्ग आव्युह का स्थायी (गणित), सारणिक के समान आव्युह का फलन है। अतः स्थायी, साथ ही निर्धारक, आव्युह की प्रविष्टियों में बहुपद है।[1] दोनों आव्युह के अधिक सामान्य फलन की विशेष स्तिथि हैं जिन्हें अन्तर्निहित कहा जाता है।
परिभाषा
n×n आव्यूह A = (ai,j) के स्थायी को इस प्रकार परिभाषित किया गया है
इस प्रकार उदाहरण के लिए,
आव्युह 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]
प्रत्येक के लिए,
इस प्रकार से उदाहरण के लिए, पहले कॉलम के साथ विस्तार करते हुए,
अनुप्रयोग
सममित टेंसर
हिल्बर्ट स्पेस की सममित टेंसर पॉवर के अध्ययन में स्थायी स्वाभाविक रूप से उत्पन्न होता है।[12] अतः विशेष रूप से, हिल्बर्ट स्पेस के लिए , की सममित टेंसर पॉवर को दर्शाता है जो सममित टेंसर का स्थान है। विशेष रूप से ध्यान दें कि , में अवयव के सममित उत्पादों द्वारा फैला हुआ है यदि ,के लिए हम इन अवयव के सममित उत्पाद को परिभाषित करते हैं
चक्र कवर
कोई भी वर्ग आव्युह शीर्ष समुच्चय पर भारित निर्देशित ग्राफ के आसन्न आव्युह के रूप में देखा जा सकता है , साथ शीर्ष i से शीर्ष j तक चाप के भार का प्रतिनिधित्व करना है ।
इस प्रकार से भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध निर्देशित चक्रों का संग्रह है जो की ग्राफ में सभी शीर्षों को कवर करता है। इस प्रकार, डिग्राफ में प्रत्येक शीर्ष i का अद्वितीय "उत्तराधिकारी" होता है चक्र आवरण में, इत्यादि V पर क्रमपरिवर्तन का प्रतिनिधित्व करता है। इसके विपरीत, V पर कोई भी क्रमपरिवर्तन प्रत्येक शीर्ष i से शीर्ष तक चाप के साथ एक चक्र कवर से मेल खाता है।
यदि चक्र-कवर का भार प्रत्येक चक्र में चापों के भार के उत्पाद के रूप में परिभाषित किया गया है, तो
उत्तम मिलान
अतः वर्ग आव्युह को एक द्विदलीय ग्राफ के आसन्न आव्युह के रूप में भी देखा जा सकता है जिसमें इस प्रकार से शीर्ष और दूसरी ओर होता है, जिसमें शीर्ष से शीर्ष तक किनारे के भार का प्रतिनिधित्व करता है यदि एक पूर्ण मिलान का भार जो से से मेल खाता है, तो मिलान में किनारों के भार के उत्पाद के रूप में परिभाषित किया गया है, तो
(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 है यदि i → j को क्रमपरिवर्तन में अनुमति है और aij = 0 अन्यथा। तब पर्म(A) n-समुच्चय के क्रमपरिवर्तन की संख्या के समान है जो सभी प्रतिबंधों को पूर्ण करता है।[9] इसके दो प्रसिद्ध विशेष स्तिथियो विक्षोभ समस्या और मेनेज समस्या का समाधान हैं: बिना किसी निश्चित बिंदु (विक्षोभ) वाले n-समुच्चय के क्रमपरिवर्तन की संख्या दी गई है
सीमा
ब्रेगमैन-मिन्क असमानता, 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 से प्राप्त किया जाता है, को की पंक्ति-योग का उत्पाद माना जाता है और को सभी संभावित पर के मानों का योग माना जाता है।
मैकमोहन का मास्टर प्रमेय
स्थायी को देखने का दूसरा तरीका बहुभिन्नरूपी जनरेटिंग फलन के माध्यम से है। मान लीजिये क्रम n का वर्ग आव्युह बनें है। बहुभिन्नरूपी जनरेटिंग फलन पर विचार करें:
सामान्यीकरण के रूप में, n गैर-ऋणात्मक पूर्णांकों के किसी भी अनुक्रम के लिए, परिभाषित करना:
आयताकार आव्यूह
गैर-वर्ग आव्युह पर प्रयुक्त करने के लिए स्थायी फलन को सामान्यीकृत किया जा सकता है। इस प्रकार से, अनेक लेखक इसे स्थायी की परिभाषा बनाते हैं और वर्ग आव्यूहों पर प्रतिबंध को विशेष स्तिथि मानते हैं।[29] विशेष रूप से, m×n आव्युह के लिए m × n के साथ, परिभाषित करें
स्थायी लोगों के लिए रायसर का कम्प्यूटेशनल परिणाम भी सामान्यीकृत होता है। यदि A, m ≤ n के साथ एक m × n आव्युह है, तो मान लीजिए कि K कॉलम को घटा कर को A से प्राप्त किया जाता है, मान लीजिए कि की पंक्ति-योग का उत्पाद है और मान लीजिए कि सभी संभावित पर के मानों का योग है।[10]तब:
विशिष्ट प्रतिनिधियों की प्रणालियाँ
गैर-वर्ग आव्युह के लिए स्थायी की परिभाषा का सामान्यीकरण कुछ अनुप्रयोगों में अवधारणा को अधिक प्राकृतिक विधियों से उपयोग करने की अनुमति देता है। उदाहरण के लिए:
मान लीजिए कि S1, S2, ..., Sm, m ≤ n वाले n-समुच्चय के उपसमुच्चय (आवश्यक नहीं कि अलग) हों। उपसमुच्चय के इस संग्रह की घटना आव्युह एक m × n (0,1)-आव्युह A है। इस संग्रह के विशिष्ट प्रतिनिधियों (एसडीआर) की प्रणालियों की संख्या पर्म (A) है।[31]
यह भी देखें
- स्थायी गणना
- बापट-बेग प्रमेय, क्रम में स्थायी आँकड़ों का अनुप्रयोग
- स्लेटर निर्धारक, क्वांटम यांत्रिकी में स्थायी का अनुप्रयोग
- हफ़नियन
टिप्पणियाँ
- ↑ Marcus, Marvin; Minc, Henryk (1965). "स्थायी". Amer. Math. Monthly. 72 (6): 577–591. doi:10.2307/2313846. JSTOR 2313846.
- ↑ Minc (1978)
- ↑ Muir & Metzler (1960)
- ↑ 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
- ↑ Muir & Metzler (1960)
- ↑ van Lint & Wilson 2001, p. 108
- ↑ Ryser 1963, pp. 25 – 26
- ↑ Percus 1971, p. 2
- ↑ 9.0 9.1 Percus 1971, p. 12
- ↑ 10.0 10.1 Ryser 1963, p. 26
- ↑ Aaronson, Scott (14 Nov 2010). "रैखिक प्रकाशिकी की कम्प्यूटेशनल जटिलता". arXiv:1011.3245 [quant-ph].
- ↑ Bhatia, Rajendra (1997). मैट्रिक्स विश्लेषण. New York: Springer-Verlag. pp. 16–19. ISBN 978-0-387-94846-1.
- ↑ 13.0 13.1 Ryser 1963, p. 124
- ↑ Ryser 1963, p. 125
- ↑ 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
- ↑ van Lint & Wilson 2001, p. 101
- ↑ van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
- ↑ Gyires, B. (1980), "The common source of several inequalities concerning doubly stochastic matrices", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, MR 0604006.
- ↑ Egoryčev, G. P. (1980), Reshenie problemy van-der-Vardena dlya permanentov (in русский), 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.
- ↑ 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.
- ↑ Brualdi (2006) p.487
- ↑ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
- ↑ Ryser (1963, p. 27)
- ↑ van Lint & Wilson (2001) p. 99
- ↑ 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
- ↑ 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.
- ↑ Percus 1971, p. 14
- ↑ Percus 1971, p. 17
- ↑ In particular, Minc (1978) and Ryser (1963) do this.
- ↑ Ryser 1963, p. 25
- ↑ Ryser 1963, p. 54
संदर्भ
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
- Minc, Henryk (1978). Permanents. Encyclopedia of Mathematics and its Applications. Vol. 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005.
- Muir, Thomas; Metzler, William H. (1960) [1882]. A Treatise on the Theory of Determinants. New York: Dover. OCLC 535903.
- Percus, J.K. (1971), Combinatorial Methods, Applied Mathematical Sciences #4, New York: Springer-Verlag, ISBN 978-0-387-90027-8
- Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America
- van Lint, J.H.; Wilson, R.M. (2001), A Course in Combinatorics, Cambridge University Press, ISBN 978-0521422604
अग्रिम पठन
- Hall Jr., Marshall (1986), Combinatorial Theory (2nd ed.), New York: John Wiley & Sons, pp. 56–72, ISBN 978-0-471-09138-7 Contains a proof of the Van der Waerden conjecture.
- Marcus, M.; Minc, H. (1965), "Permanents", The American Mathematical Monthly, 72 (6): 577–591, doi:10.2307/2313846, JSTOR 2313846