Statements and Systems of Equations

In this series on linear algebra, we want to offer several different perspectives to make it easier for the student to get a complete picture of what's going on. In many courses, geometry is used to give students intuition; although geometry is an excellent way of visualizing ideas in mathematics, linear algebra frequently deals with dimensions much higher than where our conventional notions of geometry live. For this reason, we want to introduce some perspectives that will allow us to build intuition without relying on visualization: namely, we will learn to think of equations as statements. Later on we will also introduce the function perspective.

Statements

Definition (Declarative Statement): A declarative statement is a statement that is either true or false.

"The sky is blue," is a declarative statement, as is "The sky is brown". The former is usually true, and the latter is almost never true, but both have in common that they are only ever either true or false.

We can craft more complicated declarative statements. For instance, we can add terms like or and and. Here is an example: "It is either raining or not raining." This example is an example of a tautology, which is a statement that is always true. It is always either raining or not raining. Conversely, if we were to use an "and" instead, the statement would become one that is never true: "It is raining and not raining." A statement that's never true is called a contradiction.

You may be wondering what all of this has to do with math, let alone linear algebra. Well, much of the business of a real mathematician is showing that one statement (usually a very complicated one) is, in some way, equivalent to another. To expedite this process, it helps to take some things for granted, called axioms. What you're willing to consider an axiom is ultimately a question of philosophy, and it depends on the level of rigor you want to bring to the subject.

Here are some examples of axioms we will take for granted in this course. Suppose you have three numbers x, y, and z. Then:

1. x = x (reflexivity)
2. x + y = y + x (commutativity of addition)
3. If x = y and y = z, then x = z. (transitivity of equality)
4. x*(y+z) = xy + xz (distributivity of multiplication)

All of these are statements, and when we say they are axioms it means we are taking for granted that they are true, without having to prove them. If you really want to be mathematically formal, you want to consider your set of axioms as small as possible, but keep in mind that there is a point of diminishing returns. For example, proving trivial facts like the commutativity of addition (the second statement above) involves first defining the type of numbers you're working with in terms of set theory (which has a whole host of other axioms you must take for granted), and then it's a very contrived series of steps from those axioms to show the desired property. For most, this is not worth the effort.

But I digress, the last thing we must discuss for the purposes of this course are quantifiers. There are two types of quantifiers, the universal quantifier and the existential quantifier, and they are very important for crafting statements in mathematics.

I think quantifiers are best understood through examples. Here is an example of an existential statement:

"There exists an integer that is both even and odd."

This is an example of a universal statement:

"Every integer is even or odd."

An existential statement is one that characterizes the existence (or lack thereof) of a certain type of thing. In the case of the example above, the "thing" in question was an integer. A universal statement is one that characterizes something about all members of a certain type of thing.

You may also note that the statements above are opposites, or to use terminology from formal logic, they are each other's negations.

Definition(Negation): P is the negation of Q if P is true whenever Q is false and P is false whenever Q is true.

In mathematics if you prove the negation of a statement true, then that is equivalent to proving the original statement false. This is useful because in many cases it may be easier to prove or disprove the negation of a statement rather than the original statement itself. Here are some trickier examples of negations.

Statements with Variables

Anyways, that's enough philosophy. Let's start looking at statements that have to do with numbers and variables. These are the simplest kind of statements we will be interested in in this course, and later we will introduce matrices and vectors, and consider statements that involve them.

Consider the following statement:

For two numbers x and y, x + y = 5.

This is an example of a statement, because it is either true or false, but which is it? Well it depends on which numbers x and y are. For instance, if x=2 and y=3, then the statement is true, but if x=2 and y=4, then the statement becomes 6=5, which is false.

As you can imagine, there are infinitely many combinations of x and y that make the statement true. From basic algebra, you probably know that these solutions form a line in the plane, but it's worth understanding why.

Suppose we know one pair of numbers (x,y) make the statement true, i.e. that $x+y = 5$. Then for any number c, the pair (x+c, y-c) must also make the statement true, because

This means that starting from any solution, you can move to the right by some amount and down by the same amount, and you will still have a solution. Since you can do this for any value of $c$, you generate an entire straight path of solutions, which we call a line. We say this line has slope $-1$ because if we increase x by one unit, then y must change by $-1$.

We are trying to understand this idea without drawing a picture, because there are limitations on what we can visualize. For example, you draw an equation of two variables as a line in 2d space, and, with a lot more effort, you can draw an equation of 3 variables as a flat surface in 3d space, but what about a statement involving 4 variables? What about one involving 100? Linear algebra frequently deals in these high dimensional spaces so we want some form of intuition that doesn't collapse whenever we move beyond 3d.

