Browse Groups

• ## Re: Need some help with a prestentation

(19)
• NextPrevious
• ... matrix ... transposition ... it ... matrix ... saying ... talking ... pairs ... yours ... ) ... Actually, my main point is that you need to show that
Message 1 of 19 , Nov 4, 2004
View Source
--- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:
>
> --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> >
> > I guess the
> > usual way to do it would probably to be to write the identity
matrix
> > (of the appropriate size) as a product of an odd number of
> permutation
> > matrices (corresponding to transpositions). Since each
transposition
> > matrix has determinant -1 (you just need to swap 2 rows to make
it
> the
> > identity matrix, which has determinant 1) then the identity
matrix
> > would have determinant (-1)^k for some odd k, i.e. -1, a
> > and so the result would follow by reductio ad absurdum.
>
> Ok, I read your exact reasoning again. I think we're actually
saying
> pretty much the same thing, the difference is just that you're
talking
pairs"
> of "raw order". Well, I'd need to define mine more precisely,
yours
> are two simple words that are well-known already, so... you win ;-
)
> But I still say our proofs are equivalent...
>
> Cheers!
> Stefan

Actually, my main point is that you need to show that
oddness/evenness can't both occur at once. To be odd just means that
the permutation can be expressed as a product of an odd number of
transpositions - to be even is similarly defined. There is a
question of whether it is possible to be simultaneously odd and even
that needs to be addressed. You've defined oddness/evenness
differently, in terms of wrong pairs and described a canonical way
of defining it, so providing a well-defined notion of odd vs even.
What it doesn't prove is that it is impossible to write an odd/even
permutation (as defined like this) as a product of an even/odd
number of transpositions. (In other words, if you didn't do it
canonically and just switched pairs and eventually came to the
identity in some non-methodical way, how would you know that you
always take an odd (or always take an even) number of
transpositions.)
You do make some reference to this: 'And whenever you do a swap, the
number of swaps done overall changes its "evenness" and at the same
time the number of wrong pairs changes its "evenness", too.' but it
is a technical issue that does require a bit of proof (and is
equivalent to the fact that the identity permutation can't be
written as the product of an odd number of permutations). If you
could flesh out the bit I quoted from you above, we'd be on the same
track.
I guess the way I'd tackle it using your definition is to look at a
permutation (a b) (where a<b, say).
So you have 1 2 ... a-1 b a+1 a+2 ... b-1 a b+1 ...
The number b has (b-1)-(a-1)=b-a smaller numbers on the right,
namely a,...,b-1.
The numbers a+1,...,b-1 all have just 1 smaller number to the right
(namely a).
All the other numbers have no smaller numbers to the right.
So the total number of wrong pairs is b-a+((b-1)-a)=2b-2a-1 which is
odd.
So by your definition a transposition is odd.
Now you just need to work the quoted bit above to the effect that if
you compose 2 permutations the number of wrong pairs is (modulo 2)
just the sum of the wrong pairs in the permutations. (It won't
generally be the sum, only the sum modulo 2 - and that is the key
thing here, to be able to prove that.) The sum of an odd number of
odd number is odd, but due to the specific way you've defined
odd/even it is something to be proven that composing permutations
actually does behave as hoped.
(In your example, for instance there are 6 smaller numbers to the
right of the 8. If you compose with another permutation, will there
be an even or odd number of smaller numbers to the right of the 8?
I've not investigated, but perhaps this depends on more than whether
the 2nd permutation is odd/even on a number by number basis, though
not for the whole sum.)
• Hi Richard, I think you misunderstood me somehow. Especially this part makes me ... I did *not* define a canonical way for solving a permutation, but rather
Message 1 of 19 , Nov 4, 2004
View Source
Hi Richard,

I think you misunderstood me somehow. Especially this part makes me
think so:

> (In other words, if you didn't do it
> canonically and just switched pairs and eventually came to the
> identity in some non-methodical way, how would you know that you
> always take an odd (or always take an even) number of
> transpositions.)

