---
title: Linear Algebra
module: Mathematical Background
moduleNumber: 0
lessonNumber: 1
order: 1
summary: >
  Every quantity a network touches is a tensor, and every layer is a matrix
  acting on one. This lesson compiles the linear algebra deep learning actually
  uses: products and norms, the system $Ax=b$ and when it is solvable, the two
  decompositions (eigen and SVD) that diagonalize a transformation, and the
  pseudoinverse that solves what cannot be solved exactly. It then derives PCA as
  the worked example that ties it all together.
topics: [Mathematical Background]
sources:
  - book: Goodfellow
    ref: "Ch. 2 — Linear Algebra"
  - book: Goodfellow
    ref: "§2.11 Determinant; §2.12 Example: Principal Components Analysis"
---

A neural network is a pipeline of linear maps interleaved with nonlinearities.
Strip the nonlinearities and what remains, the weight matrices, the activations,
the gradients, is pure linear algebra: a composition of matrix products acting on
arrays of numbers. This lesson is the working vocabulary, distilled to the objects
a network manipulates and the two decompositions that explain what those objects
_do_ to space.[^gf-linalg]

## Objects: scalars, vectors, matrices, tensors

The data structures form a ladder by number of indices.

| Object | Indices | Notation | Example in a network |
| --- | --- | --- | --- |
| scalar | $0$ | $a \in \mathbb{R}$ | a learning rate, a single loss value |
| vector | $1$ | $x \in \mathbb{R}^{n}$ | one input example, a bias |
| matrix | $2$ | $A \in \mathbb{R}^{m \times n}$ | a weight layer, a batch of vectors |
| tensor | $k$ | $\mathsf{A}$, entry $\mathsf{A}_{i,j,k}$ | a batch of RGB images $(N, C, H, W)$ |

A vector $x \in \mathbb{R}^{n}$ is a point in $n$-dimensional space; its entries
$x_1, \dots, x_n$ are coordinates. A matrix $A \in \mathbb{R}^{m \times n}$ has
entry $A_{i,j}$ in row $i$, column $j$. The **transpose** mirrors across the main
diagonal, $(A^\top)_{i,j} = A_{j,i}$, turning an $m \times n$ matrix into an
$n \times m$ one; for a product it reverses order, $(AB)^\top = B^\top A^\top$.

> **Definition (Tensor).** An array of numbers indexed by $k$ integer coordinates,
> generalizing scalar ($k=0$), vector ($k=1$), and matrix ($k=2$). Deep-learning
> frameworks store every quantity (inputs, parameters, activations, gradients)
> as a tensor, and an operation's _shape_ (the tuple of dimension sizes) is the
> first thing that must line up.

**Broadcasting** lets operations on mismatched shapes proceed by implicitly
replicating along missing or size-$1$ axes. Adding a bias vector $b \in \mathbb{R}^{m}$
to every column of $A \in \mathbb{R}^{m \times n}$ is the broadcast
$C_{i,j} = A_{i,j} + b_i$; Goodfellow writes this $C = A + b$, with $b$ added to
each row. The rule is mechanical: align shapes from the right, and any axis of size
$1$ (or absent) is stretched to match.[^gf-broadcast] The same tensor objects and
shape rules are what every framework's array type exposes directly.[^stevens-tensor]

## Two products

There are two different "multiplications" of arrays, and conflating them is the
most common shape bug in practice.

> **Definition (Matrix product).** For $A \in \mathbb{R}^{m \times n}$ and
> $B \in \mathbb{R}^{n \times p}$, the product $C = AB \in \mathbb{R}^{m \times p}$
> has entries $C_{i,j} = \sum_{k=1}^{n} A_{i,k} B_{k,j}$. It is associative and
> distributive but **not** commutative; the inner dimensions $n$ must agree.

> **Definition (Hadamard product).** The elementwise product $A \odot B$ of two
> arrays of the _same_ shape, $(A \odot B)_{i,j} = A_{i,j} B_{i,j}$. It is what a
> gating or masking operation computes, and it is commutative.

A single dense layer is the matrix product $z = Wx + b$ with $W \in \mathbb{R}^{m \times n}$;
the elementwise activation and the gradient masks of backpropagation are Hadamard
products. The **dot product** of two vectors is the special case $x^\top y = \sum_i x_i y_i$,
a scalar measuring alignment.[^gf-products]

