# Decomposition of Permutation Group

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. • It may be not a good idea to choose that notation $\,G^{(i)}\,$ ,as it is already in use for something very different within group theory (the derived groups). Besides this, in order to talk of quotient groups, we must have normal subgroups...but these are not normal subgroups: for example, with $$n=3\,\,,\,\,G^{(1)}=\{(1)\,,\,(23)\}\rlap{\;/}\triangleleft G^{(0)}=S_3\,\,...$$ – DonAntonio Aug 27 '12 at 9:16
• @DonAntonio I have added reference to the question, please help me understand that part. Please edit the question to make it appropriate, based on the ref. – DurgaDatta Aug 27 '12 at 9:25
• Sorry @Durga, I've no access to that paper now. If you can download it somewhere and make accessible to everybody that'd be great. – DonAntonio Aug 27 '12 at 9:27
• @DonAntonio I can download and keep in accessible place, but are there any copyright issues? – DurgaDatta Aug 27 '12 at 9:31
• I don't know, yet if you download it for personal use I don't think there's any problem...but I'm not sure. – DonAntonio Aug 27 '12 at 9:33

My interpretation is that they mean the following:

1. 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).
2. 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)}$.

• +1 Excellent interpretation to an otherwise pretty confussing text. I agree that's what the author must have meant. – DonAntonio Aug 27 '12 at 11:21

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.

• This is wrong: $\,G^{(1)}\,$ is not a normal subgroup of $\,G\,$ so $\,G/G^{(1)}\,$ is meaningless... – DonAntonio Aug 27 '12 at 9:23
• Can you agree with my modified version? – akkkk Aug 27 '12 at 9:37
• indeed. Yet I think Jyrki's version is right on the money and without any need of normality or abelianity, which can be quite an issue when dealing with permutation groups. – DonAntonio Aug 27 '12 at 11:23
• Agreed, I'll leave this in place for reference. – akkkk Aug 27 '12 at 12:18