Loading ...
Sorry, an error occurred while loading the content.
 

Re: Need some help with a prestentation

Expand Messages
  • GameOfDeath2
    ... 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
      --- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
      <pochmann@g...> wrote:
      >
      > --- 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
      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
      > contradiction
      > > 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
      > 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...
      >
      > 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.)
    • Stefan Pochmann
      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 2 of 19 , Nov 4, 2004
        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

        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
      • GameOfDeath2
        ... 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 3 of 19 , Nov 5, 2004
          --- 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
          >
          > 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
        • Stefan Pochmann
          ... 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 4 of 19 , Nov 5, 2004
            --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
            <no_reply@y...> wrote:
            >
            > 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 ;-)

            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
          Your message has been successfully submitted and would be delivered to recipients shortly.