Convex hull of canonical basis of $\mathbb{R}^n$, face of a simplex

549 Views Asked by At

Let $I_n := \{1,2,...,n \}, \ p \in \Delta_n = \{(p_1, ..., p_n) \ | \ p_i \ge 0, \sum_{i=1}^n =1\}$

$ \text{supp (p)}= \{ i \in I_n \ | \ p_i \neq 0\}$

For a convex set $C$ we define $F$ to be its face if $F$ is convex and $\forall x,y \in C, \lambda \in (0,1) : \lambda x + (1- \lambda ) y \in F \Rightarrow x,y \in F$

For $A \subset I_n$ we define $F(A) : = \{ p \in \Delta_n \ | \ \text{supp(p)} \subset A \}$

I have two things to prove:

$1) F \text{ is a face } \iff \exists A \subset I_n : F = F(A)$

Here, $\Leftarrow$ is no problem. When it comes to $\Rightarrow$, I've been thinking about indirect proof. That is, let's assume that $F$ is a face but for every $A \subset I_n, \ F(A) \neq F$. But then, if we take $A$ to be a subset of canonic basis of $\mathbb{R}^n$ we get a contradiction. Is that correct?

$2) \text{conv} (\{ e_i, i \in A \} ) = F(A)$

here $e_i$ are elements of the canonical basis of $\mathbb{R}^n$

Now, when it comes to $\subset, \ F(A)$ is a convex set and evidently $\{ e_i \ , \ i \in A \} \subset F(A)$ so $F(A)$ is one of the convex sets containing $\{ e_i \ , \ i \in A \} $, so the interesection of those sets must be a subset of $F(A)$.

I have problems proving the other inclusion.

Could you help me with that?

Thank you

1

There are 1 best solutions below

4
On BEST ANSWER

It is probably easier to answer the second question before the first.

Answer to the second question.

The argument in the OP already shows that ${\textsf{conv}}(e_i;i\in A) \subseteq F(A)$. Conversely, suppose that $p\in F(A)$. Since $p\in \Delta_n$ we can write $(*) \ : \ p=(p_1,p_2,\ldots,p_n)$ with $\sum_{i=1}^{n}p_i=1$. By definition of $F(A)$, we have $p_i=0$ for any $i\not\in A$, so that $(*)$ reduces to $p=\sum_{i\in A}p_ie_i$ with $\sum_{i\in A}p_i=1$ and this is clearly in ${\textsf{conv}}(e_i;i\in A)$.

Answer to the first question.

Let $\cal F$ be a face of $\Delta_n$. By induction on $r$, we have that if $x_1,x_2,\ldots,x_r \in \Delta_n$ and $\lambda_1,\lambda_2,\ldots, \lambda_r \in{\mathbb R}_{+}$ with $\sum_{k=1}^r \lambda_k=1$ and $\sum_{k=1}^r \lambda_k x_k \in {\cal F}$, that all the $x_k$ are in $\cal F$.

It follows that for any $p\in {\cal F}$ and $i\in{\textsf{supp}}(p)$, we have $e_i\in {\cal F}$. Now, let us put $A=\bigcup_{p\in {\cal F}} {\textsf{supp}}(p)$. By what we have just shown, we have $e_i\in {\cal F}$ for every $i\in A$. If $p\in F(A)$, then $p=\sum_{i\in A}p_ie_i$ with $\sum_{i\in A}p_i=1$ by the second question above, we see that $p\in {\cal F}$ because $\cal F$ is convex. This shows the inclusion $F(A) \subseteq {\cal F}$. The reverse inclusion is clear by definition of $A$, so in the end we have ${\cal F}=F(A)$ as wished.