வரிசைமாற்ற அணி

கணிதத்தில் வரிசைமாற்ற அணி (permutation matrix) என்பது ஒவ்வொரு நிரை மற்றும் நிரலிலும் ஒரேயொரு உறுப்பு 1 ஆகவும் ஏனைய உறுப்புகள் எல்லாம் 0 ஆகவும் கொண்ட சதுர இரும அணியாகும் (binary matrix). இத்தகைய அணி (P) ஒவ்வொன்றும் m உறுப்புகளின் வரிசைமாற்றத்தைக் குறிக்கும். மேலும் மற்றொரு அணி A உடன் பெருக்கப்படும்போது முன்பெருக்கத்தில் (PA), A அணியின் நிரைகளின் வரிசைமாற்றமாகவும் பின்பெருக்கத்தில் (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 இன் நிரல்களை π இன் படி வரிசைமாற்றம் செய்யலாம் அல்லது நிரைகளை π இன் படி வரிசைமாற்றம் செய்யலாம்.

I_m இன் நிரல்களை வரிசைமாற்றம் செய்யக்கிடைக்கும் வரிசைமாற்ற அணி ஒரு m × m அணியாக இருக்கும். இந்த அணியின் குறியீடு P_π = (p_ij) எனில்:

ஒவ்வொரு i க்கும், j = π(i) எனில் p_ij = 1 ஆகவும், அவ்வாறு இல்லாவிட்டால் p_ij = 0 ஆகவும் இருக்கும்.

அதாவது i ஆவது நிரையில் π(i) நிரலில் உள்ள உறுப்பு மட்டும் 1 ஆகவும் மீதமுள்ள உறுப்புகள் எல்லாம் 0 ஆகவும் இருக்கும்.

எனவே வரிசைமாற்ற அணி P_π கீழுள்ளவாறு அமைகிறது:

$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}}.$

முற்றொருமை அணி I₅ இன் j ஆவது நிரலானது P_π அணியின் π(j) ஆவது நிரலாக அமைவதைக் காணலாம்.

பண்புகள்

(கட்டுரையின் இப்பிரிவு முழுவதும் வரிசைமாற்ற அணியின் நிரல் உருவகிப்புப் பயன்படுத்தப்படுகிறது. சில இடங்களில் நிரை உருவகிப்பு பயன்படுத்தப்படும்போது அது குறிப்பிடப்படும்)

• $P_{\pi }$ ஆல் நிரல் திசையன் g ஐப் முன்பெருக்கும்போது கிடைக்கும் அத்திசையனின் நிரைகளின் வரிசைமாற்றம்:

$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 இன் நிரைகளின் வரிசைமாற்றமாக அமைவதைக் காணலாம்.

எனினும் ஒவ்வொரு k க்கும்,

$P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T}}$ என்பதால் நிரைகளின் வரிமாற்றம் π⁻¹ ஆகும். (M அணியின் இடமாற்று அணி $M^{\mathsf {T}}$)

• வரிசைமாற்ற அணிகளெல்லாம் செங்குத்து அணிகள் (i.e., $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}\;\dots \;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)}\;\dots \;h_{\pi ^{-1}(n)}\end{bmatrix}}$

மேலுள்ள முடிவினை மீண்டும் மீண்டும் பயன்படுத்துவதன்மூலம் M அணியை வரிசைமாற்ற அணியான P_π ஆல் பின்பெருக்கம் செய்தால் M P_π ஆனது M இன் நிரல்களின் வரிசைமாற்றமாக அமைவதை காணலாம். மேலும்,

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

• m உறுப்புகளின் இரு வரிசைமாற்றங்கள் π, σ எனில் நிரல் திசையன் g மீது செயற்படும் அவற்றின் வரிசைமாற்ற அணிகள் P_π, P_σ இரண்டின் தொகுப்பு:

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

• m உறுப்புகளின் இரு வரிசைமாற்றங்கள் π, σ எனில் நிரை திசையன் h மீது செயற்படும் அவற்றின் வரிசைமாற்ற அணிகள் P_π, P_σ இரண்டின் தொகுப்பு:

$\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₍₁₎ ஆனது முற்றொருமை அணியாகும்.

{1,2,...,n} மீதான சமச்சீர் குலம் அல்லது வரிசைமாற்றுக் குலம் என்க. மொத்தம் n! வரிசைமாற்றங்கள் இருப்பதால், n! வரிசைமாற்ற அணிகள் இருக்கும். இந்த n × n வரிசைமாற்ற அணிகள், அணிப்பெருக்கலின் கீழ் முற்றொருமை அணியை முற்றொருமை உறுப்பாகக் கொண்ட குலமாக அமையும்.

மேற்கோள்கள்

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: கேம்பிறிட்ஜ் பல்கலைக்கழகப் பதிப்பகம். பன்னாட்டுத் தரப்புத்தக எண் 0-521-86565-4. Zbl 1106.05001.
• Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices (PDF)