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.

Let $V$ be a vector space of dimension n. Show that there exists $n+1$ vectors $u_1,u_2,...,u_n,u_{n+1}$ such that every vector in $V$ can be expressed as a linear combination of $u_1,u_2,...,u_n,u_{n+1}$ with non-negative coefficients.

Can anyone check my solution? I checked my solution to the answer which was completely different so I was wondering if I could do it this way.

Dimension $n$ implies Basis has $n$ vectors.

Let $s$ be any vector in $V$ and let $T$ be a basis of $n$ vectors, i.e $T= (u_1,u_2,...,u_n)$. Therefore $s$ can be written as $s=c_1u_1+c_2u_2+...+c_nu_n$

Since $u_1,u_2,...,u_n,u_{n+1}$ are linearly dependent, let $u_{n+1}=c_1u_1+c_2u_2+...+c_nu_n$. Therefore $s=u_{n+1}=0u_1+0u_2+...+0u_n+1u_{n+1}$.

Therefore I have expressed every vector in V in terms of linear combinatyion of non-negative coefficients of 0 and 1!

share|improve this question
    
You recycled the $c$'s. If (as you should) you write $s=d_1u_1+\cdots +d_nu_n$, the proof disappears. –  André Nicolas Oct 20 '12 at 5:35
    
I don't get it... congfrats on your 100k anyway~~ –  Yellow Skies Oct 20 '12 at 5:38
1  
You assumed that the same constants would be used to write $s$ as a linear combination of $u_1,\dots,u_n$ as to write $u_{n+1}$ as a linear combination of $u_1,\dots,u_n$. Remember, there have to be $u_1,\dots,u_{n+1}$ that work for every $s$. –  André Nicolas Oct 20 '12 at 5:43
    
ah! Thanks nicolas~ gotta work on a new way now –  Yellow Skies Oct 20 '12 at 5:46

2 Answers 2

up vote 8 down vote accepted

Let $u_1,u_2,\dots,u_n$ be any basis, and let $u_{n+1}=-(u_1+u_2+\cdots+u_n)$.

Now let $s$ be any element of our vector space, and suppose that $$s=c_1u_1+c_2u_2+\cdots +c_nu_n.$$ If all the $c_i$ are $\ge 0$, there is nothing to do, we have $s=c_1u_1+\cdots +c_n u_n+(0)u_{n+1}$. If some of the $c_i$ are negative, let $-k$ be the smallest of the $c_i$. Then $$s=(c_1+k)u_1+ (c_2+k)u_2+ \cdots +(c_n+k)u_n+ ku_{n+1}.$$ All the coefficients are $\ge 0$.

Remark: The proof proposed in the OP does not work. We have to exhibit fixed vectors $u_1,\dots,u_n,u_{n+1}$ that work for every $s$.

share|improve this answer

Your answer won't work. You've shown the following: for every vector $v \in V$, there exist $u_1, ..., u_{n+1}$ such that $v$ is a non-negative linear combination of the $u_i$. Such a statement is almost trivial, since you could choose $u_{n+1} = v$ (which you did), and you're done. Notice that that's different than saying that there exist $u_1, ..., u_{n+1}$ such that any $v \in V$ is expressible as a non-negative linear combination of the $u_i$.

If it helps, notice that the order of quantifiers matters. $\forall x, \exists y$ such that $P$ is not the same as $\exists y$ such that $\forall x, P$ (in general).

share|improve this answer
    
NICE~ lOVED your explanation –  Yellow Skies Oct 20 '12 at 6:04

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.