Author |
Topic: Evaluate power of a matrix (Read 3314 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Evaluate power of a matrix
« on: Mar 14th, 2007, 12:45pm » |
 Quote  Modify
|
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).
|
|
 IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Evaluate power of a matrix
« Reply #1 on: Mar 14th, 2007, 1:26pm » |
Quote Modify
|
Hint: Diagonalize.
|
| « Last Edit: Mar 14th, 2007, 1:29pm by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Evaluate power of a matrix
« Reply #2 on: Mar 14th, 2007, 1:45pm » |
Quote Modify
|
f(n) = ([(5 + sqrt(37))/2)n - ((5 - sqrt(37))/2]n)/sqrt(37)
[ 3 f(n-1), f(n); 3 f(n), f(n+1) ]
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Evaluate power of a matrix
« Reply #3 on: Mar 15th, 2007, 2:37am » |
Quote Modify
|
[0 1]n
[3 5]
Isn't that a closed form?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Evaluate power of a matrix
« Reply #4 on: Mar 15th, 2007, 9:01am » |
Quote Modify
|
on Mar 15th, 2007, 2:37am, 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.
|
|
IP Logged |
|
|
|
JP05
Guest
|
|
Re: Evaluate power of a matrix
« Reply #5 on: Mar 17th, 2007, 8:53pm » |
Quote Modify
 Remove
|
You would think that
[0 1]n
[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
[3n 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?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Evaluate power of a matrix
« Reply #6 on: Mar 18th, 2007, 1:31am » |
Quote Modify
|
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 An = PVnP-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 v1, v2 are the roots of the quadratic v2 – (a+d)v + (ad – bc) = 0, and P has the following structure:
[ b b ]
[ v1–a v2–a ]
I did not check towr’s result thoroughly, but the expression for the eigenvalues indicates they are correct.
|
| « Last Edit: Mar 18th, 2007, 9:33am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Evaluate power of a matrix
« Reply #7 on: Mar 18th, 2007, 7:55am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JP05
Guest
|
|
Re: Evaluate power of a matrix
« Reply #8 on: Mar 18th, 2007, 9:03am » |
Quote Modify
Remove
|
Thanks for the correction. What I was thinking makes much more sense now.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Evaluate power of a matrix
« Reply #9 on: Mar 18th, 2007, 9:44am » |
Quote Modify
|
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..)
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Evaluate power of a matrix
« Reply #10 on: Mar 18th, 2007, 10:28am » |
Quote Modify
|
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 x2-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.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print