wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Evaluate power of a matrix
        
(Message started by: Aryabhatta on Mar 14^th, 2007, 12:45pm)

Title: Evaluate power of a matrix
Post by Aryabhatta on Mar 14^th, 2007, 12:45pm

Let A be the 2x2 matrix

[0 1]
[3 5]

Let A(n) be the 2x2 matrix A^n (the nth power of A).

Find a closed form for A(n).

Title: Re: Evaluate power of a matrix
Post by Michael_Dagg on Mar 14^th, 2007, 1:26pm

Hint:[hide] Diagonalize.[/hide]

Title: Re: Evaluate power of a matrix
Post by towr on Mar 14^th, 2007, 1:45pm

[hide]f(n) = ([(5 + sqrt(37))/2)ⁿ - ((5 - sqrt(37))/2]ⁿ)/sqrt(37)

[ 3 f(n-1), f(n); 3 f(n), f(n+1) ][/hide]

Title: Re: Evaluate power of a matrix
Post by Grimbal on Mar 15^th, 2007, 2:37am

[0 1]n
[3 5]

Isn't that a closed form?

Title: Re: Evaluate power of a matrix
Post by Aryabhatta on Mar 15^th, 2007, 9:01am

on 03/15/07 at 02:37:13, Grimbal wrote:

[0 1]n
[3 5]

Isn't that a closed form?

I am not sure and maybe you are right, but you know what the intention is.

Title: Re: Evaluate power of a matrix
Post by JP05 on Mar 17^th, 2007, 8:53pm

You would think that

[0 1]ⁿ
[3 5]

is closed form but I bet it is not considered that because it does not provide a formula for the result.

I think the closed form answer is

[3ⁿ 0]
[0 1]

which I got from diagonalizing the original to

[3 0]
[0 1] and by multiplying it n times.

I know that any matrix that can be diagonalized can be recovered from any diagonalization from it and also from its identity.

Isn't this the ABCs of linear algebra?

Title: Re: Evaluate power of a matrix
Post by Barukh on Mar 18^th, 2007, 1:31am

The diagonalization of a square matrix A means finding two matrices P, V (the latter is the diagonal matrix) such that

A = PVP^-1.
From this identity immediately follows that Aⁿ = PVⁿP^-1, which is good since a power of a diagonal matrix is computed trivially.

As for the structure of matrices P, V: V has the eigenvalues of A on the diagonal; and P is comprised of eigenvectors of A. All this is IMHO not an ABC of linear algebra.

In the particular case of 2x2 matrix
[a b]
[c d]

the eigenvalues v₁, v₂ are the roots of the quadratic v² – (a+d)v + (ad – bc) = 0, and P has the following structure:

[ b b ]
[ v₁–a v₂–a ]

I did not check towr’s result thoroughly, but the expression for the eigenvalues indicates they are correct.

Title: Re: Evaluate power of a matrix
Post by towr on Mar 18^th, 2007, 7:55am

My method for finding the answer was different though. I just found a recurrence and proceeded to find the closed form of it. (Actually, I started with two recurrences)
You can just see what
[a b]
[c d] * A
does to a,b,c,d and work from there. Of course, the diagonalization method is more elegant.

Title: Re: Evaluate power of a matrix
Post by JP05 on Mar 18^th, 2007, 9:03am

Thanks for the correction. What I was thinking makes much more sense now.

Title: Re: Evaluate power of a matrix
Post by Aryabhatta on Mar 18^th, 2007, 9:44am

As towr points out, this is problem is solvable even if you do not know what diagonalization or eigenvalues etc mean.

It is always useful to attack a problem from different angles... (maybe not in this case, but..)

Title: Re: Evaluate power of a matrix
Post by ecoist on Mar 18^th, 2007, 10:28am

In this particular case, the given matrix A is the companion matrix of a monic polynomial, which polynomial has the negatives of its coefficients along the last row. Thus the polynomial is x²-5x-3. Let r and s be the roots of this polynomial. Then u=(1,r)^t and v=(1,s)^t are the eigenvectors of A. Hence, we can take Barukh's P as P=[v u] (Convenient way to prove that the Vandermonde matrix is nonsingular, btw!). Then

P^-1=
=1/(r-s)| r -1 |
|-s 1|.

(Sorry. Still haven't learned how to line things up.)