About

1.1-1.2 Systems of Linear Equations & Row Reduction

Theory: Systems of Linear Equations & Row Reduction

A linear equation in the variables x1,x2,…,xnx_1, x_2, \dots, x_n has the form:

a1x1+a2x2+⋯+anxn=ba_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b

A system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. A system has either:

  1. No solution (inconsistent),
  2. Exactly one unique solution (consistent), or
  3. Infinitely many solutions (consistent).

Matrix Representation & Row Operations

A linear system can be represented compactly by its coefficient matrix AA and its augmented matrix [A∣b][A \mid \mathbf{b}]:

x1−2x2+x3=02x2−8x3=8−4x1+5x2+9x3=−9⟹[1−21002−88−459−9]\begin{aligned} x_1 - 2x_2 + x_3 &= 0 \\ 2x_2 - 8x_3 &= 8 \\ -4x_1 + 5x_2 + 9x_3 &= -9 \end{aligned} \quad \Longrightarrow \quad \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ -4 & 5 & 9 & -9 \end{array}\right]

There are three elementary row operations:

  1. Replacement: Replace one row by the sum of itself and a multiple of another row (Ri←Ri+cRjR_i \leftarrow R_i + c R_j).
  2. Interchange: Swap two rows (Ri↔RjR_i \leftrightarrow R_j).
  3. Scaling: Multiply all entries in a row by a non-zero constant (Ri←cRiR_i \leftarrow c R_i, c≠0c \ne 0).

Two matrices are row equivalent (A∼BA \sim B) if one can be transformed into the other by a sequence of elementary row operations. Row equivalent augmented matrices share the exact same solution set.

Echelon Forms

A rectangular matrix is in Row Echelon Form (REF) if:

  1. All non-zero rows are above any rows of all zeros.
  2. Each leading entry (pivot) of a row is in a column to the right of the leading entry of the row above it.
  3. All entries in a column below a leading entry are zeros.

A matrix is in Reduced Row Echelon Form (RREF) if, in addition to REF: 4. The leading entry in each non-zero row is 11. 5. Each leading 11 is the only non-zero entry in its entire column.

[!NOTE] Uniqueness of RREF (Theorem 1): Each matrix is row equivalent to one and only one reduced echelon matrix.

Existence and Uniqueness Theorem (Theorem 2)

A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column — that is, if and only if an echelon form contains no row of the form:

[00⋯0b]with b≠0\left[\begin{array}{cccc|c} 0 & 0 & \cdots & 0 & b \end{array}\right] \quad \text{with } b \ne 0

If a linear system is consistent, then the solution set contains:

Solved Examples (Textbook Questions)

Exercise 1

(Adapted from Lay §1.2, Exercise 11)

Solve the linear system by finding the reduced row echelon form (RREF) of its augmented matrix:

x1−2x2−x3+3x4=0−2x1+4x2+5x3−5x4=33x1−6x2−6x3+8x4=−3\begin{aligned} x_1 - 2x_2 - x_3 + 3x_4 &= 0 \\ -2x_1 + 4x_2 + 5x_3 - 5x_4 &= 3 \\ 3x_1 - 6x_2 - 6x_3 + 8x_4 &= -3 \end{aligned}

Identify the pivot columns, state which variables are basic and which are free, and write the general solution in parametric form.

Show solution ↓
Solution

Step 1: Write the augmented matrix.

[1−2−130−245−533−6−68−3]\left[\begin{array}{cccc|c} 1 & -2 & -1 & 3 & 0 \\ -2 & 4 & 5 & -5 & 3 \\ 3 & -6 & -6 & 8 & -3 \end{array}\right]

Step 2: Forward phase (reduce to echelon form).

