Main content

## Linear algebra

### Course: Linear algebra > Unit 1

Lesson 6: Matrices for solving systems by elimination# Using matrix row-echelon form in order to show a linear system has no solutions

And another example of solving a system of linear equations by putting an augmented matrix into reduced row echelon form. Created by Sal Khan.

## Want to join the conversation?

- I tried this problem on my TI-83 Plus and got a slightly different rref than Sal.

[ 1 2 0 3 0 ]

[ 0 0 1 -2 0 ]

[ 0 0 0 0 1 ]

I entered the coefficients as matrix A, and the constants as matrix B. Then, used the Augment function and saved it as matrix C. rref [C] gave me the above.

Why does my answer differ?(22 votes)- The reason that your answer is different is that Sal did not actually finish putting the matrix in reduced row echelon form. For a matrix to be in RREF every leading (nonzero) coefficient must be 1. In the video, Sal leaves the leading coefficient (which happens to be to the right of the vertical line) as -4. Your calculator took the extra step of dividing the final row by -4, which doesn't change the zero entries and which makes the final entry 1.

Sal probably didn't put the final row in reduced form because he could see the contradiction coming. (0 = -4 is as much a contradiction as 0 = 1). He gets away with it in this case because he knows where the problem is going.(72 votes)

- Is the number of free variables equal to the number of dimensions for a possible solution? If you have 1 free variable, is the solution set a line? 2 free variables, a plane? Etc.(27 votes)
- Yes. You can write the solution space as a position vector plus each of the free variables multiplied by their own (Linearly independent) vectors, which gives you the span of those vectors. 1 free variable = span of 1 vector = line, 2 free variables = span of 2 vectors = plane, etc.(35 votes)

- can a matrix have multiple row reduced echelon forms?(22 votes)
- No, there's a theorem that says it's unique.(29 votes)

- the correction says 'The shapes described by the three orange equations are not parallel.'

why isn't there a solution then?(15 votes)- Imagine 3 lines in 2d space, imagine they form a triangle. As you may guessed, the lines aren't parallel, and yet, they don't intersect, and by that I don't mean intersection of 2 lines(there are 3 points of that for a triangle), but intersection of 3 lines at some place, a point that lies on all of the three lines, that point doesn't exist in case of triangle.

It's not always like that, but I hope that this showed you that there*might*be systems of non-parallel equations with no solutions if the amount of equations is greater than 2.(18 votes)

- After watching all three reduced row echelon videos I don't understand the following things: what is an "augmented" matrix; why we can perform operations on the matrix without changing the solution; where reduced row echelon comes from (ie where it's form/rules come from); how you know if your solution is a plane, point, etc.; the significance of the term "pivot".(10 votes)
- Augmented forms of matrices have the "solution" (x+ y = n) IN it, usually represented as the last column, or an Ax1 matrix following the original matrix. Thus the "n", the last column representing the "solution" will change when performing row operations, but the value of the equations doesn't shave, as you're performing equal operations on both (all) sides of the =. Reduced Row Echelon Form just results form elementary row operations (ie, performing equivalent operations, that do not change overall value) until you have rows like "X +0Y = a & 0X + Y = b"

Concerning points, lines, planes, etc., this is generally only brought up for intuition's sake during early stages of matrix algebra, as it can get difficult to comprehend when you're working in higher dimensions. That being said, it depends on your solution and the dimensions you're working in what geometric representation is appropriate. In two dimensions, for example, constants (X, Y) represent a point, but in there dimensions it would be a line, with infinite points on the Z-plane (X, Y, aZ).

Pivot numbers are just the first non-zero entry in a row, significant to put matrices into the appropriate form (for example Reduced Row Echelon form).(9 votes)

- I still don't have the intuition of why pivot entries must be the first entry in a row. It could be a logical consequence of its definition but womehow I'm missing the point.

For instance, in the example Sal put forward at10:00, why should the variable X1 (row 1, col.1) be the pivot entry and not X2 (row 1, col. 1)?(6 votes)- If you get a 1 you are saying the coefficient on the variable is 1. So you know x1 = 3 instead of, say, 3*x1=9. For square matrices you get something like:

1 2 2 | 20

0 1 2 | 16

0 0 1 | 7

Then you know instantly that x3 = 7 and you can do back substitution easily to find the other variables. It also makes things easier for more advanced concepts in linear algebra.(11 votes)

- i don't understand it. because my english is not good.(3 votes)
- there are plenty of other sites that teach math. you can google the videos you desire. by setting google to your language you will recieve results in your native language first. :)(6 votes)

- at around3:26Sal says "The pivot entry should be my only non-zero entry in my row". Does he mean column instead of row? If so, this is a repeating mistake throughout this video series(4 votes)
- Sal says that if a whole row is zero ([0, 0, 0, 0 | 0]), then the set of equations have an infinite amount of solutions. What is the intuition for that?

