Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
    
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
add comment

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.