Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Permutation matrix

by , PhD

A permutation matrix is the result of repeatedly interchanging the rows and columns of an identity matrix.

Table of Contents

Definition

A formal definition of permutation matrix follows.

Definition A $K imes K$ matrix $P$ is a permutation matrix if and only if it can be obtained from the $K imes K$ identity matrix I by performing one or more interchanges of the rows and columns of I.

Some examples follow.

Example The $3 imes 3$ permutation matrix[eq1]has been obtained by interchanging the second and third rows of the $3 imes 3 $ identity matrix [eq2]

Example The $4 imes 4$ permutation matrix[eq3]has been obtained by interchanging 1) the second and third rows and 2) the first and fourth columns of the $4 imes 4$ identity matrix [eq4]

Properties

The following proposition states an important property of permutation matrices.

Proposition Each row of a permutation matrix has one entry equal to 1 and all the other entries equal to 0.

Proof

The proof is by induction. A permutation matrix $P$ is obtained by performing a sequence of row and column interchanges on the identity matrix. We start from the identity matrix I, we perform one interchange and obtain a matrix $P_{1}$, we perform a second interchange and obtain another matrix $P_{2}$, and so on until at the $N$-th interchange we get the matrix $P_{N}=P$. The rows of I are the vectors of the standard basis, so they possess the stated property (each row has one entry equal to 1 and all the other entries equal to 0). We need to prove that, for any n, if $P_{n-1}$ satisfies the property, then also $P_{n}$ satisfies it. There are two cases: 1) if we interchange two rows, then we modify only the order of the rows, but not their entries; as a consequence, the rows of $P_{n}$ satisfy the same properties that were satisfied by the rows of $P_{n-1}$; 2) if we interchange two columns, then we modify some of the rows; in particular, two 1s change their position; however, they remain on the same rows, and the number of 1s and 0s on these rows does not change; as a consequence, we still have that each row has one entry equal to 1 and all the other entries equal to 0.

The same property holds for columns.

Proposition Each column of a permutation matrix has one entry equal to 1 and all the other entries equal to 0.

Proof

The proof is almost identical to the previous one. Just replace rows with columns and vice-versa.

By combining the two propositions above, we obtain the following proposition.

Proposition Let $P$ be a $K imes K$ permutation matrix. Then, its rows are the standard basis of the space of $1 imes K$ vectors, and its columns are the standard basis of the space of Kx1 vectors.

Proof

We already proved that each row of a permutation matrix has one entry equal to 1 and all the other entries equal to 0. Therefore, the rows belong to the standard basis. We need to prove that there are no repetitions, that is, there are no two identical rows. This is proved by contradiction: if two rows were identical, then we would have two 1s on the same column, which contradicts the fact that each column of a permutation matrix has one entry equal to 1 and all the other entries equal to 0. Thus, the rows of $P$ are K different vectors of the standard basis of the space of $1 imes K$ vectors. But the standard basis is formed by exactly K vectors. Therefore, the rows of $P$ are the standard basis. Analogously, we can prove that the columns of $P$ are the standard basis of the space of Kx1 vectors.

A consequence of the previous proposition follows.

Proposition A permutation matrix is full-rank.

Proof

The columns of a $K imes K$ permutation matrix constitute the standard basis of the space of Kx1 vectors, and the standard basis is a set of linearly independent vectors. Therefore, the matrix is full-rank.

Inverse of a permutation matrix

A permutation matrix is an orthogonal matrix, that is, its transpose is equal to its inverse.

Proposition Let $P$ be a $K imes K$ permutation matrix. Then, $P$ is invertible and[eq5]

Proof

The matrix $P$ is invertible because it is full-rank (see above). By the definition of inverse matrix, $P^{-1}$ needs to satisfy[eq6]Thus, we need to prove that [eq7]that is, the $left( i,j ight) $-th entry of $PP^{intercal }$ is equal to 1 if $i=j$ and to 0 if $i eq j$. But the $left( i,j ight) $-th entry of $PP^{intercal }$ is equal to the dot product of the i-th row of $P$ and the $j$-th column of $P^{intercal }$. The latter is equal to the transpose of the $j$-th row of $P$. Therefore, [eq8] If $i=j$, then[eq9]because each row of $P$ has one entry equal to 1 and all the other entries equal to 0; hence, there exists only one k such that $P_{ik} eq 0$ and in that case $P_{ik}=1$. If $i eq j$, then[eq10]because no column k can contain more than one entry different from zero; as a consequence, all the products $P_{ik}P_{jk}$ are equal to zero.

Permutation matrices and elementary operations

Remember that there are two equivalent ways of performing elementary row and column operations on a given matrix A:

  1. perform the operations directly on A;

  2. perform the operations on the identity matrix; then, A is pre- or post-multiplied by the matrix obtained by transforming the identity matrix.

Note that interchanges of rows or columns are elementary operations, and a permutation matrix is obtained by performing interchanges of the rows or columns of an identity matrix. Therefore, when we pre- or post-multiply a given matrix A by a permutation matrix $P$, we are performing on the rows or columns of A the same interchanges that were performed on I in order to obtain $P$.

Example Consider the permutation matrix[eq11]obtained by interchanging the first and second rows of the $3 imes 3$ identity matrix I. Now, take the matrix [eq12]and pre-multiply it by $P$. We get[eq13]This is the same result we get by interchanging the first and second rows of A.

How to cite

Please cite as:

Taboga, Marco (2021). "Permutation matrix", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/permutation-matrix.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.