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!

  • $\begingroup$ You recycled the $c$'s. If (as you should) you write $s=d_1u_1+\cdots +d_nu_n$, the proof disappears. $\endgroup$ – André Nicolas Oct 20 '12 at 5:35
  • $\begingroup$ I don't get it... congfrats on your 100k anyway~~ $\endgroup$ – Yellow Skies Oct 20 '12 at 5:38
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Oct 20 '12 at 5:43
  • $\begingroup$ ah! Thanks nicolas~ gotta work on a new way now $\endgroup$ – 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).

  • $\begingroup$ NICE~ lOVED your explanation $\endgroup$ – Yellow Skies Oct 20 '12 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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