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: ${\displaystyle P^{-1}=P^{\mathsf {T}}}$. Indeed, permutation matrices can be characterized as the orthogonal matrices whose entries are all non-negative.

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:

The row-based correspondence takes the permutation π to the matrix ${\displaystyle R_{\pi }}$ at the upper right. The first row of ${\displaystyle R_{\pi }}$ has its 1 in the third column because ${\displaystyle \pi (1)=3}$. More generally, we have ${\displaystyle R_{\pi }=(r_{ij})}$ where ${\displaystyle r_{ij}=1}$ when ${\displaystyle j=\pi (i)}$ and ${\displaystyle r_{ij}=0}$ otherwise.

The column-based correspondence takes π to the matrix ${\displaystyle C_{\pi }}$ at the lower left. The first column of ${\displaystyle C_{\pi }}$ has its 1 in the third row because ${\displaystyle \pi (1)=3}$. More generally, we have ${\displaystyle C_{\pi }=(c_{ij})}$ where ${\displaystyle c_{ij}}$ is 1 when ${\displaystyle i=\pi (j)}$ and 0 otherwise. Since the two recipes differ only by swapping i with j, the matrix ${\displaystyle C_{\pi }}$ is the transpose of ${\displaystyle R_{\pi }}$; and, since ${\displaystyle R_{\pi }}$ is a permutation matrix, we have ${\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}$. Tracing the other two sides of the big square, we have ${\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}$ and ${\displaystyle C_{\pi ^{-1}}=R_{\pi }}$.

Multiplying a matrix M by either ${\displaystyle R_{\pi }}$ or ${\displaystyle C_{\pi }}$ on either the left or the right will permute either the rows or columns of M by either π or π⁻¹. The details are a bit tricky.

To begin with, when we permute the entries of a vector ${\displaystyle (v_{1},\ldots ,v_{n})}$ by some permutation π, we move the ${\displaystyle i^{\text{th}}}$ entry ${\displaystyle v_{i}}$ of the input vector into the ${\displaystyle \pi (i)^{\text{th}}}$ slot of the output vector. Which entry then ends up in, say, the first slot of the output? Answer: The entry ${\displaystyle v_{j}}$ for which ${\displaystyle \pi (j)=1}$, and hence ${\displaystyle j=\pi ^{-1}(1)}$. Arguing similarly about each of the slots, we find that the output vector is

even though we are permuting by ${\displaystyle \pi }$, not by ${\displaystyle \pi ^{-1}}$. Thus, in order to permute the entries by ${\displaystyle \pi }$, we must permute the indices by ${\displaystyle \pi ^{-1}}$. (Permuting the entries by ${\displaystyle \pi }$ is sometimes called taking the alibi viewpoint, while permuting the indices by ${\displaystyle \pi }$ would take the alias viewpoint.)