What is the intuition for why row reduction can show linear dependence

Question

You can determine whether a set of column vectors is dependent by placing them in a matrix and getting the matrix into RREF. If all columns have a leading entry of $1$, then the set of vectors is independent. If a column does not have a leading entry but instead has one or more nonzero entries that are in the same row as a leading entry, then the set of vectors is dependent. For example, it can be shown that the following set of vectors $S$ is dependent:

$S=\left( \begin{bmatrix} 1 \\ 4 \\ 0 \\ 2 \end{bmatrix}, \begin{bmatrix} 3 \\ 1 \\ 4 \\ 0 \end{bmatrix}, \begin{bmatrix} -1 \\ 7 \\ -4 \\ 4 \end{bmatrix}, \begin{bmatrix} 0 \\ 11 \\ -4 \\ 6 \end{bmatrix} \right)$

This set of vectors can placed in a matrix $A$ and row reduced.

$A = \begin{bmatrix} 1 & 3 & -1 & 0 \\ 4 & 1 & 7 & 11 \\ 0 & 4 & -4 & -4 \\ 2 & 0 & 4 & 6 \end{bmatrix}$

Row reducing shows that the set of vectors is dependent because column $3$ and column $4$ have nonzero entries in the same row as leading entries.

$RREF(A)=\begin{bmatrix} 1 & 0 & 2 & 3 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

Furthermore, the entries of these columns correspond to scalars of linear combinations which show that the set of vectors is linearly dependent. For example, using the elements $3$ and $-1$ as scalars, it can be shown that column vector $4$ is a linear combination of column vectors $1$ and $2$.:

$ \begin{bmatrix} 0 \\ 11 \\ -4 \\ 6 \end{bmatrix} = $ $ 3\begin{bmatrix} 1 \\ 4 \\ 0 \\ 2 \end{bmatrix}$ $-\begin{bmatrix} 3 \\ 1 \\ 4 \\ 0 \end{bmatrix}$

Logically, why does the process of row reduction reveal the scalars which prove linear dependence in a set of vectors? I understand that it does work, but not why it should work.

EDIT: I understand that row operations don't change whether a set of column vectors are dependent/independent. My question was as follows: why in RREF do the entries of a column vector correspond to scalars in a linear combination which can prove linear dependence?

I thought of an analogy which would serve as an adequate answer to my question, but I'm not sure if it is accurate or not. You can see how large certain numbers are in terms of other numbers through division. For example, how large is the number $5$ in terms of $4$? The quotient $5/4=1.25$ tells us that $5$ is $1.25$ times as large as $4$. Similarly, through row reduction you can express column vectors in terms of other column vectors. When I row reduce columns $1$ and $2$ so that they have a leading entry of $1$, I express columns $3$ and $4$ in terms of columns $1$ and $2$.

Is this understanding somewhat accurate (it only has to serve as a general intuition)?

Answer 1

There are three kinds of row-operations and each corresponds to multiplcation by an "elementary" matrix that you can get by applying that row-operation to the identity matrix.

1. Multiply one row of a matrix by a number. For example "multiplying every term in the second row of a 3 by 3 matrix by a" is the same as multiplying by $\begin{bmatrix}1 & 0 & 0 \\ 0 & a & 0 \\ 0 & 0 & 1\end{bmatrix}$.