For example, for
$A \in \mathbb{R}^{2 \times 3}$ and $B \in \mathbb{R}^{3 \times 2}$ the shared
inner dimension $3$ is summed away, leaving a $2 \times 2$ result:

$$
\underbrace{\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix}}_{2 \times 3}
\underbrace{\begin{bmatrix} 4 & 1 \\ 0 & 2 \\ 1 & 0 \end{bmatrix}}_{3 \times 2}
=
\begin{bmatrix} 1\cdot4 + 0\cdot0 + 2\cdot1 & 1\cdot1 + 0\cdot2 + 2\cdot0 \\
-1\cdot4 + 3\cdot0 + 1\cdot1 & -1\cdot1 + 3\cdot2 + 1\cdot0 \end{bmatrix}
= \underbrace{\begin{bmatrix} 6 & 1 \\ -3 & 5 \end{bmatrix}}_{2 \times 2}.
$$

Entry $C_{i,j}$ is the dot product of row $i$ of the left factor with column $j$
of the right factor. When a layer processes a **batch** of $N$ examples at once,
the same rule applies with the batch stacked as rows: $X \in \mathbb{R}^{N \times n}$
times $W^\top \in \mathbb{R}^{n \times m}$ yields $\mathbb{R}^{N \times m}$, one
output row per example, and the bias broadcasts down the $N$ rows. Reading a
layer as a shape transformation is the fastest way to catch a bug before it runs:

$$
% caption: A dense layer as a shape map. The input dimension $n$ is contracted
% away by $W$; the batch axis $N$ and output width $m$ survive.
\begin{tikzpicture}[>=stealth, font=\footnotesize, node distance=6mm]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw, black, fill=black!6, minimum height=9mm, minimum width=20mm] (x) {$X$};
  \node[below=1mm of x, black] {shape (N, n)};
  \node[draw, acc, fill=acc!8, minimum height=9mm, minimum width=20mm, right=16mm of x] (w) {$X W^{T}$};
  \node[below=1mm of w, acc] {shape (N, m)};
  \node[draw, black, fill=black!6, minimum height=9mm, minimum width=22mm, right=16mm of w] (z) {$X W^{T} + b$};
  \node[below=1mm of z, black] {shape (N, m)};
  \draw[->, acc, thick] (x) -- (w) node[midway, above] {$W^{T}$: n to m};
  \draw[->, acc, thick] (w) -- (z) node[midway, above] {add b};
\end{tikzpicture}
$$

## Linear systems: $Ax = b$

A matrix times a vector is a system of linear equations. Solving $Ax = b$ asks
which input $x$ the map $A$ sends to a target $b$. The answer is governed by three
intertwined notions: span, linear independence, and rank.

> **Definition (Span).** The set of all linear combinations $\sum_i c_i a_i$ of a
> collection of vectors $a_1, \dots, a_n$. The product $Ax = \sum_j x_j A_{:,j}$ is
> a linear combination of $A$'s columns, so $Ax = b$ is solvable **iff** $b$ lies in
> the span of the columns of $A$, the **column space** of $A$.

> **Definition (Linear independence).** Vectors are linearly independent if no one
> of them is a linear combination of the others; equivalently, $\sum_i c_i a_i = 0$
> forces every $c_i = 0$. The **rank** of $A$ is the number of linearly independent
> columns (equivalently, rows).

For $Ax = b$ to have a solution **for every** $b \in \mathbb{R}^{m}$, the columns
must span $\mathbb{R}^{m}$, requiring $n \ge m$ and $\rank(A) = m$.
For the solution to be **unique**, the columns must be linearly independent,
requiring $n \le m$. Both at once force $A$ square ($m = n$) and **full rank**, the
condition under which the inverse exists.

> **Definition (Inverse).** The inverse $A^{-1}$ of a square matrix $A$ satisfies
> $A^{-1}A = I$. It exists **iff** $A$ is square and full rank (equivalently,
> $\det A \neq 0$), and then $Ax = b$ has the unique solution $x = A^{-1}b$. A
> matrix with no inverse is **singular**.

### A matrix as a transformation of space

Geometrically, $A$ is a linear map: it sends the unit square (spanned by the basis
vectors $e_1, e_2$) to the parallelogram spanned by $A$'s columns. Full rank means
the parallelogram has nonzero area: the map does not collapse a dimension.

