How many Corners of Simplex Intersected by Hyperplane?

194 Views Asked by At

There are $K$ linearly independent points on a $N-1$ dimensional simplex: $$x^{1}, \ldots, x^{K} \in \Delta^{N-1}$$ $$x^{k} = (x^{k}_{1}, \ldots, x^{k}_{N})$$ I would like to prove their exists $K$ "corners" of the span of $x^{1}, \ldots, x^{K}$ on the simplex: $$y^{1}, \ldots, y^{K} \in \Delta^{N-1}$$

$$\mathcal{A} = \text{span}\left(\left\{ x^{1}, \ldots, x^{K} \right\}\right) \cap \Delta^{N-1}$$

Such that every point in $\mathcal{A}$ is a convex combination of $y^{1}, \ldots, y^{K}$.


Background: I've been trying to solve this question (sorry, the notation doesn't line up perfectly). The idea is that $x^{k}$ is one of $K$ independent rows of their matrix, and $y^{k}$ is the probability distribution for a new random variable $X^{k}$ independent of $Y$. We can then construct a new random variable $\omega$ dependent on $Y$ with support $\{1, \ldots, K\}$ such that:

$$X = \sum_{k=1}^{K} X^{k} \mathbb{1}_{\omega=k}$$

by letting the probability distribution of $\omega | Y$ be the appropriate convex weights of the $y^{1}, \ldots, y^{k}$. I think the variance of $\omega$ also gives a good continuous measure for the original question.


Attempt: I was trying to come up with an iterative construction where I first include any basis vectors in $\mathcal{A}$, then any linear combination of two basis vectors in $\mathcal{A}$ not spanned by the vectors I've already included, "and so on" until I've constructed $y^{1}, \ldots, y^{K}$. I don't know how to continue in an orderly way that provably constructs the $K$ points (or if this is the simplest approach).

1

There are 1 best solutions below

5
On BEST ANSWER

You are asking for a proof that (among other things) a planar slice through a solid tetrahedron in three space must be a triangle.

The following is an example where this fails:

Let $K=3, N=4$, let the $K$ linearly independent points in $\mathbb R^4$ be

$$x^1=(1/2,0,1/2,0)\\x^2=(0,1/2,1/2,0)\\x^3=(0,1/2,0,1/2)$$ and let $$x^4=(1/2,0,0,1/2).$$ Let $\mathcal A=\operatorname{span}(\{x^1,x^2,x^3\})\cap \Delta^3$. Note that $x^4=x^1-x^2+x^3\in \operatorname{span}(\{x^1,x^2,x^3\})$, that $x^4\in\Delta^3$, and that $\mathcal A$ is the convex hull of $\{x^1,x^2,x^3,x^4\}$, and that $\mathcal A$ has the four $x^j$ as its extreme points, the sought after "corners".