Matrix multiplication and its cost

Composing maps

The product $AB$ is the map you get by applying $B$ first and then $A$ : $(AB)\mathbf{x}=A(B\mathbf{x})$ . Entry $(i,j)$ of the product is row $i$ of $A$ dotted with column $j$ of $B$ , so the shapes must fit: an $m\times n$ matrix times an $n\times p$ matrix gives an $m\times p$ matrix. The product is associative, $(AB)C=A(BC)$ , and it distributes over sums, but in general it is not commutative: $AB\neq BA$ because the order of two actions matters.

(AB)_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj},\qquad (AB)^{T}=B^{T}A^{T}

(1)

Computing $AB$ for an $m\times n$ and an $n\times p$ matrix takes $mnp$ multiply-adds (about $2mnp$ floating-point operations). For two $n\times n$ matrices that is $n^3$ , so doubling $n$ makes the work eight times larger. A matrix times a vector costs only $n^2$ . Because the product is associative, the order of the brackets does not change the answer but can change the cost enormously.

Order matters, twiceWith

A=\begin{pmatrix}1&2\\0&1\end{pmatrix}

and

B=\begin{pmatrix}0&1\\1&0\end{pmatrix}

AB=\begin{pmatrix}2&1\\1&0\end{pmatrix}

but

BA=\begin{pmatrix}0&1\\1&2\end{pmatrix}

, so the order changes the answer. Brackets change the cost: for

n\times n

matrices

A,B

and a vector

\mathbf{v}

(AB)\mathbf{v}

costs

n^3+n^2

multiply-adds while

A(B\mathbf{v})

costs

2n^2

. For

n=1000

that is a thousand million against two million.

Shape rule: $(m\times n)(n\times p)=(m\times p)$ ; the inner sizes must match.
Not commutative: $AB\neq BA$ in general, so never swap factors.
Cost: $mnp$ multiply-adds; matrix times vector is $n^2$ , matrix times matrix is $n^3$ .

Bracket your products from the vector sideWhen a chain of matrices ends in a vector, multiply from the vector side:

A(B(C\mathbf{v}))

uses only matrix-vector products. Portfolio risk

\mathbf{w}^{T}\Sigma\mathbf{w}

is computed as

\mathbf{w}\cdot(\Sigma\mathbf{w})

, never by first forming a matrix from

\mathbf{w}

Lab · what's graded

The product AB20 pts
The product BA15 pts
The shape of a product10 pts
Counting multiply-adds15 pts
Two ways to bracket20 pts
Why the bracketing matters20 pts

Composing maps

(AB)_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj},\qquad (AB)^{T}=B^{T}A^{T}

(1)

Order matters, twiceWith

A=\begin{pmatrix}1&2\\0&1\end{pmatrix}

and

B=\begin{pmatrix}0&1\\1&0\end{pmatrix}

AB=\begin{pmatrix}2&1\\1&0\end{pmatrix}

but

BA=\begin{pmatrix}0&1\\1&2\end{pmatrix}

, so the order changes the answer. Brackets change the cost: for

n\times n

matrices

A,B

and a vector

\mathbf{v}

(AB)\mathbf{v}

costs

n^3+n^2

multiply-adds while

A(B\mathbf{v})

costs

2n^2

. For

n=1000

that is a thousand million against two million.

Shape rule: $(m\times n)(n\times p)=(m\times p)$ ; the inner sizes must match.
Not commutative: $AB\neq BA$ in general, so never swap factors.
Cost: $mnp$ multiply-adds; matrix times vector is $n^2$ , matrix times matrix is $n^3$ .

Bracket your products from the vector sideWhen a chain of matrices ends in a vector, multiply from the vector side:

A(B(C\mathbf{v}))

uses only matrix-vector products. Portfolio risk

\mathbf{w}^{T}\Sigma\mathbf{w}

is computed as

\mathbf{w}\cdot(\Sigma\mathbf{w})

, never by first forming a matrix from

\mathbf{w}

Lab · what's graded

The product AB20 pts
The product BA15 pts
The shape of a product10 pts
Counting multiply-adds15 pts
Two ways to bracket20 pts
Why the bracketing matters20 pts

Matrix multiplication and its cost

Composing maps

Lab · what's graded

Log in to run your code.

Matrix multiplication and its cost

Composing maps

Lab · what's graded

Log in to run your code.