Permutation matrix

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

=

P

T

{\displaystyle P^{-1}=P^{\mathsf {T}}}

. Indeed, permutation matrices can be characterized as the orthogonal matrices whose entries are all non-negative.

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:

π

:

(

1

2

3

4

3

2

4

1

)

⟷

R

π

:

(

0

0

1

0

0

1

0

0

0

0

0

1

1

0

0

0

)

↕

↕

C

π

:

(

0

0

0

1

0

1

0

0

1

0

0

0

0

0

1

0

)

⟷

π

−

1

:

(

1

2

3

4

4

2

1

3

)

{\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}

The row-based correspondence takes the permutation π to the matrix

R

π

{\displaystyle R_{\pi }}

at the upper right. The first row of

R

π

{\displaystyle R_{\pi }}

has its 1 in the third column because

π

(

1

)

=

3

{\displaystyle \pi (1)=3}

. More generally, we have

R

π

=

(

r

i

j

)

{\displaystyle R_{\pi }=(r_{ij})}

where

r

i

j

=

1

{\displaystyle r_{ij}=1}

when

j

=

π

(

i

)

{\displaystyle j=\pi (i)}

and

r

i

j

=

0

{\displaystyle r_{ij}=0}

otherwise.

The column-based correspondence takes π to the matrix

C

π

{\displaystyle C_{\pi }}

at the lower left. The first column of

C

π

{\displaystyle C_{\pi }}

has its 1 in the third row because

π

(

1

)

=

3

{\displaystyle \pi (1)=3}

.