# What are we solving with row reduction?

Why are row reductions so useful in linear algebra? It is easy to get lost in the mechanical solving of equations. I know I can get a matrix into reduced row echelon form. But what are the outcomes of this? What can this mean?

-
You might want to look at the large list of linear algebra texts collected here: mathoverflow.net/questions/16994/linear-algebra-texts, together with the comments about them. –  Dan Ramras Sep 19 '10 at 23:49

The point of row reduction is to transform the system into an equivalent form that makes it simpler to deduce key information. In particular the reduced row echelon form immediately reveals fundamental information such as the column space, spanned by the pivot columns, the rank, the nullspace, etc. Generally such information can not be so simply deduced for a matrix in general form. Here is a worked example from Strang's Linear Algebra, 4ed p. 84:

-

The main point of row operations is that they do not change the solution set of the underlying linear system. So when you take a system of linear equations, write down its (augmented) coefficient matrix, and row reduce that matrix, you get a new system of equations that has the same solutions as the original system.

When the coefficient matrix is in reduced row echelon form, it is particularly easy to understand the solution set of the linear system. In particular, you can readily tell whether the system is consistent or inconsistent, and when the system is consistent, you can readily see how a choice for the values of the free (non-pivotal) variables leads to a solution.

I recommend David Lay's book as a textbook for this material.

One thing that sometimes gets lost in the process of Gaussian elimination (the usual algorithm for putting a matrix into reduced row echelon form) is just how similar this process is to the approach, often taught in high school algebra, of solving for one variable in a particular equation and then eliminating its occurrences from all the other equations. When you produce a pivot in a row of the coefficient matrix, this corresponds to solving the equation for that variable. When you add or subtract (multiples of) this pivotal row from the other rows to produce zeros in the pivotal column, the new rows represent the equations you get by substituting in for the pivotal variable. In a sense, Gaussian elimination is just an excellent way to keep track of the process of solving for variables and then eliminating them from the other equations.

Here's an example. We start with the equations

$3x + 6y + 3z = 3$

$2x + y + 7z = 6$.

The corresponding matrix is

$\left[\begin{array}{rrr|r} 3 & 6 & 3 & 3\\ 2 & 1 & 7 & 6\end{array}\right]$.

Dividing the first row/equation by 2 gives you the equation $x + 2y + z = 1$, which you can think of as $x = 1 - 2y - z$. You can plug that expression into the second equation to get $2(1-2y -z) + y + 7z = 6$, which simpifies to $-3y + 5z = 4$. Notice that when you row reduce by dividing the first row by 2 and then subtracting twice row 1 from row 2, you get the same thing:

$\left[\begin{array}{rrr|r} 3 & 6 & 3 & 3\\ 2 & 1 & 7 & 6\end{array}\right] \to \left[\begin{array}{rrr|r} 1 & 2 & 1 & 1\\ 2 & 1 & 7 & 6 \end{array}\right] \to \left[\begin{array}{rrr|r} 1 & 2 & 3 & 1\\ 0 & -3 & 5 & 4\end{array}\right].$

-
I totally agree with most of this answer except the use of the adjective "lowbrow"; if nothing else, Gaussian elimination is nothing but a tidy, systematic reorganization. –  Ｊ. Ｍ. Sep 20 '10 at 2:00
Fair enough. What I really meant is that in more basic courses (especially in high school algebra) one often sees the elimination method presented for two or three equations, without any mention of matrices. I changed the wording of answer to clarify this. –  Dan Ramras Sep 20 '10 at 3:09

So you have a matrix $A$ and vectors $x,b$, to solve $Ax=b$ you apply row reductions.

So considering a concrete example, if we wanted to solve

$$\left(\begin{array}{cc} 1 & 1 \\ 1 & 2\end{array}\right) x = \left(\begin{array}{c} 5 \\ 8\end{array}\right)$$

We can use the row that changes the bottom row into bottom row minus top:

$$\left(\begin{array}{cc} 1 & 1 \\ 0 & 1\end{array}\right) x = \left(\begin{array}{c} 5 \\ 3\end{array}\right)$$

Which tells us that $x = \left(\begin{array}{c} 2 \\ 3\end{array}\right)$.

The secret is that the second line is actually

$$\left(\begin{array}{cc} 1 & 0 \\ -1 & 1\end{array}\right) \left(\begin{array}{cc} 1 & 1 \\ 1 & 2\end{array}\right) x = \left(\begin{array}{cc} 1 & 0 \\ -1 & 1\end{array}\right) \left(\begin{array}{c} 5 \\ 8\end{array}\right)$$

So a row operation corresponds to multiplying both sides by a matrix - Why is this useful for solving a system? Well it's just the same as when you solve any equation, for example