Use the pivot in row 1 (11) to eliminate entries below it in column 1:

  • R2←R2+2R1R_2 \leftarrow R_2 + 2R_1: [−2,4,5,−5,3]+2[1,−2,−1,3,0]=[0,0,3,1,3][-2, 4, 5, -5, 3] + 2[1, -2, -1, 3, 0] = [0, 0, 3, 1, 3]
  • R3←R3−3R1R_3 \leftarrow R_3 - 3R_1: [3,−6,−6,8,−3]−3[1,−2,−1,3,0]=[0,0,−3,−1,−3][3, -6, -6, 8, -3] - 3[1, -2, -1, 3, 0] = [0, 0, -3, -1, -3]

The matrix becomes:

[1−2−1300031300−3−1−3]\left[\begin{array}{cccc|c} 1 & -2 & -1 & 3 & 0 \\ 0 & 0 & 3 & 1 & 3 \\ 0 & 0 & -3 & -1 & -3 \end{array}\right]

Next, use the pivot in row 2 (33) to eliminate the entry below it in column 3:

  • R3←R3+R2R_3 \leftarrow R_3 + R_2: [0,0,−3,−1,−3]+[0,0,3,1,3]=[0,0,0,0,0][0, 0, -3, -1, -3] + [0, 0, 3, 1, 3] = [0, 0, 0, 0, 0]

We obtain an echelon form:

[1−2−1300031300000]\left[\begin{array}{cccc|c} 1 & -2 & -1 & 3 & 0 \\ 0 & 0 & 3 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]

Step 3: Backward phase (reduce to RREF).

Scale row 2 by 13\frac{1}{3} to create a leading 1:

  • R2←13R2R_2 \leftarrow \frac{1}{3}R_2: [1−2−1300011/3100000]\left[\begin{array}{cccc|c} 1 & -2 & -1 & 3 & 0 \\ 0 & 0 & 1 & 1/3 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]

Eliminate the entry above the pivot in column 3:

  • R1←R1+R2R_1 \leftarrow R_1 + R_2: [1,−2,−1,3,0]+[0,0,1,1/3,1]=[1,−2,0,10/3,1][1, -2, -1, 3, 0] + [0, 0, 1, 1/3, 1] = [1, -2, 0, 10/3, 1]

The RREF is:

[1−2010/310011/3100000]\left[\begin{array}{cccc|c} 1 & -2 & 0 & 10/3 & 1 \\ 0 & 0 & 1 & 1/3 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]

Step 4: Analyze variables and write the solution.

  • The pivot positions are in column 1 and column 3.
  • Basic variables: x1,x3x_1, x_3.
  • Free variables: x2,x4x_2, x_4.

Translate the RREF back into algebraic equations:

x1−2x2+103x4=1  ⟹  x1=1+2x2−103x4x3+13x4=1  ⟹  x3=1−13x4\begin{aligned} x_1 - 2x_2 + \frac{10}{3}x_4 &= 1 \implies x_1 = 1 + 2x_2 - \frac{10}{3}x_4 \\ x_3 + \frac{1}{3}x_4 &= 1 \implies x_3 = 1 - \frac{1}{3}x_4 \end{aligned}

The general solution is:

