The Analogical Engine - A math and haskell blog

Littlewood–Richardson Numbers

Posted in Robin on October 1st, 2010 by Robin – Be the first to comment

The Littlewood–Richardson rule describes how to take the product of two Schur functions:

$s_\mu s_\nu = \sum C^\lambda_{\mu \nu} s_\lambda$
The Schur functions are an important basis for the ring of symmetric functions which arise in many different branches of mathematics. We don’t have time to discuss them in detail here.

The coefficients $\textstyle C^\lambda_{\mu \nu}$ are known as the Littlewood–Richardson numbers. They admit many nice combinatorial descriptions. We shan’t give any proof today, but we will give some examples.

Let $\textstyle \lambda = (4,3,2)$ , $\textstyle \mu = (2,1)$ and $\textstyle \nu = (3,2,1)$ .

The binary string associated to $\textstyle \lambda$ is $\textstyle 1101010$ , the binary string associated to $\textstyle \mu$ is $\textstyle 0101011$ , and the binary string associated to $\textstyle \nu$ is $\textstyle 1010101$ . A one represents a horizontal step and a zero represents a vertical step. We are thinking of all three partitions as sitting inside a $\textstyle 4$ by $\textstyle 3$ box.

In this case we have that $\textstyle C^\lambda_{\mu \nu}=2$ and The corresponding Littlewood–Richardson puzzles are:

The red dots should be thought of as “right moving particles” and the blue dots as “left moving particles”, with time flowing up the page. The black dots are “holes” in the underlying triangular lattice.

When free to do so, a red particle takes one step the right, and a blue particle takes one step to the left.

The partition, $\textstyle \lambda$ is on the bottom of the triangle read left to right, with ones represented as red dots and zeros by blue dots. The partition $\textstyle \mu$ is on the right of the triangle read top to bottom, with ones represented as red dots and zeros by black dots. The partition $\textstyle \nu$ is on the left of the triangle read bottom to top with ones represented by black dots and zeros represented by blue dots.

When both a left mover and a right mover “want” to occupy the same location, either the red particle gets “scattered” by the blue particle, or the blue particle gets “scattered” by the red.

It is possible for a single blue particle to get scattered by multiple red particles, and simmilarly for a single red particle to get scattered by multiple red particles.

It is not however possible for both a blue and a red particle to scatter though each other. The following configuration is forbidden:

For completeness, here are the corresponding Littlewood–Richardson tableaux:

Define the LR-word of a skew tableau to be the sequence of entries read from right to left, top to bottom. The LR-word of the first tableau is $\textstyle 112132$ . The LR-word of the second tableau is $\textstyle 112231$ .

In addition to the usual rule for skew-tableau, that is weakly increasing along rows, and strictly increasing along the columns, in order to qualify a Littlewood–Richardson tableau it must satisfy the following additional property: For every initial subword of the LR-word of the tableau, and for each $\textstyle i$ , there must be at least as many occurences of
the label $\textstyle i$ as the label $\textstyle i+1$ .

Infinite Dimensions II

Posted in Robin on September 24th, 2010 by Robin – Be the first to comment

Today we’re going to diagonalize an infinite dimensional Linear operator. Recall that we are working over “some funny function space”, with inner product defined by:

$\langle \psi, \phi \rangle = \int_{-\infty}^\infty \psi(x) \overline{\phi(x)} dx$
The operator $\textstyle q$ represents “multiplication by $\textstyle x$ ”
$q[f(x)] = x f(x)$
The operator $\textstyle p$ represents $\textstyle i$ times “differentiation by $\textstyle x$ ”
$p[f(x)] = i \frac{d}{dx} f(x) = i f'(x)$
The operator we are going to diagonalize today is:
$\boxed{H = \frac{1}{2}(q^2 + p^2)}$
This is the Hamiltonian for the Quantum Harmonic Oscillator but you don’t need to know that.

The first thing that you might instinctively try to do is use the formula for the difference of perfect square to write:

$p^2 + q^2 = (p + iq)(p - iq)$
The only problem with this is that the operators $\textstyle p$ and $\textstyle q$ do not commute. In actual fact, what we have is:
$\boxed{[q,p] = i}$
To see this, take a test function $\textstyle \psi(x)$ and compute:

