Geometry of systems of linear equations

Consider a linear equation a_{1}x_{2} + ⋯ + a_{n}x_{n} = b. The solutions to this systems are vectors x in ℝ^{n}. Collecting the coefficients a_{i} into another vector in ℝ^{n}, we can write this equation as a · x = b. Thus the solutions to the given equation lie in a subset of ℝ^{n}, called a hyperplane, for which a is a normal vector. Does the scalar b have an equally geometric meaning?

Example. Let a = [\begin{matrix}1 \\ 1 \end{matrix}], b = 6. Writing out the equation a · x = b in coordinates, we get

x_{1} + x_{2} = 6. The solution set is the line through \binom{6}{0} and \binom{0}{6}. The difference between any two points in the solution set is a vector in a^{⊥}. The line {ta | t ∈ ℝ} is perpendicular to the solution set, and intersects it at \binom{3}{3}. This is the closest point to the origin, and its distance to 0 is 3\sqrt{2}. Where does this appear in the equation? It’s b divided by the length of a. So if we “scale” the equation to replace a with a unit vector, we get a constant term that measures the distance from the line to the origin.

One of the homework exercises asks you to examine the general case of the above example in ℝ^{n}.

It should come as no surprise at this point that solving systems of linear equations is deeply connected to the geometry of ℝ^{n}. Define

H_{a,b} = {x ∈ ℝ^{n} | a · x = b}.

This is called a hyperplane in ℝ^{n}. A system of linear equations looks like

{a_{1} · x = b_{1} ; a_{2} · x = b_{2} ; ⋮ ; a_{k} · x = b_{k} .

Any solution must solve all of the equations simultaneously—i.e., it must lie in

H_{a_{1},b_{1}} ∩ H_{a_{2},b_{2}} ∩ ⋯ ∩ H_{a_{k},b_{k}}.

The linear relations between the a_{i}s can thus tell us something about the size (read: dimension) of the solution set. (Look at picture in textbook: p. 184.)

Proposition 0.1. If the vectors a_{i} are linearly independent, then a solution always exists.

The geometric reason, loosely speaking, is that the hyperplanes are all “oriented” in different directions, so they must intersect. This corresponds to the case where the coefficient matrix reduces to an echelon form where every row has a pivotal 1.

Proposition 0.2. If the vectors a_{i} are linearly dependent, then at least one of the following is true: • one of the equations is redundant, meaning it is a consequence of some of the others;

• the equations are inconsistent, meaning no solutions exist.

Both of these situations correspond to having a reduced coefficient matrix that contains a row of zeroes. As you’ve seen in class, all bets are off in that case; you must study the values of the b_{i}s to know if solutions exist. The easiest examples to think of are where two of the equations determine the same hyperplane (i.e., a_{i} = ta_{j} and b_{i} = tb_{j} for some i, j, t)—then one of the equations is redundant—or when two of the hyperplanes are parallel (i.e., a_{i} = ta_{j} for some i, j, t, but b_{i} ≠ tb_{j})—then no vector can possibly be in both.

We can turn this whole picture around by collecting the b_{i}s into a single vector b ∈ ℝ^{k}, and collecting corresponding elements of the a_{i}s into n vectors v_{j} in ℝ^{k}. Thus,

v_{1} = [a_{1,1} ; ⋮ ; a_{k,1}] , …, v_{n} = [a_{1,n} ; ⋮ ; a_{k,n}] , b = [b_{1} ; ⋮ ; b_{k}] ,

and the system becomes

x_{1}v_{1} + x_{2}v_{2} + ⋯ + x_{n}v_{n} = b,

a single equation in ℝ^{k}. (You’re still looking for a solution in ℝ^{n}, however.) You may recall that this was pointed out in class when defining matrix multiplication: each column of the product matrix is a linear combination of the columns of the first factor matrix. Now you’re asking: can you “build” the vector b by a linear combination of the v_{j}s, i.e., does b lie in their span? Again, the key to knowing the answer is row reduction.

Why is row reduction so important? The former view of systems of equations gives a partial answer: any equation obtained as a consequence of the given equations must also be true for a solution of the system. That is, row operations do not change the solution set. The latter view of systems of equations also gives an answer: because the set of x_{i} solving the system in ℝ^{k} is invariant under row operations on the v_{j}, row operations do not change linear relations among the coefficient vectors. Effectively, row operations are a “change of basis,” and row echelon form allows you to see exactly which columns of a matrix can form a basis, and how the remaining columns look in that basis. Example. Consider the linear map ℝ^{5} → ℝ^{3} defined by the matrix

A = [\begin{matrix}2 & −2 & 0 & −2 & −2 \\ 3 & −3 & 1 & −2 & 1 \\ 1 & −1 & 1 & −1 & 0 \end{matrix}] .

Given b ∈ ℝ^{3}, can we always find x ∈ ℝ^{5} such that Ax = b? IOW, is this map onto? We want to know if the columns of A span ℝ^{3}. We guess they might, because there are so many of them, but let’s be sure. A row reduces to

[\begin{matrix}1 & −1 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 3 \end{matrix}] .

Now we see that the 1st, 3rd, and 4th columns form a basis for ℝ^{3}, and we even know how to express the 2nd and 5th columns in that basis. Thus the given map is onto ℝ^{3}. In a couple of weeks, it will be very important to know when a linear map is onto.

What does the reduced form of A tell us about the first perspective on linear systems? Well, it also shows that all three rows are independent, so for any particular vector b ∈ ℝ^{3}, the solution set of Ax = b will be the intersection of three non-parallel hyperplanes; i.e., there will be two free parameters. This relates to a theorem you’ll see in class tomorrow, on the various dimensions of subspaces associated to a linear map.