{x1=1+2x2−103x4x2 is freex3=1−13x4x4 is free\begin{cases} x_1 = 1 + 2x_2 - \frac{10}{3}x_4 \\ x_2 \text{ is free} \\ x_3 = 1 - \frac{1}{3}x_4 \\ x_4 \text{ is free} \end{cases}
Exercise 2

(Adapted from Lay §1.1, Exercise 19 & §1.2, Exercise 21)

Determine all values of the parameter hh and kk for which the linear system represented by the augmented matrix:

[1h248k]\left[\begin{array}{cc|c} 1 & h & 2 \\ 4 & 8 & k \end{array}\right]

has:

  1. No solution (inconsistent)
  2. A unique solution
  3. Infinitely many solutions
Show solution ↓
Solution

Step 1: Perform row reduction to echelon form.

Apply the row replacement R2←R2−4R1R_2 \leftarrow R_2 - 4R_1:

R2−4R1=[4,8,k]−4[1,h,2]=[0,8−4h,k−8]R_2 - 4R_1 = [4, 8, k] - 4[1, h, 2] = [0, 8 - 4h, k - 8]

The echelon form is:

[1h208−4hk−8]\left[\begin{array}{cc|c} 1 & h & 2 \\ 0 & 8 - 4h & k - 8 \end{array}\right]

Step 2: Analyze the second row.

  1. No solution: By Theorem 2, a system has no solution if and only if the second row has the form [00b]\left[\begin{array}{cc|c} 0 & 0 & b \end{array}\right] with b≠0b \ne 0. Therefore:

    8−4h=0andk−8≠08 - 4h = 0 \quad \text{and} \quad k - 8 \ne 0 h=2andk≠8h = 2 \quad \text{and} \quad k \ne 8

  2. A unique solution: The system is consistent and has a unique solution if both column 1 and column 2 are pivot columns (0 free variables). This requires the leading coefficient in row 2 to be non-zero:

    8−4h≠0  ⟹  h≠2(for any value of k)8 - 4h \ne 0 \implies h \ne 2 \quad (\text{for any value of } k)

  3. Infinitely many solutions: The system is consistent and has at least one free variable if the bottom row is completely zero:

    8−4h=0andk−8=08 - 4h = 0 \quad \text{and} \quad k - 8 = 0 h=2andk=8h = 2 \quad \text{and} \quad k = 8

    In this case, row 2 becomes [0  0∣0][0 \; 0 \mid 0], column 2 has no pivot (x2x_2 is free), yielding infinitely many solutions.

Exercise 3

(Adapted from Lay §1.1, Exercise 23)

Determine if the three lines given by the following equations have a common point of intersection:

x1−4x2=12x1−x2=−3−x1−3x2=4\begin{aligned} x_1 - 4x_2 &= 1 \\ 2x_1 - x_2 &= -3 \\ -x_1 - 3x_2 &= 4 \end{aligned}
Show solution ↓
Solution

A common point of intersection corresponds to a solution (x1,x2)(x_1, x_2) satisfying all three equations simultaneously.

Step 1: Set up the augmented matrix.

[1−412−1−3−1−34]\left[\begin{array}{cc|c} 1 & -4 & 1 \\ 2 & -1 & -3 \\ -1 & -3 & 4 \end{array}\right]

Step 2: Row reduce to echelon form.

  • R2←R2−2R1R_2 \leftarrow R_2 - 2R_1: [2,−1,−3]−2[1,−4,1]=[0,7,−5][2, -1, -3] - 2[1, -4, 1] = [0, 7, -5]
  • R3←R3+R1R_3 \leftarrow R_3 + R_1: [−1,−3,4]+[1,−4,1]=[0,−7,5][-1, -3, 4] + [1, -4, 1] = [0, -7, 5]

The matrix becomes:

[1−4107−50−75]\left[\begin{array}{cc|c} 1 & -4 & 1 \\ 0 & 7 & -5 \\ 0 & -7 & 5 \end{array}\right]
  • R3←R3+R2R_3 \leftarrow R_3 + R_2: [0,−7,5]+[0,7,−5]=[0,0,0][0, -7, 5] + [0, 7, -5] = [0, 0, 0]

The echelon form is:

[1−4107−5000]\left[\begin{array}{cc|c} 1 & -4 & 1 \\ 0 & 7 & -5 \\ 0 & 0 & 0 \end{array}\right]

Step 3: Solve for x1x_1 and x2x_2. Row 3 is [0  0∣0][0 \; 0 \mid 0], so the system is consistent. From row 2:

7x2=−5  ⟹  x2=−577x_2 = -5 \implies x_2 = -\frac{5}{7}

Substitute into row 1:

x1−4(−57)=1  ⟹  x1+207=77  ⟹  x1=−137x_1 - 4\left(-\frac{5}{7}\right) = 1 \implies x_1 + \frac{20}{7} = \frac{7}{7} \implies x_1 = -\frac{13}{7}

Conclusion: The three lines do have a common point of intersection, located at:

(x1,x2)=(−137,−57)(x_1, x_2) = \left(-\frac{13}{7}, -\frac{5}{7}\right)