University Mathematics — Year 2 · Bachelor Year 2

17Affine Spaces

Vector spaces have a privileged point — the origin — that geometry does not want. An affine space is a vector space that has forgotten its origin: points and vectors become different species, related by translation. This short chapter builds the dictionary (points, barycenters, affine subspaces and maps), the affine view of convexity, and the classification tools used in the geometry chapters ahead.

17.1 Points and vectors

Definition 17.1

An affine space directed by a real vector space $E$ is a nonempty set $\mathcal{E}$ with a map $(A, B) \mapsto \vect{AB} \in E$ satisfying

\vect{AB} + \vect{BC} = \vect{AC} \quad \text{(Chasles)}, \qquad \text{for each } A,\ B \mapsto \vect{AB} \text{ is a bijection } \mathcal{E} \to E .

One writes $B = A + u$ for the unique point with $\vect{AB} = u$ . The dimension of $\mathcal{E}$ is $\dim E$ . Every vector space is an affine space over itself ( $\vect{AB} = B - A$ ); every choice of origin $O \in \mathcal{E}$ identifies $\mathcal{E}$ with $E$ via $M \mapsto \vect{OM}$ .

Example 17.2 (An affine space with no natural origin)

The solution plane $\mathcal E = \{(x, y, z) \in \R^3 : x + y + z = 1\}$ is not a vector subspace ( $0 \notin \mathcal E$ ), but it is an affine space directed by $E = \{x + y + z = 0\}$ : for $A, B \in \mathcal E$ the difference $\vect{AB} = B - A$ lands in $E$ (the sums cancel), Chasles is inherited from $\R^3$ , and $B \mapsto \vect{AB}$ is bijective onto $E$ . No point of $\mathcal E$ is distinguished — any choice of “origin” $O \in \mathcal E$ works equally well, and all the identifications $M \mapsto \vect{OM}$ differ by translations. This is the typical situation: solution sets of inhomogeneous linear problems (linear systems, linear differential equations in Chapter 16) are affine, never linear, and the slogan “particular solution plus kernel” is exactly the statement $\mathcal F = A + F$ of the next definition.

Definition 17.3 (Barycenter)

Let $(A_i, \lambda_i)_{i \leq k}$ be weighted points with $\sum\lambda_i \neq 0$ . The barycenter $G = \operatorname{bar}\bigl((A_i, \lambda_i)\bigr)$ is the unique point with

\sum_i \lambda_i\, \vect{GA_i} = 0 \qquad\text{equivalently}\qquad \vect{OG} = \frac{1}{\sum\lambda_i}\sum_i \lambda_i\,\vect{OA_i} \quad (\text{any } O).

Barycenters are associative (subgroups of points may be replaced by their partial barycenter with the summed weight) and invariant under rescaling of all weights.

Proof of existence and the formulas. Fix $O$ and write $s = \sum_i\lambda_i \neq 0$ . By Chasles,

\sum_i\lambda_i\,\vect{GA_i} = 0 \iff \sum_i\lambda_i\bigl(\vect{GO} + \vect{OA_i}\bigr) = 0 \iff s\,\vect{OG} = \sum_i\lambda_i\,\vect{OA_i},

which determines $G = O + \frac1s\sum_i\lambda_i\vect{OA_i}$ uniquely. Independence of $O$ : for another origin $O'$ ,

\frac1s\sum_i\lambda_i\,\vect{O'A_i} = \frac1s\sum_i\lambda_i\bigl(\vect{O'O} + \vect{OA_i}\bigr) = \vect{O'O} + \frac1s\sum_i\lambda_i\,\vect{OA_i} = \vect{O'G} :

the same point $G$ . Associativity: split the index set as $I \sqcup J$ with $s_I = \sum_{i\in I}\lambda_i \neq 0$ , and let $G_I$ be the barycenter of $(A_i, \lambda_i)_{i\in I}$ , so that $\sum_{i\in I}\lambda_i\vect{OA_i} = s_I\,\vect{OG_I}$ . Then

s\,\vect{OG} = \sum_{i\in I}\lambda_i\vect{OA_i} + \sum_{j\in J}\lambda_j\vect{OA_j} = s_I\,\vect{OG_I} + \sum_{j\in J}\lambda_j\vect{OA_j} :

$G$ is the barycenter of $(G_I, s_I)$ together with $(A_j, \lambda_j)_{j\in J}$ , as claimed. Rescaling: replacing each $\lambda_i$ by $t\lambda_i$ ( $t \neq 0$ ) multiplies $s$ and the weighted sum by $t$ , leaving $\vect{OG}$ unchanged. ∎

Remark 17.4 (Common pitfalls)

Two traps surround the definition. First, if the weights sum to zero, there is no barycenter: the map $O \mapsto \sum\lambda_i\vect{OA_i}$ is then independent of $O$ and defines a vector, not a point — for instance $(A, -1;\ B, 1)$ encodes $\vect{AB}$ . Keeping track of which of the two objects a computation produces is half of barycentric hygiene. Second, weights are only meaningful up to a common nonzero factor; formulas like “the coordinates of $G$ are $\lambda_1, \dots, \lambda_k$ ” presuppose a normalization (usually $\sum\lambda_i = 1$ ), and forgetting to normalize is the standard source of wrong ratios on a figure.

Definition 17.5 (Affine subspaces; affine maps)

An affine subspace is a set $\mathcal{F} = A + F = \{A + u : u \in F\}$ with $F$ a vector subspace (its direction); equivalently, a nonempty set stable under barycenters. Affine subspaces of $\R^n$ are exactly the solution sets of linear systems $MX = B$ (Year 1: particular solution plus kernel). A map $f \colon \mathcal{E} \to \mathcal{E}'$ is affine when it preserves barycenters — equivalently when

f(A + u) = f(A) + \varphi(u)

for a (unique) linear map $\varphi = \vec f$ , the linear part. Affine maps of $\R^n$ : $X \mapsto MX + C$ . Compositions are affine with composed linear parts; $f$ is bijective iff $\vec f$ is.

Proof of the equivalence for maps. If $f(A + u) = f(A) + \varphi(u)$ : for a barycenter $G$ of $(A_i, \lambda_i)$ , expanding every point from $A$ , $f(G) = f(A) + \varphi(\vect{AG})$ and $\varphi(\vect{AG}) = \frac{\sum\lambda_i\varphi(\vect{AA_i})}{\sum\lambda_i}$ : $f(G)$ is the barycenter of the images. Conversely, fix $A$ and define $\varphi(u) = \vect{f(A)\,f(A + u)}$ . Homogeneity: $A + tu = \operatorname{bar}\bigl(A, 1-t;\ A + u, t\bigr)$ for every real $t$ , so preservation of barycenters (with arbitrary real weights, as hypothesized) gives $\varphi(tu) = t\,\varphi(u)$ directly. Additivity: $A + u + v = \operatorname{bar}\bigl(A + 2u, \tfrac12;\ A + 2v, \tfrac12\bigr)$ , so $\varphi(u + v) = \tfrac12\varphi(2u) + \tfrac12\varphi(2v) = \varphi(u) + \varphi(v)$ , using homogeneity. Hence $\varphi$ is linear. ∎

Remark 17.6

The proof used barycenters with arbitrary real weights: the homogeneity step takes $t$ outside $\intcc01$ . If a map is only assumed to preserve barycenters with nonnegative weights — equivalently, midpoints and segments — linearity of the vector map no longer comes for free: one only gets $\Q$ -linearity, and a continuity hypothesis is needed to conclude, exactly as in Exercise 17.5. Distinguishing “preserves all barycenters” from “preserves convex combinations” is a small but real subtlety of the affine vocabulary.

Example 17.7 (Classical barycenter geometry)

The centroid of a triangle $ABC$ is the barycenter $G = \operatorname{bar}(A,1; B,1; C,1)$ . Associativity with the midpoint $A' = \operatorname{bar}(B, 1; C, 1)$ shows