$$
% caption: A matrix $A$ maps the unit square (basis $e_1,e_2$) to the
% parallelogram spanned by its columns $Ae_1,Ae_2$.
\begin{tikzpicture}[>=stealth, font=\small, scale=1.25]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % --- source: unit square ---
  \draw[black, fill=black!8] (0,0) -- (1,0) -- (1,1) -- (0,1) -- cycle;
  \draw[black] (0,0) grid[step=1] (1.05,1.05);
  \draw[->, thick] (0,0) -- (1,0) node[anchor=north, font=\footnotesize] {$e_1$};
  \draw[->, thick] (0,0) -- (0,1) node[anchor=east, font=\footnotesize] {$e_2$};
  \node[font=\footnotesize, anchor=north] at (0.5,-0.35) {unit square};
  % --- arrow ---
  \draw[->, acc, very thick] (1.6,0.5) -- (2.7,0.5) node[midway, above, font=\footnotesize, text=acc] {$A$};
  % --- target: parallelogram, columns (1.4,0.3) and (0.6,1.1) ---
  \begin{scope}[xshift=3.3cm]
    \fill[acc!15] (0,0) -- (1.4,0.3) -- (2.0,1.4) -- (0.6,1.1) -- cycle;
    \draw[->, acc, thick] (0,0) -- (1.4,0.3) node[anchor=north west, font=\footnotesize, text=acc] {$A e_1$};
    \draw[->, acc, thick] (0,0) -- (0.6,1.1) node[anchor=south east, font=\footnotesize, text=acc] {$A e_2$};
    \draw[acc, thick] (1.4,0.3) -- (2.0,1.4) -- (0.6,1.1);
    \node[font=\footnotesize, anchor=north, text=acc] at (1.0,-0.35) {parallelogram};
  \end{scope}
\end{tikzpicture}
$$

The signed area of that parallelogram is the **determinant**, met below. It records
exactly how much $A$ scales volumes, and it is zero precisely when $A$ is singular.

## Norms: measuring size

A **norm** assigns a nonnegative length to a vector, with $\norm{x} = 0$ only
at $x = 0$, scaling $\norm{\alpha x} = \abs{\alpha}\,\norm{x}$, and the
triangle inequality $\norm{x + y} \le \norm{x} + \norm{y}$. The
$L^p$ family covers most of what a network needs.

| Norm | Formula | Geometry / use |
| --- | --- | --- |
| $L^1$ | $\norm{x}_1 = \sum_i \abs{x_i}$ | sparsity-inducing; grows linearly near $0$ |
| $L^2$ (Euclidean) | $\norm{x}_2 = \parens{\sum_i x_i^2}^{1/2}$ | ordinary distance; $\norm{x}_2^2 = x^\top x$ |
| $L^p$ | $\norm{x}_p = \parens{\sum_i \abs{x_i}^p}^{1/p}$, $p \ge 1$ | interpolates the family |
| $L^\infty$ (max) | $\norm{x}_\infty = \max_i \abs{x_i}$ | largest coordinate; the $p \to \infty$ limit |
| Frobenius | $\norm{A}_F = \parens{\sum_{i,j} A_{i,j}^2}^{1/2}$ | the $L^2$ norm of a _matrix_'s entries |

The squared $L^2$ norm $x^\top x$ is preferred in objectives because its gradient
$2x$ is cheap and it is differentiable everywhere, unlike $\norm{x}_2$,
whose derivative misbehaves at the origin. The $L^1$ norm is what induces
**sparsity**: because it grows at the same rate ($1$ per unit) no matter how close a
coordinate is to zero, it pushes coordinates _exactly_ to zero, which $L^2$ does not.

### Unit balls

The set $\set{x : \norm{x} = 1}$, the surface of the **unit ball**, pictures each
norm. The shapes explain the sparsity behavior: regularizing toward the origin pulls a
solution to the boundary of one of these balls, and the $L^1$ diamond's corners sit
_on the axes_, where coordinates vanish.

