Permutation Matrix

Let $n$ be a positive integer. A permutation matrix is any $n\times n$ matrix which can be created by rearranging the rows and/or columns of the $n\times n$ identity matrix. More formally, given a permutation $\pi$ from the symmetric group $S_n$ , one can define an $n\times n$ permutation matrix $P_{\pi}$ by $P_{\pi}=(\delta_{i\, \pi(j)})$ , where $\delta$ denotes the Kronecker delta symbol.

Premultiplying an $n\times n$ matrix $A$ by an $n\times 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 \times n$ identity matrix, then rows $i$ and $j$ of $A$ will be swapped in the product $PA$ .

Postmultiplying an $n\times n$ matrix $A$ by an $n\times 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 \times n$ identity matrix, then columns $i$ and $j$ of $A$ will be swapped in the product $AP$ .

Properties

Permutation matrices have the following properties:

• They are orthogonal.
• They are invertible.
• For a fixed positive integer $n$ , the $n \times 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.
• They are the extreme points of the convex set of doubly stochastic matrices.