Given a convex polyhedron $P$, how can we prove that every point $x \in P$ is in some simplex whose vertices are vertices of $P$? One proof is to inductively build a triangulation of $P$. If $P$ is the convex hull of vertices $\{v_1, \ldots, v_n\}$ and $P_k$ is the convex hull of $\{v_1, \ldots, v_k\}$ such that a triangulation of $P_k$ is given, construct a triangulation of $P_{k+1}$ by taking the simplices formed by $v_{k+1}$ and the faces of $P_k$ that are "visible" from $v_{k+1}$.
I want to know if there is a more algebraic proof. If $x \in P$ then $x = \sum_{i=1}^n \alpha_i v_i$ for some $\alpha_i \geq 0$ with $\sum_{i=1}^n \alpha_i = 1$. Assuming $P$ has dimension $d$, we need to find $d+1$ points $v_{i_j}$, $1 \leq j \leq d+1$, so that $x = \sum_{j=1}^{d+1} \beta_j v_j$ for some $\beta_j \geq 0$, $\sum_{j=1}^{d+1} \beta_j = 1$.
Inductively, assuming $n > d+1$, it's enough to find $\beta_i$, $1 \leq i \leq n$ with $\sum_{i=1}^n \beta_i = 1$ and $\beta_j = 0$ for some $j$, with $x = \sum_{i=1}^n \beta_j v_j$. If $M$ is the matrix with columns $v_1, \ldots, v_n$ and $\gamma = (\gamma_1, \ldots, \gamma_n)$ is in $\ker M$ then $\sum_{i=1}^n \gamma_i v_i = 0$ and so $x = \sum_{i=1}^n (\alpha_i - \gamma_i)v_i$. Can we find a $\gamma \in \ker M$ so that the $\alpha_i - \gamma_i$ satisfy the given properties? We need $\sum_i \gamma_i = 0$, $\alpha_i \geq \gamma_i $ for all $i$, and $\gamma_j = \alpha_j$ for some $j$.