[Personal Notes] Introduction to Linear Algebra by Gilbert Strang — 2.2

The Idea of Elimination

“Elimination” method solves linear equations by eliminating one or more variables. Elimination yields an upper triangular system, which can be solved through back substitution. The solution we get after elimination is equal to the solution we get before.

To eliminate, we multiplied the first equation by the multiplier ℓ. And the pivot is the first nonzero in the row that does the elimination. As you can see, multiplier equals entry to eliminate divided by pivot.

To solve n equations, we need n pivots. And by the end of elimination, we want the pivots to be the diagonal of the triangular system.

Breakdown of Elimination

If we do not get n pivots, elimination results in an equation that has no solution or many solutions. We can easily visualize these situations in the column pictures.

As can be seen, pivots cannot be 0. But sometimes, we can fix the problem through a row exchange, and get full n pivots.

With a full set of pivots, there is exactly one solution — non-singular. Without, there is no solution or infinitely many solutions — singular.

Three Equations in Three Unknowns

After doing elimination on the second row, we repeat the same process with the third row using the same pivot. By the end of Gaussian elimination, we convert the original Ax = b into an upper triangular Ux = c that can be solved through back substitution.

The rule extends nicely to 4 by 4 problem or an n by n problem.