Since is invertible with inverse , this is equivalent to:

Now, let denote the columns of .
That is:

Another way of looking at the problem is as follows. By definition, we have:

In other words, we are trying to find the co-ordinates of the vector in terms of a new basis.

Recalling now that the determinant is multi-linear and anti-symmetric, consider the expression:

Let us now rewrite the equation as the following “formal” determinant , which has entries in the first row the standard basis vectors, and additional “projective symbol” :

Expanding along the top row, whilst making use of the previous remark (and being careful with the signs), we get:

Next, by expanding along the -th column, we obtain:

I shan’t derive this matrix from the “principle of relativity” which states that the laws of physics are identical in all inertial frames of reference, for this has been done very well elsewhere, and is not the purpose of this post.

Let us return instead to our good friend, the two by two rotation matrix, in order to make a few observations:

Consider a right angled triangle with sides lengths , and . If you remember the definition of your basic trigonometric functions, as well as Pythagorus’ theorem, then you will “see” that we have:

This gives us the following alternative parameterization for the rotation matrices, where :

If you recall now the definition of the hyperbolic trigonometric functions, you will “see” that and , and as a consequence, we have:

This in turn gives us an alternative parameterization for the Lorenz Transformation, where :

The upshot of this is that if you are willing to work over rather than over , and to think of your space dimension as purely real, and your time dimension as purely imaginary, then applying a “Lorenz boost” to your frame of reference is equivalent to rotating through an imaginary angle.

In the same way that a regular rotation maps circles to circles in two space dimensions, a “hyperbolic rotation” sends hyperbolae to hyperbolae in one space dimension and one time dimension. The following mathematica code will let you play around with this idea.

points = {{1, 0}, {2, 0}, {3, 0}, {4, 0}};

A[theta_] := {{Cos[theta], -Sin[theta]}, {Sin[theta], Cos[theta]}};
B[v_] := {{1/Sqrt[1 - v^2], v/Sqrt[1 - v^2]}, {v/Sqrt[1 - v^2],
    1/Sqrt[1 - v^2]}};

Plot[y /. Table[Solve[x^2 + y^2 == k^2, y], {k, 5}], {x, -5, 5},
  PlotRange -> {-5, 5}, AspectRatio -> 1];
Manipulate[
 Show[%, ListPlot[points . A[theta], PlotStyle -> PointSize[0.025],
   PlotRange -> {{-5, 5}, {-5, 5}}, AxesOrigin -> {0, 0},
   AspectRatio -> 1]], {{theta, 0}, -Pi, Pi}]

Plot[y /. Table[Solve[x^2 - y^2 == k^2, y], {k, 0, 8}], {x, -10, 10},
  PlotRange -> {-10, 10}, AspectRatio -> 1];
Manipulate[
 Show[%, ListPlot[points . B[theta], PlotStyle -> PointSize[0.025],
   PlotRange -> {{-5, 5}, {-5, 5}}, AxesOrigin -> {0, 0},
   AspectRatio -> 1]], {{theta, 0}, -0.9, 0.9}]

Since a particle moving at the speed of light is represented in this picture by the degenerate hyperbola which form the asymptotes of the rest of the family, it is clear now why the speed of light is constant in all inertial frames of reference.

But what’s really going on here? Let be the matrix representing a Minkowski bilinear form with one space dimension and one time dimension:

Compare this to the Euclidean case, in which the bilinear form is represented by the identity matrix. Now we have that any matrix of the form:

In co-ordinates, if and represent two different particles in two dimensional space, then the Euclidean inner product is usually represented as:

In the Minkowski picture, where time is imaginary, a “point” represents a particle located at a given position in one dimensional space, at a given time. The “inner product” of two “points” and is given by:

All these are special cases of the most general quadratic equation, which can be written in the following projective form:

Note that the by matrix in the middle is symmetric. As an example, the Family of circles centered at the origin, with radius are associated to the family of matrices of the form:

The first form of the hyperbola, with asymptotes parallel to the co-ordinate axes, corresponds to the matrix:

More generally, the matrix associated to a hyperbola whose axes have been tilded by an angle of clockwise from the diagonal is:

The following mathematica code will let you play around with these rotations.

   v = Transpose[{{x, y, 1}}];
   similtude[A_, M_] := Transpose[M].A.M
   equation[A_] := Solve[similtude[A, v][[1]][[1]] == 0, y]

   R[theta_] := {{Cos[theta], -Sin[theta], 0},
                 {Sin[theta], Cos[theta], 0},
                 {0, 0, 1}};
   H = {{1,0,0},{0,-1,0},{0,0,-1}}
   W[theta_] := similtude[H, R[theta]]

   Manipulate[
     Plot[Evaluate[y /. equation[W[theta]]], {x, -4, 4},
       PlotRange -> {{-4, 4}, {-4, 4}},
       AspectRatio -> 1],
   {{theta, 0}, -Pi, Pi}]

A few remarks about the code. In Mathematica square brackets are reserved for passing arguments into functions, curly brackets for defining lists, and normal round brackets for grouping terms in algebraic expressions.

Double square backets are used for indexing elements of a list. Matrices are represented as lists of list. The first list is the first row, the second list is the second row, etc…

The matrix multiplication operator is simply a dot. When defining your own functions, the variables which can be passed into a function must be followed by an underscore.

The built in functions, Transpose and Solve do more or less what you would expect. The only subtlety is that the output of Solve is a transformation rule. The /. notation replaces the left hand side with the right hand side in the transformation rule.

The built in function Plot is responnsible for drawing static plots. Leaving a parameter free (in this case the angle theta) and wrapping it inside the Manipulate command allows you to vary the parameter with the mouse and view the resulting animation.

Recall that translation can be thought of an operation in projective space represented by the matrix:

Now, starting from the matrix for a circle of radius one, centered at the origin:

  T[a_, b_] = {{1, 0, -a}, {0, 1, -b}, {0, 0, 1}};
  CC = {{1,0,0},{0,1,0},{0,0,-1}}
  M[a_, b_] := similtude[C, T[a, b]]
  Manipulate[
    Plot[Evaluate[y /. equation[CC]], {x, -2, 2},
      PlotRange -> {{-2, 2}, {-2, 2}}, AspectRatio -> 1],
  {{a, 0}, -1, 1}, {{b, 0}, -1, 1}]

Now for the fun part. Let us define the following “projective rotation”

Using this, we can smoothly deform a circle into a hyperbola. Check it out:

   P[theta_] := {{Cos[theta], 0, -Sin[theta]}, {0, 1, 0},
                 {Sin[theta], 0, Cos[theta]}};
   S[theta_] := similtude[CC, P[theta]]

   Manipulate[
     Plot[Evaluate[y /. equation[S[theta]]], {x, -10, 10},
       PlotRange -> {{-10, 10}, {-10, 10}},
       AspectRatio -> 1],
   {{theta, 0}, -Pi, Pi}]

But what’s really going on here geometrically? The following three dimensional quadratic equation describes a mathematical cone (which is more like a pair of icecream cones, touching at their tips):

By setting we are effectively taking the intersection with a plane. As you may know, all quadrics can be obtained by intersecting a cone with some given plane (hence the term conic section). The plane gives a circle, while the plane gives a hyperbola. Our “projective rotation” smoothly rotates the axis to the axis.

You might have also asked yourself “What about translation?” That’s a nice geometric operation, how can we represent it algebraically in terms of matrices?

The problem with translation is that it doesn’t preserve the origin, and is thus not a linear transformation. It is however a projective transformation, and so by working in projective space it is still possible to think of translations in terms of matrix operations. This is a common trick used in computer graphics packages such as openGL.

There are many different ways to think about two dimensional projective space. Geometrically it is the set of lines in three dimensional space which pass through the origin. Topologically its the two dimensional sphere with antipodal points identified. Think of the fact that a line through the origin in intersects the unit sphere in exactly two points.

Algebraically, it is the set of triples under the equivalence relation for all .

Another useful way to think about projective two-space is as regular two dimensional space with an additional “circle* at infinity”, that is an additional point at infinity for every possible direction which you might head out in from the origin. Imagine the hyperplane sitting inside and notice how any line passing through the origin, which does not lie in the two dimensional subspace spanned by the and directions, intersects this plane in exactly one point.

Working with the algebraic definition, a two dimensional projective transformation is just a by matrix acting on projective co-ordinates. The equivalence relation on the underlying projective space implies that two matrices which differ only by a scalar multiple represent the same projective transformation.

Suppose that we want to send the arbitrary point to the new point which is shifted across two steps and down three steps.

The first step is to embed the two dimensional plane, which we are really interested in, into the somewhat more abstract and difficult to understand two dimensional projective space, where we are going to perform our transformation. This is accomplished by the map:

The “inverse” of this embedding is the map:

Alternatively, if you have trouble visualizing projective space, just imagine embedding into as the hyperplane given by the equation . The only thing we’re really missing in this picture is the “circle at infinity” which will be important later when we consider quadrics, but does not really matter just now while we are only concerned with translation operators (which send infinity to infinity anyhow).

Consider now the following projective transformation:

If we apply this to the image of our point under our funny embedding, then we get:

Et Voila! After taking the inverse of the embedding, this is exactly the image of the point that we were looking for.

