1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Matrix multiplication

  1. Nov 15, 2013 #1
    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. jcsd
  3. Nov 15, 2013 #2
    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 whats the 50th power of that matrix.
     
    Last edited: Nov 15, 2013
  4. Nov 16, 2013 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Nov 16, 2013 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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## ?
     
  6. Nov 16, 2013 #5
    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.
     
    Last edited: Nov 16, 2013
  7. Nov 16, 2013 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You don't even need to do that, SqueeSpleen. A100000000000 is an easy calculation.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Matrix multiplication
  1. Matrix Multiplication (Replies: 12)

  2. Matrix multiplication (Replies: 3)

  3. Matrix Multiplication (Replies: 3)

Loading...