Flow Lab

Syllabus / Module 1: Linear Algebra, Reloaded

Lesson 1.3

Linear Systems, Kernel & Column Space

What Gaussian elimination was really doing: when Ax = b has solutions, the null space (kernel), column space, rank, and the rank–nullity theorem.

Written byClaude Opus

🌊
Why this matters for simulation: The pressure solve in an incompressible fluid solver is a giant Ax = b; its kernel (constant pressure) is why pressure is only defined up to a constant.

By the end of this lesson you can…

  • Read Ax = b as the question 'which input does the transformation A send to b?' and decide solvability by checking whether b lies in the column space.
  • Row reduce a matrix to (reduced) row echelon form by hand, identify pivots and free variables, and read off the rank.
  • Compute a basis for the kernel (null space) from the RREF and describe it geometrically.
  • State the rank–nullity theorem and use it to predict how many solutions a system can have.
  • Write the general solution of a consistent system as particular solution plus homogeneous solution.
  • Explain when a square matrix is invertible, compute 2×2 inverses and use Gauss–Jordan for larger ones.
  • Explain why the pressure Poisson matrix of a fluid solver is singular and how solvers cope.
On this page
·
  1. Ax⃗=b⃗A\vec x = \vec bAx=b is a question about a transformation
  2. Column space: every output you can reach
  3. Kernel: everything that gets squashed to zero
  4. General solution = particular + homogeneous
  5. Elimination, revisited
  6. Echelon forms, pivots and free variables
  7. Worked example: a 3×4 system done carefully
  8. Reading the kernel straight from the RREF
  9. Reading the column space and solvability
  10. Rank and the rank–nullity theorem
  11. Inverse matrices
  12. The 2×2 inverse
  13. Gauss–Jordan for larger matrices
  14. Fluids: the pressure solve and its kernel
  15. Code it yourself
  16. Practice problems
  17. Looking ahead
  18. Key Takeaways

Every implicit time step you will ever take, every pressure projection in a fluid solver, every steady-state heat calculation ends in the same line of code: solve Ax⃗=b⃗A\vec x = \vec b. Your first linear algebra course taught you the mechanics of that line: write the augmented matrix, eliminate, back-substitute. It probably never told you what the equation is asking, or why some systems have one answer, some have none, and some have infinitely many. In 1.2 Matrices as Transformations a matrix became a machine that moves space. This lesson reads Ax⃗=b⃗A\vec x = \vec b through that picture, and the two most important subspaces in linear algebra, the column space and the kernel, fall right out.

▶ Video What Ax = b is really asking: column space, kernel, and the shape of the solution setcaptions only
Transcript
  1. You have probably solved hundreds of linear systems by Gaussian elimination. Today we find out what those systems were actually asking.
  2. Last lesson, a matrix became a machine that moves every vector in the plane. So the equation A x equals b is really a question: which input vector does the transformation A send to the output b?
  3. For most matrices the answer is easy: exactly one input. The interesting cases, the ones your old course never explained, are when there is no answer at all, or infinitely many.
  4. Here is a matrix that will cause trouble. Its first column, one and a half, is where i hat lands. Its second column, two and one, is where j hat lands.
  5. Notice anything? The second column is exactly twice the first. Both landing spots lie on the same line.
  6. Watch what A does to the whole plane. Every grid line, every vector, gets crushed onto a single line.
  7. That line is every output A can possibly produce. It is called the column space, because it is the span of the columns. Here it is only one dimensional.
  8. Now pick a target b that is off the line, say one, three. No input can ever land there, because nothing A outputs leaves the green line. A x equals b has no solution.
  9. That is the first big idea. A x equals b is solvable exactly when b lies in the column space of A.
  10. Let's rewind. Here is a second question: which inputs get sent to zero? Take the line of vectors along negative two, one.
  11. Apply A, and every single one of them collapses onto the origin. This whole line is squashed to zero.
  12. The set of everything A sends to zero is called the kernel, or null space. You find it by solving A x equals zero. Here, x plus two y equals zero.
  13. Now choose b on the column space: four, two. One input that works is four, zero, because four times the first column is four, two. Call it a particular solution, x p.
  14. But we can add any kernel vector to x p. A sends the kernel part to zero, so the sum still lands on b. Slide along, and you trace a whole line of solutions, parallel to the kernel.
  15. Apply A to that entire line, and all of it lands on the single point b. Every one of those inputs answers our question.
  16. So the general solution is a particular solution plus anything in the kernel. Remember this shape. Linear differential equations have exactly the same structure.
  17. Count dimensions. The column space is a line, so the rank of A is one. The kernel is a line, so the nullity is one. One plus one is two, the dimension of the input space.
  18. That is the rank nullity theorem. Every input dimension is either kept, and shows up in the output, or crushed into the kernel. Nothing is lost without a trace.
  19. Compare a healthy matrix. Its columns point in different directions, so the plane is stretched and sheared but never flattened.
  20. Now the kernel is just the zero vector, the rank is two, and every b has exactly one solution. That means the transformation can be undone: B has an inverse.
  21. And here is what elimination was doing all along. Row reduce the system with b equal to four, two. The second row becomes all zeros: zero equals zero, no contradiction.
  22. The first column has a pivot. The second has none, so y is a free variable. Set y equal to t, and x equals four minus two t. That is the line we just saw.
  23. With b equal to one, three, the same steps give zero equals five halves. That impossible row is elimination's way of saying b is not in the column space.
  24. One last thing, and it matters for fluids. An incompressible fluid solver finds the pressure by solving a giant linear system, one unknown per grid cell.
  25. But only pressure differences push the fluid. Raise every cell by the same amount and the differences, and the forces, do not change.
  26. So the constant vector, all ones, is in the kernel of the pressure matrix. The matrix is singular, pressure is only defined up to a constant, and real solvers pin one cell or subtract the mean.
  27. To recap. The column space holds every reachable output, so it decides whether a solution exists. The kernel holds everything crushed to zero, so it decides how many.
  28. Next time: a single number, the determinant, that tells you whether a matrix flattens space at all.

