A Little Matrix Analysis and Ring Theory

  The partitioning of the transition matrix for the cat and mouse problem into a simple matrix sum and the multinomial expression for its powers made use of matrix analysis. A lot of the mathematics of linear algebra was developed during the 19th Century. The subject has grown more abstract over time and can be difficult for the uninitiated to follow. For a better understanding of the subject one can study the history of ring theory, Clifford algebras, the Cayley-Hamilton theorem, etc. The Cayley-Hamilton theorem allows one to write a matrix power as a polynomial of its lower powers. It applies if the order of the multiplications doesn't matter. The multinomial formula for the powers of P made use of the observation that the set of matrices U, V, X and W were closed under multiplication. The Cayley-Hamilton theorem doesn't apply to P in this case because of the cross product X but it does apply to U and V separately. Including X in the ring is not a major difficulty.

Formula for the Powers of the Cat & Mouse Transition Matrix

  I was able to derive a formula for the powers of part of the transition matrix for the cat and mouse problem by dividing it up into the sum of two matrices that have simple products. The transition matrix for the cat and mouse problem involves 7 states including the "exit" state but the state diagram can be broken up into two separate parts because two sets of states are mutually exclusive except for the "exit" state. So if we just consider the states 1, 2, 3 and 7 we get a 4x4 transition matrix P. This matrix can be written as a linear combination of two matrices, U and V, with P=U+0.5V. On multiplication we find that U²=U and we can define two other matrices X=UV and W=V² that can be used to find a simple multiplication table for the products of these four matrices.

We can then write each P^k as a linear combination of just three of these matrices. The functions odd(k) and even(k) allow us to select either V or W for the third matrix depending on whether k is odd or even. X is nearly identical with U but with the 1 replaced by a 0. We see from the formula that, for large k, P^k → U+X a matrix with all zeros except for 1s in the bottom row. Since the sum the initial probability vector, p_i, is 1 we find that the game always ends up in the same state, (U+X)p_i = (0,0,0,1), no matter what state the game starts in.

Streamlines for the Transition Matrix

  One can use matrix methods to simplify the expression P^k so that one does not have to do a large number of matrix multiplications. The result which is a consequence of factoring P into a product of a rotation and a contraction is,

 P^k = Κ + ρ^k [Η cos(k·theta) + Γ sin(k·theta)]
where Κ, Η and Γ are a set of matrices defined below. The expression can also be used to compute "streamlines" for the transition matrix using fractional values for k.

Starting at some initial point p^<0> on the edge of the probability state space or anywhere else one can compute the steps p^<k> for the integers k and then compute the streamlines as shown above. To get the coordinates of a point, (x,y), in the plane one needs to subtract the origin e^<0>=(1,0,0)^T which is the vertex at the lower left from p^<k> before calculating the projections onto the x and y axes of the plane.

One can also replace the matrices in φ by their product with p^<0> to get a vector equation for an individual streamline.

Factoring the Transition Matrix

  The transition matrix P used in the last two posts can be factored into a rotation, R, about the normal to the plane of the probability vectors followed by a radial contraction, V, in this plane. So we have P=V·R. To show that V is a contraction we can choose a set of unit vectors, the basis B, that are perpendicular to each other with two in the plane of the probability vectors and one perpendicular to it. The choice of the vectors in the plane is somewhat arbitrary. B^T·B shows the projection of each of the column vectors of B onto each other. The unit diagonals indicate that the magnitude of each is 1 and the 0 components tell us that the vectors are normal to each other. Multiplying B by V we see that the third vector of B which is normal to the plane is left unchanged. (V·B)^T·B indicates that the directions of the vectors in B are also left unchanged but the new vectors in the plane have their components parallel to the plane reduced in magnitude by the same factor, 0.854 showing that it is a contraction.

We see that R has the some of the properties of a rotation with its determinant |R|=1, its column vectors being unit vectors and perpendicular to each other and that they form a right handed set of vectors. One can see that R is a rotation in the plane of the probability vectors by computing R·B and comparing its column vectors with those of B by computing (R·B)^T·B. We see that the column vector B^<0> moves towards B^<1> and B^<1> moves towards -B^<0>. The angle of rotation is θ = -0.1 radians. By computing V·R we see that it is indeed equal to P.

  The rotation preserves the relative position of points in the plane of the probability vectors and the contraction preserves the relative directions of the points. The result is that the images of the border's triangle is always a triangle similar to it. The paths that the points follow are somewhat like those of a flow field.

Improved Transition Matrix Video

  I got a little more control over the video creation process and improved the Transition Matrix video in the last post. Each step in the video results from the multiplication of the previous set of positions by P. The power of P^k is shown in the upper left of the video. I'm using Mathcad 11 to do the plots and generate the videos in an .avi format and they are converted on upload to YouTube. The frame size chosen for the video was approximately 640 x 480. The video was recorded at 30 frames per second. There are two steps per second.

Visualizing the Action of a Transition Matrix

  An extension of the method used to find transition matrices was used to find one for a 3 state system.  Since the sum of a probability vector is 1 all possible probability vectors lie on a plane going through the unit position of the axes that represent the states of the system. Values were selected for the reduced matrix so that the initial changes were along the lines connecting the unit vectors of the axes of the coordinate system. The transition matrix found was:

When the unit vectors for the axes are taken as the initial states of the system the action of the transition matrix produces a set of points that spiral inwards to the stationary point (1/3,1/3,1/3).

To get a better picture of what the transition matrix does one can select a set of points along the border of the plane for the probability vectors and apply the transition matrix one step at a time. In this case the set of points spirals in towards the center maintaining their relative positions along the way. It might help to repeatedly click on the beginning of the progress bar while playing to restart the video.