Permutation Matrix
Definition 1
$P \in \mathbb{R}^{n \times n}$ in which only one component in each row is $1$ and the rest are $0$ is called a Permutation Matrix.
Basic Properties
Orthogonality
All permutation matrices are orthogonal matrices: $$P^{-1} = P^{T}$$
Sparseness
For sufficiently large $n$, $P \in \mathbb{R}^{n \times n}$ is a sparse matrix.
Explanation
The Permutation Matrix gives a permutation of rows and columns through matrix multiplication. The following example shows that if it is multiplied on the left, it gives a row permutation, and if it is multiplied on the right, it gives a column permutation. $$ \begin{align*} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = & \begin{bmatrix} a_{21} & a_{22} & a_{23} \\ a_{11} & a_{12} & a_{13} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \\ \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} = & \begin{bmatrix} a_{12} & a_{11} & a_{13} \\ a_{22} & a_{21} & a_{23} \\ a_{32} & a_{31} & a_{33} \end{bmatrix} \end{align*} $$