Proof Involving Matrix Polynomials and Matrix Multiplication

[Reckoning of Sand]

Homework Statement

Let A be an nxn matrix, and C be an mxm matrix, and suppose AB = BC.

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

Homework Equations

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

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

The Attempt at a Solution

If n = 1, then (A^n)B = B(C^n) becomes (A^1)B = B(C^1) which isAB = BC which is supposed to be true.

Assume (A^n)B = B(C^n) is true for n = k. Then (A^k)B = B(C^k) is true.

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

(A^k+1)B = B(C^k+1) ⇒ (A(A^k))B = B(C(C^k))

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 n = k + 1 to the equation when n = k as part of induction, but I'm still stuck.

 

[Ray Vickson]

Homework Statement

Let A be an nxn matrix, and C be an mxm matrix, and suppose AB = BC.

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

Homework Equations

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

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

The Attempt at a Solution

If n = 1, then (A^n)B = B(C^n) becomes (A^1)B = B(C^1) which isAB = BC which is supposed to be true.

Assume (A^n)B = B(C^n) is true for n = k. Then (A^k)B = B(C^k) is true.

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

(A^k+1)B = B(C^k+1) ⇒ (A(A^k))B = B(C(C^k))

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 n = k + 1 to the equation when n = k as part of induction, but I'm still stuck.

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

 

[Reckoning of Sand]

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.

 

[Ray Vickson]

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.

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

 

[jmcelve]

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?

 

[Reckoning of Sand]

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 n = 1, then (A^n)B = B(C^n) becomes (A^1)B = B(C^1) which isAB = BC which is supposed to be true.

Assume (A^n)B = B(C^n) is true for n = k. Then (A^k)B = B(C^k) is true.

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

A^kB = BC^k
A(A^kB) = A(BC^k)
(AA^k)B = A(BC^k)
A^k+1B = A(BC^k)
A^k+1B = (AB)C^k
A^k+1B = (BC)C^k
A^k+1B = B(CC^k)
A^k+1B = BC^k+1

A^kB = BC^k
(A^kB)C = (BC^k)C
(A^kB)C = B(C^kC)
(A^kB)C = BC^k+1
A^k(BC) = BC^k+1
A^k(AB) = BC^k+1
(A^kA)B = BC^k+1
A^k+1B = BC^k+1

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

The property of matrix multiplication needed for this proof is the associative law of matrix multiplication.

 

[Ray Vickson]

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 n = 1, then (A^n)B = B(C^n) becomes (A^1)B = B(C^1) which isAB = BC which is supposed to be true.

Assume (A^n)B = B(C^n) is true for n = k. Then (A^k)B = B(C^k) is true.

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

A^kB = BC^k
A(A^kB) = A(BC^k)
(AA^k)B = A(BC^k)
A^k+1B = A(BC^k)
A^k+1B = (AB)C^k
A^k+1B = (BC)C^k
A^k+1B = B(CC^k)
A^k+1B = BC^k+1

A^kB = BC^k
(A^kB)C = (BC^k)C
(A^kB)C = B(C^kC)
(A^kB)C = BC^k+1
A^k(BC) = BC^k+1
A^k(AB) = BC^k+1
(A^kA)B = BC^k+1
A^k+1B = BC^k+1

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

The property of matrix multiplication needed for this proof is the associative law of matrix multiplication.

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

RGV

 

[Reckoning of Sand]

May I ask what you meant by what "form" I think mathematical induction proofs take?