Permutation matrix
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
and
In general, for a permutation σ on
n objects, the corresponding permutation matrix is an
n-by-
n matrix
Pσ is given by
Pσ[
i,
j]=1 if
i=σ(
j) and 0 otherwise. We have
- .
Properties:
- PσPπ=Pσπ for any two permutations σ and π on n objects.
- P(1) is the identity matrix.
- Permutation matrices are orthogonal matrices and (Pσ)-1=P(σ-1).
See also
generalized permutation matrix.
A permutation matrix is a stochastic matrix; in fact doubly stochastic. One can show that all doubly stochastic matrices of a fixed size are convex linear combinations of permutation matrices, giving them a characterisation as the set of extreme points.