Closed-form expressions: the "Ladders" of math

            In order to find the probability of completing the game in a certain number of moves, we have to make a 101 by 101 matrix, giving us a total of 101 * 101 = 10201 entries. However, thus far, we have really only cared about one entry: the entry that gives the probability of moving from the first square to the last square. This means that we have 10200 matrix entries that are essentially meaningless. A natural question, therefore, is can we somehow ignore the information that doesn't matter to us and thereby simplify the process of finding out what does matter?

            Unfortunately, we can’t just start cutting away at rows and columns of the transition matrix and expect the entry we care about to remain unchanged. It’s the intermediate steps that ultimately determine how we get from point A to point B. If we want to find a way to simplify it, we have to look for more general shortcuts in matrix multiplication. One solution is to see if there exists a “closed form” expression for the value of an entry in a matrix as that matrix is raised to various powers. What exactly does that mean?

            Consider the following example. Suppose we wanted to find the sum of the first one hundred positive integers, that is, the value of 1 + 2 + 3 + … + 100. We could go about this problem by adding the terms individually (1 plus 2 is 3, 3 plus 3 is 6, 6 plus 4 is ten…), but that would clearly take a while. However, there is a shortcut. It can be shown that the sum of the first n positive integers is equal to [(n)(n+1)]/2. The sum of the first one hundred integers is therefore equal to (100)(101)/2, or 5050. [(n)(n+1)]/2 would be considered a closed form expression for the sum of the first n integers since it allows us to perform an otherwise complicated calculation in one simple step by plugging in a value for one variable.

            So, can we do the same thing for matrices? Well, in some cases, certainly. If we have a matrix filled entirely with 0's, we can determine the value for any given entry in that matrix if it’s raised to a power: it’s always 0. Of course, that trivial case doesn't help too much. Can we do the same for a matrix whose entries change as it’s raised to various powers? Well, here’s one I found. Let’s call it M:

            Now see what happens as we raise M to a few different powers:

            Do you see the pattern? The value in the bottom-left corner is always equal to (1/2) times the power that the matrix is raised to and all the other values remain constant. Thus, we can determine the value of the entries as M is raised to some positive integral power without actually multiplying M by itself over and over again. Of course, this is still a rather simple case and doesn't provide us with some general pattern that can be applied to other, more complicated matrices. I did some extensive Google searching to see what sort of matrices have these convenient closed-form expressions, and unfortunately I couldn't find anything that would be applicable to the behemoth transition matrix for Chutes and Ladders (if Google doesn't have the solution, chances are it’s time to throw in the towel). I will keep this question in the back of my head as I keep going on with this project, but at this point it doesn't look like there is a simple solution (I could see what happens if I replace the numbers with variables in the 101 by 101 matrix, but… chances are that won’t be useful. Try it with a 2 by 2 matrix and you’ll see why!).