Linear Algebra and Vector Geometry 201-SN4-RE • CEGEP, Montreal

Revision sheet: linear systems, Gauss and Gauss-Jordan (201-SN4-RE)

This sheet does not explain again how to row reduce: you have seen it in class and done it ten times. It deals with what decides the mark: reading the last row, counting the free parameters exactly, and the write-up the 201-SN4-RE (formerly 201-NYC) marker expects when the solution is an infinite set.

It is written for CEGEP students in the Science program (Sciences de la nature), and for Social Science students in the mathematics profile, who meet the same chapter in their linear algebra course (201-105). Once the sheet is read, the corrected exercise set on the same chapter puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

The number of solutions is read neither from the number of equations nor from the number of unknowns: it is read from the number of PIVOTS in the row echelon form. The whole chapter follows from that, including the count of free parameters.

This chapter is part of 201-SN4-RE, Linear Algebra and Vector Geometry

The essentials

The three allowed operations, and nothing else

• Interchange two rows: $R_{i}\leftrightarrow R_{j}$ .
• Multiply a row by a NONZERO scalar: $R_{i}\to kR_{i}$ with $k\neq 0$ .
• Add to a row a multiple of ANOTHER row: $R_{i}\to R_{i}+kR_{j}$ , where only $R_{i}$ changes.
• Each one turns the system into an EQUIVALENT system, that is, one with exactly the same solution set. That is what allows you to work on the augmented matrix $[A\,|\,B]$ rather than on the equations.
• No operation acts on the COLUMNS: interchanging two columns would amount to renaming the unknowns, and the solution could no longer be read.

R_{1} : x+y=3

R_{2} : x-y=1

. Replacing

R_{2}

R_{2}-R_{1} : -2y=-2

turns the grey line into the green one, through the SAME point

(2, 1)

: the system stays equivalent.

Writing the operation used to the left of each new row, in the form $R_{2}\to R_{2}-4R_{1}$ , is required by every marker and is worth half a mark per step on most marking schemes.

Row echelon or reduced row echelon: two forms, two readings

• ROW ECHELON FORM, Gaussian elimination: in each nonzero row, the first nonzero entry, the PIVOT, lies strictly to the right of the pivot of the row above, and zero rows are at the bottom.
• You then finish with BACK SUBSTITUTION: the last equation gives one unknown, which you substitute into the one above, and so on.
• REDUCED ROW ECHELON FORM, Gauss-Jordan elimination: every pivot equals $1$ and is the ONLY nonzero entry of its column, so there are also zeros ABOVE it.
• The solution is then read directly in the last column, with no back substitution at all.
• The RANK is the number of pivots, and it is the only number that decides everything in this chapter.

On the left, zeros only BELOW the pivots (in green): back substitution is still needed. On the right, zeros on both sides and pivots equal to

1

: the solution is read in the last column.

Gauss-Jordan costs a few more operations but removes the back substitution, where most sign errors hide. On an exam $3\times 3$ system, it is almost always the best choice.

The three cases, and the count that tells them apart

• UNIQUE SOLUTION: as many pivots as unknowns, and no row of the form $[0\ \dots\ 0\,|\,c]$ with $c\neq 0$ .
• NO SOLUTION: a row $[0\ \dots\ 0\,|\,c]$ with $c\neq 0$ appears, which stands for the impossible equation $0=c$ . The system is called inconsistent.
• INFINITELY MANY SOLUTIONS: a consistent system, but fewer pivots than unknowns.
• Number of FREE PARAMETERS $=$ number of unknowns $-$ number of pivots. The number of equations you started with never enters this count.
• HOMOGENEOUS system, with zero right-hand side: it ALWAYS has the trivial solution $X=\vec{0}$ , so it is never inconsistent. It has other solutions if and only if it has fewer pivots than unknowns.

Three equations in three unknowns, three planes: a single common point; a common line (infinitely many solutions, one parameter); or no point common to all three (inconsistent system).

There is no fourth case. A linear system has zero, one or infinitely many solutions: answering “two solutions” is impossible, whatever the size of the system.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Multiplying a row by zero to create zeros

the whole question, because the solution set you give is wrong.

What not to write

“ $R_{3}\to 0\times R_{3}$ : the third row becomes zero, the system is simpler.”

What to write

“The scalar must be NONZERO. Multiplying by $0$ destroys an equation, and the resulting system is no longer equivalent: it would have more solutions than the original.”

Why: Equivalence of systems rests on every operation being reversible. Multiplying by $k\neq 0$ is undone by dividing by $k$ ; multiplying by $0$ cannot be undone.