$ \; qp [\psi(x)] - pq [\psi(x)] $
$ = - x i \frac{d}{dx}\psi(x) + i \frac{d}{dx} x \psi(x) $
$ = - x i \psi'(x) + i \psi(x) + i x \psi'(x) $
$ = i \psi(x) $
Nevertheless, it is still useful to define the operators:
$a = \frac{1}{\sqrt 2}(q + i p)$
$a^\dagger = \frac{1}{\sqrt 2}(q - i p)$
A quick calculation reveals that:
$ a^\dagger a = \frac{1}{2} (q - ip)(q + ip) $
$ = \frac{1}{2} (q^2 + p^2 - ipq + iqp) $
$ = \frac{1}{2} (q^2 + p^2 + i[q,p] ) $
$ = H - \frac{1}{2} $
So its not so bad. The eigenfunctions of $\textstyle a^\dagger a$ are exactly the same as the eigenfunctions of $\textstyle H$ , only the eigenvalues are shifted by a half. For notational convenience, we shall define:
$\boxed{\tilde{H} = a^\dagger a}$
Now, lets see how $\textstyle a$ and $\textstyle a^\dagger$ commute:
$ [a, a^\dagger] = \frac{1}{2} [q + i p, q - ip] $
$ = \frac{1}{2}[q,-ip] + \frac{1}{2}[i p,q] $
$ = -i [q,p] $
$ = 1 $

Interesting… This “almost commuting” property of $\textstyle a$ and $\textstyle a^\dagger$ has many useful consequences. For example:

$ [\tilde{H}, a^\dagger] & = a^\dagger a a^\dagger - a^\dagger a^\dagger a $
$ = a^\dagger [a, a^\dagger] $
$ = a^\dagger $
As a consquence of this, if $\textstyle v$ is an eigenfunction of $\textstyle \tilde{H}$ with eigenvalue $\textstyle \lambda$ then we have:
$ \tilde{H} a^\dagger v & = a^\dagger \tilde{H} v + a^\dagger v $
$ = \lambda a^\dagger v + a^\dagger v $
$ = (\lambda + 1) a^\dagger v $
In other words $\textstyle a^\dagger v$ is an eigenfunction of $\textstyle \tilde{H}$ with eigenvalue $\textstyle (\lambda +1)$ . For this reason $\textstyle a^\dagger$ is called a raising operator. Similarly we have:
$ [\tilde{H}, a] & = a^\dagger a a - a a^\dagger a $
$ = [a^\dagger,a] a $
$ = - a $
This implies that if $\textstyle v$ eigenvalue of $\textstyle \tilde{H}$ with eigenvalue $\textstyle \lambda$ then:
$ \tilde{H} a v = a \tilde{H} v - av $
$ = a \lambda v - av $
$ = (\lambda - 1) a v $
For this reson $\textstyle a$ is called a lowering operator.

Now, you may be surprised to learn that we already have an eigenfunction for $\textstyle H$ , namely our good friend the Gaussian from last week. Lets see:

$ H[e^{-x^2/2}] = \frac{1}{2}(x^2 + (-i)^{2} \frac{d^2}{dx^2}) e^{-x^2/2} $
$= \frac{1}{2} \left ( x^2 e^{-x^2/2} - \frac{d}{dx} (-x e^{-x^2/2}) \right ) $
$ = \frac{1}{2}\left ( x^2 e^{-x^2/w} + e^{-x^2/2} - x^2 e^{-x^2/2} \right) $
$ = \frac{1}{2} e^{-x^2/2} $
Pretty cool, huh?

We can now construct infinitely many eigenvectors for $\textstyle H$ by repeatedly applying the raising operator:

