05 - Matrix Multiplication

Matrix Multiplication

Let $A=(a_{ij})$ be a $m\times n$ matrix and $B=(b_{ij})$ be a $n\times p$ matrix

$C=AB=(c_{ij})$ is $m\times p$ matrix such that

$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

for $1\le i\le m$ and $1\le j\le p$

Require number of columns of matrix $A$ to be equal to number of rows of matrix $B$

Properties of Matrix Multiplication

1. Let $A$ be a $m\times n$ matrix and $l,p\in \mathbb{N}\setminus \{0\}$

$$A{0}_{np}=0_{mp};0_{lm}A=0_{\ln };A{I}_n=A;I_{m}A=A$$

2. Matrix Multiplication is NOT commutative
3. Matrix Multiplication is associative
4. Matrix Multiplication is distributive under matrix addition

$$A(B+C)=AB+AC,\text{and}(A+B)C=AC+BC$$

5. If $MN=0$ then it is not necessarily true that either $M$ or $N$ are 0

Proof (Short - Not detailed)

1. Use matrix multiplication definition and sifting property for the identity ones
2. Counterexample (just think of $2\times 2$)
3. Go through double summation from definition
4. Go through double summation from definition
5. Counterexample (just think of $2\times 2$)

---

Left Multiplication Map (Pre-multiplying)

Let $M$ be $m\times n$ matrix then pre-multiplication map $L_M$ is

$$L_M\text{ from }{\mathbb{R}}_{\mathrm{col}}^n\text{ to }{\mathbb{R}}_{\mathrm{col}}^m$$

as $M\mathbf{v}$ is a $m\times 1$ column vector where $\mathbf{v}$ is a $n\times 1$ column vector

Application of Left Multiplication Map to $A,B$

$$L_A\text{ from }{\mathbb{R}}_{\mathrm{col}}^n\text{ to }{\mathbb{R}}_{\mathrm{col}}^m,L_B\text{ from }{\mathbb{R}}_{\mathrm{col}}^p\text{ to }{\mathbb{R}}_{\mathrm{col}}^n,L_{AB}\text{ from }{\mathbb{R}}_{\mathrm{col}}^n\text{ to }{\mathbb{R}}_{\mathrm{col}}^p$$

With

$$L_{AB}=L_A\circ L_B$$

As $(AB)\mathbf{v}=A(B\mathbf{v})$

The $\circ$ is for composition

---

Pre-multiplication and Post-multiplication

Let $A,M$ be matrices

• Pre-multiply $M$ by $A$: $AM$
• Post-multiply $M$ by $A$: $MA$

Notation on Power of Matirices

Let $A$ be a square matrix then

$$A^n=\underset{n\text{ times}}{\underbrace{AA\cdots A}}$$

with $A^0=I$ and $A^m{A}^n=A^{m+n}$

---

Associative Property of Matrices through Linear Maps corollary

Take $A\in {\mathcal{M}}_{m\times n}(\mathbf{F})$, take $B\in {\mathcal{M}}_{n\times p}(\mathbf{F})$, and take $C\in {\mathcal{M}}_{p\times q}(\mathbf{F})$
Then

$$A(BC)=(AB)C$$

Proof

Consider the left multiplication maps

$$L_A:{\mathbf{F}}_{\mathrm{col}}^n\to {\mathbf{F}}_{\mathrm{col}}^m\text{ and }{L}_B:{\mathbf{F}}_{\mathrm{col}}^p\to {\mathbf{F}}_{\mathrm{col}}^n\text{ and }{L}_C:{\mathbf{F}}_{\mathrm{col}}^q\to {\mathbf{F}}_{\mathrm{col}}^p$$

With respect to the standard bases of these spaces, then represent the matrices of $L_A,L_B,L_C$ as $A,B,C$ respectively
Then
By Matrix of a Composition of Linear Maps, $A(BC)$ and $(AB)C$ are matrices of

$$L_A\circ (L_B\circ L_C):{\mathbf{F}}_{\mathrm{col}}^q\to {\mathbf{F}}_{\mathrm{col}}^m\text{ and }(L_A\circ L_B)\circ L_C:{\mathbf{F}}_{\mathrm{col}}^q\to {\mathbf{F}}_{\mathrm{col}}^m$$

But composition of functions is associative, so

$$L_A\circ (L_B\circ L_C)=(L_A\circ L_B)\circ L_C$$

Hence

$$A(BC)=(AB)C$$