Systems of Linear Equations and Gaussian Elimination

Everyone knows matrix equations are basically systems of equations, right?!?! So I’m gonna walk through systems of equations step by step, starting all the way back at the middle-school level.

(If a middle schooler actually reads this, they might suffer a chain of total mental breakdowns and trip a circuit breaker, lol. I’m talking from middle-school-GD’s perspective here, but apparently these days there are tons of middle schoolers already doing uni-level stuff???!!!)

OK OK OK OK OK. First off — what even is an equation?!?!

“An equality with unknowns in it!!!” Right. So whenever we run into an equation, our goal is crystal clear: “Find the unknowns that make the equality hold.”

(For reference — when we run into a differential equation, the goal becomes “find the function that makes the equality hold.”)

Anyway. When we sit down with a system of linear equations (the only kind we’ll care about from here on) and try to find its solutions, the outcome falls into one of three buckets (with real-number unknowns). Only linear systems are this tidy, by the way: $x^2 = 4$ already has exactly two solutions.

Quick aside. The case where there are infinitely many solutions —

Like on the left: you can have infinitely many because two lines overlap, and you can also have infinitely many because two planes overlap. Both are “infinitely many” — sure — but even within infinity, there’s gotta be a hierarchy, right? Like, surely the case where two planes overlap and give infinitely many should have more solutions than the case where two lines overlap and give infinitely many, right?!?!?!

Conclusion: they’re the same. Explaining this here would take forever, so just accept it and roll with it. (What it really says is — you can build a one-to-one correspondence between the two solution sets, so as sets they’re the same size. Their dimensions differ, though, and that’s what will matter below.)

Now, in linear algebra — same as in high school — we’re not messing with degree 2 or degree 3 stuff. Say there are $m$ first-degree equations in $n$ unknowns:

If we rewrite this in the matrix form we’ve been using all along, we get this:

Which we can write as $AX = B$, right?!?! ($A$ is the $m \times n$ matrix of coefficients, $X$ the column of the $n$ unknowns, $B$ the column of the $m$ right-hand sides.)

And this matrix $A$, well —

we can call it the matrix of a linear map $L$ from an $n$-dimensional space $V$ (basis $\beta$) to an $m$-dimensional space $W$ (basis $\gamma$), like this, and as we learned earlier, we can also write it like this:

In words: column $j$ of $A$ holds the coordinates of $L(v_j)$ in the basis $\gamma$.

(The bracket in the figure carries $\beta$ on top and $\gamma$ at the bottom; some books write it the other way round. Same matrix either way.)

OK — now I’m gonna split linear systems of equations broadly into two types.

In $AX = B$ above: the case where $B$ is $0$, and the case where $B$ is not $0$. That is — $AX = 0$ vs. $AX = B$. The former is called a homogeneous equation, and the latter is called a non-homogeneous equation.

(For reference — in a non-homogeneous equation, “non-homogeneous” means $x^1$ (degree 1) and $x^0$ (degree 0) are mixed together, so it’s not homogeneous. That’s why we call it non-homogeneous.)

You gotta understand the homogeneous case before you can solve the non-homogeneous one, so let’s poke at the homogeneous equation first.

Properties of the homogeneous equation

→ The defining feature of the homogeneous equation: the solution set forms a vector space.

The set of all $X$’s satisfying $AX = 0$, gathered up together, forms a vector space (a subspace of the space of all $n$-component columns)~~~ Let’s see why.

Say and are elements of the solution set. Meaning — each of them satisfies , , right?!?!

Oh but — is also a solution!!!!! And of course , , and a bunch of other scalar multiples are also solutions.

Hmmm~~~ and for the homogeneous equation, there’s one solution we can spot right away. Among all the $X$’s that satisfy the equality, the easiest one to pick out is $X = 0$. Right?! $X = 0$ obviously satisfies it, so yeah — it’s a solution.

But like… what does $X = 0$ even mean as a solution? Nothing. Means nothing at all. A solution like that is called the trivial solution. (And that’s why a homogeneous system can never have no solution: $X = 0$ is always there.) So really, the goal with a homogeneous equation is to find the non-trivial solution!!!!

OK anyway — we wanna find $X$ satisfying $AX = 0$. But wait?!?!?! This $X$ that satisfies the equality — that means: when we hit vector $X$ with matrix $A$, it sends it to $0$. Whoa?!?!

So can we say the solution set is the kernel of $A$?!?!

Well — not quite. The $X$’s are the coordinate columns of the vectors in the kernel of the linear map $L$ that matrix $A$ represents (when $V = \mathbb{R}^n$ with its standard basis, they’re those vectors themselves) — we can say that, right?!?!!!! — that’s how I’ll write it.

Here’s the punchline. The solution set can be written as $\ker A$, and $\ker A$ is obviously a subspace, right?!?!?! That is — we already know the kernel is a vector space.

Which means: the defining feature of the homogeneous equation is that the solution set is a vector space!!!!

