Posts Tagged ‘algebra’

Answer: Parity of Permutations

December 6, 2008

The question asked you to show that it is possible to permute a list however you like using only successive swaps, and that any two lists of swaps that achieve the same permutation contain either both an even number of swaps or both an odd number of swaps.

Part one: You can get the Rockettes in order no matter how they come out on stage
Here’s an algorithm for doing it:

  1. If the Rockette who should be first is not first, switch her with the first one.
  2. If Rockette who should be second is not now second, switch her with the second one.
  3. Continue until you get to the last two Rockettes. All the Rockettes ahead of them are in place, so the last two are in the last two spots. If they’re in the wrong order, switch them, and you’re done.

Part two: A permutation has a well-defined parity (even/odd quality).
Slap a number on each of the Rockettes so that when they’re in the right order they’ll line up as (for four dancers) 1,2,3,4
As the dancers come out on stage, they’re in some random order, like 3,1,4,2
Taking that random order, we’ll calculate a number called the parity in the following way:

Take each possible pair of dancers. That makes n(n-1)/2 pairs. We’ll be assigning each of those pairs a number. If the dancer with a higher number comes later in the lineup, give that pair a one. If the dancer with the higher number comes earlier, give that pair a minus one. Multiply all the n(n-1)/2 ones and minus ones together to get a final one or minus one for the entire lineup. All of the n! possible lineups now have either a minus one or plus one associated with them through this procedure. That plus or minus one is called the lineup’s “parity”.

I’ll calculate the parity for the example order 3,1,4,2
(1,2) 1
(1,3) -1
(1,4) 1
(2,3) -1
(2,4) -1
(3,4) 1
1*-1*1*-1*-1*1 = -1
The parity of 3,1,4,2 is odd.

Lemma: Any time you swap two dancers, you go from one lineup to a new lineup. Those lineups have opposite parity, as defined above.

Proof: Since the parity comes from multiplying numbers associated with pairs of dancers, we’ll try to find all the pairs whose numbers could flip due to the switch of dancers. Switching the dancers changes the pair of those two dancers. It does not change the pair of any two dancers who weren’t involved in the switch. It also does not change the pair of any dancer who was behind both of those switched, or in front of both of those switched. However, for each dancer in the middle of the two who were switched, that dancer’s pair with each of the two who were switched gets multiplied by minus one. So all told, the number of pairs whose +/-1 gets flipped is one for the pair of the two switched dancers, and two for the each dancer in the middle of them. The two flips for the pairs for the dancer in the middle cancel each other out in the final product, so the switch of two dancers ultimately gives a lineup whose parity is opposite that of the original lineup.

For example, if I take 3,1,4,2 and switch the 1 and 2, I get 3,2,4,1. The pairs change as follows:
(1,2) 1 -> -1
(1,3) no change
(1,4) 1 -> -1
(2,3) no change
(2,4) -1 -> 1
(3,4) no change
So all together, there were three flips, and the total parity goes from -1 to 1.

Now suppose the dancers come out on stage in a permutation whose parity is plus one. We already proved that by making some switches, we can get them back to the correct starting order. If we make an odd number of switches, we’d change the parity an odd number of times, leaving it as minus one. But the correct order has parity plus one, so no odd number of switches can get us there, and the total number of switches to solve the problem must be even. Similarly, if they come out on stage in a permutation with parity minus one, we’ll have to make an odd number of switches to get them to the plus-one-parity correct order.

That means that if the Rockettes come out on stage messed up, but you can find a way to get them in order with an even number of switches, you’ll never find a way to put them back as they were and do it again with an odd number of switches.

Let’s Read the Internet! Week 2

October 19, 2008

Davisson-Germer Experiment Chad Orzel at Uncertain Principles
The first observation of the wave properties of electrons came by accident. Just like you.

A Beautiful New Theory of Everything Garrett Lisi on
In case you were wondering how everything works…

Didn’t quite catch that? Don’t worry. You can always read the paper.

Infinity is NOT a Number Mark Chu-Carroll at Good Math, Bad Math
More comprehensible than the previous post, if less profound. The fundamental problem with making infinity a number seems to be that it lets you prove all manner of foolishness, such as 1=2.

The Universal Declaration of Human Rights

It’s awfully pretentious to claim your document to be “universal”. Who has the authority? Further, what does it mean for everyone to be equal in rights? Clearly, we are not equal in many senses. Separating out “these things are rights” and “these things are what you have to deal with because of the circumstances of your life” is a tough task. For example, according to this declaration, everyone has a right to marry. But marriage is simply not a universal concept among humans. It’s perfectly conceivable to have viable, righteous societies with absolutely no concept of marriage. The concepts of privacy and property ownership could be sacrificed in righteous societies, under the right circumstances. Creating a list of rights that’s simultaneously universal and specific seems nearly impossible. But the visualization is nice.

Dead Waters Romain Vasseur et. al
Boats that get stuck in plain water. I don’t understand why this works, but the video is really cool.

Chimpanzees Make Spears to Hunt Bushbabies Not Exactly Rocket Science
Like it says, chimps make weapons and kill shit with them. In case you were wondering where we get it from.

Late Bloomers Malcolm Gladwell in The New Yorker
Just because you’re old doesn’t mean you’re useless. Therefore, you might as well slack off for another year or two before beginning that “great life’s work” stuff.

Where’s the Algebra? Michael Alison Chandler on X = Why?
Some chick with a seriously ugly smile asks whether algebra is important. But her “education” from her brother sadly misses the point. She asks, “what good are equations?”, and he replies “We have to learn equations to install lights.” But the entire article is written with the attitude that these equations are magical things that pop out of nowhere to describe lighting systems, their goal being to confuse blue-collar workers to the greatest extent possible. I don’t think there’s any understanding here the equations actually come from somewhere. Someone used a more basic set of principles to derive the equations, or else conducted experiments and then found equations to describe the results. Applying equations to describe real situations is not supposed to be a matter of plugging numbers into formulas.

The Cartoon-Off Farley Katz at The Cartoon Lounge
Normally, I wouldn’t bother linking to something that’s already been Slashdotted, but I bookmarked this page for “Let’s Read the Internet on Wednesday, and then the Slashdot post comes up just hours before I compile my links for the week. I guess the fact that the entire geek culture already knows about doesn’t really impact how funny it is.

The Sun
The web page that makes you go blind if you stare directly at it.

Fabry, Perot, and Their Wonderful Interferometer Skulls In The Stars
The author consistently produces wonderful posts explaining concepts in optics from a historical point of view. I actually used a Fabry-Perot interferometer in physics lab once. What I learned there is that they make surprisingly bad hammers.