Convex geometry

Suppose \(M\) has two parallel subspaces \(L_1, L_2\). They must also be parallel, so \(\exists b\) s.t. \(L_2 = L_1 + b\). Since 0 \(\in L_2 \Rightarrow -b \in L_1 \Rightarrow b \in L_1\). Therefore, \(L_1 + b = L_2 \subset L_1\). Similarly, we can see that \(L_1 \subset L_2\), so \(L_1 = L_2\). Regarding the existance, for any \(x \in M\), define \(T = M - x\) which is a translation of \(M\) containing 0. Since \(T\) is affine, \(\forall y \in T, \lambda \in \mathbb{R} \Rightarrow \lambda y + (1-\lambda)0 = \lambda y \in T\), so \(T\) is closed under scalar multiplication. Furthermore, \(\forall y_1, y_2 \in T\), \(\frac{1}{2}(y_1 + y_2) = \frac{1}{2}y_1 + (1-\frac{1}{2}) y_2 \in T\), so \(y_1 + y_2 = 2(\frac{1}{2}(y_1+y_2)) \in T\) and \(T\) is closed under addition. Therefore, \(L = M-M\) is a unique vectorial subspace parallel to \(M\). ◻

Let \(x_1, x_2 \in M \Rightarrow \mathbf{B}x_1 = b, \mathbf{B} x_2 = b \Rightarrow \mathbf{B}(\lambda x_1 + (1- \lambda) x_2) = \lambda b + (1-\lambda)b = b \Rightarrow \lambda x_1 + (1-\lambda) x_2 \in M \ \forall \lambda \in \mathbb{R}\), so \(M\) is affine. In the converse direction, suppose \(M\) affine. Let \(L\) be its parallel subspace, and \(\{b_1, \ldots, b_m\}\) a basis of \(L^\top\). Then, \(L = (L^\top)^\top = \{ x \mid \langle s, b_i \rangle = 0\} = \{ x \mid \mathbf{B} x = 0\}\), where \(\mathbf{B}\) is the matrix having \(b_i\) as rows. Then, \(M = L + a = \{ x \mid \mathbf{B} x = \mathbf{B} a = b\}\). ◻

(\(\Rightarrow\)) Assume \(M\) affine, we will use induction. The base case is true by definition: \(x_1, x_2 \in M, \ \lambda_1 + \lambda_2 = 1 \Rightarrow \lambda_1 x_1 + \lambda_2 x_2 \in M\). Assume \(x_i \in M, \lambda_i \in \mathbb{R}, \ i = 1, \cdots, k\) s.t. \(\sum_i^k \lambda_i = 1\) implies that \(\sum_i^k \lambda_i x_i \in M\). Now, we consider \(x_i \in M, \lambda_i \in \mathbb{R}, \ i = 1, \cdots, k+1\) s.t. \(\sum_1^{k+1} \lambda_i = 1\). Then, \(\sum_i^{k+1} \lambda_i x_i = \sum_i^k \lambda_i x_i + \lambda_{k+1} x_{k+1} = (1-\lambda_{k+1})\sum_i^k \frac{\lambda_i}{1-\lambda_{k+1}}x_i + \lambda_{k+1} x_{k+1} = (1-\lambda_{k+1})z + \lambda_{k+1} x_{k+1}\). Note that \(z\) satisfies the induction hypothesis, so \(z \in M\) and therefore by definition \(\sum_i^{k+1} \lambda_i x_i \in M\). (\(\Leftarrow\)) Assume \(M\) is closed under affine sums. Then, the affine combination of any two elements of \(M\) must be in \(M\), which is precisely the definition of affine set. ◻

The set of all affine combinations of points in \(S\), call it \(X\), must be affine by [thm:aff_closed] and contains \(S\). Since \(\mathrm{aff}(S)\) is the smallest such set containing \(S\), \(\mathrm{aff}(S) \subset X\). On the other hand, all elements of \(S\) belong to \(\mathrm{aff}(S)\), so all their affine combinations must lie in \(\mathrm{aff}(S)\) by [thm:aff_closed] and \(X \subset \mathrm{aff}(S)\). ◻

Analogous to [thm:aff_representation]. ◻

Let \(C_i = \{ x \mid \langle x, b_i \rangle \leq \beta_i \}\). Then, \(C_i\) is a closed half-space (or \(\mathbb{R}^n\) or \(\emptyset\)), and thus convex. Then, \(C = \bigcap_{i \in I} C_i\) is also convex. ◻

Analogous to [thm:aff_closed]. ◻

Analogous to [cor:aff_hull_comb]. ◻

Analogous to [thm:inequalities-convex]. ◻

