Matrix Multiplication

\( A^{m \times n} : \qquad X \in \mathbb{R}^n \longrightarrow AX \in \mathbb{R}^m \)

\( AX \)

\[ \begin{gathered} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ & & & \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \\ \vdots \quad \vdots \quad \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \end{pmatrix} \\[0.5em] = x_1 \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix} + x_2 \begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix} + \cdots + x_n \begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix} \end{gathered} \]

Matrix Multiplication

\( A^{m \times n} : \qquad X \in \mathbb{R}^n \longrightarrow AX \in \mathbb{R}^m \)

\( AX \)

\[ \begin{gathered} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ & & & \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \\ \vdots \quad \vdots \quad \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \end{pmatrix} \\[0.5em] = x_1 \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix} + x_2 \begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix} + \cdots + x_n \begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix} \end{gathered} \]

Matix Multiplication

\( A^{m \times n} : \qquad X \in \mathbb{R}^n \longrightarrow AX \in \mathbb{R}^m \)

\( AX \)

\[ \begin{gathered} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ & & & \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \\ \vdots \quad \vdots \quad \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \end{pmatrix} \\[0.5em] = x_1 \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix} + x_2 \begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix} + \cdots + x_n \begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix} \end{gathered} \]

Matix Multiplication

\( A^{m \times n} : \qquad X \in \mathbb{R}^n \longrightarrow AX \in \mathbb{R}^m \)

"Formula"

\[ (AX)_i = a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n = \sum_{k=1}^{n} a_{ik} x_k \]

Linearity Properties

  1. \( A(\alpha X + \beta Y) = \alpha AX + \beta AY \)
  2. \( (\alpha A + \beta B) X = \alpha AX + \beta BX \)

Composition of Linear Transformations

\[ \begin{gathered} \mathbb{R}^{\ell} \xrightarrow{B^{m \times \ell}} \mathbb{R}^{m} \xrightarrow{A^{n \times m}} \mathbb{R}^{n} \\[0.5em] X \longrightarrow Y = BX \longrightarrow Z = AY \\[0.5em] = A(BX) \\[0.5em] = (AB)X \\[0.5em] = AY = A(BX) \\[0.5em] = A(x_1 B_1 + x_2 B_2 + \cdots + x_{\ell} B_{\ell}) \qquad (B_j - j^{th}\ \text{col of } B) \\[0.5em] = x_1 AB_1 + x_2 AB_2 + \cdots + x_{\ell} AB_{\ell} \\[0.5em] = \begin{bmatrix} AB_1 & AB_2 & \cdots & AB_{\ell} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_{\ell} \end{bmatrix} \end{gathered} \]

Composition of Linear Transformations

\[ \begin{gathered} \mathbb{R}^{\ell} \xrightarrow{B^{m \times \ell}} \mathbb{R}^{m} \xrightarrow{A^{n \times m}} \mathbb{R}^{n} \\[0.5em] X \longrightarrow Y = BX \longrightarrow Z = AY \\[0.5em] = A(BX) \\[0.5em] = (AB)X \\[0.5em] AB := \begin{bmatrix} AB_1 & AB_2 & \cdots & AB_{\ell} \end{bmatrix} \end{gathered} \]

Col's of B.

Matix Multiplication

\[ A^{n \times m} = (A_{ij}), \qquad B^{m \times \ell} = (B_{ij}) \]\[ A^{n \times m} B^{m \times \ell} = C^{n \times \ell} \]\[ C_{ij} = (AB)_{ij} = \begin{pmatrix} A_{i1} & A_{i2} \cdots & A_{im} \end{pmatrix} \left( \begin{array}{c} B_{1j} \\ B_{2j} \\ \vdots \\ B_{mj} \end{array} \right) \]

where the first factor is the \( i^{th} \) row of \( A \) and the second factor is the \( j^{th} \) col. of \( B \).

\[ \begin{gathered} = A_{i1} B_{1j} + A_{i2} B_{2j} + \cdots + A_{im} B_{mj} \\[0.5em] = \sum_{k=1}^{m} A_{ik} B_{kj} \end{gathered} \]

(Same as (*))

Matix Multiplication

\[ \underset{A}{\begin{bmatrix} a & b \\ c & d \end{bmatrix}} \underset{B}{\begin{bmatrix} p & q \\ r & s \end{bmatrix}} = \underset{C}{\begin{bmatrix} ap+br & aq+bs \\ cp+dr & cq+ds \end{bmatrix}} \]

Matix Multiplication

\[ \begin{gathered} \underset{A}{\begin{bmatrix} a & b \\ c & d \end{bmatrix}} \underset{B}{\begin{bmatrix} p & q \\ r & s \end{bmatrix}} = \underset{C}{\begin{bmatrix} ap+br & aq+bs \\ cp+dr & cq+ds \end{bmatrix}} \\[0.5em] p \begin{bmatrix} a \\ c \end{bmatrix} + r \begin{bmatrix} b \\ d \end{bmatrix} \qquad q \begin{bmatrix} a \\ c \end{bmatrix} + s \begin{bmatrix} b \\ d \end{bmatrix} \end{gathered} \]

use columns of B to take lin comb. of columns of A.

Matix Multiplication

