I am trying to show that the group of $n\times n$ permutation matrices is isomorphic to $S_n$, the symmetric group on $n$ elements. It seems clear to me that they wold be isomorphic - we can associate each row with a number, and then each permutation matrix would correspond to some rearrangement of $n$ letters. However, I'm having difficulty coming up with a homomorphism.

  • $\begingroup$ There is such a thing as a permutation matrix, which has exactly the properties you want. $\endgroup$ – hardmath Sep 15 '17 at 0:52
  • $\begingroup$ I know that. I'm trying to prove that the group of permutation matrices is isomorphic to Sn. $\endgroup$ – confusedmath Sep 15 '17 at 0:53
  • $\begingroup$ So, first thing is to check out the definition of a permutation matrix, and then verify that as we would expect, they form a group with respect to matrix multiplication. The correspondance between permutations and permutation matrices is fairly straightforward (given how the latter are defined). $\endgroup$ – hardmath Sep 15 '17 at 0:56

The homomorphism is indeed a rather trivial one.

Consider the following map $\psi : S_n \to \mathbb P_{n \times n}$, where the latter is the set of permutation matrices of order $n$. This map is defined as follows : given $\phi \in S_n$, the $i$th column of $\psi(\phi)$ is the column vector with a $1$ in the $\phi(i)$th position, and $0$ elsewhere.

It is easy to see that $\psi(\phi)$ is indeed a permutation matrix, since a $1$ occurs in any position if and only if that position is described by $(\phi(i),i)$, for any $1 \leq i \leq n$.

This map is clearly multiplicative. The proof is awkward to write, but easy to understand. We must prove that $\psi(\alpha \circ \beta)=\psi(\alpha)\psi(\beta)$ for any permutations $\alpha,\beta$.

Note that since these are matrices, it's enough to show that each corresponding entry is equal. So let us take the entry $(i,j)$ of each matrix.

Then : $\psi(\alpha \circ \beta)_{ij} = 1$ if and only if $i = \alpha \circ \beta(j)$, as I said earlier. Otherwise, it is zero.

Note that by ordinary matrix multiplication, $(\psi(\alpha)\psi(\beta))_{ij} = \sum_{k=1}^n \psi(\alpha)_{ik}\psi(\beta)_{kj}$.

Now, we know that $\psi(\alpha)_{ik} = 1$ only when $i = \alpha(k)$. Similarly, $\psi(\beta)_{kj} = 1$ only when $k = \beta(j)$. Hence, their product is one precisely when both of these happen : $i = \alpha(k),k = \beta(j)$. If both these don't happen simultaneously, then whenever one of $\psi(\alpha)_{ik},\psi(\beta)_{kj}$ is one the other will be zero, so the whole sum will be zero. However, this is the same as saying that the sum is one exactly when $i = \alpha \circ\beta(j)$. This description matches with the decription given for $\psi(\alpha \circ \beta)_{ij}$ given earlier.

Hence, entry by entry these matrices are the same. Therefore the matrices are the same, and hence $\psi$ is a homomorphism between the two spaces, an isomorphism as it has trivial kernel and the sets are of the same cardinality.


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.