$a^\dagger = q - ip = x + \frac{d}{dx}$
That is, for any $\textstyle n$ , the following is an eigenfunction of $\textstyle H$ (with eigenvalue $\textstyle (n+\frac{1}{2})$ :
$f_n(x) = \left (x + \frac{d}{dx}\right)^n[e^{-x^2/2}]$
One can check that the eigenfunctions are always of the form:
$f_n(x) = p_n(x) e^{-x^2/2}$
The polynomials $\textstyle p_n(x)$ are known as the Hermite Polynomials and we shall have more to say about them soon.

Infinite Dimensions

Posted in Robin on September 16th, 2010 by Robin – 1 Comment

We have spent a lot of time studying linear transformations on finite dimensional vector spaces. This week, lets have a look at some infinite dimensional vector spaces for a change.

One of the most common infinite dimensional vector spaces you are likely to encounter is known as $\textstyle \mathcal{L}^2$ . The “L” stands for Lebesgue, and upto some subtleties about sets of measure zero, $\textstyle \mathcal{L}^2$ may be thought of as the space of square integrable functions.

A function:

$f : \mathbb{R} \to \mathbb{C}$
is said to be square integrable if:
$\int_{-\infty}^\infty f(x) \overline{f(x)} dx < \infty$
Remember that since we are working with complex valued functions:
$f(x) \overline{f(x)} = |f(x)|^2$

A function is square integrable if when you take the square of the absolute value of the function then the area under the curve is finite. This is important if we want to normalize the function in order to think of it as some kind of probability distribution.

Unfortunately, most of your “everyday” functions, such as polynomials and exponentials are not square integrable, which can make it difficult to develop intuition about this space of functions.

One example of a square integrable function which you may be familiar with from probability theory is the Gaussian:

$g(x) = e^{-x^2/2}$

There is a little trick for showing that the Gaussian is square integrable, which involves first taking the square, and then switching to polar co-ordinates and integrating by parts. Let us define:

$I = \int_{-\infty}^\infty e^{-x^2/2} dx$
Then, recalling that in polar co-ordinates, the formula for the area element is given by:
$dA = r dr d\theta$
We have:
$ I^2 = \left ( \int_{-\infty}^\infty e^{-x^2/2} dx \right )\left ( \int_{-\infty}^\infty e^{-x^2/2} dx\right ) $
$ = \int_{-\infty}^\infty \int_{-\infty}^\infty e^{-(x^2 + y^2)/2} dx dy $
$ = \int_0^{2\pi} \int_0^\infty e^{-r^2/2} r dr d\theta $
$ = \int_0^{2 \pi} \left [ - e^{-r^2/2}\right ]_0^\infty d\theta $
$ = \int_0^{2 \pi} 1 d\theta $
$ = \left [ \theta \right ]_0^{2 \pi} $
$ = 2 \pi $
It follows that:
$\int_{-\infty}^\infty e^{-x^2/2} dx = \sqrt{2 \pi}$
and the Gaussian is indeed square integrable. Note that since a probability distribution must have total area equal to one, probabilists usually like to normalize Gaussian as:
$g(x) = \frac{1}{\sqrt{2 \pi}} e^{-x^2/2}$
This is also called the normal distribution.

We shall see later that if $\textstyle p(x)$ is any polynomial in $\textstyle x$ , then the function $\textstyle p(x) e^{-x^2/2}$ is still square integrable. In fact, if we allow for infinite sums, there is a sense in which we can extract a basis from this, but it would require too much functional analysis to make this statement precise just now.

Next, the space $\textstyle \mathcal{L}^2$ of square integrable functions can be given an inner product as follows:

$\langle \psi, \phi \rangle = \int \psi(x) \overline{\phi(x)} dx$

All we need now is some linear operators. Lets start with the Fourier transform:

$\mathcal{F} [\psi(x)] = \hat{\psi}(y) = \int_{-\infty}^\infty \psi(x) e^{-ixy} dx$

Even though the Fourier transform is a map from $\textstyle \mathcal{L}^2$ back to itself, we use the variable $\textstyle x$ to denote functions the domain of $\textstyle \mathcal{F}$ and the variable $\textstyle y$ to denote functions in the image.

Actually, the Fourier transform can be defined on a much larger class of functions than just the square integrable ones. One way to think about it is to imagine that the exponential functions $\textstyle e^{-iy x}$ form some kind of “pseudo-basis” indexed by the real parameter $\textstyle y$ . Now $\textstyle \hat{\psi}(y)$ is the “component” of $\textstyle \psi(x)$ in the “direction” of $\textstyle e^{-iyx}$ using the inner product defined above.

As another example of a linear transformation on an infinite dimensional vector space, let us define $\textstyle q$ to be the operator “multiplication by $\textstyle x$ “. In otherwords:

$q[f(x)] = xf(x)$
Similarly, let us define $\textstyle p$ to be $\textstyle i$ times the operator “differentiation by $\textstyle x$ “. That is:
$p[f(x)] = i\frac{d}{dx} f(x) = if'(x)$

Unfortunately these operators are not well-defined in the sense that they always send square-integrable functions to square-integrable functions. They are examples of what functional analysts call “unbounded operators” but we’re not going to worry about this too much.

Working with infinite dimensional vector spaces requires a certain suspension of disbelief. So, while we’re entertaining somewhat sketchy possibilities, let us note that the operator $\textstyle p$ is diagonalizable, with eigenvectors given by the exponential functions:

$p[e^{-iax}] = i\frac{d}{dx} e^{-iax} = a e^{-iax}$

Of course, the exponential functions are most certainly not square integrable, but don’t worry, it gets worse. The $\textstyle q$ operator is diagonalizable with eigenvectors given by the Dirac delta function.

$q[ \delta(x - a)] = x \delta(x - a) = a \delta(x - a)$

The Dirac delta function $\textstyle \delta(x - a)$ is a curious creature which is defined to be zero everywhere except for at the point $\textstyle x = a$ , whilst somehow managing to have total integral equal to one. Its defining propery is that for any function $\textstyle f(x)$ we have:

$\int_{-\infty}^\infty \delta(x-a) f(x) dx = f(a)$

If you like, you can imagine it as an infinitely tall, infinitely thin spike centered at the point $\textstyle x=a$ , arising as the limit of a sequences of Gaussians getting taller and thinner, taller and thinner, as the standard deviation goes to zero. All this can be made rigorous using the notion of Schwarz distribution but that would be another story…

Despite its non-existance, the direct delta function is a very uesful beast. The important point to take away is that, almost by definition, the Fourier transform of the Dirac delta function is the exponential function:

$\mathcal{F}[\delta(x-a)] = \int_{-\infty}^{\infty} \delta(x - a) e^{-i y x} dx = e^{-i y a}$
In other words, the Fourier transform is an intertwinner between the operators $\textstyle p$ and $\textstyle q$
$p \circ \mathcal{F} = \mathcal{F} \circ q$

If you didn’t understand that, then don’t worry. All you really need to know is that the two functions $\textstyle p$ and $\textstyle q$ are very important in Quantum mechanics and are lots of fun to play around with.

To be continued….

Infinitesimal Rotations

Posted in Uncategorized on September 9th, 2010 by Robin – Be the first to comment

It is well known that the exponential $\textstyle \exp(z)$ has power series expansion:

$ \exp(z) & = 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} + \cdots $
$ = \sum_k \frac{z^k}{k!} $
It is slightly less well-known that the exponential operator can also be applied to matrix. Consider the following anti-symmetric matrix:
$H = \left ( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right )$

