[proofplan] We prove orthogonality by computing the inner products of the columns of $P$. The defining property of a permutation matrix says that each column is one of the standard basis vectors of $\mathbb{R}^n$, and that distinct columns are distinct standard basis vectors. Therefore the columns form an orthonormal list, which is exactly the statement that $P^\top P = I_n$. [/proofplan]

[step:Write the columns of the permutation matrix as distinct standard basis vectors] For each $k \in \{1,\dots,n\}$, let $p_k \in \mathbb{R}^n$ denote the $k$th column of $P$. Since $P$ is a permutation matrix, every column of $P$ has exactly one entry equal to $1$ and all other entries equal to $0$, and no two columns have their $1$ in the same row. Let $e_1,\dots,e_n \in \mathbb{R}^n$ denote the standard basis vectors, where $e_r$ has $r$th component equal to $1$ and all other components equal to $0$. Thus, for each $k \in \{1,\dots,n\}$, there exists a unique index $\sigma(k) \in \{1,\dots,n\}$ such that \begin{align*} p_k = e_{\sigma(k)}. \end{align*} The condition that no two columns have their $1$ in the same row means that the map \begin{align*} \sigma: \{1,\dots,n\} &\to \{1,\dots,n\} \end{align*} is injective. [/step]

[step:Compute the inner products of the columns]Let $i,j \in \{1,\dots,n\}$. Since $p_i = e_{\sigma(i)}$ and $p_j = e_{\sigma(j)}$, the Euclidean [inner product](/page/Inner%20Product) of the two columns is \begin{align*} p_i^\top p_j = e_{\sigma(i)}^\top e_{\sigma(j)}. \end{align*} For standard basis vectors, the inner product satisfies \begin{align*} e_r^\top e_s = \begin{cases} 1, & r=s, \end{align*} \begin{align*} 0, & r \neq s. \end{cases} \end{align*} Since $\sigma$ is injective, $\sigma(i)=\sigma(j)$ holds iff $i=j$. Therefore \begin{align*} p_i^\top p_j = \begin{cases} 1, & i=j, \end{align*} \begin{align*} 0, & i \neq j. \end{cases} \end{align*}[/step]

[guided]We want to prove $P^\top P = I_n$, and the entries of $P^\top P$ are column inner products. That is why we name the columns. For each $k \in \{1,\dots,n\}$, let $p_k \in \mathbb{R}^n$ be the $k$th column of $P$. Because $P$ is a permutation matrix, each column has exactly one entry equal to $1$ and every other entry equal to $0$. Hence each column is a standard basis vector. Let $e_1,\dots,e_n \in \mathbb{R}^n$ denote the standard basis vectors. For every $k \in \{1,\dots,n\}$, define $\sigma(k) \in \{1,\dots,n\}$ to be the row index where the unique $1$ in the $k$th column occurs. Then \begin{align*} p_k = e_{\sigma(k)}. \end{align*} The row condition in the definition of a permutation matrix says that no two columns have their $1$ in the same row. Therefore if $\sigma(i)=\sigma(j)$, then the $i$th and $j$th columns have their unique $1$ in the same row, so $i=j$. Thus $\sigma$ is injective. Now let $i,j \in \{1,\dots,n\}$. Using the column description, we compute \begin{align*} p_i^\top p_j = e_{\sigma(i)}^\top e_{\sigma(j)}. \end{align*} The standard basis vectors are orthonormal, so \begin{align*} e_r^\top e_s = \begin{cases} 1, & r=s, \end{align*} \begin{align*} 0, & r \neq s. \end{cases} \end{align*} Applying this with $r=\sigma(i)$ and $s=\sigma(j)$, and using the injectivity of $\sigma$, gives \begin{align*} p_i^\top p_j = \begin{cases} 1, & i=j, \end{align*} \begin{align*} 0, & i \neq j. \end{cases} \end{align*} Thus the columns of $P$ are orthonormal.[/guided]

[step:Identify the Gram matrix with the identity matrix] For each $i,j \in \{1,\dots,n\}$, the $(i,j)$-entry of $P^\top P$ is the inner product of the $i$th and $j$th columns of $P$: \begin{align*} (P^\top P)_{ij} = p_i^\top p_j. \end{align*} By the preceding computation, \begin{align*} (P^\top P)_{ij} = \begin{cases} 1, & i=j, \end{align*} \begin{align*} 0, & i \neq j. \end{cases} \end{align*} These are exactly the entries of the identity matrix $I_n$. Hence \begin{align*} P^\top P = I_n. \end{align*} [/step]

[step:Conclude that the permutation matrix belongs to the orthogonal group] By definition, \begin{align*} O(n) = \{Q \in \mathbb{R}^{n \times n} : Q^\top Q = I_n\}. \end{align*} Since $P \in \mathbb{R}^{n \times n}$ and $P^\top P = I_n$, it follows that $P \in O(n)$. This proves the theorem. [/step]