$$
% caption: Unit balls $\norm{x}_p=1$: $L^1$ diamond, $L^2$ circle, $L^\infty$
% square. The $L^1$ corners sit on the axes, which is why it induces sparsity.
\begin{tikzpicture}[>=stealth, font=\small, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (-2.0,0) -- (2.0,0) node[anchor=west, font=\footnotesize, black] {$x_1$};
  \draw[->, black] (0,-2.0) -- (0,2.0) node[anchor=south, font=\footnotesize, black] {$x_2$};
  % L-infinity: square
  \draw[red, very thick] (-1.4,-1.4) rectangle (1.4,1.4);
  % L2: circle
  \draw[acc, very thick] (0,0) circle (1.4);
  % L1: diamond
  \draw[green, very thick] (1.4,0) -- (0,1.4) -- (-1.4,0) -- (0,-1.4) -- cycle;
  % labels — leader lines to text placed well outside every curve
  \node[green, font=\footnotesize] at (0.95,0.95) {$L^1$};
  \node[acc, font=\footnotesize] at (-1.7,1.7) {$L^2$};
  \node[red, font=\footnotesize] at (1.75,1.7) {max};
\end{tikzpicture}
$$

## Special matrices

Three structured forms recur because each makes a hard operation cheap.

| Type | Definition | Why it matters |
| --- | --- | --- |
| diagonal | $D_{i,j} = 0$ for $i \neq j$ | $Dx$ scales coordinate $i$ by $D_{i,i}$; inverse is $1/D_{i,i}$ |
| symmetric | $A = A^\top$ | real eigenvalues, orthogonal eigenvectors (spectral theorem) |
| orthogonal | $A^\top A = A A^\top = I$ | $A^{-1} = A^\top$; preserves lengths and angles |

An **orthogonal** matrix is a rotation or reflection: it moves points without
distorting them, since $\norm{Ax}_2^2 = x^\top A^\top A x = x^\top x = \norm{x}_2^2$.
Diagonal matrices are the cheap case of every operation (multiply, invert, take
powers), and that cheapness drives the decompositions below, which aim to turn a
general matrix _into_ a diagonal one in the right coordinates.

## Eigendecomposition

An **eigenvector** of a square $A$ is a direction the map only stretches, never
rotates; the stretch factor is its **eigenvalue**.

> **Definition (Eigenvector / eigenvalue).** A nonzero vector $v$ with
> $Av = \lambda v$ for a scalar $\lambda$. The map $A$ acts on the line through $v$
> as pure scaling by $\lambda$; the direction of $v$ is unchanged (up to sign).

Stacking the eigenvectors as columns of $V$ and the eigenvalues on the diagonal of
$\diag(\lambda)$, the relations $Av_i = \lambda_i v_i$ assemble into
the **eigendecomposition**:

$$
A = V \diag(\lambda)\, V^{-1}.
$$

This says $A$ does nothing more than: change to the eigenbasis ($V^{-1}$), scale
each axis ($\diag(\lambda)$), change back ($V$). The picture is a
space stretched along its eigenvector axes.

Eigenvalues come from the condition that $Av = \lambda v$ have a nonzero solution,
i.e. that $(A - \lambda I)$ collapse a direction to zero, i.e. that
$\det(A - \lambda I) = 0$ — the **characteristic polynomial**. For
$A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$,

$$
\det \begin{bmatrix} 2 - \lambda & 1 \\ 1 & 2 - \lambda \end{bmatrix}
= (2-\lambda)^2 - 1 = \lambda^2 - 4\lambda + 3 = (\lambda - 3)(\lambda - 1),
$$

so $\lambda_1 = 3$, $\lambda_2 = 1$. Substituting $\lambda_1 = 3$ into
$(A - 3I)v = 0$ gives $-v_1 + v_2 = 0$, the direction $(1, 1)$; $\lambda_2 = 1$
gives $(1, -1)$. Normalizing, the eigenvectors are $\tfrac{1}{\sqrt 2}(1,1)$ and
$\tfrac{1}{\sqrt 2}(1,-1)$ — orthogonal, as the spectral theorem promises for a
symmetric $A$. The map stretches the $(1,1)$ direction by $3$ and leaves $(1,-1)$
fixed. The trace $2 + 2 = 4$ equals $\lambda_1 + \lambda_2$, and the determinant
$4 - 1 = 3$ equals $\lambda_1 \lambda_2$, the two scalar checks below.

$$
% caption: Along each eigenvector axis $A$ is pure scaling ($v_1$ stretched,
% $v_2$ shrunk), so the unit circle maps to an axis-aligned ellipse.
\begin{tikzpicture}[>=stealth, font=\small, scale=1.2]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % faint unit circle and resulting ellipse (eigenvalues 1.9, 0.5)
  \draw[black, dashed] (0,0) circle (1);
  \draw[acc, thick] (0,0) ellipse (1.9 and 0.5);
  % eigenvector 1 (x-axis): stretched. label below the axis, away from arrows
  \draw[->, black] (0,0) -- (1,0) node[pos=0.55, below, font=\footnotesize] {$v_1$};
  \draw[->, green, very thick] (0,0) -- (1.9,0)
    node[anchor=west, font=\footnotesize, text=green] {$A v_1$};
  % eigenvector 2 (y-axis): shrunk. label to the upper-left, clear of the red arrow
  \draw[->, black] (0,0) -- (0,1) node[pos=0.85, left, font=\footnotesize] {$v_2$};
  \draw[->, red, very thick] (0.0,0) -- (0,0.5);
  \node[red, font=\footnotesize, anchor=south west] at (0.06,0.5) {$A v_2$};
\end{tikzpicture}
$$

> **Theorem (Spectral theorem).** Every real symmetric matrix $A = A^\top$ has an
> eigendecomposition with **real** eigenvalues and an **orthogonal** eigenvector
> matrix $Q$: $A = Q \diag(\lambda) Q^\top$. The eigenvectors form an
> orthonormal basis aligned with the principal axes of the quadratic form $x^\top A x$.

### Quadratic forms and positive-definiteness

The eigenvalues classify the **quadratic form** $f(x) = x^\top A x$ (for symmetric
$A$). In the eigenbasis, writing $y = Q^\top x$,

$$
x^\top A x = x^\top Q \diag(\lambda) Q^\top x = y^\top \diag(\lambda)\, y = \sum_i \lambda_i\, y_i^2,
$$

so the sign of the form is decided entirely by the signs of the eigenvalues.

| Condition on eigenvalues | Name | Quadratic form $x^\top A x$ |
| --- | --- | --- |
| all $\lambda_i > 0$ | positive definite | $> 0$ for all $x \neq 0$ |
| all $\lambda_i \ge 0$ | positive semidefinite | $\ge 0$ for all $x$ |
| all $\lambda_i < 0$ | negative definite | $< 0$ for all $x \neq 0$ |
| mixed signs | indefinite | both signs occur |

Positive-definiteness is the multivariate "second derivative is positive": a
critical point where the **Hessian** is positive definite is a local minimum, where
it is negative definite a maximum, and where it is indefinite a saddle point. This is the
classification that drives the entire study of the
[optimization landscape](/deep-learning/optimization/the-optimization-landscape).

## Singular value decomposition

Eigendecomposition needs a square, diagonalizable matrix. The **singular value
decomposition** has no such restriction; it factors _any_ matrix.[^gf-svd]

> **Theorem (SVD).** Every matrix $A \in \mathbb{R}^{m \times n}$ factors as
> $A = U D V^\top$, where $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$
> are orthogonal and $D \in \mathbb{R}^{m \times n}$ is diagonal with nonnegative
> entries $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$, the **singular values**.

The columns of $U$ are **left-singular vectors** (eigenvectors of $A A^\top$), the
columns of $V$ are **right-singular vectors** (eigenvectors of $A^\top A$), and the
singular values are the square roots of the shared nonzero eigenvalues,
$\sigma_i = \sqrt{\lambda_i(A^\top A)}$. Geometrically the factorization reads
right-to-left as **rotate, scale, rotate**: $V^\top$ rotates the input, $D$ scales
along axes, $U$ rotates the output. A unit circle becomes an ellipse whose axis
lengths are the singular values.

$$
% caption: SVD as rotate ($V^{T}$), scale ($D$), rotate ($U$): the unit circle
% becomes an ellipse whose semi-axes are the singular values $\sigma_1,\sigma_2$.
\begin{tikzpicture}[>=stealth, font=\small, scale=0.92]
  \definecolor{acc}{HTML}{2348F2}
  % stage 1: unit circle with a marked vector
  \draw[black] (0,0) circle (0.9);
  \draw[->, acc, thick] (0,0) -- (0.64,0.64);
  \node[font=\footnotesize, anchor=north] at (0,-1.15) {unit circle};
  % arrow VT
  \draw[->, acc, very thick] (1.3,0) -- (2.2,0) node[midway, above, font=\footnotesize, text=acc] {$V^{T}$};
  % stage 2: rotated circle (still circle) with rotated vector
  \begin{scope}[xshift=3.5cm]
    \draw[black] (0,0) circle (0.9);
    \draw[->, acc, thick] (0,0) -- (0,0.9);
    \node[font=\footnotesize, anchor=north] at (0,-1.15) {rotated};
  \end{scope}
  % arrow D
  \draw[->, acc, very thick] (4.8,0) -- (5.7,0) node[midway, above, font=\footnotesize, text=acc] {$D$};
  % stage 3: ellipse (scaled), axes sigma1 sigma2
  \begin{scope}[xshift=7.4cm]
    \draw[black] (0,0) ellipse (1.4 and 0.6);
    \draw[->, black] (0,0) -- (1.4,0) node[anchor=north, font=\footnotesize, black] {$s_1$};
    \draw[->, black] (0,0) -- (0,0.6) node[anchor=south east, font=\footnotesize, black] {$s_2$};
    \node[font=\footnotesize, anchor=north] at (0,-1.15) {scaled};
  \end{scope}
  % arrow U
  \draw[->, acc, very thick] (9.1,0) -- (10.0,0) node[midway, above, font=\footnotesize, text=acc] {$U$};
  % stage 4: single rotated ellipse (output of U)
  \begin{scope}[xshift=11.9cm]
    \draw[acc, thick, rotate=28] (0,0) ellipse (1.4 and 0.6);
    \node[font=\footnotesize, anchor=north] at (0,-1.15) {rotated};
  \end{scope}
\end{tikzpicture}
$$

In the caption, $s_1, s_2$ stand for the singular values $\sigma_1, \sigma_2$,
the ellipse's semi-axis lengths. (Greek sigma is spelled out in the figure to keep
the node text renderable.)