Assume \(K\) is a convex cone, and take \(x, y \in K\). By definition of cone, \(\frac{1}{2}x, \frac{1}{2}y \in K\), and by convexity \(\frac{1}{2}(x+y) = \frac{1}{2}x + (1-\frac{1}{2})y \in K\). Therefore, \(x+y = 2 \frac{1}{2}(x+1) \in K\), so it is closed under addition. On the other hand, assume \(K\) is closed under addition and positive scalar multiplication. Let \(x, y \in K, \ \lambda \in (0, 1)\), so \(\lambda x, (1-\lambda)y \in K\) and also \(\lambda x + (1-\lambda)y \in K\), thus \(K\) is a convex cone. ◻

\(K\) is a convex cone by [thm:cone_closed], and \(S \subset K\), so \(K\) is a convex cone containing \(S\). On the other hand, every convex cone containing \(S\) must also contain \(U\), so \(K\) is minimal. ◻

Consequence of the previous corollary. ◻

1. Let \(x \in \mathrm{cone}(S)\). Let \(m \in \mathbb{N}\) be the smallest such that \(x = \sum_{i=1}^{m} \alpha_i x_i, \ \alpha_i > 0, \ x_i \in S\).

   Suppose that \(x_i\) are linearly dependent, so \(\exists \lambda_1,\ldots,\lambda_m \in \mathbb{R}\) such that \(\sum_{i=1}^m \lambda_i x_i = 0\) and at least one \(\lambda_i > 0\) (we may always choose the coefficients such that at least one is positive). Consider \(\sum_{i=1}^m(\alpha_i - \bar \gamma \lambda_i) x_i\), with \(\bar \gamma\) the largest \(\gamma\) such that \(\alpha_i - \gamma \lambda_i \geq 0 \ \forall i\). In fact, \(\sum_{i=1}^m(\alpha_i - \bar \gamma \lambda_i) x_i = \sum_{i=1}^m \alpha_i x_i - \bar \gamma \sum_{i=1}^m \lambda_i x_i = \sum_{i=1}^m \alpha_i x_i + 0 = x\). Note that at least one of the coefficients is \(0\), so this provides a representation of \(x\) with fewer than \(m\) elements, which is a contradiction.

   Therefore, \(x_i\) must be linearly independent when \(m\) is minimal, and this implies \(m \leq n\).

2. We apply the previous result to the cone generated by lifting the convex set to a higher dimension. Let \(K = \mathrm{cone}(\{ (1,x) \in \mathbb{R}^{n+1} \mid x \in S \}) \subset \mathbb{R}^{n+1}\) such that \(\mathrm{conv}(S) = K \cap \{ (1, x) \mid x \in \mathbb{R}^n\} \subset \mathbb{R}^n\).

   By the previous result, if \(y \in K \Rightarrow y = \sum_{i=1}^m w_i y_i, \ y_i \in K, \ w_i > 0, \ m \leq n+1\). In particular, let \(y \in \{ (1, x) \mid x \in S\} \subset K\). Thus, \((1,x) = \sum_{i=1}^m w_i (1, x_i), \ x_i \in S\). Therefore, \(\sum_{i=1}^m w_i x_i = x, \ \sum_{i=1}^m w_i = 1\) so that \(x\) can be represented by a convex combination with \(m \leq n+1\).

 ◻

Let \(S \subset \mathbb{R}^n\) be compact. Take a sequence \((a_k)_{k \in \mathbb{N}} \subset \mathrm{conv}(S)\). By Carathéodory’s theorem, each element of the sequence \(a_k \in \mathrm{conv}(S)\) can be written as \(a_k = \sum_{i=1}^{n+1}\lambda_i^k x_i^k, \ \lambda_i^k \geq 0, \ \sum_{i=1}^{n+1}\lambda_i^k = 1, \ x_i^k \in S\).

Let \((b_k)_{k \in \mathbb{N}}\) be the sequence \((\lambda_1^k, \ldots, \lambda_{n+1}^k, x_1^k, \ldots, x_{n+1}^k)\). Note that the sequence is bounded, since \(0 \leq \lambda_i^k \leq 1\) and \(x_i^k \in S\). Thus, there exists a convergent subsequence \(({b_k}_j)_{j \in \mathbb{N}}\) converging to \((\lambda_1, \ldots, \lambda_{n+1}, x_1, \ldots, x_{n+1})\) (by Boltzano-Weierstrass’ theorem). This limit point must satisfy \(\sum_{i=1}^{n+1} \lambda_i = 1, \ \lambda_i \geq 0, \ x_i \in S\). Therefore, \(\sum_{i=1}^{n+1} \lambda_i x_i \in \mathrm{conv}(S)\), so that \(\mathrm{conv}(S)\) is compact. ◻