G = \operatorname{bar}(A, 1;\ A', 2) :

$G$ lies on the median $AA'$ at two-thirds of it — and likewise for the other two medians: the three medians are concurrent, in one line of barycentric calculus.

Example 17.8 (The bimedians of a quadrilateral)

Let $ABCD$ be any quadrilateral (planar or not!) and consider its bimedians: the segments joining the midpoints of opposite sides, $M_{AB}M_{CD}$ and $M_{BC}M_{DA}$ . Introduce the barycenter $G$ of $(A,1; B,1; C,1; D,1)$ and group the weights two ways:

G = \operatorname{bar}\bigl(M_{AB}, 2;\ M_{CD}, 2\bigr) = \operatorname{bar}\bigl(M_{BC}, 2;\ M_{DA}, 2\bigr) :

$G$ is the midpoint of both bimedians — so the two bimedians always bisect each other, and the quadrilateral of the four midpoints is a parallelogram (its diagonals are the bimedians). No case analysis, no coordinates, and the argument survives unchanged for a skew quadrilateral in $\R^3$ , where a picture-based proof would already be delicate: associativity does not care about dimension.

Example 17.9 (Classifying an affine map, start to finish)

Let $f(x, y) = (2x - 1,\ 3y - 4)$ on $\R^2$ . Its linear part is $\varphi = \operatorname{diag}(2, 3)$ , whose spectrum $\{2, 3\}$ avoids $1$ : by the fixed-point criterion proved below (Proposition 17.17), $f$ has exactly one fixed point, found by solving

x = 2x - 1, \qquad y = 3y - 4 \qquad\Longrightarrow\qquad \Omega = (1, 2).

Recentering at $\Omega$ (set $x = 1 + u$ , $y = 2 + v$ ):

f(1 + u,\ 2 + v) = (1 + 2u,\ 2 + 3v) :

in the frame at $\Omega$ , $f$ is its linear part, an anisotropic dilation stretching by $2$ horizontally and $3$ vertically from the center $(1, 2)$ . The general lesson: an affine map is “linear map plus location data”, and the location data collapses to one well-chosen origin whenever $1$ is not an eigenvalue. Conversely, translating the origin badly creates the constant terms: affine geometry is the art of choosing where to put $0$ .

Remark 17.10 (Method: concurrency and alignment by barycenters)

Example 17.7 is an instance of a general recipe. To prove that three cevians of a triangle are concurrent, exhibit a single weighted system $(A, \alpha; B, \beta; C, \gamma)$ and use associativity three ways: grouping $(B, C)$ shows the barycenter lies on the cevian from $A$ , grouping $(C, A)$ on the cevian from $B$ , grouping $(A, B)$ on the third. For the medians, the system $(A, 1; B, 1; C, 1)$ does all the work; for cevians cutting the sides in prescribed ratios, the weights are read off the ratios. To prove three points aligned, write one as a barycenter of the other two (Exercise 17.2), or use the determinant criterion of Exercise 17.11. Both recipes replace geometric ingenuity by weight bookkeeping — this is precisely what barycentric calculus is for.

17.2 Convexity, affinely

Definition 17.11

A subset $C$ of an affine space is convex when it contains every barycenter with nonnegative weights of its points — equivalently, every segment $\intcc{A}{B} = \{\operatorname{bar}(A, 1-t; B, t) : t \in \intcc{0}{1}\}$ between its points. The convex hull $\operatorname{conv}(S)$ is the set of all nonnegative-weight barycenters of points of $S$ — the smallest convex set containing $S$ .

Example 17.12 (Epigraphs are convex sets)

The region $C = \{(x, y) : y \geq x^2\}$ above the parabola is convex: for $(x_1, y_1), (x_2, y_2) \in C$ and $t \in \intcc01$ , the convexity inequality of the square function gives

\bigl((1-t)x_1 + tx_2\bigr)^2 \leq (1-t)x_1^2 + tx_2^2 \leq (1-t)y_1 + ty_2 ,

so the barycenter stays above the parabola. The computation is general: $\{y \geq f(x)\}$ is convex exactly when $f$ is a convex function — convex sets and convex functions (Chapter 8) are two faces of one notion, epigraphs being the dictionary. This is the geometric reason support lines exist for convex functions, the fact that will prove Jensen’s inequality in Chapter 22.

Example 17.13 (Redundant generators of a convex hull)

Let $S = \{(0,0), (2,0), (2,2), (0,2), (1,1)\}$ . The fifth point is the barycenter

(1,1) = \operatorname{bar}\bigl((0,0), \tfrac12;\ (2,2), \tfrac12\bigr),

so it already lies in the hull of the other four: $\operatorname{conv}(S)$ is the square with the four corners as vertices. In general, a point of $S$ that is a nonnegative-weight barycenter of the other points of $S$ can be deleted without changing the hull; the points that can never be deleted (here the four corners) are the extreme points of the hull. Determining them is a pure barycenter computation: $(2,0)$ , say, cannot be written as $\operatorname{bar}$ of the remaining points with nonnegative weights, because the first coordinate would force all weight onto points with $x = 2$ , and the second coordinate then fails. Convexity questions reduce, again and again, to solving small weighted systems.

Theorem 17.14 (Carathéodory)

In an affine space of dimension $n$ , every point of $\operatorname{conv}(S)$ is a barycenter of at most $n + 1$ points of $S$ .

Proof. Let $G = \operatorname{bar}(A_0, \lambda_0; \dots; A_k, \lambda_k)$ with $\lambda_i > 0$ , $\sum\lambda_i = 1$ , and $k + 1 > n + 1$ points. The $k$ vectors $\vect{A_0A_i}$ ( $i \geq 1$ ) are linked ( $k > n$ ): $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ nontrivially; setting $\mu_0 = -\sum_{i\geq1}\mu_i$ , we get weights $(\mu_i)$ with $\sum\mu_i = 0$ , $\sum \mu_i\,\vect{OA_i} = 0$ (any $O$ ), not all zero. Then for every real $t$ the weights $\lambda_i - t\mu_i$ still sum to $1$ and, since $\sum_i\mu_i\vect{OA_i} = 0$ ,

\sum_i(\lambda_i - t\mu_i)\,\vect{OA_i} = \sum_i\lambda_i\,\vect{OA_i} :

they produce the same point $G$ . Now slide $t$ from $0$ : some $\mu_i$ is positive (they sum to zero and are not all zero), so

t^* = \min\Bigl\{\frac{\lambda_i}{\mu_i} : \mu_i > 0\Bigr\}

is well defined and positive. At $t = t^*$ : for indices with $\mu_i > 0$ , $\lambda_i - t^*\mu_i \geq 0$ by minimality, with equality at a minimizing index; for indices with $\mu_i \leq 0$ , $\lambda_i - t^*\mu_i \geq \lambda_i > 0$ . All weights remain nonnegative and at least one has died: $G$ is rewritten as a barycenter of fewer points. Iterate while more than $n + 1$ points remain. ∎

Example 17.15

In the plane ( $n = 2$ ): every point of the convex hull of a finite set lies in a triangle with vertices in the set — the geometric content of Carathéodory, used in optimization and probability (mixtures) alike.

Example 17.16 (Running Carathéodory’s algorithm)

Write the center of the square of Example 17.13 with its four corners $A_1 = (0,0)$ , $A_2 = (2,0)$ , $A_3 = (2,2)$ , $A_4 = (0,2)$ :

(1,1) = \operatorname{bar}\bigl(A_1, \tfrac14;\ A_2, \tfrac14;\ A_3, \tfrac14;\ A_4, \tfrac14\bigr),

four points in dimension $2$ — one too many. The proof’s recipe asks for weights $(\mu_i)$ with $\sum\mu_i = 0$ and $\sum\mu_i\vect{OA_i} = 0$ : here $\mu = (1, -1, 1, -1)$ works (the two diagonals share their midpoint). Sliding $\lambda_i \mapsto \lambda_i - t\mu_i$ keeps the barycenter fixed for every $t$ ; the extremal admissible value $t = \frac14$ makes the weights $(0, \tfrac12, 0, \tfrac12)$ , killing $A_1$ and $A_3$ simultaneously:

(1,1) = \operatorname{bar}\bigl(A_2, \tfrac12;\ A_4, \tfrac12\bigr),

a representation by two points — even better than the three that the theorem guarantees, because the center happens to lie on a segment between generators. The algorithm is entirely mechanical: find a dependence, slide until a weight dies, repeat.

17.3 Affine classification tools

Proposition 17.17 (Fixed points of affine maps)

Let $f$ be an affine endomorphism of a finite-dimensional affine space with linear part $\varphi$ . If $1 \notin \operatorname{Sp}(\varphi)$ , then $f$ has exactly one fixed point $\Omega$ , and in the vectorialization at $\Omega$ , $f$ is its linear part. (Translations, with $\varphi = \mathrm{id}$ and no fixed point, are the basic obstruction.)

Proof. Fix $O$ and write $f(O + x) = f(O) + \varphi(x)$ . The point $O + x$ is fixed iff $O + x = f(O) + \varphi(x)$ , i.e.

(\mathrm{id} - \varphi)(x) = \vect{O f(O)} .

In finite dimension, $\mathrm{id} - \varphi$ is invertible iff $0$ is not an eigenvalue of $\mathrm{id} - \varphi$ , iff $1 \notin \operatorname{Sp}\varphi$ — and in that case the displayed equation has exactly one solution $x^*$ , giving the unique fixed point $\Omega = O + x^*$ . Recentering: for any vector $u$ ,

f(\Omega + u) = f(\Omega) + \varphi(u) = \Omega + \varphi(u),

so in the frame with origin $\Omega$ the map reads $u \mapsto \varphi(u)$ : purely linear. When $1 \in \operatorname{Sp}\varphi$ , either no fixed point exists (the displayed equation may be unsolvable, as for a translation) or a whole affine subspace of them does (add any eigenvector of eigenvalue $1$ to a solution): uniqueness is exactly the spectral condition. ∎

Example 17.18 (Plane isometries, completed)

An affine isometry of the Euclidean plane has linear part in $O(2)$ : a rotation $R_\theta$ or a reflection (Year 1 volume). If $\theta \neq 0$ : $1 \notin \operatorname{Sp} R_\theta$ , so the map is a rotation about a unique center (Proposition 17.17). If the linear part is a reflection: either a reflection in an axis (fixed points exist) or a glide reflection (reflection composed with a translation along the axis, no fixed point). With translations, this is the complete classification of plane isometries.

Remark 17.19 (The plane isometries, at a glance)

Collecting the cases: identity; translations ( $\vec f = \mathrm{id}$ , no fixed point unless trivial); rotations (linear part $R_\theta$ , $\theta \neq 0$ : one center); reflections (linear part a reflection, a line of fixed points); glide reflections (same linear part, no fixed point). Four families plus the identity, each recognized by two data only: the linear part and the fixed-point set — the pattern of Proposition 17.17 made exhaustive.

Example 17.20 (A glide reflection, caught in the act)

Let $f(x, y) = (y + 1,\ x + 1)$ . The linear part $(x, y) \mapsto (y, x)$ is the reflection in the diagonal $y = x$ , so $1 \in \operatorname{Sp}\vec f$ and Proposition 17.17 is silent. Fixed points would need $x = y + 1$ and $y = x + 1$ simultaneously: impossible — none exist, so $f$ is not a reflection. Squaring settles the classification:

f\bigl(f(x, y)\bigr) = f(y + 1,\ x + 1) = (x + 2,\ y + 2),

the translation by $(2, 2)$ : $f$ is the glide reflection with axis the line $y = x$ (shifted appropriately: the midpoint of $M$ and $f(M)$ always lies on $y = x + {}$ constant, here $y = x$ , as one checks on $M = (0, 0) \mapsto (1,1)$ ) and glide vector $(1, 1)$ , half of $f \circ f$ . Compare with Exercise 17.6, where the same linear part but a different constant produced an honest reflection: with eigenvalue $1$ present, the constant term decides everything.

Example 17.21 (Affine recursions are affine dynamics)

The classical recursion $u_{n+1} = au_n + b$ ( $a \neq 1$ ) iterates the affine map $f(x) = ax + b$ of the line, whose linear part $a$ avoids the eigenvalue $1$ : there is a unique fixed point $\omega = \frac{b}{1-a}$ , and recentering there (the one-dimensional case of the proposition above) turns $f$ into multiplication by $a$ :

u_{n+1} - \omega = a\,(u_n - \omega) \qquad\Longrightarrow\qquad u_n = \omega + a^n(u_0 - \omega) .

For $u_{n+1} = \frac{u_n}2 + 3$ : $\omega = 6$ and $u_n = 6 + (u_0 - 6)2^{-n} \to 6$ . The recipe taught for such recursions in Chapter 7 — “subtract the fixed point” — is exactly the vectorialization of an affine map at its fixed point; convergence for $\abs a < 1$ is the contraction phenomenon that Chapter 4 turned into the Banach fixed-point theorem. One idea, three chapters.

Example 17.22 (Finding the center of a rotation)

Let $f(x, y) = (-y + 2,\ x)$ . The linear part is $\varphi(x, y) = (-y, x)$ : the rotation of angle $\frac\pi2$ , whose spectrum $\{\iu, -\iu\}$ avoids $1$ . By Proposition 17.17 there is exactly one fixed point: $x = -y + 2$ and $y = x$ give $x = 1$ , $y = 1$ , so $\Omega = (1, 1)$ , and $f$ is the rotation of center $(1, 1)$ and angle $\frac\pi2$ . The general lesson: when $1 \notin \operatorname{Sp}\vec f$ , classifying $f$ costs one linear system — the geometry is entirely in the linear part, the arithmetic entirely in locating the center.

Remark 17.23 (Where affine language is used next)

Barycenters and affine maps are the grammar of the geometry chapters ahead: tangent lines and planes are affine objects (Chapters 18 and 19), an affine change of variables multiplies areas and volumes by $\abs{\det \vec f}$ (Chapter 20), and expectation is a barycenter with weights given by a probability law, which is why convexity governs Jensen’s inequality (Chapter 22). In the Year 3 volume the same convexity vocabulary carries the study of $L^p$ norms and of integral inequalities.

Remark 17.24 (Perspectives within this volume)

Two threads leave this chapter. The affine thread: tangent lines (Chapter 18) and tangent planes (Chapter 19) are affine subspaces attached to nonlinear objects, and the classification of quadrics in the surfaces chapter runs on this chapter’s center equation $A\Omega = -b$ . The convex thread is longer: convexity of half-planes and disks powers the Helly theory of the weekend problem; convexity of functions gives Jensen’s inequality (Chapter 22); and the final theorem of the book — the extinction criterion for branching processes (Chapter 23) — is decided by the position of a convex curve relative to the diagonal, a picture that belongs to this chapter as much as to probability. Barycenters return there too: an expectation is a barycenter with probability weights.

17.4 Exercises

Exercise 17.1 ★

In $\R^3$ , are the following affine subspaces? Give directions and dimensions. $\{x + y + z = 1\}$ ; $\;\{x + y + z = 1,\ x - z = 3\}$ ; $\;\{x^2 + y^2 = 1\}$ ; the solution set of $MX = B$ for a given compatible system.

Solution

Solution of Exercise 17.1.

$\{x + y + z = 1\}$ : affine plane, direction the vector plane $\{x + y + z = 0\}$ , dimension $2$ . Adding $x - z = 3$ : an affine line (two independent equations), direction $\{x + y + z = 0,\ x = z\} = \operatorname{Vect}\bigl((1, -2, 1)\bigr)$ , dimension $1$ . $\{x^2 + y^2 = 1\}$ : a cylinder — not stable under barycenters (the midpoint of $(1,0,0)$ and $(-1,0,0)$ is the origin, off the cylinder): not affine. A compatible system $MX = B$ : affine subspace $X_0 + \ker M$ of dimension $\dim\ker M$ , as recalled in Definition 17.5.

Exercise 17.2 ★

Prove that three distinct points $A, B, C$ of an affine space are aligned iff $C$ is a barycenter of $A$ and $B$ , iff the vectors $\vect{AB}, \vect{AC}$ are linked. Deduce Menelaus-style weight bookkeeping: if $C = \operatorname{bar}(A, 1 - t; B, t)$ , locate $C$ for $t = \frac12$ , $t = 2$ , $t = -1$ .

Solution

Solution of Exercise 17.2.

$C = \operatorname{bar}(A, 1-t; B, t)$ means $\vect{AC} = t\,\vect{AB}$ : existence of such $t$ is exactly linkage of $\vect{AC}$ with $\vect{AB} \neq 0$ , i.e. alignment. Positions: $t = \frac12$ : midpoint; $t = 2$ : beyond $B$ , at $B$ ’s distance from it ( $\vect{AC} = 2\vect{AB}$ ); $t = -1$ : the reflection of $B$ through $A$ .

Exercise 17.3 ★

Let $f$ be the affine map of $\R^2$ given by $f(X) = MX + C$ with $M = \frac12\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}$ and $C = (1, 0)^{\mathsf T}$ . Determine the image of $f$ , its fixed points (if any), and $f \circ f$ .

