Sunday, October 2, 2022
HomeMatlabWhat Is a Permutation Matrix? – Nick Higham

What Is a Permutation Matrix? – Nick Higham


A permutation matrix is a sq. matrix through which each row and each column incorporates a single 1 and all the opposite parts are zero. Such a matrix, P say, is orthogonal, that’s, P^TP = PP^T = I_n, so it’s nonsingular and has determinant pm 1. The full variety of ntimes n permutation matrices is n!.

Premultiplying a matrix by P reorders the rows and postmultiplying by P reorders the columns. A permutation matrix P 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 I_n, the reverse id matrix J_n, and the shift matrix K_n (additionally referred to as the cyclic permutation matrix), illustrated for n = 4 by

notag   I_4 = begin{bmatrix}   1 & 0 & 0 & 0     0 & 1 & 0 & 0     0 & 0 & 1 & 0     0 & 0 & 0 & 1 end{bmatrix}, qquad   J_4 = begin{bmatrix}   0 & 0 & 0 & 1     0 & 0 & 1 & 0     0 & 1 & 0 & 0     1 & 0 & 0 & 0 end{bmatrix}, qquad   K_4 = begin{bmatrix}   0 & 1 & 0 & 0     0 & 0 & 1 & 0     0 & 0 & 0 & 1     1 & 0 & 0 & 0 end{bmatrix}.

Pre- or postmultiplying a matrix by J_n reverses the order of the rows and columns, respectively. Pre- or postmultiplying a matrix by K_n 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 J_n is a symmetric Hankel matrix and K_n is a circulant matrix.

An elementary permutation matrix P differs from I_n in simply two rows and columns, i and j, say. It may be written P = I_n - (e_i-e_j)(e_i-e_j)^T, the place e_i is the ith column of I_n. Such a matrix is symmetric and so satisfies P^2 = I_n, and it has determinant -1. A common permutation matrix could be written as a product of elementary permutation matrices P = P_1P_2dots P_k, the place k is such that det(P) = (-1)^k.

It’s straightforward to point out that det(lambda I - K_n) = lambda^n - 1, which implies that the eigenvalues of K_n are 1, w, w^2, dots, w^{n-1}, the place w = exp(2pimathrm{i}/n) is the nth root of unity. The matrix K_n has two diagonals of 1s, which transfer up by means of the matrix as it’s powered: K_n^i ne I for i< n and K_n^n = I. The next animated gif superposes MATLAB spy plots of K_{64}, K_{64}^2, …, K_{64}^{64} = I_{64}.

shift_powers.gif

The shift matrix K_n performs a basic function in characterizing irreducible permutation matrices. Recall {that a} matrix Ainmathbb{C}^{ntimes n} is irreducible if there doesn’t exist a permutation matrix P such that

notag         P^TAP = begin{bmatrix} A_{11} & A_{12}                                     0   & A_{22}                  end{bmatrix},

the place A_{11} and A_{22} are sq., nonempty submatrices.

Theorem 1. For a permutation matrix P in mathbb{R}^{n times n} the next situations are equal.

One consequence of Theorem 1 is that for any irreducible permutation matrix P, mathrm{rank}(P - I) = mathrm{rank}(K_n - I) = n-1.

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 Aotimes B to Botimes A, the place otimes 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 1. 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 P as an integer vector p, the place p_i is the column index of the 1 throughout the ith row of P. 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.

Notes

For proofs of Theorems 1–3 see Zhang (2011, Sec. 5.6). Theorem 3 can be proved in Horn and Johnson (2013, Thm. 8.7.2).

Permutations play a key function within the quick Fourier rework and its environment friendly implementation; see Van Mortgage (1992).

References

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments