1.2 Gaussian Elimination

<< 1.1 Introduction to Systems of Linear Equations | 1.3 Matrices and Matrix Operations >>

Definition: Row echelon form (REF)

Row echelon form is defined as the augmented matrix of a linear system with the following properties:

1. If a row does not consist entirely of zeros, then the first nonzero number in the row is a 1. We call this a leading 1.
2. If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
3. In any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row.

Link to original

Definition: Reduced row echelon form (RREF)

Reduced row echelon form is defined as a row echelon form with the following additional property:

• Each column that contains a leading 1 has zeros everywhere else in that column.

Link to original

Remark: Facts about echelon forms

1. Every matrix has unique RREF
2. REF are not unique
3. RREF, and all REF have the same number of zero rows, and the leading 1’s always occur in the same positions. These positions are called the pivot positions. A column that contains a pivot position is called a pivot column.

For example, consider the following augmented matrix:

$$\left[\begin{array}{cccccc}1& 2& -5& 3& 6& 14\\ 0& 0& 1& 0& -\frac{7}{2}& -6\\ 0& 0& 0& 0& 1& 2\end{array}\right]$$

The leading 1’s always occur in positions (row, column): (1,1), (2,3), and (3, 5). These are the pivot positions. The pivot columns are columns 1, 3, and 5.

Definition: General solution

Definition

Let $\mathbf{Ax}=\mathbf{b}$ : Linear system that has infinitely many solutions.

Then general solution of $\mathbf{Ax}=\mathbf{b}$ is set of parametric equations from which all solutions can be obtained.

Link to original

Definition: Gauss-Jordan elimination

Gauss-Jordan elimination is the procedure of using elementary row operation to transform an augmented matrix to reduced row echelon form.

This procedure consists of:

1. Forward phase: Zeros are introduced below the leading 1’s
2. Backward phase: Zeros are introduced above the leading 1’s

Link to original

Definition: Gaussian elimination

Gaussian elimination is the procedure of using elementary row operation to transform an augmented matrix to row echelon form.

This procedure consists of:

1. Forward phase: Zeros are introduced below the leading 1’s
2. Back-substitution: Starting from the last equation, solve for variables by substituting known values into previous equations

Link to original

Definition: Homogeneous linear system

Homogeneous linear system is defined as a linear system with $b_i=0$, for all $i=1,\dots ,n$.

It is written as

a_{11}x_{1} & + & a_{12}x_{2} & + & \dots & + & a_{1n}x_{n} & = & 0 \\ a_{21}x_{1} & + & a_{22}x_{2} & + & \dots & + & a_{2n}x_{n} & = & 0 \\ \vdots & & \vdots & && & \vdots & & \vdots \\ a_{m1}x_{1} & + & a_{m2}x_{2} & + & \dots & + & a_{mn}x_{n} & = & 0 \\ \end{matrix} $$ ## Related theorems - [[3 Reference/1.2 Gaussian Elimination#theorem-solution-of-homogeneous-linear-system|Theorem Solution of homogeneous linear system]] - [[3 Reference/1.2 Gaussian Elimination#theorem-121-free-variable-for-homogeneous-system|Theorem 1.2.1 Free variable for homogeneous system]] - [[3 Reference/1.2 Gaussian Elimination#theorem-122|Theorem 1.2.2]]Link to original

Definition: Trivial solution

Trivial solution is defined as solution of a homogeneous linear system with all that is all $0$. Other solutions are called nontrivial solution.

Link to original

Theorem: Solution of homogeneous linear system

Every homogeneous linear system has a trivial solution, and thus consistent. As a corollary of that, there are only two possibilities for its solutions:

1. The system has only the trivial solution
2. The system has infinitely many solutions, in addition to the trivial solution

Theorem 1.2.1: Free variable for homogeneous system

Let $\mathbf{Ax}=\mathbf{b}$ : Homogeneous linear system with $n$ unknowns

If the reduced row echelon form of $\mathbf{Ax}=\mathbf{b}$ has $r$ nonzero rows

Then $\mathbf{Ax}=\mathbf{b}$ has $n-r$ free variables

Recall the properties of RREF. As a result,

• Each of $r$ nonzero row hold 1 leading 1
• Each leading 1 take up 1 column

Thus, any remaining “free” columns, which is $n$ columns taken up by $r$ leading 1’s are free variables.

Theorem 1.2.2

A homogeneous linear system with more unknowns than equations has infinitely many solutions.

Consider a matrix with $m$ equations (row) in $n$ unknowns (column), and $m<n$. Because there are more columns than nonzero rows, there are simply not enough nonzero rows to “take up” the columns. Therefore, there are always at least $n-m$ free variables remaining.

More formally,

Proof

Consider $\mathbf{Ax}=0$ with $m$ equations and $n$ unknowns, where $n>m$.

In RREF, the number of nonzero rows $r\le m$ (can’t exceed the number of equations).

By Theorem 1.2.1, there are $n-r$ free variables. Since $n>m\ge r$, we have $n-r\ge n-m>0$

Therefore, there is at least one free variable, giving infinitely many solutions