Chapter 2 Formula Sheet

Pure reference. Every entry links back to the page that derives it, and the when you use it column is the reason the entry is here at all — a formula you cannot place is a formula you will not reach for.

Symbols follow Notation and Symbols: lowercase italic scalars, lowercase bold vectors, uppercase bold matrices, calligraphic sets.

Systems of linear equations — §2.1

result	statement	when you use it
general form	$\displaystyle\sum_{j=1}^{n} a_{ij}x_j = b_i,\; i = 1,\dots,m$	writing a problem down before doing anything
matrix form	$\mathbf{A}\mathbf{x} = \mathbf{b}$	everywhere
columns form	$\displaystyle\sum_{j=1}^{n} x_j\mathbf{a}_j = \mathbf{b}$	reframing solvability as reachability — the most useful identity in the chapter
three outcomes	none, exactly one, or infinitely many — never two	classifying a system before solving it
why not two	$\mathbf{A}(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) = \mathbf{b}$ whenever both are solutions	proving the trichotomy in one line
geometry	each equation is a hyperplane; the solution set is their intersection	building intuition in 2-D and 3-D

Matrices — §2.2

result	statement	when you use it
matrix	$\mathbf{A} \in \mathbb{R}^{m\times n}$, entry $a_{ij}$ in row $i$, column $j$	always row index first
addition	$(\mathbf{A}+\mathbf{B})_{ij} = a_{ij} + b_{ij}$, same shape required	element-wise, unlike multiplication
multiplication	$c_{ij} = \displaystyle\sum_{l=1}^{n} a_{il}b_{lj}$, inner dims must match	composition of two linear maps
shape rule	$(m\times n)(n\times k) = (m\times k)$	catching a bug before running anything
Hadamard product	$c_{ij} = a_{ij}b_{ij}$ — a different operation	it is what A * B computes in NumPy
columns are images	$j$-th column of $\mathbf{A}$ is $\mathbf{A}\mathbf{e}_j$	the idea that makes multiplication obvious
associativity	$(\mathbf{A}\mathbf{B})\mathbf{C} = \mathbf{A}(\mathbf{B}\mathbf{C})$	reordering a product chain to cut cost
distributivity	$(\mathbf{A}+\mathbf{B})\mathbf{C} = \mathbf{A}\mathbf{C} + \mathbf{B}\mathbf{C}$	expanding a derivation
identity	$\mathbf{I}_m\mathbf{A} = \mathbf{A}\mathbf{I}_n = \mathbf{A}$, and $\mathbf{I}_m \neq \mathbf{I}_n$	note the two different sizes for non-square $\mathbf{A}$
non-commutativity	$\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}$; shapes can even differ	never reorder a product
inverse	$\mathbf{A}\mathbf{A}^{-1} = \mathbf{I} = \mathbf{A}^{-1}\mathbf{A}$, square only, unique when it exists	undoing a bijective map
$2\times2$ inverse	$\mathbf{A}^{-1} = \dfrac{1}{a_{11}a_{22}-a_{12}a_{21}}\begin{bmatrix}a_{22} & -a_{12}\\ -a_{21} & a_{11}\end{bmatrix}$	hand calculation; the denominator is the determinant
transpose	$(\mathbf{A}^\top)_{ij} = a_{ji}$	reshaping to make dimensions agree
symmetric	$\mathbf{A} = \mathbf{A}^\top$, square only	covariance matrices, Gram matrices, Hessians

The identities, and the two traps

$$\begin{aligned} (\mathbf{A}\mathbf{B})^{-1} &= \mathbf{B}^{-1}\mathbf{A}^{-1} &&\text{true — the order \textbf{flips}}\\ (\mathbf{A}\mathbf{B})^\top &= \mathbf{B}^\top\mathbf{A}^\top &&\text{true — the order flips here too}\\ (\mathbf{A}^\top)^\top &= \mathbf{A} &&\text{true}\\ (\mathbf{A}+\mathbf{B})^\top &= \mathbf{A}^\top + \mathbf{B}^\top &&\text{true}\\ (\mathbf{A}^{-1})^\top &= (\mathbf{A}^\top)^{-1} &&\text{true}\\[6pt] (\mathbf{A}+\mathbf{B})^{-1} &\neq \mathbf{A}^{-1} + \mathbf{B}^{-1} &&\textbf{FALSE} \;-\; \tfrac{1}{2+4} \neq \tfrac12 + \tfrac14\\ \mathbf{A}, \mathbf{B} \text{ symmetric} &\not\Rightarrow \mathbf{A}\mathbf{B} \text{ symmetric} &&\textbf{FALSE} \;-\; \text{but } \mathbf{A}^\top\mathbf{A} \text{ always is} \end{aligned}$$