Properties of the non-homogeneous equation

OK now let’s look at the non-homogeneous case. Say there’s an element of the solution set satisfying $AX = B$:

Ahhh~~~ but when we look at matrix $A$, there can be a kernel, right??? Let’s also say there’s an element of $\ker A$:

That means

right?!! You can already see where this is going: is also in the solution set.

So the solution set is

And that’s all of them, not just some. If $X$ is any solution at all, then $A(X - X_0) = B - B = 0$, so $X - X_0$ lies in $\ker A$ — that is, $X = X_0 + (X - X_0)$ has exactly the form above.

OK OK OK OK — but — we assumed there exists a particular solution , right?!?!?! If no particular solution like that exists, nobody in their right mind would answer “the solution set is $\ker A$.” That is — if there’s no particular solution, the solution set is just the empty set.

So now we know what the solution set looks like — but as I wrote at the very top, the number of elements in the solution set can be 0, can be 1, or can be infinitely many, right??? Right now we’ve got a particular solution, a kernel, and the three cases we learned in high school. Here’s how they fit together: no particular solution → no solutions at all; a particular solution exists and $\ker A = \{0\}$ → exactly one solution, $X_0$; a particular solution exists and $\ker A \neq \{0\}$ → infinitely many (over the reals you can scale any nonzero kernel vector by every real number, and each scaling gives a different solution).

This might all sound like total nonsense at the moment, so let me recycle the words above at high-school-math level. Then you’ll see what every single one of those words actually means.

What’s the solution to this system?!?!

Yeah — exactly. It’s a plane.

This kind of plane — no no — every point lying on this plane is a solution!!!

So we can describe the elements of the solution set like this. Every individual point! But what the above is really saying is:

This particular solution, plus

a linear combination of the solutions of the homogeneous equation $AX = 0$ (the figure calls these the “general solutions”) — i.e. the solution set can be expressed as a particular solution plus a span.

(Note: span is often written with brackets — angle brackets.)

Let’s also look at this system.

Since it’s the line of intersection of these two planes,

this line is the elements of the solution set. Using this particular solution, plus

if we span this guy, we can express it!!!

The difference between the solution sets in the two examples — it’s that the dimension of the vector space called Kernel is different (2 for the plane, 1 for the line)?!?!

Keep that in your back pocket as we move on.

When a non-trivial solution has to exist

When we hit a homogeneous equation, our job was to find the non-trivial solution — but how do we even know whether one exists?!

“Under a special condition, it has to exist!” That special condition is

that is — when the matrix is wider than it is tall = when there are more unknowns than equations!!! (It’s a guarantee, not an if-and-only-if: with $m \ge n$ a non-trivial solution may or may not exist, depending on $A$.)

The proof is apparently easy using the dimension theorem. The dimension theorem says, for a linear map $L : V \to W$ out of a finite-dimensional space $V$,

Here $L$ is $X \mapsto AX$ from $\mathbb{R}^n$ to $\mathbb{R}^m$, and $\dim \mathrm{im}\, L$ is at most $m$ (the image sits inside $\mathbb{R}^m$), right???? So $\dim \ker L$ — at smallest, is $n - m$. But our condition says $m < n$, so $0 < n - m$, right! Which says $\dim \ker L > 0$.

And $\ker L$ is the solution set of the homogeneous equation, so the fact that the solution set has dimension at least 1 means there’s some element other than $0$ — and that is exactly the non-trivial solution~!

Gaussian Elimination (GE)

Now I’ll show you the method for actually finding the solution.

When we’re staring down a matrix this size, is it just impossible to find the solution because it’s too big?!?!?!!

No no — it’s possible, it’s possible. It just takes forever!!!! Like — it is absolutely not something that can’t be found. OK, here’s the method!!!! It’s called Gaussian Elimination (GE).

That matrix above is, of course,

a system of equations like this, written in matrix form. So now…. To solve that matrix, do we have to convert the whole thing back~~ into equations, then multiply by constants and add and subtract like we did back in middle school….. Gaussian elimination is kinda similar (same concept, really) — but it lets us finish things off more easily, right inside matrix form.

First, let me run Gaussian elimination on an elementary-school-level equation.

There are 100 bicycles in total — some with two wheels, some with four — and when we count just the wheels, there are 354. How many two-wheelers and how many four-wheelers?!

We’d set it up like this, right??? I’m gonna write this step by step as a matrix, and then as the matrix representing the system.

Apparently this matrix form is also written like this (an augmented matrix: the coefficients, a bar, then the right-hand sides):

We just rewrote it in a different layout, and the rules of equality still apply, so we can write it as

This is Gaussian elimination in action. (The moves, if you want them: row 2 minus 2 × row 1, then divide row 2 by 2, then row 1 minus row 2. So 23 two-wheelers and 77 four-wheelers. Check: 23 × 2 + 77 × 4 = 46 + 308 = 354.)

