Let $G \leq S_n$ be a permutation group. Also let $G^{(i)}, 1 \leq i \leq n$ be the subgroups of permutation whic fix elements $1,2,\cdots i$. Then $G= G^{(0)} = (G^{(0)}/G^{(1)}) (G^{(1)}/G^{(2)}) \cdots (G^{(n-1)}/G^{(n)})$ (product of quotients) I am trying to understand the matter at page 37 of $\href{http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567802&tag=1}{this}$ paper. How do we prove this.
Decomposition of Permutation Group
-
0@DerekHolt, thanks for the info. I didn't know that. – 2012-08-27
2 Answers
My interpretation is that they mean the following:
- By $G^{(i)}/G^{(i+1)}$ they mean a set of representatives of cosets of $G^{(i+1)}$ in $G^{(i)}$. With a view of reducing any confusion I will select, once and for all, such sets of representatives, and denote them by $D_i$, $i=0,1,\ldots$. Note that they are not subgroups of $G$ (or groups at all).
- The decomposition that troubles the OP means the following. Let $g$ be an arbitrary element of $G$. Then it can be written in a unique way as $ g=d_0d_1d_2\cdots d_{n-1}, $ where $d_i\in D_i$ for all indices $i$.
This follows more or less immediately from the definitions. The given element $g\in G$ belongs to a unique coset of the subgroup $G^{(1)}$, so we can write $ g=d_0g_1, $ where $d_0\in D_0$ and $g_1\in G^{(1)}$. We can then proceed, because $g_1$ belongs to a unique coset of $G^{(2)}$, and can thus be written (in a unique way) as a product $g_1=d_1g_2$, where $d_1\in D_1$ and $g_2\in G^{(2)}$. Clearly we can continue to do this. The uniqueness of the end result also follows from the fact that "tail part" of such a product, $d_jd_{j+1}\cdots d_{n-1}$ clearly belongs to the subgroup $G^{(j-1)}$.
-
0+1 Excellent interpretation to an otherwise pretty confussing text. I agree that's what the author $m$ust have meant. – 2012-08-27
Note the following: the author does not prove or note that the $G^{(i)}$ are normal. I therefore think that he does not talk about proper quotient groups, but rather some kind of left quotient that he does not properly define.
However, whatever he is talking about, if it is a true statement we can probably prove it by induction.
The theorem is trivial for $n=1$.
For the induction step, we know that $G^{(1)}\cong(G^{(1)}/G^{(2)}) \times \cdots \times (G^{(n-1)}/G^{(n)})$. Prove that $G\cong(G/G^{(1)})\times G^{(1)}$ (whatever this $G/G^{(1)}$ is).
Now, if $G$ is abelian, all subgroups are normal, and then we can use the "normal" defition of quotient groups, but this is not assumed by the author.
-
0Agreed, I'll leave this in place for reference. – 2012-08-27