Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Powers of a non-diagonalizable matrix?

  1. May 25, 2005 #1
    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?
  2. jcsd
  3. May 25, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
    Last edited: May 25, 2005
  4. May 25, 2005 #3
    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?
  5. May 25, 2005 #4
    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).
    Last edited: May 25, 2005
  6. May 25, 2005 #5
    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. :smile:
  7. May 25, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  8. May 26, 2005 #7
    Uhm..not really. :tongue2: 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%)

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook