Permütasyon matrisi - Permutation matrix

Gelen matematik , özellikle de matris teori , bir permütasyon matrisi bir kare ikili matris başka tam olarak bir, her satırda 1 giriş ve her bir sütun ve tane 0 sahiptir. Bu tür her bir matris, ki P , bir temsil permütasyon ait m elemanları ve bir matris çarpmak için kullanıldığında, ki A , satır permutasyonu sonuçlanır (pre-çarpılmasıyla oluşturmak üzere PA ) veya sütun (zaman sonrası çarpılmasıyla forma AP ) matrisinin A .

Tanım

Bir permütasyon verilen π ait m elemanlarının

${\displaystyle \pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace }$

tarafından iki satır şeklinde temsil edilir

${\displaystyle {\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},}$

permütasyonu bir permütasyon matrisi ile ilişkilendirmenin iki doğal yolu vardır; yani başlayarak m x m kimlik matrisi , bir _m göre, sütunlar permute veya satırları permute ya tt . Her iki permütasyon matrisi tanımlama yöntemi de literatürde yer almaktadır ve bir temsilde ifade edilen özellikler kolaylıkla diğer gösterime dönüştürülebilir. Bu yazıda öncelikle bu temsillerden sadece biri ele alınacak, diğeri ise ancak dikkat edilmesi gereken bir fark olduğunda bahsedilecektir.

Mx m permütasyon matris p _π = ( p _ij birim matris sütunları permutasyonu ile elde edilen) bir _m her biri için, bir, i , s _ij = 1 ise j = π ( i ) ve p _ij = 0 , aksi halde, bu makalede sütun gösterimi olarak anılacaktır . i satırındaki girişlerin tümü 0 olduğundan, π ( i ) sütununda 1'in görünmesi dışında , şunu yazabiliriz:

${\displaystyle P_{\pi }={\başlangıç{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\ matematik {e} _{\pi (m)}\end{bmatrix}},}$

burada , bir standart baz vektörü , uzunluk bir sıra vektörü temsil eder m de 1 ile j her pozisyonda inci pozisyon ve 0. ${\displaystyle \mathbf {e} _{j}}$

Örneğin, permütasyon matris p _tt permütasyon tekabül eden bir ${\displaystyle \pi ={\başlangıç{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}$

${\displaystyle P_{\pi }={\başlangıç{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&1\\0&0&1&0&0\end{bmatrix}}.}$

Gözlemleyin j inci kolon I ₅ kimlik matris artık görünür π ( j ) th sütun p _tt .

Birim matris sıraları permutasyonu ile elde edilen diğer bir temsilidir, I _m her biri için, bir, j , p _ij = 1 i = π ( j ) ve p _ij = 0 , aksi halde, şu şekilde ifade edilecektir satır gösterimi .

Özellikler

Bir permütasyon matrisinin sütun gösterimi, aksi belirtilmedikçe, bu bölüm boyunca kullanılır.

Çarparak kez kolon vektörü g vektörünün satır permute olacaktır: ${\görüntüleme stili P_{\pi }}$

${\displaystyle P_{\pi }\mathbf {g} ={\başlangıç{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}\ bitiş{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}} .}$

Bu sonucun tekrar tekrar kullanılması, M uygun büyüklükte bir matris ise, çarpımının sadece M satırlarının bir permütasyonu olduğunu gösterir . Ancak bunu gözlemleyerek ${\görüntüleme stili P_{\pi }M}$

${\displaystyle P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T }}}$

her k için satırların permütasyonunun π ^-1 ile verildiğini gösterir . ( Olup devrik matris M ). ${\displaystyle M^{\mathsf {T}}}$

Permütasyon matrisleri ortogonal matrisler olduğundan (yani, ), ters matris mevcuttur ve şu şekilde yazılabilir: ${\displaystyle P_{\pi }P_{\pi }^{\mathsf {T}}=I}$

${\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}.}$

Bir çarpımı satır vektörü h sürelerini vektör sütunları permute olacaktır: ${\görüntüleme stili P_{\pi }}$

${\displaystyle \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)}\ bitiş {bmatris}}}$

