Matrix Multiplication

Subtopic: Matricies

Matrix multiplication is the workhorse of linear algebra—it computes the composition of linear transformations, solves systems of equations, and powers everything from graphics to neural networks. The rule is simple once you see it: row times column, summed up.

Introduction

Why is matrix multiplication defined the way it is? It's not component-wise (that would be too simple and less useful). Instead, it's designed so that if matrix A represents one transformation and B represents another, then A*B represents doing B first, then A.

This connection to function composition is why matrix multiplication is so powerful—and why it's not commutative. The order of transformations matters.

Definition

For A*(m⨉n)and B*(n⨉p), the product C=A*B is an m⨉p matrix where:

(C_i*j)=(∑_k=1^n)((A_i*k))*(B_k*j)=(A_i*1)*(B_1*j)+(A_i*2)*(B_2*j)+⋯+(A_i*n)*(B_n*j)

Entry (i,j) of C is the dot product of row i of A with column j of B.

Critical requirement: the number of columns of A must equal the number of rows of B.

Geometric Interpretation

If A represents transformation (T_1) and B represents (T_2), then A*B AB represents the composition (T_1)∘(T_2): first apply (T_2), then (T_1).

For a vector x: (A*B)*x=A*(B*x). The vector is first transformed by B, then the result is transformed by A.

This explains why A*B≠B*A in general: rotating then scaling is different from scaling then rotating.

Step-by-Step Example

Multiply:

A=([1,2],[3,4]),B=([5,6],[7,8])

(C_11)= (row 1 of A) ⋅ (column 1 of B)=1*(5)+2*(7)=5+14=19

(C_12)= (row 1 of A) ⋅ (column 2 of B)=1*(6)+2*(8)=6+16=22

(C_21)= (row 2 of A) ⋅ (column 1 of B)=3*(5)+4*(7)=15+28=43

(C_22)= (row 2 of A) ⋅ (column 2 of B)=3*(6)+4*(8)=18+32=50

A*B=([19,22],[43,50])

Key Properties

• NOT commutative: A*B≠B*A in general (even when both products exist)

• Associative: (A*B)*C=A*(B*C)

• Distributive: A*(B+C)=A*B+A*C and (A+B)*C=A*C+B*C

• Identity: A*I=I*A=A, where I is the identity matrix

• Transpose: (A*B)T=BT*AT (note the reversal)

• Inverse: (A*B)(−1)=B(−1)*A(−1) (note the reversal)

Matrix-Vector Multiplication

A special case: A*(m⨉n) times x (n ⨉ 1 column vector) gives an m ⨉ 1 vector.

A*x=(x_1)*(a_1)+(x_2)*(a_2)+⋯+(x_n)*(a_n)

where (a_i) is column i of A. So A*x is a linear combination of A's columns!

This column view is often more insightful than the row-dot-column computation.

Dimension Rules

(m×n) times (n×p)=(m×p)

The inner dimensions must match; the outer dimensions give the result size.

Memory aid: (a×b)*(b×c)=(a×c) — the b's cancel.

Computational Cost

Multiplying an (m×n) matrix by an (n×p) matrix takes O*(m*n*p) operations using the standard algorithm.

For square n×n matrices, this is O(n3).

Faster algorithms exist (Strassen: O(n2.81)), but standard multiplication is usually used in practice due to better constants and numerical stability.

Block Multiplication

Matrices can be partitioned into blocks, and multiplication works block-wise as if blocks were entries:

([(A_11),(A_12)],[(A_21),(A_22)])*([(B_11),(B_12)],[(B_21),(B_22)])=([(A_11)*(B_11)+(A_12)*(B_21),⋯],[⋮,⋱])

This is useful for large matrices and parallel computation.

Applications

In graphics, transformations (rotation, scaling, translation) are matrices. Combining transformations = multiplying matrices.

In neural networks, each layer performs y=W*x+b, where W is a weight matrix. Deep networks are chains of matrix multiplications.

In solving linear systems A*x=b, understanding matrix-vector multiplication reveals the column space and solution structure.

In Markov chains, powers of the transition matrix An give the n-step transition probabilities.

Summary

Matrix multiplication combines row–column dot products to produce a new matrix. It represents composition of linear transformations, explaining its non-commutativity. Key properties: associative, distributive, and transpose and inverse reverse order. The column view (A*x as a linear combination of columns) provides geometric insight. Matrix multiplication is O(n3) for square matrices and underlies applications from graphics to machine learning.