Ordinary Row Reductions

Why

When does the technique of row reductions prevail?

Multivariable row reductions

Let $S = (A \in \R ^{m \times m}, b \in \R ^{m})$ be a linear system with $A_{kk} \neq 0$. The $k$th row reduction of $S$ is the linear system $(C, d)$ with $C_{st} = A_{st} - (A_{sk}/A_{kk})A_{kt}$ if $i < s \leq m$ and $C_{st} = A_{st}$ otherwise.

The idea, as in the example in Linear System Row Reductions, is to eliminate variable $k$ from equations $k+1, \dots , m$. We are taking the $k$th column of $A$ from

\[ \barray{A_{1k} \\ \vdots \\ A_{kk} \\ A_{k+1,k} \\ \vdots \\ A_{mk}} \quad \text{to} \quad \barray{A_{1k} \\ \vdots \\ A_{kk} \\ 0 \\ \vdots \\ 0}. \]

We interpret the $i$th row reduction as subtracting equations of the system or reducing rows of the array $A$. If $a^i, c^i \in \R ^{n}$ denote the $i$th rows of $A$ and $C$, $c^i = a^i - (A_{ik}/A_{kk})a^k$ for $k < i \leq m$, In other words, we obtain the $i$th row of matrix $C$ by subtracting a multiple of the $k$th row of matrix $A$ from the $i$th row of matrix $A$, for $k < i \leq m$. The following is an immediate consequence of real arithmetic.

Let $(A \in \R ^{m \times n}, b \in \R ^{n})$ be a linear system which row reduces to $(C, d)$. Then $x \in \R ^{n}$ is a solution of $(A, b)$ if and only if it is a solution of $(C, d)$.

Ordinary reductions

We call the system $S$ ordinarily reducible if there exists a sequence of systems $S_1, \dots , S_{m-1}$ so that $S_1$ is the $11$-reduction of $S$ and $S_{i}$ is the $ii$-reduction of $S_{i-1}$ for $i = 1, \dots , n-1$. In this case, we call $S_{n-1}$ the final ordinary reduction (or just ordinary reduction) of $S$. The following is an immediate consequence of Proposition~\ref{proposition:ordinaryrowreductions:basic}.

Let $S'$ be the (final) ordinary reduction of $S$. Then $S$ and $S'$ have equivalent solution sets.

This process of constructing the ordinary reduction is called Gauss elimination or Gaussian elimination. We call the $kk$th entry of system $S_{k-1}$ the pivot. In an ordinarily reducible system, the pivots are nonzero.

The idea is that a system is ordinarily reducible if we can take row reductions in sequence and end up with a system that is easy to back-substitute and solve. The difficulty is that this need not be the case. For example, consider the following obvious difficulty. The system $(A, b)$ in which

\[ A = \barray{0 & 1\\1 & 2} \text{ and } \barray{1 \\ 2} \]

is not ordinarily reducible, but clearly solvable.