1. Let \(w \in C\), and define the compact and convex set \(W = \{ z \in C \mid d(x,z) \leq d(x, w)\}\). Note that \(f(z) = \|x -z\|\) is continuous on \(W\), so existance of a minimum in \(W\) is guaranteed by Weierstrass’ theorem. Regarding uniqueness, suppose \(z_1, z_2 \in W\), \(z_1 \neq z_2\) are both minima of \(f\), so \(f(z_1) = f(z_2) = m\). Using the parallelogram identity, we have \(0 < \|z_1 - z_2\|^2 = \|(z_1-x) - (z_2 -x)\|^2 = 2 \|z1-x\|^2 + 2 \|z_2 - x\|^2 - \|z_1 + z_2 - 2x\|^2 = 4m^2 - 4 \|\hat z - x\|^2\) for \(\hat z = \frac{z_1 + z_2}{2} \in W\) (convex combination). Then, \(\|\hat z - x\| = f(\hat z) < m\), a contradiction.

2. (\(\Leftarrow\)) \(\forall y, z \in C\), we have \(\|y-x\|^2 = \|(y-z) - (x-z)\|^2 = \|y-z\|^2 + \|x-z\|^2 - \langle y-z, x-z \rangle \geq \|z-x\|^2 - 2 \langle y-z, x-z \rangle\). Therefore, if \(z\) is s.t. \(\langle y-z, x-z \rangle \leq 0 \ \forall y \in C\), then \(\|z-x\| \leq \|y-x\| \ \forall y \in C\), so \(z = z_0\). (\(\Rightarrow\)) Conversely, consider \(z_0\) to be the projection of \(x\) onto \(C\). Let \(y \in C\) and define \(y_\alpha = (1-\alpha) z_0 + \alpha y\) for \(\alpha > 0\). Note that \(y_\alpha \in C\) (convex combination). Define \(\varphi(\alpha) = \|x- y_\alpha\|^2\). Then, \(\frac{\partial \varphi}{\partial \alpha}\vert_{\alpha = 0} = -2 \|x-z_0\| + 2 \langle x-z_0, x-y \rangle = -2 \langle x-z_0, y-z_0 \rangle\). If \(\langle x-z_0, y-z_0 \rangle > 0\) for some \(y \in C\), \(\frac{\partial}{\partial \alpha}(\|x-y_\alpha\|^2)\vert_{\alpha = 0} < 0\), so for \(\alpha\) small we will have \(\|x-y_\alpha\| < \|x-z_0\|\), a contradiction.

 ◻

Define \(f \colon K \rightarrow \mathbb{R}\) such that \(f(x)\) is the distance from \(x \in K\) to the \(C\), \(f(x) = \min \{ \|x-y\| \mid y \in C\}\). By [thm:projection], \(\forall x \in K \ \exists y_0 \in C\) such that \(f(x) = \|x - y_0\|\), where \(y_0 = y_0(x)\). Note that \(f(x)\) is continuous (in fact, Lipschitz): by the triangle inequality, we have \(d(x',y) \leq d(x',x) + d(x', y)\) and \(d(x,y) \leq d(x, x') + d(x, y)\) \(\forall x, x' \in K, y \in C\), so \(| f(x) - f(x') | \leq \|x - x'\|\). By Weierstrass’ theorem, \(f(x)\) has a minimum in \(K\). Let \(x_0\) be such a minimum, and note that \(f(x_0) = \|x_0 - y_0\| > 0\) since \(K \cap C = \emptyset\). Define \(b = x_0 - y_0\), so \(0 < \|b\|^2 = \langle b, x_0 - y_0 \rangle \Rightarrow \langle b, y_0 \rangle < \langle b, x_0 \rangle\).

It only remains to show that \(\langle b, y_0 \rangle \geq \langle b, y \rangle \ \forall y \in C\) and \(\langle b, x_0 \rangle \leq \langle b, x \rangle \ \forall x \in K\). Take \(y \in C\) and define \(z = (1-\lambda) y_0 + \lambda y, \ \lambda \in (0, 1)\) (so \(z \in C\)). Then, by definition of \(y_0\), \(\|x_0 - z\|^2 \geq \| x_0 - y_0\|^2 \Rightarrow 0 \geq \|x_0-y_0\|^2 - \|x_0 - y_0 - \lambda (y-y_0)\|^2 \Rightarrow 0 \geq 2 \lambda \langle x_0- y_0, y -y_0 \rangle - \lambda ^2 \| y- y_0\|^2 \Rightarrow 2 \langle b, y-y_0 \rangle \leq \lambda \|y-y_0\|^2\). Now, take \(\lambda \to 0\), so \(\langle b, y \rangle \leq \langle b,y_0 \rangle \ \forall y \in C\). A similar argument for \(x \in K\) holds.

