Yazan : Şadi Evren ŞEKER
Özellikle veri güvenliği ve şifreleme algoritmaları tarafından kullanılan permutasyon matrisi tanım olarak, her satır ve sütununda sadece bir tane 1 değeri olan ve diğer değerlerinin 0 olduğu matristir (masfuf).
Örneğin aşağıdaki matris bir permutasyon matrisidir:
| 100 |
| 001 |
| 010 |
Ve bu matrisin diğer bir permutasyonu aşağıdaki şekilde olabilir:
| 001 |
| 010 |
| 100 |
Kare matrisler için permutasyon ihtimalleri, satırların yer değiştirmesi veya sütunların yer değiştirmesi olarak düşünülebilir.
Örneğin yukarıdaki ilk permutasyon matrisinde 1,2,3 şeklinde satır numaraları olduğunu kabul edersek, ikinci matriste bu sıralama 2,3,1 sırasındadır. Görüleceği üzere satır sıralamasının değiştirilmesi ile permutasyon matrisleri üretilebilir.
Bir permutasyon matrisinin alabileceği ihtimal sayısı, yukarıdaki satır değiştirme işlemlerinden de anlaşılacağı üzere n! adettir (n kare matrisin boyutu olmak üzere).
Yukarıdaki satır değiştirme işlemleri temel alınarak, satır vektörü üzerinden permütasyon matrisi modellenebilir.
Örneğin j. sıradaki değeri 1 olan satır vektörünü ej olarak gösterelim.
Buna göre yukarıdaki ilk matrisi aşağıdaki şekilde yazabiliriz:
| e1 |
| e3 |
| e2 |
Yukarıdaki gösterime göre, ilk satırın ilk elemanı 1 diğerleri 0, ikinci satırın 3. elemanı 1 diğerleri 0 ve son satırın 2. elemanı 1 ve diğerleri 0 sonucu çıkarılabilir ki bu da yazının başındaki örnek matrisi vermektedir.
Satır bazlı gösterim gibi sütun bazlı gösterim de mümkündür. Yani bir permutasyon matrisinin her sütununda sadece bir adet 1 değeri olacağına göre , hangi satırdakinin 1 olduğunu gösteren bir fonksiyon kullanılabilir. Bu fonksiyon, π sembolü ile gösterili ve örneğin p(2) fonksiyonu, 2. satırı 1 olan ve diğer satırları 0 olan kolon vektörü olarak düşünülebilir.
Buna göre yazının başındaki matrisi yazacak olursak:
| π(1) π(2) π(2) |
Şeklinde yazabiliriz.
Permutasyon Matrislerinde Çarpma
Bir permutasyon matrisini herhangi bir kolon vektörü ile çarparsak, permutasyon matrisi bu kolon vektörünün satırlarının yerini değiştirir.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
Yukarıdaki şekilde verilmiş permutasyon matrisini, aşağıdaki g kolon vektörü ile çarpmayı deneyelim:
| 1 |
| 2 |
| 3 |
| 4 |
Çarpma işleminin sonucu, aşağıda verilmiştir:
| 1 |
| 4 |
| 2 |
| 3 |
Bu çarpma işleminde dikkat edilecek bir husus, g vektörünün elemanlarının yer değiştirdiğidir. Bu yer değiştirme ise permutasyon matrisindeki sıraya göre yapılmaktadır.
Örneğimizdeki permutasyon matrisinin satır değerlerini yazalım: e1, e4, e2, e3
İşte bu değerler aynı zamanda bir çarpma işlemi sonrasında, çarpılan kolon vektörünün elemanlarının yer değiştirme sırasını da vermektedir.