# Existence of Basic Feasible Solution: Polyhedron in Standard Form

Exercise 2.6 Bertsimas Linear Optimization: Let $$A_1,...A_n$$ be a collection of vectors in $$\mathbb R^m$$. Let $$C=\sum_{i=1}^{n}{\lambda_{i} A_{i} \mid \lambda_1,..\lambda_n \geq 0}.$$

Show that any element of $$C$$ can be expressed in the form: $$\sum_{i=1}^{n} \lambda_{i} A_{i}$$, with $$\lambda_{i} \geq 0$$, and with most $$m$$ of the coefficients $$\lambda_{i}$$ being nonzero. Hint: consider the polyhedron $$\nabla=\{(\lambda_1,...\lambda_n) \in \mathbb R^n \mid \sum_{i=1}^{n} \lambda_i A_i=y, \lambda_1,...\lambda_n \geq 0\}$$

Attempt at Proof with some thoughts: Clearly the when $$n \leq m$$ we get the desired result. Now, suppose $$n>m$$. Consider the polyhedron $$\nabla=\{(\lambda_1,...\lambda_n) \in \mathbb R^n \mid \sum_{i=1}^{n} \lambda_i A_i=y, \lambda_1,...\lambda_n \geq 0\}$$ I want to use that $$\nabla$$ has a basic feasible solution since it is a polyhedron written in standard form as this will make the proof easier for me. Is this true, however? We haven't made assumption about the rows of $$A$$ being linearly independent, so I'm not sure if I can state that $$\nabla$$ has a basic feasible solution. Is it true that $$\nabla$$ has a basic feasible solution?