Solution

Solution of Exercise 17.3.

$M$ is the projection matrix onto $\operatorname{Vect}(1,1)$ along $(1,-1)$ (check $M^2 = M$ ). Image of $f$ : $\{MX + C\} = C + \operatorname{im} M$ : the affine line through $(1,0)$ directed by $(1,1)$ . Fixed points: $X = MX + C$ , i.e. $(I - M)X = C$ ; but $C = (1, 0)^{\mathsf T}$ and $\operatorname{im}(I - M) = \operatorname{Vect}(1,-1)$ ; is $(1,0)$ in it? $(1, 0) = \alpha(1,-1)$ forces $\alpha = 1$ and $0 = -1$ : no. No fixed points. And

f(f(X)) = M(MX + C) + C = MX + MC + C = f(X) + MC, \qquad MC = \tfrac12(1,1)^{\mathsf T} :

$f\circ f$ is $f$ followed by a translation along the image line — $f$ is a “glide projection”: projection onto the line composed with a slide.

Exercise 17.4 ★★

(Associativity in action) In a triangle $ABC$ , let $I, J, K$ divide $BC$ , $CA$ , $AB$ in ratios $\vect{BI} = \frac13\vect{BC}$ , $\vect{CJ} = \frac13\vect{CA}$ , $\vect{AK} = \frac13\vect{AB}$ . Express $I, J, K$ as barycenters and compute the barycenter of $(I,1;J,1;K,1)$ : what do you find, and why was it predictable?