2. Swap two rows. For example "swapping the first and third rows of a 3 by 3 matrix"is the same as multiplying by the matrix $\begin{bmatrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$.

3. Add a multiple of one row to another. For example, adding a times the second row to the first row" is the same as multiplying by the matrix $\begin{bmatrix}1 & a & 0 \\0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}$.

A set of n vectors in n dimensions is "independent" if and only if the matrix created by using those vectors as rows or columns is invertible. And that is true if and only if the matrix can be "row reduced" to the identity matrix. Saying that row operations, $R_1$, $R_2$, ... , $R_n$, will reduce matrix A to the identity matrix to the identity matrix. That, in turn, means that the matrix product $r_nr_2...r_nA= I$, the identity matrix, where "$r_1$" is the matrix corresponding to operation $R1$, $r_2$ is the matrix corresponding to operation $R_2$, etc. But that means that $(r_nr_2...r_n)A= A^{-1}A= I$ so that A is invertible with inverse $A^{-1}= r_nr_2...r_n$.

Answer 2

1. In RREF, if we have a column, say A, with no pivot, it can be represented as a linear combination of the 1's on the left of it because values $a \in A$ can be written as $a(1)$. Sound good?

2. So the question then is why can we propagate our scalars from the RREF form back to our starting form through Row Operations. This is as per your end result and intrigue.

3. Naturally, then, we're looking to show why we can distribute our scalar across our row operations so that we can get back to our starting state.

So the way then I approach this solution is to examine valid row operations: O1) Interchange 2 rows O2) Scale a row by a scalar O3) Add two rows

We can distribute our scalar across O1 because O1 doesn't do anything to our equations. Think like a system here. All we did was rearrange the numbers.

We can distribute our scalar across O2 because O2 just scales all the numbers in the row by a scalar. Ex. ax1+bx2+cx3=d <=> tax1+tbx2+tcx3=td.

We can distribute our scalar across O3 because we are just setting two rows equal to one another and moving all the values from one side onto the other. Think like a system here. We just added to both sides.

F1) So In general, call a row operation O. We know then that aO=Oa, with a being some scalar, because we can always distribute our a over our row operation in a real number way.

F2) And of course, O1, O2, and O3 don't ever swap columns, so COLUMN_K_OF(OM)=COLUMN_K_OF(MO)=COLUMN_K_OF(M), where M is a matrix.

F3) This (F1 and F2) tells us that we can commute our linear combination L=<l1,l2,...,lk> of columns $j_1$, $j_2$, ..., $j_k$ in OA across any row operation such that $l1j_1 + l2j_2 + ... lkj_k = j_{k+1} <=> l1j_1'+l2j_2'+...+lkj_k'=j_{k+1}'$, $j_{k+1}$ being the result of our linear combination of course, and all the $j_i'$ being part of A.

That should answer your question, but to propagate for you:

If $O_n(...(O_2(O_1(A)))...)=RREF(A_{(p1,p2)})$, $RREF(A_{(p1,p2)})*L$=O_n(...(O_2(O_1(A)))...)*L=O_n(...(O_2(O_1(A)))...*L)=...=O_n(...(O_2(O_1(A)L))...)=O_n(...(O_2(O_1(AL)))...)$, where here, we have propagated the linear transformation vector L across our row operations all the way to our starting matrix.

Hope this helps!

Answer 3

Linear equations might be either consistent or inconsistent. Let us examine the first case: consistent linear equations. Consistent linear equations might have either a unique solution or infinitely many solutions. (Homogeneous equations are never inconsistent, they have at least zero solution which means unique solution) I am telling you this story because we arrange and solve linear equations in matrix forms.

Consider we have an $n\times n$ square matrix and assume it has full rank. According to rank-nullity theorem the dimension of its nullspace is zero. (It only includes the zero vector) Because the matrix have full rank, we have $n$ equations and $n$ unknowns. (which means there are unique solution) So we have:

$$A\mathbf x=\mathbf 0_n \Leftarrow \Rightarrow \mathbf x=\mathbf0$$

This basically means our matrix is invertible. (It doesn't have an eigenvector corresponding to zero eigenvalue) So it has an inverse;

$$A\mathbf x =\mathbf b $$ $$\mathbf x=A^{-1}\mathbf b$$

As seen $\mathbf x$ has a single value, which means $A$ has a unique solution. So I hope you get the relation between the consistency of linear equations and invertible matrices. Then let us see why the column vectors of invertible matrices are linearly independent;

If $\mathbf a_1, \mathbf a_2,...,\mathbf a_n$ are the column vectors of A then we have the definition of linear independency:

$$x_1 \mathbf a_1+x_2 \mathbf a_2+...+x_n \mathbf a_n=\mathbf 0_n \Leftarrow \Rightarrow x_1,x_2,...,x_n=0$$

Hope it helps you understand!