The diameter of a convex hull.

Question

I want to prove the following statement:

Given $A\subset \mathbb{R}^n$ let $C(A)$ be its convex hull. Prove that $\text{diam }(A)=\text{diam }(C(A))$.

I can suppose that $A$ is a bounded closed set and I know that if $x,y\in A$ are such that $d(x,y)=\text{diam }(A)$ then $x,y\in \partial A$. I tried proving that if $z,w\in \partial C(A)$ then $d(z,w)\leq d(x,y)$ but it is a little difficult to me using the fact $C(A)$ is the convex hull.

Any hint?

Answer 1

Let $\ell = \mathrm{diam}\;A$.

Since $C(A) \supseteq A$, it is trivial to see $\mathrm{diam}\;C(A) \ge \ell$.

If $\mathrm{diam}\;C(A) > \ell$, then one can find $p, q \in C(A)$ such that $d(p,q) > \ell$.

By Carathéodory's theorem, we can express $p$ as a convex linear combination of $P \le n+1$ points from $A$. More precisely, there exists $$\begin{cases} p_1, p_2, \ldots, p_P \in A\\ \lambda_1, \lambda_2, \ldots, \lambda_{P} \ge 0 \end{cases} \quad\text{ with }\quad \begin{cases} \lambda_1 + \lambda_2 + \cdots + \lambda_P = 1\\ \lambda_1 p_1 + \lambda_2 p_2 + \cdots + \lambda_P p_P = p \end{cases} $$ Similarly, we can find $Q \le n + 1$ points in $A$ such that $$ \begin{cases} q_1, q_2, \ldots, q_Q \in A\\ \mu_1, \mu_2, \ldots, \mu_Q \ge 0 \end{cases} \quad\text{ such that }\quad \begin{cases} \mu_1 + \mu_2 + \cdots + \mu_Q = 1\\ \mu_1 q_1 + \mu_2 q_2 + \cdots + \mu_Q q_Q = q \end{cases} $$ Notice as a function of $p$ and $q$, the distance $d(p,q) = |p-q|$ is a convex function in both of its arguments. This implies

$$d(p,q) = d\left(\sum_{i=1}^P \lambda_i p_i, \sum_{j=1}^Q \mu_j q_j \right) \le \sum_{i=1}^P\sum_{j=1}^Q \lambda_i \mu_j d(p_i, q_j) \le \left(\sum_{i=1}^P\lambda_i\right)\left(\sum_{j=1}^Q \mu_j\right) \ell = \ell$$

Contradicts with our choice of $p, q$ which satisfy $d(p,q) > \ell$. This implies the underlying assumption $\mathrm{diam}\;C(A) > \ell$ is invalid. As a result, $\mathrm{diam}\;C(A) = \ell = \mathrm{diam}\;A$.

Note

If one adopt the definition that by convex hull, one mean the collection of all convex linear combinations of points from a set. We don't need Carathéodory's theorem at all. The argument above works as long as $P, Q$ exist and are finite.

Answer 2

Let $x,y\in C(A)$. Then by Carathéodory's theorem, there exists $p,q\le n+1$ and $x_1,\dots,x_{p},y_1,\dots,y_{q}\in A$ such that $x=\sum_{i=1}^{p}\lambda_{i}x_{i} $, $y=\sum_{j=1}^{q}\gamma_{j}y_{j}$, $\sum_{j=1}^{q}\gamma_{j}=1=\sum_{i=1}^{p}\lambda_{i}$ and $\lambda_{i}\ge0\ (i=1,\dots,p)$, $\gamma_{j}\ge0\ (j=1,\dots,q)$. Therefore

$$\|x-y\| = \left\|\sum_{i=1}^{p}\lambda_{i}x_{i}-y\right\|=\left\|\sum_{i=1}^{p}\lambda_{i}(x_{i}-y)\right\|\le\sum_{i=1}^{p}\lambda_{i}\|x_{i}-y\| \\ = \sum_{i=1}^{p}\lambda_{i}\left\|x_{i}-\sum_{j=1}^{q}\gamma_{j}y_{j}\right\| = \sum_{i=1}^{p}\lambda_{i}\left\|\sum_{j=1}^{q}\gamma_{j}(x_{i}-y_{j})\right\| \le \sum_{i=1}^{p}\lambda_{i}\sum_{j=1}^{q}\gamma_{j}‖x_{i}-y_{j}‖ \le \left(\sum_{i=1}^{p}\lambda_{i}\right)\left(\sum_{j=1}^{q}\gamma_{j}\right) \operatorname{diam}A = \operatorname{diam}A\text.\tag1\label1$$

