क्रमपरिवर्तन मैट्रिक्स

गणित में, विशेष रूप से मैट्रिक्स (गणित) में, क्रमपरिवर्तन मैट्रिक्स एक वर्ग बाइनरी मैट्रिक्स है जिसमें प्रत्येक पंक्ति और प्रत्येक कॉलम में 1 की बिल्कुल एक प्रविष्टि होती है और अन्यत्र 0 होता है। ऐसा प्रत्येक मैट्रिक्स, मान लीजिए P, के क्रमपरिवर्तन का प्रतिनिधित्व करता है m तत्व और, जब किसी अन्य मैट्रिक्स को गुणा करने के लिए उपयोग किया जाता है, तो कहते हैं A, परिणामस्वरूप पंक्तियों को क्रमपरिवर्तित किया जाता है (जब पूर्व-गुणा किया जाता है, तो बनाने के लिए PA) या कॉलम (जब बाद में गुणा किया जाता है, बनाने के लिए AP) मैट्रिक्स का A.

परिभाषा

एक क्रमपरिवर्तन दिया गया π एम तत्वों का,

$\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace$

द्वारा दो-पंक्ति रूप में दर्शाया गया है

${\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},$

क्रमपरिवर्तन को क्रमपरिवर्तन मैट्रिक्स के साथ जोड़ने के दो प्राकृतिक तरीके हैं; अर्थात्, m × m पहचान मैट्रिक्स से प्रारंभ करते हुए, I_m, या तो स्तंभों को क्रमबद्ध करें या पंक्तियों को क्रमबद्ध करें π. क्रमपरिवर्तन मैट्रिक्स को परिभाषित करने के दोनों तरीके साहित्य में दिखाई देते हैं और एक प्रतिनिधित्व में व्यक्त गुणों को आसानी से दूसरे प्रतिनिधित्व में परिवर्तित किया जा सकता है। यह आलेख मुख्य रूप से इनमें से केवल एक प्रतिनिधित्व से निपटेगा और दूसरे का उल्लेख केवल तभी किया जाएगा जब जागरूक होने के लिए कोई अंतर हो।

एम × एम क्रमपरिवर्तन मैट्रिक्स पी_π = (पी_ij) पहचान मैट्रिक्स के स्तंभों को क्रमपरिवर्तित करके प्राप्त किया गया I_m, अर्थात, प्रत्येक i के लिए, p_ij = 1 यदि जे = π(मे एंड p_ij = 0 अन्यथा, इस आलेख में स्तंभ प्रतिनिधित्व के रूप में संदर्भित किया जाएगा। चूँकि पंक्ति i में सभी प्रविष्टियाँ 0 हैं, सिवाय इसके कि कॉलम में 1 दिखाई देता है π(i), हम लिख सकते हैं

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}},$

कहाँ $\mathbf {e} _{j}$, एक मानक आधार वेक्टर, m लंबाई के एक पंक्ति वेक्टर को दर्शाता है जिसमें jवीं स्थिति में 1 और प्रत्येक अन्य स्थिति में 0 है। उदाहरण के लिए, क्रमपरिवर्तन मैट्रिक्स पी_π क्रमपरिवर्तन के अनुरूप $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}$ है

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

ध्यान दें कि jth कॉलम I₅ पहचान मैट्रिक्स अब के रूप में प्रकट होता है π(जे) पी का वां कॉलम_π.

अन्य प्रतिनिधित्व, पहचान मैट्रिक्स की पंक्तियों को क्रमपरिवर्तित करके प्राप्त किया गया I_m, अर्थात, प्रत्येक जे, पी के लिए_ij = 1 यदि मैं = π(जे) और p_ij = 0 अन्यथा, पंक्ति प्रतिनिधित्व के रूप में संदर्भित किया जाएगा।

गुण

क्रमपरिवर्तन मैट्रिक्स का स्तंभ प्रतिनिधित्व इस पूरे अनुभाग में उपयोग किया जाता है, सिवाय इसके कि जब अन्यथा संकेत दिया गया हो।

गुणा $P_{\pi }$ कई बार एक स्तंभ सदिश जी वेक्टर की पंक्तियों को क्रमबद्ध करेगा:

$$P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.$$

इस परिणाम के बार-बार उपयोग से पता चलता है कि यदि M एक उचित आकार का मैट्रिक्स है, उत्पाद, $P_{\pi }M$ की पंक्तियों का क्रमपरिवर्तन मात्र है M. हालाँकि, उस पर गौर कर रहा हूँ

$$P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T}}$$

प्रत्येक के लिए k दर्शाता है कि पंक्तियों का क्रमपरिवर्तन किसके द्वारा दिया गया है π⁻¹. ($M^{\mathsf {T}}$ मैट्रिक्स का मैट्रिक्स स्थानांतरित करें है M.)

चूंकि क्रमपरिवर्तन मैट्रिक्स ऑर्थोगोनल मैट्रिक्स हैं (अर्थात्, $P_{\pi }P_{\pi }^{\mathsf {T}}=I$), व्युत्क्रम मैट्रिक्स मौजूद है और इसे इस प्रकार लिखा जा सकता है

$$P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}.$$

एक पंक्ति वेक्टर को h बार गुणा करना $P_{\pi }$ वेक्टर के स्तंभों को क्रमबद्ध करेगा:

$$\mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}&h_{2}&\cdots &h_{n}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}={\begin{bmatrix}h_{\pi ^{-1}(1)}&h_{\pi ^{-1}(2)}&\cdots &h_{\pi ^{-1}(n)}\end{bmatrix}}$$

फिर से, इस परिणाम को बार-बार लागू करने से पता चलता है कि मैट्रिक्स को गुणा करने के बाद M क्रमपरिवर्तन मैट्रिक्स द्वारा P_π, वह है, M P_π, के स्तंभों को क्रमपरिवर्तित करने का परिणाम है M. उस पर भी गौर करें

$$\mathbf {e} _{k}P_{\pi }=\mathbf {e} _{\pi (k)}.$$

दो क्रमपरिवर्तन दिए गए π और σ का mतत्व, संगत क्रमपरिवर्तन मैट्रिक्स P_π और P_σ स्तंभ सदिशों पर अभिनय से बना है

$$P_{\sigma }P_{\pi }\,\mathbf {g} =P_{\pi \,\circ \,\sigma }\,\mathbf {g} .$$

पंक्ति सदिशों (अर्थात, गुणन के बाद) पर कार्य करने वाले समान आव्यूह एक ही नियम के अनुसार बनते हैं

$$\mathbf {h} P_{\sigma }P_{\pi }=\mathbf {h} P_{\pi \,\circ \,\sigma }.$$

स्पष्ट होने के लिए, उपरोक्त सूत्र क्रमपरिवर्तन संरचना के लिए उपसर्ग संकेतन का उपयोग करते हैं, अर्थात,

$$(\pi \,\circ \,\sigma )(k)=\pi \left(\sigma (k)\right).$$

होने देना $Q_{\pi }$ के अनुरूप क्रमपरिवर्तन मैट्रिक्स बनें π इसके पंक्ति प्रतिनिधित्व में। इस प्रतिनिधित्व के गुणों को स्तंभ प्रतिनिधित्व के गुणों से निर्धारित किया जा सकता है $Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.$ विशेष रूप से,

$$Q_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=P_{{\pi }^{-1}}\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{(\pi ^{-1})^{-1}(k)}^{\mathsf {T}}=\mathbf {e} _{\pi (k)}^{\mathsf {T}}.$$

इससे यह निष्कर्ष निकलता है

$$Q_{\sigma }Q_{\pi }\,\mathbf {g} =Q_{\sigma \,\circ \,\pi }\,\mathbf {g} .$$

इसी प्रकार,

$$\mathbf {h} \,Q_{\sigma }Q_{\pi }=\mathbf {h} \,Q_{\sigma \,\circ \,\pi }.$$

क्रमपरिवर्तन मैट्रिक्स ऑर्थोगोनल मैट्रिक्स के रूप में लक्षण वर्णन (गणित) हो सकते हैं जिनकी प्रविष्टियाँ सभी गैर-नकारात्मक हैं।

मैट्रिक्स समूह

यदि (1) पहचान क्रमचय को दर्शाता है, तो P₍₁₎ पहचान मैट्रिक्स है.

होने देना S_n {1,2,..., पर सममित समूह, या क्रमपरिवर्तन समूह को निरूपित करेंn}. क्योंकि वहां हैं n! क्रमपरिवर्तन, हैं n! क्रमपरिवर्तन मैट्रिक्स। उपरोक्त सूत्रों के अनुसार, n × n क्रमचय मैट्रिक्स पहचान तत्व के रूप में पहचान मैट्रिक्स के साथ मैट्रिक्स गुणन के तहत एक समूह (गणित) बनाते हैं।

वो नक्शा S_n → GL(n, Z₂) जो अपने कॉलम प्रतिनिधित्व में क्रमपरिवर्तन भेजता है वह एक वफादार प्रतिनिधित्व है।

दोगुना स्टोकेस्टिक मैट्रिक्स

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

रैखिक बीजगणितीय गुण

क्रमपरिवर्तन मैट्रिक्स का ट्रेस (रैखिक बीजगणित) क्रमपरिवर्तन के निश्चित बिंदु (गणित) की संख्या है। यदि क्रमपरिवर्तन में निश्चित बिंदु हैं, तो इसे चक्र के रूप में लिखा जा सकता है π = (a₁)(a₂)...(a_k)σ कहाँ σ का कोई निश्चित बिंदु नहीं है e_a1,e_a2,...,e_ak क्रमपरिवर्तन मैट्रिक्स के eigenvectors हैं।

क्रमपरिवर्तन मैट्रिक्स के eigenvalues ​​​​की गणना करने के लिए $P_{\sigma }$, लिखना $\sigma$ चक्रीय क्रमपरिवर्तन के उत्पाद के रूप में, मान लीजिए, $\sigma =C_{1}C_{2}\cdots C_{t}$. मान लीजिए कि इन चक्रों की संगत लंबाई है $l_{1},l_{2}...l_{t}$, और जाने $R_{i}(1\leq i\leq t)$ के जटिल समाधानों का समुच्चय बनें $x^{l_{i}}=1$. सबका मिलन $R_{i}$s संबंधित क्रमपरिवर्तन मैट्रिक्स के eigenvalues ​​​​का सेट है। प्रत्येक eigenvalue की ज्यामितीय बहुलता की संख्या के बराबर होती है $R_{i}$वह है जिसमें यह शामिल है।

समूह सिद्धांत से हम जानते हैं कि किसी भी क्रमपरिवर्तन को ट्रांसपोज़िशन (गणित) के उत्पाद के रूप में लिखा जा सकता है। इसलिए, कोई भी क्रमपरिवर्तन मैट्रिक्स P पंक्ति-इंटरचेंजिंग प्राथमिक मैट्रिक्स के उत्पाद के रूप में कारक, प्रत्येक में निर्धारक -1 होता है। इस प्रकार, क्रमपरिवर्तन मैट्रिक्स का निर्धारक P संगत क्रमपरिवर्तन के क्रमपरिवर्तन का हस्ताक्षर है।

उदाहरण

पंक्तियों और स्तंभों का क्रमपरिवर्तन

जब पीएम बनाने के लिए मैट्रिक्स एम को बायीं ओर क्रमपरिवर्तन मैट्रिक्स पी से गुणा किया जाता है, तो उत्पाद एम की पंक्तियों को क्रमपरिवर्तित करने का परिणाम होता है। एक विशेष मामले के रूप में, यदि एम एक कॉलम वेक्टर है, तो पीएम क्रमपरिवर्तन का परिणाम है एम की प्रविष्टियाँ:

P · (1, 2, 3, 4)T = (4, 1, 3, 2)T

जब इसके बजाय एम को एमपी बनाने के लिए दाईं ओर क्रमपरिवर्तन मैट्रिक्स से गुणा किया जाता है, तो उत्पाद एम के कॉलम को क्रमपरिवर्तित करने का परिणाम होता है। एक विशेष मामले के रूप में, यदि एम एक पंक्ति वेक्टर है, तो एमपी प्रविष्टियों को क्रमपरिवर्तित करने का परिणाम है एम:

(1, 2, 3, 4) · P = (2, 4, 3, 1)

पंक्तियों का क्रमपरिवर्तन

क्रमपरिवर्तन मैट्रिक्स पी_π क्रमपरिवर्तन के अनुरूप $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}$ है

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

एक सदिश g दिया गया है,

$P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.$

स्पष्टीकरण

एक क्रमपरिवर्तन मैट्रिक्स हमेशा फॉर्म में रहेगा

${\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{j}}\\\end{bmatrix}}$

कहां ई_ai 'R' के लिए ith आधार वेक्टर (एक पंक्ति के रूप में) का प्रतिनिधित्व करता है^ज, और कहाँ

${\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}$

क्रमपरिवर्तन मैट्रिक्स का क्रमपरिवर्तन रूप है।

अब, मैट्रिक्स गुणन करने में, अनिवार्य रूप से दूसरे के प्रत्येक कॉलम के साथ पहले मैट्रिक्स की प्रत्येक पंक्ति का डॉट उत्पाद बनता है। इस उदाहरण में, हम इस मैट्रिक्स की प्रत्येक पंक्ति का डॉट उत्पाद उन तत्वों के वेक्टर के साथ बनाएंगे जिन्हें हम क्रमपरिवर्तित करना चाहते हैं। यानी, उदाहरण के लिए, v=(g₀,...,जी₅)^टी,

इ_ai·में = उह_ai</उप>

तो, उपरोक्त वेक्टर v के साथ क्रमपरिवर्तन मैट्रिक्स का उत्पाद, (g) के रूप में एक वेक्टर होगा उप>ए₁</उप>, जी_{a2</उप>, ..., जीaj), और यह कि यह v का क्रमपरिवर्तन है क्योंकि हमने कहा है कि क्रमपरिवर्तन रूप है}

${\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.$

तो, क्रमपरिवर्तन मैट्रिक्स वास्तव में उनके साथ गुणा किए गए वैक्टर में तत्वों के क्रम को क्रमबद्ध करते हैं।

प्रतिबंधित प्रपत्र

• कोस्टास सरणी, एक क्रमपरिवर्तन मैट्रिक्स जिसमें प्रविष्टियों के बीच विस्थापन वैक्टर सभी अलग-अलग होते हैं
• आठ रानियों की पहेली|एन-क्वींस पहेली, एक क्रमपरिवर्तन मैट्रिक्स जिसमें प्रत्येक विकर्ण और प्रतिविकर्ण में अधिकतम एक प्रविष्टि होती है

यह भी देखें

• वैकल्पिक साइन मैट्रिक्स
• विनिमय मैट्रिक्स
• सामान्यीकृत क्रमपरिवर्तन मैट्रिक्स
• रूक बहुपद
• स्थायी (गणित)

संदर्भ

• 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