I did *not* define a canonical way for "solving" a permutation, but
rather a way for "looking" at it. I.e. the wrong pairs shall not be
swapped in some particular way (there are many ways for this), they
shall only be counted (there's only one way=result for this).

In other words, define for a permutation p:
federminant(p) := (number of wrong pairs in p) mod 2

What I left as an exercise to Joel is to prove:
1) federminant(identity) = 0
2) federminant(swap(p,i,j)) = (federminant(p) + 1) mod 2
Where swap(p,i,j) is the permutation you get by swapping elements i
and j in permutation p.

Simple induction shows that if you take permutation p, apply k swaps,
and reach permutation q, you have:
federminant(q) = (federminant(p) + k) mod 2

Now assume you take permutation p=identity, apply k swaps (with odd k)
, and reach permutation q=identity. Then you have (everything mod 2):

federminant(identity)
= federminant(q)
= federminant(p) + k
= federminant(identity) + 1
= 0 + 1
= 1

I don't think there's something missing in my proof (other than the
exercise part of course ;-), hopefully my more formal description
above makes clearer what I mean.

What do you say?

Cheers!
Stefan
• ... me ... but ... be ... they ... No, what I meant was a canonical way of defining odd vs even (rather than solving the permutation): namely sum over x
Message 1 of 19 , Nov 5, 2004
View Source
--- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:
>
> Hi Richard,
>
> I think you misunderstood me somehow. Especially this part makes
me
> think so:
>
> > (In other words, if you didn't do it
> > canonically and just switched pairs and eventually came to the
> > identity in some non-methodical way, how would you know that you
> > always take an odd (or always take an even) number of
> > transpositions.)
>
> I did *not* define a canonical way for "solving" a permutation,
but
> rather a way for "looking" at it. I.e. the wrong pairs shall not
be
> swapped in some particular way (there are many ways for this),
they
> shall only be counted (there's only one way=result for this).
>

No, what I meant was a canonical way of defining odd vs even (rather
than solving the permutation): namely sum over x #{y:y<x and y is to
the right of x} (mod 2).

> In other words, define for a permutation p:
> federminant(p) := (number of wrong pairs in p) mod 2
>
> What I left as an exercise to Joel is to prove:
> 1) federminant(identity) = 0
> 2) federminant(swap(p,i,j)) = (federminant(p) + 1) mod 2
> Where swap(p,i,j) is the permutation you get by swapping elements
i
> and j in permutation p.

2) is what I was referring to - hadn't realized you were leaving
this as an exercise. This is the part I was saying was vital.
Then I agree with you. (The point I was trying to make is that I
thought you were leaving 2) out.)

(All the rest is agreed.)

>
> Simple induction shows that if you take permutation p, apply k
swaps,
> and reach permutation q, you have:
> federminant(q) = (federminant(p) + k) mod 2
>
> Now assume you take permutation p=identity, apply k swaps (with
odd k)
> , and reach permutation q=identity. Then you have (everything mod
2):
>
> federminant(identity)
> = federminant(q)
> = federminant(p) + k
> = federminant(identity) + 1
> = 0 + 1
> = 1
>
>
> I don't think there's something missing in my proof (other than
the
> exercise part of course ;-), hopefully my more formal description
> above makes clearer what I mean.
>
> What do you say?
>
> Cheers!
> Stefan
• ... Ah, ok... so we did indeed misunderstand each other a bit ;-) How about this proof of step 2): Call a swap of two adjacent elements a bubble . Swapping
Message 1 of 19 , Nov 5, 2004
View Source
--- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
>
> 2) is what I was referring to - hadn't realized you were leaving
> this as an exercise. This is the part I was saying was vital.
> Then I agree with you. (The point I was trying to make is that I
> thought you were leaving 2) out.)
>
> (All the rest is agreed.)

Ah, ok... so we did indeed misunderstand each other a bit ;-)

a "bubble". Swapping any two elements A and B in a sequence is the
same as first bubbling A towards B (so they're adjacent), then
bubbling A and B, then bubbling B back to A's original place by
undoing the first part. A bubble clearly changes "evenness" of the
number of wrong pairs. And for a swap, we do (n+1+n) bubbles. So a
swap changes that evenness, too.

Cheers!
Stefan
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.