# Prove that if the set of vectors is linearly independent, then the arbitrary subset will be linearly independent as well.

This one is quite straightforward, but I just want to make sure that my reasoning is clear.

I have following proposition:

Proposition. If $$S = \{\mathbf{v_{1}},\mathbf{v_{2}}...,\mathbf{v_{n}}\}$$ is linearly independent then any subset $$T = \{\mathbf{v_{1}},\mathbf{v_{2}}...,\mathbf{v_{m}}\}$$, where $$m < n$$, is also linearly independent.

My attempt:

We prove proposition by contrapositive.

Suppose $$T$$ is linearly dependent. We have

$$\tag1 k_{1}\mathbf{v_{1}} + k_{2}\mathbf{v_{2}}\cdots k_{j}\mathbf{v_{j}} ... k_{m}\mathbf{v_{m}} = \bf O$$

Where there is at least one scalar, call it $$k_{j}$$, such that $$k_{j} = a$$ ($$a ≠ 0$$) and all other scalars are zero.

Since $$T$$ is the subset of $$S$$, the linear combination of vectors in $$S$$ is:

$$\bigl(k_{1}\mathbf{v_{1}} + k_{2}\mathbf{v_{2}}\cdots k_{j}\mathbf{v_{j}} ... k_{m}\mathbf{v_{m}}\bigr) + k_{m+1}\mathbf{v_{m+1}}\cdots +k_n\mathbf{v_{n}} = \bf O$$

Let $$k_{j} = a$$, and set all other scalars for zero:

$$\underbrace{\bigl(0\cdot\mathbf{v_{1}} + 0\cdot\mathbf{v_{2}}\cdots a \cdot \mathbf{v_{j}} ... 0\cdot\mathbf{v_{m}}\bigr)}_{\mathbf{= O} \text{ by } (1)} + \underbrace{0\cdot\mathbf{v_{m+1}}\cdots +0\cdot\mathbf{v_{n}}}_{\mathbf{= O} \text{ because all scalars = 0}}= \bf O$$

We can see that linear combination of $$S$$ equals to zero but we have at least one non-zero scalar, which implies that $$S$$ is not linearly independent, which is a contradiction. Therefore, if $$S$$ is linearly independent, arbitrary subset $$T$$ must be linearly independent as well. $$\Box$$

Is it correct?

• I think you should not say that $k_j=a$ and all the other scalars are zero, and you don't need this anyway. You can/need only say that there is at least one non-zero scalar. The dependence for $T$ becomes a dependence for $S$ as you have outlined. Commented Sep 15, 2019 at 7:56

Proof looks good, but scalars $$k_{1},...,k_{j-1},k_{j+1},...,k_{m}$$ may not be all zero. But still you will get set $$\{ v_{1},...,v_{n} \}$$ as linear dependent, due to false assumption. Also you can not mix both proof by contradiction and proof by contrapositive in general.

I don't see anything wrong with your proof. Just be careful with the claim that you get a contradiction. The contrapositive of a statement is logically equivalent to the statement itself, so you don't get any contradiction whatsoever when proving a contrapositive.

If you were to use a proof by contradiction, you would start off by assuming that $$S$$ is linearly independent but $$T$$ is not, and show that it leads to some impossibility.

• Should I just delete "which is a contradiction" part then? Commented Sep 15, 2019 at 7:20
• Yes, it is enough just to say that you're proving the contrapositive at the beginning of the proof.
– jl00
Commented Sep 15, 2019 at 7:21
• To be honest, I'd thought proofs by contradiction and by contrapositive were the same thing, i.e, if you want to prove $P \implies Q$, then you assume that $\lnot Q$ and show that $P$ is impossible (contradiction), or in other words, show that $\lnot P$ (contrapositive). Just the wording a bit different. Commented Sep 15, 2019 at 7:22
• @Nelver This may help you Commented Sep 15, 2019 at 7:29
• In fact they are not the same, since we have $P \implies Q \iff \neg Q \implies \neg P$ (the contrapositive), whereas in a proof by contradiction, you assume $\neg (P \implies Q) \iff \neg (\neg P \lor Q) \iff \neg \neg P \land \neg Q \iff P \land \neg Q$
– jl00
Commented Sep 15, 2019 at 7:29