$$2x+3=7x-4$$

We can add 4 to both sides and then subtract 2x from both to get

$$7=5x$$

That is the meaning of row operations, and why they help to solve a system - it's also interesting to note that if we start out with $AX=I$ and use row operations until it's in the form $IX=B$ then the inverse of $A$ has been found. Viewing the row operations as matrices, lets say it took 3 operations $R_1, R_2, R_3$ then we have $R_3 R_2 R_1 A X = I X = R_3 R_2 R_1 I$ so $A^{-1} = X = R_3 R_2 R_1$.

-

Well, Dan and muad have already told you everything, but let me stress the two main points (in my opinion):

1. Row reduction is just the same as solving one equation for one unkown in terms of the others and then plugging the obtained expression into the remaining equations. (But without having to write down the unkowns all the time.) In a nutshell, row reduction = solving your system.
2. Row reduction doesn't change the solution of the system of linear equations. (So the target in performing row reduction is to obtain a simpler system, with the same solutions as the original one, but such that solutions can be read directly from it.)

The second statement can be proved formally, but I think that, if I can convince you that (1) is true, you won't need this formal proof, will you? (Because, when you solve your system, you're sure that, if you don't make mistakes, the solution you arrive at is, well, the solution. You don't change the solution of a system when you perform your operations in order to solve it, do you? So, if row reduction = solving your system and you don't change the solutions of your system while solving it, then row reduction doesn't change the solutions of your system.)

So let's see how row reduction = solving your system. Say you're trying to solve the following system:

\begin{align} 5x - 3y &= 3 \\ 2x + 4y &= 2 \end{align}

You realize that the second equation looks nicer than the first one, so you decide to start with it and interchange both equations:

\begin{align} 2x + 4y &= 2 \\ 5x - 3y &= 3 \end{align} \qquad \qquad \qquad \qquad \textbf{Step one}

Then you solve the first equation for $x$. You divide by two your, now, first equation

$$x + 2y = 1 \qquad \qquad \qquad \qquad \textbf{Step two}$$

solve it for $x$, $x = 1 -2y$, and plug it into the second one, that is $5(1-2y) - 3y = 3$. You obtain:

$$-13y = -2 \qquad \qquad \qquad \qquad \textbf{Step three}$$

Then, you solve the second equation for $y$, dividing by $-13$

$$y = \frac{2}{13} \qquad \qquad \qquad \qquad \textbf{Step four}$$

and you perform back subtitution, that is you plug this $y$ into the first equation, $x = 1- 2\frac{2}{13}$, getting

$$x = \frac{9}{13} \qquad \qquad \qquad \qquad \textbf{Step five}$$

So you know the solution of your system is:

\begin{align} x &= \frac{9}{13} \\ y &= \frac{2}{13} \end{align}

Now, we are going to do exactly the same, but with row reduction. Our system of equations is the same as its augmented matrix:

$$\left( \begin{array}{rr|r} 5 & -3 & 3 \\ 2 & 4 & 2 \end{array} \right)$$

In Step one, we've interchanged both equations. Now, we interchange the two rows:

$$\left( \begin{array}{rr|r} 2 & 4 & 2 \\ 5 & -3 & 3 \end{array} \right) \qquad \qquad \qquad \qquad \textbf{Step one}$$

In Step two, we divided by two the first equation. Now, we divide by two the first row:

$$\left( \begin{array}{rr|r} 1 & 2 & 1 \\ 5 & -3 & 3 \end{array} \right) \qquad \qquad \qquad \qquad \textbf{Step two}$$

In Step three, we plugged $x = 1 -2y$ into the second equation. Now, we substract five times the first equation from the second:

$$\left( \begin{array}{rr|r} 1 & 2 & 1 \\ 0 & -13 & -2 \end{array} \right) \qquad \qquad \qquad \qquad \textbf{Step three}$$

In Step four, we divided the second equation by $-13$. Now, we divide the second row by $-13$:

$$\left( \begin{array}{rr|r} 1 & 2 & 1 \\ 0 & 1 & \frac{2}{13} \end{array} \right) \qquad \qquad \qquad \qquad \textbf{Step four}$$

In Step five, we performed back substitution. Now, we substract $2$ times the second row from the first one:

$$\left( \begin{array}{rr|r} 1 & 0 & \frac{9}{13} \\ 0 & 1 & \frac{2}{13} \end{array} \right) \qquad \qquad \qquad \qquad \textbf{Step five}$$

Now, the solution of your system is in the third column, because the system that corresponds to this matrix is:

\begin{align} x &= \frac{9}{13} \\ y &= \frac{2}{13} \end{align}

-