studyhubDiscrete Structures III

Notes / Unit 1 · Module 1 · Exam 1 · §1.1–1.2

Systems of Linear Equations

A system of linear equations has exactly one solution, infinitely many, or none, and row-reducing its augmented matrix tells you which. The exam asks you to spot a linear equation, write a solution set in parameters, carry out row operations in the R1 ↔ R2 notation, and solve by Gaussian elimination with back-substitution or by Gauss-Jordan elimination.

1.1Linear equations

A linear equation in n variables x₁, x₂, …, xₙ has the form a₁x₁ + a₂x₂ + ⋯ + aₙxₙ = b. The coefficients a₁, …, aₙ and the constant term b are real numbers. a₁ is the leading coefficient and x₁ the leading variable.

A line in the plane, a₁x + a₂y = b, is a linear equation in two variables; a plane in space, a₁x + a₂y + a₃z = b, is one in three.

  • No products of variables (xy) and no roots of variables (√x).
  • No variable inside a trigonometric, exponential or logarithmic function (sin x, eˣ, ln x).
  • Every variable appears to the first power only.
LinearNot linear
3x + 2y = 7xy + z = 2 (product of variables)
½x + y − πz = √2eˣ − 2y = 4 (x in an exponent)
(sin π)x₁ − 4x₂ = e²sin x₁ + 2x₂ − 3x₃ = 0 (x₁ inside a sine)

1.2Solutions and parametric representation

A solution of a linear equation is a sequence of numbers s₁, s₂, …, sₙ that makes the equation true when you substitute x₁ = s₁, …, xₙ = sₙ. It may be written (x₁, x₂, …, xₙ) = (s₁, s₂, …, sₙ). The set of all solutions is the solution set.

To describe the whole solution set, use a parametric representation: solve for one variable, call each remaining free variable a parameter, and write everything in terms of the parameters.

Worked example

Slides: x₁ + 2x₂ = 4

  1. 1Solve for the leading variable: x₁ = 4 − 2x₂.
  2. 2x₂ is free; let x₂ = t, where t is any real number.
  3. 3Solution set: x₁ = 4 − 2t, x₂ = t.
  4. 4A particular solution comes from choosing t: t = 1 gives (2, 1), t = 0 gives (4, 0).

Worked example

Slides: 3x₁ + 2x₂ − x₃ = 3

  1. 1Solve for x₃: x₃ = 3x₁ + 2x₂ − 3.
  2. 2Two variables are free: x₁ = t₁ and x₂ = t₂.
  3. 3Solution set: x₁ = t₁, x₂ = t₂, x₃ = 3t₁ + 2t₂ − 3, where t₁, t₂ are real numbers.

1.3Systems and how many solutions they have

A system of m linear equations in n variables (a linear system) is m linear equations in the same n variables. A solution of the system is a sequence s₁, …, sₙ that is a solution of every equation in it.

Example from the slides: (x₁, x₂) = (−1, 3) solves 3x₁ + 2x₂ = 3 and −x₁ + x₂ = 4, since 3(−1) + 2(3) = 3 and −(−1) + 3 = 4.

Number of solutionsCalledTwo lines in the plane
Exactly oneConsistentIntersecting lines
Infinitely manyConsistentCoincident lines (the same line)
NoneInconsistentParallel lines

Worked example

Slides: what do the graphs look like?

  1. 1x + y = 3 and x − y = −1: different slopes, so the lines intersect once, at (1, 2).
  2. 2−3x + y = 5 and −6x + 2y = 8: the second left side is 2 times the first, but 2 · 5 = 10 ≠ 8. Parallel lines, no solution.
  3. 32x − y = 1 and 4x − 2y = 2: the second equation is exactly 2 times the first. Coincident lines, infinitely many solutions.

1.4Matrices and the augmented matrix

An m × n matrix is a rectangular array with m rows and n columns. The entry aᵢⱼ sits in row i (the row subscript) and column j (the column subscript). When m = n the matrix is square of order n, and a₁₁, a₂₂, …, aₙₙ are its main diagonal entries.

Augmented matrix
The coefficients and the constant terms of a system: one row per equation, one column per variable, and a last column of constants. m equations in n variables give an m × (n + 1) matrix.
Coefficient matrix
The same without the constants: m × n.

