# insight on lemma on linear independence and spanning set

I've been staring at this lemma in my book on linear algebra for hours but I haven't managed to figure it out. Please help me understand.

Lemma:

Let $V$ be a finite-dimensional $K$-vectorspace with $S$ a spanning set. $|S| = n \in \mathbb{N}$. Then every linear independent set in $V$ has a maximum of $n$ elements.

Proof:

Let $U \subset V$ with $|U| > n$. Let $w_1,\ldots,w_{n+1}$ be $n+1$ distinct elements in $U$. Let $S = \{ v_1,\ldots,v_n \}$. Since span($S$) = $V$, we have $w_1 = a_{11}v_1+\ldots+a_{1n}v_n$, $\ldots$, $w_{n+1}=a_{n+1,1}v_1+\ldots+a_{n+1,n}v_{n}$.

Let us look at the system of linear equations: $\left\{ \begin{array}{c} a_{11}x_1 + \ldots + a_{n+1,1}x_{n+1} = 0 \\ \vdots \\ a_{1n}x_1 + \ldots + a_{n+1,n}x_{n+1} = 0 \end{array} \right.$

Since the system has more unkowns than equations and the system is valid ($x_1 = \ldots = x_n = 0$ is a solution), we have a solution $x_1 = c_1, \ldots, x_n = c_n$ with not all $c_i = 0$.

Now we have: $c_1w_1 + \ldots + c_{n+1}w_{n+1} = \sum_{i=1}^{n+1}{c_i ( \sum_{j=1}^{n}{a_{ij}v_j} ) } = \sum_{j=1}^{n}{( \sum_{i=1}^{n+1}{c_ia_{ij}} ) v_j} = 0$. Thus we have found a non-trivial linear combination of all sets with $n+1$ elements in $V$.

Question:

How has the above proof found a non-trivial linear combination of all sets with $n+1$ elements in $V$?

-

The lemma tries to establish that the vectors $w_1, \ldots, w_{n+1}$ are not linearly independent. This means that we must find constants $c_1, \ldots, c_{n+1}$ such that $\sum_{i=1}^{n+1} c_i w_i = 0$ and at least one $c_i \neq 0$ (this is the definition of linear independence). The requirement that at least one $c_i \neq 0$ is what "nontrivial combination" means. Otherwise you could choose all $c_i = 0$ and have $\sum_{i=1}^{n+1} c_i w_i = 0$ but that doesn't prove anything.

Now do you understand how the constants $c_i$ were discovered in the lemma?

In the last line of the proof, you permute the sums to emphasize terms of the form $\sum_{i=1}^{n+1} c_i a_{ij}$. The $j$-th term is precisely the $j$-th equation of the rectangular linear system that you wrote, so each of those sums is identically zero.

In conclusion, you've found $c_1, \ldots, c_{n+1}$ (and you know that at least one of them is nonzero) such that $\sum_{i=1}^{n+1} c_i w_i = 0$.

-
I don't understand why $\sum_{i=1}^{n+1}c_ia_{ij} = 0$. I also don't understand why $c_1,\ldots,c_{n+1}$ has atleast one $c_i \neq 0$. I understand all the other steps. – xcrypt Feb 3 '13 at 16:29
I think you're assuming $\sum_{i=1}^{n+1}{c_ia_{ij}} = 0$ because we looked at the system of linear equations above. But it never stated $\sum_{i=1}^{n+1}{c_ia_{ij}} = 0$. If we assume that we take exactly those $c_i, a_{ij}$ such that the system holds, it makes a little more sense. Hmm, I think I'm starting to understand now. – xcrypt Feb 3 '13 at 16:43
The sums are zero by independence of the $v_i$'s. But I don't see why at least one $c_i$ is nonzero, in your approach: if you know it you already win, don't you? :) – Brenin Feb 3 '13 at 17:04
@atricolf because we take the $a_{ij}$ from the $w_i = \sum_j^n{a_{ij}v_j}$, then we choose the unkowns $c_i$ such that the system of linear equations holds. In the end we don't assume that $\sum_{i=1}^{n+1}c_iw_i = 0$. We just end up with $0$ because of the simplification. This is where I seemed to go wrong for hours. – xcrypt Feb 3 '13 at 17:09
The $c_i$'s solve a system of $n$ equations with $n+1$ unknowns. The coefficient matrix of this system has a nontrivial nullspace. That is why you can pick the $c_i$'s so at least one of them is nonzero. In other words, there exists a nonzero vector $c$ in the nullspace of this matrix: $Ac=0$ with $c \neq 0$. – Dominique Feb 3 '13 at 18:22

I'll try to explain how I see this proof. First, this is the strategy: we have a spanning set $S=\{v_1,\dots,v_n\}$ and we assume by contradiction that a subset $U\subset V$ contains $n+1$ distinct linearly independent vectors $w_1,\dots,w_{n+1}$. This will lead to a contradiction at some point.

You can write $$w_i=\sum_{1\leq j\leq n}a_{ij}v_j,\,\,\, 1\leq i\leq n+1.$$

Now, pick a linear combination $c_1w_1+\dots+c_{n+1}w_{n+1}=0$; if, by contradiction, they were independent, then we would have $c_i=0$ for all $1\leq i\leq n+1$ (and this is the unique possible choice for the $c_i$'s!). But writing this in terms of the displayed formula, as you did, gives $$\sum_{1\leq i\leq n+1}c_ia_{ij}=0,$$ for every $1\leq j\leq n$. And this is a contradiction because it is equivalent to saying that the system $(a_{ji})\cdot \underline X=0$ has a unique solution. (This is impossible since there are more unknowns than equations.)

-