Matrix Elimination

From bio-physics-wiki

Jump to: navigation, search

Elimination is a method to solve linear systems of equations. In fact, it is one of the most basic algorithms to solve these equations and also software like Matlab uses it to solve these problems, since it's efficient. The basic idea of the method is to do row operations, so we will multiply rows by scalars and add or subtract them from each other. Let us solve the system of equations

\begin{align} x + 2y + z&=2\\ 3x + 8y + z&=12\\ 4y + z&=2\\ \end{align}

by elimination. It is much less tedious to just work with the matrix $\mathbf{A}$ than to carry all the $x,y,z$'s with you all the time. We can even leave the brackets away. So we work with the matrix \begin{align} \begin{array}{rrr|r} \color{red}{1} & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{array} \end{align}
Additionally we have to augment the vector $\mathbf{b}$ to the matrix. \begin{align} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 3 & 8 & 1 & 12\\ 0 & 4 & 1&2 \end{array} \end{align}
Step one
The first number in red is called a pivot. Our intermediate goal is to clean out all numbers below the pivot, by row operations. If we multiply the first row by $3$ and subtract it from row two we get. \begin{align} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 3 & 8 & 1 & 12\\ 0 & 4 & 1&2 \end{array} \overset{row2-3 \cdot row1}{\longrightarrow} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 0 & \color{red}{2} & -2 & 6\\ 0 & 4 & 1&2 \end{array} \end{align} The next step would be to do a row operation to make the row three, column one $31$ position zero, but it already is, so we move on to the next pivot.


Step two

We multiply by two and subtract from the third row, to get \begin{align} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 0 & \color{red}{2} & -2 & 6\\ 0 & 4 & 1&2 \end{array} \overset{row3-2 \cdot row2}{\longrightarrow} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 0 & \color{red}{2} & -2 & 6\\ 0 & 0 & \color{red}{5} & -10 \end{array} \end{align}

Now we have three pivots $1,2,5$ with all zeros below them. If we insert $x,y,z$ again we have the equations \begin{align} x + 2y + z=2\\ 2y + -2z=6\\ 5z=-10\\ \end{align} We can readily find the solution by back substitution $z=-2$, $y=1$, $x=2$.







Video Lectures:

  • Gilbert Strang - Introduction to Linear Algebra Lec. 2