# Proof Involving Matrix Polynomials and Matrix Multiplication

## 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 is$AB = 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 Helper
Dearly Missed

## 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 is$AB = 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

Last edited:
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
Homework Helper
Dearly Missed
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

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?

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 is$AB = 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+1$B = A(BC^k)$
$A$k+1$B = (AB)C^k$
$A$k+1$B = (BC)C^k$
$A$k+1$B = B(CC^k)$
$A$k+1$B = 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+1$B = 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
Homework Helper
Dearly Missed
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 is$AB = 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+1$B = A(BC^k)$
$A$k+1$B = (AB)C^k$
$A$k+1$B = (BC)C^k$
$A$k+1$B = B(CC^k)$
$A$k+1$B = 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+1$B = 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

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