Complex Numbers for Rotating, Translating, and Scaling the Plane June 7th, 2009
Patrick Stein

A good friend of mine recently discovered some of the fun things you can do with complex numbers if you’re using them to represent points in the plane. Yesterday, I re-read a passage by Tony Smith about why one should be interested in Clifford algebras. Tony Smith’s passage included all of the fun one can have with the complex plane and extends it to three, four, five, and more dimensions. I thought, I should segue from the complex numbers in the plane to Clifford algebras to quaternions in 3-space to Clifford algebras again in a series of posts here.

What are Complex Numbers

Say you’re playing around with polynomials. You start playing with the equation z^2 - 1 = 0. WIth a little fiddling, you find this is equivalent to z^2 = 1. Then, you take the square root of both sides to find that z = \pm \sqrt{1} = \pm 1. We started with a polynomial equation in one variable in which the highest exponent was two and we found two answers.

Pounding your chest and sounding your barbaric yawp, you move on to z^2 + 1 = 0. This should be easy, right? With the same fiddling, we find z^2 = -1 and then z = \pm \sqrt{-1}.

Uh-oh. What do we do now? We can’t think of any number that when multiplied by itself gives us a negative number. If we start with zero, we end with zero. If we multiply a positive number by itself, we get a positive number. If we multiply a negative number by itself, we get a positive number. Again!

Read the rest of this entry ⇒

Study with Me — Maybe Relation Algebras? June 4th, 2009
Patrick Stein

In an earlier post, I was soliciting recommendations for texts to study since I cannot seem to get Cambridge University Press to respond to me. Paul Reiners suggested (amongst other things) Relation Algebras by Games by Hirsch and Hodkinson.

I went to the Math Library at the U of MN yesterday to look through it. I only had a quick glance since I had my 11-month-old in tow. As I am no longer staff or student at the U, I could not check it out. However, as I have a Hennepin County Library card, I am able to request it via Interlibrary Loan. Soon, I will have a chance to assess it more carefully.

A Recurrence of Constrained Shuffles June 2nd, 2009
Patrick Stein

Earlier, I posted about finding the Fibonacci numbers when counting a very simple constrained shuffle. In that article, I was concerned with the question: How many permutations are there in \Sigma_n such that \left| \pi(i) - i \right| \le 1 for all i \in [1,n]?

For that problem, the answer was F_{n+1}. The number of permutations on n items where no item moves more than one space from where it started is the (n+1)-th Fibonacci number. Now, the obvious question is: How many permutations are there in \Sigma_n such that \left| \pi(i) - i \right| \le k for i \in [1,n] and k is an arbitrary positive integer?

Let’s not start so arbitrary just yet though…

Let’s just look for a moment at how much trickier things become when we let k = 2. It’s easy enough for n = 1. There’s only one shuffle possible and it satisfies the constraint. For that matter, the same is (conventionally) true for n = 0. When you have zero items, there is only one (very Zen) way to shuffle them, and it certainly does not violate the constraints.

For n = 2, there are two shuffles. Both satisfy the constraints. Similarly, with n = 3, there are 3! = 6 shuffles. All of them satisfy the constraints.

For n = 4, we get to the first interesting case. Here, some of the 4! = 24 shuffles violate the constraints. So, how many shuffles are still possible? To tackle this, we are going to use an inclusion-exclusion counting. The only items that could be out of place are the first and the last. So, how many of the 4! shuffles have either the first element move to the back or the last element move to the front?

There are 3! permutations that send the first element to the back. There are 3! permutations that send the last element to the front. We might then think that there are 4! - 2\cdot 3! valid shuffles. Alas, there are some shuffles that move both the first element to the back and the last element to the front. We have counted those twice. There are 2! = 2 of those.

So, for n = 4, there are 4! - 2\cdot 3! + 2! = 24 - 12 + 2 = 14 shuffles satisfying our constraint that \left| \pi(i) - i \right| \le 2.

What then of n = 5? Well, it’s bedtime here. This is gonna have to wait.

Goodnight.

I Discovered The Fibonacci Numbers May 31st, 2009
Patrick Stein

Alright, I wasn’t the first. But, I wasn’t particularly expecting to find them either.

One nascent game concept that I have in my head requires me to do some constrained shuffling. As an example constraint, imagine that you need to shuffle a deck of cards while ensuring that no card moved more than five spots away from where it started. Or, imagine that you had to shuffle the deck so that a card of rank r could only move to spot that had been held by a card of rank r-1, r, or r+1.

In the general case, you have a directed graph with vertexes \left\{ v_1, v_2, v_3, \ldots, v_n \right\} and a permutation \pi such that \pi(i) can only equal j if there is an edge in the graph from v_i to v_j.

Well, as this is for a game, it would get pretty boring if there were only a few possible shuffles. On the other hand, if there are a large number of possible shuffles, then I haven’t really restricted the shuffling at all for all practical purposes. So, then the question is: for a given directed graph, how many possible shuffles are there? Can I generate them without generating any of the invalid permutations, too?

Today, I started with the How many?-question. I started with a very simple graph. The vertexes are spaced evenly along an east-west line. Each vertex is connected only to itself, its nearest neighbor to the east, and its nearest neighbor to the west. Put another way, \left| \pi(i) - i \right| \le 1 for i \in [1,n].

Let’s say we already had a row of n-1 vertexes. If we add another vertex at the beginning of the row, then there are two things that a shuffle can do to that new vertex: leave it where it is or swap it with what had been the first vertex in the row. Now, suppose that c(n) is the count of valid shuffles for n vertexes in this configuration. The case where our new vertex stays where it is leaves c(n-1) possibilities for the rest of the row. The case where our new vertex swaps places with the old first vertex leaves c(n-2) possibilities. As such, c(n) = c(n-1) + c(n-2).

Cha-ching. Note that c(1) = 1 and c(2) = 2, then c(n) = F_{n+1} where F_i are the Fibonacci numbers.

Things get a great deal messier if we move up to \left| \pi(i) - i \right| \le 2. More on that some other time…

Still No Word On The Clifford Algebra Text May 29th, 2009
Patrick Stein

I still haven’t heard back from Cambridge University Press about using one of their books to publicly study Clifford algebras. So, I started looking around for alternate texts.

My second choice book is Clifford Algebras and Spinors by Pertti Lounesto. This, too, is published by Cambridge University Press. Feh.

I started poking around for other topics instead. How about a related topic? I grabbed Differential Forms and Connections by R.W.R. Darling from my shelf. It, too, is Cambridge University Press.

Alright, different topic. How about Galios theory? I grabbed A Course In Galois Theory by D.J.H. Garling from my shelf. It is Cambridge University Press. The other two Galois theory books that I have are not from Cambridge University Press, but I’m not sure they are as useful.

I can’t find any good Clifford algebra texts that are not Cambridge University Press. This Geometry of Differential Forms by Shigeyuki Morita is published by the AMS. It looks decent from a quick glance on Google books.

Any suggestions?

RSS Feeds

l