Is it because all the variables equal zero and therefor you can scale them indefinitely and get have an infinite amount of solutions?(4 votes)- A whole row being zero means that if you multiply all of the variables by 0 and add up the results, you get 0.

However, this is true no matter what the variables are, so this row doesn't actually carry any information. So you effectively have one less equation to work with, which leaves you with more unknowns than equations.(4 votes)

- I thought these equations represent four vectors in R3 not R4 ?(2 votes)
- If "Ax = b" represents the equations, A is 4 R^3 column vectors, b is a column vector of constants, and "x" is a variable vector in R^4. Each equation (row) represents a plane in R^4, not a vector. The vector "b" constrains "Ax". (I don't understand it yet either).(1 vote)

## Video transcript

I have here three linear
equations of four unknowns. And like the first video, where
I talked about reduced row echelon form, and solving
systems of linear equations using augmented matrices, at
least my gut feeling says, look, I have fewer equations
than variables, so I probably won't be able to constrain
this enough. Or maybe I'll have an infinite
number of solutions. But let's see if I'm right. So let's construct the augmented
matrix for this system of equations. My coefficients on the x1
terms are 1, 1, and 2. Coefficients on the x2
are 2, 2, and 4. Coefficients on x3
are 1, 2, and 0. There's of course no x3 term,
so we can view it as a 0 coefficient. Coefficients on the x4 are
1, minus 1, and 6. And then on the right-hand side
of the equals sign, I have 8, 12, and 4. There's my augmented matrix,
now let's put this guy into reduced row echelon form. The first thing I want to do is,
I want to zero out these two rows right here. So what can we do? I'm going to keep my first row
the same for now, so it's 1, 2, 1, 1, 8. That line essentially represents
my equals sign. What I can do is, let me
subtract-- let me replace the second row with the second
row minus the first row. So 1 minus 1 is 0, 2 minus 2
is 0, 2 minus 1 is 1, 1-- negative 1 minus 1 is minus 2,
and then 12 minus 8 is 4. There you go, that looks good so
far, it looks like column, or x2 which is represented by
column two, looks like it might be a free variable, but
we're not 100% sure yet. Let's do all of our rows. So let's take-- to get rid of
this guy right here, let's replace our third equation with
the third equation minus two times our first equation. So we get 2 minus 2 times 1 is
0, 4 minus 2 times 2, well that's 0, 0 minus 2 times
1, that's minus 2. 6 minus 2 times 1, well
that's 4, right? 6 minus 2. And then 4 minus 2 times
8, is minus 16, 4 minus 16 is minus 12. Now what can we do? Well, let's see if we can
get rid of this minus 2 term right there. So let me rewrite my
augmented matrix. I'm going to keep row two the
same this time, so I get a 0, 0, 1, minus 2, and essentially
my equals sign, or the augmented part of the matrix. And now let's see
what I can do. Let me get rid of this 0 up
here, because I want to get into reduced row echelon form. So any of my pivot entries,
which are always going to have the coefficient 1, or the entry
1, it should be the only non-zero term in my row. How do I get rid of
this one here? Well I can subtract-- I can
replace row one with row 1 minus row 2. So 1 minus 0 is 1, 2 minus 0 is
2, 1 minus 1 is 0, 1 minus minus 2, that's 1 plus
2, which is 3. And then 8 minus 4 is 4. And now how can I get
rid of this guy? Well let me replace row 3 with
row 3 plus 2 times row 1. Sorry, with row 3 plus
2 times row 2. Right? Because then you'd have minus
2, plus 2 times this, and they'd cancel out. So let's see the zeros. 0 plus 2 times 0, that's 0. 0 plus 2 times 0, that's 0,
minus 2 plus 2 times 1 is 0. 4 plus 2 times minus 2, that's
4 minus 4, that's 0. And then I have minus
12, plus 2 times 4. That's minus 12 plus
8, that's minus 4. Now, this is interesting right
now-- this is interesting. I have essentially put this in
reduced row echelon form. I have two pivot entries, that's
a pivot entry right there, and that's a pivot
entry right there. They're the only non-zero term
in their respective columns. And this is just kind of a style
issue, but this pivot entry is in a lower
row than that one. So it's in a column to the right
of this one right there. And I just inspected, this looks
like a-- this column two looks kind of like a free
variable-- there's no pivot entry there, no pivot
entry there. But let's see, let's
map this back to our system of equations. These are just numbers to
me and I just kind of mechanically, almost like a
computer, put this in reduced row echelon form. Actually, almost exactly
like a computer. But let me put it back to my
system of linear equations, to see what our result is. So we get 1 times x1, let
me write it in yellow. So I get 1 times x1, plus 2
times x2, plus 0 times x3, plus 3 times x4 is equal to 4. Obviously I could ignore this
term right there, I didn't even have to write it. Actually. I'm not going to write that. Then I get 0 times x1, plus 0
times x2, plus 1 times x3, so I can just write that. I'll just write the one. 1 times x3, minus 2 times
x4, is equal to 4. And then this last term,
what do I get? I get 0 x1, plus 0 x2 plus 0
x3 plus 0 x4, well, all of that's equal to 0, and I've got
to write something on the left-hand side. So let me just write a 0,
and that's got to be equal to minus 4. Well this doesn't make
any sense whatsoever. 0 equals minus 4. This is this is a nonsensical
constraint, this is impossible. 0 can never equal minus 4. This is impossible. Which means that it is
essentially impossible to find an intersection of these three
systems of equations, or a solution set that satisfies
all of them. When we looked at this
initially, at the beginning of the of the video, we said
there are only three equations, we have four
unknowns, maybe there's going to be an infinite set
of solutions. But turns out that these three--
I guess you can call them these three surfaces--
don't intersect in r4. Right? These are all four dimensional,
we're dealing in r4 right here, because we have--
I guess each vector has four components, or we have four
variables, is the way you could think about it. And it's always hard to
visualize things in r4. But if we were doing things
in r3, we can imagine the situation where, let's say
we had two planes in r3. So that's one plane right there,
and then I had another completely parallel
plane to that one. So I had another completely
parallel plane to that first one. Even though these would be two
planes in r3, so let me give an example. So let's say that this first
plane was represented by the equation 3x plus 6y plus 9z is
equal to 5, and the second plane was represented by the
equation 3x plus 6y plus 9z is equal to 2. These two planes in r3-- this is
the case of r3, so this is r3 right here. These two planes, clearly
they'll never intersect. Because obviously this one has
the same coefficients adding up to 5, this one has the same
coefficient adding up to 2. And when, if we just looked at
this initially, if it wasn't so obvious, we would have
said, we have only two equations with three unknowns,
maybe this has an infinite set of solutions. But it won't be the case,
because you can actually just subtract this equation, from the
bottom equation, from the top equation. And what do you get? You would get a very familiar--
so if you just subtract the bottom equation
from the top equation, and you get 3x minus 3x, 6y minus 6y, 9z
minus 9z-- actually, let me do it right here. So for that minus that, you get
zero is equal to 5 minus 2, which is 3. Which is a very similar result
that we got up there. So when you have two parallel
planes, in this case in r3, or really to any kind of two
parallel equations, or a set of parallel equations,
they won't intersect. And you're going to get, when
you put it in reduced row echelon form, or you just do
basic elimination, or you solve the systems, you're going
to get a statement that zero is equal to something, and
that means that there are no solutions. So the general take-away,
if you have zero equals something, no solutions. If you have the same number of
pivot variables, the same number of pivot entries as you
do columns, so if you get the situations-- let me write this
down, this is good to know. if you have zero is equal
to anything, then that means no solution. If you're dealing with r3,
then you probably have parallel planes, in r2 you're
dealing with parallel lines. If you have the situation where
you have the same number of pivot entries as columns, so
it's just 1, 1, 1, 1, this is the case of r4 right there. I think you get the idea. That equals a, b, c, d. Then you have a unique
solution. Now if, you have any free
variables-- so free variables look like this, so let's say we
have 1, 0, 1, 0, and then I have the entry 1, 1,
let me be careful. 0, let me do it like this. 1, 0, 0, and then I have the
entry 1, 2, and then I have a bunch of zeroes over here. And then this has to equal
zero-- remember, if this was a bunch of zeroes equaling some
variable, then I would have no solution, or equalling some
constant, let's say this is equal to 5, this
is equal to 2. If this is our reduced row
echelon form that we eventually get to, then we have
a few free variables. This is a free, or I guess we
could call this column a free column, to some degree this
one would be too. Because it has no
pivot entries. These are the pivot entries. So this is variable x2 and
that's variable x4. Then these would be
free, we can set them equal to anything. So then here we have unlimited
solutions, or no unique solutions. And that was actually the
first example we saw. And these are really the three
cases that you're going to see every time, and it's good to
get familiar with them so you're never going to get
stumped up when you have something like 0 equals minus
4, or 0 equals 3. Or if you have just a bunch of
zeros and a bunch of rows. I want to make that
very clear. Sometimes, you see a bunch of
zeroes here, on the left-hand side of the augmented divide,
and you might say, oh maybe I have no unique solutions,
I have an infinite number of solutions. But you have to look at
this entry right here. Only if this whole thing is
zero and you have free variables, then you have an
infinite number of solutions. If you have a statement like,
0 is equal to a, if this is equal to 7 right here, then all
of the sudden you would have no solution to this. That you're dealing with
parallel surfaces. Anyway, hopefully you
found that helpful.