# Proving that removing any vector of the linearly dependent set gives a linearly independent set

Consider the matrix representing 6 linearly dependent vectors: $$\left(\begin{array}{llllll} 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{array}\right)$$ I know how to prove that the vectors in this matrix are linearly dependent, but how can I show (concisely) that removing any one of the vectors we get a linearly independent set?

• The statement in the titles is false. However, in this particular example it is true. But I think you would have to show it "manually" because there is no theory about removing vectors from linearly dependent set converting it to a independent set. May 30, 2020 at 17:57
• The only vectors in the kernel are multiples of $(1,1,1,1,1,-1)$. Since there are no $0$ in this vector, any 5 columns are linearly independent May 30, 2020 at 17:59
• If you compute the five $5 \times 5$ minors (determinants of the matrices obtained by removing one column), they are all non-zero. Does anybody see a fastest solution? May 30, 2020 at 17:59
• Well, it is true in this case, which is why I wrote the linearly independent set. :)
– Manó
May 30, 2020 at 17:59
• @EnderWiggins read my comment May 30, 2020 at 18:01

Here the fastest method I can think of.

If (for example) the first 5 columns are linearly dependent, you can find a vector in the right kernel of the form $$\left[ \begin{array}a a\\ b\\ c\\ d\\ e\\ 0 \end{array}\right],$$ that is, a vector that ends with $$0$$. In general if you leave out the $$i-th$$ column and the rest are linearly dependent, you find a vector in the right kernel with a $$0$$ in the $$i$$-th position.

Since the only vectors in the right kernel of your matrix are the multiples of $$\left[ \begin{array}a 1\\ 1\\ 1\\ 1\\ 1\\ -1 \end{array}\right]$$ and it has no zeros, you can deduce that any 5 columns are linearly independent.

• That will suffice. Thank you. :)
– Manó
May 30, 2020 at 18:12

Note that the given matrix is in its Row Reduced Echelon Form and has rank 5. That is, its columns span $$\mathbb R^5$$.And basis of $$\mathbb R^5$$ can only have 5 vectors. There can not be more than 5 linearly independent vectors in $$\mathbb R^5$$. Now, coming to the given matrix, remove any column (say 3rd column), then you have $$5$$ by 5 matrix (rearrange the columns) in row reduced form with 5 pivots, hence the columns of this matrix are linearly independent. Same conclusion if you remove any other column from the given matrix. Hence, removing any column from the matrix (given in your post) results in a full rank square matrix.

• when you remove a column, it is not in row reduced form though... May 30, 2020 at 18:15
• @Exodd, my point is that by rearranging the columns (after removal of a column)-say, if you remove 1st column (then clearly we don't have row reduced form), bring the last column into first column and thus you have a row reduced form. Rearranging columns (switching column no. m with column no. n) really doesn't matter as we are only talking about linear independence of columns.
– Koro
May 30, 2020 at 18:18

You can build matrices excluding one column at a time.

If you call the original matrix $$M$$, and the matrix excluding column $$j$$ for $$M_j$$, then you can build a sparse matrix performing the exclusion, finding a factorization for $$M_j$$ in terms of $$M$$ like this:

$$M_j = ME_j$$

Where the $$E_j$$ matrices are truncated $$I$$(identity) matrices having row $$j$$ cut out.

Now to express what part of a random vector $$r$$ $$M_j$$ can capture, we can calculate

$$t_j = M_j({M_j}^{\dagger})r$$

where $$\dagger$$ is some suitable pseudo-inverse, for example Moore-Penrose.

If all $$t_j$$ are the same, then each vector is linearly dependent of all the others.

But if one is not, then it means that excluding that one loses some information.

An example when that happens is here:

$$\begin{bmatrix}0&0&0\\0&1&1\\1&1&1\end{bmatrix}$$

Excluding any one of column 2 or 3 won't make a difference, since they are the same.

But if we exclude 1, then we will lose information.

If you try it you shall find $$t_2\approx t_3 \neq t_1$$