# Matrix multiplication

1. Nov 15, 2013

### ajayguhan

1. The problem statement, all variables and given/known data

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

Find A^50

2. Relevant equations

3. 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

2. Nov 15, 2013

### 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 $A=C B C^{-1}$ then is very easy to prove that:
$A^{n}=C B^{n} C^{-1}$
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:
$X^{n}=m_{A} (X) P(X)+a_{n}X^{2}+b_{n}X+c_{n}$
(By the division algorithm) so you can compute any power as a linear combination of $A^{2}$, $A$ and $Id_{3}$, because evaluated in any multiple of $m_{A}$ 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 whats the 50th power of that matrix.

Last edited: Nov 15, 2013
3. Nov 16, 2013

### Ray Vickson

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
$$f(A) = E_1 f(-1) + E_2 f(1) + E_3 f'(1)$$
where the matrices E_i are the same for any function f. We can determine the E_i from a few powers of A:
$$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$$
So, if you can compute A^2 you can solve for E_1, E_2, E_3, then easily compute
$$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$$
for any n whatsoever.

4. Nov 16, 2013

### D H

Staff Emeritus
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$ ?

5. Nov 16, 2013

### SqueeSpleen

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

Last edited: Nov 16, 2013
6. Nov 16, 2013

### D H

Staff Emeritus
You don't even need to do that, SqueeSpleen. A100000000000 is an easy calculation.