Matrix Multiplication

Review: Matrix Basics

Matrix: Rectangular array of numbers

Dimensions: m × n (rows × columns)

Operations reviewed: Addition, subtraction, scalar multiplication

Now: Matrix multiplication

Multiplying Matrices

Key requirement: Number of columns in first = number of rows in second

If A is m × n and B is n × p, then AB is m × p

Formula: (AB)ᵢⱼ = Σ(aᵢₖ · bₖⱼ)

In words: Entry is dot product of row from A with column from B

Example 1: Basic Multiplication (2×2)

Multiply:

[1  2] × [5  6]
[3  4]   [7  8]

Calculate each entry:

Row 1, Col 1: 1(5) + 2(7) = 5 + 14 = 19 Row 1, Col 2: 1(6) + 2(8) = 6 + 16 = 22 Row 2, Col 1: 3(5) + 4(7) = 15 + 28 = 43 Row 2, Col 2: 3(6) + 4(8) = 18 + 32 = 50

Result:

[19  22]
[43  50]

Example 2: Different Dimensions

Multiply (2×3) × (3×2):

[1  2  3] × [7   8]
[4  5  6]   [9  10]
            [11 12]

Result will be 2×2

Entry (1,1): 1(7) + 2(9) + 3(11) = 7 + 18 + 33 = 58 Entry (1,2): 1(8) + 2(10) + 3(12) = 8 + 20 + 36 = 64 Entry (2,1): 4(7) + 5(9) + 6(11) = 28 + 45 + 66 = 139 Entry (2,2): 4(8) + 5(10) + 6(12) = 32 + 50 + 72 = 154

Result:

[58   64]
[139  154]

Dimension Compatibility

Can multiply A×B if: columns(A) = rows(B)

Result dimensions: rows(A) × columns(B)

Example: Check Compatibility

Can we multiply (3×2) × (2×4)?

Columns of first (2) = rows of second (2) ✓

Result: 3×4 matrix

Can we multiply (3×2) × (3×4)?

Columns of first (2) ≠ rows of second (3) ✗

Cannot multiply

Matrix Multiplication is NOT Commutative

Generally: AB ≠ BA

Order matters!

Example: Show Non-Commutative

A:

[1  2]
[3  4]

B:

[0  1]
[1  0]

AB:

[1(0)+2(1)  1(1)+2(0)]   [2  1]
[3(0)+4(1)  3(1)+4(0)] = [4  3]

BA:

[0(1)+1(3)  0(2)+1(4)]   [3  4]
[1(1)+0(3)  1(2)+0(4)] = [1  2]

AB ≠ BA

Special Cases

Sometimes AB might not exist while BA does (or vice versa)

Example: One Direction Only

A is 2×3, B is 3×1

AB exists: (2×3)(3×1) = 2×1 ✓

BA exists? (3×1)(2×3) — need 1 = 2 ✗

Only AB can be computed

Identity Matrix

Identity matrix I: Diagonal of 1s, rest 0s

2×2 identity:

[1  0]
[0  1]

3×3 identity:

[1  0  0]
[0  1  0]
[0  0  1]

Property: AI = IA = A

Example: Multiply by Identity

A:

[2  3]
[4  5]

AI:

[2  3] [1  0]   [2  3]
[4  5] [0  1] = [4  5]

Result is A (identity property)

Properties of Matrix Multiplication

Associative: (AB)C = A(BC)

Distributive: A(B + C) = AB + AC

Scalar factoring: k(AB) = (kA)B = A(kB)

NOT commutative: AB ≠ BA (generally)

Identity property: AI = IA = A

Example: Associative Property

Verify (AB)C = A(BC) for:

A = [1  2]    B = [1]    C = [1  0]
    [3  4]        [1]

AB:

[1  2] [1]   [3]
[3  4] [1] = [7]

(AB)C:

[3] [1  0] = [3  0]
[7]          [7  0]

BC:

[1] [1  0] = [1  0]
[1]          [1  0]

A(BC):

[1  2] [1  0]   [3  0]
[3  4] [1  0] = [7  0]

(AB)C = A(BC) ✓

Matrix Powers

A² = A · A

A³ = A · A · A

Only defined for square matrices

Example: Matrix Squared

A:

[1  2]
[0  3]

A²:

[1  2] [1  2]   [1  8]
[0  3] [0  3] = [0  9]

Zero Matrix

Zero matrix: All entries are 0

Property: A · 0 = 0 · A = 0

Note: AB = 0 doesn't imply A = 0 or B = 0 (unlike numbers!)

Example: Product is Zero

A:

[1   2]
[2   4]

B:

[2  0]
[-1 0]

AB:

[1(2)+2(-1)   0]   [0  0]
[2(2)+4(-1)   0] = [0  0]

Product is zero, but neither A nor B is zero matrix

Applications: Linear Transformations

Matrix multiplication represents composition of transformations

Example: Rotation then Scaling

Rotate 90° counterclockwise:

R = [0  -1]
    [1   0]

Scale by 2:

S = [2  0]
    [0  2]

Combined transformation SR:

[2  0] [0  -1]   [0  -2]
[0  2] [1   0] = [2   0]

Apply to point (1, 0):

[0  -2] [1]   [0]
[2   0] [0] = [2]

Result: (0, 2)

Applications: Systems of Equations

System:

2x + 3y = 7
4x + 5y = 11

Matrix form: AX = B

[2  3] [x]   [7]
[4  5] [y] = [11]

Solve using matrix techniques (covered in next lessons)

Applications: Networks

Adjacency matrix: Represents connections

Powers of adjacency matrix: Count paths

Example: Network Paths

Graph with 3 nodes:

A = [0  1  1]    (connections)
    [1  0  1]
    [1  1  0]

A²: Counts 2-step paths A³: Counts 3-step paths

Applications: Markov Chains

Transition matrix: Probabilities of state changes

Multiply by state vector: Find next state

Example: Weather Model

Transition matrix:

       Sunny  Rainy
Sunny  [0.8   0.2]
Rainy  [0.4   0.6]

Today sunny (100%): [1, 0]

Tomorrow:

[0.8  0.2] [1]   [0.8]
[0.4  0.6] [0] = [0.4]

80% chance sunny, 40% chance rainy (wait, this should be [0.8, 0.2] as row vector times matrix... let me reconsider)

Actually, using column vector:

[0.8  0.2] [1]   [0.8]
[0.4  0.6] [0] = [0.4]

Interpretation depends on setup

Block Matrix Multiplication

Matrices can be subdivided into blocks

Multiply blocks like elements (if dimensions compatible)

Example: Block Multiplication

Partition:

[A  B] [E]   [AE + BF]
[C  D] [F] = [CE + DF]

Where A, B, C, D, E, F are matrices themselves

Computational Complexity

Multiplying m×n by n×p matrix:

• Requires m·n·p multiplications
• For large matrices, can be slow

Example: (100×100) × (100×100)

• Requires 100·100·100 = 1,000,000 multiplications

Practice