Why This Page Matters
Until now, elimination has mostly looked like a procedure for creating zeros and solving equations. On page 149, Strang gives the bigger interpretation: elimination is discovering the structure hidden inside a matrix.
As elimination moves through a matrix, it distinguishes new independent information from redundancy.
1. Elimination Moves Systematically
Elimination starts with the first pivot and moves through the matrix:
\[ \text{columns: left to right} \]and
\[ \text{rows: top to bottom}. \]The important idea is that a pivot is not merely a convenient number used to eliminate entries below it. A pivot indicates that elimination has encountered a new independent direction or constraint that cannot be produced from what came before.
2. Question About Columns
As elimination reaches a column, it is effectively asking:
\[ \boxed{\text{Is this column a combination of previous columns?}} \]If the column receives a pivot, the answer is no. It contributes a new independent column direction.
If it receives no pivot, it is a combination of earlier pivot columns.
For example, if
\[ a_2=2a_1, \]then column 2 adds no new direction. Elimination will not find a new pivot there.
So the mental model is:
\[ \boxed{\text{new independent direction}\Rightarrow\text{new pivot}} \]while
\[ \boxed{\text{combination of earlier columns}\Rightarrow\text{no new pivot}}. \]3. Question About Rows
Elimination simultaneously asks:
\[ \boxed{\text{Is this row a combination of previous rows?}} \]If a row receives a pivot, it contributes a new independent equation or constraint.
If it eventually becomes a zero row, its information was already contained in previous rows.
For example, if
\[ r_2=2r_1, \]then
\[ R_2\leftarrow R_2-2R_1 \]turns row 2 into a zero row.
Thus elimination reveals both column dependence and row dependence in the same process.
4. A to U to R
The first downward elimination pass produces the echelon matrix \(U\):
\[ A\longrightarrow U. \]Reduction then proceeds upward to produce the reduced row echelon matrix:
\[ U\longrightarrow R. \]Strang’s distinction is important:
\[ \boxed{U\text{ tells us which columns are dependent}} \]because missing pivots identify the free columns.
Then
\[ \boxed{R\text{ tells us exactly how those columns are dependent}.} \]For example, if
\[ R= \begin{bmatrix} 1&0&-2\\ 0&1&3\\ 0&0&0 \end{bmatrix}, \]then column 3 is free, and
\[ R_3=-2R_1+3R_2. \]The corresponding columns of the original matrix satisfy the same coefficient relation:
\[ A_3=-2A_1+3A_2. \]Equivalently,
\[ 2A_1-3A_2+A_3=0. \]This relation is encoded by the special nullspace solution
\[ \begin{bmatrix} 2\\ -3\\ 1 \end{bmatrix}. \]5. Why This Matters for Large Matrices
For a small matrix, column relationships can sometimes be spotted by eye. For a large matrix, this is not practical.
Elimination systematically identifies all pivot and free columns. Each free variable produces a special solution, and each special solution records an exact dependency relation among the columns.
So the workflow is:
\[ A \longrightarrow R \longrightarrow \text{free columns} \longrightarrow \text{special solutions} \longrightarrow \text{column dependency relations}. \]6. The Final Reduced Matrix R Is Fixed by A
Different valid sequences of row exchanges and elimination steps can produce different intermediate matrices, but after complete reduction they lead to the same reduced row echelon matrix \(R\).
The nullspace is also fixed by \(A\):
\[ N(A)=N(R). \]Once \(R\) is known, the pivot positions, free variables, and Strang-style special solutions are determined.
This is the sense in which the special solutions are decided by \(A\).
7. Preview of Basis
Strang previews the idea of a basis before formally defining it later.
For now, a useful intuitive meaning is:
\[ \boxed{\text{basis = enough independent vectors to generate the whole space, with no redundancy}.} \]8. Basis for the Column Space
For the column space of \(A\), choose the pivot columns of the original matrix \(A\).
The pivot positions are discovered through elimination, but the actual basis vectors must be taken from the original matrix because row operations change the columns themselves.
\[ \boxed{\text{Basis for }C(A)=\text{pivot columns of original }A.} \]9. Basis for the Row Space
For the row space, choose the nonzero rows of \(R\).
Row operations replace rows with combinations of other rows, so they preserve the row space.
\[ \boxed{\operatorname{Row}(A)=\operatorname{Row}(R)}. \]Therefore:
\[ \boxed{\text{Basis for row space}=\text{nonzero rows of }R.} \]10. Basis for the Nullspace
The special solutions to
\[ Rx=0 \]generate every vector in the nullspace.
If, for example, \(x_3=s\) and \(x_4=t\) are free variables, a nullspace solution may take the form
\[ x=s\,s_1+t\,s_2, \]where \(s_1\) and \(s_2\) are the special solutions obtained by setting one free variable to 1 and the other to 0.
Therefore:
\[ \boxed{\text{Basis for }N(A)=\text{special solutions to }Rx=0.} \]11. Rank Connects All of These Ideas
Strang calls rank the single most important number revealed by elimination.
\[ \boxed{r=\text{number of pivots}.} \]Because every pivot belongs to one pivot row and one pivot column:
\[ \boxed{r=\text{number of pivot rows}=\text{number of pivot columns}.} \]If \(A\) has \(n\) columns, then
\[ \boxed{n-r=\text{number of free columns}.} \]Those free columns correspond to free variables, and each free variable gives one special solution:
\[ \boxed{n-r=\text{number of free variables}=\text{number of special solutions}.} \]12. Augmenting A With the Identity Matrix
Strang ends the page by considering
\[ [A\ I]. \]We perform exactly the same row operation across the entire augmented row. If a row operation changes the left side, it must change the identity matrix on the right in the same way.
For example, let
\[ A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}, \qquad I= \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}. \]Start with
\[ \left[ \begin{array}{cc|cc} 1&2&1&0\\ 3&4&0&1 \end{array} \right]. \]Apply
\[ R_2\leftarrow R_2-3R_1. \]The operation acts on the whole row:
\[ \left[ \begin{array}{cc|cc} 1&2&1&0\\ 3&4&0&1 \end{array} \right] \longrightarrow \left[ \begin{array}{cc|cc} 1&2&1&0\\ 0&-2&-3&1 \end{array} \right]. \]On the left, the operation is reducing \(A\). On the right, the same operation is being recorded by transforming \(I\).
If all row operations together are represented by \(E\), then
\[ \boxed{EA=R}. \]That is why complete reduction has the form
\[ \boxed{[A\ I]\longrightarrow[R\ E]}. \]The matrix \(E\) records the accumulated elimination operations.
13. The Invertible Case
If \(A\) is square and invertible, its reduced row echelon form is
\[ R=I. \]Then
\[ EA=I. \]Therefore
\[ \boxed{E=A^{-1}}. \]So the familiar Gauss-Jordan inverse procedure
\[ [A\ I]\longrightarrow[I\ A^{-1}] \]has a deeper interpretation: the inverse matrix is the accumulated record of the row operations that reduce \(A\) to the identity.
The Big Picture
\[ \boxed{ \text{Elimination} \longrightarrow \text{pivots} \longrightarrow \text{rank} \longrightarrow \text{independence and dependence} \longrightarrow \text{column space, row space, nullspace} } \]Elimination is therefore not merely a technique for solving equations. It exposes the structural organization of a matrix.
Note metadata
- Note type: learning-note
- Subject: learning-notes
- Source: Introduction to Linear Algebra, 5th Edition — Section 3.2, Elimination: The Big Picture