1
$\begingroup$

If $A$ and $B$ commute, then prove that so also do $A^m$ and $B^n$ for all positive integers $m$ and $n$.

My Proof

So we want to show that, for all positive integers $m$ and $n$, $A^mB^n = B^nA^m$.

Let $P(n,m) = A^mB^n$, and let $A$ and $B$ be $p \times p$ matrices.

$n,m = 1$: $P(1, 1) = AB = BA$ Since we assumed that $A$ and $B$ commute.

We first perform induction over $n$.

$n = k, m = 1$: $P(k, 1) = AB^k = B^kA$ This is the induction hypothesis.

$n = k + 1, m = 1$: $P(k + 1, 1) = (AB^k)(B)$ By the induction hypothesis.

$= A(B^kB)$ Since matrix multiplication is associative.

$= AB^{k + 1}$

Q.E.D.

We lastly perform induction over $m$.

$n = 1, m = k$: $P(1, k) = A^k B = BA^k$ This is the induction hypothesis.

$n = 1, m = k + 1$: $P(1, k + 1) = (A)(A^k B)$ By the induction hypothesis.

$= (AA^k)(B)$ Since matrix multiplication is associative.

$= A^{k + 1}B$

Q.E.D.

I would greatly appreciate it if people could please take the time to review my proof for correctness.


Since both of the answers posted so far have been down-voted, I'm going to assume that they're both incorrect and instead post my new proof.

My New Proof

Let $A$ and $B$ be $n \times n$ matrices.

For every positive integer $m$, $A^m$ and $B$ commute.

Let $P(m) = A^nB = BA^m$.

$m = 1$: $P(1) = AB = BA$ Since we assumed that $A$ and $B$ commute.

$P(m) = A^mB = BA^m$ This is the induction hypothesis.

$P(m + 1) = (A)(A^mB)$ Since $(A)(A^mB) = (AA^m)B = A^{m + 1}B$.

$= (A)(BA^m)$ By the induction hypothesis.

$= B(AA^m)$ Since we assumed that $A$ and $B$ are commutative.

$= BA^{m + 1}$ Q.E.D.

For every fixed $m$ and variable $n$, $B^nA^m = A^mB^n$.

$P(1) = BA^m = A^mB$

$P(n) = B^nA^m = A^mB^n$ This is the inductive hypothesis.

$P(n + 1) = (B)(B^nA^m)$ Since $(B)(B^nA^m) = (BB^n)A^m = B^{n + 1}A^m$, since matrix multiplication is associative.

$= (B)(A^mB^n)$ By the inductive hypothesis.

$= A^m(BB^n)$ Since we proved in the last inductive proof that $A^m$ and $B$ commute for all $m$.

$= A^mB^{n + 1}$ Q.E.D.

I would greatly appreciate feedback as to whether my new proof is correct.

$\endgroup$
7
  • $\begingroup$ In your induction over $n$ you got $P(k+1,1)=AB^{k+1}$, but that was the definition of $P(k+1,1)$. $\endgroup$
    – Nightgap
    Commented Nov 25, 2017 at 15:13
  • $\begingroup$ in the second induction you must assume that $n$ is arbitrary not =1 and use your first induction. $\endgroup$
    – YCB
    Commented Nov 25, 2017 at 15:15
  • $\begingroup$ As @Nightgap mentioned, you don't prove what you need to in your induction over $n$, or in fact over $m.$ The other problem is that you've only shown the result when one of $n$ or $m$ is $1$. You would need to show that for general $n,$ $P(n,k)=B^{n}A^{k}\Rightarrow P(n,k+1)=B^{n}A^{k+1}$ in order to prove it for all cases. $\endgroup$ Commented Nov 25, 2017 at 15:15
  • 1
    $\begingroup$ That's correct (and exactly what I said). I don't know why I got a downvote here. $\endgroup$
    – Nightgap
    Commented Nov 25, 2017 at 18:29
  • $\begingroup$ @Nightgap thanks for taking the time to respond. I wasn’t the one who down-voted any of the answers. I’d like to up-vote your answer, but It’s too unclear for me to understand if it’s correct. If someone else can corroborate the correctness of your answer, then I will up-vote it to cancel-out the down-vote. $\endgroup$ Commented Nov 25, 2017 at 18:33

3 Answers 3

1
$\begingroup$

You have to modify your second induction. Show for fixed $m$ that $A^kB^m=B^mA^k$ by induction over $k$.

For $k=1$ this is your first induction (if you correct it). For $k>1$ you get $A^kB^m=AA^{k-1}B^m=AB^mA^{k-1}$ by induction hypothesis. Now the case $k=1$ yields that this is equal to $B^mAA^{k-1}=B^mA^k$ which you wanted to show.

$\endgroup$
0
$\begingroup$

The result has little to do with matrices and it is no more difficult to prove the following more general result:

Proposition. Let $a$ and $b$ be elements of a semigroup $S$. If $a$ and $b$ commute, then the subsemigroup of $S$ generated by $a$ and $b$ is commutative.

In your case, it would prove for instance that the matrices $A^2B^3AB^2A$ and $BAB^2A^3$ commute.

Proof. The elements of the subsemigroup of $S$ generated by $a$ and $b$ can be represented by nonempty words on the alphabet $\{a, b\}$. We claim that if $u$ and $v$ are two nonempty words, then $uv = vu$ in $S$. Let us prove this result by induction on $n = |u| + |v|$ (here $|w|$ denotes the length of a word $w$).

If $n = 2$, then $(u,v) \in \{(a,a), (a,b), (b,a), (b,b)$} and the result is obvious since $ab = ba$. Suppose that the result holds for all $n \geqslant 2$ and that $|u| + |v| = n+1$. Without any loss of generality, we may assume that $|v| \leqslant |u|$ and $|u| \geqslant 2$, so that $u = u'c$, with $|u'| = |u|-1$ and $c$ is the last letter of $u$ (either $a$ or $b$). Now $$ uv = (u'c)v = u'(cv) \stackrel{\color{red}{(1)}}{=} u'(vc) = (u'v)c \stackrel{\color{red}{(2)}}{=} (vu')c = v(u'c) = vu $$ $\color{red}{(1)}$ By the induction hypothesis, $cv = vc$, since $|v| + |c| = 1 + |v| < |u| + |v| = n$.

$\color{red}{(2)}$ By the induction hypothesis, $vu' = u'v$, since $|u'| + |v| = (|u|-1) + |v| = n$.

$\endgroup$
-2
$\begingroup$

Your proof is incomplete. In second induction you should take $n = k'$. For $n = k', m = 1$ it is true from 1st induction and now you should prove for $n = k', m = k+1$ assuming it is true for $n = k', m= k$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .