Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Permutation matrix
Main Page | See live article | Alphabetical index

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
1 Definition
2 Rules
3 Notes
4 Examples
5 Explanation
6 Generalization
7 See also

Definition

Given a permutation π of m elements

the permutation matrix Pπ with m elements is defined as

with ei 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(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

and given a vector g

Explanation

A permutation matrix will always be in the form

where eai represents the ith basis vector (as a row) for Rj, 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 = (g0,...,g5)T,

eai·v=gai

So, the product of the permutation matrix with the vector v above, will be a vector in the form (ga1, ga2, ..., gaj), 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