What Row Reduction Must Preserve
Row reduction changes the entries of a matrix, and usually changes its columns. Yet it is a valid way to test whether the columns are linearly independent. The reason is not that the original columns stay fixed: it is that row operations preserve the solutions of the homogeneous system \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Those solutions record exactly the linear combinations of the columns that equal the zero vector.
Throughout, matrices and vectors have real entries. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). For \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\), the equation \(\mathbf{A}\mathbf{x}=\mathbf{0}\) means \(\,x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\). A solution is a vector \(\mathbf{x}\) satisfying that equation. The solution set consists of all such vectors.
Each row of \(\mathbf{A}\) represents one scalar equation in the unknowns \(x_1,\dots,x_n\). Thus, a homogeneous system is a collection of equations that must all hold at once. To show that a row operation preserves solutions, we must establish both directions: every solution before the operation still solves the new system, and every solution of the new system also solves the old one.
Why Each Elementary Operation Preserves Solutions
Proof. Write the equation represented by row \(i\) of \(\mathbf{A}\) as \(L_i(\mathbf{x})=0\), where \(L_i(\mathbf{x})\) is the sum of the entries in that row multiplied by the corresponding entries of \(\mathbf{x}\). The full system holds exactly when all its row equations hold. We check the three operations.
If two rows are interchanged, the same equations are required, only in a different order. Therefore the set of vectors satisfying all equations is unchanged.
If row \(i\) is multiplied by a nonzero scalar \(c\), its equation changes from \(L_i(\mathbf{x})=0\) to \(cL_i(\mathbf{x})=0\). If \(L_i(\mathbf{x})=0\), then \(cL_i(\mathbf{x})=0\). Conversely, if \(cL_i(\mathbf{x})=0\), division by \(c\ne0\) gives \(L_i(\mathbf{x})=0\). All other row equations are unchanged, so the complete solution set is unchanged.
If row \(i\) is replaced by row \(i\) plus \(c\) times a different row \(j\), its new equation is \(L_i(\mathbf{x})+cL_j(\mathbf{x})=0\), while the equation \(L_j(\mathbf{x})=0\) is still present. If the original equations hold, then \(L_i(\mathbf{x})+cL_j(\mathbf{x})=0+c\cdot0=0\), so the new system holds. Conversely, if the new system holds, then \(L_j(\mathbf{x})=0\) and \(L_i(\mathbf{x})+cL_j(\mathbf{x})=0\), so \(L_i(\mathbf{x})=0\). Thus the original equations hold too. In every case the systems have exactly the same solutions. \(\square\)
A sequence of row operations preserves the solution set as well. After the first operation, the solution set is unchanged; applying the same result to the second operation leaves it unchanged again. Repeating this reasoning for every operation proves the claim for any finite sequence. In particular, if \(\mathbf{R}\) is obtained from \(\mathbf{A}\) by row reduction, then \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{R}\mathbf{x}=\mathbf{0}\) have the same solutions.
Connecting Homogeneous Solutions to Independence
Proof. By the definition of linear independence, the columns are independent exactly when the equation \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\) forces every coefficient \(x_i\) to equal zero. By the definition of matrix multiplication, the left side is \(\mathbf{A}\mathbf{x}\). Therefore this condition says exactly that \(\mathbf{A}\mathbf{x}=\mathbf{0}\) has only the solution \(\mathbf{x}=\mathbf{0}\). By the previous theorem, one elementary row operation leaves the solution set unchanged. It therefore leaves unchanged whether that set consists only of \(\mathbf{0}\), proving that it preserves column independence. \(\square\)
The same conclusion applies after any finite sequence of row operations. This justifies using row reduction to test independence: if the reduced system has a nonzero solution, then the original system has that same solution and the columns are dependent; if the reduced system has only the zero solution, so does the original system and the columns are independent.
Worked Systems: Tracking the Same Unknowns
Worked Example: Independent Columns After Row Reduction
Determine whether the columns of the following matrix are linearly independent by reducing it and examining the homogeneous system.
First replace \(R_2\) by \(R_2-2R_1\), then replace \(R_1\) by \(R_1-2R_3\), and finally interchange \(R_2\) and \(R_3\):
The reduced homogeneous system gives \(x_1=0\) and \(x_2=0\), so it has only the zero solution. By the two theorems, the original system has the same solutions, and the columns of \(\mathbf{A}\) are independent.
Check: The original system is \(x_1+2x_2=0\), \(2x_1+4x_2=0\), and \(x_2=0\). The last equation gives \(x_2=0\), and the first then gives \(x_1=0\), confirming that the original system has only the zero solution.
Worked Example: A Nonzero Solution Reveals Dependence
Use row reduction to determine whether the columns of \(\mathbf{B}=\begin{bmatrix}1&2&3\\2&4&6\end{bmatrix}\) are linearly independent. If they are dependent, find a nonzero solution of the homogeneous system.
Replace \(R_2\) by \(R_2-2R_1\):
The reduced system is \(x_1+2x_2+3x_3=0\). Choose \(x_2=1\) and \(x_3=0\); then \(x_1=-2\), giving the nonzero solution \(\mathbf{x}=(-2,1,0)^{\top}\). The reduced system has a nonzero solution, so the original system has the same nonzero solution. Thus the columns are dependent.
Check: Substitution into the original system gives \(\mathbf{B}\mathbf{x}=(1(-2)+2(1)+3(0),\,2(-2)+4(1)+6(0))^{\top}=(0,0)^{\top}\). Equivalently, \(-2\mathbf{b}_1+\mathbf{b}_2=\mathbf{0}\), where \(\mathbf{b}_1,\mathbf{b}_2\) are the first two columns.
Worked Example: Swapping, Scaling, and Adding Rows
Consider \(\mathbf{C}=\begin{bmatrix}0&1\\2&3\end{bmatrix}\). Reduce it using a row swap, a nonzero row scaling, and a row replacement. This illustrates that each operation preserves the solutions, even when several different kinds are used in succession.
Swap the two rows. Then multiply the first row by \(\tfrac12\). Finally replace the first row by itself minus \(\tfrac32\) times the second row:
The final system is \(x_1=0\), \(x_2=0\), so it has only the zero solution. The original equations are \(x_2=0\) and \(2x_1+3x_2=0\). Substituting \(x_2=0\) into the second equation gives \(2x_1=0\), hence \(x_1=0\). This directly checks that the original system also has only the zero solution, and therefore that the columns of \(\mathbf{C}\) are independent.
Check: Multiplying the original matrix by the only solution gives \(\mathbf{C}\begin{bmatrix}0\\0\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). The direct solution of the original equations confirms there are no other solutions.
What Changes and What Does Not
The row-reduced matrix need not have the same columns as the original matrix. For example, replacing \(R_1\) by \(R_1+R_2\) changes \(\begin{bmatrix}1&0\\0&1\end{bmatrix}\) to \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\). The columns have changed from \((1,0)^{\top},(0,1)^{\top}\) to \((1,0)^{\top},(1,1)^{\top}\). What remains the same is the set of coefficient vectors \(\mathbf{x}\) solving the homogeneous system: before the operation the equations are \(x_1=0\), \(x_2=0\); afterwards they are \(x_1+x_2=0\), \(x_2=0\). Both force \(x_1=x_2=0\).
This distinction explains why it is valid to use row reduction for independence, but not to treat the transformed columns as if they were the original columns. The coefficients in \(\mathbf{x}\) refer to positions in the list of columns; row operations preserve which coefficient vectors give a zero combination. They do not leave each column vector unchanged.
Common Mistake: Treating Row-Reduced Columns as the Original Ones
A tempting but incorrect argument is: “The row-reduced matrix has new columns, so it cannot tell us whether the original columns were independent.” The conclusion does not follow. In the example above, the original matrix has the independent columns \((1,0)^{\top}\) and \((0,1)^{\top}\). After the row operation, the columns are \((1,0)^{\top}\) and \((1,1)^{\top}\), which are different vectors. But the homogeneous systems have the same solutions, so both column lists are independent.
Here is the concrete calculation. A mistaken comparison might say that the second column changed from \((0,1)^{\top}\) to \((1,1)^{\top}\), so independence could have changed. The correct comparison tests coefficient vectors: the original equation is \(\begin{bmatrix}1&0\\0&1\end{bmatrix}\mathbf{x}=\mathbf{0}\), while the transformed equation is \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\mathbf{x}=\mathbf{0}\). The first gives \(x_1=0\), \(x_2=0\); the second gives \(x_2=0\), then \(x_1+x_2=0\), hence \(x_1=0\). The solution set, and therefore the independence conclusion, is the same.
The practical principle is precise: row-reduce the matrix whose columns are the vectors, then use the homogeneous system of the reduced matrix to decide whether only the zero coefficient vector works. That conclusion applies to the original columns because the row operations preserve the full solution set—not because they preserve the original columns.
Check Your Understanding
For each question, justify your conclusion using the connection between row operations and homogeneous solutions.
- Why must the scalar used to multiply a row be nonzero for that operation to preserve the solution set?
- Suppose one row is replaced by itself plus \(4\) times another row. Explain how the unchanged second equation lets you recover the original first equation.
- Row-reduce \(\begin{bmatrix}1&1\\2&2\end{bmatrix}\) and use the resulting homogeneous system to decide whether its columns are independent.
- In your own words, distinguish what row operations preserve from what they may change about a matrix’s columns.
- Explain why having only the zero solution for \(\mathbf{R}\mathbf{x}=\mathbf{0}\), where \(\mathbf{R}\) is row equivalent to \(\mathbf{A}\), is enough to conclude that the columns of \(\mathbf{A}\) are independent.