Solution

Solution of Exercise 17.4.

$I = \operatorname{bar}(B, 2; C, 1)$ (since $\vect{BI} = \frac13\vect{BC}$ places $I$ closer to $B$ : weights $2$ on $B$ , $1$ on $C$ — check: $\vect{BI} = \frac{1}{3}\vect{BC}$ ). Similarly $J = \operatorname{bar}(C, 2; A, 1)$ , $K = \operatorname{bar}(A, 2; B, 1)$ . Summing the three weighted systems, the barycenter of $(I, 1; J, 1; K, 1)$ (each of total weight $3$ , so replace $I$ by its system, etc.) is

\operatorname{bar}\bigl(A, 1 + 2;\ B, 2 + 1;\ C, 1 + 2\bigr) = \operatorname{bar}(A, 1; B, 1; C, 1) = G ,

the centroid of $ABC$ : the triangle $IJK$ has the same centroid — predictable, because the construction treats $A, B, C$ cyclically and the centroid is the unique fixed point of the cyclic symmetry of weights.

Exercise 17.5 ★★

Prove that a map $f \colon \R^n \to \R^n$ preserving midpoints ( $f\bigl(\frac{A+B}{2}\bigr) = \frac{f(A) + f(B)}{2}$ ) and continuous is affine. (Show the vector map $u \mapsto f(O + u) - f(O)$ is additive via midpoints, then $\Q$ -homogeneous, then $\R$ -homogeneous by continuity — the same density strategy used for Cauchy’s functional equation in the Year 1 volume; re-derive the needed steps here.)

Solution

Solution of Exercise 17.5.

Set $g(u) = f(O + u) - f(O)$ (working in $\R^n$ vectorialized at $O$ ), $g(0) = 0$ .

Additivity: $\frac{(O + u) + (O + v)}{2} = O + \frac{u + v}{2}$ , so midpoint preservation gives $g\bigl(\frac{u+v}{2}\bigr) = \frac{g(u) + g(v)}{2}$ ; with $v = 0$ : $g(u/2) = g(u)/2$ ; combining, $g(u + v) = 2g\bigl(\frac{u+v}{2}\bigr) = g(u) + g(v)$ .

$\Q$ -homogeneity: additivity gives $g(nu) = ng(u)$ ( $n \in \N$ , induction), then $g(-u) = -g(u)$ (add), then $g(\frac pq u) = \frac pq g(u)$ (apply $q$ , use injectivity of scaling).

$\R$ -homogeneity: for $t \in \R$ , take rationals $t_n \to t$ : $g(t_nu) = t_ng(u)$ , and continuity of $g$ (inherited from $f$ ) passes to the limit: $g(tu) = tg(u)$ . Hence $g$ is linear and $f = f(O) + g$ : affine.

Exercise 17.6 ★★

Classify the affine map $f(x, y) = (y + 1,\; x - 1)$ of the Euclidean plane: linear part, fixed points, geometric nature (reflection? glide?). Compute $f \circ f$ and conclude.

Solution

Solution of Exercise 17.6.

Linear part $\varphi(x,y) = (y, x)$ : the reflection in the diagonal $y = x$ (orthogonal, determinant $-1$ ). Fixed points: $(x, y) = (y + 1, x - 1)$ amounts to the single equation $y = x - 1$ (the two components are equivalent): every point of the line $y = x - 1$ is fixed. So $f$ fixes that line pointwise: $f$ is the reflection in that axis (an isometry with a line of fixed points and linear part a reflection). Consistently, $f \circ f(x,y) = f(y+1, x-1) = (x - 1 + 1, y + 1 - 1) = (x, y)$ : an involution, as a reflection must be.

Exercise 17.7 ★★★

(Radon) Let $A_1, \dots, A_{n+2}$ be points of an affine space of dimension $n$ . Prove that they can be split into two disjoint groups whose convex hulls intersect. (As in Carathéodory’s proof, find weights $\mu_i$ , not all zero, with $\sum\mu_i = 0$ and $\sum\mu_i\vect{OA_i} = 0$ ; separate positive and negative weights and normalize both sides.)

Solution

Solution of Exercise 17.7.

The $n + 1$ vectors $\vect{A_1A_i}$ ( $i \geq 2$ ) are linked in dimension $n$ : there are $\mu_i$ , not all zero, with $\sum_{i\geq2} \mu_i\vect{A_1A_i} = 0$ ; set $\mu_1 = -\sum_{i \geq 2}\mu_i$ , so $\sum_{i}\mu_i = 0$ and $\sum_i \mu_i\,\vect{OA_i} = 0$ for every $O$ , with not all $\mu_i$ zero. Split indices: $P = \{i : \mu_i > 0\}$ , $N = \{i : \mu_i < 0\}$ , both nonempty (the $\mu_i$ sum to zero and are not all zero). With $s = \sum_{i\in P}\mu_i = -\sum_{i \in N}\mu_i > 0$ :

\operatorname{bar}\bigl(A_i, \tfrac{\mu_i}{s}\bigr)_{i \in P} = \operatorname{bar}\bigl(A_i, \tfrac{-\mu_i}{s}\bigr)_{i \in N},

(both sides equal the point $X$ with $\vect{OX} = \frac1s\sum_{i\in P}\mu_i\vect{OA_i}$ , by the relation): a common point of the two convex hulls, with disjoint index groups.

Exercise 17.8 ★★★

Let $f$ be an affine endomorphism of $\R^n$ with $f \circ f = f$ . Prove that $f$ is the affine projection onto the affine subspace $\operatorname{Fix}(f) = \operatorname{im} f$ along the direction $\ker\vec f$ , and that conversely all such projections are idempotent. (Show first that $\operatorname{im} f$ consists of fixed points.)

Solution

Solution of Exercise 17.8.

Image = fixed points: for $Y = f(X)$ , $f(Y) = f(f(X)) = f(X) = Y$ : every image point is fixed; conversely fixed points are images. So $\mathcal{F} = \operatorname{im} f = \operatorname{Fix}(f)$ is nonempty, and it is an affine subspace (image of an affine map), with direction $\operatorname{im}\vec f$ .

Projection structure: $\vec f$ is idempotent ( $\vec{f\circ f} = \vec f^{\,2} = \vec f$ ), so $E = \operatorname{im}\vec f \oplus \ker \vec f$ (Example 3.18). For any point $X$ , consider the vector $\vect{f(X)\,X}$ ; applying $\vec f$ :

\vec f\bigl(\vect{f(X)\,X}\bigr) = \vect{f(f(X))\,f(X)} = 0 \qquad (f \circ f = f),

so $\vect{f(X)\,X} \in \ker\vec f$ . Hence $X = f(X) + \vect{f(X)X}$ displays $X$ as a point of $\mathcal{F}$ translated by a vector of $\ker\vec f$ : $f$ is exactly the projection onto $\mathcal{F}$ along $\ker\vec f$ . Conversely such projections clearly satisfy $f \circ f = f$ .

Exercise 17.9 ★

Let $G = \operatorname{bar}(A, 1;\ B, 2;\ C, 3)$ in a triangle $ABC$ . Using associativity, show that the line $AG$ meets $BC$ at $M = \operatorname{bar}(B, 2;\ C, 3)$ , and locate $G$ on the segment $\intcc AM$ ; locate likewise the intersection of $BG$ with $CA$ .

Solution

Solution of Exercise 17.9.

Let $M = \operatorname{bar}(B, 2;\ C, 3)$ , of total weight $5$ . Associativity gives $G = \operatorname{bar}(A, 1;\ M, 5)$ , so $\vect{AG} = \frac56\,\vect{AM}$ : $G$ lies on the segment $\intcc AM$ at five-sixths of it from $A$ . Since $A \notin (BC)$ , the line $(AG) = (AM)$ meets $(BC)$ at the single point $M$ , with $\vect{BM} = \frac35\,\vect{BC}$ . Likewise, with $N = \operatorname{bar}(C, 3;\ A, 1)$ (total weight $4$ , $\vect{CN} = \frac14\,\vect{CA}$ ), associativity gives $G = \operatorname{bar}(B, 2;\ N, 4)$ : the line $(BG)$ meets $(CA)$ at $N$ , and $\vect{BG} = \frac46\,\vect{BN} = \frac23\,\vect{BN}$ .

Exercise 17.10 ★★

For $\lambda \neq 0$ , the homothety $h_{\Omega, \lambda}$ is the affine map fixing $\Omega$ with linear part $\lambda\,\mathrm{id}$ . Prove that the composition $h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ is a homothety of ratio $\lambda\mu$ when $\lambda\mu \neq 1$ , and a translation when $\lambda\mu = 1$ ; in the case $\lambda = \mu = -1$ (two point reflections), compute the translation vector.

