Establishing a bijection between permutations and permutation matrices. I am trying to prove the following: 
Given $\sigma \in S_n$ let $P(\sigma)$ be the matrix with $(P(\sigma))_{i,j} = \delta_{i,\sigma(j)}$. Show that $P$ is a bijection between $S_n$ and the set of permutation matrices of size $n$ $-$ where $\delta_{i,j}$ is the Kronecker delta which equals 1 if $i=j$ and 0 otherwise.
As I understand the question, the question is saying that for each row $i$ and column $j$ we have that position $i,j$ equals 1 iff $\sigma(j) = i$.
So then it seems then that for any $\sigma$ such that $\sigma(i) = i$, we would have $P(\sigma)$ as the identity matrix with strictly 1's from the top-left to the bottom-right and zeros everywhere else.
On the other hand, suppose that we have $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 4$, $\sigma(4) = 1$; then we'd have the following matrix
\begin{bmatrix}0 & 0 & 0& 1\\1 & 0 & 0 & 0\\0 & 1  & 0 & 0 \\ 0 & 0 & 1 & 0\end{bmatrix}
Is this a correct understanding?
If so, then here is my attempted proof of the question mentioned above:
$\bf{Injectivity}$: Assuming $\sigma, \tau \in S_n$ and $P(\sigma) = P(\tau)$ then whenever $\sigma(j) = i$ we have the jth-column and i-th row of the matrix $p$ as a 1 and similarly for $\tau(j) = i$. So $\tau = \sigma$ and we are done.
$\bf{Surjectivity}$: Let $P$ be some $n \times n$ permutation matrix. Then each row and column will have exactly one 1 with zeros everywhere else. Then for every i,j position which has a 1 in it, we can choose a permutation $\sigma$ such that $\sigma(j) = i$ for some $\sigma$ which is an n-cycle and we are done.
Is this proof sound? Thank you in advance.
 A: You're proof is fine, but more can be said. The set $P_n$ of $n\times n$ permutation matrices is a group under matrix multiplication, and as such $S_n\cong P_n$. Indeed, let $\{v_1,\ldots,v_n\}$ be a basis for $\mathbb{R}^n$ (you can take any field here, but nevermind). For each $\sigma\in S_n$, we define a linear transformation $P_\sigma$ by $P_\sigma(v_i)=v_{\sigma(i)}$, whose matrix in the basis $\{v_1,\ldots,v_n\}$ is $P(\sigma)$.
Let $\Phi:S_n\longrightarrow P_n$ be the map $\Phi(\sigma)=P_\sigma$. This map is a homomorphism since
$$P_\sigma P_\tau(v_i)=P_\sigma(v_{\tau(i)})=v_{\sigma(\tau(i))}=v_{\sigma\tau(i)}=P_{\sigma\tau}(v_i).$$
The map is injective: if $P_\tau v_i=v_{\tau(i)}=v_i$ for all $i$, then $\tau(i)=i$ for all $i$ and $\tau=1$. 
Finally, the map is surjective because $|P_n|=n!$ (permutation matrices are allowed one nonzero entry in every row and column. Starting with the leftmost column, you have $n$ choices for where to place a nonzero entry; having made this choice you have occupied a row, so going to the next column you have $n-1$ choices for where to place a nonzero entry, etc.) 
A: It can also be shown that the map $\Phi: \mathcal{S}_n \longrightarrow \mathcal{P}_n$ defined by $\sigma \in \mathcal{S}_n \longmapsto P_\sigma \in \mathcal{P}_n$ is a homomorphism and hence an isomorphism. 
If $\sigma$, $\gamma \in \mathcal{S}_n$ and $1 \le i,j \le n$, then 
$$
\left[ P_\sigma P_\gamma\right]_{ij} 
= \sum_{k=1}^n \delta_{i,\sigma(k)} \delta_{k, \gamma(j)} 
= \delta_{i, \sigma(\gamma(j))}
= \left[ P_{\sigma \circ \gamma}\right]_{ij},
$$
i.e., $P_{\sigma} P_{\gamma} = P_{\sigma \circ \gamma}$.
Thus, 
\begin{align}
\Phi(\sigma\circ\gamma) = P_{\sigma \circ \gamma} = P_\sigma P_\gamma = \Phi(\sigma)\Phi(\gamma) 
\end{align}
as desired.
