Powers of a non-diagonalizable matrix?

[TomMe]

Can anyone tell me if there's an algorithm to compute powers of a non-diagonalizable matrix?

I've been given this Markov-matrix:
1/2 1/4 1/4
0/1 1/2 1/4
1/2 1/4 1/2

and I have to find what happens over a long period of time, so calculate the matrix to the k-th power and then assume k = infinity.

I cannot diagonalize it because it only has 2 linear independent eigenvectors. I tried turning it into an upper-triangular matrix by changing to a basis with 2 independent eigenvectors and (0,0,1) but then I got stuck computing one entry of the new matrix because my knowledge of series is limited.

Any suggestions?

 

[mathwonk]

just glancing at it, it appears to go to zero over a long period of time.

e.g. one thing you can easily calculate is the determinant which seems to be 1/16. this means this matrix maps a unit cube into a parallelpiped of volume 1/16, and in general shrinks the volume of every block by 1/16.

so it shrinks things rather quickly.

 

[TomMe]

Well, actually there's a background on this matrix:

There's a lion that has 3 hunting grounds, and this lion moves between these grounds almost on a daily basis. This matrix depicts the probabilities of where the lion will move to next.

So suppose on monday he's at hunting ground number 1, the probabilities that he will move to the others the next day are in column 1.
The question here actually is: which ground will he be hunting on the most/least after a long period of time?

 

[Muzza]

Let A = your matrix, and let B = 4A. If one looks at various powers of B, then one might conjecture that the general form for B^n is

[x(n), x(n) - 1, x(n) - 1]
[y(n), y(n) + n + 1, y(n) + n]
[z(n), z(n) - n, z(n) - n + 1]

where x, y, and z are yet undetermined functions.

These undetermined functions all seem to be exponential, and I suppose that x(n) = 1/3 * 4^n + 2/3 (which is gnuplot's fit). No luck with the others though..

*edit* Oh, and of course one can derive recurrence equations for these functions easily since B^n = B * B^(n - 1).

x(n) = 4x(n - 1) - 2,
y(n) = 4y(n - 1) + 2n - 2,
z(n) = 4z(n - 1) - 2n + 4.

Which, after some thinking, seem pretty easy to solve (assume a solution of the form a * b^n + cn + d and then equate the coefficients).

 

[TomMe]

Thanks for your input. That's what I did at first, but I didn't quite see the relation between the entries, now I do.

To be honest, I don't really understand what you said after the *edit*, but I'll try to work it out.

One more thing, when I changed the basis, I came up with this upper-triangular matrix (if I did it right):

4 0 1/3
0 1 -1/3
0 0 1

Taking the powers of this matrix seems a lot easier to me. I found all the entries, except the (1,3) one:

[4^n, 0, ?]
[0, 1, -n/3]
[0, 0, 1]

I (think I) know the sum for the entry: 4/3 + 4²/3 +...+ 4^(k-1)/3 for the k-th power. If anyone could tell me a nice little formula for this, that would help me too.

 

[matt grime]

Yes, every matrix can be put in upper triangular form, and in particular jordan canonical form (assume we're over C) and its powers can be computed.

However, the sum you are asking for in the last sentence is just a geometric series. Surely you know the sum of a geometric progression.

 

[TomMe]

Uhm..not really. Yes, I've seen it in high school, but wasn't paying much attention back then. Now I'm doing some self study to take some exams next year, but haven't covered that topic yet.

Anyway, I think I've found yet a better way to solve this.
This matrix I started with has an eigenvalue 1, so that means that Ax = 1.x and thus there is an x for which the matrix doesn't change the solution, in other words the situation stabilizes into x.

With eigenvalue 1 comes an eigenvector r.(3,2,4), the sum of the elements must equal to 1: 3r + 2r + 4r = 1, so r = 1/9.
Solution: (33%,22%,44%)