\[ \begin{gathered} \underset{A}{\begin{bmatrix} a & b \\ c & d \end{bmatrix}} \underset{B}{\begin{bmatrix} p & q \\ r & s \end{bmatrix}} = \underset{C}{\begin{bmatrix} ap+br & aq+bs \\ cp+dr & cq+ds \end{bmatrix}} \\[0.5em] a\begin{pmatrix} p & q \end{pmatrix} + b\begin{pmatrix} r & s \end{pmatrix} \qquad c\begin{pmatrix} p & q \end{pmatrix} + d\begin{pmatrix} r & s \end{pmatrix} \end{gathered} \]

use rows of A to take lin comb. of rows of B.

Matix Multiplication and Row Operations

\[ \begin{gathered} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix} \quad : \text{interchange 2 rows} \\[0.5em] \begin{bmatrix} \alpha & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} \alpha a & \alpha b \\ c & d \end{bmatrix} \quad : \text{mult. first row by } \alpha \\[0.5em] \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} a+\alpha c & b+\alpha c \\ c & d \end{bmatrix} \end{gathered} \]

add \( \alpha \)-mult. of second row to first row

Matix Multiplication and "Col" Operations

\[ \begin{gathered} \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} b & a \\ d & c \end{bmatrix} \quad : \text{interchange 2 rows} \\[0.5em] \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} \alpha & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} \alpha a & b \\ \alpha c & d \end{bmatrix} \quad : \text{mult. first row by } \alpha \\[0.5em] \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 1 & 0 \\ \alpha & 1 \end{bmatrix} = \begin{bmatrix} a+\alpha b & b \\ c+\alpha d & d \end{bmatrix} \end{gathered} \]

add \( \alpha \)-mult. of second row to first row

Propeties of Matix Multiplication

  1. \[ \begin{gathered} A(\alpha B + \beta C) = \alpha AB + \beta AC \\[0.5em] (\alpha A + \beta B) C = \alpha AC + \beta BC \end{gathered} \]
  2. \[ A(BC) = (AB)C \]
  3. \[ (AB)^T = B^T A^T \]
  4. In general, \( AB \ne BA \)

Proof of (2) \( A(BC) = (AB)C \)

\[ \begin{gathered} \left( A(BC) \right)_{ij} = \sum_k A_{ik} (BC)_{kj} \\[0.5em] = \sum_k A_{ik} \left( \sum_l B_{kl} C_{lj} \right) \\[0.5em] = \sum_k \sum_l \left( A_{ik} B_{kl} C_{lj} \right) \\[0.5em] = \sum_l \sum_k \left( A_{ik} B_{kl} C_{lj} \right) \longrightarrow \sum_l (AB)_{il} C_{lj} \\[0.5em] = \sum_l \left( \sum_k A_{ik} B_{kl} \right) C_{lj} = \left( (AB)C \right)_{ij} \end{gathered} \]

Proof of (3) \( (AB)^T = B^T A^T \)

\[ \begin{gathered} \left( (AB)^T \right)_{ij} = (AB)_{ji} \\[0.5em] = \sum_k A_{jk} B_{ki} \\[0.5em] = \sum_k (A^T)_{kj} (B^T)_{ik} \\[0.5em] = \sum_k (B^T)_{ik} (A^T)_{kj} \\[0.5em] = (B^T A^T)_{ij} \end{gathered} \]

Propeties of Matix Multiplication

(5) Identity Matix (Square)

\[ \begin{gathered} I_n = \begin{pmatrix} 1 & & & 0\text{'s} \\ & 1 & & \\ 0\text{'s} & & \ddots & \\ & & & 1 \end{pmatrix}^{n \times n} \\[0.5em] I_1 = (1), \quad I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad I_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} \\[0.5em] I_n A^{n \times m} = A^{n \times m}, \quad A^{n \times m} I_m = A^n \end{gathered} \]

Propeties of Matix Multiplication

(5) Identity Matix (Square)

\[ \begin{gathered} I_n A^{n \times m} = A^{n \times m}, \qquad A^{n \times m} I_m = A^{n \times m} \\[0.5em] \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix} \\[0.5em] A^{2 \times 3} I_3 = A^{2 \times 3} \end{gathered} \]

Propeties of Matix Multiplication

(5) Identity Matix (Square)

\[ \begin{gathered} I_n A^{n \times m} = A^{n \times m}, \qquad A^{n \times m} I_m = A^{n \times m} \\[0.5em] \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix} = \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix} \\[0.5em] I_2 A^{2 \times 3} = A^{2 \times 3} \end{gathered} \]

Propeties of Matix Multiplication

(6) Diagonal Matix (Square)

\[ \begin{gathered} A^{n \times n} = \begin{pmatrix} a_1 & & & \\ & a_2 & & \\ & & \ddots & \\ & & & a_n \end{pmatrix}, \qquad B^{n \times n} = \begin{pmatrix} b_1 & & & 0 \\ & b_2 & & \\ & & \ddots & \\ 0 & & & b_n \end{pmatrix} \\[0.5em] AB = \begin{pmatrix} a_1 & & & 0 \\ & a_2 & & \\ & & \ddots & \\ 0 & & & a_n \end{pmatrix} \begin{pmatrix} b_1 & & & 0 \\ & b_2 & & \\ & & \ddots & \\ 0 & & & b_n \end{pmatrix} = \begin{pmatrix} a_1 b_1 & & & 0 \\ & a_2 b_2 & & \\ & & \ddots & \\ 0 & & & a_n b_n \end{pmatrix} \end{gathered} \]