Editing Simplex (section)

== Standard simplex ==
[[Image:2D-simplex.svg|thumb|The standard {{nowrap|2-simplex}} in {{math|'''R'''<sup>3</sup>}}]]
The '''standard {{mvar|n}}-simplex''' (or '''unit {{mvar|n}}-simplex''') is the subset of {{math|'''R'''<sup>''n''+1</sup>}} given by
: <math>\Delta^n = \left\{(t_0,\dots,t_n)\in\mathbf{R}^{n+1} ~\Bigg|~ \sum_{i = 0}^n t_i = 1 \text{ and } t_i \ge 0 \text{ for } i = 0, \ldots, n\right\}</math>.

The simplex {{math|Δ<sup>''n''</sup>}} lies in the [[affine hyperplane]] obtained by removing the restriction {{math|''t''<sub>''i''</sub> ≥ 0}} in the above definition.

The {{math|''n'' + 1}} vertices of the standard {{mvar|n}}-simplex are the points {{math|''e''<sub>''i''</sub> ∈ '''R'''<sup>''n''+1</sup>}}, where
: {{math|1=''e''<sub>0</sub> = (1, 0, 0, ..., 0),}}
: {{math|1=''e''<sub>1</sub> = (0, 1, 0, ..., 0),}}
: ⋮
: {{math|1=''e''<sub>''n''</sub> = (0, 0, 0, ..., 1)}}.

A ''standard simplex'' is an example of a [[0/1-polytope]], with all coordinates as 0 or 1. It can also be seen one [[facet (geometry)|facet]] of a regular {{math|(''n'' + 1)}}-[[orthoplex]].

There is a canonical map from the standard {{mvar|n}}-simplex to an arbitrary {{mvar|n}}-simplex with vertices ({{math|''v''<sub>0</sub>}}, ..., {{math|''v''<sub>''n''</sub>}}) given by
: <math>(t_0,\ldots,t_n) \mapsto \sum_{i = 0}^n t_i v_i</math>
The coefficients {{math|''t''<sub>''i''</sub>}} are called the [[barycentric coordinates (mathematics)|barycentric coordinates]] of a point in the {{mvar|n}}-simplex. Such a general simplex is often called an '''affine {{mvar|n}}-simplex''', to emphasize that the canonical map is an [[affine transformation]]. It is also sometimes called an '''oriented affine {{mvar|n}}-simplex''' to emphasize that the canonical map may be [[Orientation (vector space)|orientation preserving]] or reversing.

More generally, there is a canonical map from the standard <math>(n-1)</math>-simplex (with {{mvar|n}} vertices) onto any [[polytope]] with {{mvar|n}} vertices, given by the same equation (modifying indexing):
: <math>(t_1,\ldots,t_n) \mapsto \sum_{i = 1}^n t_i v_i</math>
These are known as [[generalized barycentric coordinates]], and express every polytope as the ''image'' of a simplex: <math>\Delta^{n-1} \twoheadrightarrow P.</math>

A commonly used function from {{math|'''R'''<sup>''n''</sup>}} to the interior of the standard <math>(n-1)</math>-simplex is the [[softmax function]], or normalized exponential function; this generalizes the [[standard logistic function]].

=== Examples ===
* Δ<sup>0</sup> is the point {{math|1}} in {{math|'''R'''<sup>1</sup>}}.
* Δ<sup>1</sup> is the line segment joining {{math|(1, 0)}} and {{math|(0, 1)}} in {{math|'''R'''<sup>2</sup>}}.
* Δ<sup>2</sup> is the [[equilateral triangle]] with vertices {{math|(1, 0, 0)}}, {{math|(0, 1, 0)}} and {{math|(0, 0, 1)}} in {{math|'''R'''<sup>3</sup>}}.
* Δ<sup>3</sup> is the [[regular tetrahedron]] with vertices {{math|(1, 0, 0, 0)}}, {{math|(0, 1, 0, 0)}}, {{math|(0, 0, 1, 0)}} and {{math|(0, 0, 0, 1)}} in {{math|'''R'''<sup>4</sup>}}.
* Δ<sup>4</sup> is the regular [[5-cell]] with vertices {{math|(1, 0, 0, 0, 0)}}, {{math|(0, 1, 0, 0, 0)}}, {{math|(0, 0, 1, 0, 0)}}, {{math|(0, 0, 0, 1, 0)}} and {{math|(0, 0, 0, 0, 1)}} in {{math|'''R'''<sup>5</sup>}}.