### The Moore–Penrose pseudoinverse

When $A$ is not square, $Ax = b$ is over- or under-determined and has no exact
inverse. The SVD supplies the next best thing: the **pseudoinverse**
$A^{+} = V D^{+} U^\top$, where $D^{+}$ inverts each nonzero singular value
($1/\sigma_i$) and transposes. It returns the least-error, smallest-norm answer.

| Shape of $A$ | System $Ax = b$ | What $x = A^{+}b$ gives |
| --- | --- | --- |
| tall ($m > n$), full rank | over-determined, no exact $x$ | the **least-squares** solution minimizing $\norm{Ax - b}_2$ |
| wide ($m < n$), full rank | under-determined, many $x$ | the solution of **minimum** $\norm{x}_2$ |
| square, full rank | unique | exactly $A^{-1}b$ |

The least-squares case is the normal-equations solution
$A^{+} = (A^\top A)^{-1} A^\top$ seen for
[linear regression](/deep-learning/foundations/linear-models-and-the-perceptron),
now derived through the SVD and valid even when $A^\top A$ is singular.

## Trace and determinant

Two scalar summaries of a square matrix close the toolkit.

> **Definition (Trace).** The sum of the diagonal entries,
> $\Tr(A) = \sum_i A_{i,i}$, equal to the sum of the eigenvalues. It
> is invariant under cyclic permutation, $\Tr(ABC) = \Tr(BCA)$,
> and gives the Frobenius norm as $\norm{A}_F = \sqrt{\Tr(A A^\top)}$.

