Row Echelon Form

General Case

$A x = b, A \in M_{m \times n}, b \in R^{m}$
Any matrix $A$ can be reduced to row echelon form by elementary row operations.
Definition: An $m \times n$ matrix is said to be in the row echelon form if it has a "staircase structure":

U = [\begin{matrix} 0 & x & * & * \\ 0 & 0 & x & * \\ 0 & 0 & 0 & x \end{matrix}]

where $x \neq 0$ are called pivots and $*$ are anything. The row echelon form $U$ of matrix $A$ is not unique, but the number of pivots is unique. This motivates the following definition.

Info

If $A$ is a square nonsingular, then this is a special case of row echelon form: $U = [\begin{matrix} x & * & * \\ 0 & x & * \\ 0 & 0 & x \end{matrix}]$ . If $x = 1$ and all entries above the pivots are 0, it is in reduced echelon form and is unique.

Definition:

The rank of a matrix $A$ is the number of points in $A$ 's echelon form.

Rank is one of the most important numerical quantities associated with a matrix. Since there is at most one pivot per row and one pivot per column, $0 \leq rank A \leq min {m, n}$ . If $A \in M_{n \times n}$ is nonsingular, $rank A = n$ .

In matrix language, the above key fact can be formulated as follows: there exists an $m \times m$ permutation matrix $P$ and an $m \times m$ special lower triangular such that: $P A = L U$ , to solve $A x = b$ , we therefore proceed as follows:

$A x = b ⟺ P A x = P b = \tilde{b} ⟺ L U x = \tilde{b}$ where $U x = y$
Solve $L y = \tilde{b}$ for $y$ using forward substitution.
Now we need to solve $U x = y$ for $x$ .
1. If the last $(m - r)$ entries of $y$ are nonzeros $\Rightarrow$ no solution.
2. Otherwise, we modify the back substitution procedure:
  - Solve for the basic variable (associated with its pivot) $\Rightarrow$ $r$ basic variables will be expressed in terms of $(n - r)$ free variables (correspond to columns without pivots)
  - Substitute the result into the previous equation

Free and Basic Variables:

Let $x = [x_{1}, \dots, x_{r}, x_{r + 1}, x_{n}]$ where $[x_{1}, \dots, x_{r}]$ are basic and $[x_{r + 1}, \dots, x_{n}]$ are free. (Free and basic variables are "mixed" in $x$ , but we use this notation for simplicity).

Then ${\begin{cases} x_{1} = x_{1} (x_{r + 1}, \dots, x_{n}) \\ ⋮ \\ x_{r} = x_{r} (x_{r + 1}, \dots, x_{n}) \end{cases}$ which is the general solution. Free variables can take any values while basic variables are determined by free ones. So, the general solution depends on $(n - r)$ parameters. The following theorem summarizes the above discussion.

Theorem:

A system $A x = b$ of $m$ equations with $n$ unknowns has either:
Inconsistent: 1. No solution $⟺$ $rank [A | b] > rank A$
Consistent: 2. Exactly one solution $⟺ rank [A | b] = rank A$ and $rank A = n$
3. Infinitely many solutions $⟺ rank [A | b] = rank A$ and $rank A < n$

Remark 1: Since $rank A \leq m$ , the system can have only one solution if $n \leq m$ (only "tall" systems can have unique solution; "flat" systems cannot)

Remark 2: Number of solutions is 0, 1, or $\infty$ . Below is a geometric interpretation for systems of $m = 3$ equations with $n = 2$ unknowns:
Pasted image 20231002120529.png