Problem 5.1.9 (Permutation matrices)

Question

Let $G_i$ be a field $F$ for all $i$ and use the preceding exercise to show that the set of $n 	imes n$ matrices with one $1$ in each row and each column is a subgroup of $\mathrm{GL}_n(F)$ isomorphic to $S_n$ (these matrices are called {\bf permutation matrices} since they simply permute the standard basis $e_1,\ldots,e_n$ (as above) of the $n$-dimensional vector space $F 	imes F 	imes \cdots	imes F$).

Richard Ganaye · Accepted Answer

\begin{proof} 
Here $G = F^n$. By Exercises 7 and 8, if $\chi$ is defined by
$$
\chi
\left\{
\begin{array}{ccl}
S_n &	o &\mathrm{Aut}(G)\
\pi & \mapsto & \varphi_\pi,
\end{array}
ight.
$$
where 
$$
\varphi_\pi
\left\{
\begin{array}{ccl}
 F^n& 	o& F^n\
(g_1,g_2,\ldots,g_n) & \mapsto & (g_{\pi^{-1}(1)},g_{\pi^{-1}(2)},\ldots, g_{\pi^{-1}(n)}),
\end{array}
ight.
$$
then $\chi$ is a homomorphism.
In other words,  $S_n$ acts on $G = F^n$ for the action defined by 
\begin{align}
\pi \cdot (g_1,g_2,\ldots, g_n) = (g_{\pi^{-1}(1)},g_{\pi^{-1}(2)},\ldots, g_{\pi^{-1}(n)}).
\end{align}
If ${\cal B} = (e_i)_{1\leq i \leq n}$ is the natural basis of $F_n$, then $e_i = (\delta_{1,i},\delta_{2,i},\ldots, \delta_{n,i})$, where $\delta_{i,j}$ is the Kronecker's symbol defined by
$$\delta_{i,j} = 
\begin{cases}
1 &	ext{if } i = j,\
0 & 	ext{if } i 
e j.
\end{cases}
$$
Then
\begin{align*}
\pi \cdot e_i& = \pi \cdot(\delta_{1,i},\delta_{2,i}\ldots, \delta_{n, i})\
&=(\delta_{\pi^{-1}(1),i},\delta_{\pi^{-1}(2),i},\ldots, \delta_{\pi^{-1}(n),i})\
&=(h_1,h_2,\ldots,h_n),
\end{align*}
where $$h_j = \delta_{\pi^{-1}(j),i} = 1 \iff i = \pi^{-1}(j) \iff j = \pi(i),$$ and $h_j = 0$ otherwise. Therefore
\begin{align}
\pi \cdot e_i = e_{\pi(i)}.
\end{align}
Then (1) can be rewritten as
\begin{align*}
\pi\cdot (g_1e_1+g_2 e_2+\cdots + g_ne_n) &= g_{\pi^{-1}(1)} e_1 +  g_{\pi^{-1}(2)} e_2 + \cdots +  g_{\pi^{-1}(n)} e_n\
&= g_1 e_{\pi(1)} +  g_2 e_{\pi(2)} + \cdots +  g_n e_{\pi(n)}\
&= g_1\,  \pi\cdot e_1 + g_2 \, \pi \cdot e_2 + \cdots g_n\,  \pi \cdot e_n.
\end{align*}
This means that
$$
\varphi_\pi(g_1e_1+g_2 e_2+\cdots + g_ne_n) =  g_1\,  \pi\cdot e_1 + g_2 \, \pi \cdot e_2 + \cdots g_n\,  \pi \cdot e_n,
$$
thus $\varphi_\pi$ is linear. Since 
$$\varphi_\pi(e_j) = e_{\pi(j)} = \sum_{i=1}^n \delta_{i,\pi(j)}  e_i$$
 for all $j \in [\![1,n]\!]$, its matrix relative to $\cal B$ is
\begin{align*}
 \mathscr{M}_{\cal B}(\varphi_\pi) &= (\delta_{i,\pi(j) })_{(i,j)\in [\![1,n]\!]^2}\
 &=
 \begin{pmatrix}
 \delta_{1,\pi(1)}&  \delta_{1,\pi(2)} & \cdots & \delta_{n,\pi(1)}\
 \delta_{2,\pi(1)}&  \delta_{2,\pi(2)} & \cdots & \delta_{2,\pi(1)}\
  \vdots\
  \delta_{n,\pi(1)}&  \delta_{n,\pi(2)} & \cdots & \delta_{n,\pi(1)}\
 \end{pmatrix}
 \end{align*}
 For all $\pi \in S_n$ $\varphi_\pi \in \mathrm{GL}(F^n)$ (the group of linear automorphisms of $F^n$), we obtain a homomorphism of $S_n$  to $\mathrm{GL}_n(F)$ by composing the two homomorphisms 
 $$
 \lambda
 \left\{
  \begin{array}{ccccl}
 S_n & 	o &  \mathrm{GL}(F^n) & 	o & \mathrm{GL}_n(F)\
 \pi & \mapsto & \varphi_\pi & \mapsto & \mathscr{M}_{\cal B}(\varphi_\pi) = (\delta_{i,\pi(j) })_{(i,j)\in [\![1,n]\!]^2}
 \end{array}
 ight.
 $$
Moreover, if $\lambda(\pi) =  (\delta_{i,\pi(j) })_{(i,j)\in [\![1,n]\!]^2}= I$, then $\delta_{i,\pi(j)} = \delta_{i,j}$ for all $i,j$, thus $\pi(j) = j$ for all $j$, and so $\pi = \mathrm{id}_{S_n} = ()$. This shows that $\lambda$ is injective. Therefore $S_n$ is isomorphic to the subgroup $\mathrm{im}(\lambda)$ of  $\mathrm{GL}_n(F)$.

Since $(\delta_{i,\pi(j) })_{(i,j)\in [\![1,n]\!]^2}$ is a permutation matrix for every $\pi \in S_n$, the image of $\lambda$ is contained in the set $P$ of permutations matrices. Since $|S_n| = |P| = n!$, we obtain $\mathrm{im}(\lambda) =P$.

In conclusion, $S_n$ is isomorphic to the group of permutation matrices $P = \mathrm{im}(\lambda)$.

\end{proof}

Problem 5.1.9 (Permutation matrices)

Answers

Comments

Problem 5.1.9 (Permutation matrices)

Answers

Comments

Add answer