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
In general, for a permutation σ on n
objects, the corresponding permutation matrix is an n
is given by Pσ
]=1 if i
) and 0 otherwise. We have
- 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.