SME
Linear Algebra
Row reduction
Use this for “Solve x + y + z = 6, 2x + 3y + z = 11, 3x + 4y + 2z = 17. Is there one solution, none or infinitely many?”
Diagram
3 equations in 3 unknowns, the right-hand sides after the bar.
A row reads 0 = 0: it says nothing new, so there are infinitely many solutions.
The solution: x₀ = 7, y₀ = −1, z₀ = 0.
This is an example. Type your own values to start a new problem.
a₁₁
x
+
a₁₂
y
+
a₁₃
z
=
a₁₄
a₂₁
x
+
a₂₂
y
+
a₂₃
z
=
a₂₄
a₃₁
x
+
a₃₂
y
+
a₃₃
z
=
a₃₄
rank A
Rank of A
worked out (not typed)
rank [A | b]
Rank of [A | b]
worked out (not typed)
f
Free variables
worked out (not typed)
C
How many solutions
worked out (not typed)
x₀
Particular solution, x
worked out (not typed)
y₀
Particular solution, y
worked out (not typed)
z₀
Particular solution, z
worked out (not typed)
dₓ
Direction of the line, x
worked out (not typed)
dᵧ
Direction of the line, y
worked out (not typed)
dz
Direction of the line, z
worked out (not typed)
Formulas
rank
A
=
rank
[[
a₁₁
,
a₁₂
,
a₁₃
],
[
a₂₁
,
a₂₂
,
a₂₃
],
[
a₃₁
,
a₃₂
,
a₃₃
]]
2 = rank [[1, 1, 1], [2, 3, 1], [3, 4, 2]]
rank
[A
|
b]
=
rank
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]]
2 = rank [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]]
f
=
3
−
(rank
A)
1 = 3 − 2
C
=
one
solution
if
rank
A
=
rank
[A
|
b]
=
3,
none
if
rank
A
<
rank
[A
|
b],
else
infinitely
many
2 = 2 < 3, so infinitely many
x₀
=
x
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variables
0
7 = x solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variables 0
y₀
=
y
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variables
0
−1 = y solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variables 0
z₀
=
z
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variables
0
0 = z solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variables 0
dₓ
=
change
in
x
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variable
up
by
1
−2 = change in x solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variable up by 1
dᵧ
=
change
in
y
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variable
up
by
1
1 = change in y solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variable up by 1
dz
=
change
in
z
solving
[[
a₁₁
,
a₁₂
,
a₁₃
|
a₁₄
],
[
a₂₁
,
a₂₂
,
a₂₃
|
a₂₄
],
[
a₃₁
,
a₃₂
,
a₃₃
|
a₃₄
]],
the
free
variable
up
by
1
1 = change in z solving [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]], the free variable up by 1
Assumptions
•
Row operations (a swap, a row times a nonzero number, a multiple of one row added to another) keep the solutions.
•
A row that reads 0 = a nonzero number means no solution: rank [A | b] is then one more than rank A.
•
Each free variable adds a direction: one free variable gives a line of solutions.
Step-by-step
WE KNOW
a₁₁ = 1, a₁₂ = 1, a₁₃ = 1, a₁₄ = 6, a₂₁ = 2, a₂₂ = 3, a₂₃ = 1, a₂₄ = 11, a₃₁ = 3, a₃₂ = 4, a₃₃ = 2, a₃₄ = 17
FIND
rank of A (rank A), rank of [A | b] (rank [A | b]), free variables (f), how many solutions (C), particular solution, x (x₀), particular solution, y (y₀), particular solution, z (z₀), direction of the line, x (dₓ), direction of the line, y (dᵧ), direction of the line, z (dz)
Step 1 · Find rank of A (rank A)
Use rank A = rank [[a₁₁, a₁₂, a₁₃], [a₂₁, a₂₂, a₂₃], [a₃₁, a₃₂, a₃₃]]
Row reduce [A | b] to reduced echelon form, one operation a line. Each pivot in A’s three columns adds 1 to rank A.
Start: [[1, 1, 1 | 6], [2, 3, 1 | 11], [3, 4, 2 | 17]]
R₂ → R₂ − 2R₁: [[1, 1, 1 | 6], [0, 1, −1 | −1], [3, 4, 2 | 17]]
R₃ → R₃ − 3R₁: [[1, 1, 1 | 6], [0, 1, −1 | −1], [0, 1, −1 | −1]]
R₁ → R₁ − R₂: [[1, 0, 2 | 7], [0, 1, −1 | −1], [0, 1, −1 | −1]]
R₃ → R₃ − R₂: [[1, 0, 2 | 7], [0, 1, −1 | −1], [0, 0, 0 | 0]]
Pivots in columns 1 and 2: rank 2
rank A = 2
Step 2 · Find rank of [A | b] (rank [A | b])
Use rank [A | b] = rank [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]]
No row of the reduced matrix reads 0 = a nonzero number, so the last column adds no pivot.
rank [A | b] = 2
Step 3 · Find free variables (f)
Use f = 3 − (rank A)
Three unknowns: each column of A without a pivot is a free variable.
f
=
3
−
2
f
=
1
Step 4 · Find how many solutions (C)
Use C = one solution if rank A = rank [A | b] = 3, none if rank A < rank [A | b], else infinitely many
Consistent with a free variable: each value of it gives a solution, so there are infinitely many.
2 = 2 < 3: infinitely many
C
=
one
solution
if
2
=
2
=
3,
none
if
2
<
2,
else
infinitely
many
C
=
infinitely
many
Step 5 · Find particular solution, x (x₀)
Use x₀ = x solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variables 0
x has a pivot: its row reads x + 2z = 7. With z = 0, x = 7.
x₀
=
7
Step 6 · Find particular solution, y (y₀)
Use y₀ = y solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variables 0
y has a pivot: its row reads y − z = −1. With z = 0, y = −1.
y₀
=
−1
Step 7 · Find particular solution, z (z₀)
Use z₀ = z solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variables 0
z is a free variable: set it to 0 to get one particular solution.
z₀
=
0
Step 8 · Find direction of the line, x (dₓ)
Use dₓ = change in x solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variable up by 1
Its row reads x + 2z = 7: as z goes up by 1, x changes by −2 to keep the row true.
dₓ = −2
Step 9 · Find direction of the line, y (dᵧ)
Use dᵧ = change in y solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variable up by 1
Its row reads y − z = −1: as z goes up by 1, y changes by 1 to keep the row true.
dᵧ = 1
Step 10 · Find direction of the line, z (dz)
Use dz = change in z solving [[a₁₁, a₁₂, a₁₃ | a₁₄], [a₂₁, a₂₂, a₂₃ | a₂₄], [a₃₁, a₃₂, a₃₃ | a₃₄]], the free variable up by 1
z is the free variable: let it go up by 1.
(x, y, z) = (7, −1, 0) + t(−2, 1, 1), t any number
dz = 1
Check
Put the numbers back in. Both sides should match.
Pivots in A: 1 + 1 = 2 ✓
Pivots in [A | b]: 1 + 1 = 2 ✓
1 = 3 − 2 ✓
2 = 2 < 3, so infinitely many ✓
Row 1: 1 × 7 + 1 × (−1) + 1 × 0 = 6 ✓
Row 2: 2 × 7 + 3 × (−1) + 1 × 0 = 11 ✓
Row 3: 3 × 7 + 4 × (−1) + 2 × 0 = 17 ✓
Row 1: 1 × (−2) + 1 × 1 + 1 × 1 = 0 ✓
Row 2: 2 × (−2) + 3 × 1 + 1 × 1 = 0 ✓
Row 3: 3 × (−2) + 4 × 1 + 2 × 1 = 0 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
The inverse by row reduction
Use this for “Reduce [A | I] to find A⁻¹ for A = [[2, 1, 0], [1, 1, 0], [0, 0, 3]].”
LU factorization
Use this for “Factor A = [[2, 1, 1], [4, 3, 3], [8, 7, 9]] as A = LU.”
Echelon and reduced echelon form
Use this for “Is [[1, 3, 4], [0, 1, 2]] in echelon form, reduced echelon form, or neither?”