# Permutation matrix

In linear algebra, a**permutation matrix**is a binary matrix that has exactly one 1 in each row or column and 0s elsewhere. Permutation matrices are the matrix representation of permutations.

Table of contents |

2 Rules 3 Notes 4 Examples 5 Explanation 6 Generalization 7 See also |

## Definition

Given a permutation π of *m* elements

*P*

_{π}with

*m*elements is defined as

**e**

_{i}being the i-th vector in the identity matrix

## Rules

As permutation matrices are orthogonal matrices the inverse matrix exists and can be written as*P*

_{π}with a vector

**g**will permutate the entries of the vector.

## Notes

*P*_{(1)} is the identity 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.

There are *n!* *n*-by-*n* permutation matrices.

The *n*-by-*n* permutation matrices form a group under matrix multiplication with the identity matrix as the identity element.

If a matrix *M* is multiplied from the left with a permutation matrix *P* (e.g. M P), the row vectors of *M* are permutated.

If a matrix *M* is multiplied from the right with a permutation matrix *P* (e.g. P M), the column vectors of *M* are permutated.

## Examples

The permutation matrix *P*_{π} corresponding to the permutation π=(1)(2 4 5 3) is

**g**

## Explanation

A permutation matrix will always be in the form

**e**

_{ai}represents the

*i*th basis vector (as a row) for

**R**

^{j}, and where

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** = (*g*_{0},...,*g*_{5})^{T},

**e**_{ai}·**v**=*g*_{ai}

**v**above, will be a vector in the form (

*g*

_{a1},

*g*

_{a2}, ...,

*g*

_{aj}), and that this then is a permutation of

**v**since we have said that the permutation form is

## Generalization

For example in the following matrix *M* each column or row adds up to 5.

## See also