If $p \notin \text{Conv}(A)$, $q \notin \text{Conv}(A)$, $p \in \text{Conv}(A \cup \{ q \})$, $q \in Conv(A \cup \{p\})$, then $p = q$

88 Views Asked by At

$A \subset \mathbb{R}^n$, $P, Q \in \mathbb{R}^n$, $Conv$ is the convex hull operator, defined as

$$ Conv(\{ a_1, a_2, ..., a_n \}) = \left \{ \ \Sigma \ a_i \lambda_i \mid \lambda_i \in \mathbb{R}, \Sigma \ \lambda_i = 1, \lambda_i \geq 0 \right \} $$

The assertion seems reasonable enough, and I got this far:

Let $A = \{a_1, a_2, \ldots, a_n \}$

$$ p = \sum a_i \lambda_i + (1 - \lambda) q $$

Where $\lambda = \sum \lambda_i$, and $\lambda > 0$, since $p \notin \text{Conv}(A)$.

Similarly,

$$ q = \sum a_i \delta_i + (1 - \delta) p $$

where $\delta = \sum \delta_i$, $\delta > 0$.

Now, I considered $p + q$:

$$ p + q = \sum (\lambda_i + \delta_i) a_i + (1 - \lambda)q + (1 - \delta) p \\ \lambda p + \delta q = \sum(\lambda_i + \delta_i) a_i \\ \frac{\lambda p + \delta q}{\lambda + \delta} = \sum\frac{(\lambda_i + \delta_i)}{\lambda + \delta} a_i $$

This tells us that the point that divides the line segment $p q$ in the ratio $\lambda \ : \delta$ lies in the convex hull of $A$, as $\sum\frac{(\lambda_i + \delta_i)}{\lambda + \delta} = 1$, and $\frac{(\lambda_i + \delta_i)}{\lambda + \delta} \geq 0$, and is well defined since $\lambda > 0, \delta > 0$.

But, now what? I was hoping to show that such a point must converge onto $p$ or $q$, but I've been having no such luck in proving this. I wanted to write $\lambda : \delta = k : 1$ and then proceed to solve, but it seemed far too messy for such a cute problem.

1

There are 1 best solutions below

2
On BEST ANSWER

Since $p \notin Conv(A)$ , $$ext [Conv(A \cup \{p\})] = ext(A) \cup \{p\}$$similarly$$ext [Conv(A \cup \{q\})] = ext(A) \cup\{q\}$$

now taking into account the assumptions shows that$$Conv(A \cup \{p\})= Conv(A \cup\{q\}) $$ Therefore $$ext(A) \cup \{p\} = ext(A) \cup \{q\}$$ which implies $p=q$ (since $p,q \notin ext(A) ).$