> [!Proposition] Theorem (Existence of RREF) > Every [[Real Matrices|real matrix]] can be *reduced* by [[Elementary Row Operations|elementary row operations]] to a matrix in [[Reduced Row Echelon Form for Real Matrix|reduced row echelon form]]. *Proof*. Let $A\in \text{Mat}_{mn}$. We will proceed by induction on the number of rows, $m$. Suppose $m=1$. A $1\times n$ matrix is either zero, or can be put into reduced row echelon form by dividing through by the leading entry. Now suppose that the inductive hypothesis holds for any matrix with fewer than $m$ rows. If $A=0_{mn}$ then it is already in reduced row echelon form. So suppose $A$ is non-zero. Let $\underline{c}_{j}$ be the first column in $A$ containing a non-zero entry $\alpha.$ Using elementary row operations we can swap the row containing $\alpha$ with the first row and then divide the first row by $\alpha \neq 0$. Thus the $(1,j)$th entry now equals $1$. Applying the row operations $A_{12}(\bar{a}_{2j}),A_{13}(\bar{a}_{3j}),\dots,A_{1m}(\bar{a}_{mj})$ transforms column $\underline{c}_{j}$ to $\underline{e}_{1}^{T}.$ >By induction the $(m-1)\times(n-j)$ matrix given by $B=(a_{st})_{2\leq s \leq m,\; j+1 \leq t\leq n}$ can be placed in RREF can be placed in reduced row echelon form by applying elementary row operations. We can apply those same elementary operations to $A$ which reduces it to: $\begin{pmatrix}0&\cdots&0&1&\overline{a}_{1(j+1)}&\cdots&\overline{a}_{1n}\\0&\cdots&0&0&&\\\vdots&&\vdots&\vdots&&\text{RREF}(B)\\0&\cdots&0&0&&\end{pmatrix}$ To zero-out any of the $\bar{a}_{1(j+1)}, . . . , \bar{a}_{1n}$ which are above a pivot in $\text{RREF}(B)$, if $\bar{a}_{1k}$ is the first entry to lie above a pivot in row $l$ then $A_{l1}(-\bar{a}_{1k})$ will transform the $(1,k)$th entry to $0.$ Thus we can place $A$ in RREF via elementary row operations. This process of applying elementary row operations to transform a matrix into reduced row echelon form is called r*ow reduction (or just reduction) or Gauss elimination or Gauss-Jordan elimination.* # Applications See [[Row Reduction Algorithm]]. **Examples**: >[!Example] >Determines the solutions (if any) to the following equations: $3x+y-2z=-2 \quad x+y+z=2 \quad 2x+4y+z=0.$ > >**Solution** >The linear system corresponds to the augmented matrix: $ \left(\begin{array}{ccc|c}3 & 1 & -2 & -2 \\1 & 1 & 1 & 2 \\2 & 4 & 1 & 0\end{array}\right)$ >Carrying out row reduction gives: $ \begin{aligned} & \left(\begin{array}{ccc|c} 3 & 1 & -2 & -2 \\ 1 & 1 & 1 & 2 \\ 2 & 4 & 1 & 0 \end{array}\right) \quad \stackrel{S_{12}}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 3 & 1 & -2 & -2 \\ 2 & 4 & 1 & 0 \end{array}\right) \stackrel{A_{12}(-3)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & -2 & -5 & -8 \\ 2 & 4 & 1 & 0 \end{array}\right) \\ & \stackrel{A_{13}(-2)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & -2 & -5 & -8 \\ 0 & 2 & -1 & -4 \end{array}\right) \stackrel{A_{23}(1)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & -2 & -5 & -8 \\ 0 & 0 & -6 & -12 \end{array}\right) \stackrel{M_2(-1 / 2)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 1 & \frac{5}{2} & 4 \\ 0 & 0 & -6 & -12 \end{array}\right) \\ & \stackrel{A_{21}(-1)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 0 & -\frac{3}{2} & -2 \\ 0 & 1 & \frac{5}{2} & 4 \\ 0 & 0 & -6 & -12 \end{array}\right) \stackrel{M_3(-1 / 6)}{\longrightarrow}\left(\begin{array}{ccc|c} 1 & 0 & -\frac{3}{2} & -2 \\ 0 & 1 & \frac{5}{2} & 4 \\ 0 & 0 & 1 & 2 \end{array}\right) \stackrel{A_{31}(3 / 2)}{\longrightarrow}\left(\begin{array}{lll|l} 1 & 0 & 0 & 1 \\ 0 & 1 & \frac{5}{2} & 4 \\ 0 & 0 & 1 & 2 \end{array}\right) \\ & \stackrel{A_{32}(-5 / 2)}{\longrightarrow}\left(\begin{array}{lll|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 2 \end{array}\right) \\ & \end{aligned} $ We see that: $(x,y,z)=(1,-1,2)$.