1.7: Permutation Matrices

Last updated
Save as PDF

Page ID: 96142

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

View Permutation Matrices on YouTube

A permutation matrix is another type of orthogonal matrix. When multiplied on the left, an \(n\)-by-\(n\) permutation matrix reorders the rows of an \(n\)-by-\(n\) matrix, and when multiplied on the right, reorders the columns. For example, let the string \(12\) represent the order of the rows (columns) of a two-by-two matrix. Then the permutations of the rows (columns) are given by \(12\) and \(21\). The first permutation is no permutation at all, and the corresponding permutation matrix is simply the identity matrix. The second permutation of the rows (columns) is achieved by

\[\left(\begin{array}{cc}0&1\\1&0\end{array}\right)\left(\begin{array}{cc}a&b\\c&d\end{array}\right)=\left(\begin{array}{cc}c&d\\a&b\end{array}\right),\quad\left(\begin{array}{cc}a&b\\c&d\end{array}\right)\left(\begin{array}{cc}0&1\\1&0\end{array}\right)=\left(\begin{array}{cc}b&a\\d&c\end{array}\right).\nonumber \]

The rows (columns) of a \(3\)-by-\(3\) matrix has \(3! = 6\) possible permutations, namely \(123, 132, 213, 231, 312, 321\). For example, the row permutation \(312\) is obtained by

\[\left(\begin{array}{ccc}0&0&1\\1&0&0\\0&1&0\end{array}\right)\left(\begin{array}{ccc}a&b&c\\d&e&f\\g&h&i\end{array}\right)=\left(\begin{array}{ccc}g&h&i\\a&b&c\\d&e&f\end{array}\right).\nonumber \]

Evidently, the permutation matrix is obtained by permutating the corresponding rows of the identity matrix. Because the columns and rows of the identity matrix are orthonormal, the permutation matrix is an orthogonal matrix.