Q:

Express column of a matrix as a linear combination of other columns

A matrix C is given as such:
$C = \begin{bmatrix}1&3&2&1&1&3\\2&6&5&4&4&9\\1&3&3&3&4&8\\3&9&9&9&10&20\end{bmatrix}$
Suppose I wanted to express column 4 as a linear combination of the other columns in C. I found the echelon form of C, which is:
$U = \begin{bmatrix}1&3&2&1&1&3\\0&0&1&2&2&3\\0&0&0&0&1&2\\0&0&0&0&0&0\end{bmatrix}$
Therefore, $\begin{bmatrix}3\\0\\-2\\1\\0\\0\end{bmatrix}$ is in the nullspace of C, which means column 4 = (-3)column 1 + (2)column 3 for the columns in matrix U. However, the coefficient seems to hold for matrix C as well, but doesn't elimination change column space? I understand that it must be possible to express column 4 as linear combination of column 1, column 3, and column 5 for matrix C, since they're the pivot columns, but wouldn't you have to recalculate the coefficients? So does this always hold true and could you explain it in simple terms. Thanks.

A:

Relations between columns of a matrix $A$ can be expressed as $AX=0$, for some column $X$ (since $AX = X_1 col_1(A) + X_2 col_2(A) + ... + X_n col_n(A)$).
Row operations correspond to multiplications to the left by invertible matrices. Hence by performing a sequence of row operations, a matrix $A$ is transformed into some $B = UA$, with $U$ invertible.
Then: $BX= 0 \Longleftrightarrow (UA)X = 0 \Longleftrightarrow U(AX)=0 \Longleftrightarrow AX=0$, because $U$ is invertible. Hence the linear relations satisfied by the columns of a matrix are preserved through row operations.

