# Please, how can I prove this elementary linear algebra theorem? I'm trying to prove it by induction, i.e, I know how to prove that it is true for k = 1, but then I get counfused because the next induction step would be :

Assume that it is true for k-1 ( where k-1 is the cardinality of S ) and then show it is true for k. I can't do this last part.

I would like to do it without using concepts such as dimesion an so on, since it is a very elementary theorem that preceeds these concepts ( on my book. ) Thank you !

• I would avoid induction here. – Randall Aug 13 '17 at 20:21
• How would you do it ? please – Victor Aug 13 '17 at 20:21
• This concept might help you organize your proof: en.wikipedia.org/wiki/Quotient_space_(linear_algebra) – Lorenzo Najt Aug 13 '17 at 20:33
• Start by taking your $k+1$ vectors and writing each of them as linear combinations of your $x_i$. You now have a giant system which you can argue is overdetermined. There's your dependency among the original $k+1$ vectors. – Randall Aug 13 '17 at 20:45
• @MariosGretsas there is no need for that. The concept of dimension is a bit deeper than the result OP is considering. It is more difficult to prove that dimension is a well-defined concept, but sure, if you have that, then the question becomes trivial. – Ittay Weiss Aug 13 '17 at 20:52

Presumably, you've seen the basic theory of solutions of systems of $m$ equations in $n$ unknowns, possibly in the form of the some theorems about matrices in relation to Gauss elimination. So, take $k+1$ vectors in $S$, say $y_1,\dots, y_{n+1}$. Write each as a linear combination of the vectors $x_1,\dots, x_n$ (by the way, it is not important that these vectors are linearly independent, the result and this suggested proof remain the same without that assumption). Consider the matrix of coefficients and think of it as representing a system of equations. How many equations does it represent? How many unknowns? Now, if the vectors you chose in $S$ were linearly independent, what does that mean about the space of solutions of the system? Which elementary theorem does it this contradict?

Try a proof by contradiction. Let $\{v_1,\dots.v_{k + 1}\} \in L(S)$ be independent. We know that $\{v_1,x_1,\dots,x_k\}$ is dependent. So there is some $j$ such that $x_j$ can be expressed as a linear combination of $\{v_1,x_1,\dots,x_{j - 1},x_{j + 1},\dots,x_k\}$. So if we remove $x_j$, $\{v_1,x_1,\dots,x_{j - 1},x_{j + 1},\dots,x_k\}$ is still a spanning set. Verify that we can add $v_2$ to the set, pick another value of $j$, and remove $x_j$ while still having the set be spanning, and so on until we have replaced all the $x$'s with $v$'s. Then we have that $\{v_1,\dots,v_k\}$ are spanning which yields a contradiction since $v_{k + 1}$ is independent to those vectors.

