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

*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

- .

*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)}.

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.