Reduced row echelon form and linear independence

Let's say I have the set of vectors $S = \{v_1, v_2, ..., v_n\}$ where $v_j \in R^m$, $v_j = (a_{1j}, a_{2j}, ..., a_{mj})$.

If the matrix formed by each of the vectors $A=[v_1, v_2, ..., v_n]$ looks like this (I believe), which is not a square matrix:

$$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$$

Then does A's reduced row echelon form help me determine whether the vectors of $S$ are linear dependent or independent? If so, how?

I hope I got all the indices, notation and terminology right, since I am a beginner in linear algebra, and English is not my native language.

• You have supplied the matrix $A$ with columns that correspond to vectors in $S$. While the row echelon form of $A$ (reduced or not) does convey some information about the number of linearly independent vectors in $S$, it could create a more direct correspondence to have rows of $A$ taken from $S$. – hardmath Jan 23 '16 at 23:23
• @hardmath: Yes, I have seen something similar somewhere else, where you put the vectors as columns of the matrix. How do you deduce from this the number of independent vectors? Also, how would you deduce the dependence/independence from the matrix of which the vectors are rows? – DJakarta Jan 23 '16 at 23:31

The "row rank" of $A$ is the number of linearly independent rows it has, and the "column rank" the number of its linearly independent columns. The key facts are (for any matrix $A$) that:

• The row rank is equal to the column rank.

• The row (equiv. column) rank is unchanged by elementary row operations.

Therefore you can get the rank of $A$ (as we say for simplicity) by counting the leading ones of its row echelon form. Since $S$ has $n$ vectors, we need the rank of $A$ to be $n$ (it cannot be more) in order for $S$ to be a linearly independent set.

• Thanks for your great answer! I think I understand now. – DJakarta Jan 24 '16 at 0:07
• I like to think of the reduced row-echelon form as the Swiss Army Knife of matrix computations, since it allows us to answer so many problems in linear algebra. – hardmath Jan 24 '16 at 0:08
• It does seem quite useful. That's why I asked this question: even though I wasn't sure you can use it for this purpose, it looked like it is connected. I just wasn't sure if and how. – DJakarta Jan 24 '16 at 0:10

Yes, but since you are considering the column vectors, you know that they are all independent if each column has a leading one in the reduced row-echelon form.

If we look at an explicit example:

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

Then we have

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

Notice that since columns $3$ and $4$ in $RREF(A)$ do not have leading $1$'s, they are dependent on the first two columns. Specifically:

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

$\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}$

Notice that the entries in column $3$ of $RREF(A)$ respectively correspond to the scalars for columns $1$ and $2$, such that column $3$ can be written as a linear combination of those columns. And the same goes for column $4$.

But if each column of $RREF(A)$ has a leading $1$, then each column is linearly independent.

Sidenote: The number of rows with all zeros in $RREF(A)$ tell only how many rows are independent/dependent (unless it is a square matrix, then the number of (in)dependent rows/columns will be the same) Looking at the leading 1's is much more helpful in determining linear dependence.

• Great answer. Thanks! I think I got it! – DJakarta Jan 24 '16 at 0:06
• For your explanation on how you find the coefficients of the dependent columns, $(2, -1)$ and $(3, -1)$, these are the coefficient of the first and second independent column (the ones with the pivots), not the first and second in the matrix, from what I believe. Is this true? For your example they are the same, but for $\begin{pmatrix}1 & 2 & 2 & 4\\ 0 & 0 & 1 & 3\\ \end{pmatrix}$ I believe these will be different and the coefficients will be for the independent pivot columns, if I understand correctly. – DJakarta Jan 28 '16 at 21:37
• No, it actually would still work. For $$A=\begin{bmatrix} 1 && 2 && 2 && 4 \\ 0 && 0 && 1 && 3 \end{bmatrix}$$, we have $$RREF(A)=\begin{bmatrix} 1 && 2 && 0 && -2 \\ 0 && 0 && 1 && 3 \end{bmatrix}$$. Then we would have $$\begin{bmatrix}2 \\ 0 \end{bmatrix}=2\begin{bmatrix}1 \\ 0 \end{bmatrix}$$ and $$\begin{bmatrix}4 \\ 3 \end{bmatrix}=-2\begin{bmatrix}1 \\ 0 \end{bmatrix}+3\begin{bmatrix}2 \\ 1 \end{bmatrix}$$ I may not have worded it clearly, but the coefficient in that row for each dependent column corresponds to the independent column whose pivot is in that row. – yung_Pabs Jan 31 '16 at 21:16
• That's what I was thinking. Thanks! :) – DJakarta Jan 31 '16 at 21:30

Yes, if you can convert the matrix into reduced row echelon form(or even just row echelon form) without a row of $0$s,then the vectors are linearly independent.

• Does this work the other way around? Can you say that if you cannot convert the matrix into reduced row echelon form without a row of $0s$, the vectors are linearly dependent? – DJakarta Jan 23 '16 at 23:47
• Yes. That is true also. – Tim Raczkowski Jan 23 '16 at 23:48
• Well, let's say I have the vectors $(1, 0, 0, 0), (0, 1, 1, 0), (0, 0, 0, 1)$. They are clearly independent. The reduced row echelon form would be $\begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0\end{pmatrix}$, if I haven't made any mistakes. It has a row of $0s$, yet it the vectors are linearly independent. Am I mistaking/missing something? – DJakarta Jan 23 '16 at 23:54
• @hardmath Good point. I assumed the OP was talking about square matrices. – Tim Raczkowski Jan 23 '16 at 23:55
• @Tim: "without a row of 0s" should be "with a leading one in each column". – hardmath Jan 24 '16 at 0:16