35 Permütasyonlar
Determinant, bir kare matrise bir sayı karşılık getiren işlemdir; \(2\). mertebede \(ad - bc\) olarak tanıdığımız bu sayının genel tanımı, matrisin her satırından ve her sütunundan birer eleman seçilerek kurulan çarpımların işaretli toplamıdır. “Her satırdan ve her sütundan bir eleman” seçmenin kaç yolu olduğunu ve her seçimin hangi işareti alacağını söyleyen kavram permütasyondur. Bu kısa bölümde determinantı tanımlamak için gereken kadarını kuruyoruz.
35.1 Tanım ve Gösterim
Tanım 35.1 (Permütasyon) \(n \in \mathbb{Z}^{+}\) olmak üzere \(\{1, 2, \dots, n\}\) kümesinden kendisine tanımlı bire bir (dolayısıyla örten) bir \(\sigma\) fonksiyonuna bir permütasyon denir. Bütün bu permütasyonların kümesi \(S_n\) ile gösterilir.
Bir permütasyon iki biçimde yazılır. İki satırlı gösterimde üstte girdiler, altta görüntüleri sıralanır:
\[\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n)\end{pmatrix}\]
Üst satır her zaman aynı olduğundan çoğu zaman yalnızca alt satır yazılır; buna tek satırlı gösterim denir:
\[\sigma = \sigma(1)\,\sigma(2)\,\cdots\,\sigma(n)\]
Örnek 35.1 (Küçük Permütasyon Kümeleri) \(S_2\) ve \(S_3\)’ün elemanlarını tek satırlı gösterimle yazınız.
Çözüm
\(S_2\)’de \(1\) ve \(2\)’yi iki türlü sıralayabiliriz:
\[S_2 = \{12,\ 21\}\]
\(S_3\)’te ilk sıraya \(3\), kalan iki sıraya \(2\) seçenek düşer:
\[S_3 = \{123,\ 132,\ 213,\ 231,\ 312,\ 321\}\]
\(\blacksquare\)
Önerme 35.1 (S_n’in Eleman Sayısı) \(S_n\) kümesinin \(n!\) tane elemanı vardır.
İspat
Bir permütasyonu tek satırlı gösterimde kurmak, \(1, 2, \dots, n\) sayılarını bir sıraya dizmek demektir. Birinci sıraya \(n\) sayıdan herhangi biri, ikinci sıraya kalan \(n-1\) sayıdan herhangi biri, üçüncü sıraya kalan \(n-2\) sayıdan herhangi biri konabilir ve bu böyle sürer. Öyleyse toplam seçenek sayısı
\[n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 = n!\]
\(\blacksquare\)
Permütasyonlar fonksiyon olduğundan bileşke alınabilir ve her permütasyonun tersi vardır; bileşke yine bire bir ve örten olduğundan \(S_n\)’de kalır. Birim permütasyon \(I = 12\cdots n\) olmak üzere \(\sigma \circ \sigma^{-1} = \sigma^{-1}\circ\sigma = I\)’dır. Kısacası \(S_n\), bileşke işlemiyle bir gruptur; \(n \ge 3\) için değişmeli değildir.
Örnek 35.2 (Bileşke ve Ters Hesabı) \(S_5\)’te \(\sigma = 24513\) ve \(\tau = 41352\) olsun. \(\sigma \circ \tau\), \(\tau \circ \sigma\), \(\sigma^{-1}\) ve \(\tau^{-1}\) permütasyonlarını bulunuz.
Çözüm
Gösterimi okuyalım: \(\sigma(1) = 2\), \(\sigma(2) = 4\), \(\sigma(3) = 5\), \(\sigma(4) = 1\), \(\sigma(5) = 3\); benzer biçimde \(\tau(1) = 4\), \(\tau(2) = 1\), \(\tau(3) = 3\), \(\tau(4) = 5\), \(\tau(5) = 2\).
\(\sigma \circ \tau\). Önce \(\tau\), sonra \(\sigma\) uygulanır:
\[(\sigma\circ\tau)(1) = \sigma(4) = 1, \quad (\sigma\circ\tau)(2) = \sigma(1) = 2, \quad (\sigma\circ\tau)(3) = \sigma(3) = 5\] \[(\sigma\circ\tau)(4) = \sigma(5) = 3, \quad (\sigma\circ\tau)(5) = \sigma(2) = 4\]
\[\sigma\circ\tau = 12534\]
\(\tau \circ \sigma\). Bu kez önce \(\sigma\) uygulanır:
\[(\tau\circ\sigma)(1) = \tau(2) = 1, \quad (\tau\circ\sigma)(2) = \tau(4) = 5, \quad (\tau\circ\sigma)(3) = \tau(5) = 2\] \[(\tau\circ\sigma)(4) = \tau(1) = 4, \quad (\tau\circ\sigma)(5) = \tau(3) = 3\]
\[\tau\circ\sigma = 15243\]
İki sonuç farklıdır; bileşke değişmeli değildir.
Tersler. \(\sigma^{-1}(j)\), “\(j\) sayısı \(\sigma\)’nın kaçıncı sırasında?” sorusunun cevabıdır. \(\sigma = 24513\) dizisinde \(1\) dördüncü, \(2\) birinci, \(3\) beşinci, \(4\) ikinci, \(5\) üçüncü sıradadır:
\[\sigma^{-1} = 41523\]
\(\tau = 41352\) dizisinde \(1\) ikinci, \(2\) beşinci, \(3\) üçüncü, \(4\) birinci, \(5\) dördüncü sıradadır:
\[\tau^{-1} = 25314\]
\(\blacksquare\)
35.2 İşaret
Determinanttaki her çarpımın önüne bir artı ya da eksi konacak; bu işareti belirleyen sayı şudur.
Tanım 35.2 (Ters Sayısı, Çift ve Tek Permütasyon) \(\sigma = j_1j_2\cdots j_n\) bir permütasyon olsun. \(i > k\) olduğu hâlde \(i\) sayısının dizide \(k\)’dan önce geldiği \((i,k)\) ikililerine \(\sigma\)’nın tersleri (inversiyonları) denir. Ters sayısı çift ise \(\sigma\)’ya çift, tek ise tek permütasyon denir.
\(\sigma\)’nın işareti şöyle tanımlanır:
\[\operatorname{sgn}(\sigma) = \begin{cases} +1, & \sigma \text{ çift ise}\\ -1, & \sigma \text{ tek ise}\end{cases}\]
Diziyi soldan sağa tarayın; her sayı için sağında kalan kendisinden küçük sayıları sayın ve bu sayıları toplayın. Toplam, ters sayısıdır.
Örnek 35.3 (İki Permütasyonun İşareti)
- \(S_5\)’te \(\sigma = 35142\) permütasyonunun işaretini bulunuz.
- \(S_6\)’da \(\tau = 542163\) permütasyonunun işaretini bulunuz.
Çözüm
a) Her sayının sağındaki küçükleri sayalım:
| Sayı | Sağında kalan küçükler | Adet |
|---|---|---|
| \(3\) | \(1, 2\) | \(2\) |
| \(5\) | \(1, 4, 2\) | \(3\) |
| \(1\) | — | \(0\) |
| \(4\) | \(2\) | \(1\) |
| \(2\) | — | \(0\) |
Toplam \(2 + 3 + 0 + 1 + 0 = 6\); çift sayıda ters vardır, öyleyse \(\sigma\) çifttir ve \(\operatorname{sgn}(\sigma) = +1\)’dir.
b) Aynı sayımı \(\tau = 542163\) için yapalım:
| Sayı | Sağında kalan küçükler | Adet |
|---|---|---|
| \(5\) | \(4, 2, 1, 3\) | \(4\) |
| \(4\) | \(2, 1, 3\) | \(3\) |
| \(2\) | \(1\) | \(1\) |
| \(1\) | — | \(0\) |
| \(6\) | \(3\) | \(1\) |
| \(3\) | — | \(0\) |
Toplam \(4 + 3 + 1 + 0 + 1 + 0 = 9\); tek sayıda ters vardır, öyleyse \(\tau\) tektir ve \(\operatorname{sgn}(\tau) = -1\)’dir.
\(\blacksquare\)
Birim permütasyon \(I = 12\cdots n\) artan sıralı olduğundan hiç tersi yoktur; \(I\) çifttir ve \(\operatorname{sgn}(I) = +1\)’dir. \(S_3\)’te \(123\), \(231\), \(312\) çift; \(132\), \(213\), \(321\) tektir — çift ve tek permütasyonların sayısı eşittir. Bu, \(n \ge 2\) için her zaman böyledir.
35.3 İşaretin Çarpımsallığı
İşaretin determinant hesabındaki bütün gücü, bileşkeyle uyumlu olmasından gelir. Bunu doğrudan ters sayarak göstermek zahmetlidir; kısa yol, işareti bir polinom üzerinden okumaktır.
Tanım 35.3 (Fark Polinomu) \(n\) değişkenli
\[g(x_1, x_2, \dots, x_n) = \prod_{i < j} (x_i - x_j)\]
polinomuna fark polinomu denir; çarpım, \(1 \le i < j \le n\) koşulunu sağlayan bütün ikililer üzerinden alınır. Bir \(\sigma\) permütasyonu için
\[\sigma(g) := \prod_{i<j}\big(x_{\sigma(i)} - x_{\sigma(j)}\big)\]
yazalım; bu, \(g\)’de her \(x_i\) değişkeninin yerine \(x_{\sigma(i)}\) konarak elde edilen polinomdur.
Lemma 35.1 (Fark Polinomu İşareti Görür) Her \(\sigma \in S_n\) için
\[\sigma(g) = \operatorname{sgn}(\sigma)\cdot g\]
İspat
\(\sigma(g)\)’nin çarpanları, \(i < j\) olan her ikili için \(x_{\sigma(i)} - x_{\sigma(j)}\) biçimindedir. \(\sigma\) bire bir olduğundan \(\{\sigma(i), \sigma(j)\}\) ikilileri, \(\{1, \dots, n\}\)’in bütün ikili alt kümelerini tam bir kez tarar. Öyleyse \(\sigma(g)\) ile \(g\) aynı çarpanlardan oluşur; tek fark bazı çarpanların ters işaretle yazılmış olmasıdır:
- \(\sigma(i) < \sigma(j)\) ise \(x_{\sigma(i)} - x_{\sigma(j)}\) çarpanı \(g\)’de aynen bulunur;
- \(\sigma(i) > \sigma(j)\) ise \(x_{\sigma(i)} - x_{\sigma(j)} = -\big(x_{\sigma(j)} - x_{\sigma(i)}\big)\) olur ve bir \((-1)\) çıkar.
İkinci durum tam olarak \(\sigma\)’nın terslerinde ortaya çıkar: \(i < j\) olduğu hâlde \(\sigma(i) > \sigma(j)\) olması, büyük sayının dizide küçükten önce gelmesi demektir. Ters sayısı \(t\) ise
\[\sigma(g) = (-1)^{t} g = \operatorname{sgn}(\sigma)\cdot g\]
\(\blacksquare\)
Teorem 35.1 (İşaret Çarpımsaldır) Her \(\sigma, \tau \in S_n\) için
\[\operatorname{sgn}(\tau \circ \sigma) = \operatorname{sgn}(\tau)\cdot\operatorname{sgn}(\sigma) \qquad \text{ve} \qquad \operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma)\]
İspat
Çarpımsallık. \(\sigma(g)\) işlemi “her \(x_i\) yerine \(x_{\sigma(i)}\) yaz” demekti. Bu yer değiştirmeyi önce \(\sigma\), sonra \(\tau\) için art arda uygularsak, \(x_i\) önce \(x_{\sigma(i)}\), o da \(x_{\tau(\sigma(i))}\) olur; yani iki işlemin art arda uygulanması \(\tau \circ \sigma\) permütasyonunun yer değiştirmesidir:
\[(\tau\circ\sigma)(g) = \tau\big(\sigma(g)\big)\]
Şimdi önceki lemmayı iki kez kullanalım. Sağ tarafta önce içteki \(\sigma(g) = \operatorname{sgn}(\sigma)g\) yazılır; sabit bir katsayı yer değiştirmeden etkilenmediğinden
\[\tau\big(\sigma(g)\big) = \tau\big(\operatorname{sgn}(\sigma)g\big) = \operatorname{sgn}(\sigma)\cdot\tau(g) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\cdot g\]
Sol taraf ise yine lemma gereği \(\operatorname{sgn}(\tau\circ\sigma)\cdot g\)’dir. \(g\) sıfır polinomu olmadığından katsayılar eşittir:
\[\operatorname{sgn}(\tau\circ\sigma) = \operatorname{sgn}(\tau)\operatorname{sgn}(\sigma)\]
Ters. \(\sigma\circ\sigma^{-1} = I\) ve \(\operatorname{sgn}(I) = 1\) olduğundan, az önceki eşitlikle
\[\operatorname{sgn}(\sigma)\cdot\operatorname{sgn}(\sigma^{-1}) = 1\]
İşaretler yalnızca \(+1\) ya da \(-1\) olabildiğinden bu ancak iki işaret eşitken mümkündür.
\(\blacksquare\)
En basit permütasyonlardan biri, yalnızca iki sayının yerini değiştirip kalanına dokunmayan permütasyondur. Determinantın işaret kuralı bunun işaretine dayanır.
Tanım 35.4 (Transpozisyon) \(k \ne l\) olmak üzere \(\tau(k) = l\), \(\tau(l) = k\) ve \(i \ne k,l\) için \(\tau(i) = i\) olan \(\tau\) permütasyonuna bir transpozisyon denir.
Teorem 35.2 (Her Transpozisyon Tektir) Her transpozisyonun işareti \(-1\)’dir.
İspat
\(k < l\) olsun. \(\tau\)’nun tek satırlı gösterimi, birim permütasyonun \(k\). ve \(l\). sıralarındaki sayıların yer değiştirmiş hâlidir:
\[\tau = 1\,2\,\cdots\,(k-1)\ \underbrace{l}_{k.\text{ sıra}}\ (k+1)\,\cdots\,(l-1)\ \underbrace{k}_{l.\text{ sıra}}\ (l+1)\,\cdots\,n\]
Terslerini sayalım. Yerinde duran sayılar kendi aralarında artan sırada olduğundan aralarında ters yoktur; ters ancak \(k\) ya da \(l\) içeren ikililerde ortaya çıkar:
- \((l, k)\) ikilisi: \(l > k\) ve \(l\) dizide önce geliyor — \(1\) ters.
- \(l\) ile aradaki \(k+1, \dots, l-1\) sayıları: \(l\) bunların hepsinden büyük ve hepsinden önce geliyor — \(l - k - 1\) ters.
- Aradaki \(k+1, \dots, l-1\) sayıları ile \(k\): her biri \(k\)’dan büyük ve \(k\)’dan önce geliyor — \(l - k - 1\) ters.
Toplam ters sayısı
\[1 + 2(l - k - 1)\]
Bu sayı her zaman tektir; öyleyse \(\tau\) tektir ve \(\operatorname{sgn}(\tau) = -1\)’dir.
\(\blacksquare\)
Determinantın tanımında her permütasyon bir işaretle çarpılacak. Bu bölümün üç sonucu bir sonraki bölümde şu üç özelliğe dönüşür: işaretin çarpımsallığı \(|AB| = |A||B|\) eşitliğinin, transpozisyonun tek olması “iki satır yer değiştirince determinantın işaret değiştirmesi”nin, \(\operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma)\) eşitliği ise \(|A^{t}| = |A|\)’nın temelidir.
35.4 Alıştırma
Alıştırma 35.1 (Permütasyon Hesapları)
- \(S_4\)’ün bütün elemanlarını tek satırlı gösterimle yazınız ve kaçının çift olduğunu bulunuz.
- \(S_6\)’da \(\sigma = 341625\) permütasyonunun işaretini ve \(\sigma^{-1}\)’i bulunuz.
- \(\sigma\) tek, \(\tau\) çift ise \(\sigma \circ \tau\) ve \(\tau \circ \sigma \circ \tau^{-1}\) permütasyonlarının işaretlerini belirleyiniz.
Çözüm
1. \(|S_4| = 4! = 24\)’tür. Birinci sıradaki sayıya göre gruplayalım:
\[1234,\ 1243,\ 1324,\ 1342,\ 1423,\ 1432\] \[2134,\ 2143,\ 2314,\ 2341,\ 2413,\ 2431\] \[3124,\ 3142,\ 3214,\ 3241,\ 3412,\ 3421\] \[4123,\ 4132,\ 4213,\ 4231,\ 4312,\ 4321\]
Çift ve tek permütasyonların sayısı eşit olduğundan \(12\) tanesi çifttir. (Neden eşit olduğunu görmek için: \(\tau\) sabit bir transpozisyon olsun; \(\sigma \mapsto \tau\circ\sigma\) eşlemesi çiftleri teklere, tekleri çiftlere birebir götürür.)
2. Sağdaki küçükleri sayalım: \(3 \to \{1,2\}\): \(2\); \(4 \to \{1,2\}\): \(2\); \(1 \to\) yok: \(0\); \(6 \to \{2,5\}\): \(2\); \(2 \to\) yok: \(0\); \(5 \to\) yok: \(0\). Toplam \(6\), çift; \(\operatorname{sgn}(\sigma) = +1\).
Ters için “hangi sayı kaçıncı sırada?” sorusunu cevaplayalım: \(\sigma = 341625\) dizisinde \(1\) üçüncü, \(2\) beşinci, \(3\) birinci, \(4\) ikinci, \(5\) altıncı, \(6\) dördüncü sıradadır:
\[\sigma^{-1} = 351264\]
3. İşaret çarpımsal olduğundan
\[\operatorname{sgn}(\sigma\circ\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau) = (-1)(+1) = -1\]
yani \(\sigma\circ\tau\) tektir. İkincisi için üç çarpanı birleştirelim ve \(\operatorname{sgn}(\tau^{-1}) = \operatorname{sgn}(\tau)\) olduğunu kullanalım:
\[\operatorname{sgn}(\tau\circ\sigma\circ\tau^{-1}) = \operatorname{sgn}(\tau)\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau) = \big(\operatorname{sgn}(\tau)\big)^{2}\operatorname{sgn}(\sigma) = \operatorname{sgn}(\sigma) = -1\]
öyleyse \(\tau\circ\sigma\circ\tau^{-1}\) de tektir.
\(\blacksquare\)