Underdetermined Systems

What is the relationship between the number of unknowns and the number of equations in a system?

A linear system with more unknowns than equations either has:

Zero solutions.
Infinitely many solutions.

Why? Consider a system with $m < n$ , where $m$ is the number of equations and $n$ is the number of unknowns.

The "no solutions" condition is relatively straightforward: if the equations are logically inconsistent, such that no choices for the unknowns can solve all equations in the system at the same time, there are no solutions.

For example, consider the system: $x = 1$ and $x = 2$ . Since $x$ cannot equal both 1 and 2 simultaneously, this system has no solutions. It almost seems silly to call that a "system" — but that's all a system is: a bundle of equations with variables.

The "infinite solutions" system is more interesting, and I think it's a helpful way to learn more about the nature of systems of linear equations in general.

Equations as Constraints

Writing down a system of equations is like writing down a list of constraints.

An equation with unknowns is a description of a relationship between the right side of equals, and the left side. We can't just pick any values and get both sides equal all the time; this is what makes the equation a constraint.

The equals sign is doing the constraining here.

To "satisfy" the equation (i.e. the constraint), we have to pick the right values for the unknowns in that equation.

For instance, the equation $2 x + 3 y = 7$ describes a constraint where any values of $x$ and $y$ must make the left side equal to 7. Some valid solutions include $(x = 2, y = 1)$ and $(x = 0, y = \frac{7}{3})$ .

The more equations we have, the more constraints we're placing on the system, and therefore, the more "difficult" it becomes to satisfy the system.

By "difficult" here, I'm alluding to the method of just randomly picking values to plug in. The more equations there are, the fewer choices we have that satisfy the whole system at once.

There are more clever and efficient ways of solving systems of equations than "guess and check." But even with those methods, the more equations there are, the more work we have to do to solve the system.

So with each constraint (equation) we add to the system, the fewer valid choices we're allowing for our selection of unknowns.

Dimension Reduction

"Each consistent equation reduces the solution space by one dimension."

When I read that sentence for the first time, I was puzzled. Let's build our way toward understanding it.

We know these systems have unknowns (variables), and a list of equations. For example, consider this system of three equations with three unknowns:

x + y + z = 6

2 x - y + z = 3

x + 2 y - z = 4

Now, for a moment, forget about the list of equations, but keep thinking about the unknowns.

We can still think of this as a "system" — but with no equations yet, just the unknowns.

These unknowns (x, y, z) are now totally unconstrained!

We have no equations to constrain what x, y, or z can be. They can be anything.

In this example, n = 3 dimensions, one dimension for each unknown x, y, and z.

Geometrically, since we live in 3 dimensions, it's easy to imagine this system as a space that we can float around in, totally unconstrained.

Up, down, side to side — any location in our space, we can specify and travel to. We could point to (3, 5, 268) on the map and our system will allow it. No constraints.

In this analogy, a "solution" is any point in the space, specified by our choices of unknowns, that we can "travel" to, in 3D space.

Now, let's cautiously add one equation back into the system.

Bring the first equation back, $x + y + z = 6$ .

Suddenly we are limited. We have a constraint we must satisfy.

Set the unknowns to (1, 1, 1). Will the system allow it?

x + y + z = 6

1 + 1 + 1

= 3

3 \neq 6

Shucks. We are no longer able to travel to (1, 1, 1) in our space. This is what a constraint means. We just can't go there.

Number Budgets

The first equation describes a simple rule: three numbers must add up to 6.

There's the constraint we talked about before: "must add to six."

Think of this constraint as giving us a "budget" for choosing our unknowns here. We can pick any unknown we want, as long as we're always totaling 6.

Our "budget" gets tighter with each choice we make.

Say we pick 3 for our first unknown. Our choice is now (3, y, z).

Choosing y next, our choices are more limited than they were for x.

We can use 3, 2, or 1.

Oh, and based on what we choose for y, our choice of z is even more limited!

With (3, 2, z) we only have a single choice! The only option that satisfies the budget is choosing 1 as z.

The "tighter budget" means: if we want to increase our options for choosing z, it's not free. We have to "steal" numbers from x or y to give us more z options.

Given a choice of (3, 2, 1), if we want z to now be 2, we have to steal a 1 from x or y to satisfy the budget.

If we keep fidgeting with this budget, we start to get a list of possibilities.

(3, 2, 1)

(3, 1, 2)

(2, 3, 1)

(1, 1, 4)

(0, 6, 0)

We actually have a ton of flexibility here under our budget. We can keep moving numbers around and come up with new choices.

We aren't as flexible as we were before, but we're still pretty flexible.

It is this reduction in flexibility, this slightly lower flexibility that we should think more about. It's the equation's fault. The equation limited our flexibility.

Choose Two, Force One

Here's a way to express this flexibility, and more importantly, how this flexibility changed (reduced) by adding an equation.

We can pick any two variables in our triplet of x, y, and z, and then we can use algebra to determine the third, by doing a little computation.

If we pick 1 for x and 2 for y, z has to be 3 to satisfy our rule: must sum to 6.

We have two "degress of freedom" in our "three-dimensional space."

Degrees of Freedom

Here's another way to express the idea.

Start at any valid point, say (2, 2, 2). We sum to six.

We can pick any two new values, just as before, and "move" from (2, 2, 2) to our new "location" in 3D solution space.

As long as we stick to the budget, we're allowed to move to the new location.

So let's say we want (1, 1) for (x, y). Let the algebra keep us on budget. We do the computation and get z = 4.

1 + 1 + 4 = 6.

Pick a few more examples, and plot them. What do you see?

The Plane Emerges

With two degrees of freedom in three dimensions, we make a plane. This plane is flat, but infinitely flat, extending as far as you want, in two dimensions.

Here is our now-nuanced sense of flexibility: the original 3D space was infinitely vast in all (three) directions, until we added an equation. Then we lost some flexibility. But we still have some!

We are still somehow infinitely flexible, but less infinitely flexible than before. Our flatness, as long as we're walking on that plane, can take us infinitely far along that plane.

Remember that puzzling sentence from up above?

"Each consistent equation reduces the solution space by one dimension."

It's slightly less puzzling now.

Now recall the first sentence at the very beginning.

"A linear system with more unknowns than equations has either no solutions or infinite solutions."

We have a linear system with three unknowns. We have one equation.

We have (3 - 1 = 2) degrees of freedom.

We have less freedom, but enough freedom left to reach infinite solutions.

What happens when we add a second equation? Or a third?

Or a fourth?