Now by taking supremum over $x,y\in C(A)$, from \eqref{1} we obtain $\operatorname{diam}{C(A)}\le\operatorname{diam}A$. Since $A\subseteq C(A)$ we get $\operatorname{diam}{C(A)}\ge\operatorname{diam}A$. Consequently, $\operatorname{diam}{C(A)}=\operatorname{diam}A$.

Answer 3

Let $x,y\in C\left( A\right) $. Then by Carath'{e}odory's theorem, there exists $p,q\leq n+1$ and $x_{1},...,x_{p},y_{1},...y_{q}\in A$\ such that $% x=\sum_{i=1}^{p}\lambda _{i}x_{i}$ , $y=\sum_{j=1}^{q}\gamma _{j}y_{j},\sum_{j=1}^{q}\gamma _{j}=1=\sum_{i=1}^{p}\lambda _{i}$ and $% \lambda _{i}\geq 0,i=1,...,p,\gamma _{j}\geq 0,j=1,...,q.$ Therefore \begin{eqnarray} \left \Vert x-y\right \Vert &=&\left \Vert \sum_{i=1}^{p}\lambda _{i}x_{i}-y\right \Vert =\left \Vert \sum_{i=1}^{p}\lambda _{i}\left( x_{i}-y\right) \right \Vert \leq \sum_{i=1}^{p}\lambda _{i}\left \Vert \left( x_{i}-y\right) \right \Vert \label{1} \\ &\leq &\sum_{i=1}^{p}\lambda _{i}\left \Vert \left( x_{i}-y\right) \right \Vert =\sum_{i=1}^{p}\lambda _{i}\left \Vert \left( x_{i}-\sum_{j=1}^{q}\gamma _{j}y_{j}\right) \right \Vert \nonumber \\ &\leq &\left( \sum_{i=1}^{p}\lambda _{i}\right) \left( \sum_{j=1}^{q}\gamma _{j}\right) \left \Vert \left( x_{i}-y_{j}\right) \right \Vert \leq \left( \sum_{i=1}^{p}\lambda _{i}\right) \left( \sum_{j=1}^{q}\gamma _{j}\right) \limfunc{diam}A \nonumber \\ &=&\limfunc{diam}A. \nonumber \end{eqnarray}% Now by taking supremum over $x,y\in C\left( A\right) $, from (\ref{1}) we obtain $\limfunc{diam}C\left( A\right) \leq \limfunc{diam}A$. Since $% A\subset C\left( A\right) $ we get $\limfunc{diam}C\left( A\right) \geq \limfunc{diam}A$. Consequently, $\limfunc{diam}C\left( A\right) =\limfunc{% diam}A$.

Answer 4

Using the finite-dimensionness in proving this fact is not a good practice since this claim is true in the infinite dimensional case too. Here is a proof:

Let $B$ be bounded subset of a Banach space $X.$ Its obvious that $\operatorname{diam}(B) \leq \operatorname{diam}(\operatorname{conv}B),$ since $B \subset \operatorname{conv}B.$ For the converse, pick $c_1 = \lambda_1 a_1 +(1-\lambda_1) a_2 \in \operatorname{conv}B$ and $c_2 = \lambda_2 b_1 + (1-\lambda_2) b_2 \in \operatorname{conv} B,$ for $\lambda_i \in [0,1]$ and $a_i, b_i \in B.$ Then \begin{align*} ||c_1 - c_2 || &= || \lambda_1 a_1 +(1-\lambda_1)a_2 - (\lambda_1 c_2 +(1-\lambda_1 )c_2)||=||\lambda_1(a_1 - c_2)+(1-\lambda_1)(a_2-c_2)|| \\ &\leq \lambda_1 ||a_1-c_2||+(1-\lambda_1)||a_2-c_2|| \\ &\leq \operatorname{max}\{||a_1-c_2||,||a_2-c_2||\}. \end{align*} If $\operatorname{max}\{||a_1-c_2||,||a_2-c_2||=||a_1-c_2||,$ then \begin{align*} ||a_1-c_2||&=||(\lambda_2 a_1 +(1-\lambda_2) a_1) - \lambda_2 b_1 -(1-\lambda_2) b_2|| =||\lambda_2 (a_1 - b_1)+(1-\lambda_2)(a_1-b_2)|| \\ &\leq \operatorname{max}\{||a_1-b_1||,||a_1-b_2||\} \leq \operatorname{diam} B. \end{align*} Thus $||c_1-c_2|| \leq \operatorname{diam} B,$ meaning $\operatorname{diam} B$ is one upper bound of $\{||c_1-c_2|| : c_1,c_2 \in \operatorname{conv} B\}$ and so it's greater or equal than its supremum $\operatorname{diam}(\operatorname{conv} B)\leq\operatorname{diam}(B).$ Following the equality $\operatorname{diam}(\operatorname{conv} B)=\operatorname{diam}(B).$