Interactive Linear Algebra · Rank Theorem
Dan Margalit & Joseph Rabinoff · Georgia Tech · Open textbook · §2.9
Read §2.4 on solution sets, then §2.9 on the rank theorem. Identify which side counts input coordinates.
Open the sourceRank and the information that disappears
A kernel is a precise inventory of invisible changes.
Prerequisites: 08 · A matrix is an action
Understand
Objectives
- Exhibit two distinct inputs with the same output under the collapse matrix.
- Use rank plus nullity to account for every input direction.
- Show why a 3×2 full-column-rank matrix need not lose input information.
Start with something you can see
In the matrix lab, choose Collapse. Its matrix sends the input (2,1) to (4,0). Before checking, predict what it does to the different input (0,2). Both land at (4,0). This is a collision: two inputs, one output. The drawing becomes a line, but the collision itself is the evidence that this map has forgotten something.
A map can also have more output coordinates than input coordinates without losing any input distinctions. Count independent directions, not just entries in a coordinate list. The short passage on nullspace in the MIT lecture begins at 28:16. [1]
Give the idea a precise name
Let A be a matrix mapping input vectors with n coordinates to output vectors. Its image is the set of outputs it can produce. The rank of A is the number of independent directions in that image. Its kernel, written ker A, is the set of inputs x for which Ax is the zero output. The nullity is the number of independent directions in that kernel, written dim(ker A). For a linear map, the rank–nullity theorem states:
rank(A) + dim(ker A) = n
Read this as “rank of A plus dimension of the kernel of A equals the number of input coordinates.” Here n counts input coordinates, even if the output has a different number. If k belongs to the kernel, then Ak=0, so A(x+k)=Ax: adding an invisible change k creates a collision. A fiber is the set of all inputs with one specified output; it can also be empty when that output is unreachable.
Work one small world
The lab’s Collapse matrix is A=[[1,2],[0,0]]. It sends (x,y) to (x+2y,0). The distinct inputs (2,1) and (0,2) both give (4,0); their difference (2,−1) goes to zero. Every input (4−2t,t), for any real number t, gives (4,0). There is one independent output direction and one invisible input direction: rank 1 + nullity 1 = 2 input coordinates.
Try a fresh matrix B=[[2,1],[4,2]]. The inputs (3,1) and (4,−1) both give (7,14); their difference (1,−2) is in its kernel. But (7,15) is not an output of B: the second coordinate must be twice the first. A fiber need not contain anything. The longer MIT excerpt, 26:00–43:00, discusses nullspace solutions and their relation to columns. [2]
Counterexample to “a rectangular matrix loses information”: C=[[1,0],[0,1],[1,1]] has three output rows and two input columns. It sends (u,v) to (u,v,u+v). The first two outputs recover u and v, so no two distinct inputs collide. Its rank is 2 and its nullity is 0, despite its 3×2 shape. For another explanation of dependencies, nullspace and rank, begin the full MIT lecture at 12:45. [3]
THE BRIDGEThe kernel names precisely the input changes this observation cannot see. Later, hidden-state recovery will ask whether an additional measurement removes those collisions; try the same question for a map into three coordinates.
WHERE THIS IDEA STOPSFewer output coordinates can force a collision for a linear map on all inputs, but more output coordinates do not guarantee injectivity. Shape alone does not decide it. The lab uses floating-point rank, while these integer examples are exact.
Experiment
In the matrix lab choose Collapse, which sets A=[[1,2],[0,0]]. Predict the output of (2,1) and (0,2) before inspecting the displayed rank and nullity. The marked point is A(1,1), not either test input: compute the two test outputs using the shown entries. Change a matrix entry to restore rank 2, and predict whether any distinct inputs still collide.
Can you find a nonzero input that this map sends to zero? What happens if you add it to another input?
Check & explain
For B=[[2,1],[4,2]], what is the first coordinate of B(5,−2)?
Which claim about D=[[1,1],[0,1],[1,−1]] is correct?
- It must lose information because it is rectangular
- It is injective: the second output gives v and the first then gives u
- Its nullity is 1 because it has one extra row
Teach back
For the collapse map, give two distinct inputs with one output and name an assumption or extra measurement that separates them. Then transfer the question to a 3×2 map: is it injective, and how can you tell?
- Compute both outputs and a nonzero kernel vector.
- Read rank plus nullity using the input dimension, not the output size.
- Give an explicit restriction or added measurement and test whether it removes the collision.
Read deeper
18.06 · Linear Algebra
MIT OpenCourseWare · Gilbert Strang · Open course
Study the column space and nullspace lectures; solve Ax=0 for the lab matrix.
Open the sourceMathematics for Machine Learning
Deisenroth, Faisal & Ong · Freely readable textbook
Read §2.7 on kernel and image after the first worked collision.
Open the source6. Column Space and Nullspace
Gilbert Strang · MIT OpenCourseWare · Lecture excerpt · 26:00–43:00 of 46 min
Start at 26:00. Watch the short core 28:16–31:16; then the longer passage 26:00–43:00.
Open the source9. Independence, Basis, and Dimension
Gilbert Strang · MIT OpenCourseWare · Lecture · 50 min
Begin at 12:45 for dependencies, nullspace and rank in the full 50-minute lecture; return to the early material as needed.
Open the source