Schreier's Lemma Proof not clear.

[caffeinemachine]

Hello MHB.

I am reading a book on Combinatorics in which there is proved the Schreier's Lemma. I don't fully understand the proof.

THEOREM: Let $\{g_1,\ldots,g_m\}$ generate a group $G$. Let $k_1,\ldots,k_s$ be coset representatives of for a subgroup $H$ of $G$ where $k_1=1$. Let \(\overline{g}=k_i\) iff \(gH=k_{i}H\). Then $H$ is generated by the set $$S_H=\{k_ig_j\overline{(k_ig_j)}^{-1}:i=1,\ldots,s;j=1,\ldots,m\}$$

PROOF: All the elements of $S_H$ lie in $H$. Now suppose that $h=g_{i_1}g_{i_2}\ldots g_{i_r}\in H$. For $j=0,\ldots,r,$ let $t_j=g_{i_1}\ldots g_{i_j}$, and let $u_j=\overline{t_j}$. Then, with $u_0=1$, we have $$h=u_0g_{i_1}u_1^{-1}.u_1g_{i_2}u_2^{-1}\ldots u_{r-1}g_{i_r}u_r^{-1},$$
Since $u_0=u_r=1$ and all the other $u_i$ cancel with their inverses. But $u_{j-1}g_{i_j}$ lies in the same coset as $u_j$. Thus $u_{j-1}g_{i_j}u_j^{-1}\in S_H$, and we have expressed $h$ as a product of elements of $S_H$.
__________________________________________________________
I can't see how it is true that $u_{j-1}g_{i_j}u_j^{-1}\in S_H$. Can somebody please explain this to me?

 

[Deveno]

First of all, it appears that from your proof we should have:

$\overline{g} = k$ if $Hg = Hk$.

The reason I say this, is because if $ab^{-1} \in H$, then we have:

$Ha = Hb$, NOT $aH = bH$.

We can see that $u_{j-1}g_{i_j}(u_j)^{-1} \in S_H$ directly:

clearly, $u_{j-1} = \overline{t_{j-1}}$ is one of the $k$'s, and $g_{i_j}$ is one of the $g$'s, so:

$u_{j-1}g_{i_j}$ is of the form $k_vg_w$ for some appropriate indices $v,w$.

Furthermore, since $t_j = t_{j-1}g_{i_j}$, we have:

$u_{j-1}g_{i_j}(u_j)^{-1} = \overline{t_{j-1}}g_{i_j}(\overline{t_{j-1}g_{i_j}})^{-1} = \overline{t_{j-1}}g_{i_j}(\overline{\overline{t_{j-1}}g_{i_j}})^{-1}$, which is in $S_H$

