Linear Systems

Jim Hefferon · GFDL + CC BY-SA 2.5 · Linear Algebra

A system of linear equations can always be solved by row reduction. Convert the augmented matrix to echelon form, then back-substitute. Gauss-Jordan elimination goes further, reducing to reduced row echelon form where every solution reads off directly.

Systems as augmented matrices

A system of linear equations is a list of constraints, each linear in the unknowns. Writing it as an augmented matrix strips away the variable names and keeps only the coefficients. Row operations on the matrix correspond to legitimate algebraic moves on the system.

Scheme

; Represent an augmented matrix as a list of rows.
; Each row is a list of numbers (coefficients | constant).

(define mat '((2 1 -1 8)
              (-3 -1 2 -11)
              (-2 1 2 -3)))

; Scale a row by a factor
(define (scale-row row k)
  (map (lambda (x) (* x k)) row))

; Add two rows element-wise
(define (add-rows r1 r2)
  (map + r1 r2))

; Row replacement: Ri <- Ri + k * Rj
(define (row-replace mat i j k)
  (let* ((rows (list->vector mat))
         (ri (vector-ref rows i))
         (rj (vector-ref rows j))
         (new-ri (add-rows ri (scale-row rj k))))
    (vector-set! rows i new-ri)
    (vector->list rows)))

; Eliminate below pivot in column 0
(define step1 (row-replace mat 1 0 3/2))  ; R2 <- R2 + (3/2)R1
(define step2 (row-replace step1 2 0 1))  ; R3 <- R3 + R1

(display "After eliminating column 0:")
(newline)
(for-each (lambda (row)
  (display "  ")
  (display row)
  (newline)) step2)

Echelon form and back-substitution

A matrix is in echelon form when each leading entry is to the right of the one above it, and all entries below each leading entry are zero. Once you reach echelon form, the system solves by back-substitution: start from the bottom row and work up.

Scheme

; Continue from the previous step to reach echelon form.
; After step2, our matrix is:
;   (2   1   -1   8)
;   (0  1/2  1/2  1)
;   (0   2    1   5)
;
; Eliminate below the pivot in column 1.

(define (scale-row row k)
  (map (lambda (x) (* x k)) row))

(define (add-rows r1 r2)
  (map + r1 r2))

(define echelon '((2 1 -1 8)
                  (0 1/2 1/2 1)
                  (0 2 1 5)))

; R3 <- R3 + (-4)*R2
(define (row-replace mat i j k)
  (let* ((rows (list->vector mat))
         (ri (vector-ref rows i))
         (rj (vector-ref rows j))
         (new-ri (add-rows ri (scale-row rj k))))
    (vector-set! rows i new-ri)
    (vector->list rows)))

(define result (row-replace echelon 2 1 -4))

(display "Echelon form:")
(newline)
(for-each (lambda (row)
  (display "  ")
  (display row)
  (newline)) result)

; Back-substitute from row 3:
;   -1 * x3 = 1  =>  x3 = -1
;   (1/2)x2 + (1/2)(-1) = 1  =>  x2 = 3
;   2*x1 + 3 - (-1) = 8  =>  x1 = 2
(newline)
(display "Solution: x1=2, x2=3, x3=-1")

Gauss-Jordan elimination

Gauss-Jordan goes beyond echelon form: eliminate upward too, and scale each pivot to 1. The result is reduced row echelon form (RREF). Every column either contains a pivot or represents a free variable. The solution reads off without any arithmetic.

Scheme

; Full Gauss-Jordan elimination on a 3x3 system.
; We'll go from raw system to RREF.

(define (scale-row row k) (map (lambda (x) (* x k)) row))
(define (add-rows r1 r2) (map + r1 r2))

(define (row-replace mat i j k)
  (let* ((v (list->vector mat))
         (new-ri (add-rows (vector-ref v i) (scale-row (vector-ref v j) k))))
    (vector-set! v i new-ri)
    (vector->list v)))

(define (scale-pivot mat i k)
  (let ((v (list->vector mat)))
    (vector-set! v i (scale-row (vector-ref v i) k))
    (vector->list v)))

; Start: x + y = 5, 2x - y = 1
(define m '((1 1 5)
            (2 -1 1)))

; Forward: R2 <- R2 - 2*R1
(define m1 (row-replace m 1 0 -2))

; Scale R2: R2 <- (-1/3)*R2
(define m2 (scale-pivot m1 1 -1/3))

; Backward: R1 <- R1 - R2
(define m3 (row-replace m2 0 1 -1))

(display "RREF:")
(newline)
(for-each (lambda (row)
  (display "  ")
  (display row)
  (newline)) m3)
; Should be ((1 0 2) (0 1 3)) => x=2, y=3

Free variables and solution sets

When a system has more unknowns than pivot positions, the non-pivot columns correspond to free variables. The solution set is a line, plane, or higher-dimensional flat through the particular solution. This is where linear algebra meets geometry.

Scheme

; A system with a free variable:
;   x + 2y + z = 4
;   2x + 4y + 3z = 9
; Two equations, three unknowns.

(define (scale-row row k) (map (lambda (x) (* x k)) row))
(define (add-rows r1 r2) (map + r1 r2))

(define m '((1 2 1 4)
            (2 4 3 9)))

; R2 <- R2 - 2*R1
(define m1
  (let ((v (list->vector m)))
    (vector-set! v 1 (add-rows (vector-ref v 1) (scale-row (vector-ref v 0) -2)))
    (vector->list v)))

(display "Echelon form:")
(newline)
(for-each (lambda (row)
  (display "  ") (display row) (newline)) m1)

; Result: ((1 2 1 4) (0 0 1 1))
; z = 1 (from row 2)
; x + 2y + 1 = 4, so x = 3 - 2y
; y is free.
(newline)
(display "z = 1, x = 3 - 2t, y = t  (t is free)")
(newline)
(display "Solution is a line through (3,0,1).")

Notation reference

Symbol	Scheme	Python	Meaning
[A \| b]	'((a11 ... b1) ...)	np.array([[...]])	Augmented matrix
Ri ← Ri + kRj	(row-replace mat i j k)	A[i] += k * A[j]	Row replacement
Ri ← cRi	(scale-pivot mat i c)	A[i] *= c	Row scaling
RREF	pivots = 1, rest = 0	pivots = 1, rest = 0	Reduced row echelon form
free variable	non-pivot column	non-pivot column	Parameter in solution set

Neighbors

Next chapters

Ch.2 Vector Spaces — the algebraic structure behind solution sets
Ch.3 Maps Between Spaces — matrices as linear maps

🔢 Levin Ch.1 Counting — counting the number of solutions to a system

Foundations (Wikipedia)

Translation notes

Hefferon's chapter covers additional topics: describing solution sets geometrically, general = particular + homogeneous decomposition, and a careful treatment of the uniqueness of RREF. The examples here focus on the core algorithm. For full proofs, see the original text.

Full chapter: Hefferon, Chapter One — Linear Systems.

by june.kim Vector Spaces →