Proving linear dependence of a set of vectors generated from a linearly independent set

Question

I'm trying to prove the following:

Let a set of linearly independent vectors $S = \{y_1, \ldots, y_n\}$ be given. Let $T = \{x_1,\ldots, x_n, x_{n+1}\}$ be a set of vectors all of which are linear combinations of the vectors in $S$. Show that the vectors in $T$ are linearly dependent.

There's a step (written in bold) that I'm not sure about. My attempt : Suppose $x_i = \sum_{j=1}^n a_i^j y_j$ and let

$$\sum_{i=1}^{n+1}\alpha^ix_i = \sum_{i=1}^{n+1}\alpha^i\bigg(\sum_{j=1}^na_i^jy_j\bigg) = 0$$

So we have to prove that at least one of $\alpha^i$ can be non-zero. Consider one of the $\alpha^i$'s (say $\alpha^{n+1}$) : If this is non-zero, we're done. Otherwise, assume that $\alpha^{n+1}=0$. We get

$$\sum_{i=1}^n\alpha^i\bigg(\sum_{j=1}^na_i^jy_j\bigg) = \sum_{j=1}^n\bigg(\sum_{i=1}^n\alpha^ia_i^j\bigg)y_j = 0$$

Since $y_j$'s are independent, all their coefficients are $0$, which gives us the $n$ simultaneous equations in $\alpha^i$'s :

$$\sum_{i=1}^na_i^j\alpha^i = 0, ~~~~~~~~~~~~~~ j=1,2,\ldots,n$$

Beyond this, I'm not sure how to proceed. I know that for each $i$, at least one of $\{a_i^1, a_i^2, \ldots, a_i^n\}$ is non-zero and obviously this fact will be used in the upcoming steps. Any help would be appreciated.

Answer 1

A simpler approach:

Since $T \subseteq span(S)$, we have $span(T) \subseteq span(S)$, hence

$ \dim span(T) \le \dim span(S) \le n$.

Suppose that $T$ is linearly dependent, then we would have $ \dim span(T)=n+1$, a contradiction.

Answer 2

Consider the first $n$ vectors in T, which we can express in terms of vectors in S as follows:

$x_i = \sum_{j=1}^n \alpha_i^j y_j \quad \forall i \in \{1, \dots, n\}$

If $\{x_i, \dots, x_n \}$ are not linearly independent then we are done. If they are linearly independent then the matrix $A$ with entries $\alpha_i^j$ is invertible, so we can find co-efficients $\beta_i^j$ such that:

$y_i = \sum_{j=1}^n \beta_i^j x_j \quad \forall i \in \{1, \dots, n\}$

In that case

$x_{n+1} = \sum_{i=1}^n \gamma^i y_i = \sum_{i=1}^n \gamma^i \sum_{j=1}^n \beta_i^j x_j = \sum_{j=1}^n \left(\sum_{i=1}^n \gamma^i \beta_i^j \right) x_j$

so we can express $x_{n+1}$ as a linear combination of the other vectors in T, so once again the vectors in T are not linearly independent.