Every idea here has two faces: an algebraic one you compute with, and a geometric one you can see. A matrix is a table of numbers and a way of moving space; a determinant is an alternating sum and a signed area; an eigenvector is a solution of \((A-\lambda I)v=0\) and a direction the transformation refuses to turn. This course keeps both in view at all times.
21 modules21 interactive labs189 practice problems3 checkpoint quizzesStaged hints · fully worked solutions
\(A\mathbf{x}=\mathbf{b}\)
Solve · elimination, rank, existence & uniqueness
\(A = QR\), \(A=LU\)
Factor · orthogonality, least squares, stability
\(A\mathbf{v}=\lambda\mathbf{v}\)
Diagonalize · eigenvalues, powers, dynamics
Part I · Geometry first
Vectors & span
Part II · The machinery
Matrices & systems
Part III · Structure
Subspaces & orthogonality
Part IV · The payoff
Eigenvalues & SVD
↦How to use this
Drag the vectors before you read the algebra. Every module has an orange Interactive panel — watch a matrix bend the grid, a determinant flip sign, Gram–Schmidt straighten a basis, or repeated multiplication drag every vector onto the dominant eigenvector.
Do the problems on paper. Hints come one at a time, and every solution is worked step by step with the reasoning behind each move.
Tick "Mark complete" at the bottom of each module. Progress is saved in this browser.
Always ask what a result means geometrically. "Determinant zero" and "the transformation squashes space flat" are the same sentence; so are "rank 2" and "the image is a plane." Fluency is being able to switch instantly.
Where this leads
Linear algebra is the language of nearly everything downstream: systems of differential equations are solved by finding eigenvalues (see the ODE Launchpad), separation of variables is an eigenfunction expansion in an infinite-dimensional vector space (the PDE Launchpad), and least squares underlies every regression and machine-learning fit you will ever run.
Part I · Module 1 Vectors & span
Vectors, combinations & span
Two operations — adding vectors and scaling them — generate the entire subject. Everything that follows is a question about what you can reach using only those two moves.
The span of a set of vectors is the collection of all such combinations — everywhere you can get to. In \(\mathbb{R}^2\):
Vectors
Span
Why
\(\{\mathbf{0}\}\)
the origin
every multiple of zero is zero
one nonzero \(\mathbf{v}\)
a line through the origin
the multiples \(c\mathbf{v}\) trace a line
two non-parallel vectors
the whole plane
they reach everywhere
two parallel vectors
still just a line
the second adds nothing new
InteractiveWhere can you get to?drag the vectors; slide the coefficients
v₁ —v₂ —c₁v₁ + c₂v₂ —span is —
Drag either arrowhead. The faint lattice shows the combinations with integer coefficients — a slanted grid covering the plane. Now drag \(\mathbf{v}_2\) until it lies along \(\mathbf{v}_1\): the lattice collapses onto a single line, and the readout changes to "a line". That collapse is exactly what linear dependence means, and you have just seen why it costs you a dimension.
Worked example · is b reachable?
Is \(\mathbf{b}=\begin{bmatrix}7\\4\end{bmatrix}\) in the span of \(\mathbf{v}_1=\begin{bmatrix}1\\2\end{bmatrix}\) and \(\mathbf{v}_2=\begin{bmatrix}3\\-1\end{bmatrix}\)?
STEP 1
"In the span" means: do there exist \(c_1,c_2\) with \(c_1\mathbf{v}_1+c_2\mathbf{v}_2=\mathbf{b}\)?
STEP 2
Write it out coordinate by coordinate — a linear system:
\[ c_1 + 3c_2 = 7, \qquad 2c_1 - c_2 = 4 \]
STEP 3
From the first, \(c_1 = 7-3c_2\). Substituting: \(2(7-3c_2)-c_2 = 4\), so \(14-7c_2 = 4\) and \(c_2 = \frac{10}{7}\).
STEP 4
Then \(c_1 = 7 - \frac{30}{7} = \frac{19}{7}\).
STEP 5
Check: \(\frac{19}{7}\begin{bmatrix}1\\2\end{bmatrix} + \frac{10}{7}\begin{bmatrix}3\\-1\end{bmatrix} = \begin{bmatrix}\frac{19+30}{7}\\\frac{38-10}{7}\end{bmatrix} = \begin{bmatrix}7\\4\end{bmatrix}\) ✓ Yes — and since \(\mathbf v_1,\mathbf v_2\) aren't parallel, every \(\mathbf b\) in \(\mathbb R^2\) is reachable.
"Span" and "solve" are the same question
Asking whether \(\mathbf b\in\operatorname{span}\{\mathbf v_1,\dots,\mathbf v_k\}\) is asking whether \(A\mathbf c=\mathbf b\) has a solution, where the \(\mathbf v_i\) are the columns of \(A\). Geometry on the left, elimination on the right — module M3 does the computing, module S1 names the space.
②Practice
1
Compute \(3\begin{bmatrix}2\\-1\end{bmatrix} - 2\begin{bmatrix}1\\4\end{bmatrix}\), and sketch what the operation does.
Hint 1Scale each vector first, then subtract componentwise.
Solution
STEP 1 · scale the first vector
\[ 3\begin{bmatrix}2\\-1\end{bmatrix} = \begin{bmatrix}6\\-3\end{bmatrix} \]
STEP 2 · scale the second
\[ 2\begin{bmatrix}1\\4\end{bmatrix} = \begin{bmatrix}2\\8\end{bmatrix} \]
Stretch the first vector to three times its length, stretch the second to twice and reverse it, then lay them tip-to-tail. The result is the arrow from the origin to \((4,-11)\).
STEP 5 · why this is the whole subject
Scaling and adding are the only two operations available. Every later idea — span, independence, matrix multiplication, eigenvectors — is a question about what these two moves can and cannot produce.
2
Is \(\begin{bmatrix}5\\1\end{bmatrix}\) in the span of \(\begin{bmatrix}1\\1\end{bmatrix}\) and \(\begin{bmatrix}2\\2\end{bmatrix}\)?
Hint 1Look at the two spanning vectors first — are they independent?
Hint 2\(\begin{bmatrix}2\\2\end{bmatrix} = 2\begin{bmatrix}1\\1\end{bmatrix}\), so the span is just one line.
Solution
STEP 1 · check the spanning set
The second vector is exactly twice the first, so it contributes nothing new:
It is the line \(y=x\) through the origin — all vectors with equal components.
STEP 3 · test the target
\(\begin{bmatrix}5\\1\end{bmatrix}\) has unequal components, so it is off the line.
STEP 4 · confirm algebraically
\(c_1+2c_2 = 5\) and \(c_1+2c_2=1\) — the same left side equal to two different numbers. Inconsistent, so no solution.
STEP 5 · conclusion
No. Two vectors in \(\mathbb R^2\) span the whole plane only when they are independent; parallel vectors leave you stuck on a line, and most targets are unreachable.
3
Describe the span of \(\begin{bmatrix}1\\0\\0\end{bmatrix}\) and \(\begin{bmatrix}0\\1\\0\end{bmatrix}\) in \(\mathbb{R}^3\), and give one vector not in it.
Hint 1Write a general combination and see which coordinates it can control.
Hint 2What is the third coordinate of every combination?
Solution
STEP 1 · write a general combination
\[ c_1\begin{bmatrix}1\\0\\0\end{bmatrix} + c_2\begin{bmatrix}0\\1\\0\end{bmatrix} = \begin{bmatrix}c_1\\c_2\\0\end{bmatrix} \]
STEP 2 · identify the reachable set
The first two coordinates are free, but the third is always zero. The span is the \(xy\)-plane:
\[ \left\{(x,y,0) : x,y\in\mathbb R\right\} \]
STEP 3 · give an unreachable vector
Anything with a nonzero third coordinate, e.g. \(\begin{bmatrix}0\\0\\1\end{bmatrix}\).
STEP 4 · verify
Solving \(\begin{bmatrix}c_1\\c_2\\0\end{bmatrix}=\begin{bmatrix}0\\0\\1\end{bmatrix}\) requires \(0=1\) in the last row — impossible ✓
STEP 5 · the dimension count
Two independent vectors span a two-dimensional subspace. Living inside \(\mathbb R^3\), that is a plane through the origin — and you would need a third independent vector to reach everything.
4
Find \(c_1,c_2\) so that \(c_1\begin{bmatrix}2\\1\end{bmatrix}+c_2\begin{bmatrix}-1\\3\end{bmatrix}=\begin{bmatrix}3\\11\end{bmatrix}\).
Hint 1Write the two coordinate equations.
Hint 2\(2c_1 - c_2 = 3\) and \(c_1 + 3c_2 = 11\).
Solution
STEP 1 · convert to a system
\[ 2c_1 - c_2 = 3, \qquad c_1 + 3c_2 = 11 \]
The coefficients are forced — there is exactly one way to write \(\mathbf b\) in terms of these two vectors, because they are independent. That uniqueness is what makes them a basis (module V4), and the numbers \(\frac{20}7,\frac{19}7\) are \(\mathbf b\)'s coordinates in it (module S2).
5
Three vectors in \(\mathbb{R}^2\) are given. Must they be linearly dependent? Must their span be all of \(\mathbb R^2\)?
Hint 1Think about how many independent directions \(\mathbb R^2\) can hold.
Hint 2For the second question, try a set of three vectors that all lie on one line.
Solution
STEP 1 · the dependence question
Yes, necessarily. Any set of more than \(n\) vectors in \(\mathbb R^n\) is dependent — here 3 vectors in \(\mathbb R^2\).
STEP 2 · why
Stack them as columns of a \(2\times3\) matrix. The system \(A\mathbf c=\mathbf 0\) has 3 unknowns but only 2 equations, so at least one variable is free, giving a nonzero solution — the definition of dependence.
STEP 3 · the span question
No. Take \(\begin{bmatrix}1\\1\end{bmatrix}, \begin{bmatrix}2\\2\end{bmatrix}, \begin{bmatrix}3\\3\end{bmatrix}\): all three lie on \(y=x\), so their span is only that line.
STEP 4 · what actually decides the span
Not the number of vectors but the number of independent ones — which is the rank (module M4). Three vectors of rank 1 span a line; rank 2 spans the plane.
STEP 5 · the two failure modes
Too few vectors ⟹ cannot span. Too many ⟹ must be dependent. Exactly \(n\) independent vectors in \(\mathbb R^n\) is the Goldilocks case: a basis.
6
Show that \(\operatorname{span}\{\mathbf u,\mathbf v\} = \operatorname{span}\{\mathbf u, \mathbf u+\mathbf v\}\).
Hint 1Show each span is contained in the other.
Hint 2Anything built from \(\mathbf u\) and \(\mathbf u+\mathbf v\) can be rewritten using \(\mathbf u\) and \(\mathbf v\), and conversely \(\mathbf v = (\mathbf u+\mathbf v)-\mathbf u\).
Solution
STEP 1 · one inclusion
Any element of the right-hand span is
\[ a\mathbf u + b(\mathbf u+\mathbf v) = (a+b)\mathbf u + b\mathbf v \]
a combination of \(\mathbf u,\mathbf v\) ✓ So \(\operatorname{span}\{\mathbf u,\mathbf u+\mathbf v\} \subseteq \operatorname{span}\{\mathbf u,\mathbf v\}\).
STEP 2 · the other inclusion
Conversely, \(\mathbf v = (\mathbf u+\mathbf v) - \mathbf u\), so
\[ c\mathbf u + d\mathbf v = (c-d)\mathbf u + d(\mathbf u+\mathbf v) \]
Mutual containment means the two spans are equal ✓
STEP 4 · why this matters enormously
Replacing \(\mathbf v\) by \(\mathbf u+\mathbf v\) is exactly a row operation. This proposition is the theoretical guarantee that Gaussian elimination does not change the span — you may reshuffle a spanning set freely and still describe the same space.
STEP 5 · the general statement
Adding any multiple of one vector to another, scaling a vector by a nonzero constant, or reordering the list all leave the span untouched. Those three moves are the elementary row operations of module M3.
7
A drone's displacement is \(4\mathbf i + 3\mathbf j - 12\mathbf k\) metres. Find its distance from the origin and the unit vector in its direction.
Hint 1Length is \(\sqrt{x^2+y^2+z^2}\).
Hint 2A unit vector is the vector divided by its own length.
The large negative \(z\)-component means the drone descended: it is 12 m lower and 5 m away horizontally (since \(\sqrt{4^2+3^2}=5\)).
STEP 5 · why unit vectors matter
Splitting a vector into length × direction (\(\mathbf d = 13\hat{\mathbf d}\)) separates "how much" from "which way." Projections, angles, and orthonormal bases all rely on having pure directions to work with.
8
For which value of \(k\) do \(\begin{bmatrix}2\\3\end{bmatrix}\) and \(\begin{bmatrix}6\\k\end{bmatrix}\) span only a line?
Hint 1They span a line exactly when one is a multiple of the other.
Hint 2The first components give the scale factor: \(6 = 3\times2\).
Solution
STEP 1 · state the condition
The span collapses to a line precisely when the vectors are parallel:
STEP 2 · match the first component
\[ 6 = 2c \quad\Longrightarrow\quad c = 3 \]
STEP 3 · match the second
\[ k = 3(3) = 9 \]
STEP 4 · cross-check with the determinant
\[ \det\begin{bmatrix}2&6\\3&k\end{bmatrix} = 2k - 18 = 0 \quad\Longrightarrow\quad k = 9 \ ✓ \]
STEP 5 · the general rule
Two vectors in \(\mathbb R^2\) fail to span the plane exactly when the determinant of the matrix holding them is zero. Module M6 shows why: a zero determinant means the transformation squashes area to nothing, so the image is at most a line.
9
Explain why \(\operatorname{span}\{\mathbf v_1,\dots,\mathbf v_k\}\) always contains the zero vector, and why that means a span is never a line or plane that misses the origin.
Hint 1What combination do you get by taking all coefficients zero?
Hint 2Compare the set \(\{(x,y): y = x+1\}\) with \(\{(x,y): y=x\}\).
so the zero vector is always in the span, whatever the vectors are.
STEP 2 · the consequence
A span must pass through the origin. The line \(y = x+1\) does not, so it is not the span of anything — it is a shifted line, an affine set.
STEP 3 · how shifted sets do arise
As solution sets of nonhomogeneous systems: \(A\mathbf x=\mathbf b\) with \(\mathbf b\ne\mathbf 0\) gives \(\mathbf x_p + \operatorname{null}(A)\) — a subspace translated away from the origin (module M4).
STEP 4 · the contrast
Through origin?
Closed under scaling?
\(A\mathbf x=\mathbf 0\) solutions
yes
yes — a subspace
\(A\mathbf x=\mathbf b\) solutions
no (unless \(\mathbf b=\mathbf 0\))
no — an affine shift
STEP 5 · the quick test
Given any candidate set, first ask: does it contain \(\mathbf 0\)? If not, it cannot be a subspace and cannot be a span — one line of work that settles many exam questions instantly (module V5).
Part I · Module 2 Vectors & span
Dot product, length & angle
The dot product is the bridge between algebra and geometry: one multiplication-and-add gives you lengths, angles, perpendicularity, and projections — and every one of those reappears later as orthogonality, least squares, and the spectral theorem.
①One definition, two formulas
Algebraic and geometric
\[ \mathbf u\cdot\mathbf v = u_1v_1+u_2v_2+\cdots+u_nv_n \qquad\text{and}\qquad \mathbf u\cdot\mathbf v = \|\mathbf u\|\,\|\mathbf v\|\cos\theta \]
Setting them equal is where everything comes from:
Perpendicular ⟺ \(\mathbf u\cdot\mathbf v = 0\), since \(\cos90^\circ = 0\).
Sign: positive means the vectors lean the same way, negative means they oppose.
Projection of u onto v
\[ \operatorname{proj}_{\mathbf v}\mathbf u = \frac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\,\mathbf v \]
InteractiveAngle, sign, and shadowdrag either vector
u · v —angle —relationship —‖proj‖ —
The projection is the shadow of \(\mathbf u\) on the line through \(\mathbf v\), and the dashed segment joining \(\mathbf u\) to that shadow is always perpendicular to \(\mathbf v\). Drag until the dot product passes through zero and watch the shadow vanish — that instant is orthogonality. Everything in module S5 (least squares) is this picture in higher dimensions.
Worked example · angle and decomposition
For \(\mathbf u=\begin{bmatrix}3\\4\end{bmatrix}\), \(\mathbf v=\begin{bmatrix}5\\0\end{bmatrix}\): find the angle between them and split \(\mathbf u\) into parts parallel and perpendicular to \(\mathbf v\).
Projection: \(\operatorname{proj}_{\mathbf v}\mathbf u = \frac{15}{25}\begin{bmatrix}5\\0\end{bmatrix} = \begin{bmatrix}3\\0\end{bmatrix}\).
STEP 4
Perpendicular part: \(\mathbf u - \operatorname{proj}_{\mathbf v}\mathbf u = \begin{bmatrix}0\\4\end{bmatrix}\).
STEP 5
Check: \(\begin{bmatrix}0\\4\end{bmatrix}\cdot\begin{bmatrix}5\\0\end{bmatrix} = 0\) ✓ perpendicular, and \(\begin{bmatrix}3\\0\end{bmatrix}+\begin{bmatrix}0\\4\end{bmatrix} = \mathbf u\) ✓ Every vector splits uniquely this way — the foundation of Gram–Schmidt and least squares.
②Practice
1
Compute \(\begin{bmatrix}2\\-1\\3\end{bmatrix}\cdot\begin{bmatrix}4\\5\\-1\end{bmatrix}\) and say what the sign tells you.
A dot product of exactly zero means the vectors are orthogonal — perpendicular in \(\mathbb R^3\), at \(90^\circ\).
STEP 4 · confirm with the angle formula
\[ \cos\theta = \frac{0}{\|\mathbf u\|\|\mathbf v\|} = 0 \quad\Longrightarrow\quad \theta = 90^\circ \ ✓ \]
STEP 5 · the sign dictionary
Positive ⟹ angle under \(90^\circ\) (same general direction); zero ⟹ perpendicular; negative ⟹ obtuse, pointing against each other. One arithmetic result, three geometric readings.
2
Find the angle between \(\begin{bmatrix}1\\1\end{bmatrix}\) and \(\begin{bmatrix}1\\-1\end{bmatrix}\), and between \(\begin{bmatrix}1\\1\end{bmatrix}\) and \(\begin{bmatrix}2\\0\end{bmatrix}\).
Hint 1Use \(\cos\theta = \frac{\mathbf u\cdot\mathbf v}{\|\mathbf u\|\|\mathbf v\|}\).
Hint 2\(\|(1,1)\| = \sqrt2\).
Solution
STEP 1 · first pair
\[ \mathbf u\cdot\mathbf v = 1-1 = 0 \quad\Longrightarrow\quad \theta = 90^\circ \]
\((1,1)\) points along the diagonal, \((2,0)\) along the \(x\)-axis — \(45^\circ\) apart ✓ And \((1,-1)\) is the anti-diagonal, a full \(90^\circ\) from the diagonal ✓ Note the angle ignores lengths entirely: \((2,0)\) and \((100,0)\) give the same answer.
3
Project \(\mathbf u=\begin{bmatrix}4\\3\end{bmatrix}\) onto \(\mathbf v=\begin{bmatrix}1\\1\end{bmatrix}\), and verify the leftover is perpendicular to \(\mathbf v\).
Hint 1\(\operatorname{proj}_{\mathbf v}\mathbf u = \frac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\mathbf v\).
Hint 2\(\mathbf u\cdot\mathbf v = 7\) and \(\mathbf v\cdot\mathbf v = 2\).
Solution
STEP 1 · the two dot products
\[ \mathbf u\cdot\mathbf v = 4+3 = 7, \qquad \mathbf v\cdot\mathbf v = 1+1 = 2 \]
STEP 2 · the projection
\[ \operatorname{proj}_{\mathbf v}\mathbf u = \frac72\begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}3.5\\3.5\end{bmatrix} \]
STEP 3 · the leftover
\[ \mathbf u - \operatorname{proj}_{\mathbf v}\mathbf u = \begin{bmatrix}0.5\\-0.5\end{bmatrix} \]
The coefficient \(\frac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\) is chosen precisely so that \((\mathbf u - c\mathbf v)\cdot\mathbf v = 0\). Solving that equation for \(c\) derives the projection formula — and doing the same in \(\mathbb R^n\) with a matrix gives the normal equations of least squares (module S5).
4
Find all \(k\) making \(\begin{bmatrix}k\\2\\1\end{bmatrix}\) orthogonal to \(\begin{bmatrix}3\\-1\\4\end{bmatrix}\).
The condition is a single linear equation in \(k\), so exactly one value works.
STEP 5 · the wider view
If instead all three components were unknown, \(\mathbf x\cdot\mathbf a = 0\) would describe a whole plane through the origin — the orthogonal complement of \(\mathbf a\), and a two-dimensional null space (module S1).
5
Prove the Pythagorean theorem in vector form: if \(\mathbf u\cdot\mathbf v=0\) then \(\|\mathbf u+\mathbf v\|^2 = \|\mathbf u\|^2+\|\mathbf v\|^2\).
Hint 1Start from \(\|\mathbf u+\mathbf v\|^2 = (\mathbf u+\mathbf v)\cdot(\mathbf u+\mathbf v)\).
Hint 2Expand using bilinearity, then use the orthogonality assumption.
Solution
STEP 1 · expand the square
\[ \|\mathbf u+\mathbf v\|^2 = (\mathbf u+\mathbf v)\cdot(\mathbf u+\mathbf v) = \mathbf u\cdot\mathbf u + 2\,\mathbf u\cdot\mathbf v + \mathbf v\cdot\mathbf v \]
(using symmetry, \(\mathbf u\cdot\mathbf v = \mathbf v\cdot\mathbf u\)).
STEP 2 · apply the hypothesis
Orthogonality kills the middle term:
\[ = \|\mathbf u\|^2 + \|\mathbf v\|^2 \ ✓ \]
STEP 3 · note the converse
The computation is reversible: if \(\|\mathbf u+\mathbf v\|^2 = \|\mathbf u\|^2+\|\mathbf v\|^2\) then \(2\mathbf u\cdot\mathbf v = 0\), so the vectors must be orthogonal.
Pythagoras in this form works in \(\mathbb R^n\) and in function spaces alike. It is why orthogonal decompositions are numerically well behaved, and why Parseval's identity (energy = sum of squared coefficients) holds for Fourier series.
6
A force \(\mathbf F = \begin{bmatrix}6\\8\end{bmatrix}\) N moves an object along the displacement \(\mathbf d = \begin{bmatrix}3\\0\end{bmatrix}\) m. Find the work done, and the component of force that does nothing.
Hint 1Work is \(\mathbf F\cdot\mathbf d\).
Hint 2Only the component of \(\mathbf F\) along \(\mathbf d\) contributes.
Solution
STEP 1 · compute the work
\[ W = \mathbf F\cdot\mathbf d = (6)(3) + (8)(0) = 18 \ \text{J} \]
STEP 2 · split the force
Along \(\mathbf d\) (the \(x\)-direction): \(\begin{bmatrix}6\\0\end{bmatrix}\). Perpendicular: \(\begin{bmatrix}0\\8\end{bmatrix}\).
STEP 3 · identify the useless component
The \(8\) N vertical component is perpendicular to the motion, so it contributes \(0\) to the work — it presses the object into the surface but does not move it.
Work, power, and flux are all "how much of this vector points along that one." The projection formula quantifies exactly that, which is why \(W = \|\mathbf F\|\|\mathbf d\|\cos\theta\) is the same statement in the geometric form.
7
Show that \(\|\mathbf u+\mathbf v\| \le \|\mathbf u\|+\|\mathbf v\|\) (the triangle inequality), assuming the Cauchy–Schwarz inequality \(|\mathbf u\cdot\mathbf v|\le\|\mathbf u\|\|\mathbf v\|\).
Hint 1Expand \(\|\mathbf u+\mathbf v\|^2\) as in problem 5.
Hint 2Bound the cross term with Cauchy–Schwarz and recognize a perfect square.
Only when \(\mathbf u\cdot\mathbf v = \|\mathbf u\|\|\mathbf v\|\), i.e. \(\cos\theta=1\) — the vectors point the same way. Geometrically: the direct route is shortest unless the detour happens to be straight, which is exactly what "triangle inequality" says.
8
Two documents are represented by word-count vectors \(\mathbf a = (3,0,4)\) and \(\mathbf b=(6,0,8)\). Compute their cosine similarity and explain why it, rather than distance, is used to compare texts.
Hint 1Cosine similarity is just \(\cos\theta\) between the vectors.
Perfect similarity: the second document uses the same words in the same proportions, just twice as many of them — a longer article on the same topic.
STEP 5 · why not distance
The Euclidean distance is \(\|\mathbf b-\mathbf a\| = 5\), which would wrongly call them dissimilar simply because one is longer. Cosine similarity normalizes away length and compares direction only — which is why it is the standard measure in search engines and embedding models.
9
Find a unit vector orthogonal to both \(\begin{bmatrix}1\\1\\0\end{bmatrix}\) and \(\begin{bmatrix}0\\1\\1\end{bmatrix}\) using only dot products.
Hint 1Write \(\mathbf x=(x,y,z)\) and impose two dot-product equations.
Hint 2\(x+y=0\) and \(y+z=0\) — solve in terms of one free variable.
Hint 3Normalize at the end.
Solution
STEP 1 · impose both conditions
\[ x + y = 0, \qquad y + z = 0 \]
STEP 2 · solve with a free parameter
Let \(y = t\). Then \(x = -t\) and \(z = -t\):
\[ \mathbf x = t\begin{bmatrix}-1\\1\\-1\end{bmatrix} \]
A homogeneous system \(A\mathbf x=\mathbf 0\) whose solution set is a line — the null space of the \(2\times3\) matrix with those rows (module S1). The cross product of module V3 produces the same direction in one step, but only in \(\mathbb R^3\); this method generalizes to any dimension.
Part I · Module 3 Vectors & span
Cross product, lines & planes
The cross product is the one operation special to \(\mathbb{R}^3\): it manufactures a vector perpendicular to two others, with length equal to the area they span. That single object gives you normals, planes, areas, and torque.
InteractiveNormal, area, and the right-hand rulerotate the view; drag the vectors
u × v —‖u × v‖ = area —perpendicular? —
The shaded parallelogram is what \(\mathbf u\) and \(\mathbf v\) span; the arrow standing off it is their cross product, drawn to scale so its length is that area. Tick "v × u" and it flips to point the other way — the anticommutativity is not a sign convention you memorize, it is the right-hand rule reversing. Slide the vectors toward parallel and watch the parallelogram, and the normal, shrink to nothing.
Worked example · a plane through three points
Find the plane through \(P(1,0,2)\), \(Q(2,1,0)\), \(R(0,3,1)\).
Their cross product is normal to both, hence to the plane:
\[ \mathbf n = \vec{PQ}\times\vec{PR} = \begin{bmatrix}(1)(-1)-(-2)(3)\\(-2)(-1)-(1)(-1)\\(1)(3)-(1)(-1)\end{bmatrix} = \begin{bmatrix}5\\3\\4\end{bmatrix} \]
STEP 3
Use the point-normal form with \(P\):
\[ 5(x-1) + 3(y-0) + 4(z-2) = 0 \]
STEP 4
Simplify: \(5x+3y+4z = 13\).
STEP 5
Check all three points: \(P: 5+0+8=13\) ✓, \(Q: 10+3+0=13\) ✓, \(R: 0+9+4=13\) ✓ Note the coefficients of the plane equation are the normal vector — reading a normal off a plane equation is free.
②Practice
1
Compute \(\begin{bmatrix}1\\2\\3\end{bmatrix}\times\begin{bmatrix}4\\5\\6\end{bmatrix}\) and verify it is perpendicular to both.
Hint 1Use the component formula, or expand the symbolic determinant along the first row.
Hint 2Check with dot products — both should be zero.
No angles, no perpendicular distances, no coordinates chosen cleverly — just two subtractions and a cross product. In 2-D the same idea reduces to \(\frac12|x_1y_2-x_2y_1|\), the determinant formula for triangle area.
3
Find the equation of the plane through \((2,-1,3)\) with normal \(\begin{bmatrix}4\\0\\-2\end{bmatrix}\), and determine whether \((0,5,-1)\) lies on it.
Hint 1Point-normal form: \(\mathbf n\cdot(\mathbf x-\mathbf x_0)=0\).
\(y\) does not appear, because the normal has no \(y\)-component. The plane therefore contains every direction with only a \(y\)-change — it runs parallel to the \(y\)-axis.
STEP 5 · the takeaway
A plane equation \(ax+by+cz=d\) always has \((a,b,c)\) as its normal, and \(d\) merely slides the plane along that normal. \(d=0\) makes it pass through the origin — the only case where a plane is a subspace (module V5).
4
Compute \(\mathbf u\times\mathbf u\) for any \(\mathbf u\), and explain the result geometrically.
Hint 1Use the component formula with \(\mathbf v=\mathbf u\).
Hint 2What parallelogram do \(\mathbf u\) and \(\mathbf u\) span?
Solution
STEP 1 · substitute into the formula
\[ \mathbf u\times\mathbf u = \begin{bmatrix}u_2u_3-u_3u_2\\u_3u_1-u_1u_3\\u_1u_2-u_2u_1\end{bmatrix} = \begin{bmatrix}0\\0\\0\end{bmatrix} \]
STEP 2 · geometric reason
The "parallelogram" spanned by a vector and itself is a degenerate sliver of zero area, and \(\|\mathbf u\times\mathbf u\| = \|\mathbf u\|^2\sin0 = 0\).
STEP 3 · the algebraic reason
Anticommutativity forces it: \(\mathbf u\times\mathbf u = -(\mathbf u\times\mathbf u)\), and the only vector equal to its own negative is \(\mathbf 0\).
STEP 4 · the general statement
\(\mathbf u\times\mathbf v=\mathbf 0\) exactly when \(\mathbf u\) and \(\mathbf v\) are parallel (including when either is zero) — the cross product is a dependence detector in \(\mathbb R^3\).
STEP 5 · contrast with the dot product
\(\mathbf u\cdot\mathbf u = \|\mathbf u\|^2\) is as large as possible, while \(\mathbf u\times\mathbf u = \mathbf 0\) is as small as possible. The dot product measures alignment; the cross product measures the failure of alignment.
5
Find the volume of the parallelepiped spanned by \(\begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}1\\2\\0\end{bmatrix}, \begin{bmatrix}1\\1\\3\end{bmatrix}\).
Hint 1Volume is the absolute value of the scalar triple product \(\mathbf a\cdot(\mathbf b\times\mathbf c)\).
Hint 2Equivalently, the absolute determinant of the matrix with those columns.
Solution
STEP 1 · set up the determinant
\[ V = \left|\det\begin{bmatrix}1&1&1\\0&2&1\\0&0&3\end{bmatrix}\right| \]
STEP 2 · exploit the triangular shape
The matrix is upper triangular, so the determinant is the product of the diagonal:
\[ \det = (1)(2)(3) = 6 \]
STEP 3 · state the volume
\[ V = 6 \]
STEP 4 · cross-check with the triple product
\(\mathbf b\times\mathbf c = (2)(3)-(0)(1),\ (0)(1)-(1)(3),\ (1)(1)-(2)(1) = (6,-3,-1)\), and \(\mathbf a\cdot(6,-3,-1) = 6\) ✓
STEP 5 · what zero volume would mean
If the determinant were 0, the three vectors would lie in a common plane — linearly dependent, spanning only 2 dimensions. Volume is therefore an independence test in \(\mathbb R^3\), which is exactly the role determinants play in general (module M6).
6
Find the distance from the point \(P(1,2,3)\) to the plane \(2x - y + 2z = 6\).
Hint 1Distance \(= \frac{|\mathbf n\cdot\mathbf p - d|}{\|\mathbf n\|}\), where \(\mathbf n\) is the normal from the coefficients.
Hint 2\(\mathbf n = (2,-1,2)\) with \(\|\mathbf n\|=3\).
Solution
STEP 1 · read the normal
\[ \mathbf n = \begin{bmatrix}2\\-1\\2\end{bmatrix}, \qquad \|\mathbf n\| = \sqrt{4+1+4} = 3 \]
STEP 2 · evaluate the plane expression at P
\[ 2(1) - 2 + 2(3) = 6 \]
Take any point \(\mathbf q\) on the plane; the distance is the length of the projection of \(\mathbf p - \mathbf q\) onto the unit normal — module V2's projection idea again. Had \(P\) been \((1,2,4)\), you would get \(\frac{|8-6|}{3} = \frac23\).
7
A force \(\mathbf F = (0,0,-50)\) N acts at the end of a wrench \(\mathbf r = (0.3,0,0)\) m from the bolt. Find the torque \(\boldsymbol\tau = \mathbf r\times\mathbf F\).
Hint 1Apply the component formula.
Hint 2The direction tells you the axis of rotation, by the right-hand rule.
\(\mathbf r\) and \(\mathbf F\) are perpendicular, so \(\|\boldsymbol\tau\| = (0.3)(50)\sin90^\circ = 15\) ✓
STEP 4 · direction
The torque points along \(+\mathbf j\), so the bolt turns about the \(y\)-axis in the right-hand sense.
STEP 5 · why leverage is a sine
\(\|\boldsymbol\tau\| = \|\mathbf r\|\|\mathbf F\|\sin\theta\) is maximal at \(90^\circ\) and zero when you push along the wrench — pushing straight at the bolt achieves nothing. Cross products encode that automatically.
8
Do the points \((1,1,1)\), \((2,3,4)\), \((3,5,7)\), \((0,-1,-2)\) all lie on one line? On one plane?
Hint 1Form displacement vectors from the first point and check whether they are parallel.
Hint 2Parallel displacements ⟹ collinear, which certainly means coplanar.
Solution
STEP 1 · build displacements from the first point
\[ \mathbf a = \begin{bmatrix}1\\2\\3\end{bmatrix}, \quad \mathbf b = \begin{bmatrix}2\\4\\6\end{bmatrix}, \quad \mathbf c = \begin{bmatrix}-1\\-2\\-3\end{bmatrix} \]
STEP 2 · test for parallelism
\(\mathbf b = 2\mathbf a\) and \(\mathbf c = -\mathbf a\) — all three are multiples of one vector.
STEP 3 · conclude collinearity
Every point is \((1,1,1) + t(1,2,3)\), so all four lie on a single line.
STEP 4 · and coplanarity
Trivially yes — a line lies in infinitely many planes, so the points are coplanar but do not determine a unique plane.
STEP 5 · the general test
Three points determine a plane only when their two displacement vectors are independent (nonzero cross product). Four points are coplanar iff the scalar triple product of their three displacements vanishes — a determinant test, which here is zero for the stronger reason of collinearity.
9
Why is there no cross product in \(\mathbb{R}^2\) or \(\mathbb{R}^4\) with all the usual properties, and what replaces it?
Hint 1In \(\mathbb R^2\), how many directions are perpendicular to a given vector? In \(\mathbb R^4\), how many are perpendicular to two given vectors?
Hint 2Think about the dimension of the orthogonal complement.
Solution
STEP 1 · what the cross product needs
Given two independent vectors, it must return a unique direction perpendicular to both.
STEP 2 · in ℝ³ this works
Two independent vectors span a plane; its orthogonal complement is exactly one line, so "perpendicular to both" pins down a direction (and the right-hand rule picks the sign).
STEP 3 · in ℝ⁴ it fails
Two vectors span a plane, but its orthogonal complement is a two-dimensional plane — infinitely many perpendicular directions, with no principled way to choose one.
STEP 4 · in ℝ² it also fails
You would need a vector perpendicular to two given ones inside a two-dimensional space — only \(\mathbf 0\) qualifies. What survives is the scalar \(u_1v_2-u_2v_1\), the signed area (a determinant, not a vector).
STEP 5 · what replaces it
The determinant and, more generally, the wedge product of exterior algebra, which produces an oriented area element rather than a vector. In \(\mathbb R^n\) you can also find vectors orthogonal to several given ones by solving \(A\mathbf x=\mathbf 0\) — module V2 problem 9 did exactly that, and it works in every dimension.
Part I · Module 4 Vectors & span
Linear independence & basis
A basis is a set that is big enough to reach everything and small enough to waste nothing. Those two conditions — spanning and independence — are the two halves of the most important definition in the subject.
In words: the only way to build zero is to use nothing. If some nonzero combination gives \(\mathbf 0\), the set is dependent and at least one vector is redundant — it lies in the span of the others.
Basis
\[ \mathcal B = \{\mathbf v_1,\dots,\mathbf v_n\} \ \text{is a basis of } V \iff \mathcal B \ \text{spans } V \ \text{and is independent} \]
Equivalently, and more usefully: every vector in \(V\) is a combination of the \(\mathbf v_i\) in exactly one way. Spanning gives existence; independence gives uniqueness.
InteractiveIndependent, or wasting a vector?drag the third vector
determinant —verdict —span —
With two vectors, the shaded parallelogram is their span's "unit cell" and its signed area is the determinant. Rotate \(\mathbf v_2\) toward \(\mathbf v_1\): the area shrinks, the determinant passes through zero, and the pair becomes dependent at exactly that instant. Switch to three vectors in the plane and the verdict is always dependent — three vectors can never be independent in two dimensions.
Worked example · testing independence
Are \(\mathbf v_1=\begin{bmatrix}1\\2\\1\end{bmatrix}\), \(\mathbf v_2=\begin{bmatrix}2\\1\\0\end{bmatrix}\), \(\mathbf v_3=\begin{bmatrix}4\\5\\2\end{bmatrix}\) independent?
STEP 1
Set up \(c_1\mathbf v_1+c_2\mathbf v_2+c_3\mathbf v_3 = \mathbf 0\) — a homogeneous system with the vectors as columns.
STEP 2
Row-reduce \(\begin{bmatrix}1&2&4\\2&1&5\\1&0&2\end{bmatrix}\). Subtracting twice row 1 from row 2, and row 1 from row 3:
Take \(t=1\): \(-2\mathbf v_1 - \mathbf v_2 + \mathbf v_3 = \mathbf 0\), i.e. \(\mathbf v_3 = 2\mathbf v_1+\mathbf v_2\) — the explicit redundancy. Check: \(2(1,2,1)+(2,1,0) = (4,5,2)\) ✓ So \(\{\mathbf v_1,\mathbf v_2\}\) is a basis for the same span, which is a plane in \(\mathbb R^3\).
②Practice
1
Are \(\begin{bmatrix}1\\3\end{bmatrix}\) and \(\begin{bmatrix}-2\\-6\end{bmatrix}\) independent?
Hint 1Two vectors are dependent exactly when one is a multiple of the other.
Solution
STEP 1 · look for a multiple
\[ \begin{bmatrix}-2\\-6\end{bmatrix} = -2\begin{bmatrix}1\\3\end{bmatrix} \]
STEP 2 · exhibit a nonzero combination giving zero
\[ 2\begin{bmatrix}1\\3\end{bmatrix} + 1\begin{bmatrix}-2\\-6\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix} \]
with coefficients \((2,1)\ne(0,0)\).
STEP 3 · conclude
Dependent.
STEP 4 · confirm with the determinant
\[ \det\begin{bmatrix}1&-2\\3&-6\end{bmatrix} = -6+6 = 0 \ ✓ \]
STEP 5 · the geometry
Both lie on the line \(y=3x\), so their span is that line, not the plane. For two vectors the test is trivial; for three or more, only elimination or a determinant will do — "one is a multiple of another" is not the right test then, as problem 4 shows.
2
Show that \(\left\{\begin{bmatrix}1\\1\end{bmatrix},\begin{bmatrix}1\\-1\end{bmatrix}\right\}\) is a basis of \(\mathbb R^2\), and find the coordinates of \(\begin{bmatrix}5\\1\end{bmatrix}\) in it.
Hint 1Two independent vectors in \(\mathbb R^2\) automatically span it.
\(3(1,1)+2(1,-1) = (5,1)\) ✓ The same vector has coordinates \((5,1)\) in the standard basis and \((3,2)\) in this one — the arrow never moved, only the ruler changed (module S2).
3
Determine whether \(\begin{bmatrix}1\\0\\1\end{bmatrix},\begin{bmatrix}0\\1\\1\end{bmatrix},\begin{bmatrix}1\\1\\0\end{bmatrix}\) form a basis of \(\mathbb R^3\).
Hint 1Three vectors in \(\mathbb R^3\) form a basis exactly when they are independent.
Hint 2Compute the determinant of the matrix with these columns.
Solution
STEP 1 · form the matrix
\[ A = \begin{bmatrix}1&0&1\\0&1&1\\1&1&0\end{bmatrix} \]
STEP 2 · expand along the first row
\[ \det A = 1\begin{vmatrix}1&1\\1&0\end{vmatrix} - 0 + 1\begin{vmatrix}0&1\\1&1\end{vmatrix} = 1(-1) + 1(-1) = -2 \]
STEP 3 · conclude
\(\det A = -2 \ne 0\), so the columns are independent — and three independent vectors in \(\mathbb R^3\) automatically span it.
Yes, a basis.
STEP 4 · the shortcut you just used
In \(\mathbb R^n\), any \(n\) vectors are a basis ⟺ they are independent ⟺ they span ⟺ the determinant is nonzero. With exactly \(n\) vectors, checking one condition suffices.
STEP 5 · the sign
A negative determinant means this basis is left-handed relative to the standard one — it reverses orientation. Magnitude 2 means the unit cube maps to a parallelepiped of volume 2 (module M6).
4
Give three vectors in \(\mathbb R^3\) that are pairwise non-parallel yet still dependent.
Hint 1Dependence for three vectors doesn't require any two to be parallel — it requires them to share a plane.
Hint 2Pick two independent vectors, then take their sum as the third.
with coefficients \((1,1,-1)\ne\mathbf 0\), so the set is dependent.
STEP 4 · the geometry
All three lie in the \(xy\)-plane. Three vectors are dependent precisely when they are coplanar — a condition about the trio, not about any pair.
STEP 5 · the lesson
"No two are parallel" is not a test for independence once you have three or more vectors. Use the determinant (square case) or elimination (any case) instead.
5
For which \(k\) are \(\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}0\\1\\1\end{bmatrix},\begin{bmatrix}2\\5\\k\end{bmatrix}\) dependent?
Hint 1Dependent ⟺ determinant zero.
Hint 2Expand along the first column or reduce first.
Solution
STEP 1 · set the determinant to zero
\[ \det\begin{bmatrix}1&0&2\\2&1&5\\3&1&k\end{bmatrix} = 0 \]
STEP 2 · expand along the first row
\[ 1\begin{vmatrix}1&5\\1&k\end{vmatrix} - 0 + 2\begin{vmatrix}2&1\\3&1\end{vmatrix} = (k-5) + 2(2-3) \]
STEP 3 · simplify
\[ k - 5 - 2 = k - 7 \]
STEP 4 · solve
\[ k = 7 \]
STEP 5 · verify the dependence explicitly
With \(k=7\): \(2(1,2,3)+1(0,1,1) = (2,5,7)\) ✓ — the third vector is exactly \(2\mathbf v_1+\mathbf v_2\). For every other \(k\), the three are independent and form a basis of \(\mathbb R^3\).
6
Prove that any set containing the zero vector is linearly dependent.
Hint 1You need one nonzero coefficient combination that produces \(\mathbf 0\).
Hint 2Put a 1 on the zero vector and 0 on everything else.
Solution
STEP 1 · set up
Let the set be \(\{\mathbf 0, \mathbf v_2,\dots,\mathbf v_k\}\).
The coefficients \((1,0,\dots,0)\) are not all zero, yet the combination is \(\mathbf 0\) — precisely the definition of dependence ✓
STEP 4 · the intuition
The zero vector contributes nothing to any span, so it is always redundant. A basis can never contain it.
STEP 5 · use it as a quick filter
Spot a zero column and you may declare dependence immediately — no elimination needed. Likewise, a repeated vector gives \(\mathbf v - \mathbf v = \mathbf 0\), so duplicates always mean dependence.
7
The vectors \(\mathbf v_1,\mathbf v_2,\mathbf v_3\) are independent. Are \(\mathbf v_1+\mathbf v_2\), \(\mathbf v_2+\mathbf v_3\), \(\mathbf v_1+\mathbf v_3\) independent?
Hint 1Set a general combination to zero and expand in terms of the original vectors.
Hint 2Group the coefficients of \(\mathbf v_1,\mathbf v_2,\mathbf v_3\) and use their independence.
Solution
STEP 1 · set up the test
\[ a(\mathbf v_1+\mathbf v_2) + b(\mathbf v_2+\mathbf v_3) + c(\mathbf v_1+\mathbf v_3) = \mathbf 0 \]
STEP 2 · regroup by original vector
\[ (a+c)\mathbf v_1 + (a+b)\mathbf v_2 + (b+c)\mathbf v_3 = \mathbf 0 \]
STEP 3 · use independence of the originals
Each coefficient must vanish:
\[ a+c = 0, \qquad a+b = 0, \qquad b+c = 0 \]
STEP 4 · solve the system
From the first two, \(c = -a\) and \(b = -a\). Substituting into the third: \(-a-a = -2a = 0\), so \(a=0\), hence \(b=c=0\).
STEP 5 · conclude
Only the trivial solution ⟹ independent ✓ (Worth knowing: the analogous statement fails for four vectors with the four "adjacent sums" — the determinant of the corresponding coefficient matrix is 0 there. Always run the computation rather than trusting the pattern.)
8
Find a basis for the span of \(\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}2\\4\\6\end{bmatrix},\begin{bmatrix}1\\0\\1\end{bmatrix}\), and state its dimension.
Hint 1Discard any vector that is a combination of the others.
so \(\mathbf v_2\) adds nothing to the span and can be dropped.
STEP 2 · check the survivors
Are \(\mathbf v_1 = (1,2,3)\) and \(\mathbf v_3 = (1,0,1)\) independent? Neither is a multiple of the other (the middle components 2 and 0 rule it out), so yes.
STEP 3 · state the basis
\[ \left\{\begin{bmatrix}1\\2\\3\end{bmatrix}, \begin{bmatrix}1\\0\\1\end{bmatrix}\right\} \]
STEP 4 · dimension
Two basis vectors ⟹ \(\dim = 2\). The span is a plane through the origin in \(\mathbb R^3\).
STEP 5 · note the non-uniqueness
\(\{\mathbf v_2,\mathbf v_3\}\) is an equally valid basis, as is \(\{\mathbf v_1+\mathbf v_3, \mathbf v_3\}\). Bases are never unique — but the dimension always is, which is why it is the meaningful quantity.
9
Explain why every basis of a given space has the same number of vectors, and why that number deserves the name "dimension".
Hint 1Suppose one basis had more vectors than another and think about the counting argument used in V1 problem 5.
Hint 2More vectors than a spanning set can supply ⟹ dependence.
Solution
STEP 1 · the key lemma
If a space is spanned by \(m\) vectors, then any set of more than \(m\) vectors in it must be dependent — because expressing them in terms of the \(m\) spanners gives a homogeneous system with more unknowns than equations, which always has a nonzero solution.
STEP 2 · apply it both ways
Let \(\mathcal B_1\) have \(p\) vectors and \(\mathcal B_2\) have \(q\), both bases. \(\mathcal B_1\) spans, and \(\mathcal B_2\) is independent, so \(q \le p\). Swapping roles gives \(p \le q\).
STEP 3 · conclude
\[ p = q \]
Every basis has the same size — the invariance that makes dimension well defined.
STEP 4 · why "dimension" is the right word
It counts the independent directions available: the number of coordinates you need, the number of free parameters in the space, and the number of "degrees of freedom" in any physical model built on it.
STEP 5 · what it buys you
Dimension turns hard questions into counting. Is this set a basis? Count it — if it has the right size, checking independence or spanning suffices. Does \(A\mathbf x=\mathbf b\) have a unique solution? Compare rank with the number of columns (module M4). The rank–nullity theorem (module S1) is the ultimate expression of this bookkeeping.
Part I · Module 5 Vectors & span
Subspaces
A subspace is a subset that is closed under the only two operations we have. That modest-sounding requirement forces a rigid geometry: through the origin, flat, and unbounded — lines, planes, and their higher-dimensional analogues, nothing else.
①The three conditions
S ⊆ ℝⁿ is a subspace when
\[ \text{(i) } \mathbf 0\in S \qquad \text{(ii) } \mathbf u,\mathbf v\in S \Rightarrow \mathbf u+\mathbf v\in S \qquad \text{(iii) } \mathbf u\in S,\ c\in\mathbb R \Rightarrow c\mathbf u\in S \]
Condition (i) is really a consequence of (iii) with \(c=0\), but checking it first is the fastest way to rule things out. Every span is a subspace, and every subspace is a span — the two ideas coincide.
Set
Subspace?
Reason
Line through the origin
yes
closed under both operations
Line not through the origin
no
misses \(\mathbf 0\)
First quadrant
no
\(c=-1\) leaves it
\(\{(x,y):xy=0\}\) (both axes)
no
\((1,0)+(0,1)=(1,1)\) is outside
Solutions of \(A\mathbf x=\mathbf 0\)
yes
the null space — always a subspace
Solutions of \(A\mathbf x=\mathbf b\), \(\mathbf b\ne\mathbf 0\)
no
misses \(\mathbf 0\); an affine shift
InteractiveWhich sets survive the test?pick a set; check closure
contains 0? —closed under + ? —closed under scaling? —verdict —
The shaded region is the candidate set; the two amber arrows are sample members, and the cyan arrow is their sum or scaled version. When the test vector lands outside the shading, closure has failed and you are watching the counterexample happen. The unit disk is the instructive case: it contains \(\mathbf 0\) and is closed under addition of small vectors, but scaling by 2 escapes — one failed condition is enough.
Worked example · a plane, tested properly
Is \(S = \{(x,y,z) : x + 2y - z = 0\}\) a subspace of \(\mathbb R^3\)?
STEP 1
Zero vector: \(0+0-0 = 0\) ✓ so \(\mathbf 0\in S\).
STEP 2
Addition: take \(\mathbf u,\mathbf v\in S\), so \(u_1+2u_2-u_3=0\) and \(v_1+2v_2-v_3=0\). Adding the two equations gives
\[ (u_1+v_1) + 2(u_2+v_2) - (u_3+v_3) = 0 \]
so \(\mathbf u+\mathbf v\in S\) ✓
STEP 3
Scaling: multiplying \(u_1+2u_2-u_3=0\) by \(c\) gives \(cu_1+2cu_2-cu_3=0\), so \(c\mathbf u\in S\) ✓
STEP 4
All three hold ⟹ subspace. It is the plane through the origin with normal \((1,2,-1)\).
STEP 5
Its dimension is 2: solving for \(z = x+2y\) leaves \(x,y\) free, giving the basis \(\{(1,0,1),(0,1,2)\}\). Note that changing the equation to \(x+2y-z=5\) breaks step 1 immediately — homogeneous is exactly what makes a linear condition define a subspace.
②Practice
1
Is \(\{(x,y) : y = 3x\}\) a subspace of \(\mathbb R^2\)? Is \(\{(x,y): y = 3x+2\}\)?
Hint 1Check the origin first — it settles the second one instantly.
Solution
STEP 1 · the first set, origin
\(y=3x\) with \((0,0)\): \(0 = 0\) ✓
STEP 2 · closure
If \(y_1=3x_1\) and \(y_2=3x_2\), then \(y_1+y_2 = 3(x_1+x_2)\) ✓ and \(cy_1 = 3(cx_1)\) ✓ So it is a subspace — a line through the origin, \(\operatorname{span}\{(1,3)\}\).
STEP 3 · the second set, origin
\((0,0)\) requires \(0 = 2\), false. Not a subspace.
STEP 4 · confirm with closure anyway
\((0,2)\) and \((1,5)\) are both in the set, but their sum \((1,7)\) needs \(7 = 3+2 = 5\) ✗ — addition fails too.
STEP 5 · the general principle
A linear equation defines a subspace only when it is homogeneous (right-hand side zero). The shifted line is a coset — the solution set of a nonhomogeneous system, exactly the structure of module M4.
2
Is the set of vectors in \(\mathbb R^3\) with \(x \ge 0\) a subspace?
Hint 1It contains \(\mathbf 0\) and is closed under addition — so check the third condition carefully.
Hint 2What does multiplying by \(-1\) do?
Solution
STEP 1 · origin
\((0,0,0)\) has \(x = 0 \ge 0\) ✓
STEP 2 · addition
If \(x_1\ge0\) and \(x_2\ge0\) then \(x_1+x_2\ge0\) ✓
STEP 3 · scaling — the failure
Take \(\mathbf u = (1,0,0)\in S\) and \(c=-1\):
\[ -\mathbf u = (-1,0,0) \ \text{ has } x = -1 < 0 \ \Longrightarrow\ \text{not in } S \]
STEP 4 · conclude
Not a subspace. One failed condition is fatal, however many others hold.
STEP 5 · what it is instead
A half-space — convex, and perfectly respectable in optimization (linear programming lives on such sets), but not a subspace. Inequalities never define subspaces, because they are destroyed by negative scaling.
3
Show that the solution set of \(A\mathbf x=\mathbf 0\) is always a subspace.
Hint 1Use linearity of matrix multiplication: \(A(\mathbf u+\mathbf v) = A\mathbf u + A\mathbf v\).
Hint 2Check all three conditions in turn.
Solution
STEP 1 · zero
\[ A\mathbf 0 = \mathbf 0 \ ✓ \]
so \(\mathbf 0\) is always a solution.
STEP 2 · addition
If \(A\mathbf u=\mathbf 0\) and \(A\mathbf v=\mathbf 0\), then
All three hold, so the solution set — the null space \(\operatorname{null}(A)\) — is a subspace of \(\mathbb R^n\).
STEP 5 · the contrast
The same computation fails for \(A\mathbf x = \mathbf b\) with \(\mathbf b\ne\mathbf 0\): adding two solutions gives \(A(\mathbf u+\mathbf v) = 2\mathbf b \ne \mathbf b\). Homogeneous solution sets are subspaces; nonhomogeneous ones are translates of them (module M4). Everything in module S1 rests on this.
4
Find a basis and the dimension of \(S=\{(x,y,z): x = 2y\}\subset\mathbb R^3\).
Hint 1Solve the constraint and identify which variables are free.
Hint 2Write a general element in terms of those free variables.
Solution
STEP 1 · solve the constraint
\(x = 2y\), with \(y\) and \(z\) unconstrained. Take them as free parameters \(s,t\).
STEP 2 · write a general element
\[ (x,y,z) = (2s,\ s,\ t) = s\begin{bmatrix}2\\1\\0\end{bmatrix} + t\begin{bmatrix}0\\0\\1\end{bmatrix} \]
STEP 3 · read off the basis
\[ \left\{\begin{bmatrix}2\\1\\0\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix}\right\} \]
STEP 4 · check independence
Neither is a multiple of the other (the third components 0 and 1 settle it) ✓ so this really is a basis.
STEP 5 · dimension
\(\dim S = 2\) — a plane through the origin. The count is no accident: one equation imposed on \(\mathbb R^3\) removes one degree of freedom, \(3-1=2\). That bookkeeping becomes the rank–nullity theorem in module S1.
5
Is the union of the \(x\)-axis and the \(y\)-axis a subspace of \(\mathbb R^2\)? Is their intersection?
Hint 1For the union, test closure under addition with one vector from each axis.
Hint 2The intersection of two lines through the origin is…?
Solution
STEP 1 · the union, addition test
\((1,0)\) and \((0,1)\) are both in the union, but
\[ (1,0)+(0,1) = (1,1) \]
lies on neither axis. Not a subspace.
STEP 2 · why unions generally fail
A union of two subspaces is a subspace only if one contains the other. Otherwise you can always step off both by adding.
STEP 3 · the intersection
The only point on both axes is the origin, so the intersection is \(\{\mathbf 0\}\) — the zero subspace, which satisfies all three conditions trivially ✓
STEP 4 · the general facts
Intersections of subspaces are always subspaces. Unions almost never are. When you want a subspace containing both, use the sum \(U+W = \{\mathbf u+\mathbf w\}\), which here is all of \(\mathbb R^2\).
STEP 5 · why it matters
Adding equations to a system intersects solution sets — which is why solution spaces shrink but stay subspaces. Combining spanning sets takes sums, which is why column spaces grow.
6
Is \(\{(x,y): x^2 = y^2\}\) a subspace of \(\mathbb R^2\)?
Hint 1Rewrite the condition — what shape is it?
Hint 2\(x^2=y^2\) means \(y=\pm x\): two lines.
Solution
STEP 1 · identify the set
\(x^2=y^2 \iff y = x\) or \(y = -x\) — the union of two lines through the origin.
STEP 2 · check the origin and scaling
\(\mathbf 0\) qualifies ✓, and scaling any point on either line keeps it on that line ✓ Two conditions pass.
Not a subspace — the same union failure as problem 5, disguised by a nonlinear equation.
STEP 5 · the diagnostic
A subspace can be described by linear homogeneous equations only. Squares, products, absolute values, or inequalities in the defining condition are all warning signs — check closure explicitly whenever you see one.
7
List all subspaces of \(\mathbb R^2\), and all subspaces of \(\mathbb R^3\).
Hint 1Organize by dimension: 0, 1, 2, …
Hint 2What does a one-dimensional subspace look like geometrically?
Solution
STEP 1 · ℝ² by dimension
dim
subspace
0
\(\{\mathbf 0\}\)
1
any line through the origin
2
all of \(\mathbb R^2\)
STEP 2 · ℝ³ by dimension
dim
subspace
0
\(\{\mathbf 0\}\)
1
any line through the origin
2
any plane through the origin
3
all of \(\mathbb R^3\)
STEP 3 · why nothing else is possible
A subspace of dimension \(k\) is the span of \(k\) independent vectors — a flat, unbounded object through the origin. There is no room for curved, bounded, or offset sets.
STEP 4 · the pattern in ℝⁿ
Subspaces of every dimension \(0,1,\dots,n\), each one a "flat through the origin." The two extremes \(\{\mathbf 0\}\) and \(\mathbb R^n\) are called trivial; everything between is a proper subspace.
STEP 5 · why this rigidity is useful
Because the possibilities are so limited, identifying a subspace's dimension identifies it completely up to position. That is why answers like "the null space is 2-dimensional" are informative: you immediately know the solution set is a plane through the origin.
8
Show that \(\operatorname{span}\{\mathbf v_1,\dots,\mathbf v_k\}\) is always a subspace.
Hint 1Take two general combinations and add them.
Hint 2The sum of two linear combinations is another linear combination.
Solution
STEP 1 · zero
All coefficients zero gives \(\mathbf 0\) ✓ (module V1 problem 9).
STEP 2 · addition
Take \(\mathbf u = \sum a_i\mathbf v_i\) and \(\mathbf w=\sum b_i\mathbf v_i\). Then
\[ \mathbf u+\mathbf w = \sum(a_i+b_i)\mathbf v_i \]
All three conditions hold, so every span is a subspace.
STEP 5 · and the converse
Every subspace is also a span — take any basis of it. So "span" and "subspace" describe the same objects from two directions: built from generators versus closed under operations. That equivalence is why column space (a span) and null space (a closure condition) can be compared in the same theorem.
9
The set of \(2\times2\) matrices with trace zero — is it a subspace of the space of all \(2\times2\) matrices? What is its dimension?
Hint 1Trace is \(a+d\) for \(\begin{bmatrix}a&b\\c&d\end{bmatrix}\), and it is a linear function.
Hint 2The full space of \(2\times2\) matrices has dimension 4; one linear condition removes one.
Solution
STEP 1 · check the conditions
The zero matrix has trace 0 ✓; \(\operatorname{tr}(A+B) = \operatorname{tr}A+\operatorname{tr}B = 0\) ✓; \(\operatorname{tr}(cA) = c\operatorname{tr}A = 0\) ✓ So it is a subspace.
STEP 2 · parametrize it
The condition is \(d = -a\), leaving \(a,b,c\) free:
Those three matrices are independent (each has a 1 where the others have 0), so they form a basis.
STEP 4 · dimension
\[ \dim = 3 = 4 - 1 \]
one linear condition on a 4-dimensional space.
STEP 5 · the broader point
Vector spaces need not consist of arrows: matrices, polynomials, and functions all qualify, and the same definitions apply verbatim. This trace-zero space is \(\mathfrak{sl}_2\), central to Lie theory and quantum mechanics — and PDE eigenfunction expansions (the PDE Launchpad) are linear algebra in an infinite-dimensional function space.
Part I · Checkpoint Quiz
Quiz A — Vectors, span & independence
Ten questions on combinations, dot and cross products, independence, bases, and subspaces. Tap an answer to lock it in and see the reasoning. Aim for 8/10 before starting Part II.
Question 1
What is \(\operatorname{span}\left\{\begin{bmatrix}1\\2\end{bmatrix},\begin{bmatrix}3\\6\end{bmatrix}\right\}\)?
Why
The second vector is \(3\times\) the first, so it adds no new direction. Every combination is a multiple of \((1,2)\), giving the line \(y=2x\). Two vectors span the plane only when they are independent.
Question 2
If \(\mathbf u\cdot\mathbf v = 0\) with both vectors nonzero, then:
Why
\(\mathbf u\cdot\mathbf v = \|\mathbf u\|\|\mathbf v\|\cos\theta\). With both lengths nonzero, the product vanishes only when \(\cos\theta = 0\), i.e. \(\theta = 90^\circ\). Parallel vectors give the largest possible dot product in magnitude, not zero.
Question 3
\(\|\mathbf u\times\mathbf v\|\) equals:
Why
\(\|\mathbf u\times\mathbf v\| = \|\mathbf u\|\|\mathbf v\|\sin\theta\), exactly base times height for the parallelogram. Choice A is the dot product. Volume (choice C) needs three vectors and the scalar triple product.
Question 4
Four vectors in \(\mathbb R^3\) are:
Why
More vectors than the dimension forces dependence: the homogeneous system has 4 unknowns and only 3 equations, so a nonzero solution always exists. Choice C is a common trap — pairwise non-parallel says nothing once you have three or more vectors.
Question 5
Which set is not a subspace of \(\mathbb R^2\)?
Why
The shifted line misses the origin, failing the first condition immediately. A linear equation defines a subspace only when it is homogeneous — the right-hand side must be zero.
Question 6
The projection of \(\mathbf b\) onto \(\mathbf a\) is:
Why
The result must point along \(\mathbf a\), which rules out A. The scalar must be scale-invariant in \(\mathbf a\): doubling \(\mathbf a\) doubles the numerator but quadruples \(\mathbf a\cdot\mathbf a\), leaving the projection unchanged — correct, since the projection depends only on the direction of \(\mathbf a\). Choice C fails that test.
Question 7
A basis of a vector space \(V\) is a set that:
Why
Spanning alone gives existence of a representation; independence alone gives uniqueness where one exists. Together they give exactly one representation for every vector. A basis can never contain \(\mathbf 0\), since that instantly creates a dependence.
Question 8
If \(\det\begin{bmatrix}\mathbf v_1&\mathbf v_2&\mathbf v_3\end{bmatrix} = 0\) for three vectors in \(\mathbb R^3\), they:
Why
Zero determinant means zero volume for the parallelepiped they span — the three vectors are coplanar, hence dependent, hence span at most 2 dimensions. That rules out a basis. Perpendicular vectors would give the maximum volume, not zero.
Question 9
The dimension of \(\{(x,y,z) : x+y+z = 0\}\) is:
Why
One homogeneous equation removes one degree of freedom from \(\mathbb R^3\): \(3-1 = 2\). Solving \(z = -x-y\) leaves \(x,y\) free, with basis \(\{(1,0,-1),(0,1,-1)\}\) — a plane through the origin.
The direct path is never longer than the detour, with equality only when \(\mathbf u\) and \(\mathbf v\) point the same way. It follows from Cauchy–Schwarz (\(|\mathbf u\cdot\mathbf v|\le\|\mathbf u\|\|\mathbf v\|\)), which is choice A — the two are related but distinct statements.
Part II · Module 1 Matrices & elimination
Matrices as transformations
A matrix is not a grid of numbers; it is a function that moves space. Once you see \(A\mathbf x\) as "where \(A\) sends \(\mathbf x\)", every later topic — determinants, eigenvectors, SVD — becomes a question about that motion.
①Columns are images of the basis
The single most useful fact about matrices
\[ A\mathbf e_1 = \text{column 1 of } A, \qquad A\mathbf e_2 = \text{column 2 of } A, \qquad \dots \]
Because \(\mathbf x = x_1\mathbf e_1+\cdots+x_n\mathbf e_n\) and \(A\) is linear,
\(A\mathbf x\) is a linear combination of the columns of \(A\), with weights taken from \(\mathbf x\). That is the bridge between module V1 and everything that follows: the set of all reachable \(A\mathbf x\) is the span of the columns — the column space.
InteractiveWatch a matrix move the planeedit the entries; the grid follows
A e₁ —A e₂ —det A —image —
The faint grey grid is the original plane; the coloured grid is its image. The two heavy arrows are \(A\mathbf e_1\) and \(A\mathbf e_2\) — read them straight off the columns. Notice that gridlines stay straight, parallel lines stay parallel, and the origin never moves: that is exactly what "linear" buys you. Drag \(d\) toward 0 with the projection preset and the whole plane collapses onto a line — the determinant hits zero at the same instant.
Worked example · building a matrix from its action
Find the matrix that rotates the plane \(90^\circ\) counterclockwise.
STEP 1
Ask only where the basis vectors go — the columns will be those images.
STEP 2
\(\mathbf e_1=(1,0)\) rotates to \((0,1)\).
STEP 3
\(\mathbf e_2=(0,1)\) rotates to \((-1,0)\).
STEP 4
Stack them as columns:
\[ R = \begin{bmatrix}0&-1\\1&0\end{bmatrix} \]
STEP 5
Test on \((3,1)\): \(R(3,1) = (-1,3)\) — rotated a quarter turn ✓ Note \(\det R = 1\) (area preserved) and \(R^2 = -I\) (two quarter turns is a half turn), the matrix analogue of \(i^2=-1\).
②Practice
1
Compute \(\begin{bmatrix}2&1\\0&3\end{bmatrix}\begin{bmatrix}4\\-1\end{bmatrix}\) two ways: by rows, and as a combination of columns.
Hint 1Row view: each output entry is a dot product of a row with \(\mathbf x\).
Hint 2Column view: \(4(\text{col }1) + (-1)(\text{col }2)\).
They agree ✓ — the two views are algebraically identical, just different groupings of the same nine multiplications.
STEP 5 · when to use which
The row view is how you compute by hand. The column view is how you think: it tells you the output lives in the span of the columns, which is why solvability of \(A\mathbf x=\mathbf b\) is the question "is \(\mathbf b\) in the column space?" (module S1).
2
Find the matrix that reflects \(\mathbb R^2\) across the line \(y=x\).
Hint 1Where does \(\mathbf e_1\) go? Where does \(\mathbf e_2\) go?
Hint 2Reflection across \(y=x\) swaps coordinates.
Solution
STEP 1 · image of e₁
\((1,0)\) reflects to \((0,1)\).
STEP 2 · image of e₂
\((0,1)\) reflects to \((1,0)\).
STEP 3 · assemble
\[ F = \begin{bmatrix}0&1\\1&0\end{bmatrix} \]
STEP 4 · verify
\(F(3,7) = (7,3)\) ✓ — coordinates swapped, as expected.
STEP 5 · properties worth noticing
\(\det F = -1\) (orientation reversed, area preserved) and \(F^2 = I\) (reflecting twice returns you home). Vectors on the mirror line, like \((1,1)\), are fixed: \(F\mathbf v = \mathbf v\). Those are eigenvectors with \(\lambda=1\), and \((1,-1)\) has \(\lambda=-1\) — module E1 in advance.
3
What does \(\begin{bmatrix}1&2\\2&4\end{bmatrix}\) do to the plane? Describe the image.
Hint 1Look at the two columns — are they independent?
Every output is \(x_1\mathbf a_1+x_2(2\mathbf a_1) = (x_1+2x_2)\mathbf a_1\) — a multiple of \((1,2)\). The image is the line \(y=2x\).
STEP 3 · what gets crushed
Solve \(A\mathbf x=\mathbf 0\): \(x_1+2x_2=0\), so \(\mathbf x = t(-2,1)\). The whole line spanned by \((-2,1)\) collapses to the origin — that is the null space.
STEP 4 · describe the motion
The plane is flattened onto a line: a 2-D input space maps onto a 1-D image, with a 1-D line of inputs annihilated. \(\det A = 4-4 = 0\), confirming zero area survives.
Dimensions are conserved: whatever the image loses, the null space gains. That is rank–nullity (module S1), visible here in the simplest possible case.
4
Find the \(2\times2\) matrix \(A\) with \(A\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}3\\1\end{bmatrix}\) and \(A\begin{bmatrix}1\\-1\end{bmatrix}=\begin{bmatrix}1\\5\end{bmatrix}\).
Hint 1You are told the action on a basis that isn't the standard one — first express \(\mathbf e_1,\mathbf e_2\) in terms of the given vectors.
Hint 2\(\mathbf e_1 = \frac12[(1,1)+(1,-1)]\).
Solution
STEP 1 · express e₁ in the given basis
\[ \mathbf e_1 = \tfrac12\begin{bmatrix}1\\1\end{bmatrix} + \tfrac12\begin{bmatrix}1\\-1\end{bmatrix} \]
STEP 2 · apply A using linearity
\[ A\mathbf e_1 = \tfrac12\begin{bmatrix}3\\1\end{bmatrix} + \tfrac12\begin{bmatrix}1\\5\end{bmatrix} = \begin{bmatrix}2\\3\end{bmatrix} \]
STEP 4 · assemble
\[ A = \begin{bmatrix}2&1\\3&-2\end{bmatrix} \]
STEP 5 · verify both conditions
\(A(1,1) = (2+1, 3-2) = (3,1)\) ✓ and \(A(1,-1) = (2-1, 3+2) = (1,5)\) ✓ A linear map is completely determined by its action on any basis — this problem is the practical face of that theorem, and the systematic version is the change-of-basis formula in module S2.
5
Is \(T(x,y) = (x+1, y)\) — translation by one unit — a linear transformation?
Hint 1Every linear map sends \(\mathbf 0\) to \(\mathbf 0\).
Hint 2Check additivity as well.
Solution
STEP 1 · test the origin
\[ T(0,0) = (1,0) \ne (0,0) \]
Translation becomes linear in one higher dimension.
STEP 5 · the pattern to remember
Any map of the form \(\mathbf x\mapsto A\mathbf x + \mathbf b\) with \(\mathbf b\ne\mathbf 0\) is affine, not linear — and the solution set of \(A\mathbf x=\mathbf b\) has exactly that shape (module M4).
6
Write the matrix that scales \(x\) by 3, leaves \(y\) alone, and negates \(z\) in \(\mathbb R^3\). What is its determinant, and what does that number mean here?
Hint 1Independent scalings give a diagonal matrix.
Hint 2The determinant of a diagonal matrix is the product of the diagonal.
Volumes are multiplied by \(|{-3}| = 3\): the unit cube becomes a \(3\times1\times1\) box.
STEP 5 · interpret the sign
Negative means orientation is reversed — a right-handed frame becomes left-handed, because the \(z\)-axis flipped. Determinant sign is a mirror-detector, and a single reflection always contributes a factor of \(-1\).
7
A transformation sends the unit square to the parallelogram with vertices \((0,0)\), \((2,1)\), \((3,3)\), \((1,2)\). Find its matrix and its area factor.
Hint 1Which vertex is the image of \(\mathbf e_1\)? Of \(\mathbf e_2\)?
Hint 2The vertex \((3,3)\) must be \(A(1,1) = A\mathbf e_1 + A\mathbf e_2\).
Solution
STEP 1 · identify the images
\((0,0)\) is fixed (linearity). The two edge-vertices are \(A\mathbf e_1 = (2,1)\) and \(A\mathbf e_2 = (1,2)\).
STEP 3 · assemble
\[ A = \begin{bmatrix}2&1\\1&2\end{bmatrix} \]
STEP 4 · area factor
\[ \det A = 4 - 1 = 3 \]
The unit square (area 1) becomes a parallelogram of area 3.
STEP 5 · the general principle
\(|\det A|\) is the factor by which \(A\) scales every area, not just the unit square — because any region can be approximated by small squares, all scaled identically. That is precisely the Jacobian factor in multivariable change of variables.
8
Show that any linear \(T:\mathbb R^n\to\mathbb R^m\) can be written as \(T(\mathbf x) = A\mathbf x\) for some \(m\times n\) matrix.
Hint 1Expand \(\mathbf x\) in the standard basis and push \(T\) through.
Hint 2Define \(A\) by its columns.
Solution
STEP 1 · expand the input
\[ \mathbf x = x_1\mathbf e_1 + \cdots + x_n\mathbf e_n \]
using additivity \(n-1\) times and homogeneity \(n\) times.
STEP 3 · define the matrix
Let \(A = \big[\,T(\mathbf e_1)\ \cdots\ T(\mathbf e_n)\,\big]\), an \(m\times n\) matrix since each \(T(\mathbf e_j)\in\mathbb R^m\).
STEP 4 · recognize the combination
Step 2 says \(T(\mathbf x)\) is the combination of \(A\)'s columns with weights \(x_j\) — which is exactly \(A\mathbf x\) ✓
STEP 5 · what this theorem means
Linear maps and matrices are the same thing, once a basis is fixed. Matrices are how you compute; linear maps are what the computation means. The "once a basis is fixed" caveat is the whole content of module S2 — the same map gets a different matrix in a different basis, and diagonalization (module E2) is the art of choosing the basis that makes the matrix simplest.
9
Find a \(2\times2\) matrix \(A\ne 0\) with \(A^2 = 0\), and explain geometrically how that is possible.
Hint 1You need the image of \(A\) to sit inside the null space of \(A\).
Hint 2Try a matrix with a single nonzero entry off the diagonal.
Solution
STEP 1 · propose a candidate
\[ A = \begin{bmatrix}0&1\\0&0\end{bmatrix} \]
\(A\) sends \((x,y)\mapsto(y,0)\): the whole plane lands on the \(x\)-axis. But the \(x\)-axis is exactly what \(A\) kills, since \(A(x,0) = (0,0)\).
STEP 4 · why two steps annihilate
\(\operatorname{im}(A)\subseteq\operatorname{null}(A)\), so the first application lands everything in the kill zone and the second wipes it out.
STEP 5 · what this rules out
Matrix algebra has zero divisors: \(A\ne0\) with \(A^2=0\) has no scalar analogue. Such a matrix is called nilpotent; both its eigenvalues are 0 yet it is not the zero matrix, which is precisely why it cannot be diagonalized (module E2) and why Jordan form exists.
Part II · Module 2 Matrices & elimination
Matrix multiplication
\(AB\) is the matrix of "do \(B\), then do \(A\)". Every strange-looking rule about matrix products — the row-times-column recipe, the failure of commutativity, the reversal in \((AB)^{T}\) — falls out of that one sentence.
①Four ways to see the same product
Entry formula
\[ (AB)_{ij} = \sum_{k} a_{ik}b_{kj} = (\text{row } i \text{ of } A)\cdot(\text{col } j \text{ of } B) \]
Column view: column \(j\) of \(AB\) is \(A\,(\text{column } j \text{ of } B)\).
Row view: row \(i\) of \(AB\) is \((\text{row } i \text{ of } A)\,B\).
Shapes must match: \((m\times n)(n\times p) = (m\times p)\). The inner dimensions cancel; the outer ones survive.
InteractiveOrder matterscompose a rotation and a shear both ways
SR —RS —equal? —
One shape is shown after each order of operations. They generally land in different places — that is non-commutativity, not an algebraic quirk. Rotating a sheared square is not the same as shearing a rotated one. Set \(s=0\) or \(\theta=0\) and the two collapse together, because composing with the identity commutes with everything. Both determinants stay equal, though: \(\det(AB)=\det(BA)\) always, even when \(AB\ne BA\).
Worked example · a product, three ways
Compute \(AB\) for \(A=\begin{bmatrix}1&2\\3&0\end{bmatrix}\), \(B=\begin{bmatrix}0&1\\4&-1\end{bmatrix}\).
STEP 1
Check shapes: \((2\times2)(2\times2)\) ✓ result is \(2\times2\).
STEP 2
Entry \((1,1)\) = row 1 of \(A\) dot col 1 of \(B\) = \((1)(0)+(2)(4) = 8\). Entry \((1,2)\) = \((1)(1)+(2)(-1) = -1\).
Column check: col 1 of \(AB\) should be \(A\begin{bmatrix}0\\4\end{bmatrix} = 0\begin{bmatrix}1\\3\end{bmatrix}+4\begin{bmatrix}2\\0\end{bmatrix} = \begin{bmatrix}8\\0\end{bmatrix}\) ✓
STEP 5
Now the other order: \(BA = \begin{bmatrix}3&0\\1&8\end{bmatrix}\) — completely different. But \(\det(AB) = 24 = \det(BA)\), and indeed \(\det A\cdot\det B = (-6)(-4) = 24\) ✓
STEP 4 · assemble
\[ AB = \begin{bmatrix}4&-3\\5&9\end{bmatrix} \]
STEP 5 · note the other order
\(BA\) is \((3\times2)(2\times3) = 3\times3\) — a different size entirely. When \(A\) and \(B\) are not square, \(AB\) and \(BA\) need not even be comparable.
2
Find \(2\times2\) matrices with \(AB\ne BA\), then find a nontrivial pair that does commute.
Hint 1Almost any random pair fails to commute — try a shear and a scaling.
Hint 2Powers of the same matrix always commute, as do rotations with each other.
Solution
STEP 1 · a non-commuting pair
\[ A = \begin{bmatrix}1&1\\0&1\end{bmatrix}, \qquad B = \begin{bmatrix}2&0\\0&1\end{bmatrix} \]
STEP 2 · both products
\[ AB = \begin{bmatrix}2&1\\0&1\end{bmatrix}, \qquad BA = \begin{bmatrix}2&2\\0&1\end{bmatrix} \]
Different ✓ — shearing then stretching is not stretching then shearing.
Two rotations commute, since composing rotations just adds angles.
STEP 4 · more commuting families
Any matrix commutes with \(I\), with \(cI\), and with its own powers and inverse. Two diagonal matrices always commute.
STEP 5 · when it matters
Commuting matrices can be simultaneously diagonalized — the same eigenvectors work for both. In quantum mechanics that is exactly why commuting observables can be measured together, and in module E2 it is why \(A\) and \(A^2\) share eigenvectors.
3
Show \((AB)^{T} = B^{T}A^{T}\) using a \(2\times2\) example, and explain why the order reverses.
Hint 1Compute \(AB\), transpose it, and compare with \(B^TA^T\).
Hint 2Look at what happens to the shapes if you tried \(A^TB^T\).
Solution
STEP 1 · pick matrices and multiply
\[ A=\begin{bmatrix}1&2\\0&3\end{bmatrix}, \ B=\begin{bmatrix}4&0\\1&5\end{bmatrix} \ \Longrightarrow\ AB = \begin{bmatrix}6&10\\3&15\end{bmatrix} \]
Entry \((i,j)\) of \((AB)^T\) is entry \((j,i)\) of \(AB\) = (row \(j\) of \(A\))·(col \(i\) of \(B\)) = (col \(j\) of \(A^T\))·(row \(i\) of \(B^T\)) — which is entry \((i,j)\) of \(B^TA^T\).
STEP 5 · the shape argument
If \(A\) is \(m\times n\) and \(B\) is \(n\times p\), then \((AB)^T\) is \(p\times m\). Only \(B^TA^T = (p\times n)(n\times m)\) has that shape; \(A^TB^T\) usually cannot even be formed. The same reversal governs inverses: \((AB)^{-1}=B^{-1}A^{-1}\) — socks then shoes, shoes off then socks off.
4
If \(A\) is \(3\times4\) and \(B\) is \(4\times2\), what are the shapes of \(AB\), \(BA\), \(A^TB^{T}\)? Which exist?
Hint 1The rule: \((m\times n)(n\times p)\) works only when the inner dimensions match.
Solution
STEP 1 · AB
\((3\times4)(4\times2)\): inner dimensions 4 and 4 match ✓ Result is \(3\times2\).
STEP 2 · BA
\((4\times2)(3\times4)\): inner dimensions 2 and 3 do not match ✗ Undefined.
STEP 3 · AᵀBᵀ
\(A^T\) is \(4\times3\), \(B^T\) is \(2\times4\). Then \((4\times3)(2\times4)\) has inner dimensions 3 and 2 ✗ Undefined.
STEP 4 · what does work
\(B^{T}A^{T} = (2\times4)(4\times3) = 2\times3\) ✓ — and it equals \((AB)^{T}\), which is indeed \(2\times3\).
STEP 5 · the composition reading
\(B:\mathbb R^2\to\mathbb R^4\) and \(A:\mathbb R^4\to\mathbb R^3\), so \(AB:\mathbb R^2\to\mathbb R^3\) chains correctly. \(BA\) would require feeding \(\mathbb R^3\) output into a map expecting \(\mathbb R^2\) — nonsense. Shape rules are just function-domain rules.
5
Compute \(A^2\) and \(A^3\) for \(A = \begin{bmatrix}1&1\\0&1\end{bmatrix}\), and find the pattern for \(A^n\).
Hint 1Compute the first two powers and look at the top-right entry.
Hint 2Geometrically, \(A\) is a unit shear — what does shearing \(n\) times do?
Shears accumulate additively. Both eigenvalues of \(A\) are 1, but \(A\) is not diagonalizable (only one eigenvector direction, \((1,0)\)), so \(A^n\) grows like \(n\) rather than staying bounded. Contrast module E2, where diagonalizable matrices give \(A^n = P\Lambda^nP^{-1}\) with purely exponential behaviour.
6
Compute \(\mathbf u\mathbf v^{T}\) and \(\mathbf v^{T}\mathbf u\) for \(\mathbf u = \begin{bmatrix}1\\2\end{bmatrix}\), \(\mathbf v=\begin{bmatrix}3\\-1\end{bmatrix}\). What kind of object is each?
Hint 1Track the shapes: \((2\times1)(1\times2)\) versus \((1\times2)(2\times1)\).
a \(1\times1\) matrix — a scalar, and exactly \(\mathbf u\cdot\mathbf v\).
STEP 3 · rank of the outer product
Its columns are \(3\mathbf u\) and \(-\mathbf u\), both multiples of \(\mathbf u\), so the rank is 1 and the determinant is 0.
STEP 4 · what it does
\[ (\mathbf u\mathbf v^{T})\mathbf x = \mathbf u(\mathbf v^{T}\mathbf x) = (\mathbf v\cdot\mathbf x)\,\mathbf u \]
every input is crushed onto the line through \(\mathbf u\), scaled by how much it aligns with \(\mathbf v\).
STEP 5 · where rank-1 matrices show up
Projection matrices \(\frac{\mathbf u\mathbf u^{T}}{\mathbf u^{T}\mathbf u}\) (module S5), the outer-product form of matrix multiplication, and the SVD's \(A = \sum\sigma_i\mathbf u_i\mathbf v_i^{T}\) (module E4) — where compressing an image means keeping only the largest few rank-1 pieces.
7
If \(AB = 0\), must \(A=0\) or \(B=0\)? Give a proof or a counterexample.
Hint 1Think about what \(AB=0\) says about the columns of \(B\).
Hint 2They must all lie in the null space of \(A\).
Solution
STEP 1 · counterexample
\[ A = \begin{bmatrix}1&0\\0&0\end{bmatrix}, \qquad B = \begin{bmatrix}0&0\\0&1\end{bmatrix} \]
STEP 2 · verify
\[ AB = \begin{bmatrix}0&0\\0&0\end{bmatrix} \]
yet neither factor is zero. No, the implication fails.
STEP 3 · the structural reason
\(AB=0\) says every column of \(B\) lies in \(\operatorname{null}(A)\). Here \(A\) kills the \(y\)-axis and \(B\)'s columns lie there ✓ Any \(A\) with a nontrivial null space admits such a \(B\).
STEP 4 · when the implication does hold
If \(A\) is invertible, multiply by \(A^{-1}\): \(B = A^{-1}(AB) = 0\). Invertible matrices have trivial null spaces, leaving no room for a nonzero \(B\).
STEP 5 · the moral
You cannot cancel matrices the way you cancel numbers. \(AB=AC\) does not give \(B=C\) unless \(A\) is invertible — a mistake worth watching for in every proof you write.
8
A rotation by \(30^\circ\) followed by a rotation by \(60^\circ\). Compute the product matrix and confirm it is a \(90^\circ\) rotation.
Hint 1Use the rotation matrix \(\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}\).
Hint 2The angle-addition identities will appear on their own.
Entry \((1,1)\) is \(\cos\alpha\cos\beta - \sin\alpha\sin\beta = \cos(\alpha+\beta)\) and entry \((2,1)\) is \(\sin(\alpha+\beta)\). Matrix multiplication encodes the angle-addition formulas — and since rotations commute, \(R_{30}R_{60}\) gives the same result.
9
Explain why matrix multiplication is defined by the row-times-column rule rather than entrywise.
Hint 1The requirement is \((AB)\mathbf x = A(B\mathbf x)\) for all \(\mathbf x\).
Hint 2Work out what entrywise multiplication would do to composition.
Solution
STEP 1 · state the requirement
Matrices represent linear maps, so their product must represent composition: \((AB)\mathbf x = A(B\mathbf x)\).
The coefficient of \(x_j\) is \(\sum_k a_{ik}b_{kj}\) — exactly the row-times-column rule. It is forced, not chosen.
STEP 4 · why entrywise fails
Entrywise (Hadamard) multiplication does not respect composition: with \(A=B=\begin{bmatrix}0&1\\1&0\end{bmatrix}\) (a swap), composing gives \(I\), but the entrywise product is the zero matrix — the wrong answer for "swap twice".
STEP 5 · the design principle
Definitions in linear algebra are reverse-engineered from the behaviour they must produce. The same logic explains why the determinant multiplies (\(\det(AB)=\det A\det B\): area factors compose) and why the transpose reverses order.
Part II · Module 3 Matrices & elimination
Gaussian elimination & RREF
Elimination is the engine of the entire subject. It solves systems, computes rank, inverts matrices, and finds bases for all four fundamental subspaces — and it is nothing more than the systematic use of three reversible row operations.
All three are reversible, so they never change the solution set. Apply them to the augmented matrix \([A\mid\mathbf b]\) until you reach:
Row echelon form (REF): each leading entry (pivot) is to the right of the one above; zero rows at the bottom. Then back-substitute.
Reduced row echelon form (RREF): additionally every pivot is 1 and is the only nonzero entry in its column. The solution can then be read off directly, and the RREF of a matrix is unique.
InteractiveStep through eliminationrows as planes; watch them straighten
operation —rank —status —
Each row of the system is drawn as a line in the plane; a solution is a point where they all meet. Elimination pivots the lines about their intersection — the crossing point never moves, which is the geometric content of "row operations preserve the solution set." The final step leaves lines parallel to the axes, so the coordinates can be read straight off. Switch to the inconsistent system and watch a row become \(0 = 1\): parallel lines that never meet.
Worked example · full elimination to RREF
Solve \(\begin{aligned} x + 2y + z &= 4\\ 2x + 5y - z &= 3\\ 3x + 7y \ \ \ &= 7\end{aligned}\)
Two pivots ⟹ \(\operatorname{rank}=2\), with pivot columns 1 and 3 and one free variable. Columns 1 and 3 of the original matrix form a basis for the column space, and \(\operatorname{null}\) is 1-dimensional: \(2+1=3\) ✓
\(\operatorname{rank}(A) = 1\) but \(\operatorname{rank}([A|\mathbf b]) = 2\). A system is consistent exactly when those two ranks agree. Geometrically the two planes are parallel: same normal \((1,1,1)\), different offsets, so they never meet.
4
For which \(k\) does \(\begin{aligned}x+2y&=3\\ 2x+ky&=6\end{aligned}\) have (a) a unique solution, (b) no solution, (c) infinitely many?
Hint 1Eliminate and see what the second row becomes in terms of \(k\).
Hint 2The special case is where the coefficient of \(y\) vanishes.
The second pivot exists, forcing \(y=0\) and then \(x=3\) — a unique solution.
STEP 3 · case k = 4
Row 2 becomes \(0 = 0\): no contradiction, no pivot. \(y=t\) is free and \(x = 3-2t\) — infinitely many solutions.
STEP 4 · no-solution case
There is none. The right-hand side entry also became 0, so inconsistency never arises. (Had the second equation been \(2x+4y=7\), then \(k=4\) would give \(0=1\) and no solution.)
STEP 5 · the determinant view
\(\det\begin{bmatrix}1&2\\2&k\end{bmatrix} = k-4\). Nonzero determinant ⟹ invertible ⟹ unique solution for every right-hand side. Zero determinant ⟹ either no solution or infinitely many, decided by \(\mathbf b\).
5
Solve the homogeneous system \(\begin{aligned}x+2y-z&=0\\ 2x+4y+z&=0\end{aligned}\) and describe the solution set geometrically.
Hint 1Homogeneous systems always have \(\mathbf x=\mathbf 0\); the question is whether there is more.
Hint 2Two equations, three unknowns ⟹ at least one free variable.
Row 1 becomes \(x + 2y = 0\), so \(x = -2y\) with \(y = t\) free.
STEP 4 · write the solution
\[ \mathbf x = t\begin{bmatrix}-2\\1\\0\end{bmatrix} \]
STEP 5 · the geometry
A line through the origin in \(\mathbb R^3\) — the null space, spanned by \((-2,1,0)\). Rank 2 plus nullity 1 equals 3 columns ✓ Two planes through the origin meeting in a line, exactly as expected.
6
Explain why the RREF of a matrix is unique even though the REF is not.
Hint 1Row operations preserve the row space and the null space.
Hint 2The RREF adds requirements that leave no freedom: pivots are 1 and alone in their columns.
Solution
STEP 1 · why REF is not unique
Scaling any row, or adding a multiple of a lower pivot row to a higher one, keeps echelon shape but changes entries. \(\begin{bmatrix}1&2\\0&3\end{bmatrix}\) and \(\begin{bmatrix}2&4\\0&1\end{bmatrix}\) are both REFs of the same matrix.
STEP 2 · what is preserved
Row operations never change the null space, and never change which columns are dependent on earlier ones. So the pivot column positions are determined by the original matrix.
STEP 3 · why the entries are then forced
Each non-pivot column is a specific combination of the pivot columns before it, and that combination is exactly what RREF displays. Normalizing pivots to 1 and zeroing the rest of each pivot column removes every remaining degree of freedom.
STEP 4 · conclude
Two RREFs of the same matrix have the same pivot positions and the same forced entries, hence are identical.
STEP 5 · why you should care
Uniqueness makes RREF a genuine canonical form: two matrices have the same RREF exactly when they are row-equivalent, i.e. have the same row space and null space. That is what lets you compare systems, and why "the" RREF is a legitimate phrase while "the" REF is not.
7
Balance the chemical equation \(a\,\mathrm{C_3H_8} + b\,\mathrm{O_2} \to c\,\mathrm{CO_2} + d\,\mathrm{H_2O}\) using elimination.
Hint 1Write one equation per element: carbon, hydrogen, oxygen.
Hint 2The system is homogeneous with a one-dimensional null space — scale to the smallest integers.
Solution
STEP 1 · one equation per element
\[ \text{C}: 3a = c, \qquad \text{H}: 8a = 2d, \qquad \text{O}: 2b = 2c + d \]
STEP 2 · express everything in terms of a
\[ c = 3a, \qquad d = 4a \]
STEP 3 · substitute into the oxygen equation
\[ 2b = 2(3a) + 4a = 10a \ \Longrightarrow\ b = 5a \]
The system is homogeneous, and any valid balance can be scaled — doubling every coefficient still balances. So the null space is (at least) one-dimensional by chemistry as well as by algebra, and "balancing" means picking the smallest positive integer vector in it.
8
Solve \(\begin{aligned}x_1+x_2+2x_3+x_4&=1\\ 2x_1+2x_2+x_3-x_4&=2\end{aligned}\), writing the answer in parametric vector form.
Hint 1Two equations, four unknowns ⟹ two free variables.
Hint 2Reach RREF, then set the non-pivot variables to parameters.
STEP 2 · sum over all columns
\[ \sum_{k=1}^{n}(n-k)^2 = \sum_{j=0}^{n-1}j^2 \approx \frac{n^3}{3} \]
STEP 3 · add back-substitution
Back-substitution costs only \(O(n^2)\), so the total is \(\approx \frac{n^3}{3}\) — cubic in \(n\).
STEP 4 · compare with Cramer's rule
Cramer's rule needs \(n+1\) determinants; computed by cofactor expansion that is \(O(n!)\). For \(n=20\), elimination costs a few thousand operations while \(20!\approx 2.4\times10^{18}\) — the difference between instant and never.
STEP 5 · the practical consequences
Doubling \(n\) multiplies the work by 8, which is why large sparse systems get iterative methods instead. It also motivates the LU factorization (module M5): pay \(\frac{n^3}{3}\) once, then solve each new right-hand side for only \(O(n^2)\). And numerically, partial pivoting — always choosing the largest available pivot — is what keeps that cubic work from being destroyed by round-off.
Part II · Module 4 Matrices & elimination
Existence, uniqueness & rank
Every linear system has exactly three possible fates: no solution, one solution, or infinitely many. Rank tells you which — before you finish solving.
\[ \mathbf x = \underbrace{\mathbf x_p}_{\text{any particular solution}} + \underbrace{\mathbf x_h}_{\text{anything in null}(A)} \]
That decomposition is why solution sets are lines, planes, or flats — a subspace, picked up and translated. It is also exactly the structure you meet again in differential equations, where the general solution is a particular solution plus the homogeneous one.
InteractiveThree fates of a linear systemmove b and watch the verdict
rank A —rank [A|b] —verdict —
The shaded region is the column space of \(A\) — everything the matrix can reach. The amber dot is \(\mathbf b\). When \(A\) has full rank the column space is the whole plane, so every \(\mathbf b\) is hit exactly once. Drop to rank 1 and the column space collapses to a line: drag \(\mathbf b\) onto that line and you get infinitely many solutions; drag it off and there are none. Solvability is not about \(A\) alone or \(\mathbf b\) alone — it is about whether \(\mathbf b\) lies in what \(A\) can produce.
Worked example · classifying without fully solving
For \(A = \begin{bmatrix}1&2&3\\2&4&6\\1&1&1\end{bmatrix}\), classify \(A\mathbf x=\mathbf b\) for \(\mathbf b = (1,2,0)\) and for \(\mathbf b=(1,3,0)\).
STEP 1
Find \(\operatorname{rank}(A)\). Row 2 is \(2\times\)row 1, so it will vanish. Eliminating gives
Since \(n=3 > 2\), there is one free variable. So if a solution exists there are infinitely many — uniqueness is already ruled out for both cases.
STEP 3
First \(\mathbf b = (1,2,0)\). Augment and eliminate: \(R_2\to R_2-2R_1\) gives \((0,0,0\mid 0)\) — consistent. \(\operatorname{rank}[A|\mathbf b] = 2\) ✓
STEP 4
Now \(\mathbf b = (1,3,0)\). The same operation gives \((0,0,0\mid 1)\), i.e. \(0=1\). So \(\operatorname{rank}[A|\mathbf b] = 3 \ne 2\).
STEP 5
First case: infinitely many solutions (a line). Second case: no solution. Same matrix, different fate — the only thing that changed is whether \(\mathbf b\) lies in the column space.
②Practice
1
A \(3\times5\) matrix has rank 3. How many solutions does \(A\mathbf x=\mathbf b\) have, for any \(\mathbf b\in\mathbb R^3\)?
Hint 1Rank 3 with 3 rows means the rows are independent — what does that say about consistency?
Hint 2Count free variables: \(n - r\).
Solution
STEP 1 · existence
\(\operatorname{rank}(A) = 3 = m\), so the column space is all of \(\mathbb R^3\). Every \(\mathbf b\) is reachable ⟹ always consistent.
STEP 2 · free variables
\[ n - r = 5 - 3 = 2 \]
STEP 3 · conclude
Infinitely many solutions for every \(\mathbf b\) — a 2-parameter family.
STEP 4 · the shape
The solution set is a translate of the 2-dimensional null space: a plane sitting inside \(\mathbb R^5\).
STEP 5 · the general rule
More unknowns than equations (\(n > m\)) means the system is underdetermined: it can never have a unique solution. If it is consistent at all, it has infinitely many. This is exactly the setting where least-norm solutions and the pseudoinverse (module E4) become the right tools.
2
A \(5\times3\) matrix has rank 3. Discuss existence and uniqueness.
Hint 1Rank 3 = number of columns ⟹ no free variables.
Hint 2But the column space is only 3-dimensional inside \(\mathbb R^5\).
Solution
STEP 1 · uniqueness
\(r = 3 = n\), so there are no free variables. If a solution exists it is unique.
STEP 2 · existence
The column space is a 3-dimensional subspace of \(\mathbb R^5\) — most vectors \(\mathbf b\) lie outside it.
STEP 3 · conclude
Zero or one solution: unique when \(\mathbf b\in\operatorname{col}(A)\), none otherwise.
STEP 4 · the null space
\(\operatorname{null}(A) = \{\mathbf 0\}\), which is what "no free variables" means. The columns are independent.
STEP 5 · the practical response
This is the overdetermined case — five measurements, three parameters, typical of data fitting. Exact solutions usually don't exist, so you settle for the \(\hat{\mathbf x}\) minimizing \(\|A\mathbf x-\mathbf b\|\): least squares, module S5.
3
Given \(\operatorname{rank}(A)=2\) for a \(3\times3\) matrix and one solution \(\mathbf x_p = (1,1,1)\) with \(\operatorname{null}(A) = \operatorname{span}\{(1,-1,0)\}\), write every solution.
Hint 1General solution = particular + homogeneous.
Solution
STEP 1 · apply the structure theorem
\[ \mathbf x = \mathbf x_p + \mathbf x_h, \qquad \mathbf x_h\in\operatorname{null}(A) \]
STEP 3 · verify it works
\[ A(\mathbf x_p + t\mathbf x_h) = A\mathbf x_p + tA\mathbf x_h = \mathbf b + \mathbf 0 = \mathbf b \ ✓ \]
STEP 4 · verify nothing is missed
If \(\mathbf x\) is any solution, then \(A(\mathbf x-\mathbf x_p) = \mathbf b-\mathbf b = \mathbf 0\), so \(\mathbf x-\mathbf x_p\in\operatorname{null}(A)\) — every solution has this form.
STEP 5 · the geometry
A line through \((1,1,1)\) in direction \((1,-1,0)\) — the null-space line, translated. Note \(2 + 1 = 3\) ✓ rank plus nullity equals the number of columns.
4
Can a homogeneous system \(A\mathbf x=\mathbf 0\) be inconsistent? Can it have a unique solution?
Hint 1Is \(\mathbf x=\mathbf 0\) always a solution?
Hint 2Uniqueness depends on whether there are free variables.
Solution
STEP 1 · inconsistency is impossible
\(A\mathbf 0 = \mathbf 0\) always, so the trivial solution is guaranteed. Homogeneous systems are never inconsistent.
STEP 2 · confirm via rank
Augmenting with a zero column cannot raise the rank, so \(\operatorname{rank}(A)=\operatorname{rank}([A|\mathbf 0])\) automatically ✓
STEP 3 · uniqueness
Yes, when \(\operatorname{rank}(A) = n\): no free variables means \(\mathbf x=\mathbf 0\) is the only solution.
STEP 4 · when it fails
If \(r < n\) there are free variables and infinitely many solutions — in particular whenever \(m < n\), since \(r\le m < n\).
STEP 5 · the theorem worth memorizing
A homogeneous system with more unknowns than equations always has a nonzero solution. That single fact proves that \(n+1\) vectors in \(\mathbb R^n\) are dependent — the counting argument behind the invariance of dimension (module V4 problem 9).
5
For which \(a\) does \(\begin{bmatrix}1&2&a\\1&a&2\\a&2&1\end{bmatrix}\mathbf x = \mathbf 0\) have nonzero solutions?
Hint 1Nonzero solutions exist ⟺ the matrix is singular ⟺ determinant zero.
Hint 2Expand the determinant as a cubic in \(a\).
Solution
STEP 1 · set up the condition
\[ \det\begin{bmatrix}1&2&a\\1&a&2\\a&2&1\end{bmatrix} = 0 \]
STEP 2 · expand along the first row
\[ 1(a - 4) - 2(1 - 2a) + a(2 - a^2) = a - 4 - 2 + 4a + 2a - a^3 \]
\(a=1\) is a root, so divide: \(a^3-7a+6 = (a-1)(a^2+a-6) = (a-1)(a+3)(a-2)\).
\[ a = 1,\ 2,\ -3 \]
STEP 5 · sanity check
At \(a=1\), rows 1 and 2 are \((1,2,1)\) and \((1,1,2)\), and row 3 is \((1,2,1)\) — identical to row 1, so the matrix is clearly singular ✓ For every other \(a\), the only solution is \(\mathbf x=\mathbf 0\).
6
Prove that if \(A\mathbf x=\mathbf b\) has two distinct solutions, it has infinitely many.
Hint 1Subtract the two solutions — what do you get?
Hint 2Then build a whole family from \(\mathbf x_1\) and that difference.
Solution
STEP 1 · subtract
Let \(A\mathbf x_1=\mathbf b\) and \(A\mathbf x_2=\mathbf b\) with \(\mathbf x_1\ne\mathbf x_2\). Then
\[ A(\mathbf x_1-\mathbf x_2) = \mathbf b - \mathbf b = \mathbf 0 \]
STEP 2 · name the difference
\(\mathbf d = \mathbf x_1-\mathbf x_2 \ne \mathbf 0\) lies in the null space.
STEP 3 · build the family
\[ A(\mathbf x_1 + t\mathbf d) = A\mathbf x_1 + tA\mathbf d = \mathbf b + \mathbf 0 = \mathbf b \]
for every real \(t\).
STEP 4 · they are all distinct
Since \(\mathbf d\ne\mathbf 0\), different \(t\) give different vectors. So there are infinitely many solutions ∎
STEP 5 · why "exactly two" is impossible
This is why the trichotomy has no fourth case. Linearity forces the solution set to be a translated subspace, and a subspace over \(\mathbb R\) has either one element or infinitely many — never two, never seventeen.
7
Three sensors give \(x+y=3\), \(y+z=5\), \(x+z=4\). Solve, and determine whether the readings could ever be inconsistent.
Hint 1Eliminate, or add all three equations and halve.
Hint 2Check the determinant of the coefficient matrix.
Solution
STEP 1 · sum all three equations
\[ 2(x+y+z) = 12 \ \Longrightarrow\ x+y+z = 6 \]
STEP 2 · subtract each original equation
\[ z = 6-3 = 3, \qquad x = 6-5 = 1, \qquad y = 6-4 = 2 \]
No. A nonzero determinant means \(A\) is invertible, so \(\mathbf x = A^{-1}\mathbf b\) exists uniquely for every right-hand side. These sensors can never contradict each other — which also means they provide no redundancy for error checking. Had the third reading been \(x+y=4\) instead, the system would be singular and inconsistency would become possible.
8
If \(A\) is \(4\times6\) with \(\operatorname{null}(A)\) of dimension 3, find \(\operatorname{rank}(A)\) and \(\dim\operatorname{col}(A)\). Is \(A\mathbf x=\mathbf b\) solvable for every \(\mathbf b\in\mathbb R^4\)?
Hint 1Rank–nullity: rank + nullity = number of columns.
\(\dim\operatorname{col}(A) = \operatorname{rank}(A) = 3\), a 3-dimensional subspace of \(\mathbb R^4\).
STEP 3 · test surjectivity
\(3 < 4\), so the column space is a proper subspace — a "hyperplane" through the origin in \(\mathbb R^4\).
STEP 4 · conclude
No. Only \(\mathbf b\) lying in that 3-dimensional column space give solvable systems; the rest are inconsistent.
STEP 5 · when it is solvable
Then there are infinitely many solutions — a 3-parameter family, since the nullity is 3. Note the common error: rank–nullity counts columns (6 here), not rows. Getting that wrong would give rank 1.
9
State the "invertible matrix theorem" for a square \(n\times n\) matrix: list as many equivalent conditions as you can.
Hint 1Think about solving, about the columns, about rank, determinant, null space, and eigenvalues.
Hint 2They are all really the same statement in different vocabulary.
Solution
STEP 1 · the solving conditions
\(A\) is invertible ⟺ \(A\mathbf x=\mathbf b\) has a unique solution for every \(\mathbf b\) ⟺ \(A\mathbf x=\mathbf 0\) has only \(\mathbf x=\mathbf 0\).
STEP 2 · the structural conditions
⟺ the columns are independent ⟺ the columns span \(\mathbb R^n\) ⟺ the columns form a basis ⟺ the same for the rows.
⟺ \(T(\mathbf x)=A\mathbf x\) is one-to-one ⟺ it is onto ⟺ \(0\) is not an eigenvalue ⟺ all singular values are positive ⟺ \(A^{T}A\) is invertible.
STEP 5 · why so many equivalences
For a square matrix, injective and surjective coincide — rank–nullity forces it, since losing a dimension in the image costs exactly one in the null space. That collapse is what makes this list possible; for non-square matrices the conditions genuinely separate, which is the whole content of problems 1 and 2 above. In practice: to test invertibility, run elimination and count pivots. Never compute \(A^{-1}\) just to solve one system.
Part II · Module 5 Matrices & elimination
Inverses and LU
The inverse undoes a transformation. The LU factorization records the elimination you already did, so the next right-hand side costs almost nothing — the difference between a textbook tool and a production one.
Gauss–Jordan method: row-reduce \([A\mid I]\). If you reach \([I\mid A^{-1}]\), the right half is the inverse; if a zero row appears on the left, \(A\) is singular.
\[ A = LU \quad\text{with } L \text{ unit lower triangular}, \ U \text{ upper triangular} \]
\(U\) is the echelon form you get from elimination; \(L\) holds the multipliers you used, in the positions you used them. Then \(A\mathbf x=\mathbf b\) becomes two triangular solves:
\[ L\mathbf y = \mathbf b \ (\text{forward}), \qquad U\mathbf x = \mathbf y \ (\text{backward}) \]
Each costs \(O(n^2)\) instead of \(O(n^3)\) — so ten right-hand sides cost one factorization plus ten cheap solves. With row swaps you get \(PA = LU\).
InteractiveUndoing a transformationA then A⁻¹ returns the shape
det A —A⁻¹ —condition number —
Applying \(A\) then \(A^{-1}\) returns the original shape exactly — that is what "inverse" means, geometrically. Now drive the determinant toward zero: the entries of \(A^{-1}\) blow up, because undoing a near-collapse requires enormous stretching. The condition number quantifies that fragility, and it is the reason numerical analysts avoid computing inverses at all: near-singular matrices amplify round-off catastrophically.
The \(2\times2\) formula agrees: \(\det A = 1\), so \(A^{-1} = \frac11\begin{bmatrix}1&-1\\-1&2\end{bmatrix}\) ✓ Always finish with the multiplication check — it costs seconds and catches every sign slip.
③Practice
1
Invert \(\begin{bmatrix}3&5\\1&2\end{bmatrix}\) using the \(2\times2\) formula, and verify.
Hint 1Swap the diagonal entries, negate the off-diagonal, divide by the determinant.
STEP 4 · verify the other order
\[ A^{-1}A = \begin{bmatrix}6-5&10-10\\-3+3&-5+6\end{bmatrix} = I \ ✓ \]
STEP 5 · why determinant 1 is pleasant
No fractions appear, and the transformation preserves area. Matrices with integer entries and determinant \(\pm1\) have integer inverses — the group \(SL_2(\mathbb Z)\), which underlies lattice cryptography and continued fractions.
2
Invert \(\begin{bmatrix}1&0&2\\0&1&0\\0&0&1\end{bmatrix}\) by inspection, and explain why it is easy.
Hint 1What transformation is this? What undoes it?
Hint 2It is an elementary matrix — an elimination step.
Solution
STEP 1 · identify the action
\(E\mathbf x = (x_1+2x_3,\ x_2,\ x_3)\) — it adds twice the third coordinate to the first.
For an elementary matrix implementing \(R_i\to R_i + cR_j\), the inverse implements \(R_i\to R_i - cR_j\): just flip the sign of the multiplier.
STEP 5 · why this matters for LU
Elimination is \(E_k\cdots E_1 A = U\), so \(A = E_1^{-1}\cdots E_k^{-1}U = LU\). Because each inverse is a sign flip and lower-triangular products stay lower triangular, \(L\) is assembled by copying the multipliers in place — no computation at all.
3
Find the LU factorization of \(A = \begin{bmatrix}2&1\\6&5\end{bmatrix}\).
Hint 1Do the elimination and record the multiplier.
Hint 2\(L\) has 1s on the diagonal and the multiplier below.
Solution
STEP 1 · eliminate
The multiplier is \(\ell_{21} = 6/2 = 3\). Apply \(R_2\to R_2-3R_1\):
\[ U = \begin{bmatrix}2&1\\0&2\end{bmatrix} \]
STEP 2 · record the multiplier in L
\[ L = \begin{bmatrix}1&0\\3&1\end{bmatrix} \]
STEP 3 · verify
\[ LU = \begin{bmatrix}1&0\\3&1\end{bmatrix}\begin{bmatrix}2&1\\0&2\end{bmatrix} = \begin{bmatrix}2&1\\6&3+2\end{bmatrix} = \begin{bmatrix}2&1\\6&5\end{bmatrix} = A \ ✓ \]
STEP 4 · use it to solve
For \(\mathbf b=(4,16)\): forward-solve \(L\mathbf y=\mathbf b\) gives \(y_1=4\), \(y_2 = 16-12 = 4\). Back-solve \(U\mathbf x=\mathbf y\) gives \(x_2 = 2\), then \(2x_1 = 4-2\), so \(x_1=1\).
\(\det A = \det L\cdot\det U = 1\cdot(2)(2) = 4\). LU gives the determinant as a by-product — the product of the pivots, which is how software actually computes determinants.
4
Show that if \(A\) is invertible then \(A^{-1}\) is unique.
Hint 1Suppose \(B\) and \(C\) both work, then compute \(BAC\) two ways.
Solution
STEP 1 · assume two inverses
Suppose \(BA = AB = I\) and \(CA = AC = I\).
STEP 2 · group one way
\[ B(AC) = BI = B \]
STEP 3 · group the other way
\[ (BA)C = IC = C \]
STEP 4 · use associativity
\(B(AC) = (BA)C\), so \(B = C\) ∎
STEP 5 · what the proof really used
Only associativity and the identity — so the argument works in any group or monoid, not just for matrices. Note also that for square matrices, a one-sided inverse is automatically two-sided (\(BA=I\) forces \(AB=I\)), a consequence of rank–nullity. That fails for non-square matrices, where left and right inverses genuinely differ.
5
Invert \(A = \begin{bmatrix}1&2\\2&4\end{bmatrix}\), or show it cannot be done.
Hint 1Compute the determinant first.
Hint 2What does a zero determinant say about the columns?
Not invertible — the formula would divide by zero.
STEP 3 · the structural reason
Column 2 is twice column 1, so the columns are dependent and \(A\) crushes the plane onto the line through \((1,2)\).
STEP 4 · why no inverse can exist
\(A(2,-1) = (0,0) = A(0,0)\). Two different inputs share an output, so no function can undo \(A\) — information was destroyed.
STEP 5 · what to do instead
Use the pseudoinverse \(A^{+}\) (module E4), which returns the least-squares, least-norm answer. Singular matrices are not a dead end; they just require asking a better-posed question than "undo this exactly."
6
Invert \(\begin{bmatrix}1&1&1\\0&1&1\\0&0&1\end{bmatrix}\) by Gauss–Jordan.
Hint 1It is upper triangular with 1s on the diagonal — clear upward from the bottom.
Hint 2The inverse of a unit upper-triangular matrix is unit upper triangular.
\(AA^{-1}\): row 1 dotted with column 2 gives \(-1+1+0=0\) ✓ etc. \(A\) forms running sums; \(A^{-1}\) takes successive differences. Summation and differencing are inverse operations — the discrete analogue of the Fundamental Theorem of Calculus.
7
If \(A\) and \(B\) are invertible \(n\times n\) matrices, simplify \((A B^{-1})^{-1}\) and \((A^{T}A)^{-1}A^{T}A\).
STEP 4 · the second expression
\[ (A^{T}A)^{-1}(A^{T}A) = I \]
by definition — anything times its own inverse is the identity.
STEP 5 · the trap to avoid
\((A^{T}A)^{-1}A^{T}\) is not \(A^{-1}\) in general — you may not distribute the inverse across the product unless both factors are square and invertible. When \(A\) is tall, \((A^{T}A)^{-1}A^{T}\) is the least-squares pseudoinverse (module S5): a left inverse, satisfying \((A^TA)^{-1}A^{T}A = I\) but not \(A(A^TA)^{-1}A^{T} = I\).
8
Why is solving \(A\mathbf x=\mathbf b\) by elimination preferred over computing \(A^{-1}\mathbf b\)?
Hint 1Count operations for each approach.
Hint 2Also think about round-off and about sparse matrices.
Solution
STEP 1 · operation counts
Elimination plus back-substitution costs \(\approx\frac{n^3}{3}\). Computing \(A^{-1}\) is essentially \(n\) such solves — about \(n^3\) — and then the multiplication \(A^{-1}\mathbf b\) costs another \(n^2\). Three times the work for the same answer.
STEP 2 · accuracy
Forming \(A^{-1}\) introduces round-off in every one of its \(n^2\) entries, and multiplying propagates all of it. Direct elimination with partial pivoting is backward stable; explicit inversion is not.
STEP 3 · sparsity
A sparse \(A\) usually has a dense inverse. A tridiagonal \(1000\times1000\) matrix stores 3000 numbers; its inverse needs a million. LU preserves much of the sparsity structure; the inverse destroys it.
STEP 4 · multiple right-hand sides
The right answer is not \(A^{-1}\) but the LU factorization: factor once at \(\frac{n^3}{3}\), then each new \(\mathbf b\) costs only \(O(n^2)\) — the same asymptotic cost as multiplying by \(A^{-1}\), with better accuracy.
STEP 5 · the practical rule
In MATLAB write A\b, not inv(A)*b; in NumPy use solve, not inv. The inverse is a superb theoretical object and a poor computational one — use it in proofs, not in code.
9
Find the LU factorization of \(\begin{bmatrix}1&2&1\\2&5&4\\3&8&8\end{bmatrix}\) and use it to solve \(A\mathbf x = (4,13,22)^{T}\).
Hint 1Eliminate column 1, then column 2, recording each multiplier.
Hint 2Forward-solve \(L\mathbf y=\mathbf b\), then back-solve \(U\mathbf x=\mathbf y\).
Row 1: \(-6+10+0 = 4\) ✓ Row 2: \(-12+25+0 = 13\) ✓ Row 3: \(-18+40+0 = 22\) ✓ And \(\det A = \) product of pivots \(= 1\). A second right-hand side would now cost only the two triangular solves — that is the whole point of keeping \(L\) and \(U\).
Part II · Module 6 Matrices & elimination
Determinants
One number that answers: does this matrix collapse space? By how much does it scale volume? Does it flip orientation? The determinant is not a formula to memorize — it is the signed volume factor of a transformation.
The third rule is what makes elimination the fastest way to compute a determinant: reduce to triangular form (tracking only sign changes from swaps), then multiply the diagonal.
InteractiveDeterminant as signed areadrag the columns
det —|det| = area —orientation —
Sweep column 2 past column 1 and the shading changes colour: the determinant has passed through zero and changed sign. At that instant the parallelogram is flat — the columns are parallel, the matrix is singular, and the plane has been crushed to a line. Sign is not decoration: it says whether the transformation preserves handedness, which is why the determinant of a reflection is negative and of a rotation is \(+1\).
Cofactor expansion confirms: \(2(3-10) - 4(1-6) + 2(5-9) = -14+20-8 = -2\) ✓ For \(3\times3\) either method is fine; beyond \(4\times4\), elimination is the only sane choice.
②Practice
1
Compute \(\det\begin{bmatrix}3&1\\4&2\end{bmatrix}\) and interpret it geometrically.
Hint 1\(ad-bc\).
Solution
STEP 1 · apply the formula
\[ \det = (3)(2)-(1)(4) = 6-4 = 2 \]
STEP 2 · magnitude
Areas are doubled: the unit square maps to a parallelogram of area 2.
STEP 3 · sign
Positive ⟹ orientation is preserved; counterclockwise stays counterclockwise.
STEP 4 · invertibility
Nonzero ⟹ the matrix is invertible, with \(\det(A^{-1}) = \frac12\) (halving areas, undoing the doubling).
STEP 5 · check against the columns
The columns \((3,4)\) and \((1,2)\) span a parallelogram; its area \(|3\cdot2-1\cdot4| = 2\) ✓ matches the cross-product magnitude for the corresponding 3-D vectors.
2
Compute \(\det\begin{bmatrix}1&2&3\\0&4&5\\0&0&6\end{bmatrix}\) and \(\det\begin{bmatrix}1&0&0\\2&4&0\\3&5&6\end{bmatrix}\).
Cofactor expansion along the first column of the upper-triangular matrix has only one nonzero term, and the remaining minor is again triangular — induction does the rest.
STEP 4 · why both are equal
The second matrix is the transpose of the first, and \(\det(A^{T})=\det A\).
STEP 5 · the practical consequence
Elimination reduces any matrix to triangular form, so every determinant computation becomes a product of pivots. Combined with \(A=LU\): \(\det A = \det L\det U = 1\cdot\prod u_{ii}\).
3
If \(\det A = 5\) for a \(3\times3\) matrix, find \(\det(2A)\), \(\det(A^{2})\), \(\det(A^{-1})\), and \(\det(A^{T}A)\).
Hint 1Scaling every row by 2 multiplies the determinant by \(2^n\), not by 2.
\(\det(2A)=8\det A\) is not a quirk: doubling every length in \(\mathbb R^3\) multiplies volume by \(2^3\). And \(\det(A^TA) = 25 \ge 0\) always — \(A^{T}A\) is positive semidefinite for any \(A\), a fact that underpins least squares (module S5).
4
Compute \(\det\begin{bmatrix}1&1&1\\1&2&4\\1&3&9\end{bmatrix}\) and identify the pattern.
Hint 1Row-reduce, or expand directly.
Hint 2The rows are \((1, x, x^2)\) for \(x=1,2,3\) — a Vandermonde matrix.
STEP 4 · the Vandermonde formula
\[ \prod_{i<j}(x_j-x_i) = (2-1)(3-1)(3-2) = (1)(2)(1) = 2 \ ✓ \]
STEP 5 · why it matters
The determinant is nonzero exactly when the \(x_i\) are distinct — which is precisely the statement that a polynomial of degree \(n-1\) is uniquely determined by its values at \(n\) distinct points. Polynomial interpolation is a linear system, and Vandermonde is its matrix. (It is also notoriously ill-conditioned for large \(n\), which is why practitioners use Newton or Lagrange forms instead.)
5
Show that a matrix with two identical rows has determinant zero, without computing anything.
Hint 1Swapping two rows negates the determinant.
Hint 2What if the swap changes nothing?
Solution
STEP 1 · swap the identical rows
The matrix is unchanged, so its determinant is unchanged: \(\det A = \det A\).
STEP 2 · but swapping negates
\[ \det A = -\det A \]
STEP 3 · solve
\[ 2\det A = 0 \ \Longrightarrow\ \det A = 0 \ ∎ \]
STEP 4 · geometric reading
Two identical rows mean the rows are dependent, so they span less than \(n\) dimensions — the parallelepiped is flat and has zero volume.
STEP 5 · the general version
Any dependence among the rows (or columns) forces \(\det=0\): subtract the appropriate multiples and a zero row appears. This is the determinant's real job — it is a single number that detects dependence.
6
Use Cramer's rule to solve \(\begin{aligned}2x+y&=5\\ x+3y&=10\end{aligned}\), then say why it is rarely used in practice.
Hint 1\(x_i = \det(A_i)/\det(A)\), where \(A_i\) has column \(i\) replaced by \(\mathbf b\).
Hint 2Count the determinants needed for an \(n\times n\) system.
Solution
STEP 1 · the main determinant
\[ \det A = \det\begin{bmatrix}2&1\\1&3\end{bmatrix} = 6-1 = 5 \]
STEP 2 · replace column 1 with b
\[ \det A_1 = \det\begin{bmatrix}5&1\\10&3\end{bmatrix} = 15-10 = 5 \ \Longrightarrow\ x = \tfrac55 = 1 \]
STEP 3 · replace column 2 with b
\[ \det A_2 = \det\begin{bmatrix}2&5\\1&10\end{bmatrix} = 20-5 = 15 \ \Longrightarrow\ y = \tfrac{15}{5} = 3 \]
STEP 4 · check
\(2(1)+3 = 5\) ✓ and \(1+9 = 10\) ✓
STEP 5 · why it is impractical
It needs \(n+1\) determinants, and it fails outright when \(\det A = 0\) — exactly the interesting cases. Elimination costs \(O(n^3)\) and handles singular systems gracefully. Cramer's rule remains valuable theoretically, because it shows the solution depends smoothly on the entries — useful in proofs and in sensitivity analysis, not in code.
A permutation matrix has determinant \(\pm1\) according to whether the permutation is even or odd. This example is the reversal permutation on 4 elements, which needs 2 transpositions — even. The full Leibniz formula \(\det A = \sum_\sigma \operatorname{sgn}(\sigma)\prod a_{i\sigma(i)}\) is exactly this idea summed over all \(n!\) permutations, which is why nobody computes it that way.
8
For which \(t\) is \(\begin{bmatrix}t-2&1\\4&t-2\end{bmatrix}\) singular?
Hint 1Set the determinant to zero.
Hint 2This is a characteristic equation in disguise.
STEP 3 · the two roots
\[ t = 4 \quad\text{or}\quad t = 0 \]
STEP 4 · verify t = 0
\[ \begin{bmatrix}-2&1\\4&-2\end{bmatrix} \]
Row 2 is \(-2\times\) row 1 ⟹ singular ✓
STEP 5 · what you actually computed
Write the matrix as \(tI - B\) with \(B = \begin{bmatrix}2&-1\\-4&2\end{bmatrix}\). Then \(\det(tI-B)=0\) is the characteristic equation, and \(t=0,4\) are the eigenvalues of \(B\). Every eigenvalue problem is a singularity question — module E1 makes that the main event.
9
Explain why \(\det(A+B) \ne \det A + \det B\) in general, with an example, and why \(\det(AB)=\det A\det B\) nevertheless holds.
Hint 1Try \(A = B = I\) in \(2\times2\).
Hint 2The determinant is multilinear in the columns, not linear in the matrix.
Solution
STEP 1 · a counterexample
Take \(A=B=I_2\). Then \(\det A + \det B = 1+1 = 2\), but
\[ \det(A+B) = \det(2I) = 4 \]
STEP 2 · why addition fails
The determinant is linear in each column separately, with the others held fixed. Adding two matrices changes every column at once, so multilinearity gives \(2^n\) cross terms rather than two.
STEP 3 · why multiplication works
\(|\det|\) is the volume scale factor. Composing transformations multiplies scale factors: if \(B\) triples volume and \(A\) doubles it, \(AB\) multiplies by 6. There is no corresponding statement for adding transformations, because "sum of two maps" has no volume meaning.
STEP 4 · the algebraic proof sketch
Write \(B\) as a product of elementary matrices and check \(\det(AE)=\det A\det E\) for each type — swaps give \(-1\), scalings give \(c\), additions give 1, matching the row-operation rules exactly.
STEP 5 · the moral
Determinants respect the multiplicative structure of matrices and ignore the additive one. That is why \(\det\) is a group homomorphism \(GL_n(\mathbb R)\to\mathbb R^\times\), and why so many identities involve products, inverses, and powers but never sums.
Part II · Checkpoint Quiz
Quiz B — Matrices, elimination & determinants
Ten questions on transformations, products, rank, inverses, and determinants. Tap an answer to lock it in and see the reasoning. Aim for 8/10 before starting Part III.
Question 1
The columns of \(A\) are:
Why
\(A\mathbf e_j\) picks out column \(j\), which is why \(A\mathbf x\) is the combination of columns weighted by \(\mathbf x\). Independence (C) holds only when the rank equals the number of columns. The columns span the column space, not the null space.
Question 2
If \(A\) is \(2\times3\) and \(B\) is \(3\times4\), then \(BA\) is:
Why
\((3\times4)(2\times3)\) needs the inner dimensions 4 and 2 to match — they don't. \(AB\) is defined and is \(2\times4\), which is choice A: the order matters even for whether the product exists.
Question 3
A row of zeros appearing in the RREF of \(A\) means:
Why
A zero row appears exactly when some row was a combination of the others. Inconsistency (A) requires the augmented column to be nonzero in that row — \((0\ 0\ 0\mid 0)\) is harmless, \((0\ 0\ 0\mid 5)\) is fatal. Fewer pivots means more free variables, not fewer.
Question 4
\(A\mathbf x=\mathbf b\) is consistent if and only if:
Why
Equal ranks means \(\mathbf b\) added no new direction — it already lay in the column space. Choice C guarantees a unique solution but is far stronger than necessary; plenty of singular systems are consistent, with infinitely many solutions.
Question 5
\((AB)^{-1}\) equals:
Why
Undoing a composition reverses the order — socks then shoes, shoes off then socks off. Check: \((AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = I\) ✓ The same reversal governs transposes.
Question 6
\(|\det A|\) measures:
Why
The unit cube maps to a parallelepiped of volume \(|\det A|\), and every region scales by the same factor. The sign records orientation. Choice B is the trace; the determinant is the product of the eigenvalues.
Question 7
Which row operation changes the determinant?
Why
Scaling a row by 3 multiplies the determinant by 3. Adding a multiple of another row leaves it unchanged — which is what makes elimination a valid way to compute determinants. Transposing never changes it. A row swap flips the sign.
Question 8
A \(4\times4\) matrix with \(\operatorname{rank} = 3\) has:
Why
Rank–nullity gives nullity \(= 4-3 = 1\). Any square matrix short of full rank is singular, so the determinant is 0 and there are only 3 pivots. Every other choice describes the full-rank case.
Question 9
In \(A = LU\), the entries of \(L\) below the diagonal are:
Why
\(L\) records the elimination: if you used \(R_3\to R_3-2R_1\), then \(\ell_{31}=2\). No computation is needed — you copy the multipliers into place. The pivots live on \(U\)'s diagonal, and their product is \(\det A\).
Question 10
To solve \(A\mathbf x=\mathbf b\) numerically, the recommended approach is:
Why
Elimination costs \(\approx n^3/3\) operations and is backward stable. Explicit inversion costs about three times more and amplifies round-off; Cramer's rule needs \(n+1\) determinants and fails at \(\det A=0\); cofactor expansion is \(O(n!)\). Write A\b, never inv(A)*b.
Parts III & IV · Final checkpoint Quiz
Quiz C — Subspaces, orthogonality & eigenvalues
Ten questions spanning the four fundamental subspaces, projection, diagonalization, and the SVD. This is the final checkpoint — aim for 8/10.
Question 1
Rank–nullity states that \(\operatorname{rank}(A) + \dim\operatorname{null}(A)\) equals:
Why
Columns — because each column either carries a pivot (contributing to rank) or is free (contributing to nullity). The \(m-r\) count on the row side describes the left null space instead. Mixing up rows and columns here is the single most common error in the topic.
Question 2
The null space of \(A\) is orthogonal to:
Why
\(A\mathbf x=\mathbf 0\) says every row dotted with \(\mathbf x\) is zero — that is orthogonality to the row space. Both live in \(\mathbb R^n\) and their dimensions add to \(n\), so they are orthogonal complements. The column space lives in \(\mathbb R^m\); its complement is the left null space.
Question 3
If \(Q\) has orthonormal columns and is square, then \(Q^{-1}\) is:
Why
Orthonormal columns mean \(Q^{T}Q = I\) by construction, since entry \((i,j)\) is \(\mathbf q_i\cdot\mathbf q_j\). For a square \(Q\) that makes \(Q^{T}\) the two-sided inverse — the cheapest inverse in the subject, and the reason orthogonal matrices are used wherever numerical stability matters.
Question 4
The least-squares solution of \(A\mathbf x=\mathbf b\) satisfies:
Why
The normal equations. They come from requiring the error \(\mathbf b - A\hat{\mathbf x}\) to be orthogonal to every column of \(A\), i.e. \(A^{T}(\mathbf b - A\hat{\mathbf x}) = \mathbf 0\). Choice A is what you would like but generally cannot have — which is the whole reason least squares exists.
Question 5
A projection matrix \(P\) always satisfies:
Why
Projecting something that is already in the subspace changes nothing, so \(P^2=P\). Its eigenvalues are therefore only 0 and 1, and unless \(P=I\) it is singular — it destroys the orthogonal complement. Choice B describes a reflection.
Question 6
\(A\mathbf v = \lambda\mathbf v\) with \(\mathbf v \ne \mathbf 0\) implies:
Why
Rewriting gives \((A-\lambda I)\mathbf v=\mathbf 0\) with \(\mathbf v\ne\mathbf 0\), so \(A-\lambda I\) has a nontrivial null space — singular, hence \(\det(A-\lambda I)=0\). That determinant equation is how eigenvalues are found. \(\lambda=0\) is perfectly allowed, and means \(A\) itself is singular.
Question 7
A real symmetric matrix is guaranteed to have:
Why
The spectral theorem: \(A = Q\Lambda Q^{T}\), always. The eigenvalues are real but may be negative or zero (positivity is the extra condition of positive definiteness), and they may repeat — but even then an orthonormal eigenbasis exists, so symmetric matrices are never defective.
Question 8
\(A\) is diagonalizable if and only if:
Why
An eigenbasis is exactly what \(P\) needs to be invertible in \(A = P\Lambda P^{-1}\). Distinct eigenvalues (B) and symmetry (C) each guarantee this but are not required — \(I\) has one repeated eigenvalue and is already diagonal. Invertibility is unrelated: \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\) is invertible but defective.
Question 9
Which matrices have a singular value decomposition?
Why
The SVD is built from \(A^{T}A\), which is symmetric positive semidefinite for every \(A\) — so the spectral theorem supplies \(V\) and the \(\sigma_i\) unconditionally. That universality is exactly what the eigendecomposition lacks, since it demands one basis to serve as both input and output frame.
Question 10
For a regular Markov chain, the long-run distribution is:
Why
Expand the start in the eigenbasis: the \(\lambda=1\) component survives while every other \(|\lambda|<1\) term decays, so the limit is the same regardless of where you began. It is uniform only in special cases. This is precisely how PageRank ranks the web.
Part III · Module 1 Spaces & orthogonality
Column space, null space & rank
Every matrix carries four subspaces, and one equation ties them together. Rank–nullity is the conservation law of linear algebra: whatever a transformation loses on the way out, it destroys on the way in.
①The four fundamental subspaces
Subspace
Definition
Lives in
Dimension
Column space \(\operatorname{col}(A)\)
span of the columns = all \(A\mathbf x\)
\(\mathbb R^m\)
\(r\)
Null space \(\operatorname{null}(A)\)
all \(\mathbf x\) with \(A\mathbf x=\mathbf 0\)
\(\mathbb R^n\)
\(n-r\)
Row space \(\operatorname{row}(A)\)
span of the rows = \(\operatorname{col}(A^{T})\)
\(\mathbb R^n\)
\(r\)
Left null space
all \(\mathbf y\) with \(A^{T}\mathbf y=\mathbf 0\)
\(\mathbb R^m\)
\(m-r\)
Rank–nullity
\[ \operatorname{rank}(A) + \dim\operatorname{null}(A) = n \quad(\text{number of \emph{columns}}) \]
And the fact that surprises everyone the first time: row rank equals column rank. The rows and the columns of any matrix, however lopsided its shape, span spaces of the same dimension.
Finding bases from the RREF
\[ \operatorname{col}(A): \text{ pivot columns of the \emph{original} } A; \qquad \operatorname{row}(A): \text{ nonzero rows of RREF}; \qquad \operatorname{null}(A): \text{ special solutions} \]
InteractiveThe four subspaces of a 2×2 matrixwatch rank drop
rank —nullity —rank + nullity —
With the default entries the matrix is nearly singular. Nudge \(d\) until \(ad = bc\): the column space collapses from the whole plane to a line, and at that same instant a null-space line appears — the two dimensions trade one-for-one, which is rank–nullity in motion. Switch views and notice the null space is always perpendicular to the row space. That orthogonality is not a coincidence: \(A\mathbf x=\mathbf 0\) says exactly that \(\mathbf x\) is orthogonal to every row.
Worked example · all four subspaces
For \(A = \begin{bmatrix}1&2&3\\2&4&8\end{bmatrix}\), find bases for the column space, null space, and row space.
Check the arithmetic: \(r + (n-r) = 2 + 1 = 3 = n\) ✓ The left null space has dimension \(m-r = 2-2 = 0\), so it is just \(\{\mathbf 0\}\) — meaning \(A\mathbf x=\mathbf b\) is solvable for every \(\mathbf b\). Note the null-space vector is orthogonal to both row-space basis vectors: \((-2,1,0)\cdot(1,2,0) = 0\) ✓
②Practice
1
Find the rank and nullity of \(\begin{bmatrix}1&2\\2&4\end{bmatrix}\), and bases for its column and null spaces.
Hint 1The second column is a multiple of the first.
The row space is spanned by \((1,2)\), and \((1,2)\cdot(-2,1) = 0\) ✓ The null space is exactly the orthogonal complement of the row space — always true, and the key to module S4.
2
A \(4\times7\) matrix has rank 3. Find the dimensions of all four fundamental subspaces.
Hint 1Column and row spaces both have dimension \(r\).
Hint 2Nullity is \(n-r\); left nullity is \(m-r\).
STEP 4 · left null space
\[ \dim\operatorname{null}(A^{T}) = 4 - 3 = 1 \subset\mathbb R^4 \]
STEP 5 · check the two pairings
In \(\mathbb R^7\): \(3 + 4 = 7\) ✓ In \(\mathbb R^4\): \(3 + 1 = 4\) ✓ Each space splits into a subspace and its orthogonal complement. The 1-dimensional left null space means there is exactly one linear relation among the rows, and exactly one linear constraint that \(\mathbf b\) must satisfy for solvability.
3
Find a basis for the null space of \(\begin{bmatrix}1&2&0&3\\0&0&1&4\end{bmatrix}\).
Hint 1It is already in RREF — identify pivot and free columns.
Hint 2Set each free variable to 1 in turn, the others to 0.
Solution
STEP 1 · identify variables
Pivots in columns 1 and 3; free variables \(x_2\) and \(x_4\). Nullity \(= 4-2 = 2\).
STEP 5 · state the basis and check
\[ \operatorname{null}(A) = \operatorname{span}\{(-2,1,0,0),\ (-3,0,-4,1)\} \]
Both are killed by \(A\) ✓ and they are independent because of the 1 and 0 pattern in the free positions — that pattern is why special solutions are automatically a basis.
4
Why does row rank equal column rank?
Hint 1Count pivots in the RREF.
Hint 2Each pivot contributes one basis vector to each space.
Solution
STEP 1 · row rank from the RREF
Row operations do not change the row space, and the nonzero rows of the RREF are independent (each has a leading 1 where the others are 0). So the row rank equals the number of pivots.
STEP 2 · column rank from the RREF
Row operations do not change dependence relations among the columns. In the RREF, the pivot columns are distinct standard basis vectors — independent — and every free column is a combination of earlier pivot columns.
STEP 3 · so column rank also counts pivots
The pivot columns of the original \(A\) therefore form a basis of \(\operatorname{col}(A)\), and there are as many as there are pivots.
STEP 4 · conclude
Both ranks equal the pivot count, hence each other ∎
STEP 5 · why it is remarkable
A \(3\times1000\) matrix has 1000 columns in \(\mathbb R^3\) and 3 rows in \(\mathbb R^{1000}\) — utterly different-looking sets, yet their spans have identical dimension (at most 3). The deeper reason appears in the SVD (module E4): \(A\) and \(A^{T}\) have the same nonzero singular values.
5
Is \(\mathbf b = (1,2,3)\) in the column space of \(A = \begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}\)?
Hint 1Ask whether \(A\mathbf x=\mathbf b\) is consistent.
"Is \(\mathbf b\) in the column space?" and "is \(A\mathbf x=\mathbf b\) solvable?" are the same question. The column space is a plane in \(\mathbb R^3\) here, so most \(\mathbf b\) would fail — \((1,2,4)\), for instance, gives \(0=1\) in the last row.
6
If \(\operatorname{null}(A) = \{\mathbf 0\}\) for an \(m\times n\) matrix, what can you say about the columns and about \(n\) versus \(m\)?
Hint 1Nullity 0 means no free variables.
Hint 2Rank can never exceed the number of rows.
Solution
STEP 1 · translate the hypothesis
\(\dim\operatorname{null}(A) = 0\), so by rank–nullity \(\operatorname{rank}(A) = n\) — full column rank.
STEP 2 · the columns
\(A\mathbf x=\mathbf 0\) only for \(\mathbf x=\mathbf 0\) is precisely the definition of independent columns.
STEP 3 · the shape constraint
Rank is at most \(\min(m,n)\), so \(n = r \le m\):
\[ n \le m \]
The matrix must be square or tall.
STEP 4 · the map view
\(T(\mathbf x)=A\mathbf x\) is one-to-one: distinct inputs give distinct outputs, since \(A\mathbf u = A\mathbf v\) forces \(\mathbf u-\mathbf v\in\operatorname{null}(A) = \{\mathbf 0\}\).
STEP 5 · the consequence
Full column rank guarantees \(A^{T}A\) is invertible, which is exactly the condition for the least-squares normal equations to have a unique solution (module S5). It also means \(A\) has a left inverse, \((A^{T}A)^{-1}A^{T}\), even when it has no true inverse.
7
Show that \(\operatorname{null}(A)\) is orthogonal to \(\operatorname{row}(A)\).
Hint 1Write out what \(A\mathbf x = \mathbf 0\) says row by row.
Hint 2Then extend from single rows to combinations of rows.
Solution
STEP 1 · unpack the equation
Let \(\mathbf x\in\operatorname{null}(A)\). Entry \(i\) of \(A\mathbf x\) is (row \(i\))·\(\mathbf x\), and all entries are zero:
\[ \mathbf r_i\cdot\mathbf x = 0 \quad\text{for every row } \mathbf r_i \]
STEP 2 · extend to combinations
For any \(\mathbf y = \sum c_i\mathbf r_i\) in the row space,
Every null-space vector is orthogonal to every row-space vector ∎
STEP 4 · the dimensions match up
\(\dim\operatorname{row} + \dim\operatorname{null} = r + (n-r) = n\), so they are not merely orthogonal — they are orthogonal complements filling \(\mathbb R^n\) between them.
STEP 5 · the same on the other side
Applying the result to \(A^{T}\) gives \(\operatorname{col}(A)\perp\operatorname{null}(A^{T})\) in \(\mathbb R^m\). These two orthogonal splittings are Strang's "big picture": \(\mathbb R^n = \operatorname{row}\oplus\operatorname{null}\) and \(\mathbb R^m = \operatorname{col}\oplus\operatorname{left null}\), with \(A\) mapping the row space one-to-one onto the column space.
8
Find bases for all four subspaces of \(A = \begin{bmatrix}1&3\\2&6\\3&9\end{bmatrix}\).
Hint 1Every column is a multiple of \((1,2,3)\) — the rank is 1.
Hint 2For the left null space, solve \(A^{T}\mathbf y=\mathbf 0\).
Solution
STEP 1 · rank
Column 2 is \(3\times\) column 1, so \(r = 1\). Here \(m=3\), \(n=2\).
STEP 2 · column space and null space
\[ \operatorname{col}(A) = \operatorname{span}\{(1,2,3)\}, \qquad \operatorname{null}(A) = \operatorname{span}\{(-3,1)\} \]
since \(x_1 + 3x_2 = 0\) gives \(x_1 = -3x_2\). Dimensions \(1\) and \(2-1=1\) ✓
\(A\) maps a line in \(\mathbb R^2\) (the row space) onto a line in \(\mathbb R^3\) (the column space), killing one direction and reaching only a 1-dimensional sliver of \(\mathbb R^3\). Both left-null basis vectors are perpendicular to \((1,2,3)\) ✓ — they are the plane of \(\mathbf b\)-constraints that make \(A\mathbf x=\mathbf b\) unsolvable.
9
Prove that \(\operatorname{rank}(AB) \le \min\{\operatorname{rank}(A), \operatorname{rank}(B)\}\).
Hint 1Every column of \(AB\) is \(A\) applied to a column of \(B\).
Hint 2For the other bound, think about the rows, or about the null space.
Solution
STEP 1 · bound by rank A
Column \(j\) of \(AB\) is \(A\mathbf b_j\), which lies in \(\operatorname{col}(A)\). So
Composition can only lose information. If \(B\) flattens space to a line, nothing \(A\) does afterwards can restore the lost dimension.
STEP 5 · consequences
A product of a tall and a wide matrix is rank-deficient whenever the shared inner dimension is small — the basis of low-rank approximation and matrix factorization in machine learning. And if either factor is singular, so is the product: \(\det(AB) = \det A\det B\) says the same thing numerically. The inequality can be strict: two nonzero rank-1 matrices can multiply to zero (module M2 problem 7).
Part III · Module 2 Spaces & orthogonality
Coordinates & change of basis
A vector is not a list of numbers — it acquires a list once you choose a basis. Changing basis changes every number without moving anything, and choosing the right basis is how hard problems become easy.
Independence guarantees the \(c_i\) are unique, so \([\mathbf x]_{\mathcal B}\) is well defined. Let \(P = [\mathbf v_1\ \cdots\ \mathbf v_n]\) be the matrix whose columns are the basis vectors. Then:
Both directions
\[ \mathbf x = P\,[\mathbf x]_{\mathcal B}, \qquad [\mathbf x]_{\mathcal B} = P^{-1}\mathbf x \]
Read \(P\) as "\(\mathcal B\)-coordinates in, standard coordinates out." The direction that surprises people: to find coordinates you apply \(P^{-1}\), not \(P\).
A matrix in a new basis
\[ [T]_{\mathcal B} = P^{-1}AP \]
Read right to left: convert \(\mathcal B\)-coordinates to standard, apply \(A\), convert back. Matrices related this way are called similar; they are the same transformation described by different observers.
InteractiveSame arrow, different numberstilt the basis, watch the coordinates
standard coords —B-coords —P —
The amber arrow never moves. What moves is the grid you measure it against — and with it, both readouts. When the basis is orthonormal the two coordinate systems differ only by a rotation; stretch the basis and the \(\mathcal B\)-grid becomes skewed, so equal coordinate steps no longer mean equal distances. That is why orthonormal bases are worth the trouble: they preserve lengths and angles, so \(P^{-1} = P^{T}\) (module S4).
Worked example · coordinates and a similar matrix
With \(\mathcal B = \left\{\begin{bmatrix}1\\1\end{bmatrix},\begin{bmatrix}1\\-1\end{bmatrix}\right\}\), find \([\mathbf x]_{\mathcal B}\) for \(\mathbf x = (4,2)\), and express \(A = \begin{bmatrix}3&1\\1&3\end{bmatrix}\) in this basis.
STEP 1
Build \(P\) and invert it:
\[ P = \begin{bmatrix}1&1\\1&-1\end{bmatrix}, \quad \det P = -2, \quad P^{-1} = \tfrac12\begin{bmatrix}1&1\\1&-1\end{bmatrix} \]
The matrix became diagonal. That is not luck: \((1,1)\) and \((1,-1)\) are eigenvectors of \(A\) with eigenvalues 4 and 2. Note that \(\operatorname{tr} = 6\) and \(\det = 8\) in both bases — similar matrices share those invariants, because they describe the same transformation.
②Practice
1
Find \([\mathbf x]_{\mathcal B}\) for \(\mathbf x = (7,3)\) and \(\mathcal B = \{(1,0),(1,1)\}\).
Hint 1Solve \(c_1(1,0)+c_2(1,1) = (7,3)\).
Hint 2The second coordinate determines \(c_2\) immediately.
Going from \(\mathcal B\)-coordinates to standard is just a matrix–vector product. The reverse direction is the one that costs an inverse or a solve.
STEP 5 · the mnemonic
\(P\)'s columns are the \(\mathcal B\)-vectors written in standard coordinates, so \(P\) consumes \(\mathcal B\)-coordinates and produces standard ones. Match the labels like units and the direction is never ambiguous.
3
Find the change-of-basis matrix from \(\mathcal B = \{(1,1),(1,-1)\}\) to \(\mathcal C = \{(1,0),(0,1)\}\), and its inverse.
Hint 1\(\mathcal C\) is the standard basis, so \(P\) is just the \(\mathcal B\) vectors as columns.
The columns of \(P\) are orthogonal with length \(\sqrt2\) each. Dividing by \(\sqrt2\) makes \(P\) orthonormal, and then \(P^{-1} = P^{T}\) exactly. This particular matrix is the \(2\times2\) Hadamard/Haar transform — the smallest wavelet, splitting a signal into its average and its difference.
4
Show that similar matrices \(B = P^{-1}AP\) have the same determinant and trace.
Hint 1Determinants multiply.
Hint 2For the trace, use \(\operatorname{tr}(XY) = \operatorname{tr}(YX)\).
Solution
STEP 1 · determinant
\[ \det B = \det(P^{-1})\det(A)\det(P) = \frac{1}{\det P}\det A\,\det P = \det A \ ✓ \]
STEP 2 · the trace identity
\(\operatorname{tr}(XY) = \sum_i\sum_j x_{ij}y_{ji} = \operatorname{tr}(YX)\) — the double sum is symmetric under swapping the roles.
Rank, eigenvalues, characteristic polynomial, and invertibility — everything that describes the transformation rather than the coordinate system.
STEP 5 · how to use it
These invariants are quick sanity checks. If you diagonalize a matrix and the diagonal entries do not sum to the original trace or multiply to the original determinant, you have made an arithmetic error. For \(2\times2\), trace and determinant alone determine the eigenvalues: \(\lambda^2 - (\operatorname{tr})\lambda + \det = 0\).
5
Let \(T\) be reflection across the line \(y=x\). Find its matrix in the standard basis and in \(\mathcal B = \{(1,1),(1,-1)\}\).
Hint 1In the standard basis it swaps coordinates.
Hint 2What does \(T\) do to each \(\mathcal B\)-vector? Read the answer off directly.
Solution
STEP 1 · standard basis
\[ A = \begin{bmatrix}0&1\\1&0\end{bmatrix} \]
STEP 2 · act on the B-vectors
\((1,1)\) lies on the mirror line, so it is fixed: \(T(1,1) = (1,1)\). And \((1,-1)\) is perpendicular to the mirror, so it flips: \(T(1,-1) = (-1,1) = -(1,-1)\).
STEP 3 · read the matrix off
In \(\mathcal B\)-coordinates the images are \((1,0)\) and \((0,-1)\):
STEP 4 · confirm via P⁻¹AP
\[ AP = \begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\1&-1\end{bmatrix} = \begin{bmatrix}1&-1\\1&1\end{bmatrix}, \quad P^{-1}(AP) = \tfrac12\begin{bmatrix}2&0\\0&-2\end{bmatrix} = \begin{bmatrix}1&0\\0&-1\end{bmatrix} ✓ \]
STEP 5 · the lesson
Adapting the basis to the geometry turns an off-diagonal matrix into a diagonal one, and the diagonal entries \(+1, -1\) state the geometry outright: one direction fixed, one direction flipped. Invariants agree: trace 0, determinant \(-1\) in both bases ✓
6
Find the coordinates of \(1 + 2t + 3t^2\) in the basis \(\{1,\ t-1,\ (t-1)^2\}\) of polynomials of degree \(\le2\).
Hint 1Substitute \(s = t-1\), i.e. \(t = s+1\), and expand.
A Taylor expansion is a change of basis in the space of polynomials, from \(\{1,t,t^2\}\) centred at 0 to \(\{1,(t-a),(t-a)^2\}\) centred at \(a\). The polynomial never changed — only the ruler did, exactly as with arrows in \(\mathbb R^2\). The Calculus Toolkit's series modules are the analytic face of this same idea.
7
If \(P\) is the change-of-basis matrix from \(\mathcal B\) to \(\mathcal C\), what converts \(\mathcal C\)-coordinates to \(\mathcal B\)-coordinates? What if you chain three bases?
The inner labels \(\mathcal C\) cancel, leaving \(\mathcal B\to\mathcal D\) ✓ Write the labels every time and you will never get the order backwards.
STEP 5 · a practical route
To convert between two non-standard bases, go through the standard one: \(P_{\mathcal B\to\mathcal C} = P_{\mathcal C}^{-1}P_{\mathcal B}\), where each \(P\) lists its basis vectors as columns in standard coordinates. Two easy matrices instead of one hard one.
8
Compute \([T]_{\mathcal B}\) for \(A = \begin{bmatrix}2&1\\0&3\end{bmatrix}\) and \(\mathcal B = \{(1,0),(1,1)\}\).
Hint 1Compute \(P^{-1}AP\).
Hint 2Or find \(A\mathbf v_1\) and \(A\mathbf v_2\) and express each in \(\mathcal B\)-coordinates.
Solution
STEP 1 · set up P and its inverse
\[ P = \begin{bmatrix}1&1\\0&1\end{bmatrix}, \qquad P^{-1} = \begin{bmatrix}1&-1\\0&1\end{bmatrix} \]
STEP 2 · compute AP
\[ AP = \begin{bmatrix}2&1\\0&3\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix} = \begin{bmatrix}2&3\\0&3\end{bmatrix} \]
\(A(1,0) = (2,0) = 2(1,0)\), so the first \(\mathcal B\)-column is \((2,0)\). \(A(1,1) = (3,3) = 3(1,1)\), so the second is \((0,3)\) ✓
STEP 5 · why it diagonalized
\((1,0)\) and \((1,1)\) are eigenvectors of \(A\) with eigenvalues 2 and 3 — the diagonal entries. Trace \(5\) and determinant \(6\) match the original ✓ Finding a basis that diagonalizes a matrix is the eigenvalue problem, and module E2 makes that systematic.
9
Why would anyone bother changing basis? Give three concrete payoffs.
Hint 1Think about what a diagonal matrix makes easy.
Hint 2Think about data compression and about coupled differential equations.
Solution
STEP 1 · powers and exponentials become trivial
If \(A = P\Lambda P^{-1}\) then \(A^{n} = P\Lambda^{n}P^{-1}\), and \(\Lambda^n\) just raises the diagonal entries. Computing \(A^{100}\) goes from 99 matrix multiplications to a handful of scalar powers.
STEP 2 · coupled systems decouple
In the eigenbasis, \(\mathbf x' = A\mathbf x\) becomes \(n\) independent scalar equations \(y_i' = \lambda_iy_i\), each solved by \(e^{\lambda_it}\). That is exactly how systems of ODEs are solved (module E5) and how normal modes of a vibrating structure are found.
STEP 3 · the right basis reveals structure in data
Principal component analysis rotates to the basis where the covariance matrix is diagonal; the first few coordinates then capture most of the variance, so discarding the rest compresses with minimal loss. JPEG does the same with a cosine basis, MP3 with a frequency basis.
STEP 4 · numerical conditioning
A well-chosen basis can turn an ill-conditioned problem into a stable one — the reason orthogonal bases (module S4) are preferred throughout numerical linear algebra.
STEP 5 · the unifying idea
The transformation is fixed; only its description changes. Solving hard problems often means asking "in which coordinates is this easy?" — Fourier series answer that for PDEs (the PDE Launchpad), eigenbases answer it for matrices, and both are the same move.
Part III · Module 3 Spaces & orthogonality
Linear transformations
Strip away the coordinates and what remains is a map that respects addition and scaling. Kernel and image are its null space and column space, seen without a matrix in the way.
Both conditions in one: \(T(a\mathbf u + b\mathbf v) = aT(\mathbf u)+bT(\mathbf v)\). An immediate consequence is \(T(\mathbf 0)=\mathbf 0\) — the fastest disqualifier.
Term
Definition
Matrix name
Kernel \(\ker T\)
\(\{\mathbf x : T(\mathbf x)=\mathbf 0\}\)
null space
Image \(\operatorname{im}T\)
\(\{T(\mathbf x)\}\)
column space
Injective (one-to-one)
\(\ker T = \{\mathbf 0\}\)
full column rank
Surjective (onto)
\(\operatorname{im}T = W\)
full row rank
Isomorphism
both
invertible
Not all linear transformations are matrices of numbers acting on arrows. Differentiation \(D(f)=f'\), integration, and multiplication by a fixed function are all linear — and on finite-dimensional spaces of polynomials they have honest matrices.
InteractiveA zoo of transformationspick one; watch what it preserves and destroys
matrix —kernel —image —injective / surjective —
Every transformation here sends the origin to the origin and straight lines to straight lines — that is all "linear" requires. What varies is what survives: rotations and reflections preserve length; shears preserve area but not length; the projection destroys a whole dimension, and its kernel (highlighted) is the line that collapses. Notice that for these square maps, a nontrivial kernel always comes with a shrunken image — you cannot lose injectivity without also losing surjectivity.
Worked example · differentiation as a matrix
Find the matrix of \(D(p) = p'\) on \(P_2 = \{a+bt+ct^2\}\) with basis \(\{1,t,t^2\}\), and describe its kernel and image.
STEP 1
Apply \(D\) to each basis element: \(D(1) = 0\), \(D(t) = 1\), \(D(t^2) = 2t\).
STEP 2
Write each image in coordinates: \(0 \to (0,0,0)\), \(1\to(1,0,0)\), \(2t\to(0,2,0)\).
Kernel: the first column is zero, so \(\ker D = \operatorname{span}\{1\}\) — the constants, dimension 1. That is the "+C" of integration.
STEP 5
Image: columns 2 and 3 span \(\operatorname{span}\{1,t\} = P_1\), dimension 2. Check: \(2 + 1 = 3 = \dim P_2\) ✓ Note \([D]^3 = 0\) — differentiate a quadratic three times and you always get zero, so \(D\) is nilpotent, with every eigenvalue 0.
It does send \(\mathbf 0\) to \(\mathbf 0\), so the origin test alone is not enough here — squaring breaks scaling while preserving the origin.
STEP 5 · the general test
Linear maps have every output coordinate a first-degree homogeneous expression in the inputs: sums of constants times variables. Squares, products of variables, absolute values, and additive constants all disqualify.
2
Find the kernel and image of \(T(x,y,z) = (x+y, y+z)\).
Hint 1Write the matrix and solve \(A\mathbf x=\mathbf 0\).
Hint 2The image is the span of the columns.
Solution
STEP 1 · write the matrix
\[ A = \begin{bmatrix}1&1&0\\0&1&1\end{bmatrix} \]
STEP 2 · solve for the kernel
\(x+y=0\) and \(y+z=0\), so \(y = -x\) and \(z = -y = x\). With \(x=t\):
\[ \ker T = \operatorname{span}\{(1,-1,1)\} \]
STEP 3 · the image
The columns \((1,0)\), \((1,1)\), \((0,1)\) already include two independent vectors, so
Surjective (the image is all of \(\mathbb R^2\)) but not injective (nontrivial kernel). Any map \(\mathbb R^3\to\mathbb R^2\) must lose at least one dimension — you cannot squeeze three independent directions into two without collapse.
3
Prove that \(T\) is injective if and only if \(\ker T = \{\mathbf 0\}\).
Hint 1Suppose \(T(\mathbf u)=T(\mathbf v)\) and subtract.
Hint 2For the converse, use that \(T(\mathbf 0)=\mathbf 0\).
Solution
STEP 1 · (⟸) assume trivial kernel
If \(T(\mathbf u)=T(\mathbf v)\), then by linearity \(T(\mathbf u-\mathbf v)=\mathbf 0\), so \(\mathbf u-\mathbf v\in\ker T = \{\mathbf 0\}\).
STEP 2 · conclude injectivity
\(\mathbf u-\mathbf v = \mathbf 0\), i.e. \(\mathbf u=\mathbf v\) ✓
STEP 3 · (⟹) assume injective
\(T(\mathbf 0) = \mathbf 0\) always. If some \(\mathbf x\ne\mathbf 0\) had \(T(\mathbf x)=\mathbf 0\), then \(\mathbf x\) and \(\mathbf 0\) would be two distinct inputs with the same output, contradicting injectivity.
STEP 4 · conclude
So \(\ker T=\{\mathbf 0\}\) ∎
STEP 5 · why linearity makes this work
For a general function, injectivity must be checked at every pair of points. Linearity concentrates all the information at a single point — the kernel — because the map's behaviour everywhere is a translated copy of its behaviour at \(\mathbf 0\). That reduction is what makes linear algebra tractable.
4
Find the matrix of \(T(p) = p'' + p\) on \(P_2\) with basis \(\{1,t,t^2\}\).
Hint 1Apply \(T\) to each basis polynomial.
Hint 2Express each image in coordinates and stack as columns.
Solution
STEP 1 · apply T to each basis element
\[ T(1) = 0 + 1 = 1, \qquad T(t) = 0 + t = t, \qquad T(t^2) = 2 + t^2 \]
STEP 2 · coordinates of each image
\[ 1\to(1,0,0), \qquad t\to(0,1,0), \qquad 2+t^2\to(2,0,1) \]
Upper triangular with determinant 1, so \(T\) is invertible: \(\ker T = \{0\}\) and \(\operatorname{im}T = P_2\).
STEP 5 · what invertibility means here
The ODE \(p''+p = q\) has a unique polynomial solution for every polynomial \(q\) of degree \(\le2\). Inverting gives \([T]^{-1} = \begin{bmatrix}1&0&-2\\0&1&0\\0&0&1\end{bmatrix}\), so for \(q = t^2\) the solution is \(p = t^2 - 2\). Check: \(p'' + p = 2 + t^2 - 2 = t^2\) ✓ Differential operators become matrices whenever you restrict to a finite-dimensional space of functions — the idea behind spectral methods for PDEs.
5
Can a linear map \(\mathbb R^3\to\mathbb R^2\) be injective? Can \(\mathbb R^2\to\mathbb R^3\) be surjective?
Hint 1Use rank–nullity in each case.
Hint 2Rank cannot exceed either dimension.
Solution
STEP 1 · ℝ³ → ℝ²
The rank is at most 2 (the image sits in \(\mathbb R^2\)), so
\[ \dim\ker = 3 - r \ge 3 - 2 = 1 \]
STEP 2 · conclude
The kernel is never trivial ⟹ never injective.
STEP 3 · ℝ² → ℝ³
The rank is at most 2 (only 2 columns), so the image has dimension at most 2 inside a 3-dimensional space.
STEP 4 · conclude
The image is a proper subspace ⟹ never surjective.
STEP 5 · the general statement
Injective requires \(n\le m\); surjective requires \(n\ge m\); both (an isomorphism) requires \(n=m\). Vector spaces of different finite dimensions are never isomorphic — dimension is a complete invariant, which is why every \(n\)-dimensional real vector space is "the same as" \(\mathbb R^n\).
6
\(T\) rotates \(\mathbb R^2\) by \(45^\circ\) then projects onto the \(x\)-axis. Find its matrix, kernel, and image.
Hint 1Compose in the right order: rotation first means it is the right-hand factor.
Hint 2The kernel is what rotates onto the \(y\)-axis.
Solution
STEP 1 · the two factors
\[ R = \frac{\sqrt2}{2}\begin{bmatrix}1&-1\\1&1\end{bmatrix}, \qquad P = \begin{bmatrix}1&0\\0&0\end{bmatrix} \]
Projecting first and then rotating gives \(RP = \frac{\sqrt2}{2}\begin{bmatrix}1&0\\1&0\end{bmatrix}\) — same rank, but a different kernel (the \(y\)-axis) and a different image (the line \(y=x\)). Composition is not commutative, and the geometry shows exactly why.
7
Show that \(\ker T\) is a subspace of the domain and \(\operatorname{im}T\) a subspace of the codomain.
Hint 1Check the three conditions for each, using linearity.
Solution
STEP 1 · kernel contains 0
\(T(\mathbf 0)=\mathbf 0\), so \(\mathbf 0\in\ker T\) ✓
Each uses only \(T(a\mathbf u+b\mathbf v) = aT(\mathbf u)+bT(\mathbf v)\), applied once forwards and once backwards. Linear maps automatically produce subspaces — which is why solution sets of homogeneous systems, column spaces, and eigenspaces are all subspaces without needing separate arguments.
8
The map \(S(p) = \int_0^{t} p(s)\,ds\) sends \(P_2\to P_3\). Find its matrix and describe its kernel.
Hint 1Integrate each basis polynomial.
Hint 2The domain has dimension 3, the codomain 4 — so the matrix is \(4\times3\).
The three columns are independent, so \(\operatorname{rank}=3\) and
\[ \ker S = \{0\} \]
— only the zero polynomial integrates to zero, since the definite integral from 0 pins down the constant.
STEP 5 · the relationship with D
\(D\circ S = I\) on \(P_2\): differentiating an antiderivative returns the original. But \(S\circ D \ne I\) on \(P_3\), because \(S(D(p)) = p - p(0)\) loses the constant. \(S\) is a right inverse of \(D\), not a two-sided one — the asymmetry is exactly the "+C" and the reason \(D\) has a kernel while \(S\) does not.
9
Explain why every \(n\)-dimensional real vector space is isomorphic to \(\mathbb R^n\), and why that does not make abstract vector spaces pointless.
Hint 1Choose a basis and use the coordinate map.
Hint 2For the second half, ask what the isomorphism depends on.
Solution
STEP 1 · build the map
Fix a basis \(\mathcal B = \{\mathbf v_1,\dots,\mathbf v_n\}\) and define \(\Phi(\mathbf x) = [\mathbf x]_{\mathcal B}\).
STEP 2 · it is linear
Coordinates of a sum are the sum of coordinates, and scaling scales them — immediate from uniqueness of the expansion.
STEP 3 · it is bijective
Injective because independence makes the expansion unique; surjective because every coefficient list \((c_1,\dots,c_n)\) produces the vector \(\sum c_i\mathbf v_i\). So \(V\cong\mathbb R^n\) ∎
STEP 4 · why abstraction still matters
The isomorphism depends on the choice of basis, and there is no canonical choice. Statements proved abstractly hold in every basis; statements proved in coordinates must be checked for basis-independence.
STEP 5 · the practical payoff
Function spaces are often infinite-dimensional, where no such isomorphism exists and the abstract definitions are all you have — Fourier series, Sturm–Liouville eigenfunctions, and quantum states all live there. The abstract framework also transfers instantly: once you know polynomials, matrices, and solution spaces of ODEs are vector spaces, every theorem here applies to them without reproof.
Part III · Module 4 Spaces & orthogonality
Orthogonality & Gram–Schmidt
Perpendicular bases are the ones worth having. Coordinates become dot products, inverses become transposes, and round-off stops accumulating. Gram–Schmidt manufactures such a basis from any basis at all.
Each step removes the components already accounted for, leaving only what is genuinely new. Collecting the results gives the QR factorization \(A = QR\), with \(R\) upper triangular — the numerically preferred route to least squares.
InteractiveStraightening a skewed basisstep through the projections
stage —w₂ = v₂ − proj —q₁·q₂ —
Step 1 keeps \(\mathbf v_1\) unchanged. Step 2 draws the projection of \(\mathbf v_2\) onto it — the part that is redundant — and step 3 subtracts that projection, leaving \(\mathbf w_2\) standing exactly perpendicular. The readout confirms \(\mathbf q_1\cdot\mathbf q_2 = 0\) to machine precision. Now slide \(\mathbf v_2\) toward \(\mathbf v_1\): \(\mathbf w_2\) shrinks toward zero, and the subtraction becomes a difference of nearly equal vectors — catastrophic cancellation, which is why numerical libraries use modified Gram–Schmidt or Householder reflections instead.
Normalize. \(\|\mathbf w_2\| = \sqrt{\tfrac14+\tfrac14+1} = \sqrt{\tfrac32}\), so
\[ \mathbf q_2 = \frac{1}{\sqrt6}(1,-1,2) \]
(multiplying \(\mathbf w_2\) by 2 first to clear fractions).
STEP 5
Check: \(\mathbf q_1\cdot\mathbf q_2 = \frac{1}{\sqrt{12}}(1 - 1 + 0) = 0\) ✓ and \(\|\mathbf q_2\|^2 = \frac{1+1+4}{6} = 1\) ✓ The span is unchanged — \(\{\mathbf q_1,\mathbf q_2\}\) describes the same plane, just with a perpendicular ruler.
③Practice
1
Show \(\left\{\tfrac{1}{\sqrt2}(1,1),\ \tfrac{1}{\sqrt2}(1,-1)\right\}\) is orthonormal, and use it to expand \(\mathbf x = (5,1)\).
Hint 1Check the dot product between them, and each length.
Hint 2The coordinates are just \(\mathbf x\cdot\mathbf q_i\) — no system to solve.
Module V4 problem 2 solved the same expansion with a \(2\times2\) system. Here two dot products did it. That saving scales: for an orthonormal basis of \(\mathbb R^n\) you avoid an \(O(n^3)\) solve entirely — the reason Fourier coefficients are integrals rather than the solution of an infinite linear system.
\(\mathbf q_1\cdot\mathbf q_2 = 0\) ✓ Gram–Schmidt recovered the standard basis, which makes sense: \(\mathbf v_1\) already pointed along \(x\), so removing its influence from \(\mathbf v_2\) left only the \(y\)-part. The QR factorization here is \(R = \begin{bmatrix}3&2\\0&2\end{bmatrix}\), with \(r_{ij} = \mathbf q_i\cdot\mathbf v_j\).
3
Prove that an orthogonal set of nonzero vectors is linearly independent.
Hint 1Take a combination equal to zero and dot both sides with one of the vectors.
Hint 2All the cross terms vanish.
Solution
STEP 1 · set up
\[ c_1\mathbf q_1 + \cdots + c_k\mathbf q_k = \mathbf 0 \]
Orthogonality makes every term with \(j\ne i\) vanish, leaving
\[ c_i\,\|\mathbf q_i\|^2 = 0 \]
STEP 4 · conclude
Since \(\mathbf q_i\ne\mathbf 0\), \(\|\mathbf q_i\|^2 > 0\), so \(c_i = 0\). This holds for every \(i\), hence independence ∎
STEP 5 · why this proof is so short
Dotting with \(\mathbf q_i\) isolates one coefficient — no elimination, no determinant. That same trick extracts Fourier coefficients from an infinite series: multiply by \(\sin(n\pi x/L)\), integrate, and every other term dies. Orthogonality converts a coupled problem into independent one-line problems.
4
Show that if \(Q\) is square with orthonormal columns, then \(\|Q\mathbf x\| = \|\mathbf x\|\) for all \(\mathbf x\).
Hint 1Write \(\|\mathbf y\|^2 = \mathbf y^{T}\mathbf y\).
The same computation gives \((Q\mathbf x)\cdot(Q\mathbf y) = \mathbf x\cdot\mathbf y\), so angles survive too. Orthogonal matrices are exactly the rigid motions fixing the origin — rotations (\(\det = +1\)) and reflections (\(\det = -1\)). Numerically they never amplify error: condition number exactly 1, which is why QR is preferred over the normal equations in module S5.
5
Find a vector orthogonal to both \((1,1,0)\) and \((0,1,1)\), two ways.
Hint 1One way is the cross product.
Hint 2The other is solving \(A\mathbf x = \mathbf 0\) with these as rows.
The null-space method works in any dimension and with any number of constraints; the cross product only exists in \(\mathbb R^3\) (module V3 problem 9). What you computed is the orthogonal complement of the row space — dimension \(3-2 = 1\), exactly as rank–nullity predicts.
6
Find the QR factorization of \(A = \begin{bmatrix}1&1\\1&0\\0&1\end{bmatrix}\).
Hint 1Run Gram–Schmidt on the columns to get \(Q\).
Hint 2Then \(R = Q^{T}A\), and it comes out upper triangular.
STEP 4 · assemble Q and R
\[ Q = \begin{bmatrix}\tfrac{1}{\sqrt2}&\tfrac{1}{\sqrt6}\\[2pt]\tfrac{1}{\sqrt2}&-\tfrac{1}{\sqrt6}\\[2pt]0&\tfrac{2}{\sqrt6}\end{bmatrix}, \qquad R = \begin{bmatrix}\sqrt2&\tfrac{1}{\sqrt2}\\[2pt]0&\tfrac{\sqrt6}{2}\end{bmatrix} \]
STEP 5 · verify
Column 1 of \(QR\): \(\sqrt2\,\mathbf q_1 = (1,1,0)\) ✓ Column 2: \(\tfrac{1}{\sqrt2}\mathbf q_1 + \tfrac{\sqrt6}{2}\mathbf q_2 = (\tfrac12,\tfrac12,0)+(\tfrac12,-\tfrac12,1) = (1,0,1)\) ✓ \(R\) is upper triangular because \(\mathbf q_k\) is built only from \(\mathbf a_1,\dots,\mathbf a_k\) — later columns never contribute to earlier ones.
7
What happens if you apply Gram–Schmidt to a linearly dependent set?
Hint 1Try \(\mathbf v_1 = (1,0)\), \(\mathbf v_2 = (2,0)\).
Hint 2What is left after subtracting the projection?
Solution
STEP 1 · run the example
\[ \mathbf w_1 = (1,0), \qquad \text{proj of } \mathbf v_2 = \frac{2}{1}(1,0) = (2,0) \]
Normalizing would divide by \(\|\mathbf w_2\| = 0\). The algorithm halts.
STEP 4 · what it means
\(\mathbf v_2\) contributed nothing new — it lay entirely in the span of what came before. That is precisely dependence, detected automatically.
STEP 5 · the practical fix
Discard any vector whose \(\mathbf w_k\) is zero and continue; what emerges is an orthonormal basis for the span, with the count equal to the rank. Numerically the test is \(\|\mathbf w_k\| < \varepsilon\) rather than exactly zero, and this "rank-revealing" behaviour is why QR with column pivoting is a standard tool for estimating rank — though the SVD (module E4) does it more reliably.
8
Find the orthogonal complement of \(W = \operatorname{span}\{(1,2,1)\}\) in \(\mathbb R^3\), and give a basis.
Hint 1\(W^{\perp}\) is everything orthogonal to the spanning vector.
Hint 2That is one homogeneous equation.
Solution
STEP 1 · write the condition
\[ (x,y,z)\cdot(1,2,1) = 0 \ \Longrightarrow\ x + 2y + z = 0 \]
\(\dim W + \dim W^{\perp} = 1 + 2 = 3\) ✓ — always true. A line's complement is a plane, and \((W^{\perp})^{\perp} = W\). Note the complement basis is not orthogonal to itself: \((1,0,-1)\cdot(0,1,-2) = 2 \ne 0\). Gram–Schmidt would fix that if you needed an orthonormal basis of the plane.
9
Why do numerical libraries prefer QR over the normal equations \(A^{T}A\hat{\mathbf x} = A^{T}\mathbf b\)?
Hint 1Think about what forming \(A^{T}A\) does to the condition number.
Hint 2Orthogonal transformations have condition number 1.
Solution
STEP 1 · the conditioning problem
The condition number squares:
\[ \kappa(A^{T}A) = \kappa(A)^2 \]
If \(A\) has \(\kappa = 10^{6}\) — unremarkable for a fitting problem — then \(A^{T}A\) has \(10^{12}\), which exhausts double precision.
STEP 2 · a concrete failure
With \(A = \begin{bmatrix}1&1\\\varepsilon&0\\0&\varepsilon\end{bmatrix}\), \(A^{T}A = \begin{bmatrix}1+\varepsilon^2&1\\1&1+\varepsilon^2\end{bmatrix}\). If \(\varepsilon^2\) underflows below machine epsilon, the computed \(A^{T}A\) is exactly singular even though \(A\) has full rank.
STEP 3 · what QR does instead
Substituting \(A = QR\) into the normal equations gives \(R^{T}Q^{T}QR\hat{\mathbf x} = R^{T}Q^{T}\mathbf b\), and \(Q^{T}Q=I\) with \(R^{T}\) cancellable leaves
\[ R\hat{\mathbf x} = Q^{T}\mathbf b \]
— one triangular solve, and \(A^{T}A\) is never formed.
STEP 4 · why it is stable
Orthogonal matrices preserve length exactly, so they neither amplify nor attenuate error: \(\kappa(Q) = 1\). The conditioning of the problem stays \(\kappa(A)\), not its square.
STEP 5 · the hierarchy
Normal equations are fastest and fine for well-conditioned problems; QR (via Householder reflections, not classical Gram–Schmidt) is the standard workhorse; the SVD is slowest but handles rank deficiency and gives the most diagnostic information. This is the classic accuracy-versus-speed ladder in numerical linear algebra.
Part III · Module 5 Spaces & orthogonality
Least squares & projection
When \(A\mathbf x=\mathbf b\) has no solution — the usual case with real data — the right question changes from "solve it" to "get as close as possible." The answer is a projection, and it is the most-used idea in this entire course.
①Projection onto a subspace
Onto a line, then onto a subspace
\[ \operatorname{proj}_{\mathbf a}\mathbf b = \frac{\mathbf a\cdot\mathbf b}{\mathbf a\cdot\mathbf a}\mathbf a, \qquad P = A(A^{T}A)^{-1}A^{T} \]
The matrix \(P\) projects onto \(\operatorname{col}(A)\). It satisfies \(P^{2}=P\) (projecting twice changes nothing) and \(P^{T}=P\).
The normal equations
\[ A^{T}A\,\hat{\mathbf x} = A^{T}\mathbf b \]
The derivation in one line: the error \(\mathbf b - A\hat{\mathbf x}\) must be orthogonal to every column of \(A\), i.e. \(A^{T}(\mathbf b-A\hat{\mathbf x}) = \mathbf 0\). Rearranged, that is the normal equations. If \(A\) has independent columns, \(A^{T}A\) is invertible and \(\hat{\mathbf x}\) is unique.
Fitting a line to data
\[ A = \begin{bmatrix}1&t_1\\\vdots&\vdots\\1&t_m\end{bmatrix}, \quad \mathbf x = \begin{bmatrix}c\\d\end{bmatrix}, \quad \mathbf b = \begin{bmatrix}y_1\\\vdots\\y_m\end{bmatrix} \ \Longrightarrow\ y = c + dt \]
InteractiveThe best line through scattered pointsdrag the points; drag the line
your SSE —best SSE —best fit —
Each residual is drawn as a literal square, so the quantity being minimized is visible as total shaded area. Move your line however you like — you cannot beat the least-squares line, and the readout proves it. Notice the errors are measured vertically, not perpendicular to the line: least squares assumes error in \(y\) only. Perpendicular distance gives a different answer, total least squares, which is a singular value problem (module E4).
Worked example · fitting a line
Fit \(y = c + dt\) to the points \((0,1)\), \((1,3)\), \((2,4)\).
STEP 1
Set up the (inconsistent) system \(A\mathbf x=\mathbf b\):
\[ A = \begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}, \qquad \mathbf b = \begin{bmatrix}1\\3\\4\end{bmatrix} \]
Three equations, two unknowns — no exact solution unless the points are collinear, and they are not.
STEP 2
Form \(A^{T}A\) and \(A^{T}\mathbf b\):
\[ A^{T}A = \begin{bmatrix}3&3\\3&5\end{bmatrix}, \qquad A^{T}\mathbf b = \begin{bmatrix}8\\11\end{bmatrix} \]
STEP 3
Solve the normal equations \(3c+3d = 8\), \(3c+5d = 11\). Subtracting gives \(2d = 3\):
\[ d = \tfrac32, \qquad c = \tfrac{8-4.5}{3} = \tfrac76 \]
STEP 4
The best-fit line:
\[ y = \tfrac76 + \tfrac32 t \]
STEP 5
Residuals: at \(t=0,1,2\) the line predicts \(\tfrac76, \tfrac{8}{3}, \tfrac{25}{6}\), so the errors are \(-\tfrac16, \tfrac13, -\tfrac16\). Their sum is zero ✓ — always true when the model includes an intercept, because the error must be orthogonal to the column of ones. SSE \(= \tfrac{1}{36}+\tfrac{4}{36}+\tfrac{1}{36} = \tfrac16\), and no other line does better.
②Practice
1
Project \(\mathbf b = (3,4)\) onto the line spanned by \(\mathbf a = (1,0)\), and find the error vector.
Hint 1Use \(\frac{\mathbf a\cdot\mathbf b}{\mathbf a\cdot\mathbf a}\mathbf a\).
Hint 2The error is \(\mathbf b\) minus the projection — check it is perpendicular to \(\mathbf a\).
Solution
STEP 1 · dot products
\[ \mathbf a\cdot\mathbf b = 3, \qquad \mathbf a\cdot\mathbf a = 1 \]
Projection splits any vector into a component in the subspace and a component orthogonal to it — the decomposition behind every least-squares argument.
2
Find the projection matrix onto the line through \(\mathbf a = (1,2)\), and verify \(P^2 = P\).
Hint 1\(P = \frac{\mathbf a\mathbf a^{T}}{\mathbf a^{T}\mathbf a}\).
Hint 2The outer product \(\mathbf a\mathbf a^{T}\) is a \(2\times2\) matrix.
Solution
STEP 1 · outer product and normalizer
\[ \mathbf a\mathbf a^{T} = \begin{bmatrix}1&2\\2&4\end{bmatrix}, \qquad \mathbf a^{T}\mathbf a = 5 \]
STEP 2 · the projection matrix
\[ P = \tfrac15\begin{bmatrix}1&2\\2&4\end{bmatrix} \]
STEP 3 · square it
\[ P^2 = \tfrac{1}{25}\begin{bmatrix}1&2\\2&4\end{bmatrix}\begin{bmatrix}1&2\\2&4\end{bmatrix} = \tfrac{1}{25}\begin{bmatrix}5&10\\10&20\end{bmatrix} = \tfrac15\begin{bmatrix}1&2\\2&4\end{bmatrix} = P \ ✓ \]
STEP 4 · test it
\[ P\begin{bmatrix}5\\0\end{bmatrix} = \tfrac15\begin{bmatrix}5\\10\end{bmatrix} = \begin{bmatrix}1\\2\end{bmatrix} \]
— which lies on the line ✓
STEP 5 · its spectrum
Rank 1, symmetric, trace 1, determinant 0. The eigenvalues are 1 (along \(\mathbf a\), unchanged) and 0 (perpendicular to \(\mathbf a\), annihilated). Every projection matrix has only 0s and 1s as eigenvalues — that is what \(P^2=P\) forces, since \(\lambda^2 = \lambda\).
3
Fit a line to \((1,1)\), \((2,2)\), \((3,2)\).
Hint 1Build \(A\) with a column of ones and a column of \(t\)-values.
Hint 2Solve \(A^{T}A\hat{\mathbf x} = A^{T}\mathbf b\).
Solution
STEP 1 · set up
\[ A = \begin{bmatrix}1&1\\1&2\\1&3\end{bmatrix}, \qquad \mathbf b = \begin{bmatrix}1\\2\\2\end{bmatrix} \]
STEP 2 · form the normal equations
\[ A^{T}A = \begin{bmatrix}3&6\\6&14\end{bmatrix}, \qquad A^{T}\mathbf b = \begin{bmatrix}5\\11\end{bmatrix} \]
STEP 3 · solve
From \(3c+6d=5\) and \(6c+14d=11\): doubling the first gives \(6c+12d=10\), so subtracting yields \(2d = 1\), \(d = \tfrac12\).
\[ c = \frac{5-3}{3} = \frac23 \]
STEP 4 · the fit
\[ y = \tfrac23 + \tfrac12 t \]
STEP 5 · check the residuals
Predictions \(\tfrac76, \tfrac53, \tfrac{13}{6}\); residuals \(-\tfrac16, \tfrac13, -\tfrac16\), summing to zero ✓ SSE \(= \tfrac16\). The middle point sits above the line and the outer two below — the classic signature of a slight curvature the linear model cannot capture.
4
Derive the normal equations from the requirement that the error be orthogonal to \(\operatorname{col}(A)\).
Hint 1Orthogonal to every column means \(A^{T}\mathbf e = \mathbf 0\).
Hint 2Substitute \(\mathbf e = \mathbf b - A\hat{\mathbf x}\).
Solution
STEP 1 · state the geometric condition
The closest point of \(\operatorname{col}(A)\) to \(\mathbf b\) is the one whose error vector is perpendicular to the whole subspace:
\[ \mathbf e = \mathbf b - A\hat{\mathbf x} \perp \operatorname{col}(A) \]
STEP 2 · express it with a transpose
Orthogonal to every column means every entry of \(A^{T}\mathbf e\) vanishes:
\[ A^{T}(\mathbf b - A\hat{\mathbf x}) = \mathbf 0 \]
If the columns of \(A\) are independent, \(A^{T}A\) is invertible and \(\hat{\mathbf x} = (A^{T}A)^{-1}A^{T}\mathbf b\), giving the projection \(\mathbf p = A\hat{\mathbf x} = A(A^{T}A)^{-1}A^{T}\mathbf b\).
STEP 5 · the calculus route agrees
Minimizing \(f(\mathbf x) = \|A\mathbf x-\mathbf b\|^2\) by setting \(\nabla f = 2A^{T}(A\mathbf x-\mathbf b) = \mathbf 0\) gives the identical equations — and since \(f\) is a convex quadratic, the stationary point is the global minimum. Geometry and calculus meeting here is why least squares is so robust.
5
Project \(\mathbf b = (1,1,1)\) onto the plane spanned by \((1,0,0)\) and \((0,1,0)\), two ways.
Hint 1The spanning vectors are already orthonormal — just add the two individual projections.
Hint 2Then confirm with \(P = A(A^{T}A)^{-1}A^{T}\).
STEP 3 · build P
\[ P = AA^{T} = \begin{bmatrix}1&0&0\\0&1&0\\0&0&0\end{bmatrix} \]
STEP 4 · apply it
\[ P\mathbf b = (1,1,0) \ ✓ \]
STEP 5 · the error
\(\mathbf e = (0,0,1)\), perpendicular to the plane ✓ Note how much simpler \(P\) became when \(A^{T}A = I\): the general formula collapses to \(P = AA^{T}\). Orthonormalizing first (Gram–Schmidt, module S4) always buys that simplification.
6
Fit a parabola \(y = c_0 + c_1t + c_2t^2\) to four data points — set up the system and explain why it is still "linear" least squares.
Hint 1Which quantities are the unknowns?
Hint 2Linearity is required in the coefficients, not in \(t\).
Solution
STEP 1 · build the design matrix
\[ A = \begin{bmatrix}1&t_1&t_1^2\\1&t_2&t_2^2\\1&t_3&t_3^2\\1&t_4&t_4^2\end{bmatrix}, \qquad \mathbf x = \begin{bmatrix}c_0\\c_1\\c_2\end{bmatrix}, \qquad \mathbf b = \begin{bmatrix}y_1\\y_2\\y_3\\y_4\end{bmatrix} \]
STEP 2 · the shape
\(4\times3\): four equations, three unknowns — overdetermined, so generally inconsistent.
STEP 3 · solve
Exactly as before: \(A^{T}A\hat{\mathbf x} = A^{T}\mathbf b\), a \(3\times3\) system.
STEP 4 · why it is linear least squares
The unknowns \(c_0,c_1,c_2\) appear to the first power only. The \(t^2\) sits in the matrix, where it is just a number computed from the data. Linearity is a statement about the parameters.
STEP 5 · how far this extends
Any model \(y = \sum c_jf_j(t)\) works the same way — exponentials, sines, splines, logs. That is why "linear regression" happily fits curves. Genuinely nonlinear least squares means parameters inside the functions, like \(y = ae^{bt}\) with unknown \(b\); that needs iteration (Gauss–Newton, Levenberg–Marquardt), not a single solve.
7
Show that \(P = A(A^{T}A)^{-1}A^{T}\) satisfies \(P^{T} = P\) and \(P^{2} = P\).
Hint 1Use \((XYZ)^{T} = Z^{T}Y^{T}X^{T}\) and note \(A^{T}A\) is symmetric.
Hint 2For \(P^2\), watch the middle terms cancel.
Solution
STEP 1 · symmetry of the middle factor
\[ (A^{T}A)^{T} = A^{T}(A^{T})^{T} = A^{T}A \]
so \(A^{T}A\) is symmetric, and hence so is its inverse.
STEP 2 · transpose P
\[ P^{T} = \big(A(A^{T}A)^{-1}A^{T}\big)^{T} = A\big((A^{T}A)^{-1}\big)^{T}A^{T} = A(A^{T}A)^{-1}A^{T} = P \ ✓ \]
STEP 5 · why these two properties characterize projections
\(P^2=P\) says the image is already fixed — projecting a projection changes nothing. \(P^{T}=P\) says the projection is orthogonal rather than oblique, so the error is perpendicular. Together they define an orthogonal projection, and \(I-P\) is then the complementary projection onto \(\operatorname{null}(A^{T})\). Here \(\operatorname{tr}(P) = \operatorname{rank}(A)\), a handy check.
8
Three GPS pseudo-ranges give the inconsistent system \(x+y=2\), \(x-y=0\), \(x+2y=5\). Find the least-squares estimate.
Hint 1Write \(A\) and \(\mathbf b\), then form the normal equations.
Hint 2\(A^{T}A\) will be \(2\times2\).
Solution
STEP 1 · set up
\[ A = \begin{bmatrix}1&1\\1&-1\\1&2\end{bmatrix}, \qquad \mathbf b = \begin{bmatrix}2\\0\\5\end{bmatrix} \]
STEP 2 · form AᵀA and Aᵀb
\[ A^{T}A = \begin{bmatrix}3&2\\2&6\end{bmatrix}, \qquad A^{T}\mathbf b = \begin{bmatrix}7\\12\end{bmatrix} \]
\(\mathbf e\cdot(1,1,1) = \frac{-6+2+4}{7} = 0\) ✓ and \(\mathbf e\cdot(1,-1,2) = \frac{-6-2+8}{7} = 0\) ✓ The error is perpendicular to both columns, confirming the solution. This is genuinely how satellite navigation works: more measurements than unknowns, each slightly noisy, reconciled by least squares.
9
What goes wrong in least squares when the columns of \(A\) are nearly dependent, and what is done about it?
Hint 1Think about \(\det(A^{T}A)\) approaching zero.
Hint 2The fit may be fine while the coefficients are wild.
Solution
STEP 1 · the algebra
Near-dependence makes \(A^{T}A\) nearly singular, so \((A^{T}A)^{-1}\) has enormous entries and \(\hat{\mathbf x}\) becomes hypersensitive to tiny changes in \(\mathbf b\).
STEP 2 · the symptom
Coefficients swing wildly — large positive paired with large negative — while the predictions \(A\hat{\mathbf x}\) stay reasonable. Statisticians call this multicollinearity: two predictors carrying nearly the same information, so the data cannot apportion credit between them.
STEP 3 · fix one — regularize
Ridge regression solves \((A^{T}A + \lambda I)\hat{\mathbf x} = A^{T}\mathbf b\). Adding \(\lambda I\) shifts every eigenvalue up by \(\lambda\), guaranteeing invertibility and shrinking the coefficients at the cost of a little bias.
STEP 4 · fix two — truncate
Use the SVD and discard the directions with tiny singular values (module E4). The pseudoinverse \(A^{+}\) does this and also returns the minimum-norm solution when the columns are exactly dependent.
STEP 5 · fix three — change the model
Drop a redundant predictor, or re-centre the data: fitting \(y = c + d(t-\bar t)\) instead of \(y = c+dt\) makes the two columns orthogonal, so \(A^{T}A\) becomes diagonal and the conditioning problem disappears. Often the best remedy is not a better solver but a better-posed question.
Part IV · Module 1 Eigenvalues & beyond
Eigenvalues & eigenvectors
Almost every vector changes direction under a matrix. A few special ones do not — they only stretch. Find those, and the transformation stops being a tangle of coupled numbers and becomes a list of independent scalings.
①The defining equation
Eigenvector, eigenvalue
\[ A\mathbf v = \lambda\mathbf v, \qquad \mathbf v \ne \mathbf 0 \]
Rearranged, \((A-\lambda I)\mathbf v = \mathbf 0\) with \(\mathbf v\ne\mathbf 0\), so \(A-\lambda I\) must be singular:
Characteristic equation
\[ \det(A - \lambda I) = 0 \]
For each root \(\lambda\), the eigenvectors are the nonzero elements of \(\operatorname{null}(A-\lambda I)\) — the eigenspace, a subspace, so eigenvectors are never unique (any nonzero multiple works).
For \(2\times2\) these two facts alone give the eigenvalues: \(\lambda^2 - (\operatorname{tr}A)\lambda + \det A = 0\).
InteractiveHunt for the directions that don't turnsweep a vector around the circle
x —Ax —angle between —eigenvalues —
The amber arrow is \(\mathbf x\) on the unit circle; the cyan arrow is \(A\mathbf x\). As you sweep, the angle between them shrinks to zero at exactly two directions (for the default symmetric matrix) — those are the eigenvectors, and the length of \(A\mathbf x\) there is \(|\lambda|\). Set \(b = 1, c = -1\) to make a rotation: the angle between never reaches zero, because a genuine rotation turns every direction. The eigenvalues have gone complex, and the geometry tells you so before the algebra does.
Worked example · a full eigen-computation
Find the eigenvalues and eigenvectors of \(A = \begin{bmatrix}4&1\\2&3\end{bmatrix}\).
Verify both: \(A(1,1) = (5,5) = 5(1,1)\) ✓ and \(A(1,-2) = (4-2,\ 2-6) = (2,-4) = 2(1,-2)\) ✓ Notice that in each eigen-solve the matrix \(A-\lambda I\) came out singular — rows proportional. If it does not, you have made an arithmetic error in the eigenvalue.
②Practice
1
Find the eigenvalues and eigenvectors of \(\begin{bmatrix}3&0\\0&-1\end{bmatrix}\).
Hint 1The matrix is diagonal — what does it do to \(\mathbf e_1\) and \(\mathbf e_2\)?
Solution
STEP 1 · read the eigenvalues off
For a diagonal (or triangular) matrix, the eigenvalues are the diagonal entries:
The \(x\)-axis is stretched by 3; the \(y\)-axis is flipped and left at unit length. The standard basis is already the eigenbasis.
STEP 5 · check the invariants
\(\operatorname{tr} = 2 = 3 + (-1)\) ✓ and \(\det = -3 = 3\times(-1)\) ✓ Diagonal matrices are the goal of module E2: every diagonalizable matrix becomes one in the right basis.
2
Find the eigenvalues of \(\begin{bmatrix}2&1\\1&2\end{bmatrix}\) and show its eigenvectors are perpendicular.
Hint 1Use \(\lambda^2 - (\operatorname{tr})\lambda + \det = 0\).
Hint 2The matrix is symmetric — module E3 explains why perpendicularity is guaranteed.
Symmetric matrices always have orthogonal eigenvectors for distinct eigenvalues, and always have real eigenvalues — the spectral theorem (module E3). Geometrically \(A\) stretches by 3 along \(y=x\) and leaves \(y=-x\) alone: a pure stretch along perpendicular axes, with no rotation anywhere.
3
Find the eigenvalues of the rotation matrix \(\begin{bmatrix}0&-1\\1&0\end{bmatrix}\) and explain the result.
Hint 1Compute the characteristic polynomial — you may need complex numbers.
Hint 2Which real direction does a \(90^\circ\) rotation leave unturned?
Solution
STEP 1 · characteristic equation
\(\operatorname{tr} = 0\), \(\det = 1\):
\[ \lambda^2 + 1 = 0 \]
STEP 2 · solve
\[ \lambda = \pm i \]
STEP 3 · the geometric reason
A \(90^\circ\) rotation turns every real vector, so no real direction can satisfy \(A\mathbf v = \lambda\mathbf v\). Real eigenvectors simply do not exist here.
STEP 4 · the complex eigenvectors
Over \(\mathbb C\) they do: \((1,-i)\) for \(\lambda=i\), and \((1,i)\) for \(\lambda=-i\). Check: \(A(1,-i) = (i, 1) = i(1,-i)\) ✓
STEP 5 · reading complex eigenvalues
Writing \(\lambda = re^{i\theta}\), the modulus \(r\) is the scaling and the argument \(\theta\) is the rotation per application. Here \(r=1\) and \(\theta = 90^\circ\), exactly the rotation. In dynamical systems, \(|\lambda|<1\) means spiralling inward, \(|\lambda|>1\) outward, \(|\lambda|=1\) a closed orbit — the entire stability classification in one number.
4
Find the eigenvalues of \(\begin{bmatrix}1&2&3\\0&4&5\\0&0&6\end{bmatrix}\), and one eigenvector.
Hint 1The matrix is triangular.
Hint 2The eigenvector for \(\lambda=1\) is easiest.
Solution
STEP 1 · eigenvalues
\(\det(A-\lambda I)\) of a triangular matrix is the product of the diagonal differences:
\(\operatorname{tr} = 11 = 1+4+6\) ✓ and \(\det = 24 = 1\cdot4\cdot6\) ✓ Note that "eigenvalues are the diagonal" holds only for triangular matrices — for a general matrix the diagonal entries tell you nothing directly, though they still sum to the trace.
5
Show that if \(A\mathbf v = \lambda\mathbf v\) then \(A^{2}\mathbf v = \lambda^{2}\mathbf v\), and that \(A^{-1}\mathbf v = \frac{1}{\lambda}\mathbf v\) when \(A\) is invertible.
Hint 1Apply \(A\) twice and pull the scalar out.
Hint 2For the inverse, multiply \(A\mathbf v = \lambda\mathbf v\) by \(A^{-1}\).
By induction, \(A^{n}\mathbf v = \lambda^{n}\mathbf v\) for every \(n\ge1\).
STEP 3 · the inverse
Multiply \(A\mathbf v=\lambda\mathbf v\) by \(A^{-1}\):
\[ \mathbf v = \lambda A^{-1}\mathbf v \]
STEP 4 · divide
\(\lambda\ne0\) because \(A\) is invertible (zero is never an eigenvalue of an invertible matrix), so
\[ A^{-1}\mathbf v = \tfrac1\lambda\mathbf v \ ✓ \]
STEP 5 · the general pattern
For any polynomial \(p\), \(p(A)\mathbf v = p(\lambda)\mathbf v\) — and the same holds for \(e^{A}\), giving \(e^{A}\mathbf v = e^{\lambda}\mathbf v\). The eigenvectors never change; only the eigenvalues get transformed. That is the whole engine behind module E2 and behind solving \(\mathbf x' = A\mathbf x\).
6
Find the eigenvalues and eigenvectors of \(\begin{bmatrix}3&1\\0&3\end{bmatrix}\). How many independent eigenvectors are there?
Hint 1It is triangular, so the eigenvalues are immediate — but there is a repeat.
Hint 2Compute the dimension of \(\operatorname{null}(A-3I)\).
STEP 2 · the eigenspace
\[ A - 3I = \begin{bmatrix}0&1\\0&0\end{bmatrix} \]
which has rank 1, so its null space is 1-dimensional.
STEP 3 · solve
\(v_2 = 0\), \(v_1\) free:
\[ \mathbf v = \begin{bmatrix}1\\0\end{bmatrix} \]
STEP 4 · count
Only one independent eigenvector — geometric multiplicity 1, less than the algebraic multiplicity 2.
STEP 5 · the consequence
There is no eigenbasis, so \(A\) is defective and cannot be diagonalized (module E2). It is a scaled shear: \(3I\) plus a nilpotent part. Its Jordan form is \(\begin{bmatrix}3&1\\0&3\end{bmatrix}\) itself, and \(A^{n} = 3^{n-1}\begin{bmatrix}3&n\\0&3\end{bmatrix}\) — the extra factor of \(n\) is the fingerprint of a repeated eigenvalue with too few eigenvectors.
7
Prove that eigenvectors for distinct eigenvalues are linearly independent (two-eigenvalue case).
Hint 1Assume \(c_1\mathbf v_1 + c_2\mathbf v_2 = \mathbf 0\) and apply \(A\).
Hint 2Then eliminate one term between the two relations.
\(\mathbf v_1\ne\mathbf 0\) and \(\lambda_1\ne\lambda_2\), so \(c_1 = 0\). Then (i) gives \(c_2\mathbf v_2=\mathbf 0\), so \(c_2=0\) ∎
STEP 5 · the general result
The same elimination, iterated, shows eigenvectors for any set of distinct eigenvalues are independent. Immediate corollary: an \(n\times n\) matrix with \(n\) distinct eigenvalues is diagonalizable, since the \(n\) independent eigenvectors form a basis. Repeated eigenvalues are the only way diagonalizability can fail.
8
A matrix has eigenvalues \(2\) and \(0\). Is it invertible? What is its rank, if it is \(2\times2\)?
Hint 1The determinant is the product of the eigenvalues.
Hint 2What does an eigenvalue of 0 say about the null space?
Solution
STEP 1 · determinant
\[ \det A = 2\times0 = 0 \]
so \(A\) is not invertible.
STEP 2 · what λ = 0 means
\(A\mathbf v = 0\mathbf v = \mathbf 0\) for some \(\mathbf v\ne\mathbf 0\), so the null space is nontrivial — the eigenspace for 0 is the null space.
STEP 3 · nullity
The eigenvalues are distinct, so each eigenspace is 1-dimensional: nullity \(= 1\).
\(A\) is invertible ⟺ \(0\) is not an eigenvalue. And for a diagonalizable matrix, the rank equals the number of nonzero eigenvalues counted with multiplicity — a shortcut that fails for defective matrices, where \(\begin{bmatrix}0&1\\0&0\end{bmatrix}\) has both eigenvalues 0 yet rank 1.
9
Why does the power method — repeatedly computing \(\mathbf x_{k+1} = A\mathbf x_k/\|A\mathbf x_k\|\) — converge to the dominant eigenvector?
Hint 1Expand the starting vector in the eigenbasis.
Hint 2Factor out the largest eigenvalue and see what happens to the other terms.
Solution
STEP 1 · expand the start
Assume an eigenbasis and \(|\lambda_1| > |\lambda_2| \ge \cdots\):
STEP 3 · factor out the dominant term
\[ = \lambda_1^{k}\left[c_1\mathbf v_1 + c_2\left(\tfrac{\lambda_2}{\lambda_1}\right)^{k}\mathbf v_2 + \cdots\right] \]
STEP 4 · take the limit
Every ratio \(|\lambda_j/\lambda_1| < 1\), so those terms decay geometrically. The bracket tends to \(c_1\mathbf v_1\), and after normalizing, \(\mathbf x_k\) aligns with \(\mathbf v_1\) ∎
STEP 5 · the caveats and the payoff
Convergence is linear with rate \(|\lambda_2/\lambda_1|\) — slow when the top two eigenvalues are close — and it fails if \(c_1 = 0\) (though round-off usually rescues you) or if \(|\lambda_1| = |\lambda_2|\). The payoff is that it needs only matrix–vector products, so it works on matrices too large to store densely. Google's original PageRank was the power method on a web-sized Markov matrix (module E5).
Part IV · Module 2 Eigenvalues & beyond
Diagonalization & matrix powers
If the eigenvectors form a basis, the matrix is a diagonal matrix — seen from the right angle. Everything hard about powers, exponentials, and coupled systems becomes easy in that basis.
①The factorization
Eigendecomposition
\[ A = P\Lambda P^{-1}, \qquad P = [\,\mathbf v_1\ \cdots\ \mathbf v_n\,], \qquad \Lambda = \operatorname{diag}(\lambda_1,\dots,\lambda_n) \]
It exists exactly when \(A\) has \(n\) independent eigenvectors. Sufficient (not necessary) condition: \(n\) distinct eigenvalues. It fails when some eigenvalue's geometric multiplicity falls short of its algebraic multiplicity.
Read \(A^k = P\Lambda^kP^{-1}\) right to left: convert to the eigenbasis, scale each coordinate by \(\lambda_i^k\), convert back. The coupling was an illusion of the coordinate system.
InteractiveIterating a matrixwatch every start converge to one direction
A —λ₁ᵏ, λ₂ᵏ —behaviour —
Several starting points are iterated at once, their trajectories traced. Whenever \(|\lambda_1| > |\lambda_2|\), every orbit bends toward the \(\mathbf v_1\) axis — the dominant eigendirection wins regardless of where you begin. Push both \(|\lambda|\) below 1 and everything collapses to the origin (a stable node); push both above 1 and everything escapes. Make \(\lambda_2\) negative and the orbit alternates sides while still converging in direction. The two eigenvalues, not the four matrix entries, decide the entire long-run story.
Worked example · diagonalize and take a power
Diagonalize \(A = \begin{bmatrix}4&1\\2&3\end{bmatrix}\) and compute \(A^{5}\).
STEP 1
From module E1: \(\lambda = 5\) with \(\mathbf v_1 = (1,1)\), and \(\lambda = 2\) with \(\mathbf v_2 = (1,-2)\).
STEP 2
Assemble \(P\) and \(\Lambda\):
\[ P = \begin{bmatrix}1&1\\1&-2\end{bmatrix}, \qquad \Lambda = \begin{bmatrix}5&0\\0&2\end{bmatrix} \]
Check the trace: \(2094+1063 = 3157 = 3125+32\) ✓ and \(\det = 5^5\cdot2^5 = 100000\). Four multiplications instead of four matrix products — and for \(A^{100}\) the saving is total.
Normalizing \(P\) by \(\tfrac{1}{\sqrt2}\) gives an orthogonal \(Q\) with \(Q^{-1} = Q^{T}\), so \(A = Q\Lambda Q^{T}\) — the spectral decomposition of a symmetric matrix (module E3). No inverse ever needs computing.
2
Is \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\) diagonalizable?
Hint 1Find the eigenvalues, then count independent eigenvectors.
STEP 2 · eigenspace
\[ A - I = \begin{bmatrix}0&1\\0&0\end{bmatrix} \ \Longrightarrow\ v_2 = 0 \]
so the eigenspace is \(\operatorname{span}\{(1,0)\}\), dimension 1.
STEP 3 · compare multiplicities
Algebraic 2, geometric 1 ⟹ only one independent eigenvector.
STEP 4 · conclude
Not diagonalizable — there is no eigenbasis, so no invertible \(P\) exists.
STEP 5 · a proof by contradiction
If \(A = P(I)P^{-1}\), then \(A = I\) — false. Any matrix similar to the identity is the identity, so a non-identity matrix with all eigenvalues 1 can never be diagonalized. Its powers grow linearly (module M2 problem 5) rather than purely exponentially, which is the behavioural signature of defectiveness.
3
Compute \(A^{10}\) for \(A = \begin{bmatrix}1&0\\0&-1\end{bmatrix}\) and for \(A=\begin{bmatrix}0&1\\1&0\end{bmatrix}\).
Hint 1Both are reflections — what does applying one twice do?
Solution
STEP 1 · first matrix, diagonal already
\[ A^{10} = \begin{bmatrix}1^{10}&0\\0&(-1)^{10}\end{bmatrix} = I \]
STEP 2 · second matrix, square it
\[ \begin{bmatrix}0&1\\1&0\end{bmatrix}^2 = \begin{bmatrix}1&0\\0&1\end{bmatrix} = I \]
STEP 3 · use the period
\[ A^{10} = (A^2)^5 = I^5 = I \]
STEP 4 · confirm through eigenvalues
Both have eigenvalues \(\pm1\), so \(\Lambda^{10} = I\) and \(A^{10} = PIP^{-1} = I\) either way ✓
STEP 5 · the general principle
Any reflection satisfies \(A^2 = I\), so even powers give \(I\) and odd powers give \(A\). Whenever every eigenvalue is a root of unity, the matrix is periodic — rotation by \(90^\circ\) has period 4, by \(120^\circ\) period 3. The eigenvalues predict the period without any matrix multiplication.
4
Diagonalize \(A = \begin{bmatrix}1&2\\0&3\end{bmatrix}\) and use it to find \(A^{n}\).
Hint 1Triangular, so the eigenvalues are 1 and 3.
Hint 2Find each eigenvector, then assemble \(P\Lambda^{n}P^{-1}\).
Solution
STEP 1 · eigenvector for λ = 1
\[ A - I = \begin{bmatrix}0&2\\0&2\end{bmatrix} \ \Longrightarrow\ v_2 = 0 \ \Longrightarrow\ \mathbf v_1 = \begin{bmatrix}1\\0\end{bmatrix} \]
STEP 3 · assemble and invert
\[ P = \begin{bmatrix}1&1\\0&1\end{bmatrix}, \qquad P^{-1} = \begin{bmatrix}1&-1\\0&1\end{bmatrix} \]
STEP 4 · compute the power
\[ A^{n} = \begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}1&0\\0&3^{n}\end{bmatrix}\begin{bmatrix}1&-1\\0&1\end{bmatrix} = \begin{bmatrix}1&3^{n}-1\\0&3^{n}\end{bmatrix} \]
STEP 5 · sanity checks
\(n=1\) gives \(\begin{bmatrix}1&2\\0&3\end{bmatrix} = A\) ✓ and \(n=0\) gives \(I\) ✓ The formula even extends to \(n=-1\): \(\begin{bmatrix}1&-2/3\\0&1/3\end{bmatrix}\), which is indeed \(A^{-1}\) ✓ Diagonalization gives every power at once, including negative and fractional ones.
5
The Fibonacci recurrence is \(\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}F_n\\F_{n-1}\end{bmatrix}\). Find the eigenvalues and explain the golden-ratio growth.
Hint 1Trace 1, determinant \(-1\).
Hint 2The dominant eigenvalue controls the growth rate.
\(|\psi| < 1\), so \(\psi^{n}\to0\) and \(F_n \approx \varphi^{n}/\sqrt5\). The ratio \(F_{n+1}/F_n\to\varphi\).
STEP 5 · a striking consequence
Because \(|\psi^n/\sqrt5| < \tfrac12\) for all \(n\ge0\), \(F_n\) is the nearest integer to \(\varphi^{n}/\sqrt5\). An irrational-looking formula produces exact integers, because the irrational parts cancel. Every linear recurrence yields to this method: turn it into a matrix, diagonalize, and read off the growth from the dominant eigenvalue.
6
If \(A = P\Lambda P^{-1}\), show that \(A\) and \(\Lambda\) have the same eigenvalues.
Hint 1Compare their characteristic polynomials.
Hint 2Factor \(P\) and \(P^{-1}\) out of \(A - \lambda I\).
Solution
STEP 1 · rewrite A − λI
\[ A - \lambda I = P\Lambda P^{-1} - \lambda PP^{-1} = P(\Lambda-\lambda I)P^{-1} \]
Identical characteristic polynomials ⟹ identical eigenvalues, with the same multiplicities ∎
STEP 5 · what changes and what doesn't
The eigenvalues are shared; the eigenvectors are not — \(A\)'s are \(P\) times \(\Lambda\)'s. This is why every similar matrix shares trace, determinant, rank, and characteristic polynomial: they are properties of the transformation, not of the basis you describe it in (module S2 problem 4).
7
For which \(k\) is \(\begin{bmatrix}1&k\\0&1\end{bmatrix}\) diagonalizable?
Hint 1The eigenvalue is 1, repeated, for every \(k\).
Hint 2Compute the rank of \(A - I\) as a function of \(k\).
Solution
STEP 1 · eigenvalues
Triangular, so \(\lambda = 1\) with algebraic multiplicity 2, regardless of \(k\).
STEP 2 · the eigenspace
\[ A - I = \begin{bmatrix}0&k\\0&0\end{bmatrix} \]
STEP 3 · case k ≠ 0
Rank 1, so the null space is 1-dimensional — only one eigenvector. Not diagonalizable.
STEP 4 · case k = 0
\(A - I = 0\), rank 0, so the eigenspace is all of \(\mathbb R^2\). And indeed \(A = I\) is already diagonal ✓
STEP 5 · the answer and the lesson
Only \(k = 0\). The set of non-diagonalizable matrices is "thin" — an arbitrarily small perturbation of \(\begin{bmatrix}1&k\\0&1\end{bmatrix}\) to \(\begin{bmatrix}1&k\\ \varepsilon&1\end{bmatrix}\) has distinct eigenvalues \(1\pm\sqrt{k\varepsilon}\) and is diagonalizable. But its eigenvectors become nearly parallel, so \(P\) is nearly singular and the decomposition is numerically useless. That fragility is exactly why the SVD (module E4), which always exists and is always stable, is preferred in computation.
8
Use diagonalization to solve \(\mathbf x' = A\mathbf x\) with \(A = \begin{bmatrix}2&0\\0&-3\end{bmatrix}\), then explain the general recipe.
Hint 1The system is already decoupled here.
Hint 2In general, substitute \(\mathbf x = P\mathbf y\).
All \(\operatorname{Re}\lambda_i < 0\) ⟹ every solution decays (stable). Any \(\operatorname{Re}\lambda_i > 0\) ⟹ growth in that eigendirection (unstable). Here one of each: a saddle, decaying along \(\mathbf e_2\) and growing along \(\mathbf e_1\). Complex eigenvalues add oscillation — module E5, and the whole qualitative theory in the ODE Launchpad.
9
When does \(A^{k}\to 0\) as \(k\to\infty\)? When does it converge to something nonzero?
Hint 1Look at what \(\Lambda^{k}\) does entry by entry.
Hint 2Consider \(|\lambda| < 1\), \(=1\), and \(>1\) separately.
Solution
STEP 1 · reduce to the eigenvalues
\(A^{k} = P\Lambda^{k}P^{-1}\), so the behaviour is entirely governed by \(\lambda_i^{k}\).
STEP 2 · decay to zero
\[ A^{k}\to0 \iff |\lambda_i| < 1 \ \text{for every } i \]
The largest \(|\lambda_i|\) is the spectral radius \(\rho(A)\), so the condition is \(\rho(A) < 1\).
STEP 3 · convergence to something nonzero
This needs \(\rho(A) = 1\) with every eigenvalue of modulus 1 equal to exactly \(+1\) and semisimple (enough eigenvectors), and all others strictly inside the unit circle. The limit is then the projection onto the \(\lambda=1\) eigenspace.
STEP 4 · the failure modes
Any \(|\lambda| > 1\) ⟹ blow-up. A complex \(\lambda\) with \(|\lambda|=1\) but \(\lambda\ne1\) ⟹ perpetual rotation, no limit. A repeated \(\lambda\) with too few eigenvectors ⟹ polynomial factors like \(k\lambda^{k}\), which still decay if \(|\lambda|<1\) but diverge at \(|\lambda|=1\).
STEP 5 · where this is used
Markov chains (module E5) sit exactly in the step-3 case: \(\lambda=1\) with everything else smaller, so \(A^{k}\) converges and every initial distribution flows to the same steady state. Iterative solvers converge precisely when their iteration matrix has \(\rho < 1\), and numerical schemes for PDEs are stable under the same condition.
Part IV · Module 3 Eigenvalues & beyond
Symmetric matrices & quadratic forms
Symmetric matrices are the best-behaved objects in the subject: real eigenvalues, perpendicular eigenvectors, always diagonalizable. And they are everywhere — covariance, stiffness, inertia, Hessians, graph Laplacians.
①The spectral theorem
Every real symmetric matrix
\[ A = A^{T} \ \Longrightarrow\ A = Q\Lambda Q^{T}, \qquad Q^{T}Q = I, \ \Lambda \text{ real diagonal} \]
All eigenvalues are real — no complex surprises.
Eigenvectors for distinct eigenvalues are orthogonal, and an orthonormal eigenbasis always exists.
Diagonalization is guaranteed, even with repeated eigenvalues.
\(A = \sum_i \lambda_i\mathbf q_i\mathbf q_i^{T}\): a sum of scaled projections.
②Quadratic forms and definiteness
Quadratic form
\[ Q(\mathbf x) = \mathbf x^{T}A\mathbf x = \sum_{i,j}a_{ij}x_ix_j \]
In the eigenbasis this becomes \(\sum\lambda_iy_i^2\) — no cross terms. So the signs of the eigenvalues decide everything:
Condition on eigenvalues
Name
Level set \(Q=1\)
all \(\lambda_i > 0\)
positive definite
ellipse / ellipsoid
all \(\lambda_i \ge 0\)
positive semidefinite
degenerate (cylinder)
mixed signs
indefinite
hyperbola (saddle)
all \(\lambda_i < 0\)
negative definite
empty
InteractiveLevel curves of xᵀAxthe eigenvectors are the axes
eigenvalues —type —axis directions —
The contours of \(\mathbf x^{T}A\mathbf x\) are ellipses when both eigenvalues are positive, hyperbolas when the signs differ. The principal axes always lie along the eigenvectors, and the semi-axis lengths are \(1/\sqrt{\lambda_i}\) — small eigenvalue, long axis. Slide the off-diagonal \(b\) and the ellipse tilts: the cross term \(2bxy\) is precisely the tilt, and diagonalizing removes it by rotating to the eigenbasis. That rotation is the principal axis theorem, and it is also what PCA does to data.
Worked example · classify a quadratic form
Classify \(Q(x,y) = 5x^2 + 4xy + 5y^2\) and find its principal axes.
STEP 1
Write the symmetric matrix — the cross-term coefficient is split between the two off-diagonal entries:
\[ A = \begin{bmatrix}5&2\\2&5\end{bmatrix} \]
STEP 2
Eigenvalues from \(\operatorname{tr} = 10\), \(\det = 21\):
Both positive ⟹ positive definite; the level curves are ellipses and \(Q(\mathbf x) > 0\) for every \(\mathbf x\ne\mathbf 0\).
STEP 4
Eigenvectors: for \(\lambda=7\), \(\begin{bmatrix}-2&2\\2&-2\end{bmatrix}\) gives \((1,1)\); for \(\lambda=3\), \((1,-1)\). Orthogonal ✓
STEP 5
In rotated coordinates \(u,v\) along those axes, \(Q = 7u^2 + 3v^2\) — no cross term. The ellipse \(Q=1\) has semi-axes \(1/\sqrt7\) along \((1,1)\) and \(1/\sqrt3\) along \((1,-1)\): shortest in the direction of the largest eigenvalue. Check at \((1,1)\): \(5+4+5 = 14\), and \(7u^2\) with \(u = \sqrt2\) gives \(7\cdot2 = 14\) ✓
③Practice
1
Write the symmetric matrix for \(Q(x,y) = 3x^2 - 6xy + 2y^2\).
Hint 1Diagonal entries are the pure square coefficients.
Hint 2Split the cross coefficient in half between the two off-diagonal slots.
\(\det A = 6 - 9 = -3 < 0\), so the eigenvalues have opposite signs — indefinite, a saddle. For \(2\times2\) forms the determinant sign alone decides indefiniteness, no eigenvalue computation needed.
2
Is \(A = \begin{bmatrix}2&1\\1&2\end{bmatrix}\) positive definite? Give two arguments.
Hint 1Check the eigenvalues.
Hint 2Or complete the square in \(\mathbf x^{T}A\mathbf x\).
Solution
STEP 1 · eigenvalue argument
\(\lambda = 3, 1\) (module E1 problem 2). Both positive ⟹ positive definite ✓
A sum of squares with positive coefficients, zero only when \(y=0\) and \(x = 0\) ⟹ positive definite ✓
STEP 4 · a third test — leading minors
Sylvester's criterion: \(a_{11} = 2 > 0\) and \(\det A = 3 > 0\) ⟹ positive definite ✓
STEP 5 · why three tests
Eigenvalues are the most informative but the most work; completing the square is essentially the LDL factorization (positive pivots ⟺ positive definite); leading minors are the fastest hand check. All three are equivalent, and each is the natural one in a different context.
3
Prove that the eigenvalues of a real symmetric matrix are real.
Hint 1Start from \(A\mathbf v = \lambda\mathbf v\) and multiply by the conjugate transpose \(\bar{\mathbf v}^{T}\).
Hint 2Show the resulting scalar equals its own conjugate.
Solution
STEP 1 · set up
Let \(A\mathbf v = \lambda\mathbf v\) with \(\mathbf v\ne\mathbf 0\), possibly complex. Multiply on the left by \(\bar{\mathbf v}^{T}\):
\[ \bar{\mathbf v}^{T}A\mathbf v = \lambda\,\bar{\mathbf v}^{T}\mathbf v \]
STEP 2 · the right-hand side is positive
\[ \bar{\mathbf v}^{T}\mathbf v = \sum_i |v_i|^2 > 0 \]
STEP 3 · the left-hand side is real
Take the conjugate transpose of the scalar \(\bar{\mathbf v}^{T}A\mathbf v\). Since \(A\) is real and symmetric, \(\bar A^{T} = A\), so
\[ \overline{\bar{\mathbf v}^{T}A\mathbf v} = \bar{\mathbf v}^{T}A\mathbf v \]
— a number equal to its own conjugate is real.
STEP 4 · conclude
\(\lambda\) is a real number divided by a positive real number, hence real ∎
STEP 5 · where symmetry was essential
Step 3 used \(A = \bar A^{T}\) — drop it and the argument collapses, as the rotation matrix of module E1 problem 3 shows with eigenvalues \(\pm i\). The same proof works for complex Hermitian matrices, which is why quantum-mechanical observables (Hermitian operators) always have real measured values.
4
Show that eigenvectors of a symmetric matrix for distinct eigenvalues are orthogonal.
Hint 1Compute \(\mathbf v_1^{T}A\mathbf v_2\) two different ways.
\(\lambda_1\ne\lambda_2\), so \(\mathbf v_1\cdot\mathbf v_2 = 0\) ∎
STEP 5 · repeated eigenvalues
The argument says nothing when \(\lambda_1=\lambda_2\), but the spectral theorem still guarantees an orthonormal basis within each eigenspace — apply Gram–Schmidt (module S4) there. Contrast \(\begin{bmatrix}4&1\\2&3\end{bmatrix}\) from E1: not symmetric, and its eigenvectors \((1,1)\), \((1,-2)\) have dot product \(-1 \ne 0\).
5
Classify the conic \(x^2 + 4xy + y^2 = 1\).
Hint 1Build the symmetric matrix and find its eigenvalues.
Hint 2Opposite signs mean a hyperbola.
Solution
STEP 1 · the matrix
\[ A = \begin{bmatrix}1&2\\2&1\end{bmatrix} \]
Opposite signs ⟹ indefinite ⟹ the conic is a hyperbola.
STEP 4 · principal axes
For \(\lambda=3\): \((1,1)\). For \(\lambda=-1\): \((1,-1)\). In those coordinates the equation is
\[ 3u^2 - v^2 = 1 \]
STEP 5 · verify with a point
Along \((1,-1)\), take \((t,-t)\): \(t^2 - 4t^2 + t^2 = -2t^2 < 0\), never equal to 1 — that is the direction the hyperbola opens away from. Along \((1,1)\): \(t^2+4t^2+t^2 = 6t^2 = 1\) at \(t = 1/\sqrt6\) ✓ The vertices sit on the \(\lambda > 0\) axis.
6
Show that \(A^{T}A\) is always symmetric and positive semidefinite, for any \(A\).
Hint 1Transpose the product.
Hint 2For semidefiniteness, look at \(\mathbf x^{T}A^{T}A\mathbf x\) as a squared length.
STEP 2 · the quadratic form
\[ \mathbf x^{T}A^{T}A\mathbf x = (A\mathbf x)^{T}(A\mathbf x) = \|A\mathbf x\|^2 \ \ge 0 \ ✓ \]
STEP 3 · when it is strictly positive
\(\|A\mathbf x\|^2 = 0\) only when \(A\mathbf x=\mathbf 0\). So \(A^{T}A\) is positive definite exactly when \(\operatorname{null}(A) = \{\mathbf 0\}\), i.e. \(A\) has independent columns.
STEP 4 · consequences for the eigenvalues
All eigenvalues of \(A^{T}A\) are real and \(\ge0\). Their square roots are the singular values of \(A\) — the entire basis of module E4.
STEP 5 · why this matters
It is exactly the condition under which the least-squares normal equations \(A^{T}A\hat{\mathbf x}=A^{T}\mathbf b\) have a unique solution (module S5). And since \(A^TA\) is positive definite, the Cholesky factorization applies — the fastest stable way to solve those equations when conditioning permits.
7
The Hessian of \(f(x,y) = x^2 + 3xy + y^2\) at the origin — classify the critical point.
Hint 1Compute the second partial derivatives.
Hint 2The definiteness of the Hessian classifies the critical point.
STEP 2 · the Hessian
\[ H = \begin{bmatrix}2&3\\3&2\end{bmatrix} \]
STEP 3 · eigenvalues
\(\operatorname{tr}=4\), \(\det = 4-9 = -5\):
\[ \lambda = 5,\ -1 \]
STEP 4 · classify
Mixed signs ⟹ indefinite ⟹ the origin is a saddle point.
STEP 5 · see it directly
Along \((1,1)\): \(f(t,t) = 5t^2 > 0\), a minimum in that direction. Along \((1,-1)\): \(f(t,-t) = -t^2 < 0\), a maximum. The function rises along one eigendirection and falls along the other — the geometry of a saddle, with the eigenvectors giving the exact uphill and downhill axes. The second-derivative test of multivariable calculus is a definiteness test.
8
Write the spectral decomposition \(A = \lambda_1\mathbf q_1\mathbf q_1^{T} + \lambda_2\mathbf q_2\mathbf q_2^{T}\) for \(A = \begin{bmatrix}2&1\\1&2\end{bmatrix}\).
Hint 1Normalize the eigenvectors first.
Hint 2Each \(\mathbf q\mathbf q^{T}\) is a rank-1 projection matrix.
The two projections sum to \(I\) ✓ (they are complementary), and each satisfies \(P^2=P\) ✓
STEP 5 · how to read it
\(A\) decomposes space into perpendicular directions and scales each by its eigenvalue — \(A\mathbf x = 3(\text{part along }\mathbf q_1) + 1(\text{part along }\mathbf q_2)\). Truncating such a sum to its largest terms is exactly low-rank approximation, and for a symmetric matrix it is optimal. The SVD (module E4) extends this to every matrix, square or not.
9
Why is the covariance matrix of a data set always symmetric positive semidefinite, and what does its largest eigenvector mean?
Hint 1Write it as \(\frac{1}{n-1}X^{T}X\) for centred data \(X\).
Hint 2Interpret \(\mathbf u^{T}C\mathbf u\) for a unit vector \(\mathbf u\).
Solution
STEP 1 · the form of C
With centred data in the rows of \(X\),
\[ C = \frac{1}{n-1}X^{T}X \]
which is symmetric positive semidefinite by problem 6.
STEP 2 · what the quadratic form measures
For a unit vector \(\mathbf u\),
\[ \mathbf u^{T}C\mathbf u = \frac{1}{n-1}\|X\mathbf u\|^2 = \text{variance of the data projected onto } \mathbf u \]
Variance is never negative — the statistical reason for semidefiniteness.
STEP 3 · maximize it
The Rayleigh quotient \(\mathbf u^{T}C\mathbf u\) over unit vectors is maximized at the top eigenvector, with value \(\lambda_{\max}\).
STEP 4 · the interpretation
The largest eigenvector is the first principal component — the direction of greatest spread in the data. Its eigenvalue is the variance along that direction, and the eigenvalues sum to the total variance (the trace).
STEP 5 · why PCA works
The spectral theorem guarantees the principal directions are orthogonal, so the components are uncorrelated and the variance splits cleanly among them. Keeping the top \(k\) gives the best possible \(k\)-dimensional summary. In practice you compute it from the SVD of \(X\) rather than forming \(C\) — same answer, better conditioning (module S4 problem 9).
Part IV · Module 4 Eigenvalues & beyond
Singular value decomposition
Eigenvalues need a square matrix and may not exist usefully. The SVD has neither restriction: every matrix, of any shape, factors into rotate–stretch–rotate. It is the most powerful single tool in applied linear algebra.
①The factorization
SVD
\[ A = U\Sigma V^{T}, \qquad U \ (m\times m) \ \text{orthogonal}, \quad V \ (n\times n) \ \text{orthogonal}, \quad \Sigma \ (m\times n) \ \text{diagonal} \ge 0 \]
The singular values \(\sigma_1\ge\sigma_2\ge\cdots\ge0\) sit on \(\Sigma\)'s diagonal. Where they come from:
Read \(A = U\Sigma V^{T}\) right to left as three geometric acts: \(V^{T}\) rotates the input into the right frame, \(\Sigma\) stretches each axis by \(\sigma_i\), \(U\) rotates the result into place. Every linear map is a rotation, a stretch, and another rotation.
InteractiveEvery matrix maps a circle to an ellipserotate, stretch, rotate
σ₁, σ₂ —condition σ₁/σ₂ —rank —
The unit circle always becomes an ellipse — never anything else, for any matrix at all. Its semi-axes are exactly \(\sigma_1\) and \(\sigma_2\), and their directions are the columns of \(U\); the pre-images of those axes on the circle are the columns of \(V\). Step through the stages to watch the rotate–stretch–rotate happen one factor at a time. Drive the determinant to zero and \(\sigma_2\to0\): the ellipse flattens to a segment, the rank drops to 1, and the condition number blows up. Unlike eigenvectors, these axes exist and stay perpendicular for every matrix.
Worked example · SVD of a 2×2
Find the SVD of \(A = \begin{bmatrix}3&0\\4&5\end{bmatrix}\).
Check: \(\mathbf u_1\cdot\mathbf u_2 = \frac{3-3}{10} = 0\) ✓ and \(\sigma_1\sigma_2 = 3\sqrt5\cdot\sqrt5 = 15 = |\det A|\) ✓ The condition number is \(\sigma_1/\sigma_2 = 3\) — well conditioned. Note \(A\) is not symmetric and its eigenvectors are not orthogonal, yet the singular vectors are, on both sides.
②Practice
1
Find the singular values of \(A = \begin{bmatrix}2&0\\0&3\end{bmatrix}\) and of \(\begin{bmatrix}2&0\\0&-3\end{bmatrix}\).
The eigenvalues differ: \(\{2,3\}\) versus \(\{2,-3\}\). The singular values do not.
STEP 4 · why
Singular values measure stretching magnitude only. The sign flip is absorbed into \(U\) — the reflection becomes part of the rotation factor.
STEP 5 · the general relationship
For a symmetric matrix, \(\sigma_i = |\lambda_i|\). For a general matrix there is no simple relation at all: \(\begin{bmatrix}0&1\\0&0\end{bmatrix}\) has both eigenvalues 0 but singular values 1 and 0. Singular values see the geometry; eigenvalues see the dynamics.
2
Find the singular values of \(A = \begin{bmatrix}1&1\\0&0\end{bmatrix}\) and state the rank.
Hint 1Form \(A^{T}A\) and find its eigenvalues.
Hint 2A zero singular value signals rank deficiency.
One nonzero singular value ⟹ \(\operatorname{rank}(A) = 1\) ✓ (the rows are \((1,1)\) and \((0,0)\)).
STEP 5 · the geometry and the numerics
The unit circle maps to a segment of half-length \(\sqrt2\) — a degenerate ellipse. In practice, rank is determined by counting singular values above a tolerance, because measured data never gives exactly zero. That makes the SVD the reliable rank test, where elimination on noisy data would report full rank.
3
Show that \(\|A\|_2 = \sigma_1\), where \(\|A\|_2 = \max_{\|\mathbf x\|=1}\|A\mathbf x\|\).
Hint 1Substitute \(A = U\Sigma V^{T}\) and use that \(U\) and \(V\) preserve length.
Hint 2Then maximize \(\|\Sigma\mathbf y\|\) over unit \(\mathbf y\).
Let \(\mathbf y = V^{T}\mathbf x\). Because \(V^{T}\) is orthogonal, \(\|\mathbf y\| = \|\mathbf x\| = 1\), and \(\mathbf y\) ranges over all unit vectors.
Equality at \(\mathbf y = \mathbf e_1\), i.e. \(\mathbf x = \mathbf v_1\). So \(\|A\|_2 = \sigma_1\) ∎
STEP 5 · the companion facts
The same argument gives \(\min_{\|\mathbf x\|=1}\|A\mathbf x\| = \sigma_n\), so the condition number \(\kappa = \sigma_1/\sigma_n\) is the ratio of worst-case stretch to worst-case squash — exactly how much a relative error in \(\mathbf b\) can be amplified in the solution of \(A\mathbf x=\mathbf b\).
4
Why does every matrix have an SVD, while not every matrix has an eigendecomposition?
Hint 1The SVD is built from \(A^{T}A\) — what kind of matrix is that?
Hint 2Apply the spectral theorem.
Solution
STEP 1 · the key observation
\(A^{T}A\) is symmetric positive semidefinite for any \(A\), of any shape (module E3 problem 6).
STEP 2 · apply the spectral theorem
Symmetric matrices are always orthogonally diagonalizable with real, non-negative eigenvalues here. That gives \(V\) and the \(\sigma_i = \sqrt{\lambda_i}\) unconditionally.
STEP 3 · build U
Set \(\mathbf u_i = A\mathbf v_i/\sigma_i\) for \(\sigma_i>0\); these come out orthonormal automatically, and any orthonormal completion fills out the rest of \(U\).
STEP 4 · why eigendecomposition can fail
It requires \(n\) independent eigenvectors of \(A\) itself, which defective matrices lack (module E2 problem 2). It also requires \(A\) to be square, and may force complex numbers.
STEP 5 · the trade-off
The SVD uses two different bases — \(V\) on the input side, \(U\) on the output — which is what buys the guarantee. The eigendecomposition insists on one basis serving both roles, and that is exactly the demand that sometimes cannot be met. Two frames always work; one frame sometimes does not.
5
Write \(A = \begin{bmatrix}3&0\\4&5\end{bmatrix}\) as a sum of rank-1 matrices using its SVD, and give the best rank-1 approximation.
Hint 1The worked example above has all the pieces.
Hint 2Best rank-1 = keep only the largest singular value's term.
STEP 2 · first term
\[ \sigma_1\mathbf u_1\mathbf v_1^{T} = \frac{3\sqrt5}{\sqrt{20}}\begin{bmatrix}1\\3\end{bmatrix}\begin{bmatrix}1&1\end{bmatrix} = \frac32\begin{bmatrix}1&1\\3&3\end{bmatrix} = \begin{bmatrix}1.5&1.5\\4.5&4.5\end{bmatrix} \]
STEP 3 · second term
\[ \sigma_2\mathbf u_2\mathbf v_2^{T} = \frac{\sqrt5}{\sqrt{20}}\begin{bmatrix}3\\-1\end{bmatrix}\begin{bmatrix}1&-1\end{bmatrix} = \frac12\begin{bmatrix}3&-3\\-1&1\end{bmatrix} = \begin{bmatrix}1.5&-1.5\\-0.5&0.5\end{bmatrix} \]
STEP 4 · verify the sum
\[ \begin{bmatrix}1.5&1.5\\4.5&4.5\end{bmatrix} + \begin{bmatrix}1.5&-1.5\\-0.5&0.5\end{bmatrix} = \begin{bmatrix}3&0\\4&5\end{bmatrix} = A \ ✓ \]
STEP 5 · the best rank-1 approximation
Keep the first term: \(A_1 = \begin{bmatrix}1.5&1.5\\4.5&4.5\end{bmatrix}\). The error is \(\|A - A_1\|_2 = \sigma_2 = \sqrt5 \approx 2.24\), and the Eckart–Young theorem says no other rank-1 matrix does better. Truncating the SVD is provably the optimal low-rank compression — the theoretical foundation of image compression, recommender systems, and latent semantic analysis.
6
How much storage does a rank-\(k\) approximation of a \(1000\times1000\) image save at \(k=50\)?
Hint 1Each rank-1 term needs one \(\mathbf u\), one \(\mathbf v\), and one \(\sigma\).
\(\mathbf u_i\) has 1000 entries, \(\mathbf v_i\) has 1000, plus one \(\sigma_i\): 2001 numbers.
STEP 3 · total for k = 50
\[ 50\times2001 = 100{,}050 \ \text{numbers} \]
STEP 4 · the ratio
\[ \frac{100{,}050}{1{,}000{,}000} \approx 10\% \]
— a 10× reduction.
STEP 5 · why the quality holds up
Natural images have singular values that decay rapidly, so the first 50 terms carry most of the energy \(\sum\sigma_i^2\). The discarded terms are dominated by fine texture and noise. The break-even point is \(k = mn/(m+n+1) \approx 500\) here, so any \(k\) below that saves space — and SVD compression is the conceptual ancestor of JPEG, which uses a fixed cosine basis instead of a data-dependent one for speed.
7
Define the pseudoinverse \(A^{+}\) via the SVD, and explain what \(A^{+}\mathbf b\) gives when \(A\mathbf x=\mathbf b\) has no solution, or infinitely many.
Hint 1Invert what you can: reciprocate the nonzero singular values, leave the zeros alone.
Hint 2Think about least squares and minimum norm.
Solution
STEP 1 · the definition
\[ A = U\Sigma V^{T} \ \Longrightarrow\ A^{+} = V\Sigma^{+}U^{T} \]
where \(\Sigma^{+}\) transposes \(\Sigma\) and replaces each \(\sigma_i>0\) by \(1/\sigma_i\), leaving zeros as zeros.
STEP 2 · the overdetermined case
If no exact solution exists, \(A^{+}\mathbf b\) is the least-squares solution — the same \(\hat{\mathbf x}\) the normal equations give when \(A\) has full column rank, but defined even when it does not.
STEP 3 · the underdetermined case
If infinitely many solutions exist, \(A^{+}\mathbf b\) picks the one of minimum norm — it puts nothing in the null space, since \(\Sigma^{+}\) zeroes those directions.
STEP 4 · when A is invertible
All \(\sigma_i > 0\) and \(A^{+} = A^{-1}\) exactly — the pseudoinverse extends the inverse rather than replacing it.
STEP 5 · the practical caution
Tiny singular values become huge reciprocals, amplifying noise. The standard remedy is truncation: set \(1/\sigma_i\) to zero whenever \(\sigma_i\) falls below a tolerance. That is regularization by another name, and it is closely related to ridge regression (module S5 problem 9).
8
Show that \(A\) and \(A^{T}\) have the same nonzero singular values.
Hint 1Transpose the SVD.
Hint 2What are \(U\) and \(V\) for \(A^{T}\)?
Solution
STEP 1 · transpose the factorization
\[ A = U\Sigma V^{T} \ \Longrightarrow\ A^{T} = V\Sigma^{T}U^{T} \]
STEP 2 · recognize it as an SVD
\(V\) and \(U\) are orthogonal and \(\Sigma^{T}\) is diagonal with non-negative entries — so this is the SVD of \(A^{T}\), with the roles of the two orthogonal factors swapped.
STEP 3 · compare diagonals
\(\Sigma^{T}\) has the same nonzero entries as \(\Sigma\), merely reshaped from \(m\times n\) to \(n\times m\) ∎
STEP 4 · an immediate corollary
Counting nonzero singular values gives \(\operatorname{rank}(A) = \operatorname{rank}(A^{T})\) — a one-line proof that row rank equals column rank (module S1 problem 4).
STEP 5 · the underlying reason
\(A^{T}A\) and \(AA^{T}\) always share their nonzero eigenvalues, even when they have different sizes. \(A\) maps the row space isomorphically onto the column space, and \(A^{T}\) maps it back — the stretching factors are the same in both directions.
9
Compare eigenvalues and singular values: when does each apply, and what does each tell you?
Hint 1Think about iteration versus one-shot geometry.
Hint 2Which is stable under perturbation?
Solution
STEP 1 · the comparison
Eigenvalues
Singular values
Requires
square matrix
any shape
Always exist (usefully)
no — defective matrices
yes, always
Values
may be complex
real and \(\ge0\)
Vectors
generally not orthogonal
always orthonormal
Perturbation
can be wildly sensitive
well conditioned
STEP 2 · use eigenvalues for dynamics
Anything involving \(A^{k}\), \(e^{At}\), or repeated application: stability of ODEs, Markov chains, vibration modes, iterative-method convergence. The question "what happens in the long run?" is an eigenvalue question.
STEP 3 · use singular values for geometry
Rank, norms, conditioning, low-rank approximation, least squares, PCA. The question "how much does this map stretch, and in which directions?" is a singular value question.
STEP 4 · where they coincide
For symmetric positive definite matrices they are equal. For symmetric matrices, \(\sigma_i = |\lambda_i|\). Away from symmetry they can be completely unrelated.
STEP 5 · the practical default
If you are unsure, compute the SVD: it always exists, it never lies about rank, and it degrades gracefully with noise. Reach for eigenvalues when the problem genuinely involves iterating or exponentiating the matrix — that is module E5.
Part IV · Module 5 Eigenvalues & beyond
Applications: Markov chains & systems of ODEs
Two payoffs that justify the whole eigenvalue apparatus. Discrete time gives Markov chains and steady states; continuous time gives \(\mathbf x' = A\mathbf x\) and the stability of every linear system you will meet.
Discrete time asks about \(|\lambda|\) versus 1; continuous time asks about \(\operatorname{Re}\lambda\) versus 0. The bridge is \(\lambda_{\text{discrete}} = e^{\lambda_{\text{cts}}\Delta t}\).
InteractiveConvergence to a steady statestart anywhere; end up the same place
eigenvalues —steady state —step k —
Several starting distributions are iterated simultaneously. They all converge to the same steady state, at a rate set by the second eigenvalue \(\lambda_2 = 1 - p - q\): the closer \(|\lambda_2|\) is to 1, the slower the mixing. Push both transition rates toward zero and convergence crawls — the chain barely moves between states. Switch to the ODE mode and the same matrix data drives a phase portrait instead, so you can compare the discrete and continuous stability criteria side by side.
Worked example · a two-state Markov chain
Each year 30% of city residents move to the suburbs and 20% of suburb residents move to the city. Find the long-run distribution.
STEP 1
Build the transition matrix with state order (city, suburb):
\[ P = \begin{bmatrix}0.7&0.2\\0.3&0.8\end{bmatrix} \]
Columns sum to 1 ✓
STEP 2
Find the \(\lambda=1\) eigenvector by solving \((P-I)\mathbf x=\mathbf 0\):
Check: \(P(0.4,0.6) = (0.28+0.12,\ 0.12+0.48) = (0.4,0.6)\) ✓ In the long run 40% live in the city, regardless of the initial split. The second eigenvalue is \(\operatorname{tr}-1 = 1.5-1 = 0.5\), so each year the deviation from steady state halves — about 10 years to settle within 0.1%.
③Practice
1
Find the steady state of \(P = \begin{bmatrix}0.9&0.5\\0.1&0.5\end{bmatrix}\).
Hint 1Solve \((P-I)\mathbf x = \mathbf 0\).
Hint 2Then scale so the entries sum to 1.
Solution
STEP 1 · form P − I
\[ \begin{bmatrix}-0.1&0.5\\0.1&-0.5\end{bmatrix} \]
\(P(5/6,1/6) = (0.75+0.0833,\ 0.0833+0.0833) = (0.833, 0.167)\) ✓ The second eigenvalue is \(\operatorname{tr}-1 = 1.4-1 = 0.4\), so the transient decays by 60% per step — fast mixing.
2
Show that \(\lambda=1\) is always an eigenvalue of a column-stochastic matrix.
Hint 1Columns summing to 1 says something about \(\mathbf 1^{T}P\).
Hint 2\(A\) and \(A^{T}\) share eigenvalues.
Solution
STEP 1 · translate the column condition
Each column summing to 1 means, with \(\mathbf 1 = (1,\dots,1)^{T}\),
so \(\mathbf 1\) is an eigenvector of \(P^{T}\) with eigenvalue 1.
STEP 3 · transfer to P
\(P\) and \(P^{T}\) have the same characteristic polynomial (since \(\det(M) = \det(M^{T})\)), hence the same eigenvalues. So \(\lambda=1\) is an eigenvalue of \(P\) ∎
STEP 4 · but not the same eigenvector
\(P^{T}\)'s eigenvector is \(\mathbf 1\); \(P\)'s is the steady-state distribution, which is generally not uniform. Same eigenvalue, different vectors.
STEP 5 · why probability is conserved
\(\mathbf 1^{T}\mathbf x_{k+1} = \mathbf 1^{T}P\mathbf x_k = \mathbf 1^{T}\mathbf x_k\) — the entries always sum to 1. A steady state must therefore exist, since the dynamics are confined to the bounded simplex of probability vectors.
Purely imaginary ⟹ a centre: closed elliptical orbits, neither growing nor decaying.
STEP 4 · identify the system
The equations are \(x' = y\), \(y' = -4x\), i.e. \(x'' + 4x = 0\) — simple harmonic motion with \(\omega = 2\), period \(\pi\).
STEP 5 · why centres are delicate
\(\operatorname{Re}\lambda = 0\) is the exact boundary between stable and unstable spirals, so any perturbation — a small damping term \(-\varepsilon y\) — pushes the eigenvalues off the imaginary axis and converts the centre into a spiral. Physically that is friction turning a perfect oscillator into a decaying one, and mathematically it is why centres are called non-hyperbolic and resist linearization arguments.
5
Two competing species: \(x' = 3x - y\), \(y' = -x + 3y\). Find the general solution and describe the long-run behaviour.
Hint 1The matrix is symmetric — expect real eigenvalues and orthogonal eigenvectors.
Hint 2Trace 6, determinant 8.
Solution
STEP 1 · the matrix and its eigenvalues
\[ A = \begin{bmatrix}3&-1\\-1&3\end{bmatrix}, \qquad \lambda^2-6\lambda+8 = 0 \ \Longrightarrow\ \lambda = 4,\ 2 \]
STEP 2 · eigenvectors
For \(\lambda=4\): \(\begin{bmatrix}-1&-1\\-1&-1\end{bmatrix}\) gives \((1,-1)\). For \(\lambda=2\): \(\begin{bmatrix}1&-1\\-1&1\end{bmatrix}\) gives \((1,1)\). Orthogonal ✓ (symmetric matrix).
Both eigenvalues are positive ⟹ an unstable node: everything grows. The \(e^{4t}\) term dominates, so trajectories align with \((1,-1)\) — the imbalance direction.
STEP 5 · the interpretation
Unless \(c_1 = 0\) exactly (which requires starting on the line \(x=y\)), one species runs away positive and the other negative — competitive exclusion, in the linearized model. The balanced state is unstable: it is a solution, but the slightest perturbation grows at \(e^{4t}\). Real ecological models add nonlinear saturation, but the linearization near equilibrium is exactly this computation.
6
Why is a Markov chain's steady state independent of the starting distribution?
Hint 1Expand \(\mathbf x_0\) in the eigenbasis.
Hint 2What happens to each term after \(k\) steps?
For a regular chain, \(|\lambda_j| < 1\) for \(j\ge2\), so every term after the first decays:
\[ \mathbf x_k \to c_1\mathbf v_1 \]
STEP 4 · pin down c₁
Probability is conserved, so the entries of \(\mathbf x_k\) always sum to 1. That forces \(c_1\mathbf v_1\) to be \(\mathbf v_1\) normalized to sum 1 — the same limit for every valid \(\mathbf x_0\) ∎
STEP 5 · when it fails
Regularity matters. A chain that deterministically alternates, \(P = \begin{bmatrix}0&1\\1&0\end{bmatrix}\), has \(\lambda_2 = -1\), so \((1,0)\) oscillates forever without converging — a periodic chain. Reducible chains (with unreachable groups of states) have \(\lambda=1\) repeated and multiple steady states, and the limit then does depend on where you started.
7
Compute \(e^{At}\) for \(A = \begin{bmatrix}2&0\\0&3\end{bmatrix}\) and for \(A = \begin{bmatrix}0&1\\0&0\end{bmatrix}\).
Hint 1For the diagonal one, exponentiate each entry.
Hint 2For the second, use the series — it terminates.
Solution
STEP 1 · diagonal case
\[ e^{At} = \begin{bmatrix}e^{2t}&0\\0&e^{3t}\end{bmatrix} \]
since \(A^{k}\) is diagonal with entries \(2^k, 3^k\), and the series sums entrywise.
STEP 3 · the series terminates
\[ e^{At} = I + At + \tfrac{(At)^2}{2!} + \cdots = I + At \]
STEP 4 · write it out
\[ e^{At} = \begin{bmatrix}1&t\\0&1\end{bmatrix} \]
STEP 5 · check and interpret
\(\frac{d}{dt}e^{At} = \begin{bmatrix}0&1\\0&0\end{bmatrix} = A\,e^{At}\) ✓ and \(e^{A\cdot0}=I\) ✓ The polynomial-in-\(t\) growth is the hallmark of a defective matrix; a diagonalizable one gives pure exponentials. Note also \(e^{A}e^{B} \ne e^{A+B}\) unless \(A\) and \(B\) commute — the single most common error with matrix exponentials.
8
A web has 3 pages: page 1 links to 2 and 3; page 2 links to 3; page 3 links to 1. Set up the PageRank matrix and find the ranking.
Hint 1Column \(j\) spreads page \(j\)'s rank evenly among the pages it links to.
Hint 2Find the \(\lambda=1\) eigenvector.
Solution
STEP 1 · build the link matrix
Page 1 splits its rank between 2 and 3; page 2 gives all to 3; page 3 gives all to 1:
\[ P = \begin{bmatrix}0&0&1\\ \tfrac12&0&0\\ \tfrac12&1&0\end{bmatrix} \]
STEP 5 · read the ranking and note the real algorithm
Pages 1 and 3 tie for first, page 2 is last — it receives only half of page 1's rank, while page 3 receives from both. Real PageRank adds a damping factor: \(M = 0.85P + 0.15\frac{1}{n}\mathbf 1\mathbf 1^{T}\), which guarantees regularity (handling dangling pages and disconnected components) and speeds convergence, since \(|\lambda_2| \le 0.85\).
9
A mass-spring system gives \(\mathbf x'' = -K\mathbf x\) with \(K = \begin{bmatrix}2&-1\\-1&2\end{bmatrix}\). Find the natural frequencies and normal modes.
Hint 1Try \(\mathbf x = \mathbf v\cos(\omega t)\) and see what equation \(\mathbf v\) must satisfy.
Hint 2You get \(K\mathbf v = \omega^2\mathbf v\).
Solution
STEP 1 · substitute the ansatz
With \(\mathbf x = \mathbf v\cos(\omega t)\), \(\mathbf x'' = -\omega^2\mathbf v\cos(\omega t)\), so the equation becomes
\[ -\omega^2\mathbf v = -K\mathbf v \ \Longrightarrow\ K\mathbf v = \omega^2\mathbf v \]
an eigenvalue problem with \(\lambda = \omega^2\).
STEP 2 · eigenvalues of K
\(\operatorname{tr}=4\), \(\det=3\), so \(\lambda = 3, 1\) and
\[ \omega_1 = 1, \qquad \omega_2 = \sqrt3 \]
STEP 3 · the modes
For \(\lambda=1\): \(\begin{bmatrix}1&-1\\-1&1\end{bmatrix}\mathbf v = \mathbf 0\) gives \((1,1)\). For \(\lambda=3\): \(\begin{bmatrix}-1&-1\\-1&-1\end{bmatrix}\mathbf v=\mathbf 0\) gives \((1,-1)\).
STEP 4 · interpret them
\((1,1)\) at \(\omega=1\): both masses move together — the slow, in-phase mode, which barely stretches the coupling spring. \((1,-1)\) at \(\omega=\sqrt3\): the masses move oppositely — the fast, out-of-phase mode, which stretches it hard.
STEP 5 · why this is the whole subject in one problem
\(K\) is symmetric, so the modes are orthogonal and every motion decomposes uniquely into them:
Diagonalizing decouples the oscillators. The same idea, in infinite dimensions, gives the standing waves of a vibrating string and the eigenfunction expansions of the PDE Launchpad — and it is why engineers compute eigenvalues before trusting a structure near a driving frequency.