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.

Definition

Given a permutation π of m elements

the permutation matrix P_π with m elements is defined as

with e_i 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_σ

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

The muliplication of a permutation matrix P_π with a vector g will permutate the entries of the vector.

Notes

P₍₁₎ 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

and given a vector g

Explanation

A permutation matrix will always be in the form

where e_ai represents the ith basis vector (as a row) for R^j, and where

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 = (g₀,...,g₅)^T,

e_ai·v=g_ai

So, the product of the permutation matrix with the vector 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

So, permutaton 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.

A matrix of this sort can be decomposed into permutation matrices as

with

See also

• Generalized permutation matrix