> **Definition (Determinant).** A scalar $\det(A) = \prod_i \lambda_i$, the product
> of the eigenvalues, equal to the signed volume scaling factor of the map $A$. It
> is zero **iff** $A$ is singular: the map collapses space onto a lower-dimensional
> subspace, destroying volume.

## Worked example: principal components analysis

PCA is the canonical application of this machinery: a derivation in which the answer to
a geometric optimization _is_ a set of eigenvectors.[^gf-pca] The setup: $m$ points
$x^{(1)}, \dots, x^{(m)}$ in $\mathbb{R}^{n}$ (assume centered, mean zero), to be
compressed to $\ell < n$ dimensions with the least reconstruction error.

Encode each point by projecting onto an orthonormal set of directions stacked as
columns of $D \in \mathbb{R}^{n \times \ell}$ ($D^\top D = I_\ell$), and decode by
projecting back:

$$
\text{encode: } c = D^\top x, \qquad \text{decode: } r(x) = D c = D D^\top x.
$$

Choose $D$ to minimize the total squared reconstruction error, $\sum_i \norm{x^{(i)} - D D^\top x^{(i)}}_2^2$.

> **Theorem (PCA optimal basis).** The reconstruction error is minimized by taking
> the columns of $D$ to be the $\ell$ eigenvectors of the covariance
> $X^\top X$ with the largest eigenvalues — equivalently, the top $\ell$
> right-singular vectors of the data matrix $X$.

