# Subgroup of $GL_n$ isomorphic to $S_n$

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.

• There is such a thing as a permutation matrix, which has exactly the properties you want. – hardmath Sep 15 '17 at 0:52
• I know that. I'm trying to prove that the group of permutation matrices is isomorphic to Sn. – confusedmath Sep 15 '17 at 0:53
• 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). – 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.