\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Matrix Transpose
Real Matrix Inverses
Needed by:
Index Matrices
Lower Upper Triangular Factorizations
Matrix Similarity
Sheet PDF
Graph PDF

Permutation Matrices


Can permuting the rows or columns of a matrix be represented by matrix multiplication?


Let $\sigma : \upto{n} \to \upto{n}$ be a permutation of $n$. The permutation matrix of $\sigma $ is the matrix $P$ defined by $P_{ij} = 1$ if $\sigma (i) = j$ and 0 otherwise. This is sometimes called the column representation (in contrast to the row representation, in which $P_{ij} = 1$ if $\sigma (j) = i$.

Let $A \in \R ^{n \times n}$. Then pre-multipying $A$ by $P$ permutes the rows of $A$. In other words $PA$ has the same rows as $A$ but permuted according to $\sigma $. Similarly, post-multiplying by $P$ permutes the columns of $A$. In other words, $AP$ has the same columns as $A$ but permuted according to $\sigma $. Clearly, we can also speak of permuting the components of a vector.


Let $\pi , \sigma \in S_n$ with corresponding permutation matrices $P_\sigma $ and $P_\pi $. Then $P_{\pi }P_{\sigma }A$ has the same rows as $A$ but permuted by $\pi \sigma $. Likewise, $AP_{\pi }P_{\sigma }$ has the same columns as $A$ but permuted by $\pi \sigma $. Clearly, the identity permutation on $\upto{n}$ is the identity $I \in \R ^{n \times n}$.


It is clear from the definition that $P_{\sigma }^{-1} = P_{\sigma ^{-1}}$ and so if $P$ is a permutation matrix then $P^{-1}$ is $P^\top $.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view