Three Special Operations

In order to go forward with this perspective, it will be useful to have some tools that will let us manipulate statements. Here are three very important tools that we can use when dealing with statements of equality. They're going to sound really simple, but we're going to see that these three tools actually lie at the heart of linear algebra. Here they are:

1. Multiplying both sides by the same thing.
2. Adding the same thing to both sides.
3. Rearranging statements.

You are probably already familiar with the first two. When you took algebra in middle or high school, you probably learned that you can "solve" equations like this:

In order to do so, you would subtract 8 from both sides and divide both sides by 3 and you would get $x = 1$. It's worth considering what's going on here. You have a statement of the form ``some quantity equals some other quantity''. This statement is declarative, because it is either true or false. Applying any of the three operations above produces a new statement that retains the same truth as the original, but could be easier to interpret.

Let's say that again, because it's important. This is the main idea:

In this way, we wind up with an equivalent statement. The expression itself changes, but the values of $x$ that make the statement true or false remain exactly the same.

So when we subtract 8 from both sides, we get

and when we divide both sides by 3, we get

We haven't changed the underlying truth of the statement at any point. We have only rewritten it in a form that makes the value of $x$ more clear. Just like the statement we started with, this one is also true when x is 1, and false otherwise; it's just much more obvious.

The statement

and the statement

contain exactly the same information, but the second is preferable because its meaning is clear.

It may be easy to see with a simple example like this, but it can quickly get more complicated as you add more variables and more statements, which we will see in a second. But before moving on, I want to emphasize the main idea here one more time. When we modify statements in these three ways, we produce an equivalent statement, one that is true or false for the same set of variables.

Multiple Statements

One way that we can make this more complex is by considering what happens when we have multiple statements at the same time. When we consider multiple statements at the same time, we call them systems of equations.

Consider the following system of equations:

and,

If I apply the second operation to the second statement, multiplying both sides by 2, I get the following equivalent system:

and,

Now I want to apply the first operation to the first statement, but I'm going to do it in a bit of a creative way. I am going to add $-2x + 2y$ to one side, and I'm going to add $12$ to the other side. If we accept that both statements are true, then by the second statement, these quantities are equal so it should produce an equivalent statement. This would give us the following equivalent system:

and,

Notice what we did there. We had to make an assumption that both statements were true, and we assumed that they were true for the same values of x and y. This assumption is what allowed us to combine like terms when we added (-2x + 2y) to the left side of the first statement, because we assumed that the x and y that satisfied the second statement were the same x and y that satisfied the first.

Now notice what happened. We now have an equivalent system that tells us the identity of one of the variables. Now we have two, equivalent, options: we can plug that value of y into the second equation to tell us what x is, or we could continue with our operations. I'm going to do the latter and then show how these two approaches are the same:

and,

The reason this is the same as substitution is because, in order to solve for x, we would have to multiply the value of y by 2 and then subtract it from both sides, which is exactly what we did using only the three operations.

This is probably a good place to mention what I mean by Operation 3 "Rearranging statements." This is just a way to say that the system:

and,

has the same solution set as the system:

and,

You probably remember this from middle/high school, but this is where the story of linear algebra begins. It starts by considering what happens when we have larger systems involving more variables. Let's look at that now.

Larger Systems

First I want to reiterate something. If I have a statement with $n$ variables, and I know the identity of $n-1$ of those variables, then I also know the identity of the remaining one.

More generally, each new statement we add places an additional restriction on the variables. With one statement in $n$ variables, I need to know $n-1$ of them to determine the last. With two statements, I only need to know $n-2$ variables to determine the rest. Let's see why.

Suppose we have two general statements with $n$ variables:

and

Here $x_1, x_2, \dots, x_n$ are our variables, and the $a_i$, $a'_i$, and $b, b'$ are just numbers with $a_1 \neq 0$.

Now I know this looks a little obnoxious, but let's try to eliminate one of the variables by being creative. The goal is to produce an equivalent statement that involves only $n-1$ variables.

