# Permutation matrix

In mathematics, in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry 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 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.

## Properties

Given two permutations π and σ of m elements and the corresponding permutation matrices Pπ and Pσ

$P_{\sigma }P_{\pi }=P_{\pi \,\circ \,\sigma }$ This somewhat unfortunate rule is a consequence of the definitions of multiplication of permutations (composition of bijections) and of matrices, and of the choice of using the vectors ${\mathbf {e} }_{\pi (i)}$ as rows of the permutation matrix; if one had used columns instead then the product above would have been equal to $P_{\sigma \,\circ \,\pi }$ with the permutations in their original order.

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}}.$ $g'_{i}=g_{\pi (i)}\,$ for all i, then

$P_{\sigma }(P_{\pi }({\mathbf {g} }))=P_{\sigma }({\mathbf {g} }')={\begin{bmatrix}g'_{\sigma (1)}\\g'_{\sigma (2)}\\\vdots \\g'_{\sigma (n)}\end{bmatrix}}={\begin{bmatrix}g_{\pi (\sigma (1))}\\g_{\pi (\sigma (2))}\\\vdots \\g_{\pi (\sigma (n))}\end{bmatrix}}.$ ${\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}}$ 