MATH 133 Linear Algebra and Geometry • McGill University, Montreal

Revision sheet: homogeneous systems, linear combinations and the rank theorem (MATH 133)

Q: How many basic solutions does a homogeneous system have?

Exactly as many as there are free variables, that is the number of unknowns minus the rank, where the rank is the number of pivots in the reduced form. The number of equations does not enter: three equations in five unknowns of rank two give three basic solutions, because the third equation reduced to a row of zeros and added no pivot.

Q: Does more equations than unknowns mean a homogeneous system has only the trivial solution?

No. The theorem only works in one direction: more unknowns than equations guarantees a nontrivial solution. With as many or more equations than unknowns, anything can happen, and you must reduce. Four equations in three unknowns can have a whole line of solutions if the rank is only two, because some of the equations repeat information the others already carry.

Q: How do I know if a vector b is a linear combination of the columns of A?

Row reduce the augmented matrix A with b as its last column, keeping the entries of b as letters if the question is general. The vector b is a combination of the columns exactly when the system is consistent, that is when no row reads zero equals a nonzero number. Each row of zeros on the left gives one condition on the entries of b.

Q: Why is every solution of Ax = b a particular solution plus a homogeneous one?

Because the product is linear. If p and x both solve Ax = b, then A times x minus p equals b minus b, which is zero, so x minus p solves the homogeneous system. Conversely, adding any homogeneous solution to p gives another solution. The homogeneous part tells you how many parameters there are, and p tells you where the solution set sits.

Q: Is my basic solution wrong if it is a multiple of the one in the answer key?

No. Any nonzero multiple of a basic solution is still accepted, and multiplying to clear fractions is standard practice in Nicholson. What must match is the number of basic solutions, which is always the number of unknowns minus the rank. A list with one more vector than that always contains a combination of the others, and a list with one fewer has missed a free variable.

This sheet is not a summary of Nicholson 1.3 and 2.2: you already have the textbook. It answers one question only, what makes students lose marks on homogeneous systems, linear combinations and the rank theorem in MATH 133 at McGill University, and which precise gesture avoids each loss.

Everything below reduces by hand, as on the exam. The chapter has one idea and it is the thread of the whole sheet: the answer lives in the COLUMNS. How many parameters, whether a right-hand side can be reached, what a solution set looks like: each is read on the columns of the reduced matrix, and each goes wrong the moment you count rows instead.

The thread of the chapter

Count the COLUMNS, never the equations: $Ax$ is a combination of the columns of $A$ , so whether $Ax = b$ can be solved is a question about the columns, and the number of parameters is $n - r$ , the columns without a pivot.

This chapter is part of MATH 133, Linear Algebra and Geometry (McGill)

What is on this sheet

1. The essentials
2. The rules in table form
3. The mistakes that cost marks
4. Which method to choose
5. How the answer is expected to be written
6. Check before you hand in
7. The typical problem, taken apart
8. Learn by heart
9. Frequently asked questions

Topics covered

Homogeneous system
Trivial and nontrivial solutions
Basic solutions
Rank of a matrix
Rank theorem
Linear combination
Matrix-vector product
Consistency of a linear system
Particular solution
Associated homogeneous system
Linearity of the matrix product
Balancing chemical equations

The essentials

Three facts about the columns, and nothing else

• Definition: if $A$ has columns $a_1, \ldots, a_n$ , then $Ax = x_1a_1 + \cdots + x_na_n$ . So $x$ needs one entry per COLUMN, $Ax$ has one entry per ROW, and $Ae_j = a_j$ .
• $Ax = b$ is consistent if and only if $b$ is a linear combination of the columns of $A$ . With $b$ in letters, the test is the last column of each zero row after reduction.
• Rank $r$ = number of pivots = number of columns WITH a pivot. A consistent system in $n$ unknowns has solutions with exactly $n - r$ parameters, one per column without a pivot.
• For $Ax = 0$ each parameter gives one basic solution (that parameter $1$ , the others $0$ ). There are exactly $n - r$ of them, and every solution is a linear combination of them.

The number of equations $m$ appears in this chapter in one place only: as an upper bound, $r \le m$ . That is where the theorem on homogeneous systems comes from ( $m < n$ forces $r < n$ ), and it is never a substitute for $r$ itself.

The shape of a solution set: particular plus homogeneous

• If $Ap = b$ , every solution of $Ax = b$ is $x = p + h$ with $Ah = 0$ . The homogeneous part says HOW MANY solutions; $p$ says WHERE they are.
• Linearity: $A(x + y) = Ax + Ay$ and $A(cx) = c(Ax)$ . Consequences: $A0 = 0$ , so $Ax = 0$ is always consistent; two solutions of $Ax = b$ differ by a solution of $Ax = 0$ ; their SUM solves $Ax = 2b$ .
• Two correct answers can have different particular solutions and different-looking basic solutions (scaled). They always have the same number of parameters.

p = (1, -1)

and

q = (3, 1)

both solve

x - y = 2

; their difference

q - p = (2, 2)

lies on

x - y = 0

. The blue solution set is the grey one shifted by

p

The rules in table form

Each row reads from left to right: the assumptions, then the result. A red cell is not an answer, it is the finding that the form settles nothing and the instruction to rewrite it. Every case is followed by a worked example.

What the rank says, whatever the shape of the matrix

Read the last column only after counting the pivots. The red row is the recipe students actually use, and it is not a rule at all.

Size of $A$	Rank $r$	Solutions of $Ax = 0$
$3 \times 5$	$2$	$3$ basic solutions
Example: Wide: $5 - 2 = 3$ parameters, although there are $3$ equations; the third row reduced to zero.
$5 \times 3$	$2$	$1$ basic solution
Example: Tall: $3 - 2 = 1$ parameter, a whole line of solutions with $5$ equations.
$4 \times 4$	$2$	$2$ basic solutions
Example: Square: rows $(1, 2, 0, -1)$ , $(2, 4, 1, 1)$ , $(3, 6, 1, 0)$ , $(1, 2, 1, 2)$ give $4 - 2 = 2$ parameters.
$3 \times 3$	$3$	trivial only
Example: $r = n = 3$ : no free column, $x = 0$ is the only solution.
$m \times n$	not counted	$n - m$ parameters rule that does not exist
Example: For the $4 \times 4$ above it predicts $4 - 4 = 0$ parameters; the truth is $2$ . What to do: Reduce, count the pivots, then write $n - r$ .

All five rows are homogeneous. For $Ax = b$ the same count holds only after consistency has been checked.

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. Subtracting the number of equations instead of the rank

the whole count, and every basic solution after it

What not to write

“ $3$ equations and $5$ unknowns, so $5 - 3 = 2$ parameters.”

What to write

“The reduced form has $2$ pivots, so the rank is $2$ and there are $5 - 2 = 3$ parameters.”

Left, two equations of rank

2

: only the origin. Right, three equations of rank

1

: a whole line. More equations, more solutions, because what counts is the pivots.

Why: An equation that is a combination of the others reduces to a zero row: it adds no pivot and removes no parameter. The rank theorem subtracts pivots, and the number of equations is only an upper bound on them.

2. Reading the theorem on homogeneous systems backwards

2 marks, and a wrong conclusion in every part that uses it

What not to write

“The system has $4$ equations and $3$ unknowns, so $Ax = 0$ has only the trivial solution.”

What to write

“The theorem does not apply ( $n \le m$ ). Reducing gives rank $2 < 3$ , so there is a nontrivial solution, $x = t(-1, 1, 1)$ .”

Why: More unknowns than equations GUARANTEES a nontrivial solution; the other shapes guarantee nothing either way. A square or tall matrix decides only after reduction, by comparing $r$ with $n$ .

3. Counting parameters on a system that has no solution

the whole question

What not to write

“ $x + y + z = 1$ , $x + y + z = 3$ : rank $1$ , $3$ unknowns, so $2$ parameters.”

What to write

“ $R_2 - R_1$ gives $0 = 2$ : the system is inconsistent and has no solution. The rank theorem does not apply.”

Why: The rank theorem starts with the word consistent. Check for a row $0 = c$ with $c \neq 0$ FIRST; count parameters only once you know there is something to parametrize.

4. A product Ax with the wrong number of entries

the question, since the product does not exist

What not to write

“ $C = \begin{pmatrix} 1 & 2 & -1 \\ 0 & 3 & 4 \end{pmatrix}$ and $x = (1, 1)$ , so $Cx = (3, 3)$ .”

What to write

“ $C$ has $3$ columns, so $x$ needs $3$ entries: $C(1, 0, 2) = a_1 + 2a_3 = (-1, 8)$ , a vector with $2$ entries, one per row.”

Why: $Ax$ pairs each entry of $x$ with a COLUMN. A mismatch in size is not a zero, it is an undefined expression, and the result has the size of a column, not the size of $x$ .

5. Testing consistency against the rows instead of the columns

2 marks, and the explicit combination that was asked

What not to write

“ $(1, 4, 3)$ is not a multiple of any row of $M$ , so $Mx = (1, 4, 3)$ has no solution.”

What to write