Solving systems — §2.3

result	statement	when you use it
elementary transformations	exchange two rows; multiply a row by $\lambda \neq 0$; add one row to another	each is reversible, so the solution set never changes
augmented matrix	$[\,\mathbf{A} \mid \mathbf{b}\,]$	avoiding rewriting variable names every step
row-echelon form	zero rows at the bottom; each pivot strictly right of the one above	reading off rank, consistency, free variables
reduced row-echelon form	additionally every pivot is $1$ and alone in its column	reading the solution straight off
basic / free variables	pivot columns give basic; the rest are free	counting the solution set’s dimension
free variable count	$n - \operatorname{rk}(\mathbf{A})$	predicting the answer’s shape before solving
general solution	$\mathbf{x} = \mathbf{x}_p + \lambda_1\mathbf{n}_1 + \cdots + \lambda_k\mathbf{n}_k$	the shape of every solution set in the book
why it works	$\mathbf{A}(\mathbf{x}_p + \mathbf{n}) = \mathbf{b} + \mathbf{0}$	one line, and it explains the whole decomposition
minus-1 trick	extend the RREF so the diagonal holds only $1$ and $-1$; the $-1$ columns are a null-space basis	reading a kernel basis without further elimination
inversion	$[\mathbf{A} \mid \mathbf{I}_n] \rightsquigarrow [\mathbf{I}_n \mid \mathbf{A}^{-1}]$	it is $n$ systems at once, which is why inv costs more than solve
pseudo-inverse	$\mathbf{A}^{+} = (\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top$	do not compute it this way — it squares the condition number
cost	Gaussian elimination is $O(n^3)$	why direct methods stop at thousands, not millions
large systems	stationary iterative (Jacobi, Gauss–Seidel) or Krylov (conjugate gradients)	huge sparse problems; needs a norm, hence §3.1

Vector spaces — §2.4

Group $(\mathcal{G}, \otimes)$ — four axioms:

$$\begin{aligned} &\text{closure} && \forall x,y \in \mathcal{G}: x \otimes y \in \mathcal{G}\\ &\text{associativity} && (x \otimes y) \otimes z = x \otimes (y \otimes z)\\ &\text{neutral element} && \exists e\; \forall x: x \otimes e = e \otimes x = x\\ &\text{inverse element} && \forall x\; \exists y: x \otimes y = y \otimes x = e \end{aligned}$$

Abelian adds $x \otimes y = y \otimes x$. General linear group $GL(n,\mathbb{R})$: the invertible $n\times n$ matrices under multiplication — a group, and not Abelian.

Vector space $(\mathcal{V}, +, \cdot)$ with $+ : \mathcal{V}\times\mathcal{V} \to \mathcal{V}$ and $\cdot : \mathbb{R}\times\mathcal{V} \to \mathcal{V}$:

$$\begin{aligned} &1.\; (\mathcal{V}, +) \text{ is an Abelian group}\\ &2.\; \lambda(\mathbf{x}+\mathbf{y}) = \lambda\mathbf{x} + \lambda\mathbf{y} \quad\text{and}\quad (\lambda+\psi)\mathbf{x} = \lambda\mathbf{x} + \psi\mathbf{x}\\ &3.\; \lambda(\psi\mathbf{x}) = (\lambda\psi)\mathbf{x}\\ &4.\; 1\cdot\mathbf{x} = \mathbf{x} \end{aligned}$$

result	statement	when you use it
no vector product	$\mathbf{a}\mathbf{b}$ is undefined	only $\mathbf{a}\mathbf{b}^\top \in \mathbb{R}^{n\times n}$ and $\mathbf{a}^\top\mathbf{b} \in \mathbb{R}$ exist
subspace test	$\mathcal{U} \neq \emptyset$ with $\mathbf{0} \in \mathcal{U}$; closed under scaling; closed under addition	all three, every time
trivial subspaces	$V$ itself and $\{\mathbf{0}\}$	edge cases in proofs
homogeneous solutions	$\{\mathbf{x} : \mathbf{A}\mathbf{x} = \mathbf{0}\}$ is a subspace	it is the kernel
inhomogeneous solutions	$\{\mathbf{x} : \mathbf{A}\mathbf{x} = \mathbf{b}\}$, $\mathbf{b} \neq \mathbf{0}$, is not	it is an affine subspace (§2.8)
intersections	the intersection of arbitrarily many subspaces is a subspace	building subspaces from constraints
converse	every subspace of $\mathbb{R}^n$ is the solution space of some $\mathbf{A}\mathbf{x} = \mathbf{0}$	subspaces and homogeneous systems are the same objects
bounded sets	a bounded set is never a subspace unless it is $\{\mathbf{0}\}$	distinguishing subspaces from convex sets (§7.3)

Linear independence — §2.5

$$\text{linear combination:}\quad \mathbf{v} = \sum_{i=1}^{k}\lambda_i\mathbf{x}_i$$ $$\text{\textbf{dependent}} \iff \exists\,\lambda_i \text{ not all zero with } \sum_i \lambda_i\mathbf{x}_i = \mathbf{0}$$ $$\text{\textbf{independent}} \iff \sum_i \lambda_i\mathbf{x}_i = \mathbf{0} \text{ forces every } \lambda_i = 0$$

shortcut	statement	when you use it
no third option	every set is dependent or independent	—
zero vector	any set containing $\mathbf{0}$ is dependent	the cheapest test; do it first
duplicates	two identical vectors force dependence	second cheapest
multiples	$\mathbf{x}_i = \lambda\mathbf{x}_j$ for any $\lambda$ forces dependence	sign of $\lambda$ is irrelevant
the characterisation	nonzero vectors with $k \ge 2$ are dependent iff one is a combination of the others	the conceptual statement
counting bound	$m$ vectors in $\mathbb{R}^k$ with $m > k$ are dependent	no arithmetic needed
pivot-column test	write as columns, reduce; independent iff every column is a pivot column	the reliable method
ordering caveat	which vectors survive depends on the order offered; the count does not	comparing two people’s answers
coefficient shortcut	if $\mathbf{x}_j = \mathbf{B}\boldsymbol\lambda_j$ with $\mathbf{B}$‘s columns independent, then $\{\mathbf{x}_j\}$ independent iff $\{\boldsymbol\lambda_j\}$ is	testing combinations of combinations cheaply

Basis and rank — §2.6

result	statement	when you use it
span	the set of all linear combinations; always a subspace	manufacturing a subspace
generating set	spans all of $V$	necessary but not sufficient for a basis
basis	a linearly independent generating set	the four characterisations below
dimension	the common size of every basis, $\dim(V)$	it is well defined precisely because the size is invariant
subspace dimension	$\dim(U) \le \dim(V)$, with equality iff $U = V$	no same-dimension proper subspaces
dimension caveat	it counts directions, not components	a line in $\mathbb{R}^{1000}$ is one-dimensional
basis of a subspace	spanning vectors as columns → row-echelon form → keep the pivot columns	extracting a basis from a spanning set
dimension formula	$\dim(U_1 \cap U_2) = \dim U_1 + \dim U_2 - \dim(U_1 + U_2)$	predicting an intersection’s size before computing it

Four equivalent characterisations of a basis $\mathcal{B}$:

$$\begin{aligned} &1.\; \mathcal{B} \text{ is a basis}\\ &2.\; \mathcal{B} \text{ is a minimal generating set}\\ &3.\; \mathcal{B} \text{ is a maximal linearly independent set}\\ &4.\; \text{every } \mathbf{x} \text{ has a \textbf{unique} representation } \mathbf{x} = \sum_i \lambda_i\mathbf{b}_i \end{aligned}$$

Rank $\operatorname{rk}(\mathbf{A})$ — the number of independent columns, which equals the number of independent rows:

property	statement	when you use it
row = column rank	$\operatorname{rk}(\mathbf{A}) = \operatorname{rk}(\mathbf{A}^\top)$	switching whichever is easier to count
image dimension	$\dim(\operatorname{Im}(\mathbf{A})) = \operatorname{rk}(\mathbf{A})$	how much the map can reach
invertibility	$\mathbf{A} \in \mathbb{R}^{n\times n}$ invertible $\iff \operatorname{rk}(\mathbf{A}) = n$	deciding without computing an inverse
solvability	$\mathbf{A}\mathbf{x} = \mathbf{b}$ solvable $\iff \operatorname{rk}(\mathbf{A}) = \operatorname{rk}(\mathbf{A}\mid\mathbf{b})$	classifying a system in two rank calls
null-space dimension	$\dim(\ker(\mathbf{A})) = n - \operatorname{rk}(\mathbf{A})$	the free-variable count
full rank	$\operatorname{rk}(\mathbf{A}) = \min(m,n)$	not the same as invertible
near-dependence	rank cannot see it; use np.linalg.cond	the practical diagnostic on real data

Linear mappings — §2.7

$$\Phi \text{ linear} \iff \forall\mathbf{x},\mathbf{y},\lambda,\psi:\; \Phi(\lambda\mathbf{x} + \psi\mathbf{y}) = \lambda\Phi(\mathbf{x}) + \psi\Phi(\mathbf{y})$$ $$\text{consequence:}\quad \Phi(\mathbf{0}) = \mathbf{0} \quad\text{— the cheapest disqualifier}$$

result	statement	when you use it
isomorphism	linear and bijective	“the same space in disguise”
endomorphism	$\Phi : V \to V$ linear	Chapter 4’s subject
automorphism	$\Phi : V \to V$ linear and bijective	invertible endomorphism
isomorphism theorem	finite-dimensional $V, W$ isomorphic $\iff \dim V = \dim W$	why $\mathbb{R}^{m\times n} \cong \mathbb{R}^{mn}$
coordinates	$\mathbf{x} = \sum_i \alpha_i\mathbf{b}_i$ with $B$ an ordered basis	ordering matters — coordinates are a list
transformation matrix	column $j$ of $\mathbf{A}_\Phi$ = coordinates of $\Phi(\mathbf{b}_j)$ in $C$	constructing the matrix of a map
coordinate mapping	$\hat{\mathbf{y}} = \mathbf{A}_\Phi\hat{\mathbf{x}}$	matrices map coordinates, not vectors
basis change	$\tilde{\mathbf{A}}_\Phi = \mathbf{T}^{-1}\mathbf{A}_\Phi\mathbf{S}$	read right to left: translate in, map, translate out
equivalence	$\tilde{\mathbf{A}} = \mathbf{T}^{-1}\mathbf{A}\mathbf{S}$	general basis change
similarity	$\tilde{\mathbf{A}} = \mathbf{S}^{-1}\mathbf{A}\mathbf{S}$	endomorphisms; similar implies equivalent, not conversely
composition	$\mathbf{A}_{\Psi\circ\Phi} = \mathbf{A}_\Psi\mathbf{A}_\Phi$	why multiplication is composition
kernel	$\ker(\Phi) = \{\mathbf{v} : \Phi(\mathbf{v}) = \mathbf{0}\} \subseteq \mathbb{R}^n$ (the width)	what gets destroyed
image	$\operatorname{Im}(\Phi) = \Phi(V) \subseteq \mathbb{R}^m$ (the height)	the column space; what can be reached
injectivity	$\Phi$ injective $\iff \ker(\Phi) = \{\mathbf{0}\}$	the all-pairs test collapses to one system
rank-nullity	$\dim(\ker\Phi) + \dim(\operatorname{Im}\Phi) = \dim(V)$	a conservation law; the fundamental theorem of linear mappings
three-way equivalence	if $\dim V = \dim W$: injective $\iff$ surjective $\iff$ bijective	square matrices only — check one, get three
similar invariants	similar matrices share determinant, trace and eigenvalues	the fastest check on any basis change

Affine spaces — §2.8

result	statement	when you use it
affine subspace	$L = \mathbf{x}_0 + U$ with $U$ a subspace	a subspace slid off the origin
not a subspace	excludes $\mathbf{0}$ whenever $\mathbf{x}_0 \notin U$; not closed under either operation	it fails all three subspace tests
parametric equation	$\mathbf{x} = \mathbf{x}_0 + \lambda_1\mathbf{b}_1 + \cdots + \lambda_k\mathbf{b}_k$	describing a line, plane or hyperplane
containment	$L \subseteq \tilde{L} \iff U \subseteq \tilde{U}$ and $\mathbf{x}_0 - \tilde{\mathbf{x}}_0 \in \tilde{U}$	comparing two descriptions of possibly-equal sets
line	$k = 1$	one support point, one direction
plane	$k = 2$	two independent directions
hyperplane	$k = n-1$	codimension one, so it has two sides — the decision boundary
inhomogeneous solutions	empty, or an affine subspace of dimension $n - \operatorname{rk}(\mathbf{A})$	§2.3’s general solution, renamed
single equation	$\sum_i \lambda_ix_i = b$ with some $\lambda_i \neq 0$ defines a hyperplane	one equation removes one dimension
converse	every $k$-dimensional affine subspace of $\mathbb{R}^n$ solves some system with $\operatorname{rk} = n-k$	affine subspaces and inhomogeneous systems coincide
affine mapping	$\phi(\mathbf{x}) = \mathbf{a} + \Phi(\mathbf{x})$, $\mathbf{a}$ the translation vector	what a “linear layer” actually computes
decomposition	every affine map is uniquely a linear map followed by a translation	separating the two parts
preserved	dimension and parallelism	why affine maps keep flat things flat
augmentation trick	append $1$ to $\mathbf{x}$, absorb $\mathbf{a}$ into an extra column	why design matrices have a column of ones

The one-page summary

If you keep only six facts from Chapter 2:

$$\begin{aligned} &\textbf{1.}\;\; \mathbf{A}\mathbf{x} = \mathbf{b} \text{ asks whether } \mathbf{b} \text{ is a combination of } \mathbf{A}\text{'s columns.}\\[3pt] &\textbf{2.}\;\; \text{The columns of } \mathbf{A} \text{ are } \mathbf{A}\mathbf{e}_j \text{ — where the basis vectors go.}\\[3pt] &\textbf{3.}\;\; \text{Every solution set is } \mathbf{x}_p + \ker(\mathbf{A}).\\[3pt] &\textbf{4.}\;\; \operatorname{rk}(\mathbf{A}) \text{ decides invertibility, solvability, and both dimensions.}\\[3pt] &\textbf{5.}\;\; \dim(\ker\Phi) + \dim(\operatorname{Im}\Phi) = \dim(V).\\[3pt] &\textbf{6.}\;\; \text{Affine} = \text{linear} + \text{a translation, and that translation is the bias term.} \end{aligned}$$

Numerical cheat sheet

you want	use	not
solve a square system	np.linalg.solve(A, b)	inv(A) @ b
least squares, any shape	np.linalg.lstsq(A, b, rcond=None)	the normal equations — they square $\kappa$
the pseudo-inverse itself	np.linalg.pinv(A)	forming $(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top$
rank	np.linalg.matrix_rank(A)	counting nonzero singular values by eye
how close to singular	np.linalg.cond(A)	the rank — it cannot see near-dependence
matrix product	A @ B	A * B, which is the Hadamard product
a genuine column vector	x.reshape(-1, 1)	x.T on a 1-D array, which does nothing
compare two results	np.allclose(a, b)	a == b

Recall card

• A group needs four properties and Abelian needs a fifth: closure, associativity, a neutral element, an inverse for every element, then commutativity. Check them in that order — closure usually fails first and costs the least to test.
• Matrix multiplication is associative and distributive but not commutative, and the shapes are the reason: AB and BA need not even have the same size, as exercise 2.4 parts (d) and (e) show at 2 by 2 against 4 by 4.
• Inverses and transposes both REVERSE the order of a product, and for the same reason: undoing two operations means undoing the last one first.
• Elementary row operations never change the solution set. That single fact is what licenses Gaussian elimination, and it is why you may reduce as aggressively as you like.
• Three outcomes, decided by two rank comparisons. Compare the rank of A with the rank of the augmented matrix for consistency, then compare the rank of A with the number of columns for uniqueness.
• The number of free variables is columns minus rank, and a column of zeros is a free variable too — exercise 2.6 has two of them, and missing them turns a three-dimensional solution set into a single point.
• The general solution is one particular solution plus the whole kernel, so the solution set has dimension equal to the number of columns minus the rank whenever the system is consistent.
• A subspace must contain the zero vector and be closed under addition and scaling. Testing for the zero vector first disposes of most candidates immediately.
• Vectors are independent exactly when the only combination giving zero is the trivial one, which is the same as saying the matrix of them has rank equal to its column count.
• More than n vectors in an n-dimensional space are always dependent — a counting argument that settles several exercises with no arithmetic at all.
• A basis is a maximal independent set, and every basis of a space has the same size. That is what makes dimension well defined rather than a property of the basis you happened to pick.
• Rank is the dimension of the column space and of the row space at once, so row rank and column rank are always equal.
• The dimension of a sum is the sum of the dimensions minus the dimension of the intersection. Rearranged, it tells you the size of an intersection before you compute a single basis vector for it: exercise 2.12 gives 3 plus 3 minus 4, so 2.
• A linear map is determined by where it sends a basis, so its matrix’s columns are the images of the basis vectors written in the target basis.
• A basis-change matrix’s columns are the new basis vectors expressed in the old basis. When you doubt the direction, check that the old basis matrix times P gives the new one.
• Similar matrices share trace, determinant, rank and eigenvalues but not their entries. If the trace moved, your basis-change arithmetic is wrong, and you learned that without redoing it.
• Injective, surjective and bijective each have a rank characterisation: full column rank, full row rank, and both at once — which for a square matrix collapses to invertibility.

Next: Analytic Geometry — adds length, angle and distance to everything above.