Перестановки можно представить в виде квадратной бинарной матрицы.

Матрица перестановки $\sigma$ — такая матрица $\mat \sigma$, в которой на $i$-й строке цифра $1$ стоит только в столбце $\sigma(i)$, а остальные элементы равны $0$.

Например,

В матрице перестановки в каждой строке и в каждом столбце ровно одна $1$.

У единичной перестановки матрица равна единичной матрице, $\mat \1 = \1$.

Матрицы перестановок можно легко использовать для выражения операций с перестановками. В частности,

При этом $\mat \sigma \cdot (\mat \sigma)^\T = (\mat \sigma)^\T \cdot \mat \sigma = \1$, поэтому матрицы перестановок ортогональны, то есть $(\mat \sigma)^{-1} = (\mat \sigma)^\T$.

Еще важное свойство: определитель матрицы перестановки равен четности этой перестановки

Следующее свойство открывает большое количество возможностей в матричных вычислениях. Рассмотрим пока матрицу $P_{ij} = \mat (ij)$ — матрицу транспозиции элементов $i$ и $j$.

При перемножении $P_{ij}$ на любую матрицу $A$, у $A$ меняются местами строки $i$ и $j$. А если умножить $A$ на $P_{ij}$, то в матрице $A$ поменяются местами столбцы $i$ и $j$.

Мы знаем, что любую перестановку порядка $n$ можно разложить в композицию $n-1$ транспозиции. Значит, можно добиться любой перестановки строк и столбцов матрицы $A$ с помощью двух матриц перестановок $P$ и $Q$, просто посчитав $P \cdot A \cdot Q$.