How Do I Show $A$ has a Unique Radon Point?

Question

The Question to solve:

For a set $A\subseteq \mathbb{R}^d$ and a point $x\in \mathbb{R}^d$, we say that $x$ is a Radon point of $A$ if $A$ can be partitioned into $A = A_1\cup A_2$ with $A_1\cap A_2 = \emptyset$ so that $x\in conv(A_1)\cap conv(A_2)$. Show that if $A$ is a set of $d+2$ points in general position, then $A$ has a unique Radon point.

I know Radon theorem says if $|A|\geq d+2$, we will have $conv(A_1)\cap conv(A_2)\neq \emptyset$. However, I don’t know how to show that if $|A|=d+2$, and the points are in general position, then $A$ has a unique $x\in conv(A_1)\in conv(A_2)$.

Your help would be really appreciated.

Answer 1

Let $A = \left\{\boldsymbol{a}_1,\ldots,\boldsymbol{a}_{d+2}\right\}$. If $\boldsymbol{x}$ and $\boldsymbol{y}$ are Radon points then you can find two sets of indices $I$, $J$ and $\alpha, \beta\in \mathbb R_{\ge 0}^{d+2}$ such that \begin{align} \boldsymbol{x} &= \sum_{i\in I} \alpha_i\boldsymbol{a}_i = \sum_{i\not\in I} \alpha_i \boldsymbol{a}_i\\ \boldsymbol{y} &= \sum_{i\in J} \beta_i\boldsymbol{a}_i = \sum_{i\not\in J} \beta_i \boldsymbol{a}_i\\ 1 &= \sum_{i\in I} \alpha_i = \sum_{i\not\in I} \alpha_i\\ 1 &= \sum_{i\in J} \beta_i = \sum_{i\not\in I} \beta_i. \end{align}

Let $u_i = \begin{cases} \alpha_i & \text{if $i\in I$}\\ -\alpha_i & \text{if $i\not\in I$} \end{cases}$ and $v_i = \begin{cases} \beta_i & \text{if $i\in J$}\\ -\beta_i & \text{if $i\not\in J$} \end{cases}$ such that:

\begin{align} \sum_{i=1}^{d+2} u_i &= \sum_{i=1}^{d+2} v_i = 0\\ \sum_{i=1}^{d+2} u_i\boldsymbol{a}_i &= \sum_{i=1}^{d+2} v_i\boldsymbol{a}_i = 0 \end{align}

Since the points are in general position $\boldsymbol{a}_1, \ldots, \boldsymbol{a}_{d+1}$ are affinely independent. So $u_{d+2}\neq 0$ and $v_{d+2}\neq 0$. Now let $\lambda = \frac{u_{d+2}}{v_{d+2}}$ then,

\begin{align} \sum_{i=1}^{d+1} \left(u_i - \lambda v_i\right) &= -u_{d+2} - \lambda \left(-v_{d+2}\right) = -u_{d+2} + \lambda v_{d+2} = 0\\ \sum_{i=1}^{d+1} \left(u_i - \lambda v_i\right)\boldsymbol{a}_i &= -u_{d+2}\boldsymbol{a}_{d+2} - \lambda \left(-v_{d+2}\right)\boldsymbol{a}_{d+2} = \left(-u_{d+2} + \lambda v_{d+2}\right)\boldsymbol{a}_{d+2} = 0 \end{align}

Again since $\boldsymbol{a}_1, \ldots, \boldsymbol{a}_{d+1}$ are affinely independent, $u_i - \lambda v_i = 0$ for $i\le d+1$. So $u = \lambda v$.

• If $\lambda < 0$, let $i\in I$, $\alpha_i > 0$ then clearly $v_i = \frac1\lambda u_i = \frac1\lambda \alpha_i < 0$ so $i\not\in J$ and $\beta_i>0$. This proves that, $$\left\{i \in I:\alpha_i > 0\right\} \subset \left\{i\not\in J: \beta_i>0\right\}.$$ We can prove the inverse similarly. This means that: $$\left\{i \in I:\alpha_i > 0\right\} = \left\{i\not\in J: \beta_i>0\right\}.$$ $$1 = \sum_{i\in I:\, \alpha_i>0} \alpha_i = \sum_{i\not\in J:\, \beta_i>0} \lambda \left(-\beta_i\right) = -\lambda$$ so $\lambda = -1$. On the other hand:

$$\boldsymbol{x} = \sum_{i\in I:\, \alpha_i>0} \alpha_i\boldsymbol{a}_i = \sum_{i\not\in J:\, \beta_i>0} \lambda \left(-\beta_i\right)\boldsymbol{a}_i = -\lambda \sum_{i\not\in J:\, \beta_i>0} \beta_i\boldsymbol{a}_i = \boldsymbol{y}$$

a similar proof can be done for the case where $\lambda > 0$.

Answer 2

Put $X=\{(x_a)_{a\in A}\in\mathbb R^A:\sum_{i=1}^{d+2} x_a=0\}$. Then $X$ is a linear space of dimension $d+1$. Define a linear map $f:X\to \mathbb R^d$ putting $f((x_a)_{a\in A})=\sum_{a\in A} x_aa$ for each $(x_a)_{a\in A}\in X$. Then the image $f(X)$ is the affine hull of the set $A$. Since the latter has size $d+2$ and is in general position, $f(X)=\mathbb R^d$. Then the kernel $K$ of the map $f$ has dimension $1$. Pick any nonzero vector $y=(y_a)_{a\in A}$ from $K$. Multiplying $y$ by a constant, we can suppose that the sum of its positive components is $1$. Pick any element $b\in A$ such that $y_b>0$. Now let $r$ be any Radon point of $A$ and $A_1\cup A_2$ be a partition of $A$ into two disjoint sets such that $A\ni b$ and $x\in \operatorname{conv} A_1\cap \operatorname{conv} A_2$. Therefore there exists a vector $(x_a)_{a\in A}\in\mathbb R^A$ such that $x_a\ge 0$ for each $a\in A_1$, $\sum_{a\in A_1} x_a=1$, $r=\sum_{a\in A_1} x_aa$, $x_a\le 0$ for each $a\in A_2$, $\sum_{a\in A_2} x_a=-1$, and $-r=\sum_{a\in A_2} x_aa$. Thus $0=\sum_{a\in A} ax_a=f((x_a)_{a\in A})$, that is $(x_a)_{a\in A}\in K$. Since the space $K$ is one dimensional, the sum of the positive components is $1$ both for $(y_a)_{a\in A}$ and $(x_a)_{a\in A}$, $y_b>0$, and $x_b\ge 0$, we see that $(y_a)_{a\in A}=(x_a)_{a\in A}$, therefore the vector $y$ determines the point $r$ uniquely.