Ax⃗=b⃗A\vec x = \vec b is a question about a transformation

Recall the two readings of a matrix–vector product from the previous lessons. Column by column,

Ax⃗=[∣∣∣a⃗1a⃗2⋯a⃗n∣∣∣][x1⋮xn]=x1a⃗1+x2a⃗2+⋯+xna⃗n,A\vec x = \begin{bmatrix} | & | & & | \\ \vec a_1 & \vec a_2 & \cdots & \vec a_n \\ | & | & & | \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = x_1 \vec a_1 + x_2 \vec a_2 + \cdots + x_n \vec a_n ,

so Ax⃗A\vec x is a linear combination of the columns with weights taken from x⃗\vec x. Geometrically, AA is a function: it takes an input vector x⃗∈Rn\vec x \in \mathbb{R}^n and returns an output Ax⃗∈RmA\vec x \in \mathbb{R}^m.

So the equation Ax⃗=b⃗A\vec x = \vec b asks one question in two languages:

  • Transformation language: which input vector(s) x⃗\vec x does AA send to the output b⃗\vec b?
  • Combination language: which weights x1,…,xnx_1, \dots, x_n build b⃗\vec b out of the columns of AA?

You met the second version in 1.1 Vectors, Linear Combinations & Span, when we found coefficients of a linear combination by solving a little system. Now we can ask the two follow-up questions every scientist cares about:

  1. Existence. Is there any input that lands on b⃗\vec b?
  2. Uniqueness. If so, is there exactly one, or many?

The column space answers the first question, and the kernel answers the second.

Column space: every output you can reach

The column space of AA is the set of all possible outputs:

C(A)={ Ax⃗:x⃗∈Rn }=span⁡{a⃗1,…,a⃗n}⊆Rm.C(A) = \{\, A\vec x : \vec x \in \mathbb{R}^n \,\} = \operatorname{span}\{\vec a_1, \dots, \vec a_n\} \subseteq \mathbb{R}^m .

It is the span of the columns, so it is always a flat subspace through the origin of the output space. This gives us the first theorem of the lesson almost for free:

Take the matrix from the video,

A=[12121].A = \begin{bmatrix} 1 & 2 \\ \tfrac12 & 1 \end{bmatrix}.

Its second column (2,1)(2, 1) is exactly twice its first column (1,12)(1, \tfrac12). Every output is x(1,12)+y(2,1)=(x+2y)(1,12)x(1, \tfrac12) + y(2, 1) = (x + 2y)(1, \tfrac12), a multiple of one vector. So the column space is the line through the origin in the direction (2,1)(2, 1). The entire plane gets crushed onto that line. Then:

  • b⃗=(4,2)\vec b = (4, 2) lies on the line, so Ax⃗=(4,2)A\vec x = (4,2) is solvable.
  • b⃗=(1,3)\vec b = (1, 3) does not (it isn’t a multiple of (2,1)(2,1)), so Ax⃗=(1,3)A\vec x = (1, 3) has no solution. No input, however clever, can land off the line.

When the columns of a 2×2 matrix are independent, the column space is all of R2\mathbb{R}^2 and every b⃗\vec b is reachable.

Kernel: everything that gets squashed to zero

The second subspace lives in the input space. The kernel (or null space) of AA is everything AA sends to the zero vector:

N(A)=ker⁡A={ x⃗∈Rn:Ax⃗=0⃗ }.N(A) = \ker A = \{\, \vec x \in \mathbb{R}^n : A\vec x = \vec 0 \,\}.

The system Ax⃗=0⃗A\vec x = \vec 0 is called the homogeneous system. It always has at least the trivial solution x⃗=0⃗\vec x = \vec 0, because a linear map sends the origin to the origin. The kernel is interesting when it contains more than that.

For our singular AA, Ax⃗=0⃗A\vec x = \vec 0 means (x+2y)(1,12)=(0,0)(x + 2y)(1, \tfrac12) = (0, 0), i.e. x+2y=0x + 2y = 0. That is the line

N(A)=span⁡{[−21]}.N(A) = \operatorname{span}\left\{ \begin{bmatrix} -2 \\ 1 \end{bmatrix} \right\}.

Every vector on this line collapses onto the origin. You can check one directly: A(−2,1)=(−2+2,  −1+1)=(0,0)A(-2, 1) = (-2 + 2,\; -1 + 1) = (0, 0).

Why is the kernel always a subspace? If Au⃗=0⃗A\vec u = \vec 0 and Av⃗=0⃗A\vec v = \vec 0, then by linearity A(cu⃗+dv⃗)=cAu⃗+dAv⃗=0⃗A(c\vec u + d\vec v) = cA\vec u + dA\vec v = \vec 0. So combinations of kernel vectors stay in the kernel, which makes it a flat subspace through the origin: a point, a line, a plane, and so on.

General solution = particular + homogeneous

Here is why the kernel controls uniqueness. Suppose x⃗p\vec x_p is one solution of Ax⃗=b⃗A\vec x = \vec b (a particular solution), and x⃗h\vec x_h is any vector in the kernel. Then