“After reduction the condition is $b_1 - b_2 + b_3 = 0$ , and $1 - 4 + 3 = 0$ : $(1, 4, 3) = 5a_1 - 2a_2$ is a combination of the COLUMNS.”

Why: $Mx$ is built from the columns, so the reachable right-hand sides are the combinations of the columns. The rows describe the equations, not the outputs. Every column must pass the condition, which is the fastest check on it.

6. Adding two solutions of Ax = b

2 marks

What not to write

“ $p$ and $q$ solve $Ax = b$ , so $p + q$ is a third solution.”

What to write

“ $A(p + q) = b + b = 2b$ , so $p + q$ solves $Ax = 2b$ . It is $p - q$ that solves $Ax = 0$ .”

Why: Adding is safe only for the homogeneous system. For $Ax = b$ , a combination $\alpha p + \beta q$ is a solution exactly when $\alpha + \beta = 1$ , for instance the midpoint $\frac{1}{2}(p + q)$ .

7. Giving one solution when the system has infinitely many

the marks for the structure of the solution set

What not to write

“ $Ax = (2, 3, 1)$ is solved by $x = (-3, -2, 5)$ .”

What to write

“Since $Aw = 0$ with $w = (-1, -1, 1) \neq 0$ , the solutions are $x = (-3, -2, 5) + t(-1, -1, 1)$ , $t$ real.”

Why: A particular solution is only the anchor. As soon as the associated homogeneous system has a nontrivial solution, the answer is a family, and the question solve always asks for all of it.

8. Rejecting a scaled basic solution, or accepting a sum as one

1 mark lost for nothing, or the count of basic solutions

What not to write

“My $(-1, 0, -4, 2, 0)$ is wrong, the key says $(-\frac{1}{2}, 0, -2, 1, 0)$ .” Or: “ $(4, 1, -2, 1, 0)$ is a fourth basic solution.”

What to write

“ $(-1, 0, -4, 2, 0)$ is $2$ times the key's vector, so it is accepted. $(4, 1, -2, 1, 0) = X_1 + X_2$ is a solution but not a basic one: there are exactly $n - r = 3$ .”

Why: Basic solutions are fixed up to nonzero multiples, and Nicholson scales them to clear fractions. Their NUMBER is fixed exactly, so a list longer than $n - r$ always contains a combination of the others.

Which method to choose

Which tool the question is asking for

Read the shape of the system and the verb of the question before touching a row

Both columns lie on the grey line, so every

x_1a_1 + x_2a_2

does too:

(2, -2)

is reached,

(2, 1)

is not. Two columns in the plane do not guarantee the plane.

If homogeneous, and more unknowns than equations → a nontrivial solution exists: say so from the theorem, reduce only if one is asked for

Example: $2 \times 4$ : guaranteed; $(-2, 4, 3, 0)$ is one
If homogeneous, square or taller than wide → reduce and compare the rank $r$ with $n$

Example: $4 \times 3$ of rank $2$ : a line of solutions, $t(-1, 1, 1)$
If how many parameters, how many basic solutions → check consistency, then $n - r$ with $r$ the number of pivots

Example: $3 \times 5$ of rank $2$ : $3$ basic solutions
If is $b$ a combination of the columns, can this target be reached, for which $b$ → reduce $(A \mid b)$ with $b$ in letters; each zero row gives a condition

Example: $b_1 - b_2 + b_3 = 0$ ; $(1, 4, 3)$ passes, $(1, 1, 1)$ fails
If $Au$ , $Av$ are given but $A$ is not → linearity: write the new vector as a combination of u and v

Example: $A(3u - 2v) = 3Au - 2Av$
If solve $Ax = b$ completely → one particular solution plus the combination of basic solutions of $Ax = 0$

Example: $(-3, 0, 2, 0) + s(3, 1, 0, 0) + t(-5, 0, 2, 1)$

Every branch but the first ends with a count of pivots. The one thing this chapter never needs is the number of equations, except to bound the rank.

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.

Writing the general solution so that a marker can follow it

When to use it: Any question that says solve, find all solutions, or give the general solution of $Ax = b$ or $Ax = 0$

1 Write the augmented matrix and reduce it, naming each operation on the line where it happens: $R_2 \to R_2 - 2R_1$ .
2 Check consistency out loud: no row $0 = c$ with $c \neq 0$ , so the system is consistent.
3 Name the pivots and the rank, then the free variables as parameters: rank $2$ , $4$ unknowns, so $4 - 2 = 2$ parameters, $x_2 = s$ and $x_4 = t$ .
4 Solve each pivot row for its leading variable in terms of the parameters.
5 Split the answer into a constant vector and one vector per parameter, and say which is which.
6 Multiply $A$ by the particular solution and by each basic solution: you must get $b$ and $0$ .

