Matrix Multiplication: Finding A^50 with a Shortcut Method

[ajayguhan]

Homework Statement

A=[1 0 0]
[1 0 1]
[0 1 0]

Find A^50

Homework Equations

The Attempt at a Solution

I'm sure that we can't multiply it 50 times...it's a tedious process , there must be a short cut

 

[SqueeSpleen]

What where you studying when you found this problem? (It's important to know it so I can know what level of advice can I give you).
If it was taken from a Linear Algebra course similar to the one I had you could solve it doing this:
If [itex]A=C B C^{-1}[/itex] then is very easy to prove that:
[itex]A^{n}=C B^{n} C^{-1}[/itex]
There are some matrix's that are very easy to power, they are Jordan Decomposition
Do you know what's Jordan Decomposition?
Other way to solve it (probably easy) could be to apply the Hamilton-Cayley theorem.
First you compute the minimal polynomial of the matrix.
You have:
[itex]X^{n}=m_{A} (X) P(X)+a_{n}X^{2}+b_{n}X+c_{n}[/itex]
(By the division algorithm) so you can compute any power as a linear combination of [itex]A^{2}[/itex], [itex]A[/itex] and [itex]Id_{3}[/itex], because evaluated in any multiple of [itex]m_{A}[/itex] the matrix A is zero.

If it isn't from a linear Algebra Course and you don't know the Hamilton-Cayley Theorem the only hint I can give to you is to compute the first few (4-6) powers, try to see a patern, prove it and use it to show what's the 50th power of that matrix.

 

[Ray Vickson]

Homework Statement

A=[1 0 0]
[1 0 1]
[0 1 0]

Find A^50

Homework Equations

The Attempt at a Solution

I'm sure that we can't multiply it 50 times...it's a tedious process , there must be a short cut

If you know about eigenvalues, you can easily determine that theeigenvalues of A are -1 and 1 (multiplicity 2). It follows from the Jordan Canonical form that for any polynomial function f(x) we have
[tex] f(A) = E_1 f(-1) + E_2 f(1) + E_3 f'(1)[/tex]
where the matrices E_i are the same for any function f. We can determine the E_i from a few powers of A:
[tex] f(x) = x^0 = 1 \Longrightarrow A^0 = I = E_1 (-1)^0 + E_2 1^0 \\
f(x) = x \Longrightarrow A^1 = A = E_1(-1)^1 + E_2 1^1 + E_3 1^0 \\
f(x) = x^2 \Longrightarrow A^2 = E_1 (-1)^2 + E_2 1^2 + E_3 2 \cdot 1^1[/tex]
So, if you can compute A^2 you can solve for E_1, E_2, E_3, then easily compute
[tex] A^n = E_1 (-1)^n + E_2 1^n + E_3 n 1^{n-1} = (-1)^n E_1 + E_2 + n E_3[/tex]
for any n whatsoever.

 

[D H]

I'm sure that we can't multiply it 50 times...it's a tedious process , there must be a short cut

Another way to write ##A^{50}## is ##(A^2)^{25}##. What's ##A^2## ? ##A^4 = (A^2)^2## ? ##A^6 = (A^2)^3## ? Do you see a pattern emerging? Can you prove that this pattern is valid for all ##A^{2n}=(A^2)^n## ?

 

[SqueeSpleen]

A more computational way would be to compute:
[itex]A^{2}, A^{4}, A^{8}, A^{16}, A^{32}[/itex]
And do:
[itex]A^{50}=A^{32} \cdot A^{16} \cdot A^{2}[/itex]
You only have to do 7 products.

 

[D H]

You don't even need to do that, SqueeSpleen. A^100000000000 is an easy calculation.