Permutation matrix

Short description: Matrix with exactly one 1 per row and column

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0.[1]: 26 An n × n permutation matrix can represent a permutation of n elements. Pre-multiplying an n-row matrix M by a permutation matrix P, forming PM, results in permuting the rows of M, while post-multiplying an n-column matrix M, forming MP, permutes the columns of M.

Every permutation matrix P is orthogonal, with its inverse equal to its transpose: P−1=PT.[1]: 26 Indeed, permutation matrices can be characterized as the orthogonal matrices whose entries are all non-negative.[2]

## Contents

* 1 The two permutation/matrix correspondences
* 2 Permutation matrices permute rows or columns
* 3 The transpose is also the inverse
* 4 Multiplying permutation matrices
* 5 Matrix group
* 6 Doubly stochastic matrices
* 7 Linear-algebraic properties
* 8 Restricted forms
* 9 See also
* 10 References

## The two permutation/matrix correspondences

There are two natural one-to-one correspondences between permutations and permutation matrices, one of which works along the rows of the matrix, the other along its columns. Here is an example, starting with a permutation π in two-line form at the upper left:

π:(12343241)⟷Rπ:(0010010000011000)↕↕Cπ:(0001010010000010)⟷π−1:(12344213)

The row-based correspondence takes the permutation π to the matrix Rπ at the upper right. The first row of Rπ has its 1 in the third column because π(1)=3. More generally, we have Rπ=(rij) where rij=1 when j=π(i) and rij=0 otherwise.

The column-based correspondence takes π to the matrix Cπ at the lower left. The first column of Cπ has its 1 in the third row because π(1)=3. More generally, we have Cπ=(cij) where cij is 1 when i=π(j) and 0 otherwise. Since the two recipes differ only by swapping i with j, the matrix Cπ is the transpose of Rπ; and, since Rπ is a permutation matrix, we have Cπ=RπT=Rπ−1. Tracing the other two sides of the big square, we have Rπ−1=Cπ=Rπ−1 and Cπ−1=Rπ.[3]

## Permutation matrices permute rows or columns

Multiplying a matrix M by either Rπ or Cπ on either the left or the right will permute either the rows or columns of M by either π or π−1. The details are a bit tricky.

To begin with, when we permute the entries of a vector (v1,…,vn) by some permutation π, we move the ith entry vi of the input vector into the π(i)th slot of the output vector. Which entry then ends up in, say, the first slot of the output? Answer: The entry vj for which π(j)=1, and hence j=π−1(1). Arguing similarly about each of the slots, we find that the output vector is

(vπ−1(1),vπ−1(2),…,vπ−1(n)),

even though we are permuting by π, not by π−1. Thus, in order to permute the entries by π, we must permute the indices by π−1.[1]: 25 (Permuting the entries by π is sometimes called taking the alibi viewpoint, while permuting the indices by π would take the alias viewpoint.[4])

Now, suppose that we pre-multiply some n-row matrix M=(mi,j) by the permutation matrix Cπ. By the rule for matrix multiplication, the (i,j)th entry in the product CπM is

∑k=1nci,kmk,j,

where ci,k is 0 except when i=π(k), when it is 1. Thus, the only term in the sum that survives is the term in which k=π−1(i), and the sum reduces to mπ−1(i),j. Since we have permuted the row index by π−1, we have permuted the rows of M themselves by π.[1]: 25 A similar argument shows that post-multiplying an n-column matrix M by Rπ permutes its columns by π.

The other two options are pre-multiplying by Rπ or post-multiplying by Cπ, and they permute the rows or columns respectively by π−1, instead of by π.

## The transpose is also the inverse

A related argument proves that, as we claimed above, the transpose of any permutation matrix P also acts as its inverse, which implies that P is invertible. (Artin leaves that proof as an exercise,[1]: 26 which we here solve.) If P=(pi,j), then the (i,j)th entry of its transpose PT is pj,i. The (i,j)th entry of the product PPT is then

∑k=1npi,kpj,k.

Whenever i≠j, the kth term in this sum is the product of two different entries in the kth column of P; so all terms are 0, and the sum is 0. When i=j, we are summing the squares of the entries in the ith row of P, so the sum is 1. The product PPT is thus the identity matrix. A symmetric argument shows the same for PTP, implying that P is invertible with P−1=PT.

## Multiplying permutation matrices

Given two permutations of n elements 𝜎 and Template:Tau, the product of the corresponding column-based permutation matrices Cσ and Cτ is given,[1]: 25 as you might expect, by CσCτ=Cσ∘τ, where the composed permutation σ∘τ applies first Template:Tau and then 𝜎, working from right to left: (σ∘τ)(k)=σ(τ(k)). This follows because pre-multiplying some matrix by Cτ and then pre-multiplying the resulting product by Cσ gives the same result as pre-multiplying just once by the combined Cσ∘τ.

For the row-based matrices, there is a twist: The product of Rσ and Rτ is given by

RσRτ=Rτ∘σ,