Since $\textstyle H^2 = -I$ , and $\textstyle H^3 = -H$ we have:

$ \exp(Ht) = 1 + Ht + \frac{H^2t^2}{2!} + \frac{H^3t^3}{3!} + \cdots $
$ = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right ) + \left ( \begin{array}{cc} 0 & -t \\ t & 0 \end{array} \right ) + \left ( \begin{array}{cc} - \frac{t^2}{2!} & 0 \\ 0 & - \frac{t^2}{2!} \end{array} \right ) + \left ( \begin{array}{cc} 0 & \frac{t^3}{3!} \\ - \frac{t^3}{3!} & 0 \end{array} \right ) + \cdots $
$ = \left ( \begin{array}{cc} \sum_k \frac{(-1)^k t^{2k}}{(2k)!}& -\sum_k \frac{(-1)^k t^{2k+1}}{(2k+1)!} \\ \sum_k \frac{(-1)^k t^{2k+1}}{(2k+1)!} & \sum_k \frac{(-1)^k t^{2k}}{(2k)!} \end{array} \right ) $
$ = \left ( \begin{array}{cc} \cos(t) & -\sin(t) \\ \sin(t) & \cos(t) \end{array} \right ) $
And what do you know? Its our favourite rotation matrix!

But wait, there’s more… Let $\textstyle U(t) = \exp(Ht)$ and consider $\textstyle U'(t)$ we have:

$ U'(t) = \left ( \begin{array}{cc} \frac{d}{dt} \cos(t) & -\frac{d}{dt} \sin(t) \\ \frac{d}{dt} \sin(t) & \frac{d}{dt} \cos(t) \end{array} \right ) $
$ = \left ( \begin{array}{cc} -\sin(t) & -\cos(t) \\ \cos(t) & -\sin(t) \end{array} \right ) $
But we also have:
$U'(t) = \frac{d}{dt} \exp(Ht) = H \exp(Ht)$

And indeed:

$\left ( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right ) \left ( \begin{array}{cc} \cos(t) & -\sin(t) \\ \sin(t) & \cos(t) \end{array} \right ) = \left ( \begin{array}{cc} -\sin(t) & -\cos(t) \\ \cos(t) & -\sin(t) \end{array} \right ) $

This is, of course a special case of something much more general. The set of $\textstyle n$ by $\textstyle n$ anti-symmetric matrices form a Lie algebra with the commutator as bracket.

The exponential of an anti-symmetric matrix is always orthogonal. That is, the associated Lie group is the group of orthogonal matrices.

A Lie group is also a smooth manifold, and as such has a tangent space. The tangent space at the identity is precicely the Lie algebra.

Expanding $\textstyle \sin$ and $\textstyle \cos$ to first order, we get:

$ \left ( \begin{array}{cc} \cos(d\theta) & -\sin(d \theta) \\ \sin(d\theta) & \cos(d\theta) \end{array} \right) = \left ( \begin{array}{cc} 1 & -d\theta \\ d\theta & 1 \end{array} \right) = 1 + d\theta H $

In other words, the matrix:

$H = \left ( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right )$
lives in the Lie algebra of the orthogonal group and can be thought of as an infintesimal generator for the two by two rotations.

Now consider the action of $\textstyle U(t)$ on the following matrix representing a hyperbola in projective space:

$ M = \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{array} \right ) $

As we saw earlier:

