Prove that if $v_{p} \notin \text{span}(S_k)$ then $S_{p} = S_k \cup\{v_{p}\}$ is linearly independent.

Question

Let $S_k = \{v_1, v_2, ..., v_k\}$ be a linear independent set where each $v_i\in \mathbb{R}^n$.

Prove that if $v_{p} \notin \text{span}(S_k)$ then $S_{p} = S_k \cup\{v_{p}\}$ is linearly independent.

I'm having a bit of trouble with coming up with a proof for this. So far I have the following.

---

Proof (contrapositive).

If $S_{p} = S_k \cup\{v_{p}\}$ is linearly dependent then $v_{p} \in \text{span}(S_k)$.

Let $A = (v_1|v_2|...|v_k|v_{p})\in \mathbb{R}^{n\times(k+1)}$. Since $S_{p}$ is linearly dependent, $A\tilde c = \tilde 0$ where not all $c_i \in \tilde c$ are $0$.

Since $v_1, v_2, ..., v_k$ are linearly independent, we can conclude that by row reducing $A$, the pivots occur in the first $k$ columns of $A$ since pivots correspond the linearly independent vectors. We can also conclude that the $k+1$ column corresponds to a free variable. Thus, $v_p$ is expressible as a linear combination of the vectors to its left in $A$. So we can conclude that $v_{p} \in \text{span}(S_k)$.

Would this hold as a proof?

Answer 1

I would say your proof is acceptable, but could be improved. Perhaps another sentence or so of explanation as to why the linear independence of $S_k$ makes the free variable occur in the $k+1$ column of $A$ would round out the proof.

I think that a simpler proof uses strictly the definition of linear independence/dependence, rather than relying on knowledge of matrices and pivots and so on. For your contrapositive argument, we can simply do the following.

Suppose $S_p=S_k\cup\{v_p\}$ is linearly dependent. Then there exists scalars $c_1,\ldots, c_p$ not all zero (say, $c_t\neq 0$ for some $t$) such that $$0=c_1v_1+\cdots+c_pv_p\iff c_pv_p=-(c_1v_1+\cdots +c_kv_k)$$ If $c_p=0$ then $0=c_1v_1+\cdots+c_kv_k$ with some $c_t\neq 0$, contradicting linear independence of $S_k$. Hence, $c_p\neq 0$ so we get $$v_p=\frac{-1}{c_p}(c_1v_1+\cdots+c_kv_k)\implies v_p\in\operatorname{Span}(S_k)$$

Answer 2

Let $c_1,...,c_k, c_p$ such that $c_1v_1+..+c_kv_k+c_pv_p=0$, we deduce that $c_1v_1+..+c_kv_k=-c_pv_p$, if $c_p\neq 0$, this implies that $v_p={{-1}\over c_p}(c_1v_1+..+c_kv_k)\in S_k$ contradiction, so $c_p=0$ and $c_1v_1+..+c_kv_k=0$ this implies that $c_1=...=c_k=0$ since $v_1,..,v_k$ linearly independent.