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

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

परिभाषा

m तत्वों के क्रमपरिवर्तन π को देखते हुए,

$\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, के अनुसार या तो स्तंभों को क्रमबद्ध करें या पंक्तियों को क्रमबद्ध करें π. क्रमचय आव्यूहों को परिभाषित करने की दोनों विधियाँ साहित्य में दिखाई देती हैं और एक निरूपण में अभिव्यक्त गुणों को आसानी से दूसरे निरूपण में परिवर्तित किया जा सकता है। यह लेख मुख्य रूप से इनमें से केवल एक अभ्यावेदन से निपटेगा और दूसरे का उल्लेख केवल तभी किया जाएगा जब जागरूक होने के लिए कोई अंतर हो।

m × m क्रमपरिवर्तन आव्यूह P_π = (p_ij) पहचान आव्यूह के स्तंभों को अनुमति देकर प्राप्त किया गया I_m, यानी प्रत्येक i के लिए, p_ij = 1 if j = π(i) और 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 प्रत्येक अन्य स्थिति में है। उदाहरण के लिए, क्रमपरिवर्तन आव्यूह P_π क्रमपरिवर्तन के अनुरूप $\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}}.$

ध्यान दें कि I₅ पहचान आव्यूह का jth स्तंभ अब P_π.के π(j)th स्तंभ के रूप में प्रकट होता है।

पहचान आव्यूह I_m, की पंक्तियों को अनुमति देकर प्राप्त अन्य प्रतिनिधित्वयानी प्रत्येक j के लिए, p_ij = 1 अगर I_m = π( j,) और 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