Yine, bu sonucun tekrar tekrar uygulanması, bir M matrisinin P _π permütasyon matrisi , yani MP _{π ile} sonradan çarpılmasının , M'nin sütunlarına izin verilmesiyle sonuçlandığını göstermektedir . Şuna da dikkat edin

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

İki permütasyon verilen TT ve σ ait m elemanları, karşılık gelen bir permütasyon matrisler p _π ve P _σ sütun vektörleri ile etkili birleşiminden oluşur

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

Satır vektörlerine etki eden aynı matrisler (yani çarpma sonrası) aynı kurala göre oluşur

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

Açık olmak gerekirse, yukarıdaki formüller permütasyon bileşimi için önek gösterimini kullanır , yani,

${\displaystyle (\pi \,\circ \,\sigma )(k)=\pi \left(\sigma (k)\sağ).}$

Satır gösteriminde π'ye karşılık gelen permütasyon matrisi olsun . Bu gösterimin özellikleri, sütun gösteriminin özelliklerinden belirlenebilir, çünkü Özellikle, ${\ Displaystyle Q_{\pi }}$${\displaystyle Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.}$

${\displaystyle 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}}.}$

Bundan şu sonuç çıkar

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

Benzer şekilde,

${\displaystyle \mathbf {h} \,Q_{\sigma }Q_{\pi }=\mathbf {h} \,Q_{\sigma \,\circ \,\pi }.}$

matris grubu

(1) kimlik permütasyon belirtirse, o zaman P ₍₁₎ olan birim matris .

Let S _{, n} ifade simetrik grubu veya permütasyon grubu ile, {1,2, ..., n }. n olduğundan beri ! permütasyonlar, n ! permütasyon matrisleri. Yukarıdaki formüllere göre, n × n permütasyon matrisleri , kimlik elemanı olarak kimlik matrisi ile matris çarpımı altında bir grup oluşturur .

S _n → A ⊂ GL( n , Z ₂ ) haritası aslına uygun bir temsildir . Böylece, | bir | = n ! .

Çifte stokastik matrisler

Bir permütasyon matrisinin kendisi çift ​​stokastik bir matristir , ancak aynı zamanda bu matrislerin teorisinde özel bir rol oynar. Birkhoff-Von Neumann teoremi her iki kat stokastik gerçek matris olduğunu söyler konveks bir kombinasyonu aynı düzenin permütasyon matrisler ve permütasyon matrisler tam olarak en uç noktaları iki kat stokastik matrislerin kümesinin. Yani, çifte stokastik matrisler kümesi olan Birkhoff politopu , permütasyon matrisleri kümesinin dışbükey kabuğudur.

Doğrusal cebirsel özellikler

İz bir permütasyon matris sayısı sabit nokta permütasyon. Eğer permütasyon sabit noktalara sahipse, döngü formunda π = ( a ₁ )( a ₂ )...( a _k )σ şeklinde yazılabilir, burada σ sabit noktaları yoktur, o zaman e _{a 1} , e _{a 2} , ..., e _{bir k} olan özvektörler permütasyon matrisi.

Hesaplamak için öz bir permütasyon matrisi , yazma bir ürünü olarak döngü , demek . Bu döngülerin karşılık gelen uzunlukları ve karmaşık çözümlerinin kümesi olsun . Tüm s'lerin birleşimi , karşılık gelen permütasyon matrisinin özdeğerleri kümesidir. Geometrik çokluğu , her özdeğerinin sayısına eşittir bunu ihtiva s. ${\ Displaystyle P_{\sigma }}$${\görüntüleme stili \sigma }$${\displaystyle \sigma =C_{1}C_{2}\cdots C_{t}}$${\displaystyle l_{1},l_{2}...l_{t}}$${\displaystyle R_{i}(1\leq i\leq t)}$${\displaystyle x^{l_{i}}=1}$${\görüntüleme stili R_{i}}$${\görüntüleme stili R_{i}}$

