Matrix is Row Equivalent to Reduced Echelon Matrix

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbf A = \sqbrk a_{m n}$ be a matrix of order $m \times n$ over a field $F$.


Then $A$ is row equivalent to a reduced echelon matrix of order $m \times n$.


Proof

Let the first column of $\mathbf A$ containing a non-zero element be column $j$.

Let such a non-zero element be in row $i$.

Take element $a_{i j} \ne 0$ and perform the elementary row operations:

$(1): \quad r_i \to \dfrac {r_i} {a_{i j}}$
$(2): \quad r_1 \leftrightarrow r_i$

This gives a matrix with $1$ in the $\tuple {1, j}$ position:

$\begin {bmatrix}
    0 & \cdots &      0 &       1 & b_{1, j + 1} & \cdots & b_{1 n} \\
    0 & \cdots &      0 & b_{2 j} & b_{2, j + 1} & \cdots & b_{2 n} \\

\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 

    0 & \cdots &      0 & b_{m j} & b_{m, j + 1} & \cdots & b_{m n} \\

\end {bmatrix}$

Now the elementary row operations $r_k \to r_k - b_{k j} r_1, k \in \set {2, 3, \ldots, m}$ gives the matrix:

$\begin{bmatrix}

0 & \cdots & 0 & 1 & c_{1, j + 1} & \cdots & c_{1 n} \\ 0 & \cdots & 0 & 0 & c_{2, j + 1} & \cdots & c_{2 n} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & 0 & c_{m, j + 1} & \cdots & c_{m n} \\ \end{bmatrix}$

If some zero rows have appeared, do some further elementary row operations, that is row interchanges, to put them at the bottom.


We now repeat the process with the remaining however-many-there-are rows:

$\begin{bmatrix}

\cdots & 0 & 1 & d_{1, j + 1} & \cdots & d_{1, k - 1} & d_{1 k} & d_{1, k + 1} & \cdots & d_{1 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & d_{2, k + 1} & \cdots & d_{2 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{3 k} & d_{3, k + 1} & \cdots & d_{3 n} \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{n k} & d_{m, k + 1} & \cdots & d_{m n} \\ \end{bmatrix}$


Then we can get the reduced echelon form by:

$r_i \to r_i - d_{i k} r_2, i \in \set {1, 3, 4, \ldots, m}$

as follows:

$\begin{bmatrix}

\cdots & 0 & 1 & {e_{1, j + 1 } } & \cdots & {e_{1, k - 1} } & 0 & {e_{1, k + 1} } & \cdots & {e_{1 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & {e_{2, k + 1} } & \cdots & {e_{2 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{3, k + 1} } & \cdots & {e_{3 n} } \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{m, k + 1} } & \cdots & {e_{m n} } \\ \end{bmatrix}$

Thus we progress, until the entire matrix is in reduced echelon form.

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Matrix_is_Row_Equivalent_to_Reduced_Echelon_Matrix&oldid=626476"