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.

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

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.

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

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.

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

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.

## 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

- Desmond Higham and Nicholas Higham, MATLAB Information, third version, SIAM, 2017.
- Roger A. Horn and Charles R. Johnson, Matrix Evaluation, second version, Cambridge College Press, 2013. My evaluate of the second version.
- Charles F. Van Mortgage, Computational Frameworks for the Quick Fourier Rework, SIAM, 1992.
- Fuzhen Zhang, Matrix Concept: Fundamental Outcomes and Strategies, Springer, 2011.