The Analogical Engine » Robin - A math and haskell blog

Robin

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.

Why’s (poignant) guide to Ruby

Posted in Links, Robin on January 21st, 2010 by Robin – Be the first to comment

Despite numerous other unfinished projects, I have decided to learn Ruby.

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.

Another nice analogy

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

The field with one element

A nice analogy

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

The Anatomy of Integers and Permutations.

The best part is – they even made it into a screen play.

Matrices in Haskell II

Posted in Robin on December 14th, 2009 by Robin – Be the first to comment

What’s the use of a matrix if you can’t find its characteristic polynomial? So, a very primitive haskell type for polynomials:

 
import MyPermutations
import MyMatrices
 
type Polynomial = [Int]
 
polySum :: Polynomial -> Polynomial -> Polynomial
polySum p q = if (length p >= length q) 
	then zipWith (+) p (q ++ [0,0..])
	else zipWith (+) q (p ++ [0,0..])
 
polyProduct :: Polynomial -> Polynomial -> Polynomial
polyProduct p q = map (polyProduct' p q) [0..((length p) + (length q) - 2)]
 
polyProduct' :: Polynomial -> Polynomial -> Int -> Int
polyProduct' p q k = sum [ ((p++[0,0..])!!i) * ((q++[0,0..])!!(k-i)) | 
                                         i <- [0..k] ]
 
.

Its not too much effort to generalize matrices with integer entries to matrices with polynomial entries:

 
type MatrixPoly = [[Polynomial]]
 
polyMatTranspose :: MatrixPoly -> MatrixPoly
polyMatTranspose ([]:xs) = []
polyMatTranspose xs = (map head xs):(polyMatTranspose (map tail xs))
 
polyMatProduct :: MatrixPoly -> MatrixPoly -> MatrixPoly
polyMatProduct m1 m2 = polyMatProduct' m1 (polyMatTranspose m2)
 
polyMatProduct' :: MatrixPoly -> MatrixPoly -> MatrixPoly
polyMatProduct' [] m = []
polyMatProduct' (r:rs) m = (polyFindRow' r m):(polyMatProduct' rs m)
 
polyFindRow' :: [Polynomial] -> MatrixPoly -> [Polynomial]
polyFindRow' r m = map (foldr (polySum) [0]) (map (zipWith (polyProduct) r) m)
 
polyDeterminant :: MatrixPoly -> Polynomial
polyDeterminant m = foldr (polySum) [0] (map (polyDetTerm m) 
                                           (allPermutedLists (length m)))
 
polyDetTerm :: MatrixPoly -> PermutedList -> Polynomial
polyDetTerm m p = map (\x -> (-1)^(sign p) * x) (polyDetTerm' m p)
 
polyDetTerm' :: MatrixPoly -> PermutedList -> Polynomial
polyDetTerm' _ [] = [1]
polyDetTerm' (m:ms) (p:ps) = polyProduct (m!!(p-1)) (polyDetTerm' ms ps)
 
polyMinor :: MatrixPoly -> [Int] -> [Int] -> MatrixPoly
polyMinor m rows cols = [ [ (m!!(i-1))!!(j-1) | j <- cols ] | i <- rows ] 
 
almostPolyMatInverse :: MatrixPoly -> MatrixPoly
almostPolyMatInverse m =  [ [ polyDeterminant $ polyMinor m (foo n i) (foo n j) 
                                        |  i <- [1..n] ] | j <- [1..n]]
	where n = length m
 
.

Finally:

 
charpoly :: Matrix -> Polynomial
charpoly m = polyDeterminant $ matPolyAdd (matToPolyMat m) 
      (diagonalPolyMat (take (length m) (repeat [0,-1])))
 
matToPolyMat :: Matrix -> MatrixPoly
matToPolyMat = map (map (\x -> [x])) 
 
matPolyAdd :: MatrixPoly -> MatrixPoly -> MatrixPoly
matPolyAdd = zipWith (zipWith (polySum))
 
diagonalPolyMat :: [Polynomial] -> MatrixPoly
diagonalPolyMat xs = diagonalPolyMat' (length xs) 1 xs
 
diagonalPolyMat' :: Int -> Int -> [Polynomial] -> MatrixPoly
diagonalPolyMat' _ _ [] = []
diagonalPolyMat' n k (x:xs) = ((take (k-1) (repeat [0])) ++ [x] 
         ++ (take (n-k) (repeat [0]))):(diagonalPolyMat' n (k+1) xs)
 
.

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

September 2010

M T W T F S S

« Aug

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

September 2010
M	T	W	T	F	S	S
« Aug
		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

Robin

Recent Posts

Math

Meta

Calendar