permutation matrix (original) (raw)

1 Permutation Matrix

Let n be a positive integer. A permutation matrix is any n×n matrix which can be created by rearranging the rows and/or columns of the n×n identity matrix. More formally, given a permutation π from the symmetric group Sn, one can define an n×n permutation matrix Pπ by Pπ=(δi⁢π⁢(j)), where δ denotes the Kronecker delta symbol.

Premultiplying an n×n matrix A by an n×n permutation matrix results in a rearrangement of the rows of A. For example, if the matrix P is obtained by swapping rows i and j of the n×n identity matrix, then rows i and j of A will be swapped in the product P⁢A.

Postmultiplying an n×n matrix A by an n×n permutation matrix results in a rearrangement of the columns of A. For example, if the matrix P is obtained by swapping rows i and j of the n×n identity matrix, then columns i and j of A will be swapped in the product A⁢P.

2 Properties

Permutation matrices have the following properties:

• •
  They are orthogonal (http://planetmath.org/OrthogonalMatrices).
• •
• •
  For a fixed (http://planetmath.org/Fixed3) positive integer n, the n×n permutation matrices form a group under matrix multiplication.
• •
  Since they have a single 1 in each row and each column, they are doubly stochastic.
• •