Then, take the hyperplane \(H = \{ x \mid \langle x, b \rangle = \beta \}\) with \(\beta \in (\langle b, y_0 \rangle, \langle b, x_0 \rangle)\). We have shown that \(\forall x \in K, \langle x, b \rangle > \beta\) and \(\forall y \in C, \langle y, b \rangle < \beta\), completing the proof. ◻

Take a sequence \((x_k)_{k \in \mathbb{N}}\) that does not belong to \(\mathrm{cl}(C)\) and converges to \(x_0\). Let \(\hat x_k\) be the projection of \(x_k\) onto \(\mathrm{cl}(C)\). Define \(a_k = \frac{\hat x_k - x_k}{\|\hat x_k - x_k\|}\). By [thm:projection], \(\langle y - \hat x_k, x_k - \hat x_k \rangle \leq 0, \ \forall y \in C, k \in \mathbb{N} \Rightarrow \langle y, x_k - \hat x_k \rangle \leq \langle x_k, x_k - \hat x_k \rangle = \|x_k - \hat x_k\|^2 + \langle \hat x_k, x_k - \hat x_k \rangle \Rightarrow \langle y, x_k - \hat x_k \rangle \leq \langle \hat x_k, x_k - \hat x_k \rangle \Rightarrow \langle \hat x_k, a_k \rangle \leq \langle y , a_k \rangle\) which results in the important inequality \(\langle x_k, a_k \rangle \leq \langle y, a_k \rangle \ \forall y \in \mathrm{cl}(C), k \in \mathbb{N}\). Since the sequence \((a_k)_{k \in \mathbb{N}}\) is bounded (\(\|a_k\| = 1 \ \forall k\)), by Boltzano-Weierstrass’ theorem there exists a convergent subsequence \(({a_k}_j)_{j \in \mathbb{N}}\). Let \(a_0\) be the limit of such a sequence. Then, \(\lim_{j \to \infty} \langle {x_k}_j, {a_k}_j \rangle \leq \lim_{j \to \infty} \langle y , {a_k}_j \rangle \ \Rightarrow \ \langle x_0, a_0 \rangle \leq \langle y, a_0 \rangle \ \forall y \in C\). We have thus constructed the supporting hyperplane \(H = \{ x \mid \langle x, b \rangle = \beta \}\) with \(b = a_0, \ \beta = \langle a_0, x_0 \rangle\), such that \(C \subset h_H^+\) and \(x_0 \in H\). ◻

Let \(z \in F \cap \mathrm{ri}(D)\). If \(x \in D, \ x \neq z\) then \(\exists y \in D\) such that \(z \in \mathrm{ri}(\{ (1 - \lambda) x + \lambda y \mid \lambda \in (0,1)\})\). Since \(F\) is a face, \(x, y \in F\) by definition, so \(D \subset F\). ◻

\(F' \subset F\) because \(\mathrm{ri}(F')\) meets \(F\), and likewise \(F \subset F'\). ◻

If \(\mathrm{ri}(C)\) met \(F\), we would have \(C \subset F\), and therefore \(C = F\), a contradiction. Therefore, \(F \subset \mathrm{cl(C)} \setminus \mathrm{ri}(C) = \mathrm{rb}(C)\). ◻

Two alternative proofs are found in the references. They require further development of the theory of faces not covered here. ◻

Let the polytope be \(\mathrm{conv}(\{b_1, \ldots, b_m\})\), with \(b_i\) its vertices. The vertex centroid is defined as the arithmetic mean of the vertices, that is, \(v_{\text{centre}} = \frac{1}{m}\sum_{i=1}^m b_i\). Note that this is a convex sum (\(\lambda_i = \frac{1}{m}\)), so by [thm:convex_closed] \(v_{\text{centre}}\) must belong to \(\mathrm{conv}(\{b_1, \ldots, b_m\})\). ◻

By induction. Denote by \(S(n,k)\) the number of k-faces of an n-simplex. The base case is trivial: a 1-simplex (segment) has 2 0-faces and 1 1-face, so \(S(1,0) = 2 = \binom{2}{1}, \ S(1,1) = 1 = \binom{2}{2}\). Next, assume that \(S(n-1, k) = \binom{(n-1) + 1}{k+1} = \binom{n}{k+1}\). Now, consider an n-simplex by adding an affinely independent vertex \(v\) to an existing (n-1)-simplex, named as base. Its total number of k-faces will be the number of k-faces that do not include \(v\) plus the number of k-faces that do include \(v\). The first is given precisely by the number of k-faces of the base, \(S(n-1, k)\). To count the latter, consider that the k-faces that do not include \(v\) are formed by taking the (k-1)-faces of the base and joining them with \(v\), so their count is given by \(S(n-1, k-1)\). Thus, \(S(n, k) = S(n-1, k) + S(n-1, k-1) = \binom{n}{k+1} + \binom{n}{k} = \binom{n+1}{k+1}\). ◻