> **Proof.** Stack the points as rows of $X \in \mathbb{R}^{m \times n}$. For a
> single direction ($\ell = 1$, unit vector $d$), the reconstruction is $d d^\top x$
> and the total error expands as
>
> $$
> \sum_i \norm{x^{(i)} - d d^\top x^{(i)}}_2^2
> = \sum_i \parens{ \norm{x^{(i)}}_2^2 - (d^\top x^{(i)})^2 }
> = \text{const} - \sum_i (d^\top x^{(i)})^2,
> $$
>
> using $d^\top d = 1$ to cancel the cross term. Minimizing error therefore
> **maximizes** the captured variance $\sum_i (d^\top x^{(i)})^2 = d^\top X^\top X\, d$,
> subject to $d^\top d = 1$. Form the Lagrangian
> $\mathcal{L}(d, \lambda) = d^\top X^\top X\, d - \lambda(d^\top d - 1)$; setting
> $\nabla_d \mathcal{L} = 0$ gives
>
> $$
> 2 X^\top X\, d - 2\lambda d = 0 \;\Longrightarrow\; X^\top X\, d = \lambda d.
> $$
>
> So the optimal $d$ is an **eigenvector** of $X^\top X$, and the captured variance
> equals its eigenvalue $\lambda$ — maximized by the **largest** eigenvalue. For
> general $\ell$, the same argument with orthogonality constraints yields the top
> $\ell$ eigenvectors. $\qed$

The covariance $X^\top X$ is symmetric, so the spectral theorem guarantees a real,
orthonormal eigenbasis: the **principal axes**. The first principal component is
the direction of greatest variance; projecting onto it loses the least information.