$M(t) = U(t)^T M U(t) = \left( \begin{array}{ccc} \cos (2 t ) & -\sin (2 t ) & 0 \\ -\sin (2 t ) & -\cos (2 t ) & 0 \\ 0 & 0 & -1 \end{array} \right)$

What happens if we differentiate this action? Of course we have:

$ M'(t) & = \left ( \begin{array}{ccc} \frac{d}{dt} \cos (2 t ) & - \frac{d}{dt}\sin (2 t ) & 0 \\ - \frac{d}{dt}\sin (2 t ) & - \frac{d}{dt}\cos (2 t ) & 0 \\ 0 & 0 & 0 \end{array} \right ) $
$ = \left ( \begin{array}{ccc} -2\sin (2 t ) & -2\cos (2 t ) & 0 \\ -2\cos (2 t ) & 2 \sin (2 t ) & 0 \\ 0 & 0 & 0 \end{array} \right) $

But we also have:

$M'(t) = U(t)^T M U'(T) + U'(t)^T M U(t)$
Now, keeping in mind that $\textstyle H^T = -H$ , and that $\textstyle H$ commutes with $\textstyle U(t)$ , this gives us:
$ M'(t) & = U(t)^T M H U(t) - U(t) H M U(t) $
$ = M(t) H - H M(t) $
$ = [M(t), H] $

Indeed:

$ M(t) H - H M(t) = $
$ \left( \begin{array}{cc} \cos (2 t ) & -\sin (2 t ) \\ -\sin (2 t ) & -\cos (2 t ) \\ \end{array} \right ) \left ( \begin{array}{cc} 0 & -1 \\ 1 & 0 \\ \end{array} \right ) - \left ( \begin{array}{cc} 0 & -1 \\ 1 & 0 \\ \end{array} \right ) \left( \begin{array}{cc} \cos (2 t ) & -\sin (2 t ) \\ -\sin (2 t ) & -\cos (2 t ) \\ \end{array} \right) $
$ = \left( \begin{array}{cc} -\sin (2 t ) & -\cos (2 t ) \\ -\cos(2 t ) & \sin (2 t ) \\ \end{array} \right ) - \left ( \begin{array}{cc} \sin (2 t ) & \cos (2 t ) \\ \cos(2 t ) & -\sin (2 t ) \\ \end{array} \right ) $
$ = \left( \begin{array}{cc} -2\sin (2 t ) & -2\cos (2 t ) \\ -2\cos(2 t ) & 2\sin (2 t ) \\ \end{array} \right ) $

Its interesting to see that when $\textstyle U(t)$ acts by conjugation, the derivative of this action is the commutator with the infintessimal generator $\textstyle H$ .

Matrices and Determinants

Posted in Robin on September 2nd, 2010 by Robin – Be the first to comment

Let $\textstyle \mathbf{A}$ denote an invertible $\textstyle n \times n$ matrix, and let $\textstyle \mathbf{B}$ denote its inverse.
Suppose that we are given a column vector $\textstyle \mathbf{y}$ and that we wish to solve the equation $\textstyle \mathbf{A} \mathbf{x} = \mathbf{y}$ for the unknown vector $\textstyle \mathbf{x}$ .

Since $\textstyle \mathbf{A}$ is invertible with inverse $\textstyle \mathbf{B}$ , this is equivalent to:

$\mathbf{x} = \mathbf{B} \, \mathbf{y}$
In co-ordinates:
$x_k = \sum_j b_{kj} \, y_j$
This would be great if we had a nice expression for the inverse of a matrix.

Now, let $\textstyle \{ \mathbf{c_1}, \mathbf{c_2}, \ldots \mathbf{c_n} \}$ denote the columns of $\textstyle \mathbf{A}$ .
That is:

$\mathbf{c_k} = \begin{bmatrix} a_{1k} \\ a_{2k} \\ \cdots \\ a_{nk} \end{bmatrix}$
If $\textstyle \{\mathbf{e_1}, \mathbf{e_2}, \ldots, \mathbf{e_n}\}$ denotes the standard basis then:
$\mathbf{c_k} = \mathbf{A} \, \mathbf{e_k}$
That is, the columns of the matrix $\textstyle \mathbf{A}$ are the images of the standard basis vectors.

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

$\mathbf{y} = y_1 \mathbf{e_1} + y_2 \mathbf{e_2} + \cdots + y_n \mathbf{e_n}$
To solve the equation $\textstyle \mathbf{A} \mathbf{x} = \mathbf{y}$ for $\textstyle x$ we must find unknowns $\textstyle \{x_1, x_2, \ldots, x_n \}$ such that:
$\mathbf{y} = x_1 \mathbf{c_1} + x_2 \mathbf{c_2} + \cdots x_n \mathbf{c_n}$