Slides: the system x − 4y + 3z = 5, −x + 3y − z = −3, 2x − 4z = 6 has this augmented matrix and coefficient matrix:

[  1  −4   3  |  5 ]
[ −1   3  −1  | −3 ]
[  2   0  −4  |  6 ]

[  1  −4   3 ]
[ −1   3  −1 ]
[  2   0  −4 ]

1.5Elementary row operations

These three operations on a system give an equivalent system (same solutions). On the augmented matrix they are the elementary row operations:

OperationNotationOn the system
Interchange two rowsR1 ↔ R2Swap two equations
Multiply a row by a nonzero constant½R1 → R1Multiply an equation by a nonzero constant
Add a multiple of a row to another row−2R1 + R3 → R3Add a multiple of one equation to another

Two matrices are row-equivalent when one can be obtained from the other by a finite sequence of elementary row operations. The slides' examples:

[  0   1  3  | 4 ]
[ −1   2  0  | 3 ]
[  2  −3  4  | 1 ]

[ −1   2  0  | 3 ]
[  0   1  3  | 4 ]
[  2  −3  4  | 1 ]
R1 ↔ R2
[ 2  −4   6  | −2 ]
[ 1   3  −3  |  0 ]
[ 5  −2   1  |  2 ]

[ 1  −2   3  | −1 ]
[ 1   3  −3  |  0 ]
[ 5  −2   1  |  2 ]
½R1 → R1
[ 1  2  −4  |  3 ]
[ 0  3  −2  | −1 ]
[ 2  1   5  | −2 ]

[ 1   2  −4  |  3 ]
[ 0   3  −2  | −1 ]
[ 0  −3  13  | −8 ]
−2R1 + R3 → R3

1.6Row-echelon and reduced row-echelon form

A matrix is in row-echelon form when:

  1. Any rows of all zeros are at the bottom.
  2. The first nonzero entry of every other row is 1, a leading 1.
  3. In two successive nonzero rows, the leading 1 of the higher row is farther left than the one below: a stair-step.

It is in reduced row-echelon form when, in addition, every column with a leading 1 has zeros everywhere else, above and below it.

Slides' matrixRow-echelon?Reduced?
a. [1 2 −1 4; 0 1 0 3; 0 0 1 2]YesNo: 2 and −1 sit above leading 1s
b. [1 −5 2 −1 3; 0 0 1 3 −2; 0 0 0 1 4; 0 0 0 0 1]YesNo
c. [1 2 −3 4; 0 2 1 −1; 0 0 1 −3]No: row 2 starts with 2, not 1No
d. [1 2 −1 2; 0 0 0 0; 0 1 2 −4]No: the zero row is not at the bottomNo
e. [1 0 0 −1; 0 1 0 2; 0 0 1 3; 0 0 0 0]YesYes
f. [0 1 0 5; 0 0 1 3; 0 0 0 0]YesYes

1.7Gaussian elimination with back-substitution

  1. Write the augmented matrix of the system.
  2. Use elementary row operations to bring it to row-echelon form: working column by column, get a leading 1, then make every entry below it 0.
  3. Write the system the row-echelon matrix stands for and back-substitute from the bottom equation up.

Worked example

Slides, Example 1: x − 2y + 3z = 9, −x + 3y = −4, 2x − 5y + 5z = 17

  1. 1Augmented matrix [1 −2 3 | 9; −1 3 0 | −4; 2 −5 5 | 17].
  2. 2R1 + R2 → R2 gives row 2 = [0 1 3 | 5].
  3. 3−2R1 + R3 → R3 gives row 3 = [0 −1 −1 | −1].
  4. 4R2 + R3 → R3 gives row 3 = [0 0 2 | 4].
  5. 5½R3 → R3 gives row 3 = [0 0 1 | 2]. Row-echelon form: x − 2y + 3z = 9, y + 3z = 5, z = 2.
  6. 6Back-substitute: z = 2; y = 5 − 3(2) = −1; x = 9 + 2(−1) − 3(2) = 1. Solution (1, −1, 2).
[ 1  −2  3  | 9 ]
[ 0   1  3  | 5 ]
[ 0   0  1  | 2 ]
The row-echelon form reached