=== Increasing coordinates ===
An alternative coordinate system is given by taking the [[indefinite sum]]:
: <math>
\begin{align}
s_0 &= 0\\
s_1 &= s_0 + t_0 = t_0\\
s_2 &= s_1 + t_1 = t_0 + t_1\\
s_3 &= s_2 + t_2 = t_0 + t_1 + t_2\\
&\;\;\vdots\\
s_n &= s_{n-1} + t_{n-1} = t_0 + t_1 + \cdots + t_{n-1}\\
s_{n+1} &= s_n + t_n = t_0 + t_1 + \cdots + t_n = 1
\end{align}
</math>
This yields the alternative presentation by ''order,'' namely as nondecreasing {{mvar|n}}-tuples between 0 and 1:
: <math>\Delta_*^n = \left\{(s_1,\ldots,s_n)\in\mathbf{R}^n\mid 0 = s_0 \leq s_1 \leq s_2 \leq \dots \leq s_n \leq s_{n+1} = 1 \right\}. </math>
Geometrically, this is an {{mvar|n}}-dimensional subset of <math>\mathbf{R}^n</math> (maximal dimension, codimension 0) rather than of <math>\mathbf{R}^{n+1}</math> (codimension 1). The facets, which on the standard simplex correspond to one coordinate vanishing, <math>t_i=0,</math> here correspond to successive coordinates being equal, <math>s_i=s_{i+1},</math> while the [[Interior (topology)|interior]] corresponds to the inequalities becoming ''strict'' (increasing sequences).

A key distinction between these presentations is the behavior under permuting coordinates – the standard simplex is stabilized by permuting coordinates, while permuting elements of the "ordered simplex" do not leave it invariant, as permuting an ordered sequence generally makes it unordered. Indeed, the ordered simplex is a (closed) [[fundamental domain]] for the [[group action|action]] of the [[symmetric group]] on the {{mvar|n}}-cube, meaning that the orbit of the ordered simplex under the {{mvar|n}}! elements of the symmetric group divides the {{mvar|n}}-cube into <math>n!</math> mostly disjoint simplices (disjoint except for boundaries), showing that this simplex has volume {{math|1/''n''!}}. Alternatively, the volume can be computed by an iterated integral, whose successive integrands are 1, {{mvar|x}}, {{math|''x''<sup>2</sup>/2}}, {{math|''x''<sup>3</sup>/3!}}, ..., {{math|''x''<sup>''n''</sup>/''n''!}}.

A further property of this presentation is that it uses the order but not addition, and thus can be defined in any dimension over any ordered set, and for example can be used to define an infinite-dimensional simplex without issues of convergence of sums.

=== Projection onto the standard simplex ===
Especially in numerical applications of [[probability theory]], a [[Graphical projection|projection]] onto the standard simplex is of interest. Given&nbsp;{{tmath|p}}, possibly with coordinates that are negative or in excess of&nbsp;1, the closest point&nbsp;{{tmath|t}} on the simplex has coordinates 
: <math>t_i= \max\{p_i+\Delta\, ,0\},</math>
where&nbsp;<math>\Delta</math> is chosen such that&nbsp;<math display="inline">\sum_i\max\{p_i+\Delta\, ,0\}=1.</math>

<math>\Delta</math> can be easily calculated from sorting the coordinates of&nbsp;{{tmath|p}}.<ref>{{cite arXiv |eprint=1101.6081|title=Projection Onto A Simplex |author=Yunmei Chen |author2=Xiaojing Ye |year=2011 |class=math.OC }}</ref>
The sorting approach takes&nbsp;<math>O( n \log n)</math> complexity, which can be improved to&nbsp;{{math|O(''n'')}} complexity via [[Selection algorithm|median-finding]] algorithms.<ref>{{Cite journal | last1 = MacUlan | first1 = N. | last2 = De Paula | first2 = G. G. | doi = 10.1016/0167-6377(89)90064-3 | title = A linear-time median-finding algorithm for projecting a vector on the simplex of n | journal = Operations Research Letters | volume = 8 | issue = 4 | pages = 219 | year = 1989 }}</ref> Projecting onto the simplex is computationally similar to projecting onto the <math>\ell_1</math> ball. [[Integer programming|Also see Integer programming]].

=== Corner of cube ===
Finally, a simple variant is to replace "summing to 1" with "summing to at most 1"; this raises the dimension by 1, so to simplify notation, the indexing changes:
: <math>\Delta_c^n = \left\{(t_1,\ldots,t_n)\in\mathbf{R}^n ~\Bigg|~ \sum_{i = 1}^n t_i \leq 1 \text{ and } t_i \ge 0 \text{ for all } i \right\}.</math>
This yields an {{mvar|n}}-simplex as a corner of the {{mvar|n}}-cube, and is a standard orthogonal simplex. This is the simplex used in the [[simplex method]], which is based at the origin, and locally models a vertex on a polytope with {{mvar|n}} facets.