Permutation matrix

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when used to multiply another matrix, say , results in permuting the rows (when pre-multiplying, to form ) or columns (when post-multiplying, to form ) of the matrix .
Definition.
Given a permutation of "m" elements,
represented in two-line form by 
there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the "m" × "m" identity matrix, , either permute the columns or permute the rows, according to . Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to the other representation. This article will primarily deal with just one of these representations and the other will only be mentioned when there is a difference to be aware of.
The "m × m" permutation matrix "P" = ("p""ij") obtained by permuting the columns of the identity matrix , that is, for each "i", if "j" = ("i") and otherwise, will be referred to as the column representation in this article. Since the entries in row "i" are all 0 except that a 1 appears in column ("i"), we may write
where formula_4, a standard basis vector, denotes a row vector of length "m" with 1 in the "j"th position and 0 in every other position.
For example, the permutation matrix "P" corresponding to the permutation formula_5 is
Observe that the "j"th column of the identity matrix now appears as the ("j")th column of "P".
The other representation, obtained by permuting the rows of the identity matrix , that is, for each "j", "p""ij" = 1 if "i" = ("j") and otherwise, will be referred to as the row representation.
Properties.
The column representation of a permutation matrix is used throughout this section, except when otherwise indicated.
Multiplying formula_7 times a column vector g will permute the rows of the vector:
Repeated use of this result shows that if is an appropriately sized matrix, the product, formula_9 is just a permutation of the rows of . However, observing that 
for each shows that the permutation of the rows is given by −1. (formula_11 is the transpose of matrix .)
As permutation matrices are orthogonal matrices (i.e., formula_12), the inverse matrix exists and can be written as
Multiplying a row vector h times formula_7 will permute the columns of the vector:
Again, repeated application of this result shows that post-multiplying a matrix by the permutation matrix , that is, , results in permuting the columns of . Notice also that
Given two permutations and of elements, the corresponding permutation matrices and acting on column vectors are composed with
The same matrices acting on row vectors (that is, post-multiplication) compose according to the same rule
To be clear, the above formulas use the prefix notation for permutation composition, that is,
Let formula_20 be the permutation matrix corresponding to in its row representation. The properties of this representation can be determined from those of the column representation since formula_21 In particular, 
From this it follows that 
Similarly,
Matrix group.
If (1) denotes the identity permutation, then is the identity matrix.
Let denote the symmetric group, or group of permutations, on {1,2...,}. Since there are permutations, there are permutation matrices. By the formulas above, the permutation matrices form a group under matrix multiplication with the identity matrix as the identity element.
The map is a faithful representation. Thus, .
Doubly stochastic matrices.
A permutation matrix is itself a doubly stochastic matrix, but it also plays a special role in the theory of these matrices. The Birkhoff–von Neumann theorem says that every doubly stochastic real matrix is a convex combination of permutation matrices of the same order and the permutation matrices are precisely the extreme points of the set of doubly stochastic matrices. That is, the Birkhoff polytope, the set of doubly stochastic matrices, is the convex hull of the set of permutation matrices.
Linear algebraic properties.
The trace of a permutation matrix is the number of fixed points of the permutation. If the permutation has fixed points, so it can be written in cycle form as where has no fixed points, then are eigenvectors of the permutation matrix.
To calculate the eigenvalues of a permutation matrix formula_25, write formula_26 as a product of cycles, say, formula_27. Let the corresponding lengths of these cycles be formula_28, and let formula_29 be the set of complex solutions of formula_30. The union of all formula_31s is the set of eigenvalues of the corresponding permutation matrix. The geometric multiplicity of each eigenvalue equals the number of formula_31s that contain it.
From group theory we know that any permutation may be written as a product of transpositions. Therefore, any permutation matrix factors as a product of row-interchanging elementary matrices, each having determinant −1. Thus the determinant of a permutation matrix is just the signature of the corresponding permutation.
Examples.
Permutation of rows and columns.
When a permutation matrix "P" is multiplied from the left with a matrix "M" to make "PM" it will permute the rows of "M" (here the elements of a column vector),<br>
when "P" is multiplied from the right with "M" to make "MP" it will permute the columns of "M" (here the elements of a row vector):
Permutations of rows and columns are for example reflections (see below) and cyclic permutations (see cyclic permutation matrix).
Permutation of rows.
The permutation matrix "P"π corresponding to the permutation formula_5 is
Given a vector g,
Explanation.
A permutation matrix will always be in the form 
where e"a""i" represents the "i"th 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 column of the second. In this instance, we will be forming the dot product of each row of this matrix with the vector of elements we want to permute. That is, for example, v = ("g"0...,"g"5)T, 
So, the product of the permutation matrix with the vector v above, will be a vector in the form ("g""a"1, "g""a"2, ..., "g""a""j"), and that this then is a permutation of v since we have said that the permutation form is 
So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.