2. Replacing two rows at once by their combination

the whole question, with infinitely many solutions announced where there is only one.

What not to write

“ $R_{1}\to R_{1}+R_{2}$ and $R_{2}\to R_{1}+R_{2}$ in the same step.”

What to write

“An elementary operation replaces ONLY ONE row, and the row used as the reference stays intact. Otherwise the two rows become identical and an equation is lost.”

Why: Losing an equation does not show in the rest of the computation: nothing looks wrong, the system has simply lost information, and so it has more solutions than the real one.

3. Taking an all-zero row for a contradiction

3 marks, and a conclusion that is the exact opposite of the truth.

What not to write

“The last row is $[0\ \ 0\ \ 0\,|\,0]$ , so the system has no solution.”

What to write

“ $[0\ \ 0\ \ 0\,|\,0]$ is the equation $0=0$ , always true: it signals a REDUNDANT equation, hence infinitely many solutions. It is $[0\ \ 0\ \ 0\,|\,c]$ with $c\neq 0$ that makes the system impossible.”

The only three cases, for two equations in two unknowns: intersecting, parallel or coincident lines (the row

[0\ \ 0\,|\,0]

, dashed, adds nothing). No fourth case.

Why: The whole reading hinges on the LAST entry, the one after the bar. Zero, the row says nothing; nonzero, it says the impossible.

4. Counting the free parameters on the number of equations

2 marks, and a basis of the null space that is missing a vector.

What not to write

“ $3$ equations and $4$ unknowns, so $4-3=1$ free parameter.”

What to write

“The count is made on the PIVOTS: unknowns minus pivots. If one of the three equations is a combination of the other two, only $2$ pivots remain, so $4-2=2$ free parameters.”

Two columns carry a pivot (in green), two do not: those last two are the ones that become free parameters, whatever the number of equations written at the start.

Why: The number of equations you start with measures nothing: two equations can say the same thing. Only row reduction reveals how many INDEPENDENT pieces of information the system contains.

5. Reading a row echelon form as if it were reduced

the whole question, even though the row reduction was right.

What not to write

“The row echelon form is $\begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}$ with right-hand side $\begin{pmatrix} 5 \\ 6 \end{pmatrix}$ , so $x=5$ and $y=6$ .”

What to write

“A row echelon form requires BACK SUBSTITUTION: $3y=6$ gives $y=2$ , then $2x+2=5$ gives $x=\frac{3}{2}$ . Only the REDUCED row echelon form, with pivots equal to $1$ and zeros above them, can be read directly.”

Why: A pivot other than $1$ , or a nonzero entry above a pivot, means that the unknown of that row still depends on the following ones. The last column is the solution only in the reduced form.

6. Declaring a homogeneous system impossible

2 marks for rigour, and often a whole theory question.

What not to write

“The homogeneous system $AX=\vec{0}$ has no solution.”

What to write

“A homogeneous system ALWAYS has the trivial solution $X=\vec{0}$ : it is never inconsistent. The real question is whether it has others, which happens exactly when there are fewer pivots than unknowns.”

The lines of a homogeneous system

ax+by=0

all pass through the origin: the zero solution always exists. There are others when the lines coincide (on the right).

Why: A row $[0\ \dots\ 0\,|\,c]$ with $c\neq 0$ cannot appear: the right-hand side is zero at the start and elementary operations keep it zero. Inconsistency is therefore ruled out by the very structure of the system.

7. Concluding that the system is impossible because it has more equations than unknowns

3 marks, and a question handed in without a single computation.

What not to write

“ $5$ equations for $3$ unknowns: the system is overdetermined, so impossible.”

What to write

“Nothing guarantees that. If two of the five equations are combinations of the other three, row reduction gives two zero rows and the system has a unique solution. Only the pivots decide.”

\ell_{1} : x+y=4

\ell_{2} : x-y=2

\ell_{3} : x+2y=5

: three equations, two unknowns, and a unique solution, because the three lines pass through

(3, 1)

. Only the pivots decide.

Why: The word “overdetermined” describes the FORM of the system, not its content. Redundancy is common in real problems, where the same data are measured in several ways.

8. Carrying on with a Gauss-Jordan inversion after a zero row

the whole question, plus the time spent producing a matrix that is not an inverse.

What not to write

“The second row of the left block has become zero, I keep going with the operations on the right block.”

What to write

“A row that is entirely zero in the LEFT block proves that $A$ is not invertible: stop the procedure and conclude that $A^{-1}$ does not exist.”