A(x⃗p+x⃗h)=Ax⃗p+Ax⃗h=b⃗+0⃗=b⃗.A(\vec x_p + \vec x_h) = A\vec x_p + A\vec x_h = \vec b + \vec 0 = \vec b .

So adding a kernel vector to a solution gives another solution. Conversely, if x⃗1\vec x_1 and x⃗2\vec x_2 are two solutions, their difference satisfies A(x⃗1−x⃗2)=b⃗−b⃗=0⃗A(\vec x_1 - \vec x_2) = \vec b - \vec b = \vec 0, so it lies in the kernel. Together:

For our example with b⃗=(4,2)\vec b = (4, 2): x⃗p=(4,0)\vec x_p = (4, 0) works, because 4⋅(1,12)=(4,2)4 \cdot (1, \tfrac12) = (4, 2). The general solution is

[xy]=[40]+t[−21],t∈R,\begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 4 \\ 0 \end{bmatrix} + t \begin{bmatrix} -2 \\ 1 \end{bmatrix}, \qquad t \in \mathbb{R},

a line parallel to the kernel. In the video, applying AA to this whole line collapses it onto the single point b⃗\vec b. You could just as well have picked x⃗p=(0,2)\vec x_p = (0, 2) or (2,1)(2, 1). Different particular solutions just slide the starting point along the same line.

So a linear system has zero, one, or infinitely many solutions, never exactly two: either b⃗∉C(A)\vec b \notin C(A) (none), or the solution set is a shifted copy of the kernel (a single point if the kernel is trivial, otherwise a line, plane, …).

◆ Interactive Input space → output space: column space, kernel, and the solutions of Ax = b

Loading simulation…

Things to try:

  1. Start with the lesson example. Drag b⃗\vec b around the right panel. It turns red (no solution) off the green column space and green when it’s on it, and then the pink solution line appears on the left, parallel to the red kernel. The sim marks the solution closest to the origin as x⃗p\vec x_p, but any point on the pink line would do.
  2. Drag x⃗\vec x along the pink line on the left. Its image Ax⃗A\vec x on the right doesn’t move at all. That is ”AA sends the whole line to b⃗\vec b” in action.
  3. Switch to Rank 2: invertible. The kernel shrinks to a dot, the column space fills the plane, and the solution set becomes a single point for every b⃗\vec b.
  4. Pick any matrix and press Make column 2 = 2 × column 1. Watch the transformed grid on the right fold up into a line and the readout’s rank drop from 2 to 1 while the nullity rises from 0 to 1.
✅ Concept check

For $A = \begin{bmatrix} 1 & 2 \\ \tfrac12 & 1 \end{bmatrix}$, which right-hand side makes $A\vec x = \vec b$ solvable?

Elimination, revisited

Now let’s redo the mechanics you already know, but read every step geometrically. Row operations are:

  1. swap two rows,
  2. multiply a row by a nonzero number,
  3. add a multiple of one row to another.

Each is reversible, so row operations never change the solution set of Ax⃗=b⃗A\vec x = \vec b (and in particular never change the kernel). What they do change is how easy the system is to read. They do change the column space in general, which is why we read column-space information off the original columns, as you’ll see below.

Echelon forms, pivots and free variables

A matrix is in row echelon form (REF) when all zero rows are at the bottom and each row’s first nonzero entry (its pivot) is strictly to the right of the pivot above it. It is in reduced row echelon form (RREF) when, in addition, every pivot equals 1 and is the only nonzero entry in its column. The RREF of a matrix is unique; REFs are not.

  • A pivot column contains a pivot. Its variable is a pivot (basic) variable.
  • A column with no pivot gives a free variable: you can set it to anything, and the pivot variables adjust.

The rank of AA is the number of pivots.

Worked example: a 3×4 system done carefully

Solve Ax⃗=b⃗A\vec x = \vec b with

A=[120324181215],b⃗=[132].A = \begin{bmatrix} 1 & 2 & 0 & 3 \\ 2 & 4 & 1 & 8 \\ 1 & 2 & 1 & 5 \end{bmatrix}, \qquad \vec b = \begin{bmatrix} 1 \\ 3 \\ 2 \end{bmatrix}.

Step 1: eliminate below the first pivot. Use R2→R2−2R1R_2 \to R_2 - 2R_1 and R3→R3−R1R_3 \to R_3 - R_1 on the augmented matrix:

[120312418312152]⟶[120310012100121].\left[\begin{array}{cccc|c} 1 & 2 & 0 & 3 & 1 \\ 2 & 4 & 1 & 8 & 3 \\ 1 & 2 & 1 & 5 & 2 \end{array}\right] \longrightarrow \left[\begin{array}{cccc|c} 1 & 2 & 0 & 3 & 1 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 & 1 \end{array}\right].

Step 2: look for the next pivot. Column 2 has nothing below row 1, so it has no pivot: x2x_2 will be free. The next pivot is the 1 in column 3, row 2. Eliminate below it with R3→R3−R2R_3 \to R_3 - R_2:

[120310012100000].\left[\begin{array}{cccc|c} \boxed{1} & 2 & 0 & 3 & 1 \\ 0 & 0 & \boxed{1} & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].

This is already the RREF (the pivots are 1 and each pivot column is otherwise zero). The bottom row reads 0=00 = 0: no contradiction, so the system is consistent.

Step 3: read it off. Pivots sit in columns 1 and 3, so the rank is 2. The free variables are x2=sx_2 = s and x4=tx_4 = t. The two nonzero rows say

