Linear Algebra

Key ideas

Objects and shapes. A vector is a 1-D array (one example's features), a matrix a 2-D array (a dense layer's weights), a tensor any $k$-D array. With one example per row, a mini-batch of $n$ examples with $d$ features is $X\in\mathbb{R}^{n\times d}$. A product $AB$ needs matching inner sizes: $(n\times k)(k\times m)\to n\times m$, and entry $(i,j)$ is row $i$ of $A$ dotted with column $j$ of $B$¹. A batch of 32 examples with 10 features times a $10\times64$ weight matrix gives $32\times64$: one row of 64 outputs per example.

Norms¹: $\lVert x\rVert_1=\sum|x_i|$ (Manhattan, city-block distance), $\lVert x\rVert_2=\sqrt{\sum x_i^2}$, $\lVert x\rVert_\infty=\max|x_i|$. Every norm satisfies $\lVert\alpha x\rVert=|\alpha|\lVert x\rVert$ and the triangle inequality $\lVert x+y\rVert\le\lVert x\rVert+\lVert y\rVert$ — equality is not guaranteed. Among the $p$-norms only $\ell_2$ comes from an inner product, since only it satisfies the parallelogram law⁷. $\lVert x\rVert_1$ is the walking distance on a grid (no diagonals).

Dot products and angles²: $x^\top y=\lVert x\rVert\lVert y\rVert\cos\theta$; orthogonal means $x^\top y=0$; cosine similarity ignores length. For unit vectors $\lVert u-v\rVert^2=2-2u^\top v$. The closest point to $x$ on the line through a unit vector $u$ is $(x^\top u)\,u$. Entry $(i,j)$ of $HH^\top$ is the dot product of rows $i$ and $j$ — a cosine only if the rows are normalised.

Rank, null space, invertibility. Rank = number of linearly independent columns ²; rank + nullity = number of columns⁴. The solutions of $Ax=0$ form a subspace (the null space) of dimension $n-\operatorname{rank}A$: sums and multiples of solutions are solutions, and a nullity of 2 or more means they are not all multiples of one vector. For a square $A$ these are equivalent: $A$ invertible, $\det A\ne0$, full rank, columns independent, null space $\{0\}$, $Ax=b$ uniquely solvable for every $b$, 0 not an eigenvalue². Pairwise independence of columns is weaker and not enough. A column times a row ($cr^\top$) has rank 1, so its determinant is 0; a set of vectors containing $0$ is always dependent. For $2\times2$, $\begin{bmatrix}a&b\\c&d\end{bmatrix}^{-1}=\frac1{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$.

Linear maps and subspaces. A linear map is fixed by its values on a basis: write the new input as a combination of inputs you know and combine their images the same way. For a linear map $T:V\to W$, $\dim V=\dim\ker T+\dim\operatorname{im}T$ (the rank theorem again)⁴. Two subspaces of a space $X$ satisfy $\dim(V\cap W)\ge\dim V+\dim W-\dim X$, because $\dim(V+W)\le\dim X$.

Determinant = signed factor by which $A$ scales area/volume²; for $2\times2$, $ad-bc$. $\det(AB)=\det A\det B$, $\det A^{-1}=1/\det A$. If $y=Ax$, densities rescale: $p_y(y)=p_x(x)/|\det A|$.

Eigenvalues. $Av=\lambda v$, $v\ne0$; eigenvalues are roots of $\det(A-\lambda I)$. Then $\det A=\prod\lambda_i$, $\operatorname{tr}A=\sum\lambda_i$ — read them off the characteristic polynomial: its constant term is $\det A$ and the coefficient of $\lambda^{n-1}$ is $(-1)^{n-1}\operatorname{tr}A$. $A^k$, $A^{-1}$, $cA$ keep the eigenvectors with eigenvalues $\lambda^k$, $1/\lambda$, $c\lambda$³. Symmetric matrices have real eigenvalues and orthogonal eigenvectors, $A=W\Sigma W^\top$³. Similar matrices ($B=P^{-1}AP$) share eigenvalues, trace and determinant. A projection ($P^2=P$) has eigenvalues 0 and 1 only, is diagonalizable, and its trace equals its rank. $A+A^\top$ and $A^\top A$ are always symmetric; $A$ maps orthogonal $e_1, e_2$ to orthogonal vectors exactly when its columns are orthogonal, i.e. $A^\top A$ is diagonal.

Power iteration. Repeatedly multiplying a random vector by $A$ (and normalising) aligns it with the eigenvector of the largest $|\lambda|$; the other components shrink like $(\lambda_i/\lambda_1)^k$³.

Singular values. $A=U\Sigma V^\top$; the singular values are the square roots of the eigenvalues of $A^\top A$, and the spectral norm $\lVert A\rVert_2$ is the largest one⁶. Power iteration on $AA^\top$ therefore estimates $\sigma_{\max}^2$ from below: a ratio $\lVert AA^\top u\rVert/\lVert u\rVert$ can never exceed $\lVert AA^\top\rVert_2=\sigma_{\max}^2$.

Random matrices. Take a $d\times d$ matrix with independent entries of mean 0 and variance 1 (e.g. standard normal). Its largest $|\text{eigenvalue}|$ is about $\sqrt d$ (circular law)³, but its spectral norm is $2\sqrt d\,(1+o(1))$ as $d\to\infty$ (Bai–Yin law, needs a finite fourth moment); for Gaussian entries $\mathbb{E}\lVert G\rVert_2\le2\sqrt d$ for every $d$⁸. So a matrix of size-1 entries stretches some vector by about $2\sqrt d$ — why initial weights are scaled by $1/\sqrt d$.

Cost of products. $(p\times q)(q\times r)$ costs $pqr$ multiplications. Matrix multiplication is associative, so choose the parenthesisation that keeps intermediate results small⁵. For a tall $A\in\mathbb{R}^{n\times d}$ ($n\gg d$), $A(A^\top A)$ costs $2nd^2$ but $(AA^\top)A$ costs $2n^2d$, because it builds an $n\times n$ intermediate.

Einsum. Repeated indices are summed: $\operatorname{tr}(A)=a_{ii}$, $(AB)_{ik}=a_{ij}b_{jk}$; in code torch.einsum('ij,jk->ik', A, B)².

Formulas

Worked example

$A=\begin{bmatrix}2&1\\1&2\end{bmatrix}$: $\det(A-\lambda I)=(2-\lambda)^2-1=0$ gives $\lambda=3,1$ with eigenvectors $(1,1)$ and $(1,-1)$. Check: trace $4=3+1$, determinant $3=3\cdot1$, so $A$ triples areas. $A^{-1}$ has eigenvalues $1/3$ and $1$; power iteration on $A$ approaches $(1,1)/\sqrt2$, with the error shrinking by $\lambda_2/\lambda_1=1/3$ per step.

Chain cost with $A_{10\times100}$, $B_{100\times5}$, $C_{5\times50}$: $(AB)C$ costs $10\cdot100\cdot5+10\cdot5\cdot50=7{,}500$; $A(BC)$ costs $100\cdot5\cdot50+10\cdot100\cdot50=75{,}000$.

In code

import numpy as np

A = np.array([[2.0, 1.0], [1.0, 2.0]])
print(np.linalg.eigvalsh(A))                    # [1. 3.]
print(np.trace(A), round(np.linalg.det(A), 6))  # 4.0 3.0
B = np.array([[1.0, 2.0], [0.0, 2.0]])
print(np.linalg.svd(B, compute_uv=False))       # [2.92080963 0.68474165]
rng = np.random.default_rng(0)
d = 1000
G = rng.standard_normal((d, d))
print(round(np.linalg.norm(G, 2) / np.sqrt(d), 3))                # 1.998
print(round(np.abs(np.linalg.eigvals(G)).max() / np.sqrt(d), 3))  # 1.014

Common pitfalls

• Shapes: with examples as rows, $X$ is (batch × features), not the transpose.
• $|x+y|=|x|+|y|$ is false in general; only the triangle inequality holds¹.
• Determinant 0 ⇔ not invertible; a large determinant does not mean "well-conditioned".
• Eigenvectors are shared by $A$, $A^2$, $A^{-1}$, $2A$ — the eigenvalues change³.
• $\operatorname{tr}(AB)\ne\operatorname{tr}A\cdot\operatorname{tr}B$, and $\operatorname{tr}(A^2)$ can be negative; but $\operatorname{tr}(AB)=\operatorname{tr}(BA)$.
• Singular values ≠ eigenvalues unless $A$ is symmetric positive semidefinite⁶.
• Matrix products are associative but not commutative; order of evaluation changes the cost, not the result⁵.