# 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.

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.)

• Thanks. That makes sense as well. – letsmakemuffinstogether Oct 1 '15 at 18:58
• There is another component to the question: show that $P: S_n \rightarrow M_n{\mathbb{R}}$ has $P(\sigma\tau)=P(\sigma)P(\tau)$. Any hints on how to do this? I think I see how it's done but I'm having troubles putting it into words and using summation notation to multiply the matrices $P(\sigma)$ and $P(\tau)$. – letsmakemuffinstogether Oct 1 '15 at 20:07
• @letsmakemuffinstogether that is my proof that $\Phi$ is a homomorphism. – David Hill Oct 1 '15 at 21:46

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.