Gaussian Elimination

linear-algebra

Definition

Gaussian Elimination

Gaussian elimination is an algorithm used to transform a matrix into its row echelon form (REF) or reduced row echelon form (RREF) using a sequence of elementary row operations. It is primarily used to solve systems of linear equations, determine the rank of a matrix, and compute inverses of matrices.

Elementary Row Operations

Gaussian elimination uses the following elementary row operations:

1. Row Swap: Swap two rows $R_i\leftrightarrow R_j$.
2. Row Scaling: Multiply a row by a non-zero scalar $R_i\leftarrow \lambda R_i$ where $\lambda \ne 0$.
3. Row Addition: Add a multiple of one row to another row $R_i\leftarrow R_i+\lambda R_j$.

These operations are invertible and preserve the solution space of the system or the rank of the matrix.

Row Echelon Form (REF)

Row Echelon Form

A matrix is in row echelon form if:

1. All non-zero rows are above rows of all zeros.
2. The leading entry (pivot) of each non-zero row is to the right of the leading entry of the row above.
3. The entries below each pivot are zero.

Example of REF

$$\left[\begin{array}{ccc}1& 2& 3\\ 0& 1& 4\\ 0& 0& 5\end{array}\right]$$

Reduced Row Echelon Form (RREF)

Reduced Row Echelon Form

A matrix is in reduced row echelon form if it satisfies the conditions of row echelon form (REF) and additionally:

1. The pivot in each row is $1$.
2. Each pivot is the only non-zero entry in its column.

Example of RREF

$$\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& -1\\ 0& 0& 1\end{array}\right]$$

Steps of Gaussian Elimination

1. Select a Pivot: Choose the leftmost non-zero entry as a pivot. If necessary, swap rows to bring a non-zero entry into the pivot position.
2. Create Zeros Below the Pivot: Use row operations to create zeros below the pivot.
3. Move to the Next Row: Repeat the process for the submatrix below the current pivot.
4. Continue Until in Row Echelon Form.

For RREF, additional steps are performed to ensure each pivot is $1$ and the entries above each pivot are zero.

Determining the Rank of a Matrix

Rank

The rank of a matrix $A$ is the number of non-zero rows in its row echelon form (REF) or reduced row echelon form (RREF). It represents the number of linearly independent rows or the dimension of the row space.

Example

Given the matrix:

$$\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 4\\ 3& 4& 5\end{array}\right]$$

1. Step 1: Use $1$ in the first row as the pivot.

2. Step 2: Eliminate entries below:

   • Row 2: $R_2\leftarrow R_2-2R_1$
   • Row 3: $R_3\leftarrow R_3-3R_1$

   New matrix:

$$\left[\begin{array}{ccc}1& 2& 3\\ 0& -1& -2\\ 0& -2& -4\end{array}\right]$$

3. Step 3: Use $-1$ in Row 2 as the next pivot.

4. Step 4: Eliminate entries below:

   • Row 3: $R_3\leftarrow R_3-2R_2$

   Final REF:

$$\left[\begin{array}{ccc}1& 2& 3\\ 0& -1& -2\\ 0& 0& 0\end{array}\right]$$

5. Rank: There are 2 non-zero rows, so $\mathrm{rank}(A)=2$.