In other words, we are trying to find the co-ordinates of the vector $\textstyle \mathbf{y}$ in terms of a new basis.

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

$ \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{i-1}} & \mathbf{y} & \mathbf{c_{i+1}} & \ldots & \mathbf{c_n} \end{array} \right ] \\ = \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{i-1}} & \sum_k x_k \, \mathbf{c_k} & \mathbf{c_{i+1}} & \ldots & \mathbf{c_n} \end{array} \right ] $
$ = \sum_k x_k \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{i-1}} & \mathbf{c_k} & \mathbf{c_{i+1}} & \ldots & \mathbf{c_n} \end{array} \right ] $
$ = x_i \det \mathbf{A} $

Let us now rewrite the equation $\textstyle \mathbf{Ax} = \mathbf{y}$ as the following “formal” determinant $\textstyle \mathbf{F}$ , which has entries in the first row the standard basis vectors, and additional “projective symbol” $\textstyle \mathbf{z}$ :

$\mathbf{F} = \det \left [ \begin{array}{c:c:c:c|c} \mathbf{e_1} & \mathbf{e_2} & \cdots & \mathbf{e_n} & \mathbf{z} \\ \hline a_{11} & a_{12} & . & a_{1n} & y_1 \\ a_{21} & a_{22} & . & a_{2n} & y_2 \\ . & . & . & . & . \\ a_{n1} & a_{n2} & . & a_{nn} & y_n \\ \end{array} \right ]$

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

$ = \sum_k (-1)^{k+1} \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{k-1}} & \mathbf{c_{k+1}} & \ldots & \mathbf{c_n} & \mathbf{y} \end{array} \right ]\mathbf{e_k} + (-1)^{n+1}\det \mathbf{A} \, \mathbf{z} $
$= (-1)^{n+1} \sum_k \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{k-1}} & \mathbf{y}& \mathbf{c_{k+1}} & \ldots & \mathbf{c_n} \end{array} \right ]\mathbf{e_k} + (-1)^{n+1}\det \mathbf{A} \, \mathbf{z} $
$= (-1)^{n+1} \sum_k x_k \det(\mathbf{A}) \mathbf{e_k} + (-1)^{n+1}\det \mathbf{A} \, \mathbf{z} $
which after “deprojectivizing” gives us exactly the vector $\textstyle \mathbf{x}$ which we were searching for.

Next, by expanding $\textstyle \det \left [ \begin{array}{c|c|c|c|c|c|c} \mathbf{c_1} & \ldots & \mathbf{c_{k-1}} & \mathbf{y}& \mathbf{c_{k+1}} & \ldots & \mathbf{c_n} \end{array} \right ]$ along the $\textstyle k$ -th column, we obtain:

$x_k = \sum_i (-1)^{i+k} y_i \mathbf{A_{ik}}$
where $\textstyle \mathbf{A_{rc}}$ denotes the determinant of the minor obtained from $\textstyle \mathbf{A}$ by removing the $\textstyle r$ -th row and the $\textstyle c$ -th column. From which we recover the well-known formula for the inverse of a matrix:

$\mathbf{A^{-1}} = \left (\frac{(-1)^{i+j}\mathbf{A_{ji}}}{\mathbf{\det(A)}} \right )_{i,j=1 \ldots n}$

Special Relativity and Hyperbolae

Posted in Robin on August 27th, 2010 by Robin – Be the first to comment

The matrix for the Lorenz Transformation, in one space dimension and one time dimension (with $\textstyle c=1$ ) is given by:

$L_v = \left ( \begin{array}{cc} \frac{1}{\sqrt{1 - v^2}} & \frac{v}{\sqrt{1 - v^2}} \\ \frac{v}{\sqrt{1 - v^2}} & \frac{1}{\sqrt{1 - v^2}} \end{array}\right )$

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:

$R_\theta = \left ( \begin{array}{cc} \cos(\theta) & - \sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array}\right )$

Consider a right angled triangle with sides lengths $\textstyle 1$ , $\textstyle x$ and $\textstyle \sqrt{1+x^2}$ . If you remember the definition of your basic trigonometric functions, as well as Pythagorus’ theorem, then you will “see” that we have:

$ \cos(\arctan(x)) = \frac{1}{\sqrt{1 + x^2}} $
$ \sin(\arctan(x)) = \frac{x}{\sqrt{1 + x^2}} $

This gives us the following alternative parameterization for the rotation matrices, where $\textstyle v = \tan(\theta)$ :

$R_v = \left ( \begin{array}{cc} \frac{1}{\sqrt{1 + v^2}} & \frac{-v}{\sqrt{1 + v^2}} \\ \frac{v}{\sqrt{1 + v^2}} & \frac{1}{\sqrt{1 + v^2}} \end{array}\right )$
It looks rather like the Lorenz transformation, doesn’t it? Though not quite.

