- Source: Matriks permutasi
Dalam matematika, khususnya dalam teori matriks, matriks permutasi adalah matriks biner persegi yang memiliki tepat satu entri 1 di setiap baris dan setiap kolom dan 0 di tempat lain. Setiap matriks tersebut, misalnya P, mewakili permutasi dari m elemen dan, ketika digunakan untuk mengalikan matriks lain, katakanlah A, menghasilkan permutasi baris (saat pra-perkalian, untuk membentuk PA) atau kolom (saat pasca-perkalian, untuk membentuk AP) dari matriks A.
Definisi
Diberikan permutasi π dari m elemen,
π
:
{
1
,
…
,
m
}
→
{
1
,
…
,
m
}
{\displaystyle \pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace }
diwakili dalam bentuk dua baris oleh
(
1
2
⋯
m
π
(
1
)
π
(
2
)
⋯
π
(
m
)
)
,
{\displaystyle {\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},}
ada dua cara alami untuk mengasosiasikan permutasi dengan matriks permutasi; yaitu, dimulai dengan matriks identitas m × m, Im, baik mengubah kolom atau mengubah baris, menurut π. Kedua metode untuk mendefinisikan matriks permutasi muncul dalam literatur dan properti yang diekspresikan dalam satu representasi dapat dengan mudah dikonversi ke representasi lainnya. Artikel ini terutama akan membahas salah satu dari representasi ini dan yang lainnya hanya akan disebutkan jika ada perbedaan yang harus diperhatikan.
Matriks permutasi m × m Pπ = (pij) diperoleh dengan mengubah kolom-kolom dari matriks identitas Im, yaitu untuk setiap i, i, pij = 1 if j = π(i) sebaliknya, akan disebut sebagai representasi kolom dalam artikel ini. Karena entri pada baris i semuanya 0 kecuali bahwa 1 muncul di kolom (i), kita dapat menulis
P
π
=
[
e
π
(
1
)
e
π
(
2
)
⋮
e
π
(
m
)
]
,
{\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}},}
dimana
e
j
{\displaystyle \mathbf {e} _{j}}
, vektor basis standar, menyatakan vektor baris dengan panjang m dengan 1 pada posisi ke-j dan 0 pada setiap posisi lainnya.
Misalnya, matriks permutasi Pπ sesuai dengan permutasi
π
=
(
1
2
3
4
5
1
4
2
5
3
)
{\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}
adalah
P
π
=
[
e
π
(
1
)
e
π
(
2
)
e
π
(
3
)
e
π
(
4
)
e
π
(
5
)
]
=
[
e
1
e
4
e
2
e
5
e
3
]
=
[
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
]
.
{\displaystyle P_{\pi }={\begin{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&0&1\\0&0&1&0&0\end{bmatrix}}.}
Amati bahwa kolom ke-j dari matriks identitas I5 sekarang muncul sebagai kolom ke-π(j) dari Pπ.
Representasi lain, diperoleh dengan permutasi baris dari matriks identitas Im, yaitu, untuk setiap j, pij = 1 jika i = π(j) dan pij = 0 sebaliknya, akan disebut sebagai representasi baris.
Referensi
Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices, arXiv:1005.0402 , Bibcode:2010arXiv1005.0402N
Kata Kunci Pencarian:
- Matriks permutasi
- Faktorisasi
- Daftar topik permutasi
- Determinan
- Daftar matriks yang dinamakan
- Transpos
- Nilai dan vektor eigen
- Grup permutasi
- Rumus Cauchy–Binet
- Simetri oktahedral
