In
linear algebra, a
Permutation matrix is a
matrix that has exactly one 1 in each row or column and 0s elsewhere. Permutation matrices are the matrix representation of
permutations.
For example, the permutation matrix corresponding to σ=(1)(2 4 5 3) is
- <math>P_\sigma = \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}</math>
and
- <math>P_\sigma\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}.</math>
In general, for a permutation σ on n objects, the correponding permutation matrix is an n-by-n matrix P_{σ} is given by P_{σ}[i,j]=1 if i=σ(j) and 0 otherwise. We have
- <math>P_\sigma\begin{bmatrix}g_1\\ \vdots\\ g_n\end{bmatrix}
=\begin{bmatrix}g_{\sigma(1)}\\ \vdots\\ g_{\sigma(n)}\end{bmatrix}</math>.
Properties:
- P_{σ}P_{π}=P_{σπ} for any two permutations σ and π on n objects.
- P_{(1)} is the identity matrix.
- Permutation matrices are orthogonal matrix and P_{σ}^{-1}=P_{σ-1}.
See also generalized permutation matrix.
All Wikipedia text
is available under the
terms of the GNU Free Documentation License