It’s literally the same thing, isn’t it…….. T_T No…. actually there are a few rules, but this example is too simple to really show them off…… Anyway — the principle is exactly the same as elementary school!

So now,

for a giant 5×10 matrix like this, we multiply rows by nonzero constants, swap rows, and add multiples of one row to another (same idea as the old way of solving equations) and clean it up. Every one of those moves can be undone (swap back, divide by the same nonzero constant, subtract the same multiple again), so the cleaned-up system has exactly the same solutions as the original one.

Where exactly?! Until when?! do we have to keep cleaning — that is precisely the rule of Gaussian elimination, but talking about that rule right here feels like a bit much. I think it’ll click better if I cover it afterward, so I’ll continue with how to actually do Gaussian elimination in the very next post!!!

So for now, here’s what a matrix looks like once it’s cleaned up all the way. (The numbers in this picture are only illustrative: they aren’t the exact result of cleaning up the matrix above. What matters is the shape.)

This is the cleaned-up form!!!!! Eyeballing it — you get the feeling that there’s a lot of 0’s, and roughly if you draw a staircase through the leading 1’s, everything below the staircase is 0… that kind of vibe.

But if you actually write out this matrix as its corresponding system of equations, you can really feel how clean things have gotten.

The far-right side got cut off. It’s $0 = b'_{(5)}$.

OK, let me list the characteristics of the matrix above.

① In every row that isn’t all 0’s, the first non-zero entry is a 1 (a leading 1), and each leading 1 sits further to the right than the one in the row above — so the 0’s pile up on the left like a staircase!!!!

② Rows that are entirely 0’s are stuck at the very bottom, hmm???

③ Now, look at the columns where the leading 1’s live — everything else in those columns is 0?!?!?!

When all three conditions hold, we can call the matrix sufficiently clean.

With a clean matrix like this, we can see the solution at a glance~~~!!

Huh?!?!? So what is the solution then?

Let me give it to you up front. Move everything that isn’t tied to a ’leading 1’ over to the right-hand side and write it out.

Note) If $b'_{(5)} = 0$ doesn’t hold, the solution set becomes the empty set (the last equation would read $0 = b'_{(5)}$, which is false)!!! Watch out, watch out. (The primes just remind us that the right-hand side went through the same row operations as the matrix. The unknowns aren’t touched by row operations, so $x'_{(i)}$ is simply $x_i$ again.)

The above isn’t just the answer~~~!!! — let me write it out as the full solution set.

The thing about the variables $x'_{(1)}, x'_{(3)}, x'_{(6)}, x'_{(8)}$ tied to the leading 1’s is — once the values of all the other variables are pinned down, these guys are immediately fixed.

Think about it for a sec. Writing $x'_{(7)} = $ something would be weird. Because $x'_{(7)}$ shows up in tons of other rows too… that’s what’s going on here. Those variables don’t affect the other rows. Those variables are dependent on the others!!! That’s what I’m trying to say!!!

So those guys are called dependent variables, and the ones up there — $x'_{(2,4,5,7,9,10)}$ — are called independent variables~ (many books say pivot variables and free variables)

Starting at $x'_{(10)}$ and walking upward one by one to grab the elements of the solution set is no effort at all. The independent unknowns are free, so you can plug in whatever values you want; then the dependent ones have to be fixed so the equations hold, which is exactly what the formulas above do (as long as $b'_{(5)} = 0$).

And this gloriously convenient matrix form is called the Row Reduced Echelon Form — from here on out, I’ll just call it RREF, taking the first letters of each word above.

(Many books say reduced row echelon form. And strictly speaking, stopping at the staircase shape is Gaussian elimination, while going on to clear the columns above each leading 1 as well is called Gauss–Jordan elimination; here the whole cleanup goes under the name Gaussian elimination.)

---

Heads-up. The figures here are the original notes, slips and all. A few things to watch for:

• The picture that introduces the second example repeats the first system ($x+y+z=1$ and $2x+2y+2z=2$, a single plane). The second example is two different planes that meet in a line, such as $x+y+z=1$ and $x+y=1$, as the pictures after it show.
• In the last line of the two solution-set pictures, the vectors inside the angle brackets should be the ones from the span line above: $(-1,1,0)$ and $(-1,0,1)$ in the first, $(-1,1,0)$ in the second. The pictures write $(1,0,0)$.
• The picture with the thick arrow and the two thin arrows calls the vectors that span $\ker A$ "general solutions". They are solutions of the homogeneous equation $AX = 0$; the general solution of $AX = B$ is the whole set $X_0 + \ker A$.
• In the augmented matrix of the bicycle problem, the first row should read 1, 1 and 100 (from $x + y = 100$); the picture writes 2, 1.
• In the big matrix equations, the last entry of the right-hand column should be $b_5$ ($b'_5$ in the cleaned-up one): there are 5 rows, not 10.
• In the cleaned-up matrix, the 8th entry of row 3 and the 5th entry of row 5 should be 0; the picture has 6s there.