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