(since if $\overline{g} = k_r$, then $\overline{\overline{g}g'} = \overline{k_rg'} = \overline{gg'}$, that is:

$H\overline{g}g' = (H\overline{g})g' = (Hk_r)g' = (Hg)g' = Hgg'$).

Perhaps it might be useful to see an application.

Let $G = S_4$ with generating set $\{(1\ 2), (2\ 3), (3\ 4)\}$.

Let H be the subgroup:

$\{e, (1\ 2\ 3\ 4), (1\ 3)(2\ 4), (1\ 4\ 3\ 2), (1\ 3), (2\ 4), (1\ 4)(2\ 3), (1\ 2)(3\ 4)\}$.

$|H| = 8$, so we have 3 (right) cosets:

$H, H(1\ 2\ 3),H(1\ 3\ 2)$. So we may take our traversal set to be $\{e,(1\ 2\ 3), (1\ 3\ 2)\}$.

we now have 9 possible products $k_ig_j$:

(1 2)
(2 3)
(3 4)
(1 2 3)(1 2) = (1 3)
(1 2 3)(2 3) = (1 2)
(1 2 3)(3 4) = (1 2 3 4)
(1 3 2)(1 2) = (2 3)
(1 3 2)(2 3) = (1 3)
(1 3 2)(3 4) = (1 3 4 2) <--note we only get 6 distinct products.

now we find which coset of $H$ these are in (finding $\overline{k_ig_j}$). So:

$\overline{(1\ 2)} = (1\ 2\ 3)$
$\overline{(2\ 3)} = (1\ 3\ 2)$
$\overline{(3\ 4)} = (1\ 2\ 3)$
$\overline{(1\ 3)} = e$
$\overline{(1\ 2\ 3\ 4)} = e$
$\overline{(1\ 3\ 4\ 2)} = (1\ 3\ 2)$

Now we calculate $S_H$:

(1 2)(1 3 2) = (1 3) <--this is in $H$.
(2 3)(1 2 3) = (1 3)
(3 4)(1 3 2) = (1 4 3 2)<--also in $H$.
(1 3)e = (1 3)
(1 2 3 4)e = (1 2 3 4)
(1 3 4 2)(1 2 3) = (2 4),

so we see that $S_H = \{e, (1\ 3), (2\ 4), (1\ 2\ 3\ 4), (1\ 4\ 3\ 2)\}$.

Note this generating set is by no means minimal, in fact:

$H = \langle (1\ 3), (1\ 2\ 3\ 4)\rangle$.

Another example is given here:

Schreier's lemma - Wikipedia, the free encyclopedia

 

[caffeinemachine]

First of all, it appears that from your proof we should have:

$\overline{g} = k$ if $Hg = Hk$.

The reason I say this, is because if $ab^{-1} \in H$, then we have:

$Ha = Hb$, NOT $aH = bH$.

We can see that $u_{j-1}g_{i_j}(u_j)^{-1} \in S_H$ directly:

clearly, $u_{j-1} = \overline{t_{j-1}}$ is one of the $k$'s, and $g_{i_j}$ is one of the $g$'s, so:

$u_{j-1}g_{i_j}$ is of the form $k_vg_w$ for some appropriate indices $v,w$.

Furthermore, since $t_j = t_{j-1}g_{i_j}$, we have:

$u_{j-1}g_{i_j}(u_j)^{-1} = \overline{t_{j-1}}g_{i_j}(\overline{t_{j-1}g_{i_j}})^{-1} = \overline{t_{j-1}}g_{i_j}(\overline{\overline{t_{j-1}}g_{i_j}})^{-1}$, which is in $S_H$

(since if $\overline{g} = k_r$, then $\overline{\overline{g}g'} = \overline{k_rg'} = \overline{gg'}$, that is:

$H\overline{g}g' = (H\overline{g})g' = (Hk_r)g' = (Hg)g' = Hgg'$).

Perhaps it might be useful to see an application.

Let $G = S_4$ with generating set $\{(1\ 2), (2\ 3), (3\ 4)\}$.

Let H be the subgroup:

$\{e, (1\ 2\ 3\ 4), (1\ 3)(2\ 4), (1\ 4\ 3\ 2), (1\ 3), (2\ 4), (1\ 4)(2\ 3), (1\ 2)(3\ 4)\}$.

$|H| = 8$, so we have 3 (right) cosets:

$H, H(1\ 2\ 3),H(1\ 3\ 2)$. So we may take our traversal set to be $\{e,(1\ 2\ 3), (1\ 3\ 2)\}$.

we now have 9 possible products $k_ig_j$:

(1 2)
(2 3)
(3 4)
(1 2 3)(1 2) = (1 3)
(1 2 3)(2 3) = (1 2)
(1 2 3)(3 4) = (1 2 3 4)
(1 3 2)(1 2) = (2 3)
(1 3 2)(2 3) = (1 3)
(1 3 2)(3 4) = (1 3 4 2) <--note we only get 6 distinct products.

now we find which coset of $H$ these are in (finding $\overline{k_ig_j}$). So:

$\overline{(1\ 2)} = (1\ 2\ 3)$
$\overline{(2\ 3)} = (1\ 3\ 2)$
$\overline{(3\ 4)} = (1\ 2\ 3)$
$\overline{(1\ 3)} = e$
$\overline{(1\ 2\ 3\ 4)} = e$
$\overline{(1\ 3\ 4\ 2)} = (1\ 3\ 2)$

Now we calculate $S_H$:

(1 2)(1 3 2) = (1 3) <--this is in $H$.
(2 3)(1 2 3) = (1 3)
(3 4)(1 3 2) = (1 4 3 2)<--also in $H$.
(1 3)e = (1 3)
(1 2 3 4)e = (1 2 3 4)
(1 3 4 2)(1 2 3) = (2 4),

so we see that $S_H = \{e, (1\ 3), (2\ 4), (1\ 2\ 3\ 4), (1\ 4\ 3\ 2)\}$.

Note this generating set is by no means minimal, in fact:

$H = \langle (1\ 3), (1\ 2\ 3\ 4)\rangle$.

Another example is given here:

Schreier's lemma - Wikipedia, the free encyclopedia

Thank you Deveno for the kind explanation. It really helps. I was not able to read it before because of my exams. Sorry for the delay in feedback.