Solution

Solution of Exercise 17.10.

Vectorialize at an origin $O$ and write points as vectors: $h_{\Omega, \lambda}(x) = \omega + \lambda(x - \omega)$ with $\omega = \vect{O\Omega}$ . The composition $g = h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ is affine with linear part $\mu\lambda\,\mathrm{id}$ . If $\lambda\mu \neq 1$ : $1 \notin \operatorname{Sp}(\lambda\mu\,\mathrm{id})$ , so Proposition 17.17 yields a unique fixed point $\Omega''$ and, vectorialized there, $g = \lambda\mu\,\mathrm{id}$ : the homothety $h_{\Omega'', \lambda\mu}$ . If $\lambda\mu = 1$ the linear part is the identity, so $g$ is a translation; expanding,

g(x) = \omega' + \mu\bigl(\omega + \lambda(x - \omega) - \omega'\bigr) = x + (1 - \mu)\,\omega' + \mu(1 - \lambda)\,\omega .

For $\lambda = \mu = -1$ (point reflections) the vector is $2\omega' - 2\omega = 2\,\vect{\Omega\Omega'}$ : the composition of the point reflections in $\Omega$ then $\Omega'$ is the translation by $2\,\vect{\Omega\Omega'}$ .

Exercise 17.11 ★★