x1+2x2+3x4=1,x3+2x4=1,x_1 + 2x_2 + 3x_4 = 1, \qquad x_3 + 2x_4 = 1 ,

so x1=1−2s−3tx_1 = 1 - 2s - 3t and x3=1−2tx_3 = 1 - 2t. In vector form:

x⃗=[1010]⏟x⃗p+s[−2100]⏟n⃗1+t[−30−21]⏟n⃗2.\vec x = \underbrace{\begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}}_{\vec x_p} + s \underbrace{\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}}_{\vec n_1} + t \underbrace{\begin{bmatrix} -3 \\ 0 \\ -2 \\ 1 \end{bmatrix}}_{\vec n_2}.

Step 4: check. Ax⃗pA\vec x_p is column 1 plus column 3: (1,2,1)+(0,1,1)=(1,3,2)=b⃗(1,2,1) + (0,1,1) = (1,3,2) = \vec b. ✓ And An⃗1=−2(1,2,1)+(2,4,2)=0⃗A\vec n_1 = -2(1,2,1) + (2,4,2) = \vec 0, An⃗2=−3(1,2,1)−2(0,1,1)+(3,8,5)=(0,0,0)A\vec n_2 = -3(1,2,1) - 2(0,1,1) + (3,8,5) = (0,0,0). ✓

The general solution is exactly “particular + homogeneous”: setting the free variables to zero gives x⃗p\vec x_p, and the coefficients of ss and tt are the kernel vectors.

Reading the kernel straight from the RREF

The recipe in Step 3 always works. For Ax⃗=0⃗A\vec x = \vec 0 the right-hand side is zero, so the particular part vanishes and you get:

They are automatically independent: each has a 1 in its own free slot where the others have 0. So

dim⁡N(A)=number of free variables.\dim N(A) = \text{number of free variables}.

This dimension is called the nullity of AA.

Reading the column space and solvability

The pivot columns of the original matrix AA form a basis for C(A)C(A). Here that’s columns 1 and 3: (1,2,1)(1,2,1) and (0,1,1)(0,1,1). The other columns are combinations of them, and the kernel vectors record the recipes: n⃗1\vec n_1 says column 2 = 2·column 1, and n⃗2\vec n_2 says column 4 = 3·column 1 + 2·column 3. So C(A)C(A) is a plane in R3\mathbb{R}^3.

Which b⃗\vec b are in that plane? Run the same elimination on a general right-hand side (b1,b2,b3)(b_1, b_2, b_3). The last row becomes

[0000b1−b2+b3],\left[\begin{array}{cccc|c} 0 & 0 & 0 & 0 & b_1 - b_2 + b_3 \end{array}\right],

so the system is solvable exactly when b1−b2+b3=0b_1 - b_2 + b_3 = 0. That is the equation of the column-space plane. Our b⃗=(1,3,2)\vec b = (1,3,2) passes: 1−3+2=01 - 3 + 2 = 0. A right-hand side like (1,0,0)(1, 0, 0) would produce the impossible row 0=10 = 1.

Rank and the rank–nullity theorem

The rank of AA is the dimension of its column space, which equals the number of pivots:

rank⁡A=dim⁡C(A)=#pivots.\operatorname{rank} A = \dim C(A) = \#\text{pivots}.

Every column of AA is either a pivot column or a free column, so counting columns gives:

Geometric meaning. The input space has nn dimensions’ worth of directions. AA keeps some of them, which show up as the column space, and crushes the rest into the kernel. No dimension is lost without a trace. In the 2×2 example, one direction (along (−2,1)(-2,1)) is crushed and one survives as the column-space line: 1+1=21 + 1 = 2. In the 3×4 example: 2+2=42 + 2 = 4.

▶ Video A 3×3 matrix of rank 2 flattens space onto a plane; its kernel line collapses to the origincaptions only
Transcript
  1. The same ideas work in three dimensions. Let's watch a three by three matrix flatten space.
  2. This matrix should look familiar from lesson one point one. Its third column is the sum of the first two, so the three columns only span a plane.
  3. Here is a lattice filling a block of space. Apply the matrix, and the whole block is pressed flat into that plane: the column space.
  4. The column space is the plane z equals x plus y. Any target b off this plane has no solution. The rank is two.
  5. Rewind. One direction must be lost: rank two plus nullity one makes three. The kernel is the line along negative one, negative one, one.
  6. Apply the matrix once more. The block flattens, and the entire kernel line collapses to the origin.
  7. Three dimensions in, two dimensions out, one dimension crushed. That is rank nullity in a picture.

The video’s matrix is the dependent example from 1.1 Vectors, Linear Combinations & Span: columns (1,0,1)(1,0,1), (0,1,1)(0,1,1) and their sum (1,1,2)(1,1,2). Three input dimensions go in, a two-dimensional plane (z=x+yz = x + y) comes out, and the line spanned by (−1,−1,1)(-1,-1,1) is crushed to zero: 2+1=32 + 1 = 3.

Some consequences you can now predict without computing anything:

  • Wide matrices (m<nm \lt n, more unknowns than equations): rank ≤m<n\le m \lt n, so the nullity is at least n−m>0n - m \gt 0. A consistent wide system always has infinitely many solutions.
  • Tall matrices (m>nm \gt n, more equations than unknowns): rank ≤n<m\le n \lt m, so the column space is a proper subspace of Rm\mathbb{R}^m. Some right-hand sides have no solution. That’s why overdetermined data-fitting problems use least squares instead.
  • Square matrices: rank nn ⇔ nullity 0 ⇔ every b⃗\vec b has exactly one solution. One property gives you all three.
