Permutation matrix

Matrices describing the permutations of 3 elements
The product of two permutation matrices is a permutation matrix as well.

These are the positions of the six matrices:

(They are also permutation matrices.)

In mathematics, in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix represents a specific permutation of m elements and, when used to multiply another matrix, can produce that permutation in the rows or columns of the other matrix.

Definition

Given a permutation π of m elements,

\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace

given in two-line form by

{\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},

its permutation matrix acting on m-dimensional column vectors is the m × m matrix P_π whose entries are all 0 except that in row i, the entry π(i) equals 1. We may write

P_{\pi }={\begin{bmatrix}{\mathbf e}_{{\pi (1)}}\\{\mathbf e}_{{\pi (2)}}\\\vdots \\{\mathbf e}_{{\pi (m)}}\end{bmatrix}},

where ${\mathbf e}_{j}$ denotes a row vector of length m with 1 in the jth position and 0 in every other position.^[1]

Properties

Given two permutations π and σ of m elements, the corresponding permutation matrices P_π and P_σ which act on column vectors can be composed

P_{\sigma} P_{\pi} = P_{\sigma\,\circ\,\pi}.

However, note that if the corresponding permutation matrices are defined to act on row vectors, i.e., $[P_\pi]_{ij} = \delta_{i \pi(j)}$ where $\delta$ is the Kronecker delta, the rule is reversed

P_{\sigma} P_{\pi} = P_{\pi\,\circ\,\sigma}.

As permutation matrices are orthogonal matrices (i.e., $P_{{\pi }}P_{{\pi }}^{{T}}=I$ ), the inverse matrix exists and can be written as

P_{{\pi }}^{{-1}}=P_{{\pi ^{{-1}}}}=P_{{\pi }}^{{T}}.

Multiplying $P_{{\pi }}$ times a column vector g will permute the rows of the vector:

P_{\pi }{\mathbf {g}}={\begin{bmatrix}{\mathbf {e}}_{{\pi (1)}}\\{\mathbf {e}}_{{\pi (2)}}\\\vdots \\{\mathbf {e}}_{{\pi (n)}}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{{\pi (1)}}\\g_{{\pi (2)}}\\\vdots \\g_{{\pi (n)}}\end{bmatrix}}.

Multiplying a row vector h times $P_{{\pi }}$ will permute the columns of the vector by the inverse of $P_{{\pi }}$ :

{\mathbf {h}}P_{\pi }={\begin{bmatrix}h_{1}\;h_{2}\;\dots \;h_{n}\end{bmatrix}}{\begin{bmatrix}{\mathbf {e}}_{{\pi (1)}}\\{\mathbf {e}}_{{\pi (2)}}\\\vdots \\{\mathbf {e}}_{{\pi (n)}}\end{bmatrix}}={\begin{bmatrix}h_{{\pi ^{{-1}}(1)}}\;h_{{\pi ^{{-1}}(2)}}\;\dots \;h_{{\pi ^{{-1}}(n)}}\end{bmatrix}}

Again it can be checked that $({\mathbf {h}}P_{\sigma })P_{\pi }={\mathbf {h}}P_{{\pi \circ \sigma }}$ .

Notes

Let S_n denote the symmetric group, or group of permutations, on {1,2,...,n}. Since there are n! permutations, there are n! permutation matrices. By the formulas above, the n × n permutation matrices form a group under matrix multiplication with the identity matrix as the identity element.

If (1) denotes the identity permutation, then P₍₁₎ is the identity matrix.

One can view the permutation matrix of a permutation σ as the permutation σ of the rows of the identity matrix I, or as the permutation σ⁻¹ of the columns of I.

A permutation matrix is a doubly stochastic matrix. The Birkhoff–von Neumann theorem says that every doubly stochastic real matrix is a convex combination of permutation matrices of the same order and the permutation matrices are precisely the extreme points of the set of doubly stochastic matrices. That is, the Birkhoff polytope, the set of doubly stochastic matrices, is the convex hull of the set of permutation matrices.^[2]

The product PM, premultiplying a matrix M by a permutation matrix P, permutes the rows of M; row i moves to row π(i). Likewise, MP permutes the columns of M.

The map S_n → A ⊂ GL(n, Z₂) is a faithful representation. Thus, |A| = n!.

The trace of a permutation matrix is the number of fixed points of the permutation. If the permutation has fixed points, so it can be written in cycle form as π = (a₁)(a₂)...(a_k)σ where σ has no fixed points, then e_a₁,e_a₂,...,e_{a_k} are eigenvectors of the permutation matrix.

To calculate the eigenvalues of a permutation matrix $P_{\sigma }$ , write $\sigma$ as a product of cycles, say, $\sigma =C_{1}C_{2}\cdots C_{t}$ . Let the corresponding lengths of these cycles be $l_{1},l_{2}...l_{t}$ , and let $R_{i}(1\leq i\leq t)$ be the set of complex solutions of $x^{l_{i}}=1$ . The union of all $R_{i}$ s is the set of eigenvalues of the corresponding permutation matrix. The geometric multiplicity of each eigenvalue equals the number of $R_{i}$ s that contain it.^[3]

From group theory we know that any permutation may be written as a product of transpositions. Therefore, any permutation matrix P factors as a product of row-interchanging elementary matrices, each having determinant −1. Thus the determinant of a permutation matrix P is just the signature of the corresponding permutation.

Examples

Permutation of rows and columns

When a permutation matrix P is multiplied with a matrix M from the left (PM) it will permute the rows of M (here the elements of a column vector),
when P is multiplied with M from the right (MP) it will permute the columns of M (here the elements of a row vector):

P * (1,2,3,4)^T = (4,1,3,2)^T

(1,2,3,4) * P = (2,4,3,1)

Permutations of rows and columns are for example reflections (see below) and cyclic permutations (see cyclic permutation matrix).

reflections

(1,2,3,4) * P^T = (4,1,3,2)

P^T * (1,2,3,4)^T = (2,4,3,1)^T

These arrangements of matrices are reflections of those directly above.
This follows from the rule $\left(\mathbf {AB} \right)^{\mathrm {T} }=\mathbf {B} ^{\mathrm {T} }\mathbf {A} ^{\mathrm {T} }\,$ (Compare: Transpose)

Permutation of rows

The permutation matrix P_π corresponding to the permutation : $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},$ is

P_{\pi }={\begin{bmatrix}{\mathbf {e}}_{{\pi (1)}}\\{\mathbf {e}}_{{\pi (2)}}\\{\mathbf {e}}_{{\pi (3)}}\\{\mathbf {e}}_{{\pi (4)}}\\{\mathbf {e}}_{{\pi (5)}}\end{bmatrix}}={\begin{bmatrix}{\mathbf {e}}_{{1}}\\{\mathbf {e}}_{{4}}\\{\mathbf {e}}_{{2}}\\{\mathbf {e}}_{{5}}\\{\mathbf {e}}_{{3}}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.

Given a vector g,

P_{\pi }{\mathbf {g}}={\begin{bmatrix}{\mathbf {e}}_{{\pi (1)}}\\{\mathbf {e}}_{{\pi (2)}}\\{\mathbf {e}}_{{\pi (3)}}\\{\mathbf {e}}_{{\pi (4)}}\\{\mathbf {e}}_{{\pi (5)}}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.

Explanation

A permutation matrix will always be in the form

{\begin{bmatrix}{\mathbf {e}}_{{a_{1}}}\\{\mathbf {e}}_{{a_{2}}}\\\vdots \\{\mathbf {e}}_{{a_{j}}}\\\end{bmatrix}}

where e_{a_i} represents the ith basis vector (as a row) for R^j, and where

{\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}

is the permutation form of the permutation matrix.

Now, in performing matrix multiplication, one essentially forms the dot product of each row of the first matrix with each column of the second. In this instance, we will be forming the dot product of each row of this matrix with the vector of elements we want to permute. That is, for example, v= (g₀,...,g₅)^T,

e_{a_i}·v=g_{a_i}

So, the product of the permutation matrix with the vector v above, will be a vector in the form (g_a₁, g_a₂, ..., g_{a_j}), and that this then is a permutation of v since we have said that the permutation form is

{\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.

So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.

References

↑ Brualdi (2006) p.2
↑ Brualdi (2006) p.19
↑ J Najnudel, A Nikeghbali 2010 p.4

Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices (PDF)

This article is issued from Wikipedia - version of the 11/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.