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

गणित में, विशेष रूप से आव्यूह (गणित) सिद्धांत में, क्रमपरिवर्तन आव्यूह एक वर्ग बाइनरी आव्यूह होता है जिसमें प्रत्येक पंक्ति और प्रत्येक स्तंभ में 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 अन्यथा, इस आलेख में स्तंभ प्रतिनिधित्व के रूप में संदर्भित किया जाएगा। चूंकि पंक्ति i में सभी प्रविष्टियां 0 हैं, इसके अतिरिक्त कि स्तंभ π(i) में 1 दिखाई देता है हम लिख सकते हैं

$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 है।  

उदाहरण के लिए, क्रमपरिवर्तन मैट्रिक्स 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₅ पहचान आव्यूह का jवां स्तंभ अब P_π.के π(j)वें स्तंभ के रूप में प्रकट होता है।

पहचान आव्यूह 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}}$$

पुनः, इस परिणाम के बार-बार आवेदन से पता चलता है कि क्रमपरिवर्तन आव्यूह P_π, यानी, M P_π, द्वारा आव्यूह M को गुणा करना के बाद 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 क्रमचय आव्यूह के इगनवेक्टर हैं।

एक क्रमचय आव्यूह के इगनवेल्यूज़ ​​​​की गणना करने के लिए $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 संबंधित क्रमचय आव्यूह के इगनवेल्यूज़ ​​​​का सेट है। प्रत्येक इगनवेल्यूज़ की ज्यामितीय बहुलता की संख्या के बराबर होती है $R_{i}$इसमें यह सम्मिलित है।

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

उदाहरण

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

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

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

इसके के स्थान पर जब M को MP बनाने के अधिकार पर क्रमपरिवर्तन आव्यूह से गुणा किया जाता है, तो गुणनफल M के स्तंभ को अनुमति देने का परिणाम होता है। एक विशेष स्थिति के रूप में, यदि एम एक पंक्ति वेक्टर है, तो एमपी की प्रविष्टियों को अनुमति देने का परिणाम है M:

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

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

क्रमपरिवर्तन आव्यूह 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}}.$

सदिश 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}}$

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

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

क्रमपरिवर्तन आव्यूह का क्रमचय रूप है।

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

e_ai·v = g_ai

तो, ऊपर दिए गए वेक्टर v के साथ क्रमचय आव्यूह का गुणनफल,(g_a1, g_a2, ..., g_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