✅ Concept check

A $5 \times 7$ matrix has rank 3. What is the dimension of its kernel?

✅ Concept check

$P = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$ projects the plane onto the $x$-axis. What is its kernel?

Inverse matrices

A square matrix AA is invertible if there is a matrix A−1A^{-1} with

A−1A=AA−1=I.A^{-1}A = AA^{-1} = I .

Geometrically, A−1A^{-1} is the transformation that undoes AA. That’s only possible if AA never merges two inputs into one output. If Au⃗=Av⃗A\vec u = A\vec v with u⃗≠v⃗\vec u \ne \vec v, then A−1A^{-1} wouldn’t know where to send that output. Since Au⃗=Av⃗A\vec u = A\vec v means u⃗−v⃗∈N(A)\vec u - \vec v \in N(A), a map can be undone exactly when its kernel is trivial. Combined with rank–nullity, this gives the central equivalence of the subject:

The 2×2 inverse

For A=[abcd]A = \begin{bmatrix} a & b \\ c & d \end{bmatrix},

A−1=1ad−bc[d−b−ca],provided ad−bc≠0.A^{-1} = \frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}, \qquad \text{provided } ad - bc \ne 0.

You can check it by multiplying: [abcd][d−b−ca]=[ad−bc00ad−bc]\begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix} = \begin{bmatrix} ad - bc & 0 \\ 0 & ad - bc \end{bmatrix}. The number ad−bcad - bc is the 2×2 determinant, the same independence test from lesson 1.1. When it’s zero the columns are parallel, the plane is flattened, and no inverse exists. For our singular example, 1⋅1−2⋅12=01\cdot 1 - 2 \cdot \tfrac12 = 0, as expected.

Example. The healthy matrix from the video, B=[12−121]B = \begin{bmatrix} 1 & 2 \\ -\tfrac12 & 1 \end{bmatrix}, has ad−bc=1+1=2ad - bc = 1 + 1 = 2, so

B−1=12[1−2121]=[12−11412].B^{-1} = \frac12 \begin{bmatrix} 1 & -2 \\ \tfrac12 & 1 \end{bmatrix} = \begin{bmatrix} \tfrac12 & -1 \\ \tfrac14 & \tfrac12 \end{bmatrix}.

Check the first row of BB−1BB^{-1}: (1)(12)+(2)(14)=1(1)(\tfrac12) + (2)(\tfrac14) = 1 and (1)(−1)+(2)(12)=0(1)(-1) + (2)(\tfrac12) = 0. ✓

Gauss–Jordan for larger matrices

To invert an n×nn \times n matrix, row reduce the wide matrix [ A∣I ][\,A \mid I\,]. If AA reduces to II, the right half becomes A−1A^{-1}:

[ A∣I ]  →row ops  [ I∣A−1 ].[\,A \mid I\,] \;\xrightarrow{\text{row ops}}\; [\,I \mid A^{-1}\,].

Why does this work? The row operations amount to multiplying on the left by some matrix EE with EA=IEA = I. Applying the same EE to II gives E=A−1E = A^{-1}. Equivalently, you are solving the nn systems Ax⃗=e⃗1,…,Ax⃗=e⃗nA\vec x = \vec e_1, \dots, A\vec x = \vec e_n at once, and their solutions are the columns of A−1A^{-1}. If a pivot is missing, AA is singular and Gauss–Jordan tells you so.

Worked example. Invert A=[101011113]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 3 \end{bmatrix}. This is the video’s rank-2 matrix with its corner entry changed from 2 to 3, which breaks the dependence.

