If entries at pivot position are zero then the column is a linear combination of the previous columns

linear algebramatricesmatrix-rank

In the 7th lecture of Gilbert Strang's Linear Algebra course, he does row operations on a matrix (m x n) to convert it to echelon form. He found the first k pivot elements; for k+1 th pivot element, he found that the entries of a column from row k+1 to m are zero, and from this, he concludes that this column is a linear combination of previous columns. Why or how can we figure that out?

Here is the link to the video (from the point where he says that) https://youtu.be/VqP2tREMvt0?list=PL49CF3715CB9EF31D&t=281

Best Answer

At the point in the lecture that you refer to, Strang has found the first two columns of the final reduced row echelon form. In general, the reduced row echelon form (RREF) can be interpreted as sequentially reporting the relationships between the columns so far: a column of $A$ is a pivot column (i.e. corresponds to a pivot in the RREF) if (and only if) it is linearly independent to the columns before it. Otherwise, the entries of that RREF column express how it can be attained as a combination of the previous pivot columns in $A$.

In the particular problem, Strang computes the reduction $$ A = \pmatrix{1&2&2&2\\2&4&6&8\\3&6&8&10} \leadsto R = \pmatrix{1&2&0&-2\\0&0&1&2\\0&0&0&0}. $$ We can interpret the columns of $R$ as follows:

  • $(1,0,0)$: the first column of $A$ is independent from the columns that proceed it (this is always true if the first column is non-zero)
  • $(2,0,0)$: the second column of $A$ is not independent from the columns that precede it. It can be expressed as $2 \cdot [\text{pivot column 1}]$.
  • $(0,1,0)$: the third column of $A$ is independent from the columns that proceed it.
  • $(-2,2,0)$: the fourth column of $A$ is not independent from the columns that precede it. It can be expressed as $-2 \cdot [\text{pivot column 1}] + 2 \cdot [\text{pivot column 2}]$.

Here's a "proof" of this phenomenon. Note first that row-operations preserve the nullspace. That is, if $R$ is the RREF of $A$, then the solutions to $Ax = 0$ are the same as the solutions to $Rx = 0$. On the other hand, every description of a column of $R$ in terms of its other columns corresponds to an element of the nullspace of $R$. It follows that any linear relationship between the columns of $R$ must also hold for the columns of $A$.

For example, the fact that $[\text{column 2}] = 2 \cdot [\text{column 1}]$ can be expressed as $$ 2 \cdot [\text{column 1}] - 1 \cdot [\text{column 2}] = 0 \iff R \pmatrix{2\\-1\\0\\0} = \pmatrix{0\\0\\0\\0}, $$ which is to say that $(2,-1,0,0)$ is an element of the nullspace of $R$. This means that $(2,-1,0,0)$ is also an element of the nullspace of $A$, which (if we follow our previous line of reasoning backwards) means that the columns of $A$ also satisfy the relation $[\text{column 2}] = 2 \cdot [\text{column 1}]$. Similarly, the fact that $[\text{column 4}] = -2 \cdot [\text{column 1}] + 2 \cdot [\text{column 3}]$ holds for the matrix $R$ corresponds to the fact that the vector $x = (-2,0,2,-1)$ is an element of the nullspace of $R$, which in turn implies that it is an element of the nullspace of $A$, which in turn implies that the columns of $A$ satisfy this same relation.

Related Question