If you recall now the definition of the hyperbolic trigonometric functions, you will “see” that $\textstyle \cos(i x) = \cosh(x)$ and $\textstyle \sin(i x) = i \sin(x)$ , and as a consequence, we have:

$ \cosh(\tanh^{-1}(x)) = \frac{1}{\sqrt{1-x^2}} \\ $
$ \sinh(\tanh^{-1}(x)) = \frac{x}{\sqrt{1-x^2}} $

This in turn gives us an alternative parameterization for the Lorenz Transformation, where $\textstyle v = \tan(\phi)$ :

$L_\phi = \left ( \begin{array}{cc} \cosh(\phi) & \sinh(\phi) \\ \sinh(\phi) & \cosh(\phi) \end{array}\right )$

The upshot of this is that if you are willing to work over $\textstyle \mathbb{C}$ rather than over $\textstyle \mathbb{R}$ , 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.

$ \left ( \begin{array}{cc} \cos(i \theta) & - \sin(i \theta) \\ \sin(i \theta) & \cos(i \theta) \end{array}\right ) \left ( \begin{array}{c} x \\ i t \end{array} \right ) = \left ( \begin{array}{c} x \cos(i \theta) - i t \sin(i \theta) \\ x \sin(i \theta) + i t \cos(i \theta) \end{array} \right ) $
$ = \left ( \begin{array}{c} x \cosh(\theta) + t \sinh(\theta) \\ i(x \sinh(\theta) + t \cosh(\theta)) \end{array} \right ) $

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 $\textstyle A$ be the matrix representing a Minkowski bilinear form with one space dimension and one time dimension:

$A = \left ( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array} \right )$
Then any matrix $\textstyle M$ of the form:
$M = \frac{1}{\sqrt{1 - v^2}} \left ( \begin{array}{cc} 1 & v \\ v & 1 \end{array}\right )$
will have the property that:
$M^T A M = A$

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:

$N = \left ( \begin{array}{cc} \cos(\theta) & - \sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array}\right )$
has the property that:
$N^T I N = I$

In co-ordinates, if $\textstyle v_1 = (x_1, y_1)$ and $\textstyle v_2 = (x_2, y_2)$ represent two different particles in two dimensional space, then the Euclidean inner product is usually represented as:

$\langle v_1, v_2 \rangle = x_1 x_2 + y_1 y_2$

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” $\textstyle p_1 = (x_1, i t_1)$ and $\textstyle p_2 = (x_2, i t_2)$ is given by:

$\langle p_1, p_2 \rangle = x_1 x_2 + i^2 t_1 t_2 = x_1 x_2 - t_1 t_2$

Conic Sections and Projective Space

Posted in Robin on August 20th, 2010 by Robin – Be the first to comment

I’m sure you’ve all seen the equation of a circle before:

$x^2 + y^2 = 1$
You’ve probably also seen the equation of a hyperbola:
$xy = 1$
Or perhaps you’re more familliar with seeing the asymptotes at 45 degree angles to the co-ordinate axes, as in:
$x^2 - y^2 = 1$

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

$ \left [ \begin{array}{ccc}x & y & 1 \end{array} \right ] \left [ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{array} \right] \left [ \begin{array}{c} x \\ y \\ 1\end{array} \right] =0 $

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

$A_R = \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & -R^2 \end{array} \right]$

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

$A_R = \left [ \begin{array}{ccc} 0 & 1/\sqrt 2 & 0 \\ 1/\sqrt 2 & 0 & 0 \\ 0 & 1 & -1 \end{array} \right]$
while the second hyperbola, with asymptotes at 45 degrees, corresponds to the matrix:
$A_R = \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 1 & -1 \end{array} \right]$

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

$ \left( \begin{array}{ccc} \cos (\theta ) & \sin (\theta ) & 0 \\ -\sin (\theta ) & \cos (\theta ) & 0 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{array} \right) \left( \begin{array}{ccc} \cos (\theta ) & -\sin (\theta ) & 0 \\ \sin (\theta ) & \cos (\theta ) & 0 \\ 0 & 0 & 1 \end{array} \right) $
$ =\left( \begin{array}{ccc} \cos ^2(\theta )-\sin ^2(\theta ) & -2 \cos (\theta ) \sin (\theta ) & 0 \\ -2 \cos (\theta ) \sin (\theta ) & \sin ^2(\theta )-\cos ^2(\theta ) & 0 \\ 0 & 0 & -1 \end{array} \right) \\ $
$= \left( \begin{array}{ccc} \cos (2 \theta ) & -\sin (2 \theta ) & 0 \\ -\sin (2 \theta ) & -\cos (2 \theta ) & 0 \\ 0 & 0 & -1 \end{array} \right) $

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:

