# Linear algebra : Homework. Show that there exists $n+1$ vectors $u_1,u_2,…,u_n,u_{n+1}$

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!

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

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

-

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

-
NICE~ lOVED your explanation – Yellow Skies Oct 20 '12 at 6:04