स्थायी (गणित): 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> दोनों आव्युह के अधिक सामान्य फलन की विशेष स्तिथि हैं जिन्हें [[िम्मनत|अन्तर्निहित]] कहा जाता है। | ||
== परिभाषा == | == परिभाषा == | ||
{{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>'' के सभी अवयव σ तक फैला हुआ है; यानी संख्या 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 के निर्धारक से भिन्न है जिसमें क्रमपरिवर्तन के [[हस्ताक्षर (क्रमपरिवर्तन)]] को ध्यान में नहीं रखा जाता है। | |||
आव्युह 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 सदिश को तर्क के रूप में लेता है, तो यह [[बहुरेखीय मानचित्र]] है और यह सममित है (जिसका अर्थ है कि सदिश के किसी भी क्रम का परिणाम समान स्थायी होता है)। इसके अतिरिक्त क्रम का 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 की किसी पंक्ति या स्तंभ को [[अदिश (गणित)]] s से गुणा करने पर perm(A) से s⋅perm(A) में परिवर्तित हो जाता है, | ||
* [[ खिसकाना ]] के तहत | * पर्म(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> | ||
== निर्धारकों से संबंध == | == निर्धारकों से संबंध == | ||
एक पंक्ति, स्तंभ या विकर्ण के साथ निर्धारक की गणना के लिए नाबालिगों द्वारा लाप्लास का विस्तार सभी संकेतों को अनदेखा करके स्थायी तक विस्तारित होता है।<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=" | प्रत्येक <math display="inline">i</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 पंक्ति और 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> इस प्रकार से साधारण उदाहरण से पता चलता है कि ऐसा ही है। | ||
<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 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>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> के उप-स्थान के रूप में <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 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> तक चाप के साथ एक चक्र कवर से मेल खाता है। | |||
भारित निर्देशित ग्राफ का वर्टेक्स चक्र कवर डिग्राफ में शीर्ष-असंबद्ध [[निर्देशित चक्र]] | |||
यदि | यदि चक्र-कवर का भार प्रत्येक चक्र में चापों के भार के उत्पाद के रूप में परिभाषित किया गया है, तो | ||
<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 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 हैं। | ||
मान लीजिए Ω(n,k) क्रम n के सभी (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''<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> | ||
स्थायी का उपयोग प्रतिबंधित (निषिद्ध) पदों के साथ क्रमपरिवर्तन की संख्या की गणना करने के लिए भी किया जा सकता है। मानक n- | :यदि 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 का | जहां 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 में | ब्रेगमैन-मिन्क असमानता, 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'' × ''n''}} [[दोगुना स्टोकेस्टिक मैट्रिक्स]] 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 130: | Line 128: | ||
| title = Aufgabe 45 | | title = Aufgabe 45 | ||
| volume = 35 | | volume = 35 | ||
| year = 1926}}.</ref> इस अनुमान के प्रमाण 1980 में | | 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 में | | 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 | |||