3

I want to prove that for a finite set $M$, the convex hull conv$(M)$ is a polytope. I often see this written, but I haven't actually seen a proof for this yet. The definition I use for polytope is, that it is a bounded polyhedron and a polyhedron is a set of points satisfying inequalities of the form $Ax\leq b$.
Geometrically it is relatively easy to see that this is true, but I find a proof of this quite hard.

conv$(M)=\{\sum^n_{i=1}\lambda_im_i:\lambda\geq0,\; \sum^n_{i=1}\lambda_i=1\}$, i.e. the convex combination of all points $m_i$ in $M$.

Since $M$ is finite, it is also bounded, therefore conv$(M)$ is bounded, meaning if conv$(M)$ is a polyhedron, it is also a polytope.

My problem now lies in the proof of conv$(M)$ being a polyhedron. As conv$(M)$ is essentially the union of line segments between points in $M$, and line segments are polyhedra, I think it would be possible to show it using the fact that for sets $s,s'\subset\Bbb{R}^n$: conv$(s)$+conv$(s')$=conv$(s+s')$. But I am having difficulties coming up with a proof and so I would appreciate any help. Thank you.

user619755
  • 620
  • Let $M\subset\Bbb R^n$ and suppose that $\text{conv}(M)$ contains an $n$-simplex. Look at the planes of $P$ the following form: $P$ contains $n+1$ affinely independent points of $M$, and all points of $M$ are in one of the closed half-spaces defined by $P$. There are finitely many such $P$, and $\text{conv}(M)$ will be the intersection of these closed half-spaces. There's still quite some work needed to prove this... – Angina Seng Sep 16 '20 at 14:23

0 Answers0