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.

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

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.