Why: $[A\,|\,I]$ turns into $[I\,|\,A^{-1}]$ only if the left block can reach the identity. A zero row means fewer pivots than rows, so the identity is out of reach.

Which method to choose

What the row echelon matrix says, row by row

Look at the augmented matrix AFTER row reduction, starting with the last nonzero row. A single reading decides the number of solutions.

If a row $[0\ \ 0\ \ \dots\ \ 0\,|\,c]$ with $c\neq 0$ → INCONSISTENT system: no solution, and you stop there

Example: $[0\ \ 0\ \ 0\,|\,5]$ stands for $0=5$
If as many pivots as unknowns, and no impossible row → UNIQUE solution: back substitute, or read it directly if the form is reduced
If a consistent system with fewer pivots than unknowns → INFINITELY many solutions, with (unknowns $-$ pivots) free parameters

Example: $4$ unknowns and $2$ pivots give $2$ parameters
If a row that is entirely zero, right-hand side included → REDUNDANT equation: ignore it, it only lowers the number of pivots

It never makes the system impossible, unlike the first branch.
If the right-hand side is zero from the start → HOMOGENEOUS system: never inconsistent, and comparing pivots with unknowns is enough

This reading is done on the ROW ECHELON matrix, never on the starting one. Counting pivots before you have row reduced makes no sense, and yet it is what rushed papers do.

Gauss or Gauss-Jordan, and how far to go

Look at what the question really asks, because pushing on to the reduced form is not always useful.

If the solution of a square system with a unique solution is asked for → GAUSS-JORDAN: the solution is read without back substitution, and sign errors disappear
If only the RANK is asked for, or a discussion of the number of solutions → GAUSS is enough: the row echelon form already shows every pivot

Going on to the reduced form would be time lost, and the marking scheme does not ask for it.
If a BASIS of the solution set or of the null space is asked for → GAUSS-JORDAN, then the parametric form: each free unknown gets a parameter and contributes a vector
If the INVERSE of a matrix is asked for → GAUSS-JORDAN on $[A\,|\,I]$ , up to $[I\,|\,A^{-1}]$ , stopping at once if a row of the left block becomes zero
If the system has a PARAMETER in its coefficients → row reduce while avoiding any division by an expression in the parameter, then discuss the values that make a pivot zero

Dividing by $m-2$ without handling the case $m=2$ is the classic error in this type of exercise.

In every case, never go back to the equations along the way: work on the augmented matrix from start to finish, and write equations only when you conclude.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Solving a system with infinitely many solutions

When to use it: Row reduction leaves fewer pivots than unknowns and the system is consistent.

1 Name the PIVOT (leading) unknowns and the FREE unknowns, saying which columns hold the pivots.
2 Assign a parameter to each free unknown, with a letter different from those of the unknowns: “let $y=s$ and $t=u$ ”.
3 Express each leading unknown in terms of the parameters, starting from the last nonzero row and working upward.
4 Write the general solution as a vector, then split it into a sum of fixed vectors multiplied by the parameters.
5 Conclude by giving the SET of solutions, and check by substituting the general solution into one of the original equations.

Concluding sentence

The solution set is $\left\{(4-2s-3u, s, 2+u, u)\ :\ s\in\mathbb{R},\ u\in\mathbb{R}\right\}$ , which depends on two free parameters.

The trap: Stopping at the row echelon matrix and writing “there are infinitely many solutions”. The question asks WHICH ONES: without a parametric form, half the marks are lost.

Marking: 1 mark for the row reduction, 0.5 mark for identifying the free unknowns, 1 mark for the parametric form, 0.5 mark for writing the set.

Discussing a system according to a parameter

When to use it: The coefficients contain a letter, and the question says “discuss according to the values of $m$ ”.

1 Row reduce using only operations whose coefficients do NOT depend on the parameter, for as long as possible.
2 Locate the coefficient of the last pivot, which is an expression in $m$ , and write explicitly for which values it is zero.
3 Handle the GENERAL CASE first, the one where this coefficient is not zero: a unique solution, given in terms of $m$ .
4 Then handle each critical value separately, replacing $m$ by that value FROM the start and reading the last row again.
5 Conclude with a summary of the three cases, giving the number of solutions for each.

Concluding sentence

If $m\neq 2$ and $m\neq -3$ , the system has a unique solution; if $m=2$ , it has infinitely many solutions with one parameter; if $m=-3$ , it is inconsistent.

The trap: Dividing a row by an expression such as $m-2$ without having set aside the case $m=2$ . The operation is then illegal, and the whole discussion that follows is worth nothing.