[101100011010113001]→R3−R1[101100011010012−101]\left[\begin{array}{ccc|ccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 3 & 0 & 0 & 1 \end{array}\right] \xrightarrow{R_3 - R_1} \left[\begin{array}{ccc|ccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 2 & -1 & 0 & 1 \end{array}\right] →R3−R2[101100011010001−1−11]→R1−R3,  R2−R3[10021−101012−1001−1−11].\xrightarrow{R_3 - R_2} \left[\begin{array}{ccc|ccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & -1 & -1 & 1 \end{array}\right] \xrightarrow{R_1 - R_3,\; R_2 - R_3} \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 2 & 1 & -1 \\ 0 & 1 & 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & -1 & -1 & 1 \end{array}\right].

So A−1=[21−112−1−1−11]A^{-1} = \begin{bmatrix} 2 & 1 & -1 \\ 1 & 2 & -1 \\ -1 & -1 & 1 \end{bmatrix}. Spot check: row 3 of AA times column 3 of A−1A^{-1} is (1)(−1)+(1)(−1)+(3)(1)=1(1)(-1) + (1)(-1) + (3)(1) = 1. ✓ With the original corner entry 2, the same elimination would have produced the row [ 0  0  0∣⋯ ][\,0\;0\;0 \mid \cdots\,] on the left: no third pivot, no inverse.

✅ Concept checkselect all that apply

Let $A$ be a $4 \times 4$ matrix. Select every statement that guarantees $A$ is invertible.

Fluids: the pressure solve and its kernel

Here is the biggest Ax⃗=b⃗A\vec x = \vec b you’ll meet in this course. An incompressible fluid solver (Stam’s Stable Fluids, and the 11.10 The Projection Method for Incompressible Flow) first moves the velocity field forward, which leaves it slightly compressible. Then it finds a pressure pp whose gradient removes the divergence, by solving the Poisson equation

∇2p=ρΔt ∇⋅u⃗∗.\nabla^2 p = \frac{\rho}{\Delta t}\, \nabla \cdot \vec u^{*}.

Discretized on a grid with one unknown pip_i per cell, the Laplacian ∇2\nabla^2 becomes a matrix LL (you’ll build the operator in 2.11 The Laplacian & Vector Identities and the discretization in 10.1 Finite Differences: Discretizing Derivatives). In 1D with spacing hh, the row for cell ii is the stencil (pi−1−2pi+pi+1)/h2(p_{i-1} - 2p_i + p_{i+1})/h^2. Solid walls impose a Neumann condition (no flow through the wall, so ∂p/∂n=0\partial p / \partial n = 0), which modifies the end rows. For four cells:

L=1h2[−11001−21001−21001−1].L = \frac{1}{h^2}\begin{bmatrix} -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & 1 & -1 \end{bmatrix}.

Every row sums to zero, so L (1,1,1,1)=0⃗L\,(1, 1, 1, 1) = \vec 0. The constant vector is in the kernel. Physically, only pressure differences push fluid. Raise the pressure in every cell by the same amount, and every force stays the same. Everything in this lesson now applies:

  • Pressure is only defined up to a constant. If p⃗\vec p solves Lp⃗=b⃗L\vec p = \vec b, so does p⃗+c 1⃗\vec p + c\,\vec 1. That’s particular + homogeneous.
  • LL is singular (rank n−1n - 1, nullity 1), so np.linalg.solve will fail or return garbage.
  • Not every right-hand side is allowed. Adding up all the rows of LL gives zero, so the entries of Lp⃗L\vec p always sum to zero. A solution can exist only if ∑ibi=0\sum_i b_i = 0. Physically, the net divergence in a closed box must be zero: you can’t pump fluid into a sealed container. Rank–nullity shows this is also sufficient. The column space has dimension n−1n-1 and sits inside the (n−1)(n-1)-dimensional set of vectors whose entries sum to zero, so the two are equal.
🐍 PythonThe pressure matrix is singular, and that's physics
⌘/Ctrl + Enter
✅ Concept check

Why is the pressure Poisson matrix with Neumann (solid-wall) boundaries singular?

Code it yourself

First, use SymPy’s exact arithmetic to confirm the worked example. Then you’ll write the algorithm.

🐍 PythonExact RREF, kernel and column space with SymPy
⌘/Ctrl + Enter
🧪 Coding exerciseExercise: RREF and a kernel basis from scratch
⌘/Ctrl + Enter

Now use row reduction to produce the full solution set of a singular system, or detect that there isn’t one.

🧪 Coding exerciseExercise: the general solution of a singular system
⌘/Ctrl + Enter

Practice problems

✏️ Pen & paperA rank-1 matrix by hand●○○

Let A=[2−6−13]A = \begin{bmatrix} 2 & -6 \\ -1 & 3 \end{bmatrix}.

  1. Describe the column space and the kernel geometrically, and give a basis for each.
  2. Find the general solution of Ax⃗=(4,−2)A\vec x = (4, -2).
  3. Does Ax⃗=(1,1)A\vec x = (1, 1) have a solution?
  4. Verify rank–nullity.
Show worked solution
  1. Column 2 is −3-3 times column 1, so C(A)=span⁡{(2,−1)}C(A) = \operatorname{span}\{(2, -1)\}, a line through the origin with slope −12-\tfrac12. For the kernel, Ax⃗=0⃗A\vec x = \vec 0 reduces to the single equation 2x−6y=02x - 6y = 0 (the second row is −12-\tfrac12 times the first), so x=3yx = 3y and N(A)=span⁡{(3,1)}N(A) = \operatorname{span}\{(3, 1)\}.
  2. (4,−2)=2(2,−1)(4, -2) = 2(2,-1) is in the column space. Row reduce: R2→R2+12R1R_2 \to R_2 + \tfrac12 R_1 gives [2−64000]\left[\begin{array}{cc|c} 2 & -6 & 4 \\ 0 & 0 & 0 \end{array}\right]. So 2x−6y=42x - 6y = 4, i.e. x=2+3yx = 2 + 3y. With y=ty = t free: x⃗=(2,0)+t(3,1)\vec x = (2, 0) + t(3, 1). Check: A(2,0)=(4,−2)A(2,0) = (4, -2) ✓, and A(3,1)=(6−6,−3+3)=(0,0)A(3,1) = (6-6, -3+3) = (0,0) ✓.
  3. The same row operation gives the last row [ 0    0∣1+12 ]=[ 0    0∣32 ][\,0\;\;0 \mid 1 + \tfrac12\,] = [\,0\;\;0 \mid \tfrac32\,], which reads 0=320 = \tfrac32. No solution: (1,1)(1,1) is not a multiple of (2,−1)(2,-1).
  4. Rank 1 (one pivot) + nullity 1 (one free variable) = 2 = number of columns. ✓
✏️ Pen & paperSolvability condition and general solution for a 3×3●●○

Let A=[1232473610]A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 7 \\ 3 & 6 & 10 \end{bmatrix}.

  1. Find the RREF of AA, its rank, and a basis for N(A)N(A).
  2. For which b⃗=(b1,b2,b3)\vec b = (b_1, b_2, b_3) is Ax⃗=b⃗A\vec x = \vec b solvable? Describe this set geometrically.
  3. Find the general solution for b⃗=(1,3,4)\vec b = (1, 3, 4).
Show worked solution
  1. R2→R2−2R1R_2 \to R_2 - 2R_1 and R3→R3−3R1R_3 \to R_3 - 3R_1 give rows (0,0,1)(0, 0, 1) and (0,0,1)(0, 0, 1). Then R3→R3−R2R_3 \to R_3 - R_2 zeros the last row, and R1→R1−3R2R_1 \to R_1 - 3R_2 clears above the second pivot:
RREF⁡(A)=[120001000].\operatorname{RREF}(A) = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}.

Pivots in columns 1 and 3, so the rank is 2. x2x_2 is free. Setting x2=1x_2 = 1 gives x1=−2x_1 = -2, x3=0x_3 = 0, so N(A)=span⁡{(−2,1,0)}N(A) = \operatorname{span}\{(-2, 1, 0)\}. Check: −2(1,2,3)+(2,4,6)=0⃗-2(1,2,3) + (2,4,6) = \vec 0 ✓. Nullity 1, and 2+1=32 + 1 = 3 ✓. 2. Track the right-hand side through the same operations. Row 2 becomes b2−2b1b_2 - 2b_1, row 3 becomes b3−3b1b_3 - 3b_1, and then row 3 becomes (b3−3b1)−(b2−2b1)=b3−b1−b2(b_3 - 3b_1) - (b_2 - 2b_1) = b_3 - b_1 - b_2. The system is solvable iff b3=b1+b2b_3 = b_1 + b_2. That’s a plane through the origin in R3\mathbb{R}^3, the column space, spanned by the pivot columns (1,2,3)(1,2,3) and (3,7,10)(3,7,10). (Both satisfy b3=b1+b2b_3 = b_1 + b_2 ✓.) 3. b⃗=(1,3,4)\vec b = (1, 3, 4) satisfies 4=1+34 = 1 + 3 ✓. Reducing the augmented matrix: rows become [1  2  3∣1][1\;2\;3 \mid 1], [0  0  1∣1][0\;0\;1 \mid 1], [0  0  0∣0][0\;0\;0 \mid 0], and then R1−3R2R_1 - 3R_2 gives [1  2  0∣−2][1\;2\;0 \mid -2]. So x3=1x_3 = 1 and x1=−2−2x2x_1 = -2 - 2x_2:

x⃗=[−201]+t[−210].\vec x = \begin{bmatrix} -2 \\ 0 \\ 1 \end{bmatrix} + t\begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix}.