(Menelaus) In a triangle $ABC$ , let $A' \in (BC)$ , $B' \in (CA)$ , $C' \in (AB)$ , all distinct from the vertices, and define $\alpha, \beta, \gamma$ by $\vect{A'B} = \alpha\,\vect{A'C}$ , $\vect{B'C} = \beta\,\vect{B'A}$ , $\vect{C'A} = \gamma\,\vect{C'B}$ . Prove that $A', B', C'$ are aligned if and only if $\alpha\beta\gamma = 1$ . (Write each point as a barycenter of two vertices; show that three points are aligned iff their barycentric coordinate rows with respect to $(A, B, C)$ form a singular $3 \times 3$ matrix.)

Solution

Solution of Exercise 17.11.

$\vect{A'B} = \alpha\,\vect{A'C}$ says exactly $1\cdot \vect{A'B} - \alpha\,\vect{A'C} = 0$ , i.e. $A' = \operatorname{bar}(B, 1;\ C, -\alpha)$ (total weight $1 - \alpha \neq 0$ since $B \neq C$ ); likewise $B' = \operatorname{bar}(C, 1;\ A, -\beta)$ and $C' = \operatorname{bar}(A, 1;\ B, -\gamma)$ .

The alignment criterion. Give each point $P$ its normalized barycentric row $p = (p_A, p_B, p_C)$ , $p_A + p_B + p_C = 1$ , with respect to $(A, B, C)$ . If $\sum_i c_i p_i = 0$ with $(c_1, c_2, c_3) \neq 0$ for three points $P_1, P_2, P_3$ , then summing the entries gives $\sum c_i = 0$ , and $\sum_i c_i \vect{OP_i} = \sum_j \bigl(\sum_i c_ip_{ij}\bigr)\vect{OV_j} = 0$ : the $P_i$ are affinely dependent, i.e. aligned. Conversely an affine dependence $(t_i)$ gives $w = \sum t_ip_i$ with entries summing to $0$ and $\sum_j w_j\vect{OV_j} = 0$ ; expanding from $A$ , $w_B \vect{AB} + w_C\vect{AC} = 0$ , so $w = 0$ by affine independence of $(A, B, C)$ : the rows are linearly dependent. So alignment amounts to a vanishing $3 \times 3$ determinant, and scaling rows by the nonzero factors $1 - \alpha$ , $1 - \beta$ , $1 - \gamma$ changes nothing:

\det\begin{pmatrix} 0 & 1 & -\alpha\\ -\beta & 0 & 1\\ 1 & -\gamma & 0\end{pmatrix} = 1 - \alpha\beta\gamma .

Hence $A', B', C'$ are aligned iff $\alpha\beta\gamma = 1$ : Menelaus’ theorem.

Exercise 17.12 ★★★

Prove that the convex hull of a compact subset $K$ of $\R^n$ is compact. (By Theorem 17.14, $\operatorname{conv}(K)$ is the image of a compact set under a continuous map.) Show by an example in $\R^2$ that the convex hull of a closed set need not be closed.

Solution

Solution of Exercise 17.12.

Let $\Delta = \{\lambda \in \R^{n+1} : \lambda_i \geq 0,\ \sum\lambda_i = 1\}$ : closed and bounded in $\R^{n+1}$ , hence compact, and $K^{n+1}$ is compact as a finite product. The map

\Phi \colon \Delta \times K^{n+1} \to \R^n, \qquad \Phi(\lambda, x_0, \dots, x_n) = \sum_{i=0}^n \lambda_i x_i

is continuous, and Theorem 17.14 says precisely that $\operatorname{conv}(K) = \Phi(\Delta \times K^{n+1})$ : a continuous image of a compact set (Theorem 4.16), hence compact.

For a closed set: take $S = (\R \times \{0\}) \cup \{(0, 1)\}$ , closed in $\R^2$ . A convex combination putting weight $t$ on $(0,1)$ and $1 - t$ on axis points has second coordinate $t$ , so

\operatorname{conv}(S) = \bigl(\R \times \intco01\bigr) \cup \{(0,1)\}

(for $0 \leq t < 1$ , $(x, t) = t\,(0,1) + (1-t)\,\bigl(\tfrac x{1-t}, 0\bigr)$ ). The point $(1, 1) = \lim_{t \to 1}(1, t)$ is adherent but not in the hull: not closed.

17.5 Problem: from Radon to Helly, centerpoints and Jung’s theorem

The two Radon types for four points of the plane in general position: one point inside the triangle of the others (partition \A_4\ \A_1, A_2, A_3\), or convex position, where the Radon point (orange) is the intersection of the two diagonals. — The two Radon types for four points of the plane in general position: one point inside the triangle of the others (partition $\{A_4\} \mid \{A_1, A_2, A_3\}$ ), or convex position, where the Radon point (orange) is the intersection of the two diagonals.

Problem 17.1

Weekend problem — Helly’s theorem and two of its dividends

Radon’s lemma (Exercise 17.7) says that $n + 2$ points of an $n$ -dimensional affine space always split into two groups with intersecting convex hulls. This problem turns that one linear-algebra fact into a chain of theorems of combinatorial geometry: Helly’s intersection theorem, the centerpoint theorem (a two-dimensional median), and Jung’s covering theorem. Throughout, the plane is $\R^2$ with its usual Euclidean structure, and $\det$ is the determinant in the canonical basis.

Part I — Barycentric coordinates. Points $A_0, \dots, A_k$ are affinely independent when the vectors $\vect{A_0A_1}, \dots, \vect{A_0A_k}$ are linearly independent.

Show that affine independence does not depend on the choice of the base point $A_0$ , and that it is equivalent to: whenever two families of weights, each summing to $1$ , define the same barycenter of $(A_0, \dots, A_k)$ , the weights coincide.
Let $(A, B, C)$ be affinely independent in the plane. Show that every point $M$ admits a unique triple $(\alpha, \beta, \gamma)$ with $\alpha + \beta + \gamma = 1$ and $M = \operatorname{bar}(A, \alpha; B, \beta; C, \gamma)$ — its barycentric coordinates.
Prove the determinant formulas

$\alpha = \frac{\det(\vect{MB}, \vect{MC})}{\det(\vect{AB}, \vect{AC})}, \qquad \beta = \frac{\det(\vect{MC}, \vect{MA})}{\det(\vect{AB}, \vect{AC})}, \qquad \gamma = \frac{\det(\vect{MA}, \vect{MB})}{\det(\vect{AB}, \vect{AC})} :$

barycentric coordinates are ratios of signed areas.
The lines $BC$ , $CA$ , $AB$ are the coordinate lines $\{\alpha = 0\}$ , $\{\beta = 0\}$ , $\{\gamma = 0\}$ . Show that $M$ lies in the closed triangle $\operatorname{conv}\{A, B, C\}$ iff $\alpha, \beta, \gamma \geq 0$ , and that the three lines cut the plane into exactly seven regions, classified by the signs of $(\alpha, \beta, \gamma)$ (the sign pattern $(-, -, -)$ being impossible).
Let $u \colon \R^2 \to \R$ be an affine map (an affine form). Show $u(M) = \alpha\,u(A) + \beta\,u(B) + \gamma\,u(C)$ , that the level sets of a nonconstant affine form are lines, that every line arises this way, and that the closed half-planes $\{u \geq c\}$ are convex.

Part II — Radon partitions, refined. A family of $n + 2$ points of $\R^n$ is in general position when every $n + 1$ of them are affinely independent. An affine dependence of $(A_1, \dots, A_{n+2})$ is a family $(\mu_i)$ with $\sum_i \mu_i = 0$ and $\sum_i \mu_i\,\vect{OA_i} = 0$ for one (hence every) origin $O$ .

Compute a nonzero affine dependence of the four points $A_1 = (0,0)$ , $A_2 = (3,0)$ , $A_3 = (0,3)$ , $A_4 = (1,1)$ ; give the Radon partition and the Radon point.
Show that for points in general position the vector space of affine dependences has dimension exactly $1$ , and that a nonzero dependence has no vanishing coefficient.
Deduce that the Radon partition of $n + 2$ points in general position is unique (up to swapping the two blocks), each block being the set of indices where $\mu_i$ has one fixed sign.
For four points of the plane in general position, show the dichotomy: either the partition has type $(1, 3)$ — one point interior to the triangle of the other three — or type $(2, 2)$ : the four points are in convex position and the segments joining the two pairs (the diagonals) intersect, at the Radon point.
Carry out question 6 for the unit square $(0,0)$ , $(1,0)$ , $(1,1)$ , $(0,1)$ : dependence, partition, Radon point.

Part III — Helly’s theorem in the plane.

Let $C_1, C_2, C_3, C_4$ be convex subsets of $\R^2$ , any three of which have a common point. Pick $x_i \in \bigcap_{j \neq i} C_j$ and apply Radon’s lemma to $x_1, \dots, x_4$ : show that the Radon point belongs to all four sets. (For each $k$ , the block not containing $x_k$ consists of points of $C_k$ .)
(Helly) Let $C_1, \dots, C_m$ ( $m \geq 3$ ) be convex subsets of $\R^2$ , any three of which intersect. Prove $\bigcap_{i=1}^m C_i \neq \emptyset$ , by induction on $m$ : replace $C_{m-1}$ and $C_m$ by $C_{m-1} \cap C_m$ and check the hypothesis for the new family using question 11.
Three counterexamples, one per hypothesis: (a) the three closed edges of a triangle pairwise intersect but have no common point ( $3$ cannot be lowered to $2$ ); (b) the four sets $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ , for four points in general position, satisfy the triple-intersection hypothesis but not the conclusion (convexity matters); (c) the closed half-planes $H_k = \intco{k}{+\infty} \times \R$ , $k \in \N$ , pairwise and triple-wise intersect but $\bigcap_k H_k = \emptyset$ (infinite families need compactness).
(Compact Helly) Let $(K_i)_{i \in I}$ be an arbitrary family of compact convex subsets of $\R^2$ , any three of which intersect. Using question 12 and the Borel–Lebesgue property (Theorem 4.20), show $\bigcap_{i \in I} K_i \neq \emptyset$ .
(First dividend) Let $S$ be a finite set of points of the plane and $r > 0$ . Show: if every three points of $S$ lie in some closed disk of radius $r$ , then $S$ lies in one closed disk of radius $r$ . (Apply Helly to the disks $\overline D(p, r)$ , $p \in S$ .)

Part IV — The centerpoint theorem. A centerpoint of a finite set $S$ of $n$ points of the plane is a point $c$ (not necessarily in $S$ ) such that every closed half-plane containing $c$ contains at least $n/3$ points of $S$ .

(Dimension $1$ ) For reals $x_1 \leq \dots \leq x_n$ , show that the median $c = x_{\lceil n/2 \rceil}$ satisfies: every closed half-line containing $c$ contains at least $n/2$ of the $x_i$ .
(Counting lemma) If $A, B, C$ are subsets of $S$ with $\abs A, \abs B, \abs C > \tfrac{2n}3$ , show $A \cap B \cap C \neq \emptyset$ .
Let $m = \floor{2n/3} + 1$ and let $\mathcal F$ be the (finite) family of the convex hulls $\operatorname{conv}(T)$ , $T \subseteq S$ , $\abs T = m$ . Show that any three members of $\mathcal F$ have a common point, and deduce from Helly a point $c$ common to all of them.
Prove that this $c$ is a centerpoint of $S$ : the centerpoint theorem. (If a closed half-plane through $c$ contained fewer than $n/3$ points, its open complement would contain a set $T$ of $m$ points, and $\operatorname{conv}(T)$ would avoid $c$ .)
Sharpness: let $n = 3k$ and place $k$ points in each of three disks of small radius $\varepsilon$ centered at the vertices of a large triangle. Show that for every point $c$ of the plane some closed half-plane containing $c$ contains at most $n/3$ points of $S$ , so the constant $1/3$ cannot be improved. (Among the three directions from $c$ to the disk centers, two make an angle at most $2\pi/3$ .)

Part V — Jung’s theorem and synthesis.

(Triangle lemma) Let $P, Q, R$ be three points with pairwise distances $\leq 1$ . Show they lie in a closed disk of radius $1/\sqrt3$ . (If some angle is $\geq \pi/2$ , take the disk on the longest side as diameter, using the median formula $\norm{RM}^2 = \tfrac12\norm{RP}^2 + \tfrac12\norm{RQ}^2 - \tfrac14\norm{PQ}^2$ ; if the triangle is acute, bound the circumradius $a/(2\sin \widehat A)$ using its largest angle, which lies in $\intco{\pi/3}{\pi/2}$ .)
(Jung) Deduce: every compact subset of the plane of diameter $\leq 1$ is contained in a closed disk of radius $1/\sqrt3$ .
Sharpness: for the equilateral triangle $A_1A_2A_3$ of side $1$ with centroid $G$ , prove the Leibniz identity $\sum_i \norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + \sum_i \norm{\vect{GA_i}}^2$ for every point $O$ , and conclude that any disk containing the three vertices has radius $\geq 1/\sqrt3$ , with equality only for the circumdisk.
(Helly in $\R^n$ ) State and prove Helly’s theorem in $\R^n$ : if finitely many convex sets are such that any $n + 1$ of them intersect, then all of them intersect. (Radon’s lemma Exercise 17.7 handles $n + 2$ sets; then induct as in question 12.)
Synthesis. Assemble the chain

$\text{affine dependence} \Rightarrow \text{Radon} \Rightarrow \text{Helly} \Rightarrow \text{centerpoint and Jung},$

indicating in one sentence each: where linear algebra enters, where the signs of the weights enter, where convexity enters, and which single step used the dimension of the plane. What do the constants $3$ (in Helly), $1/3$ (centerpoint) and $1/\sqrt3$ (Jung) become in $\R^n$ ? (State without proof.)

Solution

Solution of Problem 17.1.

1. Rebase at $A_j$ : for $i \neq j$ , $\vect{A_jA_i} = \vect{A_0A_i} - \vect{A_0A_j}$ . If $\sum_{i \neq j} c_i\vect{A_jA_i} = 0$ , expanding gives $\sum_{i \notin \{0, j\}} c_i\,\vect{A_0A_i} - \bigl(\sum_{i\neq j} c_i\bigr)\vect{A_0A_j} = 0$ ; independence of the $\vect{A_0A_i}$ forces $c_i = 0$ for $i \notin \{0, j\}$ , then $c_0 = 0$ : independence at $A_j$ . For the equivalence: two weight families $(\lambda_i)$ , $(\lambda_i')$ summing to $1$ with the same barycenter give, with $\nu = \lambda - \lambda'$ : $\sum\nu_i = 0$ and (origin $A_0$ ) $\sum_{i \geq 1}\nu_i\,\vect{A_0A_i} = 0$ , so $\nu = 0$ under independence. Conversely a nontrivial relation $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ , completed by $\mu_0 = -\sum_{i\geq1} \mu_i$ , lets one add $t(\mu_i)$ to any weight family without moving the barycenter: non-uniqueness.

2. $(\vect{AB}, \vect{AC})$ is a basis of $\R^2$ : write $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ (unique) and set $\alpha = 1 - \beta - \gamma$ ; the barycenter condition at origin $A$ reads exactly $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ . Uniqueness is question 1.

3. From $\alpha\vect{MA} + \beta\vect{MB} + \gamma\vect{MC} = 0$ and Chasles, $\vect{MA} = -\beta\,\vect{AB} - \gamma\,\vect{AC}$ . With $D = \det(\vect{AB}, \vect{AC})$ :

\begin{align*} \det(\vect{MB}, \vect{MC}) &= \det(\vect{MA} + \vect{AB},\ \vect{MA} + \vect{AC})\\ &= \det(\vect{MA}, \vect{AC}) + \det(\vect{AB}, \vect{MA}) + D = -\beta D - \gamma D + D = \alpha D, \end{align*}

using bilinearity and $\det(\vect{MA}, \vect{AC}) = -\beta D$ , $\det(\vect{AB}, \vect{MA}) = -\gamma D$ . The other two formulas follow by the same computation with the roles permuted cyclically.

4. By definition $\operatorname{conv}\{A, B, C\}$ is the set of barycenters with nonnegative weights; normalizing the weights to sum $1$ and invoking uniqueness (question 2), $M \in \operatorname{conv}\{A,B,C\}$ iff $\alpha, \beta, \gamma \geq 0$ . Each coordinate is an affine function of $M$ (question 3: a $2\times2$ determinant with one column affine in $M$ ), so each open sign condition defines an open half-plane. The pattern $(-,-,-)$ contradicts $\alpha + \beta + \gamma = 1$ ; each of the remaining seven patterns is realized: scale a sign-respecting triple with at least one $+$ entry so that the (positive) sum is $1$ — e.g. $(-1, 1, 1)$ , $(3, -1, -1)$ , $(\frac13, \frac13, \frac13)$ , and permutations.

5. An affine map preserves barycenters (Definition 17.5), so $u(M) = \alpha u(A) + \beta u(B) + \gamma u(C)$ . Writing $u(x, y) = ax + by + c$ with $(a, b) \neq (0,0)$ : $\{u = c'\}$ is a line, and every line $ax + by = c'$ is such a level set. If $u(M), u(N) \geq c$ and $t \in \intcc01$ , then $u\bigl(\operatorname{bar}(M, 1-t; N, t)\bigr) = (1-t)u(M) + tu(N) \geq c$ : half-planes are convex.

6. The conditions $\sum\mu_i = 0$ , $3\mu_2 + \mu_4 = 0$ , $3\mu_3 + \mu_4 = 0$ give (taking $\mu_4 = 3$ ) the dependence $(\mu_1, \mu_2, \mu_3, \mu_4) = (-1, -1, -1, 3)$ . Signs split as $\{A_4\} \mid \{A_1, A_2, A_3\}$ , and normalizing each side by $3$ :

A_4 = \operatorname{bar}\bigl(A_1, \tfrac13;\ A_2, \tfrac13;\ A_3, \tfrac13\bigr) = (1,1),

the centroid of the triangle: the Radon point is $A_4$ itself, which indeed lies inside the triangle $A_1A_2A_3$ .

7. The linear map $\Phi \colon \R^{n+2} \to \R \times \R^n$ , $\mu \mapsto (\sum\mu_i,\ \sum\mu_i\vect{OA_i})$ , has rank $\leq n + 1$ , so $\dim\ker \Phi \geq 1$ . If two independent dependences $\mu, \mu'$ existed, a suitable combination $\nu = \mu'_{n+2}\mu - \mu_{n+2}\mu'$ (or $\mu$ itself if both last coefficients vanish) would be a nonzero dependence with $\nu_{n+2} = 0$ ; restricting to $A_1, \dots, A_{n+1}$ and rebasing at $A_1$ , some $\nu_i \neq 0$ with $i \geq 2$ (a single nonzero weight cannot sum to zero), giving a nontrivial relation $\sum_{i\geq2}\nu_i\vect{A_1A_i} = 0$ : the $n+1$ points would be affinely dependent, against general position. So $\dim\ker \Phi = 1$ . The same restriction argument shows a nonzero dependence has no vanishing coefficient.

8. Let $\mu \neq 0$ be a dependence, $P = \{i : \mu_i > 0\}$ and $N = \{i : \mu_i < 0\}$ : both nonempty ( $\sum\mu_i = 0$ , $\mu \neq 0$ ) and exhaustive (no zero coefficient). Radon’s construction (Exercise 17.7) produces the common hull point from exactly this partition. Since the dependence is unique up to a nonzero scalar (question 7), the unordered pair $\{P, N\}$ — hence the Radon partition — is unique.

9. Blocks are nonempty, so the type is $(1,3)$ or $(2,2)$ . Type $(1,3)$ , block $\{j\}$ : the Radon point lies in $\operatorname{conv}\{A_j\} = \{A_j\}$ , so $A_j \in \operatorname{conv}$ of the other three; it cannot lie on an edge (three of the points would be aligned, against general position), so $A_j$ is interior to the triangle. Type $(2,2)$ , blocks $\{i,j\} \mid \{k,l\}$ : the Radon point $z$ lies on $\intcc{A_i}{A_j} \cap \intcc{A_k}{A_l}$ , and $z$ is not an endpoint (that would align three points): the two segments cross at an interior point. Moreover no point lies in the hull of the others: such a containment $A_l = \operatorname{bar}(A_i, \lambda_i)_{i \neq l}$ with $\lambda_i \geq 0$ is an affine dependence with sign pattern $(+,+,+,-)$ , which by uniqueness (question 8) would make the partition $(1,3)$ . So in the $(2,2)$ case the four points are in convex position and the crossing segments are the diagonals.

10. The equations $\mu_2 + \mu_3 = 0$ , $\mu_3 + \mu_4 = 0$ , $\sum\mu_i = 0$ give the dependence $(1, -1, 1, -1)$ : partition $\{(0,0), (1,1)\} \mid \{(1,0), (0,1)\}$ , and

\operatorname{bar}\bigl((0,0), \tfrac12;\ (1,1), \tfrac12\bigr) = \bigl(\tfrac12, \tfrac12\bigr) = \operatorname{bar}\bigl((1,0), \tfrac12;\ (0,1), \tfrac12\bigr) :

the Radon point is the center of the square, where the two diagonals cross — type $(2,2)$ , as the picture predicts.

11. Radon applied to $x_1, \dots, x_4$ gives blocks $I \mid J$ and a point $z \in \operatorname{conv}\{x_i : i \in I\} \cap \operatorname{conv}\{x_j : j \in J\}$ . Fix $k \in \{1, \dots, 4\}$ , say $k \in I$ . Every $j \in J$ satisfies $j \neq k$ , so $x_j \in C_k$ by the choice $x_j \in \bigcap_{l \neq j}C_l$ ; since $C_k$ is convex, $z \in \operatorname{conv}\{x_j : j \in J\} \subseteq C_k$ . As $k$ was arbitrary, $z \in C_1 \cap C_2 \cap C_3 \cap C_4$ .

12. Induction on $m$ . For $m = 3$ the hypothesis is the conclusion; $m = 4$ is question 11. Let $m \geq 4$ , assume the statement for $m$ sets, and take $C_1, \dots, C_{m+1}$ with the triple-intersection property. Set $C_m' = C_m \cap C_{m+1}$ , convex. The family $C_1, \dots, C_{m-1}, C_m'$ has $m$ members; a triple avoiding $C_m'$ intersects by hypothesis, and a triple $\{C_i, C_j, C_m'\}$ has intersection $C_i \cap C_j \cap C_m \cap C_{m+1}$ , nonempty by question 11 applied to $C_i, C_j, C_m, C_{m+1}$ (any three of these meet, by hypothesis). The induction hypothesis now yields a common point of the new family, i.e. of all $m+1$ sets.

13. (a) The closed edges $\intcc PQ$ , $\intcc QR$ , $\intcc RP$ of a nondegenerate triangle: any two share a vertex, but a common point of all three would lie in $\intcc PQ \cap \intcc RP = \{P\}$ and in $\intcc QR$ , which excludes $P$ . (b) Any three of the sets $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ omit three of the four points, leaving exactly one common point; the total intersection omits every point. The $S_i$ are finite, not convex: convexity is essential. (c) Finitely many $H_k = \intco{k}{+\infty} \times \R$ intersect in $\intco{k_{\max}}{+\infty} \times \R \neq \emptyset$ , yet no point has $x \geq k$ for all $k \in \N$ : for infinite families, compactness is essential.

14. Suppose $\bigcap_{i \in I}K_i = \emptyset$ and fix $i_0$ . Every $x \in K_{i_0}$ misses some $K_i$ , so $K_{i_0} \subseteq \bigcup_{i \in I}(\R^2 \setminus K_i)$ , a cover by open sets ( $K_i$ is compact, hence closed). By Borel–Lebesgue (Theorem 4.20) finitely many suffice: $K_{i_0} \cap K_{i_1} \cap \dots \cap K_{i_N} = \emptyset$ . But any three members of this finite family of convex sets intersect, so question 12 makes the intersection nonempty: contradiction.

15. Set $D_p = \overline D(p, r)$ for $p \in S$ : compact convex sets. For $p, q, s \in S$ , the hypothesis gives a closed disk $\overline D(z, r)$ containing $p, q, s$ ; then $\norm{\vect{zp}}, \norm{\vect{zq}}, \norm{\vect{zs}} \leq r$ , i.e. $z \in D_p \cap D_q \cap D_s$ . By Helly (question 12; the family is finite) there is $c \in \bigcap_{p \in S}D_p$ : every $p \in S$ satisfies $\norm{\vect{cp}} \leq r$ , so $S \subseteq \overline D(c, r)$ .

16. Let $c = x_{\lceil n/2\rceil}$ . A closed half-line containing $c$ is $\intoc{-\infty}{t}$ with $t \geq c$ or $\intco{t}{+\infty}$ with $t \leq c$ . The first contains $x_1, \dots, x_{\lceil n/2\rceil}$ : at least $\lceil n/2\rceil \geq n/2$ points. The second contains $x_{\lceil n/2\rceil}, \dots, x_n$ : exactly $n - \lceil n/2\rceil + 1 = \floor{n/2} + 1 > n/2$ points.

17. $\abs{A \cap B} = \abs A + \abs B - \abs{A \cup B} \geq \abs A + \abs B - n > \tfrac{4n}3 - n = \tfrac n3$ , then

\abs{A \cap B \cap C} \geq \abs{A \cap B} + \abs C - n > \tfrac n3 + \tfrac{2n}3 - n = 0 .

18. Note $m > 2n/3$ . For $T_1, T_2, T_3 \subseteq S$ of cardinality $m$ , question 17 provides a point $x \in T_1 \cap T_2 \cap T_3$ ; then $x \in \operatorname{conv}(T_i)$ for each $i$ : any three members of $\mathcal F$ meet. The family is finite (finitely many subsets of $S$ ) and consists of convex sets, so Helly (question 12) gives $c \in \bigcap_{\abs T = m}\operatorname{conv}(T)$ .

19. Suppose some closed half-plane $H \ni c$ contains fewer than $n/3$ points of $S$ . Its complement $U$ is an open half-plane, convex, with $\abs{S \cap U} > 2n/3$ , hence $\abs{S \cap U} \geq \floor{2n/3} + 1 = m$ ; choose $T \subseteq S \cap U$ with $\abs T = m$ . Then $\operatorname{conv}(T) \subseteq U$ by convexity of $U$ , so $c \in \operatorname{conv}(T) \subseteq U$ : contradiction with $c \in H$ . Hence every closed half-plane containing $c$ contains at least $n/3$ points: $c$ is a centerpoint.

20. Take the triangle equilateral of side $L$ and $\varepsilon = L/100$ . Let $c$ be any point; we exhibit a closed half-plane containing $c$ and at most $k$ points.

Case 1: $c$ is within $L/10$ of a vertex, say $B$ . Directions from $c$ to $A$ and to $C$ deviate from the directions $B \to A$ , $B \to C$ by at most $\arcsin\bigl(\tfrac{L/10}{9L/10}\bigr) = \arcsin\tfrac19$ , so they make an angle $\leq \tfrac\pi3 + 2\arcsin\tfrac19 < \tfrac{2\pi}3$ . Case 2: $c$ is at distance $> L/10$ from all vertices. If $c$ is in the triangle, the three angular gaps between the directions $u_A, u_B, u_C$ from $c$ to the vertices sum to $2\pi$ , so some gap is $\leq 2\pi/3$ ; if $c$ is outside, the three directions lie in an open half-plane of directions and two of them make an angle $< \pi/2$ . In every case two directions, say toward $X$ and $Y$ , make an angle $\leq 2\pi/3$ ; let $w$ be their unit bisector, so $\langle u_X, w\rangle, \langle u_Y, w\rangle \geq \cos\tfrac\pi3 = \tfrac12$ . For any point $b$ of the disk around $X$ :

\langle \vect{cb}, w\rangle \geq \tfrac12\norm{\vect{cX}} - \varepsilon > 0,

since $\norm{\vect{cX}} \geq L/10 > 2\varepsilon$ (and likewise for $Y$ ): the open half-plane $\{\langle \vect{cx}, w\rangle > 0\}$ swallows both clusters. Its closed complement contains $c$ and at most the $k$ points of the third cluster. So no point of the plane beats $n/3$ : with question 19, the centerpoint constant is exactly $1/3$ .

21. Order the angles; the largest, $\theta$ , satisfies $\theta \geq \pi/3$ (the three sum to $\pi$ ). If $\theta \geq \pi/2$ , say at $R$ , let $M$ be the midpoint of the opposite side $\intcc PQ$ . The median formula ( $\vect{RM} = \tfrac12(\vect{RP} + \vect{RQ})$ , expand and eliminate $\langle\vect{RP}, \vect{RQ}\rangle$ with the law of cosines) gives

\norm{\vect{RM}}^2 = \tfrac12\norm{\vect{RP}}^2 + \tfrac12\norm{\vect{RQ}}^2 - \tfrac14\norm{\vect{PQ}}^2 \leq \tfrac12\norm{\vect{PQ}}^2 - \tfrac14\norm{\vect{PQ}}^2 = \tfrac14\norm{\vect{PQ}}^2,

using $\norm{\vect{PQ}}^2 = \norm{\vect{RP}}^2 + \norm{\vect{RQ}}^2 - 2\langle\vect{RP}, \vect{RQ}\rangle \geq \norm{\vect{RP}}^2 + \norm{\vect{RQ}}^2$ (the inner product is $\leq 0$ ). So the disk of diameter $\intcc PQ$ , of radius $\leq \tfrac12 < \tfrac1{\sqrt3}$ , contains all three points (degenerate aligned triples fall under $\theta = \pi$ ). If $\theta < \pi/2$ the triangle is acute; by the law of sines the circumradius is $R_c = a/(2\sin\theta)$ with $a \leq 1$ the side opposite $\theta$ , and $\theta \in \intco{\pi/3}{\pi/2}$ gives $\sin\theta \geq \sqrt3/2$ , so $R_c \leq 1/\sqrt3$ : the circumdisk does the job.

22. For $p \in S$ let $K_p = \overline D(p, 1/\sqrt3)$ : compact convex. Any three points $p, q, s$ of $S$ are pairwise at distance $\leq 1$ , so question 21 gives a disk of radius $1/\sqrt3$ containing them: its center lies in $K_p \cap K_q \cap K_s$ . By compact Helly (question 14, arbitrary families allowed) there is $c \in \bigcap_{p\in S}K_p$ : every $p \in S$ is within $1/\sqrt3$ of $c$ , i.e. $S \subseteq \overline D(c, 1/\sqrt3)$ . This is Jung’s theorem in the plane.

23. With $G$ the centroid, $\sum_i\vect{GA_i} = 0$ , so

\sum_i\norm{\vect{OA_i}}^2 = \sum_i\norm{\vect{OG} + \vect{GA_i}}^2 = 3\norm{\vect{OG}}^2 + 2\Bigl\langle \vect{OG}, \sum_i\vect{GA_i}\Bigr\rangle + \sum_i\norm{\vect{GA_i}}^2,

and the middle term vanishes: the Leibniz identity. For the equilateral triangle of side $1$ , $\norm{\vect{GA_i}} = 1/\sqrt3$ (two thirds of the height $\sqrt3/2$ ), so $\sum_i\norm{\vect{GA_i}}^2 = 1$ . If $\overline D(O, r)$ contains the vertices, then $3r^2 \geq \sum_i\norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + 1 \geq 1$ : $r \geq 1/\sqrt3$ , with equality forcing $O = G$ and all three distances equal to $r$ — the circumdisk. Jung’s constant $1/\sqrt3$ is sharp.

24. Helly in $\R^n$ : if $C_1, \dots, C_m$ ( $m \geq n + 1$ ) are convex subsets of $\R^n$ and any $n + 1$ of them intersect, then all of them do. Base case $m = n + 2$ : pick $x_i \in \bigcap_{j\neq i}C_j$ ; Radon’s lemma (Exercise 17.7) splits $x_1, \dots, x_{n+2}$ into blocks $I \mid J$ with a common hull point $z$ , and for each $k$ , the block not containing $k$ consists of points of $C_k$ , so $z \in C_k$ by convexity, exactly as in question 11. Induction step for $m \geq n + 2$ : replace $C_m, C_{m+1}$ by $C_m \cap C_{m+1}$ ; an $(n+1)$ -tuple of the new family containing the intersected member amounts to $n + 2$ of the old sets, handled by the base case, and the other tuples are covered by hypothesis. Conclude by the induction hypothesis.

25. Linear algebra enters once: $n + 2$ vectors in the $(n+1)$ -dimensional space of pairs (total weight, weighted position) must be dependent — that is the affine dependence. The signs of its coefficients split the points into the two Radon blocks and turn one linear relation into an equality of two nonnegative barycenters. Convexity is used exactly twice: in Helly’s step (the hull of points of $C_k$ stays in $C_k$ ) and in the applications (half-planes and disks are convex). The dimension of the plane entered only through the number $4 = 2 + 2$ of points fed to Radon, i.e. the “ $3 = 2 + 1$ ” in Helly’s hypothesis; everything else was dimension-free, as question 24 confirms. In $\R^n$ the constants become: Helly number $n + 1$ ; centerpoint constant $\frac1{n+1}$ (every finite set has a point every closed half-space through which contains a fraction $\geq \frac1{n+1}$ of it); Jung radius $\sqrt{\frac{n}{2(n+1)}}$ for sets of diameter $1$ — equal to $1/\sqrt3$ when $n = 2$ .