Powers of a non-diagonalizable matrix?

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?
 PhysOrg.com science news on PhysOrg.com >> Leading 3-D printer firms to merge in $403M deal (Update)>> LA to give every student an iPad;$30M order>> CIA faulted for choosing Amazon over IBM on cloud contract
 Recognitions: Homework Help Science Advisor 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.
 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?

Powers of a non-diagonalizable matrix?

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).
 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.
 Recognitions: Homework Help Science Advisor 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.
 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%)

 Similar discussions for: Powers of a non-diagonalizable matrix? Thread Forum Replies Calculus & Beyond Homework 3 Calculus & Beyond Homework 3 Calculus & Beyond Homework 1 Calculus & Beyond Homework 9 Linear & Abstract Algebra 6