Check: A(−2,0,1)=(−2+3,  −4+7,  −6+10)=(1,3,4)A(-2, 0, 1) = (-2 + 3,\; -4 + 7,\; -6 + 10) = (1, 3, 4) ✓.

✏️ Pen & paperInverses●●○
  1. Compute the inverse of A=[3152]A = \begin{bmatrix} 3 & 1 \\ 5 & 2 \end{bmatrix} and use it to solve Ax⃗=(1,2)A\vec x = (1, 2).
  2. For which values of kk is M=[1kk4]M = \begin{bmatrix} 1 & k \\ k & 4 \end{bmatrix} invertible? For each value where it isn’t, find its kernel and column space.
Show worked solution
  1. ad−bc=6−5=1ad - bc = 6 - 5 = 1, so A−1=[2−1−53]A^{-1} = \begin{bmatrix} 2 & -1 \\ -5 & 3 \end{bmatrix}. Check: [3152][2−1−53]=[6−5−3+310−10−5+6]=I\begin{bmatrix} 3 & 1 \\ 5 & 2 \end{bmatrix}\begin{bmatrix} 2 & -1 \\ -5 & 3 \end{bmatrix} = \begin{bmatrix} 6 - 5 & -3 + 3 \\ 10 - 10 & -5 + 6 \end{bmatrix} = I ✓. Then x⃗=A−1(1,2)=(2−2,  −5+6)=(0,1)\vec x = A^{-1}(1, 2) = (2 - 2,\; -5 + 6) = (0, 1). Check: 3⋅0+1=13\cdot 0 + 1 = 1, 5⋅0+2=25 \cdot 0 + 2 = 2 ✓.

  2. ad−bc=4−k2ad - bc = 4 - k^2, which is zero exactly when k=±2k = \pm 2. So MM is invertible for all k≠±2k \ne \pm 2.

    • k=2k = 2: M=[1224]M = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}. The kernel is given by x+2y=0x + 2y = 0, so it’s span⁡{(−2,1)}\operatorname{span}\{(-2, 1)\}. The column space is span⁡{(1,2)}\operatorname{span}\{(1, 2)\}.
    • k=−2k = -2: M=[1−2−24]M = \begin{bmatrix} 1 & -2 \\ -2 & 4 \end{bmatrix}. The kernel is given by x−2y=0x - 2y = 0, so it’s span⁡{(2,1)}\operatorname{span}\{(2, 1)\}. The column space is span⁡{(1,−2)}\operatorname{span}\{(1, -2)\}.

    In both cases rank 1 + nullity 1 = 2. (Because MM is symmetric, its kernel comes out perpendicular to its column space. That’s no accident, as you’ll see when we study symmetric matrices.)

✏️ Pen & paperCounting arguments and the pressure matrix●●●
  1. Can a 3×53 \times 5 matrix have a trivial kernel? Can a 5×35 \times 3 matrix have C(A)=R5C(A) = \mathbb{R}^5? Justify both answers with rank–nullity.
  2. For the 4-cell Neumann Laplacian LL in the fluids section (take h=1h = 1), compute N(L)N(L) by hand and find the rank.
  3. Show that Lp⃗=b⃗L\vec p = \vec b is solvable if and only if b1+b2+b3+b4=0b_1 + b_2 + b_3 + b_4 = 0.
  4. Solve Lp⃗=(1,0,0,−1)L\vec p = (1, 0, 0, -1), giving the general solution, and then the solution with mean pressure zero.
