स्थायी (गणित)
रैखिक बीजगणित में, वर्ग आव्युह का स्थाई, सारणिक के समान आव्युह का फलन है। अतः स्थायी, साथ ही निर्धारक, आव्युह की प्रविष्टियों में बहुपद है।[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