3
$\begingroup$

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!

  • 0
    ah! Thanks nicolas~ gotta work on a new way now2012-10-20

2 Answers 2

8

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

3

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

  • 0
    NICE~ lOVED your explanation2012-10-20