# Proving Phi is a homomorphism

Fix a positive integer n.

For each $\sigma \in Sn$ define an n×n matrix,

$\phi(σ)$ by $\phi (\sigma)_{i,j}=\{1$ if $i = \sigma (j),$ $0$ if $i \neq \sigma (j) \}$

Assume that this matrix is invertible

Prove that $\phi : S_n \to GLn(\mathbb{R})$ is a homomorphism and find $ker \phi$

i cant seem to find agood way of doing this a friend of mine said since $S_n$ is a bijection that every row and colum must have exactly one entry that is a one and used this result to show its a homomorphism but im not sure this a valid approach.

I tried writing out $\phi (\sigma \tau ) = \phi (\sigma) \phi (\tau)$

where the RHS = $\sum_{k=0}^{n} \phi(\sigma)_{i,k} \phi(\tau)_{k,j}$ but im not sure how to justify what i need to do next and i have no clue what to do with the left hand side.

You do not need to assume that $\phi(\sigma)$ is invertible: it can be easily proven. Note that $\phi(\sigma)_{\sigma(i),i} = 1$ for all $i$, and zero for any other entry. So $\phi(\sigma)$ is a matrix whose columns are precisely the standard basis vectors in a different order. Hence $\phi(\sigma)$ has full rank and is invertible.

Note that $\phi(\sigma\tau)_{i,j} = 1$ exactly when $i = \sigma \tau(j)$, and zero otherwise.

Similarly, note that $(\phi(\sigma)\phi(\tau))_{i,j} = \sum_{k} \phi(\sigma)_{i,k}\phi(\tau)_{k,j}$. When is this equal to $1$? Note that each individual product $\phi(\sigma)_{i,k}\phi(\tau)_{k,j}$ is either zero or one, since the entries of $\phi(\xi)$ are either zero or one for any $\xi \in S_n$.

CLAIM : If $i = \sigma\tau(j)$, then this sum is one, otherwise it is zero.

Proof: Suppose $i = \sigma\tau(j)$. Note that if $k = \tau(j)$, then $i = \sigma(k)$, so $\phi(\sigma)_{i,k}\phi(\tau)_{k,j} = 1$. Furthermore, for any other $k'$, note that $k' \neq \sigma(j)$, so $\phi(\sigma)_{i,k'}\phi(\tau)_{k',j} = 0$, simply because the second term is zero. Hence, $\sum_{k} \phi(\sigma)_{i,k}\phi(\tau)_{k,j} = 1$.

Suppose now that the sum is one. Then, exactly one of the terms $\phi(\sigma)_{i,k}\phi(\tau)_{k,j}$ is one, since each term takes only value zero or one. Suppose that $\phi(\sigma)_{i,k}\phi(\tau)_{k,j} = 1$. Since both these terms have to be one, we see that $k = \tau(j)$ and $i = \sigma(k)$, so $i = \sigma\tau(j)$.

Hence, it follows that for all $i,j$, $\phi(\sigma\tau)_{i,j} = (\phi(\sigma)\phi(\tau))_{i,j}$. Hence, $\phi(\sigma\tau) = \phi(\sigma)\phi(\tau)$ as matrices, whence $\phi$ is a homomorphism.

Note that if $\phi(\sigma) = I$, then $\phi(\sigma)_{i,i} = 1$ for all $i$, so $\sigma(i) = i$ for all $i$. Therefore, $\sigma$ is the identity permutation. Hence, the kernel of $\phi$ is trivial, which indicates that $\phi$ is injective. The image of $\phi$ is called the set of permutation matrices.

• Took me ahwile to understand the last part about the $\ker \phi$ but very good explanation! Oct 14 '17 at 4:40
• You are welcome! Oct 14 '17 at 4:42