क्रमपरिवर्तन आव्यूह: Difference between revisions
(The m × m) |
(इसके) |
||
Line 32: | Line 32: | ||
क्रमचय को क्रमपरिवर्तन आव्यूह के साथ संबद्ध के दो प्राकृतिक तरीके हैं; अर्थात्, m × m तत्समक आव्यूह से प्रारंभ करते हुए, {{math|''I''<sub>''m''</sub>}}, के अनुसार या तो स्तंभों को क्रमबद्ध करता है या {{pi}}. के अनुसार पंक्तियों को अनुबद्ध करता है। क्रमचय आव्यूहों को परिभाषित करने की दोनों विधियाँ साहित्य में दिखाई देती हैं और एक निरूपण में अभिव्यक्त गुणों को आसानी से दूसरे निरूपण में परिवर्तित किया जा सकता है। यह लेख मुख्य रूप से इनमें से केवल एक अभ्यावेदन से निपटेगा और दूसरे का उल्लेख केवल तभी किया जाएगा जब जागरूक होने के लिए कोई अंतर हो। | क्रमचय को क्रमपरिवर्तन आव्यूह के साथ संबद्ध के दो प्राकृतिक तरीके हैं; अर्थात्, m × m तत्समक आव्यूह से प्रारंभ करते हुए, {{math|''I''<sub>''m''</sub>}}, के अनुसार या तो स्तंभों को क्रमबद्ध करता है या {{pi}}. के अनुसार पंक्तियों को अनुबद्ध करता है। क्रमचय आव्यूहों को परिभाषित करने की दोनों विधियाँ साहित्य में दिखाई देती हैं और एक निरूपण में अभिव्यक्त गुणों को आसानी से दूसरे निरूपण में परिवर्तित किया जा सकता है। यह लेख मुख्य रूप से इनमें से केवल एक अभ्यावेदन से निपटेगा और दूसरे का उल्लेख केवल तभी किया जाएगा जब जागरूक होने के लिए कोई अंतर हो। | ||
''m × m'' क्रमपरिवर्तन आव्यूह ''P''<sub>π</sub> = (''p<sub>ij</sub>'') पहचान आव्यूह | ''m × m'' क्रमपरिवर्तन आव्यूह ''P''<sub>π</sub> = (''p<sub>ij</sub>'') पहचान आव्यूह {{math|''I''<sub>''m''</sub>}}, के स्तंभों को अनुमति देकर प्राप्त किया जाता है, अर्थात, प्रत्येक i के लिए, ''p<sub>ij</sub>'' = 1 if ''j'' = π(''i'') और {{math|''p''<sub>''ij''</sub> {{=}} 0}} अन्यथा, इस आलेख में '''स्तंभ प्रतिनिधित्व''' के रूप में संदर्भित किया जाएगा।<ref>Terminology is not standard. Most authors choose one representation to be consistent with other notation they have introduced, so there is generally no need to supply a name.</ref> चूंकि पंक्ति ''i'' में सभी प्रविष्टियां 0 हैं, इसके अतिरिक्त कि स्तंभ {{pi}}(i) में 1 दिखाई देता है हम लिख सकते हैं | ||
:<math>P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)} \\ \mathbf e_{\pi(2)} \\ \vdots \\ \mathbf e_{\pi(m)} \end{bmatrix},</math> | :<math>P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)} \\ \mathbf e_{\pi(2)} \\ \vdots \\ \mathbf e_{\pi(m)} \end{bmatrix},</math> | ||
जहां <math>\mathbf e_j</math>, '''मानक आधार सदिश''', लंबाई ''m'' के एक पंक्ति सदिश को दर्शाता है जिसमें | जहां <math>\mathbf e_j</math>, '''मानक आधार सदिश''', लंबाई ''m'' के एक पंक्ति सदिश को दर्शाता है जिसमें ''j'' वीं स्थान में 1 और प्रत्येक अन्य स्थिति में 0 है।<ref name=Bru2>Brualdi (2006) p.2</ref> | ||
उदाहरण के लिए, क्रमपरिवर्तन | |||
उदाहरण के लिए, क्रमपरिवर्तन मैट्रिक्स Pπ क्रमपरिवर्तन के अनुरूप है<math>\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{pmatrix}</math> है | |||
:<math>P_\pi | :<math>P_\pi | ||
= | = | ||
Line 62: | Line 64: | ||
\end{bmatrix}. | \end{bmatrix}. | ||
</math> | </math> | ||
ध्यान दें कि | ध्यान दें कि {{math|''I''<sub>5</sub>}} पहचान आव्यूह का ''j''वां स्तंभ अब ''P''<sub>{{pi}}</sub>.के π(''j'')वें स्तंभ के रूप में प्रकट होता है। | ||
पहचान आव्यूह {{math|''I''<sub>''m''</sub>}}, की पंक्तियों को | पहचान आव्यूह {{math|''I''<sub>''m''</sub>}}, की पंक्तियों को क्रमपरिवर्तित करके प्राप्त अन्य प्रतिनिधित्व यानी प्रत्येक j के लिए, p<sub>''ij''</sub> = 1 अगर ''I<sub>m</sub>'' = {{pi}}( ''j'',) और {{math|''p''<sub>''ij''</sub> {{=}} 0}} अन्यथा, '''पंक्ति प्रतिनिधित्व''' के रूप में संदर्भित किया जाएगा। | ||
== गुण == | == गुण == | ||
एक क्रमचय आव्यूह का स्तंभ प्रतिनिधित्व इस खंड में उपयोग किया जाता है, | एक क्रमचय आव्यूह का स्तंभ प्रतिनिधित्व इस खंड में उपयोग किया जाता है, इसके अतिरिक्त कि जब अन्यथा इंगित किया गया हो। | ||
गुणा <math>P_{\pi}</math> बार एक [[कॉलम वेक्टर|स्तंभ वेक्टर]] जी वेक्टर की पंक्तियों को क्रमबद्ध करेगा: | गुणा <math>P_{\pi}</math> बार एक [[कॉलम वेक्टर|स्तंभ वेक्टर]] जी वेक्टर की पंक्तियों को क्रमबद्ध करेगा: | ||
<math display=block>P_\pi \mathbf{g} | <math display=block>P_\pi \mathbf{g} | ||
= | = | ||
Line 94: | Line 96: | ||
\end{bmatrix}. | \end{bmatrix}. | ||
</math> | </math> | ||
इस परिणाम के बार-बार प्रयोग से पता चलता है कि यदि {{mvar|M}} उचित आकार का आव्यूह है, | इस परिणाम के बार-बार प्रयोग से पता चलता है कि यदि {{mvar|M}} उचित आकार का आव्यूह है, गुणनफल, <math>P_{\pi} M</math> की पंक्तियों का एक क्रमचय मात्र है {{mvar|M}}. यद्यपि, यह देखते हुए | ||
<math display=block>P_{\pi} \mathbf{e}_k^{\mathsf T} = \mathbf{e}_{\pi^{-1} (k)}^{\mathsf T}</math> | <math display=block>P_{\pi} \mathbf{e}_k^{\mathsf T} = \mathbf{e}_{\pi^{-1} (k)}^{\mathsf T}</math> | ||
प्रत्येक के लिए {{mvar|k}} दिखाता है कि पंक्तियों का क्रमपरिवर्तन | प्रत्येक के लिए {{mvar|k}} दिखाता है कि पंक्तियों का क्रमपरिवर्तन {{pi}}<sup>-1</sup> द्वारा दिया गया है(<math>M^{\mathsf T}</math> आव्यूह {{mvar|M}}. का [[ट्रांसपोज़ मैट्रिक्स|ट्रांसपोज़ आव्यूह]] है) | ||
क्रमचय आव्यूह [[ऑर्थोगोनल मैट्रिक्स|ऑर्थोगोनल आव्यूह]] हैं (अर्थात, <math>P_{\pi}P_{\pi}^{\mathsf T} = I</math>), | क्रमचय आव्यूह [[ऑर्थोगोनल मैट्रिक्स|ऑर्थोगोनल आव्यूह]] हैं (अर्थात, <math>P_{\pi}P_{\pi}^{\mathsf T} = I</math>), व्युत्क्रम आव्यूह उपस्थित है और इसे इस प्रकार लिखा जा सकता है | ||
<math display=block>P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{\mathsf T}.</math> | <math display=block>P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{\mathsf T}.</math> | ||
पंक्ति सदिश h को गुणा करना <math>P_{\pi}</math> वेक्टर के स्तंभ को अनुमति देगा: | पंक्ति सदिश h को गुणा करना <math>P_{\pi}</math> वेक्टर के स्तंभ को अनुमति देगा: | ||
Line 113: | Line 115: | ||
\begin{bmatrix} h_{\pi^{-1}(1)} & h_{\pi^{-1}(2)} & \cdots & h_{\pi^{-1}(n)} \end{bmatrix} | \begin{bmatrix} h_{\pi^{-1}(1)} & h_{\pi^{-1}(2)} & \cdots & h_{\pi^{-1}(n)} \end{bmatrix} | ||
</math> | </math> | ||
पुनः, इस परिणाम के बार-बार आवेदन से पता चलता है कि क्रमपरिवर्तन आव्यूह {{math|''P''<sub>π</sub>}}, यानी, {{math|''M P''<sub>π</sub>}}, द्वारा आव्यूह {{mvar|M}} को गुणा करना के बाद {{mvar|M}}. में स्तंभों को क्रमपरिवर्तित किया जाता है। यह भी ध्यान दे<math display=block>\mathbf{e}_k P_{\pi} = \mathbf{e}_{\pi (k)}.</math>{{math|''m''}} तत्व के दो क्रमपरिवर्तन {{pi}} और {{math|σ}} को देखते हुए, संबंधित क्रमचय आव्यूह {{math|''P''<sub>π</sub>}} और {{math|''P''<sub>σ</sub>}} स्तंभ सदिशों पर क्रिया करने वाले निम्नलिखित से बने होते हैं<math display="block">P_{\sigma} P_{\pi}\, \mathbf{g} = P_{\pi\,\circ\,\sigma}\, \mathbf{g}. </math> | |||
{{math|''m''}} तत्व के दो क्रमपरिवर्तन {{pi}} और {{math|σ}} को देखते हुए, संबंधित क्रमचय आव्यूह {{math|''P''<sub>π</sub>}} और {{math|''P''<sub>σ</sub>}} स्तंभ सदिशों पर क्रिया करने वाले निम्नलिखित से बने होते हैं<math display="block">P_{\sigma} P_{\pi}\, \mathbf{g} = P_{\pi\,\circ\,\sigma}\, \mathbf{g}. </math> | |||
पंक्ति सदिशों (अर्थात्, गुणन के बाद) पर कार्य करने वाले समान आव्यूह समान नियम के अनुसार रचना करते हैं | पंक्ति सदिशों (अर्थात्, गुणन के बाद) पर कार्य करने वाले समान आव्यूह समान नियम के अनुसार रचना करते हैं | ||
<math display=block> \mathbf{h} P_{\sigma} P_{\pi} = \mathbf{h} P_{\pi\,\circ\,\sigma}. </math> | <math display=block> \mathbf{h} P_{\sigma} P_{\pi} = \mathbf{h} P_{\pi\,\circ\,\sigma}. </math> | ||
Line 133: | Line 132: | ||
यदि (1) तत्समक क्रमचय को दर्शाता है, तब {{math|''P''<sub>(1)</sub>}} पहचान आव्यूह है। | यदि (1) तत्समक क्रमचय को दर्शाता है, तब {{math|''P''<sub>(1)</sub>}} पहचान आव्यूह है। | ||
मान लीजिए कि {{math|''S<sub>n</sub>''}} {1,2,..., पर [[सममित समूह]], या [[क्रमपरिवर्तन समूह]] को दर्शाता है।चूँकि {{math|''n''}}}. क्योंकि वहां हैं {{math|''n''!}} क्रमचय हैं {{math|''n''!}} क्रमपरिवर्तन आव्यूह। उपरोक्त सूत्रों के अनुसार, {{math|''n'' × ''n''}} क्रमचय आव्यूह [[पहचान तत्व]] के रूप में पहचान आव्यूह के साथ आव्यूह गुणा के तहत एक [[समूह (गणित)]] बनाते हैं। | |||
वो नक्शा {{math|''S''<sub>''n''</sub> → GL(''n'', '''Z'''<sub>2</sub>)}} जो अपने स्तंभ प्रतिनिधित्व में क्रमचय भेजता है वह एक | वो नक्शा {{math|''S''<sub>''n''</sub> → GL(''n'', '''Z'''<sub>2</sub>)}} जो अपने स्तंभ प्रतिनिधित्व में क्रमचय भेजता है वह एक विश्वसनीय प्रतिनिधित्व है। | ||
== दोगुना प्रसंभाव्य आव्यूह == | == दोगुना प्रसंभाव्य आव्यूह == | ||
एक क्रमपरिवर्तन आव्यूह अपने आप में एक [[दोगुना स्टोकेस्टिक मैट्रिक्स|दोगुना प्रसंभाव्य आव्यूह]] है, लेकिन यह इन आव्यूह के सिद्धांत में एक विशेष भूमिका भी निभाता है। बिरखॉफ-वॉन न्यूमैन प्रमेय का कहना है कि प्रत्येक दोगुना प्रसंभाव्य वास्तविक आव्यूह एक ही क्रम के क्रमपरिवर्तन मैट्रिसेस का [[उत्तल संयोजन]] है और क्रमपरिवर्तन मैट्रिसेस दोगुनी स्टोचैस्टिक आव्यूह के सेट के [[चरम बिंदु]] हैं। यही है, [[बिरखॉफ पॉलीटॉप]], डबल प्रसंभाव्य आव्यूह का सेट, क्रमपरिवर्तन आव्यूह के सेट का उत्तल पतवार है।<ref name=Bru19>Brualdi (2006) p.19</ref> | एक क्रमपरिवर्तन आव्यूह अपने आप में एक [[दोगुना स्टोकेस्टिक मैट्रिक्स|दोगुना प्रसंभाव्य आव्यूह]] है, लेकिन यह इन आव्यूह के सिद्धांत में एक विशेष भूमिका भी निभाता है। बिरखॉफ-वॉन न्यूमैन प्रमेय का कहना है कि प्रत्येक दोगुना प्रसंभाव्य वास्तविक आव्यूह एक ही क्रम के क्रमपरिवर्तन मैट्रिसेस का [[उत्तल संयोजन]] है और क्रमपरिवर्तन मैट्रिसेस दोगुनी स्टोचैस्टिक आव्यूह के सेट के [[चरम बिंदु]] हैं। यही है, [[बिरखॉफ पॉलीटॉप]], डबल प्रसंभाव्य आव्यूह का सेट, क्रमपरिवर्तन आव्यूह के सेट का उत्तल पतवार है।<ref name=Bru19>Brualdi (2006) p.19</ref> | ||
== रैखिक बीजगणितीय गुण == | == रैखिक बीजगणितीय गुण == | ||
क्रमपरिवर्तन आव्यूह का [[ट्रेस (रैखिक बीजगणित)]] क्रमपरिवर्तन के [[निश्चित बिंदु (गणित)]] की संख्या है। यदि क्रमपरिवर्तन के निश्चित बिंदु हैं, तो इसे चक्र रूप में लिखा जा सकता है {{math|1=π = (''a''<sub>1</sub>)(''a''<sub>2</sub>)...(''a''<sub>''k''</sub>)σ}} जहां {{mvar|σ}} का कोई निश्चित बिंदु नहीं है {{math|'''''e'''''<sub>''a''<sub>1</sub></sub>,'''''e'''''<sub>''a''<sub>2</sub></sub>,...,'''''e'''''<sub>''a''<sub>''k''</sub></sub>}} क्रमचय आव्यूह के [[इगनवेक्टर]] हैं। | क्रमपरिवर्तन आव्यूह का [[ट्रेस (रैखिक बीजगणित)]] क्रमपरिवर्तन के [[निश्चित बिंदु (गणित)]] की संख्या है। यदि क्रमपरिवर्तन के निश्चित बिंदु हैं, तो इसे चक्र रूप में लिखा जा सकता है {{math|1=π = (''a''<sub>1</sub>)(''a''<sub>2</sub>)...(''a''<sub>''k''</sub>)σ}} जहां {{mvar|σ}} का कोई निश्चित बिंदु नहीं है {{math|'''''e'''''<sub>''a''<sub>1</sub></sub>,'''''e'''''<sub>''a''<sub>2</sub></sub>,...,'''''e'''''<sub>''a''<sub>''k''</sub></sub>}} क्रमचय आव्यूह के [[इगनवेक्टर]] हैं। | ||
एक क्रमचय आव्यूह के [[eigenvalue|इगनवेल्यूज़]] की गणना करने के लिए <math>P_{\sigma}</math>, लिखना <math>\sigma</math> चक्रीय क्रमचय के | एक क्रमचय आव्यूह के [[eigenvalue|इगनवेल्यूज़]] की गणना करने के लिए <math>P_{\sigma}</math>, लिखना <math>\sigma</math> चक्रीय क्रमचय के गुणनफल के रूप में, कहते हैं, <math>\sigma= C_{1}C_{2} \cdots C_{t}</math>. माना कि इन चक्रों की संगत लंबाइयाँ हैं <math>l_{1},l_{2}...l_{t}</math>, और जाने <math>R_{i} (1 \le i \le t)</math> के जटिल समाधानों का समुच्चय हो <math>x^{l_{i}}=1</math>. सबका मिलन <math>R_{i}</math>s संबंधित क्रमचय आव्यूह के इगनवेल्यूज़ का सेट है। प्रत्येक इगनवेल्यूज़ की [[ज्यामितीय बहुलता]] की संख्या के बराबर होती है <math>R_{i}</math>इसमें यह सम्मिलित है।<ref name=J_Najnudel2010_4> नजनुदेल, ए नीकेघबली 2010 पृष्ठ.4</ref> | ||
[[समूह सिद्धांत]] से हम जानते हैं कि किसी भी क्रमचय को [[स्थानान्तरण (गणित)]] के गुणनफल के रूप में लिखा जा सकता है। इसलिए, कोई भी क्रमपरिवर्तन आव्यूह {{math|''P''}} पंक्ति-विनिमेय [[प्राथमिक मैट्रिक्स|प्राथमिक आव्यूह]] के | [[समूह सिद्धांत]] से हम जानते हैं कि किसी भी क्रमचय को [[स्थानान्तरण (गणित)]] के गुणनफल के रूप में लिखा जा सकता है। इसलिए, कोई भी क्रमपरिवर्तन आव्यूह {{math|''P''}} पंक्ति-विनिमेय [[प्राथमिक मैट्रिक्स|प्राथमिक आव्यूह]] के गुणनफल के रूप में कारक, प्रत्येक में निर्धारक -1 है। इस प्रकार, एक क्रमपरिवर्तन आव्यूह का निर्धारक {{math|''P''}} संबंधित क्रमचय के क्रमपरिवर्तन का संकेत है। | ||
== उदाहरण == | == उदाहरण == | ||
=== पंक्तियों और स्तंभों का क्रमपरिवर्तन === | === पंक्तियों और स्तंभों का क्रमपरिवर्तन === | ||
जब एक आव्यूह M को पीएम बनाने के लिए बाईं ओर एक क्रमचय आव्यूह P से गुणा किया जाता है, तो | जब एक आव्यूह M को पीएम बनाने के लिए बाईं ओर एक क्रमचय आव्यूह P से गुणा किया जाता है, तो गुणनफल M की पंक्तियों को क्रमबद्ध करने का परिणाम होता है। विशेष स्थिति के रूप में, यदि M एक स्तंभ वेक्टर है, तो PM की प्रविष्टियों को क्रमपरिवर्तित करने का परिणाम है | ||
{|style="text-align: center; width: 100%;" | {|style="text-align: center; width: 100%;" | ||
|[[File:Permutation matrix; P * column.svg|thumb|center|180px|''P'' · (1, 2, 3, 4)<sup>T</sup> = (4, 1, 3, 2)<sup>T</sup>]] | |[[File:Permutation matrix; P * column.svg|thumb|center|180px|''P'' · (1, 2, 3, 4)<sup>T</sup> = (4, 1, 3, 2)<sup>T</sup>]] | ||
|} | |} | ||
इसके | इसके के स्थान पर जब M को ''MP'' बनाने के अधिकार पर क्रमपरिवर्तन आव्यूह से गुणा किया जाता है, तो गुणनफल ''M'' के स्तंभ को अनुमति देने का परिणाम होता है। एक विशेष स्थिति के रूप में, यदि एम एक पंक्ति वेक्टर है, तो एमपी की प्रविष्टियों को अनुमति देने का परिणाम है M: | ||
{|style="text-align: center; width: 100%;" | {|style="text-align: center; width: 100%;" | ||
|[[File:Permutation matrix; row * P.svg|thumb|center|257px|(1, 2, 3, 4) · ''P'' = (2, 4, 3, 1)]] | |[[File:Permutation matrix; row * P.svg|thumb|center|257px|(1, 2, 3, 4) · ''P'' = (2, 4, 3, 1)]] | ||
Line 164: | Line 161: | ||
=== पंक्तियों का क्रमपरिवर्तन === | === पंक्तियों का क्रमपरिवर्तन === | ||
क्रमपरिवर्तन आव्यूह | क्रमपरिवर्तन आव्यूह ''P''<sub>π</sub> क्रमपरिवर्तन के अनुरूप <math>\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{pmatrix}</math> है | ||
:<math>P_\pi | :<math>P_\pi | ||
= | = | ||
Line 228: | Line 225: | ||
\mathbf{e}_{a_j} \\ | \mathbf{e}_{a_j} \\ | ||
\end{bmatrix}</math> | \end{bmatrix}</math> | ||
जहां | जहां '''e'''<sub>''ai''</sub> ''''R'''<sup>''j''</sup>' के लिए iवें आधार वेक्टर (एक पंक्ति के रूप में) का प्रतिनिधित्व करता है<sup>j</sup>, और जहां | ||
:<math>\begin{bmatrix} | :<math>\begin{bmatrix} | ||
1 & 2 & \ldots & j \\ | 1 & 2 & \ldots & j \\ | ||
Line 234: | Line 231: | ||
क्रमपरिवर्तन आव्यूह का क्रमचय रूप है। | क्रमपरिवर्तन आव्यूह का क्रमचय रूप है। | ||
अब, [[मैट्रिक्स गुणन|आव्यूह गुणन]] करने में, अनिवार्य रूप से दूसरे के प्रत्येक स्तंभ के साथ पहली आव्यूह की प्रत्येक पंक्ति का [[डॉट उत्पाद]] बनता है। इस उदाहरण में, हम इस आव्यूह की प्रत्येक पंक्ति के डॉट | अब, [[मैट्रिक्स गुणन|आव्यूह गुणन]] करने में, अनिवार्य रूप से दूसरे के प्रत्येक स्तंभ के साथ पहली आव्यूह की प्रत्येक पंक्ति का [[डॉट उत्पाद|डॉट गुणनफल]] बनता है। इस उदाहरण में, हम इस आव्यूह की प्रत्येक पंक्ति के डॉट गुणनफल को उन तत्वों के वेक्टर के साथ बनाएंगे जिन्हें हम क्रमपरिवर्तित करना चाहते हैं। यानी, उदाहरण के लिए, '''v''' = (''g''<sub>0</sub>,...,''g''<sub>5</sub>)<sup>T,</sup> | ||
: | :'''e'''<sub>''ai''</sub>·'''v''' = ''g<sub>ai</sub>'' | ||
तो, ऊपर दिए गए वेक्टर v के साथ क्रमचय आव्यूह का गुणनफल, (''g'' | तो, ऊपर दिए गए वेक्टर v के साथ क्रमचय आव्यूह का गुणनफल,(''g<sub>a</sub>''<sub>1</sub>, ''g<sub>a</sub>''<sub>2</sub>, ..., ''g<sub>aj</sub>'') के रूप में एक वेक्टर होगा | ||
<sub>, और यह तब v का क्रमपरिवर्तन है क्योंकि हमने कहा है कि क्रमचय रूप है | |||
:<math>\begin{pmatrix} | :<math>\begin{pmatrix} | ||
1 & 2 & \ldots & j \\ | 1 & 2 & \ldots & j \\ | ||
a_1 & a_2 & \ldots & a_j\end{pmatrix}.</math> | a_1 & a_2 & \ldots & a_j\end{pmatrix}.</math> | ||
तो, क्रमचय आव्यूह वास्तव में उनके साथ गुणा किए गए वैक्टरों में तत्वों के क्रम को क्रमबद्ध करते हैं। | तो, क्रमचय आव्यूह वास्तव में उनके साथ गुणा किए गए वैक्टरों में तत्वों के क्रम को क्रमबद्ध करते हैं। | ||
== प्रतिबंधित रूप == | == प्रतिबंधित रूप == | ||
* [[कोस्टास सरणी]], एक क्रमचय आव्यूह जिसमें प्रविष्टियों के बीच विस्थापन वैक्टर सभी अलग हैं | * [[कोस्टास सरणी]], एक क्रमचय आव्यूह जिसमें प्रविष्टियों के बीच विस्थापन वैक्टर सभी अलग-अलग होते हैं | ||
* | * एन-क्वींस पहेली, एक क्रमपरिवर्तन आव्यूह जिसमें प्रत्येक विकर्ण और प्रतिविकर्ण में अधिकतम एक प्रविष्टि होती है | ||
== यह भी देखें == | == यह भी देखें == |
Revision as of 00:05, 27 June 2023
गणित में, विशेष रूप से आव्यूह (गणित) सिद्धांत में, क्रमपरिवर्तन आव्यूह एक वर्ग बाइनरी आव्यूह होता है जिसमें प्रत्येक पंक्ति और प्रत्येक स्तंभ में 1 की बिल्कुल एक प्रविष्टि होती है और अन्यत्र 0s होता है ऐसा प्रत्येक आव्यूह, मान लीजिए P, m तत्वों के क्रमपरिवर्तन का प्रतिनिधित्व करता है और, जब किसी अन्य आव्यूह को गुणा करने के लिए उपयोग किया जाता है, मान लीजिए A, की पंक्तियों को क्रमपरिवर्तित करने के परिणामस्वरूप (PAबनाने के लिए पूर्व-गुणा करते समय) या स्तंभ (गुणा करने के बाद, AP बनाने के लिए) आव्यूह A होता है।
परिभाषा
m तत्वों के क्रमपरिवर्तन π को देखते हुए,
दो-पंक्ति रूप द्वारा दर्शाया गया है
क्रमचय को क्रमपरिवर्तन आव्यूह के साथ संबद्ध के दो प्राकृतिक तरीके हैं; अर्थात्, m × m तत्समक आव्यूह से प्रारंभ करते हुए, Im, के अनुसार या तो स्तंभों को क्रमबद्ध करता है या π. के अनुसार पंक्तियों को अनुबद्ध करता है। क्रमचय आव्यूहों को परिभाषित करने की दोनों विधियाँ साहित्य में दिखाई देती हैं और एक निरूपण में अभिव्यक्त गुणों को आसानी से दूसरे निरूपण में परिवर्तित किया जा सकता है। यह लेख मुख्य रूप से इनमें से केवल एक अभ्यावेदन से निपटेगा और दूसरे का उल्लेख केवल तभी किया जाएगा जब जागरूक होने के लिए कोई अंतर हो।
m × m क्रमपरिवर्तन आव्यूह Pπ = (pij) पहचान आव्यूह Im, के स्तंभों को अनुमति देकर प्राप्त किया जाता है, अर्थात, प्रत्येक i के लिए, pij = 1 if j = π(i) और pij = 0 अन्यथा, इस आलेख में स्तंभ प्रतिनिधित्व के रूप में संदर्भित किया जाएगा।[1] चूंकि पंक्ति i में सभी प्रविष्टियां 0 हैं, इसके अतिरिक्त कि स्तंभ π(i) में 1 दिखाई देता है हम लिख सकते हैं
जहां , मानक आधार सदिश, लंबाई m के एक पंक्ति सदिश को दर्शाता है जिसमें j वीं स्थान में 1 और प्रत्येक अन्य स्थिति में 0 है।[2]
उदाहरण के लिए, क्रमपरिवर्तन मैट्रिक्स Pπ क्रमपरिवर्तन के अनुरूप है है
ध्यान दें कि I5 पहचान आव्यूह का jवां स्तंभ अब Pπ.के π(j)वें स्तंभ के रूप में प्रकट होता है।
पहचान आव्यूह Im, की पंक्तियों को क्रमपरिवर्तित करके प्राप्त अन्य प्रतिनिधित्व यानी प्रत्येक j के लिए, pij = 1 अगर Im = π( j,) और pij = 0 अन्यथा, पंक्ति प्रतिनिधित्व के रूप में संदर्भित किया जाएगा।
गुण
एक क्रमचय आव्यूह का स्तंभ प्रतिनिधित्व इस खंड में उपयोग किया जाता है, इसके अतिरिक्त कि जब अन्यथा इंगित किया गया हो।
गुणा बार एक स्तंभ वेक्टर जी वेक्टर की पंक्तियों को क्रमबद्ध करेगा:
क्रमचय आव्यूह ऑर्थोगोनल आव्यूह हैं (अर्थात, ), व्युत्क्रम आव्यूह उपस्थित है और इसे इस प्रकार लिखा जा सकता है
इसी प्रकार,
आव्यूह समूह
यदि (1) तत्समक क्रमचय को दर्शाता है, तब P(1) पहचान आव्यूह है।
मान लीजिए कि Sn {1,2,..., पर सममित समूह, या क्रमपरिवर्तन समूह को दर्शाता है।चूँकि n}. क्योंकि वहां हैं n! क्रमचय हैं n! क्रमपरिवर्तन आव्यूह। उपरोक्त सूत्रों के अनुसार, n × n क्रमचय आव्यूह पहचान तत्व के रूप में पहचान आव्यूह के साथ आव्यूह गुणा के तहत एक समूह (गणित) बनाते हैं।
वो नक्शा Sn → GL(n, Z2) जो अपने स्तंभ प्रतिनिधित्व में क्रमचय भेजता है वह एक विश्वसनीय प्रतिनिधित्व है।
दोगुना प्रसंभाव्य आव्यूह
एक क्रमपरिवर्तन आव्यूह अपने आप में एक दोगुना प्रसंभाव्य आव्यूह है, लेकिन यह इन आव्यूह के सिद्धांत में एक विशेष भूमिका भी निभाता है। बिरखॉफ-वॉन न्यूमैन प्रमेय का कहना है कि प्रत्येक दोगुना प्रसंभाव्य वास्तविक आव्यूह एक ही क्रम के क्रमपरिवर्तन मैट्रिसेस का उत्तल संयोजन है और क्रमपरिवर्तन मैट्रिसेस दोगुनी स्टोचैस्टिक आव्यूह के सेट के चरम बिंदु हैं। यही है, बिरखॉफ पॉलीटॉप, डबल प्रसंभाव्य आव्यूह का सेट, क्रमपरिवर्तन आव्यूह के सेट का उत्तल पतवार है।[4]
रैखिक बीजगणितीय गुण
क्रमपरिवर्तन आव्यूह का ट्रेस (रैखिक बीजगणित) क्रमपरिवर्तन के निश्चित बिंदु (गणित) की संख्या है। यदि क्रमपरिवर्तन के निश्चित बिंदु हैं, तो इसे चक्र रूप में लिखा जा सकता है π = (a1)(a2)...(ak)σ जहां σ का कोई निश्चित बिंदु नहीं है ea1,ea2,...,eak क्रमचय आव्यूह के इगनवेक्टर हैं।
एक क्रमचय आव्यूह के इगनवेल्यूज़ की गणना करने के लिए , लिखना चक्रीय क्रमचय के गुणनफल के रूप में, कहते हैं, . माना कि इन चक्रों की संगत लंबाइयाँ हैं , और जाने के जटिल समाधानों का समुच्चय हो . सबका मिलन s संबंधित क्रमचय आव्यूह के इगनवेल्यूज़ का सेट है। प्रत्येक इगनवेल्यूज़ की ज्यामितीय बहुलता की संख्या के बराबर होती है इसमें यह सम्मिलित है।[5]
समूह सिद्धांत से हम जानते हैं कि किसी भी क्रमचय को स्थानान्तरण (गणित) के गुणनफल के रूप में लिखा जा सकता है। इसलिए, कोई भी क्रमपरिवर्तन आव्यूह P पंक्ति-विनिमेय प्राथमिक आव्यूह के गुणनफल के रूप में कारक, प्रत्येक में निर्धारक -1 है। इस प्रकार, एक क्रमपरिवर्तन आव्यूह का निर्धारक P संबंधित क्रमचय के क्रमपरिवर्तन का संकेत है।
उदाहरण
पंक्तियों और स्तंभों का क्रमपरिवर्तन
जब एक आव्यूह M को पीएम बनाने के लिए बाईं ओर एक क्रमचय आव्यूह P से गुणा किया जाता है, तो गुणनफल M की पंक्तियों को क्रमबद्ध करने का परिणाम होता है। विशेष स्थिति के रूप में, यदि M एक स्तंभ वेक्टर है, तो PM की प्रविष्टियों को क्रमपरिवर्तित करने का परिणाम है
इसके के स्थान पर जब M को MP बनाने के अधिकार पर क्रमपरिवर्तन आव्यूह से गुणा किया जाता है, तो गुणनफल M के स्तंभ को अनुमति देने का परिणाम होता है। एक विशेष स्थिति के रूप में, यदि एम एक पंक्ति वेक्टर है, तो एमपी की प्रविष्टियों को अनुमति देने का परिणाम है M:
पंक्तियों का क्रमपरिवर्तन
क्रमपरिवर्तन आव्यूह Pπ क्रमपरिवर्तन के अनुरूप है
सदिश g दिया है,
स्पष्टीकरण
एक क्रमपरिवर्तन आव्यूह हमेशा रूप में रहेगा
जहां eai 'Rj' के लिए iवें आधार वेक्टर (एक पंक्ति के रूप में) का प्रतिनिधित्व करता हैj, और जहां
क्रमपरिवर्तन आव्यूह का क्रमचय रूप है।
अब, आव्यूह गुणन करने में, अनिवार्य रूप से दूसरे के प्रत्येक स्तंभ के साथ पहली आव्यूह की प्रत्येक पंक्ति का डॉट गुणनफल बनता है। इस उदाहरण में, हम इस आव्यूह की प्रत्येक पंक्ति के डॉट गुणनफल को उन तत्वों के वेक्टर के साथ बनाएंगे जिन्हें हम क्रमपरिवर्तित करना चाहते हैं। यानी, उदाहरण के लिए, v = (g0,...,g5)T,
- eai·v = gai
तो, ऊपर दिए गए वेक्टर v के साथ क्रमचय आव्यूह का गुणनफल,(ga1, ga2, ..., gaj) के रूप में एक वेक्टर होगा , और यह तब v का क्रमपरिवर्तन है क्योंकि हमने कहा है कि क्रमचय रूप है
तो, क्रमचय आव्यूह वास्तव में उनके साथ गुणा किए गए वैक्टरों में तत्वों के क्रम को क्रमबद्ध करते हैं।
प्रतिबंधित रूप
- कोस्टास सरणी, एक क्रमचय आव्यूह जिसमें प्रविष्टियों के बीच विस्थापन वैक्टर सभी अलग-अलग होते हैं
- एन-क्वींस पहेली, एक क्रमपरिवर्तन आव्यूह जिसमें प्रत्येक विकर्ण और प्रतिविकर्ण में अधिकतम एक प्रविष्टि होती है
यह भी देखें
संदर्भ
- ↑ Terminology is not standard. Most authors choose one representation to be consistent with other notation they have introduced, so there is generally no need to supply a name.
- ↑ Brualdi (2006) p.2
- ↑ Zavlanos, Michael M.; Pappas, George J. (November 2008). "भारित ग्राफ मिलान के लिए एक गतिशील प्रणाली दृष्टिकोण". Automatica. 44 (11): 2817–2824. doi:10.1016/j.automatica.2008.04.009. S2CID 834305. Retrieved 21 August 2022.
In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices... Lemma 5: Let denote the set of orthogonal matrices and denote the set of element-wise non-negative matrices. Then, , where is the set of permutation matrices.
- ↑ Brualdi (2006) p.19
- ↑ नजनुदेल, ए नीकेघबली 2010 पृष्ठ.4
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
- Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices, arXiv:1005.0402, Bibcode:2010arXiv1005.0402N