Concluding sentence

“The system is consistent and has rank $2$ , so its solutions involve $4 - 2 = 2$ parameters: $x = p + sX_1 + tX_2$ , where $p$ solves $Ax = b$ and the basic solutions $X_1$ , $X_2$ solve $Ax = 0$ .”

The trap: Stopping at the reduced matrix. A reduced matrix is not an answer: the question asks for the solutions, in vector form.

Marking: Typically 3 marks for the reduction with named operations, 1 for consistency and the rank, 3 for the solution in the form particular plus basic solutions, 1 for the verification.

Check before you hand in

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

Multiply back

Compute $Ap$ and $AX_j$ for each basic solution with the row-by-column rule. Five seconds per row, and it catches every sign slip in the back substitution.

$A(-3, 0, 2, 0) = (1, 4, 3)$ : correct. A row that gives $2$ instead of $0$ for a basic solution means a sign lost in one leading variable.
Count the pieces

The number of vectors multiplying a parameter must equal $n - r$ . More means one is a combination of the others; fewer means a free variable was forgotten.

$5$ unknowns, rank $2$ : exactly three basic solutions, never two.
Test the columns against a consistency condition

Every column $a_j = Ae_j$ is reachable, so it must satisfy the condition on $b$ . A column that fails it proves the condition is wrong.

$b_1 - b_2 + b_3 = 0$ on $(1, 2, 1)$ , $(2, 3, 1)$ , $(1, 0, -1)$ : $0$ , $0$ , $0$ .
Check the size of every product

An $m \times n$ matrix takes $n$ entries and returns $m$ . Write the sizes above the product before computing.

$2 \times 3$ times a vector with $3$ entries gives $2$ entries; a vector with $2$ entries cannot be multiplied at all.

The typical problem, taken apart

One system, solved in the form particular plus homogeneous

Solve $Ax = b$ with $A = \begin{pmatrix} 1 & -3 & 2 & 1 \\ 2 & -6 & 5 & 0 \\ 1 & -3 & 3 & -1 \end{pmatrix}$ and $b = (1, 4, 3)$ . Write the answer as a particular solution plus a combination of basic solutions, and say how many parameters there are and why.

Step 1

$\left(\begin{array}{cccc|c} 1 & -3 & 2 & 1 & 1 \\ 2 & -6 & 5 & 0 & 4 \\ 1 & -3 & 3 & -1 & 3 \end{array}\right)$ . $R_2 \to R_2 - 2R_1$ gives $(0, 0, 1, -2 \mid 2)$ and $R_3 \to R_3 - R_1$ gives $(0, 0, 1, -2 \mid 2)$ .

Why

Each operation is named on the line where it is used, because the method marks are given for the operations, not for the final matrix.

Step 2

$R_3 \to R_3 - R_2$ gives a zero row, $(0, 0, 0, 0 \mid 0)$ , and $R_1 \to R_1 - 2R_2$ gives $(1, -3, 0, 5 \mid -3)$ .

Why

The zero row ends with $0$ , so the system is consistent. That sentence must be written BEFORE counting parameters, since the rank theorem needs it.

Step 3

Pivots in columns $1$ and $3$ : rank $2$ , four unknowns, $4 - 2 = 2$ parameters. Set $x_2 = s$ and $x_4 = t$ .

Why

Three equations and yet two parameters, not one: the third equation added no pivot. This is the line where students subtract $4 - 3$ .

Step 4

$x_1 = -3 + 3s - 5t$ and $x_3 = 2 + 2t$ , so $x = (-3, 0, 2, 0) + s(3, 1, 0, 0) + t(-5, 0, 2, 1)$ .

Why

The constant vector is the particular solution $p$ ; the vectors multiplying $s$ and $t$ are the basic solutions of $Ax = 0$ . Writing the split is what shows the structure the question is testing.

Step 5

Check: $Ap = (-3 + 4, -6 + 10, -3 + 6) = (1, 4, 3)$ ; $A(3, 1, 0, 0) = (0, 0, 0)$ ; $A(-5, 0, 2, 1) = (-5 + 4 + 1, -10 + 10, -5 + 6 - 1) = (0, 0, 0)$ .

Why

Three products, one minute, and the whole answer is certified. A single nonzero entry locates the faulty back substitution.

The conclusion, written out

“The system is consistent, of rank $2$ , so its solutions involve $2$ parameters: $x = (-3, 0, 2, 0) + s(3, 1, 0, 0) + t(-5, 0, 2, 1)$ , $s, t$ real.”

