[proofplan] Start with any finite convex representation of $x$ by points of $A$. If the representation uses more than $n+1$ points with positive coefficient, those points are affinely dependent because the lifted vectors $(b_j,1)$ lie in $\mathbb{R}^{n+1}$. An affine dependence lets us perturb the coefficients while preserving both their sum and the represented point, and choosing the largest safe perturbation eliminates at least one positive coefficient. Repeating this finite reduction gives a convex representation using at most $n+1$ points, which is then padded with zero coefficients if necessary. [/proofplan] [step:Choose a finite convex representation with positive coefficients] Since $x \in \operatorname{conv}(A)$, by the definition of convex hull there exist an integer $m \in \mathbb{N}$, points $b_1,\dots,b_m \in A$, and coefficients $\alpha_1,\dots,\alpha_m \in [0,\infty)$ such that \begin{align*} \sum_{j=1}^{m} \alpha_j = 1 \end{align*} and \begin{align*} x = \sum_{j=1}^{m} \alpha_j b_j. \end{align*} Discard every index $j$ for which $\alpha_j = 0$. The remaining list is nonempty because the sum of the coefficients is $1$. Relabeling the remaining points and coefficients, we may assume \begin{align*} \alpha_j > 0 \quad \text{for every } j \in \{1,\dots,m\}. \end{align*} [guided] Because $x$ belongs to the convex hull of $A$, it is already known to be a finite convex combination of points of $A$. Thus there are an integer $m \in \mathbb{N}$, points $b_1,\dots,b_m \in A$, and coefficients $\alpha_1,\dots,\alpha_m \in [0,\infty)$ satisfying \begin{align*} \sum_{j=1}^{m} \alpha_j = 1 \end{align*} and \begin{align*} x = \sum_{j=1}^{m} \alpha_j b_j. \end{align*} The reduction argument only needs to track points that actually contribute to the convex combination. If $\alpha_j = 0$, then the term $\alpha_j b_j$ contributes the zero vector in $\mathbb{R}^n$, so removing that term preserves both the represented point and the condition that the coefficients sum to $1$. Since the total sum of the coefficients is $1$, not all coefficients are zero. After discarding the zero coefficients and relabeling, we may assume \begin{align*} \alpha_j > 0 \quad \text{for every } j \in \{1,\dots,m\}. \end{align*} [/guided] [/step] [step:Produce an affine dependence whenever more than $n+1$ points remain] Assume $m > n+1$. For each $j \in \{1,\dots,m\}$, define the lifted vector $v_j \in \mathbb{R}^{n+1}$ by \begin{align*} v_j = (b_j,1). \end{align*} The [vector space](/page/Vector%20Space) $\mathbb{R}^{n+1}$ has dimension $n+1$, and the list $v_1,\dots,v_m$ has length $m > n+1$, so it is linearly dependent. Hence there exist [real numbers](/page/Real%20Numbers) $\beta_1,\dots,\beta_m$, not all zero, such that \begin{align*} \sum_{j=1}^{m} \beta_j v_j = 0. \end{align*} Equating the first $n$ coordinates and the last coordinate gives \begin{align*} \sum_{j=1}^{m} \beta_j b_j = 0 \end{align*} and \begin{align*} \sum_{j=1}^{m} \beta_j = 0. \end{align*} Because the coefficients $\beta_j$ are not all zero and have sum $0$, at least one $\beta_j$ is positive and at least one $\beta_j$ is negative. [guided] Suppose the current representation uses too many points, meaning $m > n+1$. The right way to detect redundancy is to convert affine dependence into ordinary linear dependence. For each $j \in \{1,\dots,m\}$, define the lifted vector $v_j \in \mathbb{R}^{n+1}$ by \begin{align*} v_j = (b_j,1). \end{align*} There are $m$ vectors $v_1,\dots,v_m$ in the vector space $\mathbb{R}^{n+1}$, whose dimension is $n+1$. Since $m > n+1$, these vectors are linearly dependent. Therefore there exist real numbers $\beta_1,\dots,\beta_m$, not all zero, such that \begin{align*} \sum_{j=1}^{m} \beta_j v_j = 0. \end{align*} Now expand this equality using the definition $v_j = (b_j,1)$. Equality in $\mathbb{R}^{n+1}$ means equality in the first $n$ coordinates and in the last coordinate. The first $n$ coordinates give \begin{align*} \sum_{j=1}^{m} \beta_j b_j = 0, \end{align*} while the last coordinate gives \begin{align*} \sum_{j=1}^{m} \beta_j = 0. \end{align*} This is precisely an affine dependence among the points $b_1,\dots,b_m$. Since the numbers $\beta_j$ are not all zero but their sum is zero, they cannot all be nonnegative and cannot all be nonpositive. Thus at least one $\beta_j$ is positive and at least one $\beta_j$ is negative. [/guided] [/step] [step:Perturb the coefficients until one coefficient vanishes] Define the nonempty index set \begin{align*} I_+ = \{j \in \{1,\dots,m\} : \beta_j > 0\}. \end{align*} For $j \in I_+$, the quotient $\alpha_j/\beta_j$ is positive. Define \begin{align*} t_* = \min_{j \in I_+} \frac{\alpha_j}{\beta_j}. \end{align*} For each $j \in \{1,\dots,m\}$, define a new coefficient \begin{align*} \alpha_j' = \alpha_j - t_* \beta_j. \end{align*} If $\beta_j > 0$, then the definition of $t_*$ gives $t_* \le \alpha_j/\beta_j$, so $\alpha_j' \ge 0$. If $\beta_j \le 0$, then $\alpha_j' = \alpha_j + t_*|\beta_j| \ge 0$. Hence every $\alpha_j'$ is nonnegative. The sum of the new coefficients is still $1$: \begin{align*} \sum_{j=1}^{m} \alpha_j' &= \sum_{j=1}^{m} \alpha_j - t_* \sum_{j=1}^{m} \beta_j \\ &= 1 - t_* \cdot 0 \\ &= 1. \end{align*} The represented point is still $x$: \begin{align*} \sum_{j=1}^{m} \alpha_j' b_j &= \sum_{j=1}^{m} \alpha_j b_j - t_* \sum_{j=1}^{m} \beta_j b_j \\ &= x - t_* \cdot 0 \\ &= x. \end{align*} By the definition of the minimum, there is an index $j_* \in I_+$ such that \begin{align*} t_* = \frac{\alpha_{j_*}}{\beta_{j_*}}. \end{align*} For this index, \begin{align*} \alpha_{j_*}' = \alpha_{j_*} - t_* \beta_{j_*} = 0. \end{align*} Thus the new convex representation has at least one zero coefficient. [guided] The affine dependence gives a direction in coefficient space along which the convex combination does not move. We now choose how far to move in that direction. Define the set of indices with positive dependence coefficient by \begin{align*} I_+ = \{j \in \{1,\dots,m\} : \beta_j > 0\}. \end{align*} This set is nonempty because the numbers $\beta_j$ are not all zero and have sum $0$. For every $j \in I_+$, both $\alpha_j$ and $\beta_j$ are positive, so the quotient $\alpha_j/\beta_j$ is positive. Define \begin{align*} t_* = \min_{j \in I_+} \frac{\alpha_j}{\beta_j}. \end{align*} The minimum exists because $I_+$ is a finite nonempty set. For each $j \in \{1,\dots,m\}$, define \begin{align*} \alpha_j' = \alpha_j - t_* \beta_j. \end{align*} We check first that these are valid convex coefficients. If $\beta_j > 0$, then $j \in I_+$, and the definition of $t_*$ gives \begin{align*} t_* \le \frac{\alpha_j}{\beta_j}. \end{align*} Multiplying by the positive number $\beta_j$ gives $t_*\beta_j \le \alpha_j$, hence $\alpha_j' \ge 0$. If $\beta_j \le 0$, then \begin{align*} \alpha_j' = \alpha_j - t_*\beta_j = \alpha_j + t_*|\beta_j| \ge 0. \end{align*} So all new coefficients are nonnegative. Next we verify that the new coefficients still sum to $1$. Using the affine-dependence identity $\sum_{j=1}^m \beta_j = 0$, we compute \begin{align*} \sum_{j=1}^{m} \alpha_j' &= \sum_{j=1}^{m}(\alpha_j - t_*\beta_j) \\ &= \sum_{j=1}^{m} \alpha_j - t_* \sum_{j=1}^{m} \beta_j \\ &= 1 - t_* \cdot 0 \\ &= 1. \end{align*} Now we verify that the represented point is unchanged. Using the affine-dependence identity $\sum_{j=1}^m \beta_j b_j = 0$, we compute \begin{align*} \sum_{j=1}^{m} \alpha_j' b_j &= \sum_{j=1}^{m}(\alpha_j - t_*\beta_j)b_j \\ &= \sum_{j=1}^{m} \alpha_j b_j - t_* \sum_{j=1}^{m} \beta_j b_j \\ &= x - t_* \cdot 0 \\ &= x. \end{align*} Finally, the choice of $t_*$ guarantees that at least one coefficient becomes exactly zero. Since $I_+$ is finite and nonempty, there exists $j_* \in I_+$ such that \begin{align*} t_* = \frac{\alpha_{j_*}}{\beta_{j_*}}. \end{align*} Therefore \begin{align*} \alpha_{j_*}' = \alpha_{j_*} - t_*\beta_{j_*} = 0. \end{align*} Thus the perturbation preserves the convex combination and removes at least one active point. [/guided] [/step] [step:Iterate the reduction until at most $n+1$ points remain] After the preceding step, discard all indices $j$ for which $\alpha_j' = 0$. The remaining coefficients are positive, still sum to $1$, and still represent $x$ as a convex combination of points of $A$. If the number of remaining points is greater than $n+1$, repeat the same reduction. Each reduction decreases the number of positive coefficients by at least one. Since the initial number of positive coefficients is finite, after finitely many reductions we obtain an integer $r \in \{1,\dots,n+1\}$, points $c_1,\dots,c_r \in A$, and coefficients $\mu_1,\dots,\mu_r \in (0,\infty)$ such that \begin{align*} \sum_{k=1}^{r} \mu_k = 1 \end{align*} and \begin{align*} x = \sum_{k=1}^{r} \mu_k c_k. \end{align*} [/step] [step:Pad the representation to exactly $n+1$ coefficients] For $i \in \{1,\dots,n+1\}$, define points $a_i \in A$ and coefficients $\lambda_i \in [0,\infty)$ as follows. For $1 \le i \le r$, set \begin{align*} a_i = c_i, \qquad \lambda_i = \mu_i. \end{align*} For $r < i \le n+1$, set \begin{align*} a_i = c_1, \qquad \lambda_i = 0. \end{align*} Then $a_1,\dots,a_{n+1} \in A$, all coefficients $\lambda_i$ are nonnegative, and \begin{align*} \sum_{i=1}^{n+1} \lambda_i &= \sum_{k=1}^{r} \mu_k \\ &= 1. \end{align*} Moreover, \begin{align*} \sum_{i=1}^{n+1} \lambda_i a_i &= \sum_{k=1}^{r} \mu_k c_k \\ &= x. \end{align*} This proves the required representation by at most $n+1$ points, written with exactly $n+1$ listed points and allowing zero coefficients. [/step]