Marking: 1 mark for a row reduction with no illegal division, 1 mark for the general case, 0.5 mark per special case handled.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Substitute the solution into ALL the original equations

Replace the values found in every original equation, not only in the one used for the last back substitution. It is the only check that catches a pivoting error.

$a=1$ , $b=-2$ , $c=3$ give $1-2+3=2$ , $4-4+3=3$ and $9-6+3=6$ : all three equations are satisfied.
Check the general solution with two sets of parameters

When there are infinitely many solutions, give the parameters two different values and check both resulting vectors. If one passes and the other does not, the parametric form is wrong.

$s=0$ then $s=1$ must both give valid solutions; a single try does not test the coefficient of the parameter.
Count pivots and unknowns before concluding

Write the count explicitly: number of unknowns, number of pivots, difference. A negative difference is impossible, and a zero difference rules out announcing infinitely many solutions.

$4$ unknowns, $2$ pivots, so exactly $2$ free parameters, so two vectors in the basis of the solutions of the associated homogeneous system.
Read the last row before anything else

Before solving, check whether a row has the form $[0\ \dots\ 0\,|\,c]$ . If $c\neq 0$ , the work is over: the system has no solution, and any attempt to solve it would be time lost.

$[0\ \ 0\ \ 0\,|\,-4]$ means $0=-4$ : write “the system is inconsistent” and move on to the next question.
Check an inverse found by Gauss-Jordan

Multiply the matrix you found by the starting matrix: the product must be the identity. On a $3\times 3$ matrix, checking one row is often enough to spot an error.

A nonzero off-diagonal entry in $AA^{-1}$ signals an operation that was not applied to the right block.

The typical problem, taken apart

The parabola through three points, by Gaussian elimination

Find the real numbers $a$ , $b$ and $c$ such that the parabola with equation $y=ax^{2}+bx+c$ passes through the points $(1, 2)$ , $(2, 3)$ and $(3, 6)$ .

The three points of the question, not collinear: they determine exactly one parabola

y=ax^{2}+bx+c

, which is what the existence and uniqueness of the solution of the system express, not a lucky computation.

Step 1

Each point gives one equation: $a+b+c=2$ , $4a+2b+c=3$ , $9a+3b+c=6$ .

Why

Going from the geometric problem to the system is the only non-mechanical step. The unknowns are $a$ , $b$ , $c$ , not $x$ and $y$ , which are the data.

Step 2

Augmented matrix: $\begin{pmatrix} 1 & 1 & 1 \\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{pmatrix}$ with right-hand side $\begin{pmatrix} 2 \\ 3 \\ 6 \end{pmatrix}$ .

Why

Leave the equations behind right away: the matrix is quicker to write and the risk of dropping a term is much lower.

Step 3

$R_{2}\to R_{2}-4R_{1}$ gives $[0\ \ -2\ \ -3\,|\,-5]$ , and $R_{3}\to R_{3}-9R_{1}$ gives $[0\ \ -6\ \ -8\,|\,-12]$ .

Why

The pivot of the first column is already $1$ : the most favourable case, and it avoids any fraction at this step. Writing the two operations in the margin is worth half a mark.

Step 4

$R_{3}\to R_{3}-3R_{2}$ gives $[0\ \ 0\ \ 1\,|\,3]$ . The matrix is in row echelon form, with three pivots.

Why

Three pivots for three unknowns: the solution is unique, and you can say so before even back substituting. It is also what proves that only one parabola fits.

Step 5

Back substitution: the third row gives $c=3$ ; the second gives $-2b-3\times 3=-5$ , that is $-2b=4$ and $b=-2$ .

Why

Work up row by row, substituting each time the value just found. Writing the full equation before solving it avoids the sign error on $-2b$ .

Step 6

The first row gives $a+(-2)+3=2$ , so $a=1$ .

Why

The last substitution, and the quickest, since the pivot is $1$ . An error here would show up immediately in the next check.

Step 7

Check in the three original equations: $1-2+3=2$ , $4-4+3=3$ , $9-6+3=6$ .

Why

The three original equations, not the echelon rows: it is the only check that catches a badly performed elementary operation.

Step 8

Conclusion: the parabola sought has equation $y=x^{2}-2x+3$ .

Why

The question was about a parabola, not a triple: giving the answer as an equation is what the marking scheme expects, and it is worth half a mark.

The conclusion, written out

The system has the unique solution $a=1$ , $b=-2$ , $c=3$ : the parabola sought has equation $y=x^{2}-2x+3$ , and it is the only one through the three points.

