Matrix Multiplication on Square Matrices over Ring with Unity is not Commutative

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R$ be a ring with unity.

Let $n \in \Z_{>0}$ be a (strictly) positive integer such that $n \ne 1$.

Let $\map {\mathcal M_R} n$ denote the $n \times n$ matrix space over $R$.


Then (conventional) matrix multiplication over $\map {\mathcal M_R} n$ is not commutative:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} n: \mathbf {A B} \ne \mathbf {B A}$


If $R$ is specifically not commutative, then the result holds when $n = 1$ as well.


Proof

The proof proceeds by induction.

For all $n \in \Z_{\ge 2}$, let $\map P n$ be the proposition:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} n: \mathbf {A B} \ne \mathbf {B A}$


Edge Cases

$n = 1$

Consider the case where $n = 1$.

Then:

\(\displaystyle \mathbf {A B}\) \(=\) \(\displaystyle a_{11} b_{11}\)
\(\displaystyle \mathbf {B A}\) \(=\) \(\displaystyle b_{11} a_{11}\)


and it follows that (conventional) matrix multiplication over $\map {\mathcal M_R} 1$ is commutative if and only if $R$ is a commutative ring.


$R$ not a Ring with Unity

Consider the case where $R$ is not a ring with unity, and is a general ring.

Let $R$ be the trivial ring.

From Matrix Multiplication on Square Matrices over Trivial Ring is Commutative:

$\forall \mathbf A, \mathbf B \in \map {\mathcal M_R} n: \mathbf {A B} = \mathbf {B A}$

Hence the result does not follow for all rings.


It is not established at this point on exactly which rings (conventional) matrix multiplication $\map {\mathcal M_R} n$ commutes.

However, the existence of just one such ring (the trivial ring) warns us that we cannot apply the main result to all rings.


Basis for the Induction

From Matrix Multiplication is not Commutative/Order 2 Square Matrices, it is seen that there exist $2 \times 2$ matrices that don't commute under matrix multiplication, thus proving the result for $n = 2$.

$\map P 2$ is the case:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} 2: \mathbf {A B} \ne \mathbf {B A}$

This is demonstrated in Matrix Multiplication is not Commutative: Order $2$ Square Matrices.

Thus $\map P 2$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} k: \mathbf {A B} \ne \mathbf {B A}$


from which it is to be shown that:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} {k + 1}: \mathbf {A B} \ne \mathbf {B A}$


Induction Step

This is the induction step:

From the induction hypothesis, it is assumed that there exist $2$ order $k$ square matrices $\mathbf A$ and $\mathbf B$ such that $\mathbf {A B} \ne \mathbf {B A}$.


For an order $n$ square matrix $\mathbf D$, let $\mathbf {D'}$ be the square matrix of order $n + 1$ defined as:

$d'_{i j} = \begin {cases} d_{i j} & : i < n + 1 \land j < n + 1 \\ 0 & : i = n + 1 \lor j = n + 1 \end{cases}$


Thus $\mathbf D'$ is just $\mathbf D$ with a zero row and zero column added at the ends.

We have that $\mathbf D$ is a submatrix of $\mathbf D'$.


Now:

$\paren {a' b'}_{i j} = \begin{cases} \displaystyle \sum_{r \mathop = 1}^{n + 1} \mathbf a'_{i r} b'_{r j} & : i < n + 1 \land j < n + 1 \\ 0 & : i = n + 1 \lor j = n + 1 \end{cases}$


But:

\(\displaystyle \sum_{r \mathop = 1}^{n + 1} a'_{i r} b'_{r j}\) \(=\) \(\displaystyle a'_{i \paren {n + 1} } b'_{\paren {n + 1} i} + \sum_{r \mathop = 1}^n a'_{i r} b'_{r j}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{r \mathop = 1}^n a_{i r} b_{r j}\)


and so:

\(\displaystyle \mathbf A' \mathbf B' \paren {n + 1, n + 1}\) \(=\) \(\displaystyle \paren {\mathbf {A B} }' \paren {n + 1, n + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \mathbf {A B}\)
\(\displaystyle \) \(\ne\) \(\displaystyle \mathbf {B A}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {\mathbf {B A} }' \paren {n + 1, n + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \mathbf B' \mathbf A' \paren {n + 1; n + 1}\)


Thus it is seen that:

$\exists \mathbf A', \mathbf B' \in \mathcal M_{n + 1 \times n + 1}: \mathbf A' \mathbf B' \ne \mathbf B' \mathbf A'$


So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\exists \mathbf A, \mathbf B \in \map {\mathcal M_R} n: \mathbf {A B} \ne \mathbf {B A}$

and by definition (conventional) matrix multiplication over $\map {\mathcal M_R} n$ is not commutative.

$\blacksquare$