Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $E$ be a finite set and $G$ a transitive group of permutations of $E$. For $x\in E$, let $S_x$ denote the stabilizer of $x$. Then, for any $x,y\in E$, the number of orbits of $E$ under the action of $S_x$ is equal to the number of orbits of $E$ under the action of $S_y$.

I have seen this mentioned in some books without proof like a triviality, but I can't find a proof. I know Burnside's lemma and I know that $G/S_x$ and $G/S_y$ (sets of left cosets) are isomorphic to $E$, and hence to each other, as $G$-sets. None of this seems to help. I'm probably missing something very obvious. Can you help me?

share|improve this question
    
$G$ acts component-wise on $E×E$. As $G$ is transitive, the diagonal $\Delta$ is an orbit. The number of orbits of $G$ on $E×E$ equals the number of orbits of $S_x$ on $E$. I think that as the same is obviously true for $y$, the authors of the books considered the equality you are looking for to be trivial. –  j.p. Aug 13 '11 at 7:44

2 Answers 2

up vote 7 down vote accepted

You mean $x, y \in E$, right? Let $g \in G$ be such that $gx = y$. For the purposes of counting orbits, relabeling the elements of $E$ shouldn't change the number of orbits, so let's relabel every $a \in E$ with the new label $ga$.

In this new labeling, the group action looks like the following: where we used to have $ha = b$ (with $h \in G$), we now have

$$(ghg^{-1}) ga = gb.$$

In other words, in this new "coordinate system," $h \in G$ acts as $ghg^{-1}$.

Now restricting to $S_x$ in the old coordinate system is the same as restricting to $g S_x g^{-1} = S_y$ in the new coordinate system. In particular the two group actions are isomorphic, so have the same number of orbits.

share|improve this answer

Since $G$ acts transitively on $E$, then for any $x,y\in E$ there exists $g\in G$ such that $gx=y$. Then $S_y = gS_xg^{-1}$:

Indeed, since $gx=y$, then $g^{-1}y=x$. Thus, if $ghg^{-1}\in gS_xg^{-1}$, we have $ghg^{-1}y = ghx = gx = y$, so $ghg^{-1}\in S_y$; hence $S_y\subseteq gS_xg^{-1}$. Using the same argument, we get that $S_x\subseteq g^{-1}S_yg$, which gives the other inclusion.

So $S_x$ and $S_y$ are conjugate, and in particular there is an automorphism of $G$ that maps $S_x$ to $S_y$; this automorphism induces an isomorphism of the cosets of $S_x$ to the cosets of $S_y$ as $G$-sets.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.