Simplex
Introduction
Simplex is known as the simplest polytope possible, such as point, line segment, triangle, tetrahedron, pentachoron, hexateron, etc., in any given dimensional spaces.
In this blog post, I would like to quickly discuss the mathematical definition of simplex and some of its simplest properties.
Simplex
Formally, a $k$-simplex is the set of points
$$
C = \left\{ \theta_{0}u_{0} + \theta_{1}u_{1} + \cdots + \theta_{k}u_{k} \right\}
$$
where $\sum_{i=0}^{k}\theta_{i}=1$, $\theta_{i} \geq 0$ for $0 \leq i \leq k$, and the $k + 1$ points $\{u_{0}, u_{1}, \cdots, u_{k}\}$ are affinely independent, i.e., the $k$ vectors $\{u_{1} - u_{0}, \cdots, u_{k} - u_{0}\}$ are linearly independent. Note that $u_{i}$ can be an $n$-dimensional point where $n \geq k$.
Therefore,
- A 0-simplex is a point which is the simplest polytope in the 0-dimensional space.
- A 1-simplex is a line segment which is the simplest polytope in the 1-dimensional space.
- A 2-simplex is a triangle which is the simplest polytope in the 2-dimensional space.
- A 3-simplex is a tetrahedron which is the simplest polytope in the 3-dimensional space.
A standard $k$-simplex is a $k$-simplex whose $k + 1$ affinely independent points $u_{0}$, $u_{1}$, $\cdots$, $u_{k}$ are the $k+1$ standard unit vectors in $\mathbb{R}^{k+1}$. For example, when $k = 2$, the standard 2-simplex is the equilateral triangle with vertices $(1, 0, 0)$, $(0, 1, 0)$ and $(0, 0, 1)$ in $\mathbb{R}^{3}$.
Simplex and Pascal’s Triangle
It can be proved by contradiction that if $k + 1$ points $\{u_{0}, u_{1}, \cdots, u_{k}\}$ are affinely independent, any subset of the $k + 1$ points are also affinely independent. This naturally means a $k$-simplex consists of the $\tbinom {k+1}{1}$ 0-simplex, $\tbinom {k+1}{2}$ 1-simplex, …, $\tbinom {k+1}{k+1}$ $k$-simplex that uses the affine basis from $\{u_{0}, u_{1}, \cdots, u_{k}\}$. Those simplexes are called faces formally. Therefore, the total number of faces a $k$-simplex has is
$$
\begin{align}
\tbinom {k+1}{1} + \tbinom {k+1}{2} + \cdots + \tbinom {k+1}{k+1}
&= \left( \tbinom {k+1}{0} + \tbinom {k+1}{1} + \tbinom {k+1}{2} + \cdots + \tbinom {k+1}{k+1} \right) - \tbinom {k+1}{0} \\
&= 2^{k+1} - 1 \\
\end{align}
$$
Because the face numbers follows the binomial coefficient pattern, the face numbers also follows the Pascal’s triangle, without the left diagonal which are the $\tbinom {k+1}{0}$s.
Simplex and Optimization
Simplex is naturally the solution pool for some constrained linear programing optimization problems.
For example, the top-$k$ problem, which is finding the indices of the largest or smallest $k$ items in an array, is within this scope. Normally, there are two common approaches algorithmically to solve this problem. The first approach is the most straightforward one but asymptotically slower. We could just sort the array, track the indices during the sorting, and take the top-$k$ item indices after sorting. This would take $O(N\log N)$ in the worst case. The second approach is to employ some data structure, such as max-heap or min-heap, and this would take $O(N\log k)$ in the worst case. But either way, the solution is quite algorithmic.
The top-$k$ problem, however, can also be formulated as a balanced transportation linear programming problem. Given an array of values $\{v_{0}, v_{1}, \cdots, v_{n}\}$, the balanced transportation cost matrix, in which the center values are the unit transportation cost or income, can be defined as follows.
| Top-$k$ | Non-Top-$k$ | Supply | |
|---|---|---|---|
| $v_0$ | $v_0$ | $v_0 - 1$ | $\frac{1}{k}$ |
| $v_1$ | $v_1$ | $v_1 - 1$ | $\frac{1}{k}$ |
| $v_2$ | $v_2$ | $v_2 - 1$ | $\frac{1}{k}$ |
| $v_3$ | $v_3$ | $v_3 - 1$ | $\frac{1}{k}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\frac{1}{k}$ |
| $v_{n-1}$ | $v_{n-1}$ | $v_{n-1} - 1$ | $\frac{1}{k}$ |
| Demand | $1$ | $\frac{n}{k} - 1$ |
The solution of problem, i.e., the amount of supply going to the top-$k$ from different suppliers, is $(x_{0}, x_{1}, \cdots, x_{n-1})$. This solution is actually on a $(n-1)$-simplex
$$
C = \left\{ x_{0}u_{0} + x_{1}u_{1} + \cdots + x_{n-1}u_{n-1} \right\}
$$
where $\sum_{i=0}^{n-1}x_{i}=1$, $x_{i} \geq 0$ for $0 \leq i \leq n-1$, and the $n$ points $\{u_{0}, u_{1}, \cdots, u_{n-1}\}$ are the standard affine basis in $\mathbb{R}^n$ whose $u_{0} = (1, 0, 0, \cdots, 0)$, $u_{1} = (0, 1, 0, \cdots, 0)$, $u_{2} = (0, 0, 1, \cdots, 0)$, $\cdots$, $u_{n-1} = (0, 0, 0, \cdots, 1)$. Also note that not all the points on this $(n-1)$-simplex are the solutions to this problem.