The classic mistake on this problem: Reading the row echelon matrix as if it were reduced and announcing $a=2$ , $b=-5$ , $c=3$ by copying the last column. Back substitution is required as long as the pivots are not $1$ with zeros above them.

Learn by heart

• Three operations only: interchange, multiply by $k\neq 0$ , add a multiple of ANOTHER row.
• An operation replaces only ONE row; the reference row does not change.
• Row echelon form: back SUBSTITUTE. Reduced row echelon form: READ.
• Rank $=$ number of pivots. Free parameters $=$ unknowns $-$ pivots.
• $[0\ \dots\ 0\,|\,c]$ with $c\neq 0$ : no solution. $[0\ \dots\ 0\,|\,0]$ : redundant equation.
• Zero, one or infinitely many solutions. Never two.
• A homogeneous system ALWAYS has the trivial solution: it is never inconsistent.
• More equations than unknowns implies nothing: only the pivots decide.
• Inversion: $[A\,|\,I]$ to $[I\,|\,A^{-1}]$ , and stop if a row of the left block becomes zero.
• Never divide by an expression in the parameter without handling separately the value that makes it zero.

Frequently asked questions

What is the difference between Gaussian elimination and Gauss-Jordan elimination?

Gaussian elimination stops at the row echelon form, with zeros only below the pivots, and then needs back substitution to find the unknowns. Gauss-Jordan keeps going until every pivot equals one and is the only nonzero entry of its column: the solution can then be read directly in the last column.

How do you know how many solutions a system has?

Row reduce the augmented matrix, then count the pivots. A row of zeros followed by a nonzero number makes the system impossible. Otherwise, as many pivots as unknowns gives a unique solution, and fewer pivots than unknowns gives infinitely many solutions, with as many parameters as the difference.

What does a row of all zeros mean in the row echelon matrix?

It means that the corresponding equation was redundant, that is, it could be deduced from the others. It never makes the system impossible: it only lowers the number of pivots, so it raises the number of free parameters. A contradiction comes instead from a row of zeros followed by a nonzero number.

Can a homogeneous system have no solution?

No, never. The zero vector is always a solution, since the right-hand side is zero and stays zero after any elementary operation. The real question is whether there are other solutions, which happens exactly when the number of pivots is smaller than the number of unknowns.

How do you count the free parameters of a system?

Subtract the number of pivots from the number of unknowns. The number of equations you start with does not matter, because several equations can say the same thing. Each column without a pivot corresponds to a free unknown, which gets a parameter when you write the general solution.

Can you interchange two columns during Gaussian elimination?

No. Elementary operations act only on the rows, which represent the equations. Interchanging two columns would amount to renaming the unknowns, and the last column would no longer match the right variables. Only interchanging two rows is allowed.

Practise it

Corrected exercises: Linear systems, Gauss and Gauss-Jordan, 201-SN4-RE

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

16 corrected exercises
160 points
225 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Matrices, systems and determinants Next sheet Determinants and Cramer's rule

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-sn4-linear-systems. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-SN4-RE tutor in Montreal?

Get in touch for a first session. We go back over the moves that cost marks on the linear algebra exam, from reading a system to writing a proof about linearly independent sets, then we test them on exercises at the level of real CEGEP tests.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: linear systems, Gauss and Gauss-Jordan (201-SN4-RE)

The essentials

The three allowed operations, and nothing else

Row echelon or reduced row echelon: two forms, two readings

The three cases, and the count that tells them apart

The mistakes that cost marks

1. Multiplying a row by zero to create zeros

2. Replacing two rows at once by their combination

3. Taking an all-zero row for a contradiction

4. Counting the free parameters on the number of equations

5. Reading a row echelon form as if it were reduced

6. Declaring a homogeneous system impossible

7. Concluding that the system is impossible because it has more equations than unknowns

8. Carrying on with a Gauss-Jordan inversion after a zero row

Which method to choose

What the row echelon matrix says, row by row

Gauss or Gauss-Jordan, and how far to go

How the answer is expected to be written

Solving a system with infinitely many solutions

Discussing a system according to a parameter

Check before you hand in

The typical problem, taken apart

The parabola through three points, by Gaussian elimination

Learn by heart

Frequently asked questions

What is the difference between Gaussian elimination and Gauss-Jordan elimination?

How do you know how many solutions a system has?

What does a row of all zeros mean in the row echelon matrix?

Can a homogeneous system have no solution?

How do you count the free parameters of a system?

Can you interchange two columns during Gaussian elimination?

Corrected exercises: Linear systems, Gauss and Gauss-Jordan, 201-SN4-RE

See also

Looking for a 201-SN4-RE tutor in Montreal?