Matriu permutació

La matriu permutació és la matriu quadrada en tots les seues n×n elements iguals a 0, llevat un qualsevol per cada fila i columna, el qual deu ser igual a 1. D'acort a esta definició existixen n! matrius de permutació distintes, de les quals una mitat correspon a matrius de permutació parell (en el determinant igual a 1) i l'atra mitat a matrius de permutació impar (en el determinant igual a -1).

Per a n = 3 es té:

Matrius de permutació parell:

$\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right);\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right);\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right).$

Matrius de permutació impar:

$\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right);\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right);\left(\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right).$

Pot notar-se que les matrius de permutació conformen un grup d'orde n! respecte al producte.

Definició

Donat un conjunt A de m elements:

$A=\{1,\dots ,m\}$

i donada un biyección $\pi$ que a cada element a de A li associa un element b de A:

$\begin{array}{cccc}\pi :& A& ⟶& A\\ & a& ⟼& b=\pi (a)\end{array}$

Cada possible biyección $\pi$ de A sobre A és una permutació dels elemntos de A, representada en forma de dos llínees per:

$\left(\begin{array}{cccc}1& 2& \cdots & m\\ \pi (1)& \pi (2)& \cdots & \pi (m)\end{array}\right),$

hi ha dos maneres naturals d'associar la permutació en una matriu de permutació; a és dir, començant en la matriu identitat de m × m, $I_m$, permuta les columnes o permuta les files, segons $\pi$. Abdós métodos per a definir les matrius de permutació apareixen en la lliteratura i les propietats expressades en una representació poden ser fàcilment convertides a l'atra representació. Este artícul tractarà principalment d'una sola d'estes representacions i l'atra només es mencionarà quan hi haja una diferència que calga tindre en conte.

La matriu permutació de m &xD7; m $P_{\pi }$ = (p_ij) que s'obté en permutar les columnes de la matriu identitat $I_m$és dir, per cada i, p_ij = 1 si j = $\pi$(i) i 0 en cas contrari, es referirà a la representació de la columna en este artícul. Ya que les entrades en la fila i són totes 0 excepto que un 1 apareix en la columna $\pi$(i), podem escriure

$P_{\pi }=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (m)}\end{array}\right]$

a on ${𝐞}_j$, un vector de base estàndar, denota un vector de llongitut m en un 1 en la posició j i 0 en qualsevol atra posició.

Per eixemple, la matriu permutació $P_{\pi }$corresponent a la permutació: $\pi =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 4& 2& 5& 3\end{array}\right),$ és:

$P_{\pi }=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ {𝐞}_{\pi (3)}\\ {𝐞}_{\pi (4)}\\ {𝐞}_{\pi (5)}\end{array}\right]=\left[\begin{array}{c}{𝐞}_1\\ {𝐞}_4\\ {𝐞}_2\\ {𝐞}_5\\ {𝐞}_3\end{array}\right]=\left[\begin{array}{ccccc}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{array}\right]$

Observem que la columna j de la matriu identitat $I_5$ara apareix com la columna$\pi (j)$de $P_{\pi }$.

$\left[\begin{array}{ccccc}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{array}\right]\left[\begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\end{array}\right]=\left[\begin{array}{c}1\\ 4\\ 2\\ 5\\ 3\end{array}\right]$

L'atra representació, obtinguda per permutar les files de la matriu identitat $I_m$, és dir, per cada j, p_ij = 1 si i =$\pi (j)$i 0 en cas contrari, es denominarà representació de la fila.

$\left[\begin{array}{ccccc}1& 2& 3& 4& 5\end{array}\right]\left[\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0\end{array}\right]=\left[\begin{array}{ccccc}1& 4& 2& 5& 3\end{array}\right]$

Propietats

La representació de les columnes d'una matriu permutació s'utilisa a lo llarc d'esta secció, llevat que s'indique lo contrari.

Multiplicant $P_{\pi }$voltes un vector columna g permutarà les files del vector:

