- --- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"

<pochmann@g...> wrote:>

matrix

> --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2

> <no_reply@y...> wrote:

> >

> > I guess the

> > usual way to do it would probably to be to write the identity

> > (of the appropriate size) as a product of an odd number of

transposition

> permutation

> > matrices (corresponding to transpositions). Since each

> > matrix has determinant -1 (you just need to swap 2 rows to make

it

> the

matrix

> > identity matrix, which has determinant 1) then the identity

> > would have determinant (-1)^k for some odd k, i.e. -1, a

saying

> contradiction

> > and so the result would follow by reductio ad absurdum.

>

> Ok, I read your exact reasoning again. I think we're actually

> pretty much the same thing, the difference is just that you're

talking

> about "determinants" of "matrices" and I'm talking about "wrong

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...

Actually, my main point is that you need to show that

>

> Cheers!

> Stefan

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

think so:

> (In other words, if you didn't do it

I did *not* define a canonical way for "solving" a permutation, but

> 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.)

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

Contradiction!

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 - --- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"

<pochmann@g...> wrote:>

me

> Hi Richard,

>

> I think you misunderstood me somehow. Especially this part makes

> think so:

but

>

> > (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,

> 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:

i

> 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

> 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.)

>

swaps,

> Simple induction shows that if you take permutation p, apply k

> and reach permutation q, you have:

odd k)

> federminant(q) = (federminant(p) + k) mod 2

>

> Now assume you take permutation p=identity, apply k swaps (with

> , and reach permutation q=identity. Then you have (everything mod

2):

>

the

> federminant(identity)

> = federminant(q)

> = federminant(p) + k

> = federminant(identity) + 1

> = 0 + 1

> = 1

>

> Contradiction!

>

> I don't think there's something missing in my proof (other than

> exercise part of course ;-), hopefully my more formal description

> above makes clearer what I mean.

>

> What do you say?

>

> Cheers!

> Stefan - --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2

<no_reply@y...> wrote:>

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

> 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.)

How about this proof of step 2): Call a swap of two adjacent elements

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