Permutacijska matrika

Permutacijska matrika (oznaka ) je kvadratna matrika, ki ima v vsaki vrstici samo en element enak 1, na ostalih mestih pa ima ničle. Prav tako ima tudi v vsakem stolpcu samo po en element enak 1, ostali pa so 0. Vsaka takšna matrika predstavlja določeno permutacijo elementov. Vsaka permutacija ima svojo permutacijsko matriko. Če permutacijsko matriko pomnožimo z drugo matriko, dobimo permutacije v vrsticah v drugi matriki. Permutacijska matrika je nesigularna, kar pomeni, da njena determinanta ni nikoli enaka 0 (vedno je +1 ali -1).

Matrike, ki opisujejo permutacije 3 elementov. Skupaj 6 (1.2.3 = 3!) permutacij (v vsaki vrstici).
V vsakem kvadratu je ena izmed permutacij treh elementov.

Permutacijska matrika se vedno dobi s permutacijami enotske matrike. Vsaka enotska matrika je tudi permutacijska matrika.

Definicija

uredi

Permutacijo   elementov označimo s  

 

To lahko enakovredno zapišemo v posebni obliki, ki jo imenujemo ciklično označevanje permutacij

 

kjer je

  • v prvi vrstici so napisani vsi elementi, ki jih permutiramo
  • v drugi vrstici so zapisane posamezne vrednosti permutiranih elementov
  pomeni permutirani element na prvem mestu
itd.

Permutacijska matrika   z razsežnostjo   ima povsod 0, razen v vrstici  , kjer ima vrednost 1. To lahko zapišemo kot

 

kjer je

  •   enotski vrstični vektor z dolžino  , ki ima enico na  -tem mestu, na vseh ostalih mestih pa ima  .

Zgled

uredi

Ena izmed permutacij štirih elementov je :

 

Pripadajoča matrika pa je:

 .

Permutacijski matriki   (dva elementa, ki permutirata) sta   in  

Primer permutacijske matrike   (štirje elementi, ki permutirajo):  

Značilnosti

uredi
  • za dve permutaciji   in   velja  
kjer je
  kompozitum permutacij   in  
  • permutacijske matrike so ortogonalne, zanje velja : 
  • permutacijska matrika spada med stohastične matrike
  • množenje permutacijske matrike   s poljubno matriko   povzroči permutacijo vrstic v matriki   (to je  )
  • množenje poljubne matrike   s permutacijsko matriko   ima za posledico permutacijo stolpcev v matriki   (to je  )
  • obratna vrednost permutacijske matrike je enaka njeni transponirani   ali   (  je enotska matrika)

Posplošitev permutacijske matrike

uredi

Vsota elementov v vsaki vrstici permutacijske matrike je 1. To lahko posplošimo tako, da dovolimo v vsaki vrstici poljubno vsoto. Takšne matrike so vsote permutacijskih matrik.

Primer: Naslednja matrika ima v vsaki vrstici vsoto elementov enako 5

 .

Glej tudi

uredi

Zunanje povezave

uredi
  • Weisstein, Eric Wolfgang. »Permutation Matrix«. MathWorld.
  • Značilnosti permutacijske matrike[mrtva povezava] (angleško)