Worked example

Slides: an inconsistent system, x − 3y + z = 1, 2x − y − 2z = 2, x + 2y − 3z = −1

  1. 1−2R1 + R2 → R2 gives [0 5 −4 | 0]; −R1 + R3 → R3 gives [0 5 −4 | −2].
  2. 2−R2 + R3 → R3 gives [0 0 0 | −2], the equation 0 = −2.
  3. 3That can never be true, so the system has no solution.

Worked example

Slides: infinitely many solutions, y − z = 0, x − 3z = −1, −x + 3y = 1

  1. 1R1 ↔ R2 puts a leading 1 first: [1 0 −3 | −1; 0 1 −1 | 0; −1 3 0 | 1].
  2. 2R1 + R3 → R3 gives [0 3 −3 | 0]; −3R2 + R3 → R3 gives [0 0 0 | 0].
  3. 3Row 3 is 0 = 0. z has no leading 1, so z = t; then y = t and x = −1 + 3t.
  4. 4Solution set: x = −1 + 3t, y = t, z = t, for any real t.

For practice, the slides' other 1.1 systems: x − y − z = 0, x + 2y − z = 6, 2x − z = 5 has solution (3, 2, 1); x + y + z = 2, −x + 3y + 2z = 8, 4x + y = 4 has solution (0, 4, −2).

1.8Gauss-Jordan elimination and homogeneous systems

Gauss-Jordan elimination carries Gaussian elimination on until the matrix is in reduced row-echelon form: after the zeros below each leading 1, clear the entries above it too. The solution is then read straight off, with no back-substitution. Done on Example 1 it ends at [1 0 0 | 1; 0 1 0 | −1; 0 0 1 | 2].

Worked example

Slides, Exercise 2: 2x₁ + 4x₂ − 2x₃ = 0, 3x₁ + 5x₂ = 1

  1. 1½R1 → R1 gives [1 2 −1 | 0].
  2. 2−3R1 + R2 → R2 gives [0 −1 3 | 1]; −R2 → R2 gives [0 1 −3 | −1].
  3. 3−2R2 + R1 → R1 gives [1 0 5 | 2]. Reduced form: [1 0 5 | 2; 0 1 −3 | −1].
  4. 4x₃ has no leading 1, so x₃ = t. Then x₁ = 2 − 5t, x₂ = −1 + 3t, x₃ = t.
[ 1  0   5  |  2 ]
[ 0  1  −3  | −1 ]
Reduced row-echelon form of Exercise 2

The slides' 4-variable Examples 2 and 3 work the same way; check your answers against (x₁, x₂, x₃, x₄) = (−1, 2, 1, 3) and (2, −1, 3, 0).

A system is homogeneous when every constant term is 0. Setting every variable to 0 always works, the trivial solution, so:

Every homogeneous system is consistent. If it has fewer equations than variables, it has infinitely many solutions.

Worked example

Slides, Example 4: x₁ − x₂ + 3x₃ = 0, 2x₁ + x₂ + 3x₃ = 0

  1. 1−2R1 + R2 → R2 gives [0 3 −3 | 0]; ⅓R2 → R2 gives [0 1 −1 | 0].
  2. 2R2 + R1 → R1 gives [1 0 2 | 0]. Reduced form: [1 0 2 | 0; 0 1 −1 | 0].
  3. 3x₃ = t is free: x₁ = −2t, x₂ = t, x₃ = t. t = 0 gives the trivial solution, t = 1 gives (−2, 1, 1).

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

  1. 1.Is (sin π)x₁ − 4x₂ = e² linear? Is sin x₁ + 2x₂ = 0? Why the difference?
  2. 2.Write the solution set of x₁ + 2x₂ = 4 in parameters, and give two particular solutions.
  3. 3.What size is the augmented matrix of 3 equations in 4 variables, and what goes in the column of a variable an equation doesn't contain?
  4. 4.Apply −2R1 + R3 → R3 to [1 2 −4 | 3; 0 3 −2 | −1; 2 1 5 | −2]. Which rows change?
  5. 5.After elimination the last row is 0 0 0 | 0. What does that tell you? What if it is 0 0 0 | 5?
  6. 6.Why is every homogeneous system consistent, and when must it have infinitely many solutions?