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

  • $\begingroup$ Thanks. That makes sense as well. $\endgroup$ – letsmakemuffinstogether Oct 1 '15 at 18:58
  • $\begingroup$ 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)$. $\endgroup$ – letsmakemuffinstogether Oct 1 '15 at 20:07
  • $\begingroup$ @letsmakemuffinstogether that is my proof that $\Phi$ is a homomorphism. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.