$P_{\pi }𝐠=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (n)}\end{array}\right]\left[\begin{array}{c}{g}_1\\ g_2\\ ⋮\\ g_n\end{array}\right]=\left[\begin{array}{c}{g}_{\pi (1)}\\ g_{\pi (2)}\\ ⋮\\ g_{\pi (n)}\end{array}\right].$

L'us repetit d'este resultat mostra que si $M$és una matriu de tamany apropiat, el producte, $P_{\pi }$$M$és només una permutació de les files de $M$. No obstant, observant que

$P_{\pi }{𝐞}_k^{𝖳}={𝐞}_{{\pi }^{-1}(k)}^{𝖳}$

per a cada $k$ es mostra que la permutació de les files ve donada per ${\pi }^{-1}$. ($M^T$és la transpuesta de $M$).

Com les matrius de permutació són matrius ortogonals (és dir, $P_{\pi }{P}_{\pi }^{𝖳}=I$), existix la matriu inversa i es pot escriure com

$P_{\pi }^{-1}=P_{{\pi }^{-1}}=P_{\pi }^{𝖳}.$

Multiplicar un vector fila h voltes $P_{\pi }$ permutarà les columnes del vector:

$𝐡P_{\pi }=\left[\begin{array}{c}{h}_1{h}_2\dots h_n\end{array}\right]\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (n)}\end{array}\right]=\left[\begin{array}{c}{h}_{{\pi }^{-1}(1)}{h}_{{\pi }^{-1}(2)}\dots h_{{\pi }^{-1}(n)}\end{array}\right]$

Una volta més, l'aplicació repetida d'este resultat mostra que la post-multiplicació d'una matriu $M$per la matriu permutació $P_{\pi }$o siga, $M$$P_{\pi }$resulta en la permutació de les columnes de $M$. Note's també que

${𝐞}_k{P}_{\pi }={𝐞}_{\pi (k)}.$

Donades dos permutació $\pi$ i σ de m elements, les corresponents matrius de permutació $P_{\pi }$ i$P_{\sigma }$ actuen sobre vectores columna i estan composts per

$P_{\sigma }{P}_{\pi }𝐠=P_{\pi \circ \sigma }𝐠.$

Les mateixes matrius que actuen sobre els vectores fila (és dir, post-multiplicació) es componen segons la mateixa regla

$𝐡P_{\sigma }{P}_{\pi }=𝐡P_{\pi \circ \sigma }.$

Per a ser clars, les fòrmules anteriors utilisen la notació polaca per a la composició de permutació, és dir,

$\pi \circ \sigma (k)=\pi (\sigma (k)).$

Deixem que $Q_{\pi }$siga la matriu permutació corresponent a $\pi$en la seua representació en files. Les propietats d'esta representació es poden determinar a partir de les de la representació de la columna, ya que $Q_{\pi }=P_{\pi }^{𝖳}=P_{{\pi }^{-1}}.$ En particular,

$Q_{\pi }{𝐞}_k^{𝖳}=P_{{\pi }^{-1}}{𝐞}_k^{𝖳}={𝐞}_{({\pi }^{-1}{)}^{-1}(k)}^{𝖳}={𝐞}_{\pi (k)}^{𝖳}.$

D'això es deduïx que

$Q_{\sigma }{Q}_{\pi }𝐠=Q_{\sigma \circ \pi }𝐠.$

De la mateixa manera,

$𝐡Q_{\sigma }{Q}_{\pi }=𝐡Q_{\sigma \circ \pi }.$

Atres propietats:

l'element neutre del grup és la matriu identitat.

• l'element invers de cada element del grup de matrius de permutació és la matriu trasponer corresponent.
• Cada element del grup de matrius de permutació és una matriu ortogonal.
• El producte de matrius de permutació parell sempre genera una matriu de permutació parell.
• El producte de matrius de permutació impar sempre genera una matriu de permutació parell.
• El producte de matrius de permutació de paritat distinta sempre genera una matriu de permutació impar.
• Observe que les matrius de permutació parell conformen un semigrupo i que ademés el grup de matrius de permutació no és conmutativo.
• Cada element del grup de matrius de permutació fòra del semigrupo és una matriu simètrica.

Vore també

• Matriu
• Permutació