First, multiply both sides of the first equation by $\frac{-a'_1}{a_1}$:

Now add this new equation to the second equation:

The $x_1$ terms cancel, leaving

If we multiply both sides by $a_1$, we get a slightly cleaner expression:

Now we have a new statement involving only $n-1$ variables. This means that if we know the identity of $n-2$ of the variables, the last one is determined.

When does this fail?

If you look closely, there is one situation where this process breaks down. Suppose that

for every $i = 1, 2, \dots, n$.

In that case, every coefficient on the left-hand side becomes zero, and we are left with

This new statement is either:

• a tautology (always true), if $a_1b' - a'_1b = 0$, or
• a contradiction (never true), otherwise.

Let's interpret what this means.

The condition

for all $i$ is equivalent to

So the second equation is just a constant multiple of the first.

• If the right-hand side is scaled by the same constant, then the two equations are equivalent, carrying the same information. Adding the second equation gives us nothing new, which is why we end up with a tautology.

• If the right-hand side is not scaled by the same constant, then the two equations are incompatible. They describe different solution sets, and no values of the variables can satisfy both simultaneously, which is why we get a contradiction.

Each new statement is capable of reducing the number of variables that can be chosen freely by one. Later in the course when we discuss linear independence we will solidify exactly what we mean by "new", but for now just consider that if a new statement is just a multiple of an old one, or if it can be formed by some combination of the previous statements, then it isn't actually new. At best it adds no new information, and if it conflicts with the previous statements, then the statements are contradictory and there is no solution at all.

If we have $n$ unknown variables, then:

• with 1 new statement, we can make a new statement with $n-1$ variables,
• with 2 new statements, we can make one with $n-2$ variables,
• and in general, each additional new statement allows us to craft a statement with one less variable.

Following this pattern, if we want to reduce the system to a single variable, one that directly tells us the identity of that variable, then starting from $n$ variables, we would need $n$ statements, each one contributing new information, meaning it cannot be obtained from the previous statements.

Now note that we are typically free to choose which variable we eliminate at each step. So if we can reduce the system down to one variable, then in principle we could repeat this process to isolate each variable individually, producing statements of the form $x_i = c$ for every $i$. We will discuss the most efficient ways to do this in a future lesson when we talk about Gaussian Elimination.

Put simply, to completely determine the identity of all $n$ variables, we need $n$ statements that cannot be obtained from each other.

That was a lot of theory, so let's look at an example. Consider the system:

You may think the last statement doesn't have enough variables, but it does, the coefficient on $x_3$ is just 0. For a trivial example of why this is fine, consider the system:

Obviously, this system has a solution, and it's actually the ideal system... the one we want to end up with, but each statement only concerns one variable at a time.

Getting back to the problem, I'm noticing that if I'm able to get rid of the $x_3$ in the second statement, then I could look at the last two equations in isolation and it would just be a 2x2 system, which I know how to solve. I can make this happen by multiplying the first statement by 3 and adding it to the second:

Now we can just look at the system formed by the last two statements, and I'll just solve it since you probably remember this stuff from basic algebra (note there are many ways to do this):

This time I'll do substitution to get $x_2$:

And now I can plug both of these into the first equation with three variables to get:

Because we were careful to only take actions which preserved the solution set that would satisfy these statements (the three special operations), we can say that the values of $x_1, x_2, x_3$ that satisfy the system:

are the exact same as the values that satisfy the system:

but this system is much more interpretable.

I will ask you to solve a larger system of equations maybe only once or twice in this course, because this is a task better delegated to a computer. That said, it is important to understand how computers solve these sorts of problems. This is something we will, again, examine when we discuss Gaussian elimination.

Instead, consider this question. It's a bit more challenging conceptually, but it's much more important to understand.

Can a System Have More Than One Solution?

The last detail we will touch on is this one. The answer to this question is obviously yes, because we have already seen instances of systems of equations with infinitely many solutions. But you may be interested to discover that this is actually the only way a system can have more than one solution, i.e., a system can't have exactly two solutions. Let's see why with a $2 \times 2$ example.

Suppose a system of equations,

had two solutions, $(x_1, x_2)$ and $(x_1', x_2')$ that both satisfied both equations.

Then,

and

so we can write the equivalent statement:

which reduces to:

Analogously, from the second equation we obtain:

Now, notice that if $(x_1, x_2) \neq (x_1', x_2')$, then the quantities $x_1 - x_1'$ and $x_2 - x_2'$ are both nonzero (you can't have one be nonzero and the other be zero because then neither of the equations above could be true). Thus, we have found a nonzero pair that satisfies both equations when the right-hand side is $0$.

Now consider the pair

where $t$ is any real number. Then by distributivity,

and similarly,

This means that any multiple of this difference also satisfies both equations.

Thus, if $(x_1, x_2)$ is a solution, then

will also satisfy the original system for every value of $t$. This shows that if a system of linear equations has more than one solution, it must have infinitely many solutions.