Show worked solution
  1. No. A 3×53 \times 5 matrix has at most 3 pivots (one per row), so its rank is at most 3 and its nullity is 5−rank⁡≥25 - \operatorname{rank} \ge 2. No again for the 5×35 \times 3 matrix: its rank is at most 3 (one pivot per column), so C(A)C(A) is at most a 3-dimensional subspace of R5\mathbb{R}^5 and can’t be all of it.
  2. Lp⃗=0⃗L\vec p = \vec 0 reads −p1+p2=0-p_1 + p_2 = 0, p1−2p2+p3=0p_1 - 2p_2 + p_3 = 0, p2−2p3+p4=0p_2 - 2p_3 + p_4 = 0, p3−p4=0p_3 - p_4 = 0. The first gives p2=p1p_2 = p_1, the second then p3=2p2−p1=p1p_3 = 2p_2 - p_1 = p_1, and the third p4=2p3−p2=p1p_4 = 2p_3 - p_2 = p_1 (the fourth is then automatic). So N(L)=span⁡{(1,1,1,1)}N(L) = \operatorname{span}\{(1,1,1,1)\}, the nullity is 1, and the rank is 4−1=34 - 1 = 3.
  3. (⇒) Each column of LL sums to zero (equivalently, the rows add up to the zero row), so for any p⃗\vec p the entries of Lp⃗L\vec p sum to ∑jpj(column j sum)=0\sum_j p_j (\text{column } j \text{ sum}) = 0. So if Lp⃗=b⃗L\vec p = \vec b, then ∑bi=0\sum b_i = 0. (⇐) The set S={b⃗:∑bi=0}S = \{\vec b : \sum b_i = 0\} is a 3-dimensional subspace (one linear condition in R4\mathbb{R}^4). We just showed C(L)⊆SC(L) \subseteq S, and dim⁡C(L)=rank⁡L=3=dim⁡S\dim C(L) = \operatorname{rank} L = 3 = \dim S. A 3-dimensional subspace inside another 3-dimensional subspace must equal it, so C(L)=SC(L) = S.
  4. ∑bi=0\sum b_i = 0 ✓. Pin p1=0p_1 = 0. Row 1: −p1+p2=1-p_1 + p_2 = 1 gives p2=1p_2 = 1. Row 2: p1−2p2+p3=0p_1 - 2p_2 + p_3 = 0 gives p3=2p_3 = 2. Row 3: p2−2p3+p4=0p_2 - 2p_3 + p_4 = 0 gives p4=3p_4 = 3. Row 4 checks: p3−p4=−1p_3 - p_4 = -1 ✓. General solution: p⃗=(0,1,2,3)+c(1,1,1,1)\vec p = (0, 1, 2, 3) + c(1, 1, 1, 1). The mean of (0,1,2,3)(0,1,2,3) is 32\tfrac32, so the zero-mean solution is c=−32c = -\tfrac32: p⃗=(−32,−12,12,32)\vec p = (-\tfrac32, -\tfrac12, \tfrac12, \tfrac32). Physically, fluid enters at one end and leaves at the other, so the pressure ramps linearly to push it through.

Looking ahead

You now have the two subspaces that organize the rest of the module. In 1.4 Determinants as Volume Scaling a single number, det⁡A\det A, will detect at a glance whether a square matrix flattens space, i.e. whether its kernel is nontrivial. Then in 1.5 Eigenvectors & Eigenvalues the eigenvectors of AA for eigenvalue λ\lambda will turn out to be exactly the kernel of A−λIA - \lambda I: finding eigenvectors is a null-space computation, and you just wrote the code for it.

Key Takeaways

  • Ax⃗=b⃗A\vec x = \vec b asks which input AA sends to b⃗\vec b, or equivalently which combination of the columns builds b⃗\vec b.
  • The column space C(A)C(A) is every reachable output (the span of the columns). The system is solvable iff b⃗∈C(A)\vec b \in C(A).
  • The kernel N(A)N(A) is everything AA crushes to 0⃗\vec 0. It decides uniqueness: the general solution is x⃗p+x⃗h\vec x_p + \vec x_h with x⃗h∈N(A)\vec x_h \in N(A), the same structure as linear ODEs.
  • Row reduction to RREF exposes everything: pivots count the rank, free variables generate a kernel basis, and a row 0=c≠00 = c \ne 0 means b⃗∉C(A)\vec b \notin C(A).
  • Rank–nullity: rank⁡A+dim⁡N(A)=n\operatorname{rank} A + \dim N(A) = n. Every input dimension is either kept or crushed.
  • A square matrix is invertible ⇔ trivial kernel ⇔ full rank ⇔ columns form a basis. Use 1ad−bc[d−b−ca]\frac{1}{ad-bc}\begin{bmatrix} d & -b \\ -c & a\end{bmatrix} for 2×2 and Gauss–Jordan on [A∣I][A \mid I] for larger matrices, but solve systems in code with solve, not inv.
  • The fluid pressure matrix has the constant vector in its kernel. Pressure is defined only up to a constant, the right-hand side must have zero net divergence, and solvers pin a cell or subtract the mean.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.

Where this leads

These later lessons build directly on this one: