क्रमपरिवर्तन आव्यूह

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

परिभाषा

एक क्रमपरिवर्तन दिया {{pi}एम तत्वों की,

$\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 अन्यथा, इस आलेख में कॉलम प्रतिनिधित्व के रूप में संदर्भित किया जाएगा। चूंकि पंक्ति में प्रविष्टियां सभी 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 के एक पंक्ति सदिश को दर्शाता है जिसमें 1 j स्थान पर और 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}}.$

ध्यान दें कि का jवाँ स्तंभ I₅ आइडेंटिटी मैट्रिक्स अब इस रूप में दिखाई देता है π(जे)पी का वां स्तंभ_π.

पहचान मैट्रिक्स की पंक्तियों को अनुमति देकर प्राप्त अन्य प्रतिनिधित्व I_m, यानी प्रत्येक j के लिए, p_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 दिखाता है कि पंक्तियों का क्रमपरिवर्तन किसके द्वारा दिया गया है π^-1. ($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 संबंधित क्रमचय के क्रमपरिवर्तन का हस्ताक्षर है।

उदाहरण

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

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

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' के लिए iवें आधार वेक्टर (एक पंक्ति के रूप में) का प्रतिनिधित्व करता है^j, और कहाँ

${\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