|
In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. Permutation matrices are the matrix representation of permutations.
Definition
Given a permutation π of m elements
- <math>\pi : \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace<math>
the permutation matrix Pπ with m elements is defined as
- <math>P_{\pi} :=
\begin{bmatrix}
\mathbf{e}_{\pi(1)} \\
\vdots \\
\mathbf{e}_{\pi(m)} \\
\end{bmatrix}
<math>
with ei being the i-th vector in the identity matrix
Rules
Given two permutations π and σ of m elements and the corresponding permutation matrices Pπ and Pσ
- <math>P_{\pi} P_{\sigma} = P_{\pi \circ \sigma}<math>
As permutation matrices are orthogonal matrices the inverse matrix exists and can be written as
- <math>P_{\pi}^{-1} = P_{\pi^{-1}}<math>
The muliplication of a permutation matrix Pπ with a vector g will permutate the entries of the vector.
- <math>P_\pi \mathbf{g}
=
\begin{bmatrix}
\mathbf{e}_{\pi(1)} \\
\vdots \\
\mathbf{e}_{\pi(n)}
\end{bmatrix}
\begin{bmatrix}
g_1 \\
\vdots \\
g_n
\end{bmatrix}
=
\begin{bmatrix}
g_{\pi(1)} \\
\vdots \\
g_{\pi(n)}
\end{bmatrix}
<math>
Notes
P(1) is the identity matrix. This is clear if one views the permutation matrix of a permutation σ, as the permutation of the rows or columns of the identity matrix.
A permutation matrix is a stochastic matrix; in fact doubly stochastic. One can show that every doubly stochastic matrix is a convex linear combination of permutation matrices of the same size, giving permutation matrices a characterisation as the set of extreme points.
The product of a matrix M with a permutation matrix P on the left (MP) permutes the rows of M, likewise, on the right (PM), permutes the columns of M.
Since the map Sn → A ⊂ GL(n, Z2) is a faithful representation, we have the following:
- There are n! n-by-n permutation matrices, so |Sn| = |A| = n!.
- The n-by-n permutation matrices form a group under matrix multiplication with the identity matrix as the identity element, as Sn is.
The trace of a permutation matrix is the number of fixed points of the permutation. If the permutation has fixed points, so it can be written as (a1)(a2)...(an)q where q has no fixed points, then e1,e2,...,en are eigenvectors of the permutation matrix.
Examples
The permutation matrix Pπ corresponding to the permutation π=(1)(2 4 5 3) is
- <math>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}_{3} \\
\mathbf{e}_{5} \\
\mathbf{e}_{2} \\
\mathbf{e}_{4}
\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}
<math>
and given a vector g
- <math>P_\pi \mathbf{g}
=
\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}
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>
Explanation
A permutation matrix will always be in the form
- <math>\begin{bmatrix}
\mathbf{e}_{a_1} \\
\mathbf{e}_{a_2} \\
\vdots \\
\mathbf{e}_{a_j} \\
\end{bmatrix}<math>
where eai represents the ith basis vector (as a row) for Rj, and where
- <math>\begin{bmatrix}
1 & 2 & \ldots & j \\
a_1 & a_2 & \ldots & a_j\end{bmatrix}<math>
is the permutation form of the permutation matrix.
Now, in performing matrix multiplication, one essentially forms the dot product of each row of the first matrix with each each column of the second. In this instance, we will be forming the dot product of each column of this matrix with the vector with elements we want to permute. That is, for example, if we call this vector v = (g0,...,g5)T,
- eai·v=gai
So, the product of the permutation matrix with the vector v above,
will be a vector in the form (ga1, ga2, ..., gaj), and that this then is a permutation of v since we have said that the permutation form is
- <math>\begin{bmatrix}
1 & 2 & \ldots & j \\
a_1 & a_2 & \ldots & a_j\end{bmatrix}<math>
So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.
Generalization
The sum of the values in each column or row in a permatution matrix adds up to exactly 1. A possible generalization of permutation matrices are matrices where the values of each column and row add up to a number c.
For example in the following matrix M each column or row adds up to 5.
- <math>M =
\begin{bmatrix}
5 & 0 & 0 & 0 & 0 \\
0 & 3 & 2 & 0 & 0 \\
0 & 0 & 0 & 5 & 0 \\
0 & 1 & 2 & 0 & 2 \\
0 & 1 & 1 & 0 & 3
\end{bmatrix}
<math>
A matrix of this sort can be decomposed into permutation matrices as
- <math>M = c_1 P_1 + \ldots + c_t P_t<math>
with
- <math>\sum_{i=1}^{t} c_i = c.<math>
See also
| 