* As correctly pointed out by Cale Gibbard, its not actually a circle at infinity, but a projective line. If two people head out in opposite directions along the plane they will reach the same point at infinity.

Statistical Aspects of Data Mining

Machine Learning

Also, the data set for the netflix prize.

Regardless of whether you have any actual interest in learning Ruby or not, if your laughing muscles need a work out, may I recommend:

Why’s (poignant) guide to Ruby

It even has a soundtrack.

Hence,

By simply reversing the sequences (using the index substitution ), we get a further bijection:

So these two sets will have the same generating series. Using the product and sum lemma, we obtain:

We now extend the definition of inversions to words on the alphabet . If is the symbol at the position of the word , then an inversion in is a pair of positions such that , but .

We wish to know the generating series with respect to inversions for the set of words of length on with occurrences of .

To get it, we will use an indirect decomposition, decomposing an element as a word , together with permutations in a bijection which additively preserves inversions, where and is a set with elements.

That is, our weight-preserving bijection will look like:

We split the domain of a permutation into blocks with sizes in the obvious way, with the block consisting of the elements where . Note that acts on in a canonical way, with a permutation sending to .

The word is then defined by if .

We define the permutation for each as the subword of consisting of the elements of . Note that if and are both elements of , then is an inversion of if and only if it is also is an inversion of .

It will help to illustrate this bijection with an example. Take , and , so that , and .

Let be the permutation (in word form):

Then we construct the word by taking to be the block in which occurs:

We then compute:

To invert the above process, we simply replace the occurrence of in the word with . Hence, this is a bijection.

To see that it is additively weight-preserving with respect to inversions, we do a bit of a case analysis. We classify the inversions of according to whether and are in the same block or in different blocks.

If they are in different blocks, say and , then since , we must have , and so . Hence is also an inversion of . Conversely, every inversion of will clearly be an inversion of of this type, since if but , we have that and , but since , any element of is greater than any element of , and in particular .

If they are in the same block , then by a previous argument, is an inversion of if and only if it is an inversion of .

Hence, we have that .

By subtracting from each of the elements of , we obtain a standard permutation , and this is obviously inversion-preserving.

So, we have a weight-preserving bijection:

Hence, we have a corresponding equation of generating series. Let be the generating series for
. Then:

[pdf version]

This animation shows for through to the number of permutations with a given number of inversions and major index. I love the way that discrete structure slowly falls away into something nearly continuous. I would have included more frames in the animation, but as there are permutations in it gets expensive to compute these by brute force counting. I would need to come up with a more effective method.

An inversion of a permutation on is a pair of elements with such that That is, the permutation reverses their order. The inversion number, is the number of such pairs that a given permutation has. For example, the permutation (regarded as a word, not a cycle) has inversions and so

A descent in a permutation is a position with where a larger number occurs immediately before a smaller one. That is, The major index, is defined as the sum of the descents. For example, in the permutation we have descents at the first position (3 falls to 1), and at the third (4 falls to 2). So the major index of this permutation is

The plot shows at position the number of permutations with exactly inversions, and major index as a normalised shade of grey, darker meaning larger. Indices increase left to right and top to bottom.

You can easily see from the symmetry of the plots that permutations are equidistributed with respect to these two indices, so that we can expect the polynomial where the coefficient of is the number of permutations with inversion number and major index will be a symmetric polynomial in and

Also, the sage-combinat-dev mailing list.

So, why am I still fumbling along trying to implement inefficient algorithms for basic algebraic and combinatorial structures in Haskell, when efficient versions already exist in this fabulous open source project? Well:

• I like the idea of functional programming, especially higher order functions. The fact that the lambda calculus and turing machines provide equivalent models of computation is highly non-trivial. The natural way to decompose a problem into smaller sub-problems in a functional language is very different from the natural way to decompose the same problem in an imperative language. Once you have the “atomic” pieces of the puzzle, you can recombine them in novel ways. Having new ways to break something apart suggests new ways to put it back together again.
• One of the things that originally attracted me to mathematics is the fact that everything can be reduced to first principles. Foundational paradoxes aside, I have always felt uncomfortable proving theorems using the results of other theorems which I don’t myself know how to prove. Similarly, I have always felt uncomfortable programming with sophisticated libraries, the inner workings of which I have no understanding. For this reason, I would like to implement my own “toy algorithms” for manipulating daily mathematical objects, even if in practice I end up using somebody elses library for efficiency reasons.
• From what limited programming experience I have, the one thing I have learned is that even very simple things are actually much more complicated than they first seem. Forcing myself to explain my reasoning to a computer is a great way to uncover hidden, unarticulated assumptions. Even if this is a painful process, the resulting clarity of vision seems worth it.