|
|
| Author |
Message |
Snis Pilbor
science forum addict
Joined: 11 May 2005
Posts: 50
|
 Posted: Wed Jun 21, 2006 12:05 am Post subject:
Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Hi,
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n doesn't require great
ingenuity, but boy oh boy is the straightforward attack longwinded.
I've had to write it up twice now, once for homework and once for a
practice qual, and it is always a good 1/2-3/4 of a page! Is there a
"nicer" way to prove this fact?
It seems like when it comes to permutations there are lots of other
things like this. I've never seen a proof of simplicity of A_n that
doesn't put God himself to shame due to the sheer ugliness. Maybe I'm
just not reading the right books... thanks for any heuristical advice
or insight you can give me.
SP |
|
| Back to top |
|
 |
jaapsch
science forum beginner
Joined: 06 Jun 2005
Posts: 25
|
| Posted: Wed Jun 21, 2006 7:03 am Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
| Quote: | This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n doesn't require great
ingenuity, but boy oh boy is the straightforward attack longwinded.
I've had to write it up twice now, once for homework and once for a
practice qual, and it is always a good 1/2-3/4 of a page! Is there a
"nicer" way to prove this fact?
|
Below is about the shortest way I know to prove it without induction.
If you leave out some of the explaining text, it is only about 5 lines.
I write the permutation left to right, so p.q means permutation p is
applied first, then perm q.
Given two permutations (1 2 3 4 ... n) and (1 2).
(1 2 3 4 .. n) . (1 2) = (2 3 4 .. n)
(2 3 4 .. n)^-k . (1 2) . (2 3 4 .. n)^k = (1 2+k)
So all transpositions (1 a) can be formed for any a in {2...n}.
(1 a) . (1 b) . (1 a) = (a b)
So all transpositions (a b) can be formed for any a,b in {1...n}.
(a1 a2) . (a1 a3) ... (a1 ai) = (a1 a2 a3 ..ai)
So all cycles (a1 a2 a3 ..ai) can be formed, aj in {1...n}.
Every permutation is a product of (disjoint) cycles, and so any
permutation in Sn can be formed from (1 2 3 4 ... n) and (1 2). |
|
| Back to top |
|
|
Jyrki Lahtonen
science forum Guru Wannabe
Joined: 02 May 2005
Posts: 190
|
| Posted: Wed Jun 21, 2006 1:43 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
| Quote: | Hi,
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n doesn't require great
ingenuity, but boy oh boy is the straightforward attack longwinded.
I've had to write it up twice now, once for homework and once for a
practice qual, and it is always a good 1/2-3/4 of a page! Is there a
"nicer" way to prove this fact?
|
I dunno. The way I think about is via sorting. The claimed generation
is equivalent to the claim that you can sort a list of n numbers into
an increasing order by judiciously applying the following two "moves":
A) swap the first two,
B) spin them around cyclically.
IOW the task is to show that you can rearrange "a mungled n-hour dial"
by spinning it around, and at some points swapping the first two.
A simple proof by induction shows that you can always reduce the number
"missorted pairs" by at most three moves (two spins and a single swap)
unless the numbers are already sorted (in which case you're done).
| Quote: | It seems like when it comes to permutations there are lots of other
things like this. I've never seen a proof of simplicity of A_n that
doesn't put God himself to shame due to the sheer ugliness. Maybe I'm
just not reading the right books... thanks for any heuristical advice
or insight you can give me.
|
I don't know about this one. I don't think that the standard proof
is that ugly. At the lowest levels group theory may become relatively
combinatoric in nature, and that occasionally forces you to case-by-case
analysis. Undesirable? Most definitely, but perhaps also unavoidable.
Cheers,
Jyrki |
|
| Back to top |
|
|
Ryan Reich
science forum Guru Wannabe
Joined: 21 May 2005
Posts: 120
|
| Posted: Wed Jun 21, 2006 4:13 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
On Wed, 21 Jun 2006 16:43:02 +0300, Jyrki Lahtonen <lahtonen@utu.fi> wrote:
| Quote: | Snis Pilbor wrote:
It seems like when it comes to permutations there are lots of other
things like this. I've never seen a proof of simplicity of A_n that
doesn't put God himself to shame due to the sheer ugliness. Maybe I'm
just not reading the right books... thanks for any heuristical advice
or insight you can give me.
I don't know about this one. I don't think that the standard proof
is that ugly. At the lowest levels group theory may become relatively
combinatoric in nature, and that occasionally forces you to case-by-case
analysis. Undesirable? Most definitely, but perhaps also unavoidable.
|
I would argue that the purpose of viewing a general group as a permutation
group, or studying representations of groups as linear transformations, is
precisely to make the dirty combinatorial arguments (or linear-algebra
arguments) possible, since in the end these are the only way we can get a
handle on the complexities of our abstractions.
Think about how we study topology: the most influential idea in the entire
subject is algebraic topology, and for more than half a century (i.e. since
the subject was really born) this has been all about CW complexes, and these
are just combinatorial objects. The basic tools in geometry in general
involve tearing apart your space into small, understandable pieces with simple
interactions (triangulations, for example, are one historical method). Even
in algebraic geometry, the present state of extreme abstraction is the result
of a transition from intuitive but unworkable geometric ideas, to unintuitive
but very powerful and in some ways very mechanical categorical ideas. This is
not even to mention Hilbert's idea of founding mathematics on "finitary"
logical axioms and rules of deduction. All we can understand is the finite,
and in the end we reduce everything to it.
--
Ryan Reich
ryan.reich@gmail.com
sci.math |
|
| Back to top |
|
|
Snis Pilbor
science forum addict
Joined: 11 May 2005
Posts: 50
|
| Posted: Wed Jun 21, 2006 8:02 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
jaapsch wrote:
| Quote: | Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
Below is about the shortest way I know to prove it without induction.
(snip)
Given two permutations (1 2 3 4 ... n) and (1 2).
(snip)
|
NO! If I meant (1 2 3 ... n) and (1 2) I would have said so, that is
an easier problem than the problem I stated. I said *an n-cycle* and
*a transposition*. We can without loss of generality assume the
n-cycle is (123...n) *or* we can without loss of generality assume the
transposition is (12) but we can't do *both* without loss of
generality, at least not without explaining why, which is the whole
hard part of the proof. The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as. Proving (12...n) and (12) generate S_n is trivial, as
you guys pointed out.
Thanks for helping out..
SP |
|
| Back to top |
|
|
Russell
science forum Guru
Joined: 25 Mar 2005
Posts: 594
|
| Posted: Wed Jun 21, 2006 8:34 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
[snip]
The problem is not "show that an n-cycle and a
| Quote: | transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as.
|
Wouldn't you need just one more step? Given an arbitrary n-cycle c,
there must exist some k<n such that c^k takes 1 to 2. And there you
are, WLOG...
Proving (12...n) and (12) generate S_n is trivial, as
| Quote: | you guys pointed out.
Thanks for helping out..
SP |
|
|
| Back to top |
|
|
John H Palmieri
science forum beginner
Joined: 04 May 2005
Posts: 13
|
| Posted: Wed Jun 21, 2006 9:18 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
On Jun 21 2006, "Russell" <russell@mdli.com> wrote:
| Quote: | Snis Pilbor wrote:
[snip]
The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as.
Wouldn't you need just one more step? Given an arbitrary n-cycle c,
there must exist some k<n such that c^k takes 1 to 2. And there you
are, WLOG...
|
But c^k need not be an n-cycle: if k divides n, then c^k has order
n/k.
| Quote: | Proving (12...n) and (12) generate S_n is trivial, as
you guys pointed out.
Thanks for helping out..
SP
|
--
J. H. Palmieri
Associate Professor of Mathematics University of Washington
Box 354350, Seattle, WA 98195-4350 palmieri@math.washington.edu
http://www.math.washington.edu/~palmieri/ |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Wed Jun 21, 2006 9:34 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Russell wrote:
| Quote: | Snis Pilbor wrote:
[snip]
The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as.
Wouldn't you need just one more step? Given an arbitrary n-cycle c,
there must exist some k<n such that c^k takes 1 to 2. And there you
are, WLOG...
|
Unless k is coprime to n, we wouldn't know that c^k is again an
n-cycle.
regards, chip |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Thu Jun 22, 2006 12:40 am Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
| Quote: | jaapsch wrote:
Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
Below is about the shortest way I know to prove it without induction.
(snip)
Given two permutations (1 2 3 4 ... n) and (1 2).
(snip)
NO! If I meant (1 2 3 ... n) and (1 2) I would have said so, that is
an easier problem than the problem I stated. I said *an n-cycle* and
*a transposition*. We can without loss of generality assume the
n-cycle is (123...n) *or* we can without loss of generality assume the
transposition is (12) but we can't do *both* without loss of
generality, at least not without explaining why, which is the whole
hard part of the proof. The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as. Proving (12...n) and (12) generate S_n is trivial, as
you guys pointed out.
Thanks for helping out..
SP
|
What is the order of the group generated by (1 2 3 4) and (1 3)?
If necessary compute the multiplication table explicitly; I did.
regards, chip |
|
| Back to top |
|
|
Derek Holt
science forum beginner
Joined: 14 Jan 2006
Posts: 14
|
| Posted: Thu Jun 22, 2006 8:29 am Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
| Quote: | jaapsch wrote:
Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
Below is about the shortest way I know to prove it without induction.
(snip)
Given two permutations (1 2 3 4 ... n) and (1 2).
(snip)
NO! If I meant (1 2 3 ... n) and (1 2) I would have said so, that is
an easier problem than the problem I stated. I said *an n-cycle* and
*a transposition*. We can without loss of generality assume the
n-cycle is (123...n) *or* we can without loss of generality assume the
transposition is (12) but we can't do *both* without loss of
generality, at least not without explaining why, which is the whole
hard part of the proof. The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as. Proving (12...n) and (12) generate S_n is trivial, as
you guys pointed out.
|
OK, two comments, one linguistic and one mathematical.
For the linguistic point, as you admit yourself, you asked for a proof
that S_n is generated by *an n-cycle* and *a transposition*. Well
(1,2,...,n) is an n-cycle, and (1,2) is a transposition, so jaapsch has
correctly answered the question that you asked.
It seems as though what you intended to ask was: let g be any n-cycle
and let h be any transposition in S_n; then prove that S_n is generated
by g and h. As has already been pointed out, this is false in general -
for example, the subgroup of S_4 generated by (1,2,3,4) and (1,3) has
order 8, and is not equal to S_4.
It turns out that the answer is yes if and only if n is prime (and
when n = 1).
Derek Holt. |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Thu Jun 22, 2006 12:34 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Derek Holt wrote:
| Quote: | Snis Pilbor wrote:
jaapsch wrote:
Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
Below is about the shortest way I know to prove it without induction.
(snip)
Given two permutations (1 2 3 4 ... n) and (1 2).
(snip)
NO! If I meant (1 2 3 ... n) and (1 2) I would have said so, that is
an easier problem than the problem I stated. I said *an n-cycle* and
*a transposition*. We can without loss of generality assume the
n-cycle is (123...n) *or* we can without loss of generality assume the
transposition is (12) but we can't do *both* without loss of
generality, at least not without explaining why, which is the whole
hard part of the proof. The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as. Proving (12...n) and (12) generate S_n is trivial, as
you guys pointed out.
OK, two comments, one linguistic and one mathematical.
For the linguistic point, as you admit yourself, you asked for a proof
that S_n is generated by *an n-cycle* and *a transposition*. Well
(1,2,...,n) is an n-cycle, and (1,2) is a transposition, so jaapsch has
correctly answered the question that you asked.
It seems as though what you intended to ask was: let g be any n-cycle
and let h be any transposition in S_n; then prove that S_n is generated
by g and h. As has already been pointed out, this is false in general -
for example, the subgroup of S_4 generated by (1,2,3,4) and (1,3) has
order 8, and is not equal to S_4.
It turns out that the answer is yes if and only if n is prime (and
when n = 1).
Derek Holt.
|
Just to add, if one prefers not to get their "hands dirty"
constructing the multiplication table as I did, realize
the (rigid) symmetries of the square are generated by
(1 2 3 4) and (1 3), assuming a consecutive numbering
of vertices around the perimeter. This nonabelian group
of order 8 is often called the dihedral group D_4 to
distinguish it from the quaternion group (the other
nonabelian group of order  .
regards, chip |
|
| Back to top |
|
|
Snis Pilbor
science forum addict
Joined: 11 May 2005
Posts: 50
|
| Posted: Thu Jun 22, 2006 6:58 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
| Quote: | Derek Holt wrote:
Snis Pilbor wrote:
jaapsch wrote:
Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
(big snippage)
It turns out that the answer is yes if and only if n is prime (and
when n = 1).
Derek Holt.
|
Oh man, I screwed up there, please forgive me I caused anyone to pull a
lot of hair out over this. I remember now that when I did this problem
on homework some years back, it was assumed n was prime. Here is the
context in which this arose on a recent practice qual. A problem in 2
parts:
a. Show that (12345) and (12) generate S_5
b. Suppose a quintic polynomial has exactly 2 nonreal roots, show its
Galois group is S_5.
Part a is trivial of course. For part b, of course the nonreal roots
are conjugate, hence the Galois group has a transposition, and by
Cauchy's theorem it has an order 5 element, ie a 5-cycle. Given that a
transposition and a 5-cycle generate S_5, we're done. I didn't
remember the primality condition.
The part a seems to be jeering and taunting at me. As if there is some
way to show that not only does the Galois group contain an order 5
element, but that it contains an order 5 element that sends one of the
nonreal roots to the other. This *seems* like it should be easy, but I
wasn't able to show it. So I tried to use the more general result
instead...
Please forgive a newbie and have patience with me, I apologize
sincerely for all the confusion my post caused
S.P. |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Thu Jun 22, 2006 8:41 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Snis Pilbor wrote:
| Quote: | Derek Holt wrote:
Snis Pilbor wrote:
jaapsch wrote:
Snis Pilbor wrote:
This is a problem I've run into several times. Proving that a
transposition and an n-cycle generate S_n
(snip)
Is there a
"nicer" way to prove this fact?
(big snippage)
It turns out that the answer is yes if and only if n is prime (and
when n = 1).
Derek Holt.
Oh man, I screwed up there, please forgive me I caused anyone to pull a
lot of hair out over this. I remember now that when I did this problem
on homework some years back, it was assumed n was prime. Here is the
context in which this arose on a recent practice qual. A problem in 2
parts:
a. Show that (12345) and (12) generate S_5
b. Suppose a quintic polynomial has exactly 2 nonreal roots, show its
Galois group is S_5.
Part a is trivial of course. For part b, of course the nonreal roots
are conjugate, hence the Galois group has a transposition, and by
Cauchy's theorem it has an order 5 element, ie a 5-cycle. Given that a
transposition and a 5-cycle generate S_5, we're done. I didn't
remember the primality condition.
The part a seems to be jeering and taunting at me. As if there is some
way to show that not only does the Galois group contain an order 5
element, but that it contains an order 5 element that sends one of the
nonreal roots to the other. This *seems* like it should be easy, but I
wasn't able to show it. So I tried to use the more general result
instead...
Please forgive a newbie and have patience with me, I apologize
sincerely for all the confusion my post caused
|
You need irreducibility in (b) to conclude that the Galois
group is S_5. For example, x^5 - x is a quintic with exactly
two nonreal roots, but the Galois group (of its splitting field
over Q) is just S_2.
Less trivial examples, with no rational roots, could also be
given to show that the Galois group need not be all of S_5.
For example, multiply an irreducible cubic & an irreducible
quadratic.
One fact to keep in mind is that the Galois group of an
irreducible polynomial acts transitively on the roots.
regards, chip |
|
| Back to top |
|
|
Gerry Myerson
science forum Guru
Joined: 28 Apr 2005
Posts: 871
|
| Posted: Fri Jun 23, 2006 1:15 am Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
In article <1150979666.867594.50450@i40g2000cwc.googlegroups.com>,
"Chip Eastham" <hardmath@gmail.com> wrote:
| Quote: | This nonabelian group
of order 8 is often called the dihedral group D_4 to
distinguish it from the quaternion group (the other
nonabelian group of order .
|
No, it's called the dihedral group D_4 because it is the dihedral
group D_4, and would be even if there were no other nonabelian
group of order 8. Thus, the nonabelian group of order 10 is called
the dihedral group D_5, even though there's no quaternion group
in sight.
Although of course some authors call D_4 D_8.
--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email) |
|
| Back to top |
|
|
Russell
science forum Guru
Joined: 25 Mar 2005
Posts: 594
|
| Posted: Fri Jun 23, 2006 8:03 pm Post subject:
Re: Is there an easy way to show a transposition & n-cycle generate S_n?
|
|
|
Chip Eastham wrote:
| Quote: | Russell wrote:
Snis Pilbor wrote:
[snip]
The problem is not "show that an n-cycle and a
transposition of two elements, one of which conveniently gets sent to
the other by the n-cycle, generate S_n", which is what you guys seem to
have read it as.
Wouldn't you need just one more step? Given an arbitrary n-cycle c,
there must exist some k<n such that c^k takes 1 to 2. And there you
are, WLOG...
Unless k is coprime to n, we wouldn't know that c^k is again an
n-cycle.
regards, chip
|
Heh, thanks to you and to everyone else who set me right. You can
see that *I'm* not taking very many practice quals just now.
So, ok, let me stipulate that for the cases where a particular
transposition
and n-cycle do not generate S_n, the OP is correct in his opinion that
it is
difficult to prove that they do. (And no doubt, very messy to write
down such
an attempted proof.) |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 1:08 am | All times are GMT
|
|
Dirty Dozen Brass Band | Free Ringtones | Problem Mortgage | Loans | Credit Counseling
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
