What Is a Permutation Matrix? – Nick Higham

A permutation matrix is a sq. matrix through which each row and each column incorporates a single and all the opposite parts are zero. Such a matrix, say, is orthogonal, that’s, , so it’s nonsingular and has determinant . The full variety of permutation matrices is .

Premultiplying a matrix by reorders the rows and postmultiplying by reorders the columns. A permutation matrix that has the specified reordering impact is constructed by doing the identical operations on the id matrix.

Examples of permutation matrices are the id matrix , the reverse id matrix , and the shift matrix (additionally referred to as the cyclic permutation matrix), illustrated for by

Pre- or postmultiplying a matrix by reverses the order of the rows and columns, respectively. Pre- or postmultiplying a matrix by shifts the rows or columns, respectively, one place ahead and strikes the primary one to the final place—that’s, it cyclically permutes the rows or columns. Notice that is a symmetric Hankel matrix and is a circulant matrix.

An elementary permutation matrix differs from in simply two rows and columns, and , say. It may be written , the place is the th column of . Such a matrix is symmetric and so satisfies , and it has determinant . A common permutation matrix could be written as a product of elementary permutation matrices , the place is such that .

It’s straightforward to point out that , which implies that the eigenvalues of are , the place is the th root of unity. The matrix has two diagonals of s, which transfer up by means of the matrix as it’s powered: for and . The next animated gif superposes MATLAB spy plots of , , …, .

The shift matrix performs a basic function in characterizing irreducible permutation matrices. Recall {that a} matrix is irreducible if there doesn’t exist a permutation matrix such that

the place and are sq., nonempty submatrices.

Theorem 1. For a permutation matrix the next situations are equal.

One consequence of Theorem 1 is that for any irreducible permutation matrix , .

The following outcome reveals {that a} reducible permutation matrix could be expressed by way of irreducible permutation matrices.

Theorem 2. Each reducible permutation matrix is permutation much like a direct sum of irreducible permutation matrices.

One other notable permutation matrix is the vec-permutation matrix, which relates to , the place is the Kronecker product.

A permutation matrix is an instance of a doubly stochastic matrix: a nonnegative matrix whose row and column sums are all equal to . A basic outcome characterizes doubly stochastic matrices by way of permutation matrices.

Theorem 3 (Birkhoff). A matrix is doubly stochastic if and provided that it’s a convex mixture of permutation matrices.

In coding, reminiscence could be saved by representing a permutation matrix as an integer vector , the place is the column index of the throughout the th row of . MATLAB features that return permutation matrices also can return the permutation in vector type. Right here is an instance with the MATLAB lu operate that illustrates how permuting a matrix could be carried out utilizing the vector permutation illustration.

>> A = gallery('frank',4), [L,U,P] = lu(A); P
A =
     4     3     2     1
     3     3     2     1
     0     2     2     1
     0     0     1     1
P =
     1     0     0     0
     0     0     1     0
     0     0     0     1
     0     1     0     0
>> P*A
ans =
     4     3     2     1
     0     2     2     1
     0     0     1     1
     3     3     2     1
>> [L,U,p] = lu(A,'vector'); p
p =
     1     3     4     2
>> A(p,:)
ans =
     4     3     2     1
     0     2     2     1
     0     0     1     1
     3     3     2     1

For extra on dealing with permutations in MATLAB see part 24.3 of MATLAB Information.