1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @JoséCarlosSantos I have added the link to the video. Is it of any help? $\endgroup$
    – Aur Bhai
    May 2, 2022 at 7:53

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks for your response. Actually, I found out about it in his book where he has written that non-pivot columns are a linear combination of columns before them (as can be seen in this case). I want to get an intuition or a mathematical proof of why is it true $\endgroup$
    – Aur Bhai
    May 2, 2022 at 13:39
  • $\begingroup$ @AurBhai Se my latest edit. $\endgroup$ May 2, 2022 at 23:34
  • $\begingroup$ I got what you are trying to say. But here the combination can be seen once you get reduced form. I want to know that suppose while elimination of a matrix with 5 columns when you try to find 3rd pivot element you see that 3rd column has all zeros and hence cannot be a pivot column at this point itself how can we say that col 3 is a linear combination of col 1 and col 2 $\endgroup$
    – Aur Bhai
    May 3, 2022 at 2:53
  • $\begingroup$ The same logic can be applied to any intermediate form. If you reduce to a matrix $R$ and see that its third column can be written as a linear combination of the first two, then the same must hold for the original matrix. $\endgroup$ May 3, 2022 at 3:28
  • $\begingroup$ Thank you for your help $\endgroup$
    – Aur Bhai
    May 3, 2022 at 4:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .