• Support PF! Buy your school textbooks, materials and every day products Here!

Proof Involving Matrix Polynomials and Matrix Multiplication

  • #1

Homework Statement



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?

Homework 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]

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.
 

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement



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?

Homework 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]

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.
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:
  • #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.
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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
 
  • #5
52
0
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?
 
  • #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.
 
  • #7
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
Yes: you have it now. You could shorten the argument a lot, but you do include all the needed steps.

RGV
 
  • #8
May I ask what you meant by what "form" I think mathematical induction proofs take?
 

Related Threads on Proof Involving Matrix Polynomials and Matrix Multiplication

Replies
9
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
11
Views
7K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
3K
Replies
1
Views
606
Top