The classic mistake on this problem: Writing only $x = (-3, 0, 2, 0)$ , one solution out of infinitely many, or only $s(3, 1, 0, 0) + t(-5, 0, 2, 1)$ , which solves $Ax = 0$ and not the system that was asked.

Learn by heart

• $Ax = x_1a_1 + \cdots + x_na_n$ : one entry of $x$ per column, one entry of $Ax$ per row.
• $Ax = b$ is consistent if and only if $b$ is a linear combination of the columns.
• Rank $=$ number of pivots. Consistent system: $n - r$ parameters. The number of equations only bounds $r$ .
• Homogeneous with MORE unknowns than equations: nontrivial solution guaranteed. The converse is FALSE.
• Basic solutions: exactly $n - r$ of them, each one fixed up to a nonzero multiple.
• Every solution of $Ax = b$ is $p + h$ , with $Ap = b$ and $Ah = 0$ .
• $A(x + y) = Ax + Ay$ , $A(cx) = c(Ax)$ , $A0 = 0$ ; two solutions of $Ax = b$ add up to a solution of $Ax = 2b$ .

Frequently asked questions

How many basic solutions does a homogeneous system have?

Exactly as many as there are free variables, that is the number of unknowns minus the rank, where the rank is the number of pivots in the reduced form. The number of equations does not enter: three equations in five unknowns of rank two give three basic solutions, because the third equation reduced to a row of zeros and added no pivot.

Does more equations than unknowns mean a homogeneous system has only the trivial solution?

No. The theorem only works in one direction: more unknowns than equations guarantees a nontrivial solution. With as many or more equations than unknowns, anything can happen, and you must reduce. Four equations in three unknowns can have a whole line of solutions if the rank is only two, because some of the equations repeat information the others already carry.

How do I know if a vector b is a linear combination of the columns of A?

Row reduce the augmented matrix A with b as its last column, keeping the entries of b as letters if the question is general. The vector b is a combination of the columns exactly when the system is consistent, that is when no row reads zero equals a nonzero number. Each row of zeros on the left gives one condition on the entries of b.

Why is every solution of Ax = b a particular solution plus a homogeneous one?

Because the product is linear. If p and x both solve Ax = b, then A times x minus p equals b minus b, which is zero, so x minus p solves the homogeneous system. Conversely, adding any homogeneous solution to p gives another solution. The homogeneous part tells you how many parameters there are, and p tells you where the solution set sits.

Is my basic solution wrong if it is a multiple of the one in the answer key?

No. Any nonzero multiple of a basic solution is still accepted, and multiplying to clear fractions is standard practice in Nicholson. What must match is the number of basic solutions, which is always the number of unknowns minus the rank. A list with one more vector than that always contains a combination of the others, and a list with one fewer has missed a free variable.

Practise it

Corrected exercises: Homogeneous systems and the rank theorem, MATH 133 at McGill

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.

10 corrected exercises
100 points
150 minutes

Do the exercises

Previous sheet Gaussian elimination Next sheet Matrix algebra

Looking for a MATH 133 tutor in Montreal?

Get in touch for a first session. This chapter is where linear algebra stops being arithmetic on rows and becomes a way of reading columns, and it is worth getting right before the midterm.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: homogeneous systems, linear combinations and the rank theorem (MATH 133)

The essentials

Three facts about the columns, and nothing else

The shape of a solution set: particular plus homogeneous

The rules in table form

What the rank says, whatever the shape of the matrix

The mistakes that cost marks

1. Subtracting the number of equations instead of the rank

2. Reading the theorem on homogeneous systems backwards

3. Counting parameters on a system that has no solution

4. A product Ax with the wrong number of entries

5. Testing consistency against the rows instead of the columns

6. Adding two solutions of Ax = b

7. Giving one solution when the system has infinitely many

8. Rejecting a scaled basic solution, or accepting a sum as one

Which method to choose

Which tool the question is asking for

How the answer is expected to be written

Writing the general solution so that a marker can follow it

Check before you hand in

The typical problem, taken apart

One system, solved in the form particular plus homogeneous

Learn by heart

Frequently asked questions

How many basic solutions does a homogeneous system have?

Does more equations than unknowns mean a homogeneous system has only the trivial solution?

How do I know if a vector b is a linear combination of the columns of A?

Why is every solution of Ax = b a particular solution plus a homogeneous one?

Is my basic solution wrong if it is a multiple of the one in the answer key?

Corrected exercises: Homogeneous systems and the rank theorem, MATH 133 at McGill

See also

Looking for a MATH 133 tutor in Montreal?