[proofplan] We define the permutation matrix by its action on the standard basis of $k^n$. This action sends a basis to a basis, so each $P_\sigma$ is invertible and has inverse $P_{\sigma^{-1}}$. We then verify the homomorphism identity on every standard basis vector, which determines equality of linear maps. Finally, injectivity follows because $P_\sigma e_i=e_{\sigma(i)}$ records the value of $\sigma$ on each element of $\{1,\dots,n\}$. [/proofplan]

[step:Define the linear map determined by a permutation of the standard basis] Let $E=\{e_1,\dots,e_n\}$ denote the standard ordered basis of $k^n$. For each $\sigma\in S_n$, define the $k$-[linear map](/page/Linear%20Map) \begin{align*} P_\sigma:k^n\to k^n \end{align*} to be the unique linear map satisfying \begin{align*} P_\sigma e_i=e_{\sigma(i)} \end{align*} for every $i\in\{1,\dots,n\}$. Equivalently, the matrix entries of $P_\sigma$ in the standard basis are given by \begin{align*} (P_\sigma)_{ji}=1 \text{ if } j=\sigma(i), \qquad (P_\sigma)_{ji}=0 \text{ if } j\ne \sigma(i). \end{align*} Thus $P_\sigma$ is the permutation matrix associated to $\sigma$ under the convention $P_\sigma e_i=e_{\sigma(i)}$. [/step]

[step:Show each permutation matrix is invertible]Fix $\sigma\in S_n$. Since $\sigma$ is a bijection of $\{1,\dots,n\}$, the list \begin{align*} (e_{\sigma(1)},\dots,e_{\sigma(n)}) \end{align*} is a reordering of the standard ordered basis of $k^n$, hence is again a basis of $k^n$. Therefore $P_\sigma$ sends a basis of $k^n$ to a basis of $k^n$, so $P_\sigma$ is an invertible $k$-linear map. More explicitly, for every $i\in\{1,\dots,n\}$, \begin{align*} P_\sigma P_{\sigma^{-1}} e_i=P_\sigma e_{\sigma^{-1}(i)}=e_i \end{align*} and \begin{align*} P_{\sigma^{-1}}P_\sigma e_i=P_{\sigma^{-1}}e_{\sigma(i)}=e_i. \end{align*} Let $I_n:k^n\to k^n$ denote the identity map. Since two linear maps $k^n\to k^n$ that agree on the standard basis agree everywhere, we have \begin{align*} P_\sigma P_{\sigma^{-1}}=I_n \end{align*} and \begin{align*} P_{\sigma^{-1}}P_\sigma=I_n. \end{align*} Thus $P_\sigma\in GL_n(k)$ and $P_\sigma^{-1}=P_{\sigma^{-1}}$.[/step]

[guided]Fix $\sigma\in S_n$. The point of introducing $P_\sigma$ through the formula $P_\sigma e_i=e_{\sigma(i)}$ is that invertibility becomes a basis statement. Because $\sigma$ is a permutation, the vectors \begin{align*} e_{\sigma(1)},\dots,e_{\sigma(n)} \end{align*} are precisely the standard basis vectors $e_1,\dots,e_n$ in a different order. Hence they form a basis of $k^n$. A linear map that sends a basis to a basis is invertible, so $P_\sigma$ is invertible. We can also identify the inverse directly, which is useful for seeing that the image lies in $GL_n(k)$. The candidate inverse is $P_{\sigma^{-1}}$, since $\sigma^{-1}$ undoes the permutation $\sigma$. For every $i\in\{1,\dots,n\}$, \begin{align*} P_\sigma P_{\sigma^{-1}} e_i=P_\sigma e_{\sigma^{-1}(i)}=e_{\sigma(\sigma^{-1}(i))}=e_i. \end{align*} Similarly, \begin{align*} P_{\sigma^{-1}}P_\sigma e_i=P_{\sigma^{-1}}e_{\sigma(i)}=e_{\sigma^{-1}(\sigma(i))}=e_i. \end{align*} Both composites agree with the identity map $I_n:k^n\to k^n$ on every standard basis vector. Since a linear map out of $k^n$ is determined by its values on the standard basis, the two identities \begin{align*} P_\sigma P_{\sigma^{-1}}=I_n \end{align*} and \begin{align*} P_{\sigma^{-1}}P_\sigma=I_n \end{align*} follow. Therefore $P_\sigma\in GL_n(k)$ and its inverse is $P_{\sigma^{-1}}$.[/guided]

[step:Verify multiplication agrees with composition of permutations] Let $\sigma,\tau\in S_n$. The product $\sigma\tau$ denotes the composite permutation $\sigma\circ\tau$, so \begin{align*} (\sigma\tau)(i)=\sigma(\tau(i)) \end{align*} for every $i\in\{1,\dots,n\}$. For each standard basis vector $e_i\in k^n$, \begin{align*} P_\sigma P_\tau e_i=P_\sigma e_{\tau(i)}=e_{\sigma(\tau(i))}=e_{(\sigma\tau)(i)}=P_{\sigma\tau}e_i. \end{align*} Again, equality on the standard basis implies equality of linear maps. Hence \begin{align*} P_\sigma P_\tau=P_{\sigma\tau}. \end{align*} Thus the map \begin{align*} \rho:S_n\to GL_n(k) \end{align*} defined by $\rho(\sigma)=P_\sigma$ satisfies \begin{align*} \rho(\sigma\tau)=\rho(\sigma)\rho(\tau) \end{align*} for all $\sigma,\tau\in S_n$, so $\rho$ is a [group homomorphism](/page/Group%20Homomorphism). [/step]

[step:Recover the permutation from its permutation matrix] Suppose $\sigma,\tau\in S_n$ and $\rho(\sigma)=\rho(\tau)$. Then $P_\sigma=P_\tau$ as linear maps $k^n\to k^n$. For every $i\in\{1,\dots,n\}$, applying both maps to $e_i$ gives \begin{align*} e_{\sigma(i)}=P_\sigma e_i=P_\tau e_i=e_{\tau(i)}. \end{align*} The standard basis vectors are distinct, so $e_{\sigma(i)}=e_{\tau(i)}$ implies $\sigma(i)=\tau(i)$. Since this holds for every $i\in\{1,\dots,n\}$, the permutations $\sigma$ and $\tau$ are equal. Therefore $\rho$ is injective. Combining the homomorphism property with injectivity, $\rho:S_n\to GL_n(k)$ is an injective group homomorphism. [/step]