$T_{a,b} = \left [ \begin{array}{ccc} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 1 \end{array}\right ]$

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

$A = \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{array} \right]$
and applying the following similarity transform:

$ \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -a & -b & 1 \end{array}\right ] \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{array} \right] \left [ \begin{array}{ccc} 1 & 0 & -a \\ 0 & 1 & -b \\ 0 & 0 & 1 \end{array} \right] $
$= \left [ \begin{array}{ccc} 1 & 0 & -a \\ 0 & 1 & -b \\ -a & -b & -1+a^2+b^2 \end{array} \right]$
We obtain the matrix for a circle of radius one, centered at the point $\textstyle (a,b)$ . The following code will let you play around with this:

  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”

$ \left( \begin{array}{ccc} \cos (\theta ) & 0 & -\sin (\theta ) \\ 0 & 1 & 0 \\ \sin (\theta ) & 0 & \cos (\theta ) \end{array} \right) $

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

$ \left [ \begin{array}{ccc}x & y & z \end{array} \right ] \left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{array} \right] \left [ \begin{array}{c} x \\ y \\ z\end{array} \right] =0 $

By setting $\textstyle z=1$ 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 $\textstyle z=1$ plane gives a circle, while the $\textstyle x=1$ plane gives a hyperbola. Our “projective rotation” smoothly rotates the $\textstyle z$ axis to the $\textstyle x$ axis.

Translations as Projective Transformations

Posted in Robin on August 11th, 2010 by Robin – Be the first to comment

You probably already know that in two dimensional space, the geometric act of rotating a vector through a given angle can be represented algebraically by the matrix:

$R_{\theta} = \left [ \begin{array}{cc} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array} \right ]$

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 $\textstyle \mathbb{R}^3$ intersects the unit sphere in exactly two points.

Algebraically, it is the set of triples $\textstyle [x:y:z]$ under the equivalence relation $\textstyle [\lambda x: \lambda y: \lambda z] \sim [x:y:z]$ for all $\textstyle \lambda \neq 0$ .

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 $\textstyle z=1$ sitting inside $\textstyle \mathbb{R}^3$ and notice how any line passing through the origin, which does not lie in the two dimensional subspace spanned by the $\textstyle x$ and $\textstyle y$ directions, intersects this plane in exactly one point.

Working with the algebraic definition, a two dimensional projective transformation is just a $\textstyle 3$ by $\textstyle 3$ 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 $\textstyle (x,y)$ to the new point $\textstyle (x + 3, y-2)$ 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:

$(x,y) \mapsto [x:y:1]$

The “inverse” of this embedding is the map:

$[x:y:z] \mapsto (x/z, y/z)$
I say “inverse” in inverted commas, because this map is not defined everywhere. In particular its not defined when $\textstyle z=0$ .

Alternatively, if you have trouble visualizing projective space, just imagine embedding $\textstyle \mathbb{R}^2$ into $\textstyle \mathbb{R}^3$ as the hyperplane given by the equation $\textstyle z=1$ . 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:

$M = \left [ \begin{array}{ccc} 1 & 0 & 2 \\ 0 & 1 & -3 \\ 0 & 0 & 1 \end{array} \right ]$
(or if you prefer, just think of it as a regular three dimensional transformation, which happens to map the hyperplane $\textstyle z=1$ back to itself)

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

$\left [ \begin{array}{ccc} 1 & 0 & 2 \\ 0 & 1 & -3 \\ 0 & 0 & 1 \end{array} \right ] \left [ \begin{array}{c} x \\ y \\ 1 \end{array} \right ] = \left [ \begin{array}{c} x + 2 \\ y - 3 \\ 1 \end{array} \right ] $

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 $\textstyle x,y$ plane they will reach the same point at infinity.

Back from the Dead

Posted in Robin on August 5th, 2010 by Robin – Be the first to comment

This blog has been dead for some time, but since I am now officially on the job market, I have decided to re-open it. I plan to post something new at least once a week.

Data Mining

Posted in Links, Robin on January 28th, 2010 by Robin – Be the first to comment

For anybody who is interested, here are two online video lecture series from Stanford University:

Statistical Aspects of Data Mining

Machine Learning

Also, the data set for the netflix prize.

Subscribe: Entries | Comments
Search for:
Recent Posts
Math
Meta
Calendar

January 2012

M T W T F S S

« Oct

1

2 3 4 5 6 7 8

9 10 11 12 13 14 15

16 17 18 19 20 21 22

23 24 25 26 27 28 29

30 31

January 2012
M	T	W	T	F	S	S
« Oct
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Recent Posts

Math

Meta

Calendar