The Unapologetic Mathematician

Mathematics for the interested outsider

Solving Equations with Gaussian Elimination

The row echelon form of a matrix isn’t unique, but it’s still useful for solving systems of linear equations. If we have a system written in matrix form as

\displaystyle Ax=y

then applying elementary row operations builds up a new matrix that we multiply on the left of both sides

\displaystyle EAx=Ey

If the new matrix EA is in row echelon form, the resulting system of equations will be simple to solve.

A little more explicitly, this works because each of the equations is linear, and so each of the elementary row operations corresponds to some manipulation of the equations which gives rise to an equivalent system. for example, the order of the equations doesn’t matter, so swapping two of them (swapping two rows) doesn’t change the solution. Similarly, multiplying both sides of one equation by a nonzero number doesn’t change the solution to that equation, and so doesn’t change the solution of the system. Finally, adding two equations gives another valid equation. Since the three equations “overdetermine” the solution (they’re linearly dependent), we can drop one of the first two. The result is the same as a shear.

Since we’re just doing the same thing to the rows of the column vector y as we are to the matrix A, we may as well stack them beside each other. In this way, we get the “augmented matrix” of the system of equations. For example, we might have the system

\displaystyle\begin{aligned}2x+y-z&=8\\-3x-y+2z&=-11\\-2x+y+2z&=-3\end{aligned}

with the augmented matrix

\displaystyle\begin{pmatrix}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{pmatrix}

Then we can follow along our elimination from yesterday, applying the same steps to the system of equations. Foe example, if at this point we add the first and third equations we get 2y+z=5, “eliminating” the variable x from the equation. We replace the third equation with this new, simpler equation, giving the effect of a shear just like we did yesterday.

At the end, we found the row echelon form

\displaystyle\begin{pmatrix}2&1&-1&8\\{0}&\frac{1}{2}&\frac{1}{2}&1\\{0}&0&-1&1\end{pmatrix}

which corresponds with the system

\displaystyle\begin{aligned}2x+y-z&=8\\\frac{1}{2}y+\frac{1}{2}z&=1\\-z&=1\end{aligned}

Now the equations are arranged like a ladder for us to climb up. First, we solve the bottom equation to find z=-1. Then we can plug this into the next equation up to find \frac{1}{2}y-\frac{1}{2}=1, which is easily solved to find y=3. Then we plug both of these answers into the next equation up to find 2x+3+1=8, which is easily solved to find x=2, and we’re done. In fact, this is why we use the word “echelon” — French for a rung of a ladder — to describe this form.

What about our other example from yesterday? This corresponds to a system of four equations with three unknowns, since we’re interpreting the last column as the column vector on the right side of the equation. The system is

\displaystyle\begin{aligned}2x+y-z&=8\\-4x-2y+2z&=-11\\4x+4y-3z=6\\-2x-3y+2z&=-3\end{aligned}

We convert this to an augmented matrix, put this matrix into row echelon form, and return it to the form of a system of equations to find

\displaystyle\begin{aligned}2x+y-z&=8\\2y-z&=-10\\{0}&=5\\{0}&=0\end{aligned}

The empty row on the bottom is fine, since it just tells us the tautology that 0=0. Unfortunately, the line above that contains the contradiction that 0=5. That is, whenever the row echelon form of a system of equations has a leading coefficient in the last column, that system is unsolvable. We don’t even need to climb the ladder to know that.

On the other hand, if we started with the system

\displaystyle\begin{aligned}2x+y-z&=8\\-4x-2y+2z&=-16\\4x+4y-3z=6\\-2x-3y+2z&=2\end{aligned}

and put it in row echelon form (do it yourself) we get

\displaystyle\begin{aligned}2x+y-z&=8\\2y-z&=-10\\{0}&=0\\{0}&=0\end{aligned}

Now we have no contradictions, but the system is underdetermined. Indeed, the rank is {2}, so the kernel has dimension {1}, and thus we’ll have one free parameter in our solution. It’s still easy to solve, though. We first find that y=\frac{1}{2}z-5. Plugging this into the first equation we find 2x-\frac{1}{2}z-5=8, which is easily solved to find x=\frac{1}{4}z-\frac{13}{2}.

So whether the system is exactly solvable, underdetermined, or contradictory, we can find whatever solutions may exist explicitly using a row echelon form.

September 2, 2009 Posted by | Algebra, Linear Algebra | 9 Comments

   

Follow

Get every new post delivered to your Inbox.

Join 393 other followers