with 𝜎 applied before Template:Tau in the composed permutation. This happens because we must post-multiply to avoid inversions under the row-based option, so we would post-multiply first by Rσ and then by Rτ.

Some people, when applying a function to an argument, write the function after the argument (postfix notation), rather than before it. When doing linear algebra, they work with linear spaces of row vectors, and they apply a linear map to an argument by using the map's matrix to post-multiply the argument's row vector. They often use a left-to-right composition operator, which we here denote using a semicolon; so the composition σ;τ is defined either by

(σ;τ)(k)=τ(σ(k)),

or, more elegantly, by

(k)(σ;τ)=((k)σ)τ,

with 𝜎 applied first. That notation gives us a simpler rule for multiplying row-based permutation matrices:

RσRτ=Rσ;τ.

## Matrix group

When π is the identity permutation, which has π(i)=i for all i, both Cπ and Rπ are the identity matrix.

There are n! permutation matrices, since there are n! permutations and the map C:π↦Cπ is a one-to-one correspondence between permutations and permutation matrices. (The map R is another such correspondence.) By the formulas above, those n × n permutation matrices form a group of order n! under matrix multiplication, with the identity matrix as its identity element, a group that we denote 𝒫n. The group 𝒫n is a subgroup of the general linear group GLn(ℝ) of invertible n × n matrices of real numbers. Indeed, for any field F, the group 𝒫n is also a subgroup of the group GLn(F), where the matrix entries belong to F. (Every field contains 0 and 1 with 0+0=0, 0+1=1, 0*0=0, 0*1=0, and 1*1=1; and that's all we need to multiply permutation matrices. Different fields disagree about whether 1+1=0, but that sum doesn't arise.)

Let Sn<- denote the symmetric group, or group of permutations, on {1,2,...,n} where the group operation is the standard, right-to-left composition "∘"; and let Sn-> denote the opposite group, which uses the left-to-right composition ";". The map C:Sn<-->GLn(ℝ) that takes π to its column-based matrix Cπ is a faithful representation, and similarly for the map R:Sn->->GLn(ℝ) that takes π to Rπ.

## Doubly stochastic matrices

Every permutation matrix is doubly stochastic. The set of all doubly stochastic matrices is called the Birkhoff polytope, and the permutation matrices play a special role in that polytope. The Birkhoff–von Neumann theorem says that every doubly stochastic real matrix is a convex combination of permutation matrices of the same order, with the permutation matrices being precisely the extreme points (the vertices) of the Birkhoff polytope. The Birkhoff polytope is thus the convex hull of the permutation matrices.[5]

## Linear-algebraic properties

Just as each permutation is associated with two permutation matrices, each permutation matrix is associated with two permutations, as we can see by relabeling the example in the big square above starting with the matrix P at the upper right:

ρP:(12343241)⟷P:(0010010000011000)↕↕P−1:(0001010010000010)⟷κP:(12344213)

So we are here denoting the inverse of C as κ and the inverse of R as ρ. We can then compute the linear-algebraic properties of P from some combinatorial properties that are shared by the two permutations κP and ρP=κP−1.

A point is fixed by κP just when it is fixed by ρP, and the trace of P is the number of such shared fixed points.[1]: 322 If the integer k is one of them, then the standard basis vector ek is an eigenvector of P.[1]: 118

To calculate the complex eigenvalues of P, write the permutation κP as a composition of disjoint cycles, say κP=c1c2⋯ct. (Permutations of disjoint subsets commute, so it doesn't matter here whether we are composing right-to-left or left-to-right.) For 1≤i≤t, let the length of the cycle ci be ℓi, and let Li be the set of complex solutions of xℓi=1, those solutions being the ℓith roots of unity. The multiset union of the Li is then the multiset of eigenvalues of P. Since writing ρP as a product of cycles would give the same number of cycles of the same lengths, analyzing ρp would give the same result. The multiplicity of any eigenvalue v is the number of i for which Li contains v.[6] (Since any permutation matrix is normal and any normal matrix is diagonalizable over the complex numbers,[1]: 259 the algebraic and geometric multiplicities of an eigenvalue v are the same.)

From group theory we know that any permutation may be written as a composition of transpositions. Therefore, any permutation matrix factors as a product of row-switching elementary matrices, each of which has determinant −1\. Thus, the determinant of the permutation matrix P is the sign of the permutation κP, which is also the sign of ρP.

## Restricted forms

* Costas array, a permutation matrix in which the displacement vectors between the entries are all distinct
* n-queens puzzle, a permutation matrix in which there is at most one entry in each diagonal and antidiagonal

## See also

* Alternating sign matrix
* Exchange matrix
* Generalized permutation matrix
* Rook polynomial
* Permanent

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Artin, Michael (1991). Algebra. Prentice Hall. pp. 24–26,118,259,322. ISBN 0-13-004763-5. OCLC 24364036.
2. ↑ Zavlanos, Michael M.; Pappas, George J. (November 2008). "A dynamical systems approach to weighted graph matching". Automatica 44 (11): 2817–2824. doi:10.1016/j.automatica.2008.04.009. https://www.sciencedirect.com/science/article/abs/pii/S0005109808002616. Retrieved 21 August 2022. "Let On denote the set of n×n orthogonal matrices and Nn denote the set of n×n element-wise non-negative matrices. Then, Pn=On∩Nn, where Pn is the set of n×n permutation matrices.".
3. ↑ This terminology is not standard. Most authors use just one of the two correspondences, choosing which to be consistent with their other conventions. For example, Artin uses the column-based correspondence. We have here invented two names in order to discuss both options.
4. ↑ Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). The Symmetries of Things. A K Peters/CRC Press. p. 179. doi:10.1201/b21368. ISBN 978-0-429-06306-0. OCLC 946786108. "A permutation—say, of the names of a number of people—can be thought of as moving either the names or the people. The alias viewpoint regards the permutation as assigning a new name or alias to each person (from the Latin alias = otherwise). Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin alibi = in another place.)"
5. ↑ Brualdi 2006, p. 19
6. ↑ Najnudel & Nikeghbali 2013, p. 4 harvnb error: no target: CITEREFNajnudelNikeghbali2013 (help)

* Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. https://archive.org/details/combinatorialmat0000brua.
* Najnudel, Joseph (2013), "The Distribution of Eigenvalues of Randomized Permutation Matrices", Annales de l'Institut Fourier 63 (3): 773–838, doi:10.5802/aif.2777, Bibcode: 2010arXiv1005.0402N, http://www.numdam.org/item/AIF_2013__63_3_773_0/

* v
* t
* e

Matrix classes

Explicitly constrained entries|

* (0,1)
* Alternant
* Anti-diagonal
* Anti-Hermitian
* Anti-symmetric
* Arrowhead
* Band
* Bidiagonal
* Binary
* Bisymmetric
* Block-diagonal
* Block
* Block tridiagonal
* Boolean
* Cauchy
* Centrosymmetric
* Conference
* Complex Hadamard
* Copositive
* Diagonally dominant
* Diagonal
* Discrete Fourier Transform
* Elementary
* Equivalent
* Frobenius
* Generalized permutation
* Hadamard
* Hankel
* Hermitian
* Hessenberg
* Hollow
* Integer
* Logical
* Markov
* Metzler
* Monomial
* Moore
* Nonnegative
* Partitioned
* Parisi
* Pentadiagonal
* Permutation
* Persymmetric
* Polynomial
* Positive
* Quaternionic
* Sign
* Signature
* Skew-Hermitian
* Skew-symmetric
* Skyline
* Sparse
* Sylvester
* Symmetric
* Toeplitz
* Triangular
* Tridiagonal
* Unitary
* Vandermonde
* Walsh
* Z

Constant|

* Exchange
* Hilbert
* Identity
* Lehmer
* Of ones
* Pascal
* Pauli
* Redheffer
* Shift
* Zero

Conditions on eigenvalues or eigenvectors|

* Companion
* Convergent
* Defective
* Diagonalizable
* Hurwitz
* Positive-definite
* Stability
* Stieltjes

Satisfying conditions on products or inverses|

* Congruent
* Idempotent or Projection
* Invertible
* Involutory
* Nilpotent
* Normal
* Orthogonal
* Orthonormal
* Singular
* Unimodular
* Unipotent
* Totally unimodular
* Weighing

With specific applications|

* Adjugate
* Alternating sign
* Augmented
* Bézout
* Carleman
* Cartan
* Circulant
* Cofactor
* Commutation
* Confusion
* Coxeter
* Derogatory
* Distance
* Duplication
* Elimination
* Euclidean distance
* Fundamental (linear differential equation)
* Generator
* Gramian
* Hessian
* Householder
* Jacobian
* Moment
* Payoff
* Pick
* Random
* Rotation
* Seifert
* Shear
* Similarity
* Symplectic
* Totally positive
* Transformation
* Wedderburn
* X–Y–Z

Used in statistics|

* Bernoulli
* Centering
* Correlation
* Covariance
* Design
* Dispersion
* Doubly stochastic
* Fisher information
* Hat
* Precision
* Stochastic
* Transition

Used in graph theory|

* Adjacency
* Biadjacency
* Degree
* Edmonds
* Incidence
* Laplacian
* Seidel adjacency
* Skew-adjacency
* Tutte

Used in science and engineering|

* Cabibbo–Kobayashi–Maskawa
* Density
* Fundamental (computer vision)
* Fuzzy associative
* Gamma
* Gell-Mann
* Hamiltonian
* Irregular
* Overlap
* S
* State transition
* Substitution
* Z (chemistry)

Related terms|

* Jordan canonical form
* Linear independence
* Matrix exponential
* Matrix representation of conic sections
* Perfect matrix
* Pseudoinverse
* Quaternionic matrix
* Row echelon form
* Wronskian

* List of matrices
* Category:Matrices

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Permutation matrix. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Permutation_matrix&oldid=4154897"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template