Solving Linear Systems

Basic Definitions

(Pivot) The pivot of a row in a matrix is the leftmost nonzero entry in that row.

(Row Echelon Form) A matrix is in row echelon form (REF) if and only if:

  1. All rows consisting entirely of zeros are at the bottom of the matrix, and
  2. The pivot of each nonzero row is in a column strictly to the right of the pivot of the row above it.

(Reduced Row Echelon Form) A matrix is in reduced row echelon form if and only if

  1. The matrix is in Row Echelon Form
  2. The pivot in each nonzero row is d
  3. Each pivot is the only nonzero column in its column

(Consistency) A system of linear equations is consistent if it has at least one solution. Otherwise it is inconsistent

(Basic Variable): We say that xix_i is a basic variable if the ithi^{th} column of rref(C) has a pivot.

(Free Variable): We say that xix_i is a basic variable if the ithi^{th} column of rref(C) has NO pivot.

Rouché–Capelli Theorem

Let AA be the augmented matrix and CC the coefficient matrix.

Inconsistent System

A system is inconsistent iff the last column of rref⁡(A)\operatorname{rref}(A) has a pivot.

Unique Solution

A system has exactly one solution iff:

  • the last column of rref⁡(A)\operatorname{rref}(A) has no pivot
  • every column of rref⁡(C)\operatorname{rref}(C) does have a pivot

In other words:

rank⁡(rref⁡(A))=rank⁡(rref⁡(C))=number of variables\operatorname{rank}(\operatorname{rref}(A)) = \operatorname{rank}(\operatorname{rref}(C)) = \text{number of variables}

Infinitely Many Solutions

A system has infinitely many solutions iff:

  • the last column of rref⁡(A)\operatorname{rref}(A) has no pivot
  • rref⁡(C)\operatorname{rref}(C) has at least one column without a pivot

In other words:

rank⁡(rref⁡(A))=rank⁡(rref⁡(C))≠number of variables\operatorname{rank}(\operatorname{rref}(A)) = \operatorname{rank}(\operatorname{rref}(C)) \neq \text{number of variables}

Specifically, the dimension of the solution set (set of possible input vectors x to produce Ax = b) is:

dim⁡(solution set)=number of variables−rank⁡(rref⁡(C))\dim(\text{solution set}) = \text{number of variables} - \operatorname{rank}(\operatorname{rref}(C))