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!

Proof Involving Matrix Polynomials and Matrix Multiplication

  1. Sep 26, 2012 #1
    1. The problem statement, all variables and given/known data

    Let [itex]A[/itex] be an [itex]nxn[/itex] matrix, and [itex]C[/itex] be an [itex]mxm[/itex] matrix, and suppose [itex]AB = BC[/itex].

    (a) Prove the following by induction: For every [itex]n∈ℕ[/itex], [itex](A^n)B = B(C^n)[/itex]. What property of matrix multiplication do you need to prove this?

    2. Relevant equations

    The four basic properties of matrix multiplication discussed in my course are

    1. Distributive: [itex](A + B)C = AC + BC[/itex] and [itex]C(A + B) = CA + CB[/itex]
    2. Scalar Commutativity: [itex](tA)B = t(AB) = A(tB)[/itex]
    3. Associative: [itex]A(BC) = (AB)C[/itex]

    3. The attempt at a solution

    If [itex]n = 1[/itex], then [itex](A^n)B = B(C^n)[/itex] becomes [itex](A^1)B = B(C^1)[/itex] which is[itex] AB = BC[/itex] which is supposed to be true.

    Assume [itex](A^n)B = B(C^n)[/itex] is true for [itex]n = k[/itex]. Then [itex](A^k)B = B(C^k)[/itex] is true.

    Prove [itex](A^n)B = B(C^n)[/itex] is true for [itex]n = k + 1[/itex].

    [itex](A[/itex]k+1[itex])B = B(C[/itex]k+1[itex]) ⇒ (A(A^k))B = B(C(C^k))[/itex]

    I'm not really sure how to proceed. I tried rewriting the matrix products as the summations of the products of their entries, but that didn't seem to get me anywhere. I know that I have to relate the equation when [itex]n = k + 1[/itex] to the equation when [itex]n = k[/itex] as part of induction, but I'm still stuck.
     
  2. jcsd
  3. Sep 26, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Your problem is not a lack of understanding about matrix products, etc., but a very basic lack of understanding of what *induction* is. I am going to ask you a question: do you actually know how induction is supposed to work? If you say YES, could you explain very briefly WHAT form you think such arguments take?

    RGV
     
    Last edited: Sep 26, 2012
  4. Sep 26, 2012 #3
    No. I do not know what induction really is. My instructor only really gave one example quickly. I think he also mentioned that we should have already know what it was, but I did not learn it in AP Calculus BC.
     
  5. Sep 26, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    There are numerous on-line sources that take you through some examples using induction. See,. eg., http://www.themathpage.com/aprecalc/mathematical-induction.htm or
    http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html or
    http://www.math.utah.edu/mathcircle/notes/induction.pdf . The first one is easiest, the second one is a bit harder and the third one is quite challenging.

    RGV
     
  6. Sep 27, 2012 #5
    Hey Ray,

    I'm interested in solving this problem too. If we are given the base case scenario (n=1) as true, can we use that to prove the n=k+1 case is true (in addition to using the n=k case)? The articles you linked typically avoided using the base case scenario in their proofs, but I find it difficult to use *only* the inductive assumption to prove the k+1 case. Is there some rule in induction that demands you can't use the base case, or not?
     
  7. Sep 30, 2012 #6
    Ray, I still don't know the answer to your question, but I think I know how to get the answer to the problem.

    If [itex]n = 1[/itex], then [itex](A^n)B = B(C^n)[/itex] becomes [itex](A^1)B = B(C^1)[/itex] which is[itex] AB = BC[/itex] which is supposed to be true.

    Assume [itex](A^n)B = B(C^n)[/itex] is true for [itex]n = k[/itex]. Then [itex](A^k)B = B(C^k)[/itex] is true.

    Prove [itex](A^n)B = B(C^n)[/itex] is true for [itex]n = k+1[/itex].

    [itex]A^kB = BC^k[/itex]
    [itex]A(A^kB) = A(BC^k)[/itex]
    [itex](AA^k)B = A(BC^k)[/itex]
    [itex]A[/itex]k+1[itex]B = A(BC^k)[/itex]
    [itex]A[/itex]k+1[itex]B = (AB)C^k[/itex]
    [itex]A[/itex]k+1[itex]B = (BC)C^k[/itex]
    [itex]A[/itex]k+1[itex]B = B(CC^k)[/itex]
    [itex]A[/itex]k+1[itex]B = BC[/itex]k+1

    [itex]A^kB = BC^k[/itex]
    [itex](A^kB)C = (BC^k)C[/itex]
    [itex](A^kB)C = B(C^kC)[/itex]
    [itex](A^kB)C = BC[/itex]k+1
    [itex]A^k(BC) = BC[/itex]k+1
    [itex]A^k(AB) = BC[/itex]k+1
    [itex](A^kA)B = BC[/itex]k+1
    [itex]A[/itex]k+1[itex]B = BC[/itex]k+1

    Therefore, [itex]A^nB = BC^n[/itex] is true for [itex]n = k+1[/itex], so [itex]A^nB = BC^n[/itex] is true for all [itex]n∈ℕ[/itex].

    The property of matrix multiplication needed for this proof is the associative law of matrix multiplication.
     
  8. Sep 30, 2012 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Yes: you have it now. You could shorten the argument a lot, but you do include all the needed steps.

    RGV
     
  9. Sep 30, 2012 #8
    May I ask what you meant by what "form" I think mathematical induction proofs take?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof Involving Matrix Polynomials and Matrix Multiplication
Loading...