$$
% caption: PCA on a 2D cloud. The first principal axis is the direction of
% maximum variance; projecting onto it (drop-lines) is the best rank-1 fit.
\begin{tikzpicture}[>=stealth, font=\small, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % principal axis direction ~ (1, 0.5), unit-ish; draw long line through origin
  % points scattered around the line
  \def\pts{(-2.2,-1.0),(-1.5,-0.9),(-1.1,-0.4),(-0.6,-0.45),(-0.2,0.1),(0.3,-0.05),(0.7,0.5),(1.1,0.4),(1.6,0.95),(2.2,1.0),(0.0,0.45),(-0.9,-0.15)}
  % first principal axis
  \draw[green, very thick] (-2.8,-1.4) -- (2.8,1.4)
    node[anchor=south west, font=\footnotesize, text=green] {1st principal axis};
  % second axis (orthogonal), shorter
  \draw[acc, thick] (-0.7,1.4) -- (0.7,-1.4)
    node[anchor=north west, font=\footnotesize, text=acc] {2nd axis};
  % projection drop-lines onto first axis (axis direction u=(2,1)/sqrt5)
  % projection of point p onto line: ( (p.u) ) u
  \foreach \px/\py in {-1.5/-0.9, -0.2/0.1, 0.7/0.5, 1.6/0.95, 0.0/0.45, -0.9/-0.15}{
    % t = (2*px + 1*py)/5 ; foot = (2t, t)
    \pgfmathsetmacro{\tt}{(2*\px + \py)/5}
    \pgfmathsetmacro{\fx}{2*\tt}
    \pgfmathsetmacro{\fy}{\tt}
    \draw[black] (\px,\py) -- (\fx,\fy);
  }
  % the points
  \foreach \p in \pts { \fill[black] \p circle (1.7pt); }
\end{tikzpicture}
$$

The compression keeps the top $\ell$ axes and discards the rest. Because variance
along the discarded axes is smallest, the data, projected onto an
$\ell$-dimensional subspace, loses the least possible squared error, which is
exactly the SVD's low-rank approximation guarantee restated for data.

## Low rank as a design principle

Low rank has also become a design principle for large models, not only an
analysis tool.

**Low-rank adaptation.** Fine-tuning a large model by updating every weight is
expensive. **LoRA** (Hu et al., 2021) freezes a pretrained weight matrix $W$ and
learns only a low-rank correction $W + BA$, where $B \in \mathbb{R}^{m \times r}$
and $A \in \mathbb{R}^{r \times n}$ with $r \ll \min(m, n)$. The update $BA$ has
rank at most $r$, so it costs $r(m + n)$ parameters instead of $mn$ — for a
$4096 \times 4096$ layer and $r = 8$, that is $65{,}536$ trainable numbers instead
of $16.8$ million. The hypothesis, borne out empirically, is that the _adaptation_ a task
needs lies on a low-dimensional subspace even when the model does not: the SVD's
rank structure applied to a weight update.

**Randomized SVD.** The exact SVD costs $O(mn \min(m,n))$, prohibitive for the
huge matrices in modern pipelines. **Randomized SVD** (Halko, Martinsson, Tropp,
2011) projects the matrix onto a small random subspace, computes an exact
decomposition of the tiny result, and recovers the top-$k$ singular vectors in
$O(mnk)$ — the standard route to PCA on data too large for the full factorization.

**Attention as a matrix product.** Transformer attention is
$\softmax(QK^\top / \sqrt{d})\,V$: two matrix products with a
row-wise softmax between them (Vaswani et al., 2017). Every idea in this lesson —
shapes that must line up, the contraction that sums an inner dimension away, the
$1/\sqrt{d}$ scaling that keeps the dot products in a stable range — appears
in this one operation at the center of the field.[^lora][^attention]

## Takeaways

- Every quantity in a network is a **tensor**; layers are **matrix products**
  ($Wx + b$), gates and gradient masks are **Hadamard products** ($A \odot B$).
- $Ax = b$ is solvable **iff** $b$ lies in the column space; the inverse exists
  **iff** $A$ is square and full rank. Geometrically $A$ maps the unit square to a
  parallelogram whose signed area is $\det A$.
- **Norms** measure size; $L^1$ (diamond, sparsity), $L^2$ (circle, distance),
  $L^\infty$ (square, max), Frobenius (matrix). The unit-ball corners of $L^1$
  explain why it zeroes coordinates.
- **Eigendecomposition** $A = V \diag(\lambda) V^{-1}$ diagonalizes a
  square map along its invariant axes; the spectral theorem makes this orthogonal
  for symmetric $A$, and the eigenvalue signs classify the quadratic form
  $x^\top A x$ (positive-definite $\Rightarrow$ local minimum).
- **SVD** $A = U D V^\top$ exists for _any_ matrix and reads as rotate–scale–rotate;
  it yields the **pseudoinverse** $A^{+}$, the least-squares / minimum-norm solver
  for non-invertible systems.
- **PCA** is the worked example: minimizing reconstruction error _is_ maximizing
  projected variance, whose optimum is the **top eigenvectors of $X^\top X$**, the
  same statement as the SVD's low-rank approximation.

[^gf-linalg]: **Goodfellow**, _Deep Learning_, Ch. 2 — Linear Algebra: the minimal algebra a network needs, framed as the objects (tensors) and the operations (products, decompositions) that move them through a model.
[^gf-broadcast]: **Goodfellow**, _Deep Learning_, §2.1 — Scalars, Vectors, Matrices and Tensors: implicit broadcasting of a bias vector across a matrix, $C = A + b$, as the convenient shape-shorthand frameworks adopt.
[^stevens-tensor]: **Stevens**, _Deep Learning with PyTorch_, Ch. 3 — It Starts with a Tensor: the tensor as the fundamental storage type, with shape, stride, and dtype the first things any operation must reconcile.
[^gf-products]: **Goodfellow**, _Deep Learning_, §2.2–§2.3 — Multiplying Matrices and Vectors: the contraction (matrix) product versus the elementwise (Hadamard) product, and the dot product as the alignment special case.
[^gf-svd]: **Goodfellow**, _Deep Learning_, §2.8 — Singular Value Decomposition: $A = UDV^\top$ for any real matrix, generalizing eigendecomposition to non-square and non-diagonalizable maps.
[^gf-pca]: **Goodfellow**, _Deep Learning_, §2.12 — Example: Principal Components Analysis: deriving PCA as the linear code that minimizes $L^2$ reconstruction error, whose optimum is the top eigenvectors of the covariance.
[^lora]: Hu, Shen, Wallis, Allen-Zhu, Li, Wang, Wang, Chen (2021), _LoRA: Low-Rank Adaptation of Large Language Models_, arXiv:2106.09685 — a rank-$r$ additive update $BA$ to a frozen weight matrix; and Halko, Martinsson, Tropp (2011), _Finding Structure with Randomness_, SIAM Review 53, the randomized range-finder behind fast approximate SVD/PCA.
[^attention]: Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, Polosukhin (2017), _Attention Is All You Need_, NeurIPS — scaled dot-product attention $\softmax(QK^\top/\sqrt{d})V$ as the matrix-product core of the transformer.