Use induction. For $k=1$ it's easy. Say $k\ge 2$. Assume the result true for $k-1$. Let $y_1$, $\ldots$, $y_{k+1}$ dependent on $x_1$, $\ldots$, $x_k$. If in the expressions for the $y_i$ the vector $x_k$ does not appear then the $y_i$'s are dependent on $k-1$ vectors, so linearly dependent. Otherwise, say $x_k$ appears in the linear expression for the $y_{k+1}$. In this case, from any other vector $y_i$, $1\le i \le k$ we can subtract a multiple of $y_{k+1}$ so the resulting vector $$y'_i \colon = y_i - c_i y_{k+1}$$is dependent only on $x_1$, $\ldots$, $x_{k-1}$. Now by the induction hypothesis, the $k$ vectors $y'_i$ $1\le i \le k$ are linearly dependent $$\sum_{i=1}^k a_i ( y_i - c_i y_{k+1}) = 0$$ ( where nor all $a_i$'s are $0$ ), and from here we get a linear dependence for $y_1$, $\ldots$, $y_{k+1}$.

orangeskid's proof is constructive and gives rise to a recursive algorithm. Per my comment, I'll start with a base case of $n = 0$. Furthermore, the condition that $S$ be independent is unnecessary. The result also holds if $S$ is a dependent set. As a constructive proof, the algorithm constructively witnesses the fact that the $n+1$ vectors are dependent. That is, it produces the coefficients (not all $0$) that lead to a linear combination equal to $0$. I'll write $\langle x_1,\dots, x_n \rangle$ for a finite sequence.

The algorithm will be represented by a function $\mathcal{D}$ which will take a sequence of vectors, $\langle v_1, \dots, v_n \rangle$ representing $S$, a sequence of vectors, $\langle w_1, \dots, w_{n+1} \rangle$, and produce a sequence of scalars, $\langle c_1, \dots, c_{n+1} \rangle$ such that $\sum_{i=1}^{n+1} c_i w_i = 0$. Since $w_i \in L(\{v_1,\dots,v_n\})$, $w_i = \sum_{j=1}^n a_j v_j$ and so we'll represent $w_i$ as $\langle a_{i,1},\dots,a_{i,n}\rangle$, which makes $\langle w_1, \dots, w_{n+1} \rangle$ a sequence of sequences, better known as a matrix.

When $n = 0$, then $S = \{\}$ and $L(S) = \{0\}$. This gives the base case of the algorithm: $$\mathcal{D}(\langle\rangle,\langle\langle\rangle\rangle) \equiv \langle1\rangle$$

In the $n = m+1$ case, following orangeskid's proof we check whether $v_n$ occurs in any of the $w_i$. That is, if there is an $i$ such that $a_{i,n} \neq 0$. If there isn't, we can drop the last element of the sequences representing $w_i$ and take the first (or any) $n = m+1$ (out of $n+1$) $w_i$ and recurse:

$$\mathcal{D}(\langle v_1, \dots, v_n\rangle, \langle w_1,\dots, w_{n+1}\rangle) \equiv \langle c_1,\dots,c_n,0\rangle\text{ if }\forall i.a_{i,n}=0 \\ \text{where } w_i' = \langle a_1,\dots,a_m\rangle\text{ and }\langle c_1,\dots,c_n\rangle = \mathcal{D}(\langle v_1,\dots,v_m\rangle,\langle w_1',\dots,w_{m+1}'\rangle$$

Otherwise, if $a_{k,n} \neq 0$, we can write $w_i' = w_i - p_i w_k$ for $i \neq k$ such that $w_i' = \sum_{j=1}^m b_{i,j} v_j$. To accomplish this, we need to solve $a_{i,n} = p_i a_{k,n}$ which is just $p_i = \frac{a_{i,n}}{a_{k,n}}$. Generally, we have $b_{i,j} = a_{i,j} - p_i a_{k,j} = a_{i,j} - \frac{a_{i,n}a_{k,j}}{a_{k,n}}$. We now have $m+1$ vectors $w_i'$ each of length $m$, so we can recurse. The result is $\langle c_1, \dots, c_n\rangle$ such that $$\sum_{j=1}^{k-1} c_j w_j' + \sum_{j=k}^{n}c_j w_{j+1}' = 0 = \sum_{j=1}^{k-1} c_j (w_j - p_j w_k) + \sum_{j=k}^{n}c_j(w_{j+1}-p_{j+1}w_k)$$ Distributing gives the resulting coefficients $\langle c_1,\dots,c_{k-1},-\sum_{j=1}^{k-1} c_j p_j-\sum_{j=k}^nc_jp_{j+1},c_{k},\dots,c_{n}\rangle$. $$\mathcal{D}(\langle v_1, \dots, v_n\rangle, \langle w_1,\dots, w_{n+1}\rangle) \equiv \langle c_1,\dots,c_{k-1},-r,c_{k},\dots,c_n\rangle\text{ if }a_{k,n}\neq0 \\ \text{where }p_i = a_{i,n}/a_{k,n},\ w_i' = w_i - p_i w_n, \\ \langle c_1,\dots,c_n\rangle = \mathcal{D}(\langle v_1,\dots,v_{k-1},v_{k+1},\dots,v_n\rangle,\langle w_1',\dots,w_{k-1}',w_{k+1}',\dots,w_{n+1}'\rangle), \\ \text{and } r = \sum_{j=1}^{k-1} c_j p_j + \sum_{j=k}^{n}c_j p_{j+1}$$

You may notice that $\mathcal{D}$ is closely related to Gaussian elimination.

We'll use the following lemma, which can be shown by induction (try it next!):

Lemma. Let $V$ be a vector space, let $G_1 = \{v_1, \dots, v_n\}$ generate $V$, and let $L = \{w_1, \dots, w_m \} \subset V$ be independent. Then there exists a set $H \subseteq G_1$ containing $m$ distinct vectors such that $$G_2 := (G_1 \setminus H) \cup L$$ still generates $V$.

This means that you can remove $m$ vectors from a generating system containing $n$ vectors, substitute them with $m$ with linearly independent vectors, and still obtain a generating system. Of course, since the statement has $H \subseteq G_1$, it must be that $m \leq n$, that is, $|H| = |L| \leq |G_1| = |G_2|$.

Now let us consider $L(S)$, which is a vector space generated by $S$. Let $S' = \{y_1, \dots, y_{k+1}\} \subset L(S)$: then $S'$ too trivially generates $L(S)$ (just write some arbitrary $v \in L(S)$ as a linear combination of the $y_j$'s, then express each $y_j$ as a linear combination of $x_i$'s).

Let's prove your theorem by contradiction. Suppose that $S'$ is independent. Now apply the Lemma, using $S$ as $G_1$ and $S'$ as $L$. This implies that $|S'| \leq |S|$, that is, $k +1 \leq k$, which is false for all integer $k$.

• You implicitly used the concept of dimension. – Ittay Weiss Aug 14 '17 at 7:08
• Yet, no mention of dimension is made in the Lemma, which can be used to define such concepts – giobrach Aug 14 '17 at 7:52
• You used dimension when you say "since ... $H\subseteq G_1$, it must be that $m\le n$". – Ittay Weiss Aug 14 '17 at 11:56
• But that's a simple theorem from set theory! Though I agree that the Lemma itself can be regarded as "additional structure," since I exploited the fact that $L(S)$ is finitely generated and so on. I'll leave this here as a reference – giobrach Aug 14 '17 at 18:18
• I see. But why do you claim that $S'$ Still generates $L(S)$? – Ittay Weiss Aug 15 '17 at 7:43