Gönderen grup teorisi herhangi permütasyon ürünü olarak yazılı alınabileceğini transpozisyonlar . Bu nedenle, herhangi bir permütasyon matrisi P faktörleri , her biri -1 determinantına sahip olan satır değiş tokuş eden temel matrislerin bir ürünü olarak . Bu nedenle, bir permütasyon matris belirleyici P sadece bir imza gelen permütasyon.

Örnekler

Satır ve sütunların permütasyonu

Bir M matrisi , PM yapmak için soldaki bir permütasyon matrisi P ile çarpıldığında, çarpım , M'nin satırlarına izin vermenin sonucudur . Özel bir durum olarak, M bir sütun vektörüyse, PM , M girişlerine izin vermenin sonucudur :

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

Bunun yerine M , MP yapmak için sağdaki bir permütasyon matrisi ile çarpıldığında , ürün M'nin sütunlarına izin vermenin sonucudur . Özel bir durum olarak, M bir satır vektörüyse, MP , M girişlerine izin vermenin sonucudur :

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

Satırların permütasyonu

Permütasyon matris P _tt permütasyon tekabül eden bir ${\displaystyle \pi ={\başlangıç{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}$

${\displaystyle P_{\pi }={\başlangıç{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&1\\0&0&1&0&0\end{bmatrix}}.}$

Bir vektör g verildiğinde ,

${\displaystyle P_{\pi }\mathbf {g} ={\başlangıç{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}}.}$

Açıklama

Bir permütasyon matrisi her zaman formda olacaktır.

${\displaystyle {\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{ j}}\\\end{bmatris}}}$

burada E _{bir i} temsil i için (bir satır olarak) inci baz vektör R ^j , ve burada

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

bir permütasyon permütasyon matris formu.

Şimdi, matris çarpımını gerçekleştirirken , esasen ikincinin her sütunu ile birinci matrisin her satırının nokta çarpımını oluşturur. Bu örnekte, permüte etmek istediğimiz elemanların vektörü ile bu matrisin her satırının nokta çarpımını oluşturacağız. Yani, örneğin, v  = ( g ₀ ,..., g ₅ ) ^T ,

e _{bir ben} · v  =  g _{bir ben}

Böylece, vektör ile permütasyon matrisinin ürünün v yukarıda şeklinde (bir vektör olacak g _{bir 1} , g _{bir 2} , ..., g _{bir j} ) ve bu daha sonra bunun bir permütasyon v biz yana permütasyon formunun olduğunu söylediler

${\displaystyle {\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.}$

Bu nedenle, permütasyon matrisleri gerçekten de vektörlerle çarpılan elemanların sırasını değiştirir.

Kısıtlı formlar

• Costas dizisi , girişler arasındaki yer değiştirme vektörlerinin hepsinin farklı olduğu bir permütasyon matrisi
• n-kraliçe bulmacası , her köşegen ve karşı köşegende en fazla bir girişin olduğu bir permütasyon matrisi

Ayrıca bakınız

• Alternatif işaret matrisi
• Genelleştirilmiş permütasyon matrisi
• kale polinomu
• Kalıcı

Referanslar

• Brualdi, Richard A. (2006). Kombinatoryal matris sınıfları . Matematik Ansiklopedisi ve Uygulamaları. 108 . Cambridge: Cambridge Üniversitesi Yayınları . ISBN'si 0-521-86565-4. Zbl  1106.05001 .
• Joseph, Necnudel; Ashkan, Nikeghbali (2010), Rastgele Permütasyon Matrislerinin Özdeğerlerinin Dağılımı , arXiv : 1005.0402 , Bibcode : 2010arXiv1005.0402N