A permutation matrix is the result of repeatedly interchanging the rows and columns of an identity matrix.
A formal definition of permutation matrix follows.
Definition A matrix is a permutation matrix if and only if it can be obtained from the identity matrix by performing one or more interchanges of the rows and columns of .
Some examples follow.
Example The permutation matrixhas been obtained by interchanging the second and third rows of the identity matrix
Example The permutation matrixhas been obtained by interchanging 1) the second and third rows and 2) the first and fourth columns of the identity matrix
The following proposition states an important property of permutation matrices.
Proposition Each row of a permutation matrix has one entry equal to and all the other entries equal to .
The proof is by induction. A permutation matrix is obtained by performing a sequence of row and column interchanges on the identity matrix. We start from the identity matrix , we perform one interchange and obtain a matrix , we perform a second interchange and obtain another matrix , and so on until at the -th interchange we get the matrix . The rows of are the vectors of the standard basis, so they possess the stated property (each row has one entry equal to and all the other entries equal to ). We need to prove that, for any , if satisfies the property, then also 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 satisfy the same properties that were satisfied by the rows of ; 2) if we interchange two columns, then we modify some of the rows; in particular, two s change their position; however, they remain on the same rows, and the number of s and s on these rows does not change; as a consequence, we still have that each row has one entry equal to and all the other entries equal to .
The same property holds for columns.
Proposition Each column of a permutation matrix has one entry equal to and all the other entries equal to .
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 be a permutation matrix. Then, its rows are the standard basis of the space of vectors, and its columns are the standard basis of the space of vectors.
We already proved that each row of a permutation matrix has one entry equal to and all the other entries equal to . 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 s on the same column, which contradicts the fact that each column of a permutation matrix has one entry equal to and all the other entries equal to . Thus, the rows of are different vectors of the standard basis of the space of vectors. But the standard basis is formed by exactly vectors. Therefore, the rows of are the standard basis. Analogously, we can prove that the columns of are the standard basis of the space of vectors.
A consequence of the previous proposition follows.
Proposition A permutation matrix is full-rank.
The columns of a permutation matrix constitute the standard basis of the space of vectors, and the standard basis is a set of linearly independent vectors. Therefore, the matrix is full-rank.
A permutation matrix is an orthogonal matrix, that is, its transpose is equal to its inverse.
Proposition Let be a permutation matrix. Then, is invertible and
The matrix is invertible because it is full-rank (see above). By the definition of inverse matrix, needs to satisfyThus, we need to prove that that is, the -th entry of is equal to if and to if . But the -th entry of is equal to the dot product of the -th row of and the -th column of . The latter is equal to the transpose of the -th row of . Therefore, If , thenbecause each row of has one entry equal to and all the other entries equal to ; hence, there exists only one such that and in that case . If , thenbecause no column can contain more than one entry different from zero; as a consequence, all the products are equal to zero.
Remember that there are two equivalent ways of performing elementary row and column operations on a given matrix :
perform the operations directly on ;
perform the operations on the identity matrix; then, 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 by a permutation matrix , we are performing on the rows or columns of the same interchanges that were performed on in order to obtain .
Example Consider the permutation matrixobtained by interchanging the first and second rows of the identity matrix . Now, take the matrix and pre-multiply it by . We getThis is the same result we get by interchanging the first and second rows of .
Please cite as:
Taboga, Marco (2021). "Permutation matrix", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/permutation-matrix.
Most of the learning materials found on this website are now available in a traditional textbook format.