Matrices as Linear Maps

1. \(\mA\mB = \begin{bmatrix}2(1)+1(2) & 2(-1)+1(0)\\ 0(1)+3(2) & 0(-1)+3(0)\end{bmatrix} = \begin{bmatrix}4&-2\\6&0\end{bmatrix}\).
\(\mB\mA = \begin{bmatrix}1(2)+(-1)(0) & 1(1)+(-1)(3)\\ 2(2)+0 & 2(1)+0\end{bmatrix} = \begin{bmatrix}2&-2\\4&2\end{bmatrix}\). Different ✓.

2. Rows: \((2\cdot1+1\cdot2,\ 0\cdot1+3\cdot2) = (4,6)\).
Columns: \(1\begin{bmatrix}2\\0\end{bmatrix}+2\begin{bmatrix}1\\3\end{bmatrix} = \begin{bmatrix}2\\0\end{bmatrix}+\begin{bmatrix}2\\6\end{bmatrix}=\begin{bmatrix}4\\6\end{bmatrix}\) ✓.

3. \(\det\mA = 6-0 = 6\). \(\det\mB = 0-(-2) = 2\). \(\det(\mA\mB) = 4(0)-(-2)(6) = 12 = 6\times2\) ✓.
The relationship is \(\det(\mA\mB)=\det\mA\cdot\det\mB\), and it has a clean geometric reading: determinant is the factor by which area is scaled, and applying two maps in sequence multiplies the scalings. It also immediately explains why a product is singular if either factor is: destroy a dimension once and no later map can restore it.

(⟸) Suppose \(\mathcal{N}(\mA)=\{\vzero\}\) and \(\mA\vu=\mA\vv\). Then by linearity \(\mA(\vu-\vv)=\vzero\), so \(\vu-\vv\in\mathcal{N}(\mA)=\{\vzero\}\), so \(\vu=\vv\). That is injectivity, in exactly the form from Lecture 1.

(⟹) Suppose \(T\) is injective and take \(\vx\in\mathcal{N}(\mA)\), so \(\mA\vx=\vzero\). But also \(\mA\vzero=\vzero\) (every linear map sends zero to zero). Two inputs with the same output, so injectivity forces \(\vx=\vzero\). ∎

Note how much simpler this is than for a general function: for a linear map you only have to check one point, the origin. That is a genuine gift of linearity.

Rank–nullity consequence. \(\rank(\mA)+\dim\mathcal{N}(\mA)=n\). Since \(\mathcal{C}(\mA)\subseteq\RR^m\) we have \(\rank(\mA)\le m\). Therefore

A positive-dimensional null space contains nonzero vectors, so \(T\) is not injective. ∎

Interpretation. Any linear dimensionality reduction from \(\RR^n\) to \(\RR^m\) with \(m<n\) must lose information: there is a subspace of dimension at least \(n-m\) that gets crushed to zero and can never be recovered. PCA does not evade this; it chooses which \(n-m\) dimensions to destroy, picking the ones carrying least variance. Autoencoders do not evade it either — they escape only by being nonlinear, so that the "subspace" being preserved can be a curved manifold rather than a flat subspace.

Let \(S,T\) be linear. For any \(\vu,\vv\) and scalars \(\alpha,\beta\):

The second equality used linearity of \(T\); the third used linearity of \(S\). ∎ (Same peeling pattern as the injectivity-of-composition proof in Lecture 1.)

Consequence for depth. An \(L\)-layer network with no activation computes \(\vy=\mW_L\mW_{L-1}\cdots\mW_1\vx\). By the above, the composition is linear, so it equals \(\mW\vx\) for the single matrix \(\mW=\mW_L\cdots\mW_1\). Whatever function the deep stack computes, one layer of the right shape computes it too. Worse, \(\rank(\mW)\le\min_\ell \rank(\mW_\ell)\), so depth can only reduce the achievable rank — a hundred layers buys strictly nothing and risks a bottleneck.

Adding biases makes it affine rather than linear, but the same collapse happens: a composition of affine maps is affine. The nonlinearity is the only thing standing between "deep network" and "one matrix".

Caveat worth knowing: deep linear networks are still studied, because although their expressivity is that of one layer, their optimisation dynamics are different and surprisingly informative. Expressive power and trainability are separate questions.

import numpy as np, time
rng = np.random.default_rng(0)
n = 512
A, B = rng.normal(size=(n,n)), rng.normal(size=(n,n))

def mm_loops(A, B):                       # only run this on a smaller n!
    m, p = A.shape; p2, q = B.shape
    C = np.zeros((m, q))
    for i in range(m):
        for j in range(q):
            s = 0.0
            for k in range(p): s += A[i,k]*B[k,j]
            C[i,j] = s
    return C

def mm_cols(A, B):
    return np.column_stack([A @ B[:, j] for j in range(B.shape[1])])

for name, f, size in [("triple loop", mm_loops, 128),
                      ("column-wise", mm_cols, n),
                      ("A @ B",       lambda A,B: A@B, n)]:
    a, b = A[:size,:size], B[:size,:size]
    t0 = time.perf_counter(); C = f(a, b); t1 = time.perf_counter()
    print(f"{name:12s} n={size:4d}  {(t1-t0)*1000:9.1f} ms  "
          f"max err {np.abs(C - a@b).max():.2e}")

Typical result. All three agree to about \(10^{-13}\) — the small discrepancy is floating-point summation order, not a bug. Timings: the triple loop takes on the order of a second at \(n=128\); the column-wise version takes a few milliseconds at \(n=512\); A @ B takes a few milliseconds too but does \(64\times\) more work than the \(n=128\) loop. Extrapolated to the same size, the gap between the pure-Python loop and BLAS is typically three to four orders of magnitude.

Why. Four things, roughly in order of importance:

1. No interpreter overhead. The loop executes \(2n^3 \approx 2.7\times10^8\) Python bytecode operations, each involving object allocation and type dispatch. BLAS runs compiled machine code.
2. Cache blocking. The naive loop walks \(\mB\) down a column, striding \(n\) floats between accesses — a cache miss almost every time. BLAS partitions the matrices into tiles that fit in L1/L2 cache and reuses each loaded tile many times. On modern hardware, matrix multiplication is memory-bound before it is compute-bound, and this is the dominant fix.
3. SIMD vectorisation. AVX-512 or NEON instructions perform 8–16 multiply-accumulates per cycle per core.
4. Multithreading. BLAS splits the work across cores automatically.

The lesson for ML. This is why everything in deep learning is expressed as matrix multiplication even when another formulation would be more natural. A GPU is, to a first approximation, a machine for doing exactly this operation, and an algorithm that cannot be written as dense linear algebra is an algorithm that cannot use the hardware. That constraint has shaped the field's architectures at least as much as any mathematical consideration.