Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

17Affiene ruimten

Vectorruimten hebben een bevoorrecht punt — de oorsprong — dat de meetkunde niet wil. Een affiene ruimte is een vectorruimte die haar oorsprong is vergeten: punten en vectoren worden verschillende soorten, verbonden door translatie. Dit korte hoofdstuk bouwt het woordenboek (punten, barycentra, affiene deelruimten en afbeeldingen), de affiene kijk op convexiteit, en de classificatietools die in de volgende meetkundige hoofdstukken worden gebruikt.

17.1 Punten en vectoren

Definitie 17.1

Een affiene ruimte gericht door een reële vectorruimte $E$ is een niet-lege verzameling $\mathcal{E}$ met een afbeelding $(A, B) \mapsto \vect{AB} \in E$ die voldoet aan

\vect{AB} + \vect{BC} = \vect{AC} \quad \text{(Chasles)}, \qquad \text{voor elke } A,\ B \mapsto \vect{AB} \text{ is een bijectie } \mathcal{E} \to E .

Men schrijft $B = A + u$ voor het unieke punt met $\vect{AB} = u$ . De dimensie van $\mathcal{E}$ is $\dim E$ . Elke vectorruimte is een affiene ruimte over zichzelf ( $\vect{AB} = B - A$ ); elke keuze van oorsprong $O \in \mathcal{E}$ identificeert $\mathcal{E}$ met $E$ via $M \mapsto \vect{OM}$ .

Voorbeeld 17.2 (Een affiene ruimte zonder natuurlijke oorsprong)

Het oplossingsvlak $\mathcal E = \{(x, y, z) \in \R^3 : x + y + z = 1\}$ is geen vectordeelruimte ( $0 \notin \mathcal E$ ), maar wel een affiene ruimte gericht door $E = \{x + y + z = 0\}$ : voor $A, B \in \mathcal E$ landt het verschil $\vect{AB} = B - A$ in $E$ (de sommen heffen elkaar op), Chasles is geërfd van $\R^3$ , en $B \mapsto \vect{AB}$ is bijectief op $E$ . Geen punt van $\mathcal E$ is onderscheiden — elke keuze van “oorsprong” $O \in \mathcal E$ werkt even goed, en alle identificaties $M \mapsto \vect{OM}$ verschillen door translaties. Dit is de typische situatie: oplossingsverzamelingen van inhomogene lineaire problemen (lineaire stelsels, lineaire differentiaalvergelijkingen in Hoofdstuk 16) zijn affien, nooit lineair, en de slogan “particuliere oplossing plus kern” is precies de uitspraak $\mathcal F = A + F$ van de volgende definitie.

Definitie 17.3 (Barycentrum)

Zij $(A_i, \lambda_i)_{i \leq k}$ gewogen punten met $\sum\lambda_i \neq 0$ . Het barycentrum $G = \operatorname{bar}\bigl((A_i, \lambda_i)\bigr)$ is het unieke punt met

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

Barycentra zijn associatief (deelgroepen van punten mogen worden vervangen door hun partiële barycentrum met het samengenomen gewicht) en invariant onder herschaling van alle gewichten.

Bewijs van bestaan en de formules. Fixeer $O$ en schrijf $s = \sum_i\lambda_i \neq 0$ . Via 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},

wat $G = O + \frac1s\sum_i\lambda_i\vect{OA_i}$ uniek bepaalt. Onafhankelijkheid van $O$ : voor een andere oorsprong $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} :

hetzelfde punt $G$ . Associativiteit: splits de indexverzameling als $I \sqcup J$ met $s_I = \sum_{i\in I}\lambda_i \neq 0$ , en zij $G_I$ het barycentrum van $(A_i, \lambda_i)_{i\in I}$ , zodat $\sum_{i\in I}\lambda_i\vect{OA_i} = s_I\,\vect{OG_I}$ . Dan

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 het barycentrum van $(G_I, s_I)$ samen met $(A_j, \lambda_j)_{j\in J}$ , zoals beweerd. Herschaling: vervanging van elke $\lambda_i$ door $t\lambda_i$ ( $t \neq 0$ ) vermenigvuldigt $s$ en de gewogen som met $t$ , en laat $\vect{OG}$ onveranderd. ∎

Opmerking 17.4 (Klassieke valkuilen)

Twee vallen omringen de definitie. Ten eerste, als de gewichten tot nul sommeren, is er geen barycentrum: de afbeelding $O \mapsto \sum\lambda_i\vect{OA_i}$ is dan onafhankelijk van $O$ en definieert een vector, geen punt — bijvoorbeeld encodeert $(A, -1;\ B, 1)$ de vector $\vect{AB}$ . Bijhouden welk van de twee objecten een berekening oplevert is de helft van de barycentrische hygiëne. Ten tweede zijn gewichten alleen betekenisvol op een gemeenschappelijke niet-nul factor na; formules als “de coördinaten van $G$ zijn $\lambda_1, \dots, \lambda_k$ ” veronderstellen een normalisatie (meestal $\sum\lambda_i = 1$ ), en vergeten te normaliseren is de standaardbron van foute verhoudingen op een figuur.

Definitie 17.5 (Affiene deelruimten; affiene afbeeldingen)

Een affiene deelruimte is een verzameling $\mathcal{F} = A + F = \{A + u : u \in F\}$ met $F$ een vectordeelruimte (haar richting); equivalent, een niet-lege verzameling die stabiel is onder barycentra. Affiene deelruimten van $\R^n$ zijn precies de oplossingsverzamelingen van lineaire stelsels $MX = B$ (Jaar 1: particuliere oplossing plus kern). Een afbeelding $f \colon \mathcal{E} \to \mathcal{E}'$ is affien wanneer ze barycentra behoudt — equivalent wanneer

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

voor een (unieke) lineaire afbeelding $\varphi = \vec f$ , het lineaire deel. Affiene afbeeldingen van $\R^n$ : $X \mapsto MX + C$ . Samenstellingen zijn affien met samengestelde lineaire delen; $f$ is bijectief dan en slechts dan als $\vec f$ dat is.

Bewijs van de equivalentie voor afbeeldingen. Als $f(A + u) = f(A) + \varphi(u)$ : voor een barycentrum $G$ van $(A_i, \lambda_i)$ , door elk punt uit $A$ te ontwikkelen, $f(G) = f(A) + \varphi(\vect{AG})$ en $\varphi(\vect{AG}) = \frac{\sum\lambda_i\varphi(\vect{AA_i})}{\sum\lambda_i}$ : $f(G)$ is het barycentrum van de beelden. Omgekeerd, fixeer $A$ en definieer $\varphi(u) = \vect{f(A)\,f(A + u)}$ . Homogeniteit: $A + tu = \operatorname{bar}\bigl(A, 1-t;\ A + u, t\bigr)$ voor elke reële $t$ , dus behoud van barycentra (met willekeurige reële gewichten, zoals verondersteld) geeft direct $\varphi(tu) = t\,\varphi(u)$ . Additiviteit: $A + u + v = \operatorname{bar}\bigl(A + 2u, \tfrac12;\ A + 2v, \tfrac12\bigr)$ , dus $\varphi(u + v) = \tfrac12\varphi(2u) + \tfrac12\varphi(2v) = \varphi(u) + \varphi(v)$ , via homogeniteit. Dus is $\varphi$ lineair. ∎

Opmerking 17.6

Het bewijs gebruikte barycentra met willekeurige reële gewichten: de homogeniteitsstap neemt $t$ buiten $\intcc01$ . Als een afbeelding slechts barycentra met niet-negatieve gewichten behoudt — equivalent midpunten en segmenten — komt lineariteit van de vectorafbeelding niet gratis: men verkrijgt alleen $\Q$ -lineariteit, en een continuïteitshypothese is nodig om te concluderen, precies als in Oefening 17.5. Het onderscheid tussen “behoudt alle barycentra” en “behoudt convexe combinaties” is een klein maar reëel subtiliteit van de affiene woordenschat.

Voorbeeld 17.7 (Klassieke barycentrische meetkunde)

Het zwaartepunt van een driehoek $ABC$ is het barycentrum $G = \operatorname{bar}(A,1; B,1; C,1)$ . Associativiteit met het midden $A' = \operatorname{bar}(B, 1; C, 1)$ toont

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

$G$ ligt op de zwaartelijn $AA'$ op twee derden ervan — en evenzo voor de andere twee zwaartelijnen: de drie zwaartelijnen zijn concurrent, in één regel barycentrische rekenkunde.

Voorbeeld 17.8 (De bimedianen van een vierhoek)

Zij $ABCD$ een willekeurige vierhoek (vlak of niet!) en beschouw haar bimedianen: de segmenten die de midpunten van overstaande zijden verbinden, $M_{AB}M_{CD}$ en $M_{BC}M_{DA}$ . Introduceer het barycentrum $G$ van $(A,1; B,1; C,1; D,1)$ en groepeer de gewichten op twee manieren:

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

$G$ is het midden van beide bimedianen — dus bisecteren de twee bimedianen elkaar altijd, en de vierhoek van de vier midpunten is een parallellogram (haar diagonalen zijn de bimedianen). Geen gevalonderscheid, geen coördinaten, en het argument overleeft onveranderd voor een scheve vierhoek in $\R^3$ , waar een bewijs op basis van een tekening al delicaat zou zijn: associativiteit geeft niet om dimensie.

Voorbeeld 17.9 (Een affiene afbeelding classificeren, van begin tot eind)

Zij $f(x, y) = (2x - 1,\ 3y - 4)$ op $\R^2$ . Haar lineaire deel is $\varphi = \operatorname{diag}(2, 3)$ , waarvan het spectrum $\{2, 3\}$ de $1$ vermijdt: door het criterium van vaste punten hieronder (Propositie 17.17) heeft $f$ precies één vast punt, gevonden door op te lossen

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

Hercentreren in $\Omega$ (stel $x = 1 + u$ , $y = 2 + v$ ):

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

in het raam in $\Omega$ is $f$ haar lineaire deel, een anisotrope dilatie die met factor $2$ horizontaal en $3$ verticaal uitrekt vanuit het centrum $(1, 2)$ . De algemene les: een affiene afbeelding is “lineaire afbeelding plus locatiegegevens”, en de locatiegegevens storten in tot één goed gekozen oorsprong wanneer $1$ geen eigenwaarde is. Omgekeerd creëert een slechte keuze van oorsprong de constante termen: affiene meetkunde is de kunst van waar je $0$ zet.

Opmerking 17.10 (Methode: concurrentie en collineariteit via barycentra)

Voorbeeld 17.7 is een instantie van een algemeen recept. Om te bewijzen dat drie cevianen van een driehoek concurrent zijn, vertoon één gewogen stelsel $(A, \alpha; B, \beta; C, \gamma)$ en gebruik associativiteit op drie manieren: groeperen van $(B, C)$ toont dat het barycentrum op de ceviaan vanuit $A$ ligt, groeperen van $(C, A)$ op de ceviaan vanuit $B$ , groeperen van $(A, B)$ op de derde. Voor de zwaartelijnen doet het stelsel $(A, 1; B, 1; C, 1)$ al het werk; voor cevianen die de zijden in voorgeschreven verhoudingen snijden, worden de gewichten van de verhoudingen afgelezen. Om te bewijzen dat drie punten collineair zijn, schrijf er één als barycentrum van de andere twee (Oefening 17.2), of gebruik het determinantcriterium van Oefening 17.11. Beide recepten vervangen meetkundige vindingrijkheid door gewichtenboekhouding — dat is precies waarvoor barycentrische rekenkunde dient.

17.2 Convexiteit, affien

Definitie 17.11

Een deelverzameling $C$ van een affiene ruimte is convex wanneer ze elk barycentrum met niet-negatieve gewichten van haar punten bevat — equivalent, elk segment $\intcc{A}{B} = \{\operatorname{bar}(A, 1-t; B, t) : t \in \intcc{0}{1}\}$ tussen haar punten. De convexe omhulling $\operatorname{conv}(S)$ is de verzameling van alle barycentra met niet-negatieve gewichten van punten van $S$ — de kleinste convexe verzameling die $S$ bevat.

Voorbeeld 17.12 (Epigrafen zijn convexe verzamelingen)

Het gebied $C = \{(x, y) : y \geq x^2\}$ boven de parabool is convex: voor $(x_1, y_1), (x_2, y_2) \in C$ en $t \in \intcc01$ geeft de convexiteitsongelijkheid van de kwadraatfunctie

\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 ,

zodat het barycentrum boven de parabool blijft. De berekening is algemeen: $\{y \geq f(x)\}$ is convex precies wanneer $f$ een convexe functie is — convexe verzamelingen en convexe functies (Hoofdstuk 8) zijn twee gezichten van één begrip, met epigrafen als woordenboek. Dit is de meetkundige reden dat steunlijnen bestaan voor convexe functies, het feit dat Jensens ongelijkheid zal bewijzen in Hoofdstuk 22.

Voorbeeld 17.13 (Redundante generatoren van een convexe omhulling)

Zij

S = \bigl\{(0,0),\ (2,0),\ (2,2),\ (0,2),\ (1,1)\bigr\}.

Het vijfde punt is het barycentrum

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

dus het ligt al in de omhulling van de andere vier: $\operatorname{conv}(S)$ is het vierkant met de vier hoeken als hoekpunten. In het algemeen kan een punt van $S$ dat een barycentrum met niet-negatieve gewichten is van de andere punten van $S$ worden weggelaten zonder de omhulling te veranderen; de punten die nooit weggelaten kunnen worden (hier de vier hoeken) zijn de extreme punten van de omhulling. Die bepalen is een pure barycentrumberekening: $(2,0)$ bijvoorbeeld kan niet worden geschreven als $\operatorname{bar}$ van de resterende punten met niet-negatieve gewichten, omdat de eerste coördinaat al het gewicht op punten met $x = 2$ zou dwingen, en de tweede coördinaat dan faalt. Convexiteitsvragen herleiden, keer op keer, tot het oplossen van kleine gewogen stelsels.

Stelling 17.14 (Carathéodory)

In een affiene ruimte van dimensie $n$ is elk punt van $\operatorname{conv}(S)$ een barycentrum van ten hoogste $n + 1$ punten van $S$ .

Bewijs. Zij $G = \operatorname{bar}(A_0, \lambda_0; \dots; A_k, \lambda_k)$ met $\lambda_i > 0$ , $\sum\lambda_i = 1$ , en $k + 1 > n + 1$ punten. De $k$ vectoren $\vect{A_0A_i}$ ( $i \geq 1$ ) zijn lineair afhankelijk ( $k > n$ ): $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ niet-triviaal; met $\mu_0 = -\sum_{i\geq1}\mu_i$ krijgen we gewichten $(\mu_i)$ met $\sum\mu_i = 0$ , $\sum \mu_i\,\vect{OA_i} = 0$ (elke $O$ ), niet alle nul. Dan produceren voor elke reële $t$ de gewichten $\lambda_i - t\mu_i$ nog steeds som $1$ en, omdat $\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} :

ze leveren het zelfde punt $G$ . Schuif nu $t$ vanaf $0$ : enige $\mu_i$ is positief (ze sommeren tot nul en zijn niet alle nul), dus

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

is welgedefinieerd en positief. Bij $t = t^*$ : voor indices met $\mu_i > 0$ geldt $\lambda_i - t^*\mu_i \geq 0$ door minimaliteit, met gelijkheid bij een minimerende index; voor indices met $\mu_i \leq 0$ , $\lambda_i - t^*\mu_i \geq \lambda_i > 0$ . Alle gewichten blijven niet-negatief en ten minste één is gestorven: $G$ is herschreven als barycentrum van minder punten. Itereer zolang er meer dan $n + 1$ punten overblijven. ∎

Voorbeeld 17.15

In het vlak ( $n = 2$ ): elk punt van de convexe omhulling van een eindige verzameling ligt in een driehoek met hoekpunten in de verzameling — de meetkundige inhoud van Carathéodory, gebruikt in optimalisatie en waarschijnlijkheid (mengsels) gelijkelijk.

Voorbeeld 17.16 (Het algoritme van Carathéodory uitvoeren)

Schrijf het centrum van het vierkant van Voorbeeld 17.13 met de vier hoeken $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),

vier punten in dimensie $2$ — één te veel. Het recept van het bewijs vraagt om gewichten $(\mu_i)$ met $\sum\mu_i = 0$ en $\sum\mu_i\vect{OA_i} = 0$ : hier werkt $\mu = (1, -1, 1, -1)$ (de twee diagonalen delen hun midden). Schuiven van $\lambda_i \mapsto \lambda_i - t\mu_i$ houdt het barycentrum vast voor elke $t$ ; de extreme toelaatbare waarde $t = \frac14$ maakt de gewichten $(0, \tfrac12, 0, \tfrac12)$ , en doodt $A_1$ en $A_3$ tegelijk:

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

een voorstelling door twee punten — zelfs beter dan de drie die de stelling garandeert, omdat het centrum toevallig op een segment tussen generatoren ligt. Het algoritme is geheel mechanisch: vind een afhankelijkheidsrelatie, schuif tot een gewicht sterft, herhaal.

17.3 Affiene classificatietools

Propositie 17.17 (Vaste punten van affiene afbeeldingen)

Zij $f$ een affien endomorfisme van een eindigdimensionale affiene ruimte met lineair deel $\varphi$ . Als $1 \notin \operatorname{Sp}(\varphi)$ , dan heeft $f$ precies één vast punt $\Omega$ , en in de vectorialisatie in $\Omega$ is $f$ haar lineaire deel. (Translaties, met $\varphi = \mathrm{id}$ en geen vast punt, zijn de basale obstructie.)

Bewijs. Fixeer $O$ en schrijf $f(O + x) = f(O) + \varphi(x)$ . Het punt $O + x$ is vast dan en slechts dan als $O + x = f(O) + \varphi(x)$ , d.w.z.

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

In eindige dimensie is $\mathrm{id} - \varphi$ inverteerbaar dan en slechts dan als $0$ geen eigenwaarde is van $\mathrm{id} - \varphi$ , d.w.z. $1 \notin \operatorname{Sp}\varphi$ — en in dat geval heeft de weergegeven vergelijking precies één oplossing $x^*$ , die het unieke vaste punt $\Omega = O + x^*$ geeft. Hercentreren: voor elke vector $u$ ,

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

dus in het raam met oorsprong $\Omega$ leest de afbeelding $u \mapsto \varphi(u)$ : puur lineair. Wanneer $1 \in \operatorname{Sp}\varphi$ , bestaat er ofwel geen vast punt (de weergegeven vergelijking kan onoplosbaar zijn, zoals bij een translatie) ofwel een hele affiene deelruimte ervan (voeg elke eigenvector van eigenwaarde $1$ toe aan een oplossing): uniciteit is precies de spectrale voorwaarde. ∎

Voorbeeld 17.18 (Isometrieën van het vlak, voltooid)

Een affiene isometrie van het euclidische vlak heeft lineair deel in $O(2)$ : een rotatie $R_\theta$ of een spiegeling (volume Jaar 1). Als $\theta \neq 0$ : $1 \notin \operatorname{Sp} R_\theta$ , dus de afbeelding is een rotatie om een uniek centrum (Propositie 17.17). Als het lineaire deel een spiegeling is: ofwel een spiegeling in een as (vaste punten bestaan) ofwel een glijspiegeling (spiegeling samengesteld met een translatie langs de as, geen vast punt). Met de translaties is dit de volledige classificatie van vlakke isometrieën.

Opmerking 17.19 (De vlakke isometrieën, in één oogopslag)

De gevallen verzamelend: identiteit; translaties ( $\vec f = \mathrm{id}$ , geen vast punt tenzij triviaal); rotaties (lineair deel $R_\theta$ , $\theta \neq 0$ : één centrum); spiegelingen (lineair deel een spiegeling, een lijn van vaste punten); glijspiegelingen (zelfde lineaire deel, geen vast punt). Vier families plus de identiteit, elk herkend door slechts twee gegevens: het lineaire deel en de verzameling vaste punten — het patroon van Propositie 17.17 exhaustief gemaakt.

Voorbeeld 17.20 (Een glijspiegeling, op heterdaad betrapt)

Zij $f(x, y) = (y + 1,\ x + 1)$ . Het lineaire deel $(x, y) \mapsto (y, x)$ is de spiegeling in de diagonaal $y = x$ , dus $1 \in \operatorname{Sp}\vec f$ en Propositie 17.17 zwijgt. Vaste punten zouden tegelijk $x = y + 1$ en $y = x + 1$ nodig hebben: onmogelijk — er bestaan er geen, dus $f$ is geen spiegeling. Kwadrateren beslist de classificatie:

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

de translatie over $(2, 2)$ : $f$ is de glijspiegeling met as de lijn $y = x$ (passend verschoven: het midden van $M$ en $f(M)$ ligt altijd op $y = x + {}$ constante, hier $y = x$ , zoals men controleert op $M = (0, 0) \mapsto (1,1)$ ) en glijvector $(1, 1)$ , de helft van $f \circ f$ . Vergelijk met Oefening 17.6, waar hetzelfde lineaire deel maar een andere constante een eerlijke spiegeling opleverde: met eigenwaarde $1$ aanwezig beslist de constante term alles.

Voorbeeld 17.21 (Affiene recursies zijn affiene dynamica)

De klassieke recursie $u_{n+1} = au_n + b$ ( $a \neq 1$ ) itereert de affiene afbeelding $f(x) = ax + b$ van de lijn, waarvan het lineaire deel $a$ de eigenwaarde $1$ vermijdt: er is een uniek vast punt $\omega = \frac{b}{1-a}$ , en hercentreren daar (het eendimensionale geval van de propositie hierboven) maakt van $f$ vermenigvuldiging met $a$ :

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

Voor $u_{n+1} = \frac{u_n}2 + 3$ : $\omega = 6$ en $u_n = 6 + (u_0 - 6)2^{-n} \to 6$ . Het recept dat voor zulke recursies in Hoofdstuk 7 wordt geleerd — “trek het vaste punt af” — is precies de vectorialisatie van een affiene afbeelding in haar vaste punt; convergentie voor $\abs a < 1$ is het contractieverschijnsel dat Hoofdstuk 4 tot de vaste-puntstelling van Banach maakte. Eén idee, drie hoofdstukken.

Voorbeeld 17.22 (Het centrum van een rotatie vinden)

Zij $f(x, y) = (-y + 2,\ x)$ . Het lineaire deel is $\varphi(x, y) = (-y, x)$ : de rotatie over hoek $\frac\pi2$ , waarvan het spectrum $\{\iu, -\iu\}$ de $1$ vermijdt. Door Propositie 17.17 is er precies één vast punt: $x = -y + 2$ en $y = x$ geven $x = 1$ , $y = 1$ , dus $\Omega = (1, 1)$ , en $f$ is de rotatie met centrum $(1, 1)$ en hoek $\frac\pi2$ . De algemene les: wanneer $1 \notin \operatorname{Sp}\vec f$ , kost het classificeren van $f$ één lineair stelsel — de meetkunde zit geheel in het lineaire deel, de rekenkunde geheel in het lokaliseren van het centrum.

Opmerking 17.23 (Waar affiene taal hierna wordt gebruikt)

Barycentra en affiene afbeeldingen zijn de grammatica van de volgende meetkundige hoofdstukken: raaklijnen en raakvlakken zijn affiene objecten (Hoofdstukken 18 en 19), een affiene variabelensubstitutie vermenigvuldigt oppervlakten en inhouden met $\abs{\det \vec f}$ (Hoofdstuk 20), en de verwachting is een barycentrum met gewichten gegeven door een waarschijnlijkheidswet, waarom convexiteit Jensens ongelijkheid bestuurt (Hoofdstuk 22). In het volume van Jaar 3 draagt dezelfde convexiteitswoordenschat de studie van $L^p$ -normen en integraalongelijkheden.

Opmerking 17.24 (Perspectieven binnen dit volume)

Twee draden verlaten dit hoofdstuk. De affiene draad: raaklijnen (Hoofdstuk 18) en raakvlakken (Hoofdstuk 19) zijn affiene deelruimten gehecht aan niet-lineaire objecten, en de classificatie van kwadrieken in het oppervlakkenhoofdstuk loopt op de centrumvergelijking $A\Omega = -b$ van dit hoofdstuk. De convexe draad is langer: convexiteit van halfvlakken en schijven voedt de Helly-theorie van het weekendprobleem; convexiteit van functies geeft Jensens ongelijkheid (Hoofdstuk 22); en de slotstelling van het boek — het uitdovingscriterium voor vertakkingsprocessen (Hoofdstuk 23) — wordt beslist door de ligging van een convexe kromme ten opzichte van de diagonaal, een beeld dat evenzeer bij dit hoofdstuk hoort als bij de waarschijnlijkheid. Barycentra keren daar ook terug: een verwachting is een barycentrum met waarschijnlijkheidsgewichten.

17.4 Oefeningen

Oefening 17.1 ★

In $\R^3$ , zijn de volgende affiene deelruimten? Geef richtingen en dimensies. $\{x + y + z = 1\}$ ; $\;\{x + y + z = 1,\ x - z = 3\}$ ; $\;\{x^2 + y^2 = 1\}$ ; de oplossingsverzameling van $MX = B$ voor een gegeven compatibel stelsel.

Oplossing

Oplossing van Oefening 17.1.

$\{x + y + z = 1\}$ : affien vlak, richting het vectorvlak $\{x + y + z = 0\}$ , dimensie $2$ . Toevoegen van $x - z = 3$ : een affiene lijn (twee onafhankelijke vergelijkingen), richting $\{x + y + z = 0,\ x = z\} = \operatorname{Vect}\bigl((1, -2, 1)\bigr)$ , dimensie $1$ . $\{x^2 + y^2 = 1\}$ : een cilinder — niet stabiel onder barycentra (het midden van $(1,0,0)$ en $(-1,0,0)$ is de oorsprong, buiten de cilinder): niet affien. Een compatibel stelsel $MX = B$ : affiene deelruimte $X_0 + \ker M$ van dimensie $\dim\ker M$ , zoals herinnerd in Definitie 17.5.

Oefening 17.2 ★

Bewijs dat drie onderscheiden punten $A, B, C$ van een affiene ruimte collineair zijn dan en slechts dan als $C$ een barycentrum is van $A$ en $B$ , dan en slechts dan als de vectoren $\vect{AB}, \vect{AC}$ lineair afhankelijk zijn. Leid Menelaos-achtige gewichtenboekhouding af: als $C = \operatorname{bar}(A, 1 - t; B, t)$ , lokaliseer $C$ voor $t = \frac12$ , $t = 2$ , $t = -1$ .

Oplossing

Oplossing van Oefening 17.2.

$C = \operatorname{bar}(A, 1-t; B, t)$ betekent $\vect{AC} = t\,\vect{AB}$ : bestaan van zulk een $t$ is precies lineaire afhankelijkheid van $\vect{AC}$ met $\vect{AB} \neq 0$ , d.w.z. collineariteit. Posities: $t = \frac12$ : midden; $t = 2$ : voorbij $B$ , op de afstand van $B$ tot $A$ ervan vandaan ( $\vect{AC} = 2\vect{AB}$ ); $t = -1$ : de spiegeling van $B$ door $A$ .

Oefening 17.3 ★

Zij $f$ de affiene afbeelding van $\R^2$ gegeven door $f(X) = MX + C$ met $M = \frac12\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}$ en $C = (1, 0)^{\mathsf T}$ . Bepaal het beeld van $f$ , haar vaste punten (indien aanwezig), en $f \circ f$ .

Oplossing

Oplossing van Oefening 17.3.

$M$ is de projectiematrix op $\operatorname{Vect}(1,1)$ langs $(1,-1)$ (controleer $M^2 = M$ ). Beeld van $f$ : $\{MX + C\} = C + \operatorname{im} M$ : de affiene lijn door $(1,0)$ gericht door $(1,1)$ . Vaste punten: $X = MX + C$ , d.w.z. $(I - M)X = C$ ; maar $C = (1, 0)^{\mathsf T}$ en $\operatorname{im}(I - M) = \operatorname{Vect}(1,-1)$ ; ligt $(1,0)$ erin? $(1, 0) = \alpha(1,-1)$ dwingt $\alpha = 1$ en $0 = -1$ : nee. Geen vaste punten. En

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$ gevolgd door een translatie langs de beeldlijn — $f$ is een “glijprojectie”: projectie op de lijn samengesteld met een verschuiving.

Oefening 17.4 ★★

(Associativiteit in actie) In een driehoek $ABC$ , zij $I, J, K$ die $BC$ , $CA$ , $AB$ verdelen in de verhoudingen $\vect{BI} = \frac13\vect{BC}$ , $\vect{CJ} = \frac13\vect{CA}$ , $\vect{AK} = \frac13\vect{AB}$ . Druk $I, J, K$ uit als barycentra en bereken het barycentrum van $(I,1;J,1;K,1)$ : wat vind je, en waarom was het voorspelbaar?

Oplossing

Oplossing van Oefening 17.4.

$I = \operatorname{bar}(B, 2; C, 1)$ (aangezien $\vect{BI} = \frac13\vect{BC}$ $I$ dichter bij $B$ plaatst: gewichten $2$ op $B$ , $1$ op $C$ — controle: $\vect{BI} = \frac{1}{3}\vect{BC}$ ). Evenzo $J = \operatorname{bar}(C, 2; A, 1)$ , $K = \operatorname{bar}(A, 2; B, 1)$ . Optellen van de drie gewogen stelsels: het barycentrum van $(I, 1; J, 1; K, 1)$ (elk van totaalgewicht $3$ , dus vervang $I$ door haar stelsel, enz.) is

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

het zwaartepunt van $ABC$ : de driehoek $IJK$ heeft hetzelfde zwaartepunt — voorspelbaar, omdat de constructie $A, B, C$ cyclisch behandelt en het zwaartepunt het unieke vaste punt is van de cyclische symmetrie van de gewichten.

Oefening 17.5 ★★

Bewijs dat een afbeelding $f \colon \R^n \to \R^n$ die midpunten behoudt ( $f\bigl(\frac{A+B}{2}\bigr) = \frac{f(A) + f(B)}{2}$ ) en continu is, affien is. (Toon dat de vectorafbeelding $u \mapsto f(O + u) - f(O)$ additief is via midpunten, daarna $\Q$ -homogeen, daarna $\R$ -homogeen door continuïteit — dezelfde densiteitsstrategie als voor de functionaalvergelijking van Cauchy in het volume van Jaar 1; leid de nodige stappen hier opnieuw af.)

Oplossing

Oplossing van Oefening 17.5.

Stel $g(u) = f(O + u) - f(O)$ (werkend in $\R^n$ gevectorialiseerd in $O$ ), $g(0) = 0$ .

Additiviteit: $\frac{(O + u) + (O + v)}{2} = O + \frac{u + v}{2}$ , dus middenbehoud geeft $g\bigl(\frac{u+v}{2}\bigr) = \frac{g(u) + g(v)}{2}$ ; met $v = 0$ : $g(u/2) = g(u)/2$ ; combinerend, $g(u + v) = 2g\bigl(\frac{u+v}{2}\bigr) = g(u) + g(v)$ .

$\Q$ -homogeniteit: additiviteit geeft $g(nu) = ng(u)$ ( $n \in \N$ , inductie), daarna $g(-u) = -g(u)$ (optellen), daarna $g(\frac pq u) = \frac pq g(u)$ (pas $q$ toe, gebruik injectiviteit van schaling).

$\R$ -homogeniteit: voor $t \in \R$ , neem rationalen $t_n \to t$ : $g(t_nu) = t_ng(u)$ , en continuïteit van $g$ (geërfd van $f$ ) gaat over naar de limiet: $g(tu) = tg(u)$ . Dus is $g$ lineair en $f = f(O) + g$ : affien.

Oefening 17.6 ★★

Classificeer de affiene afbeelding $f(x, y) = (y + 1,\; x - 1)$ van het euclidische vlak: lineair deel, vaste punten, meetkundige aard (spiegeling? glij?). Bereken $f \circ f$ en concludeer.

Oplossing

Oplossing van Oefening 17.6.

Lineair deel $\varphi(x,y) = (y, x)$ : de spiegeling in de diagonaal $y = x$ (orthogonaal, determinant $-1$ ). Vaste punten: $(x, y) = (y + 1, x - 1)$ komt neer op de enkele vergelijking $y = x - 1$ (de twee componenten zijn equivalent): elk punt van de lijn $y = x - 1$ is vast. Dus laat $f$ die lijn puntsgewijs vast: $f$ is de spiegeling in die as (een isometrie met een lijn van vaste punten en lineair deel een spiegeling). Consistent, $f \circ f(x,y) = f(y+1, x-1) = (x - 1 + 1, y + 1 - 1) = (x, y)$ : een involutie, zoals een spiegeling moet zijn.

Oefening 17.7 ★★★

(Radon) Zij $A_1, \dots, A_{n+2}$ punten van een affiene ruimte van dimensie $n$ . Bewijs dat ze gesplitst kunnen worden in twee disjuncte groepen waarvan de convexe omhullingen snijden. (Zoals in het bewijs van Carathéodory, vind gewichten $\mu_i$ , niet alle nul, met $\sum\mu_i = 0$ en $\sum\mu_i\vect{OA_i} = 0$ ; scheid positieve en negatieve gewichten en normaliseer beide zijden.)

Oplossing

Oplossing van Oefening 17.7.

De $n + 1$ vectoren $\vect{A_1A_i}$ ( $i \geq 2$ ) zijn lineair afhankelijk in dimensie $n$ : er zijn $\mu_i$ , niet alle nul, met $\sum_{i\geq2} \mu_i\vect{A_1A_i} = 0$ ; stel $\mu_1 = -\sum_{i \geq 2}\mu_i$ , zodat $\sum_{i}\mu_i = 0$ en $\sum_i \mu_i\,\vect{OA_i} = 0$ voor elke $O$ , met niet alle $\mu_i$ nul. Splits indices: $P = \{i : \mu_i > 0\}$ , $N = \{i : \mu_i < 0\}$ , beide niet-leeg (de $\mu_i$ sommeren tot nul en zijn niet alle nul). Met $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},

(beide zijden gelijk aan het punt $X$ met $\vect{OX} = \frac1s\sum_{i\in P}\mu_i\vect{OA_i}$ , door de relatie): een gemeenschappelijk punt van de twee convexe omhullingen, met disjuncte indexgroepen.

Oefening 17.8 ★★★

Zij $f$ een affien endomorfisme van $\R^n$ met $f \circ f = f$ . Bewijs dat $f$ de affiene projectie is op de affiene deelruimte $\operatorname{Fix}(f) = \operatorname{im} f$ langs de richting $\ker\vec f$ , en dat omgekeerd alle dergelijke projecties idempotent zijn. (Toon eerst dat $\operatorname{im} f$ uit vaste punten bestaat.)

Oplossing

Oplossing van Oefening 17.8.

Beeld = vaste punten: voor $Y = f(X)$ , $f(Y) = f(f(X)) = f(X) = Y$ : elk beeldpunt is vast; omgekeerd zijn vaste punten beelden. Dus $\mathcal{F} = \operatorname{im} f = \operatorname{Fix}(f)$ is niet-leeg, en het is een affiene deelruimte (beeld van een affiene afbeelding), met richting $\operatorname{im}\vec f$ .

Projectiestructuur: $\vec f$ is idempotent ( $\vec{f\circ f} = \vec f^{\,2} = \vec f$ ), dus $E = \operatorname{im}\vec f \oplus \ker \vec f$ (Voorbeeld 3.18). Voor elk punt $X$ , beschouw de vector $\vect{f(X)\,X}$ ; toepassen van $\vec f$ :

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

dus $\vect{f(X)\,X} \in \ker\vec f$ . Vandaar $X = f(X) + \vect{f(X)X}$ vertoont $X$ als een punt van $\mathcal{F}$ getransleerd over een vector van $\ker\vec f$ : $f$ is precies de projectie op $\mathcal{F}$ langs $\ker\vec f$ . Omgekeerd voldoen zulke projecties duidelijk aan $f \circ f = f$ .

Oefening 17.9 ★

Zij $G = \operatorname{bar}(A, 1;\ B, 2;\ C, 3)$ in een driehoek $ABC$ . Toon met associativiteit dat de lijn $AG$ de lijn $BC$ snijdt in $M = \operatorname{bar}(B, 2;\ C, 3)$ , en lokaliseer $G$ op het segment $\intcc AM$ ; lokaliseer evenzo het snijpunt van $BG$ met $CA$ .

Oplossing

Oplossing van Oefening 17.9.

Zij $M = \operatorname{bar}(B, 2;\ C, 3)$ , van totaalgewicht $5$ . Associativiteit geeft $G = \operatorname{bar}(A, 1;\ M, 5)$ , dus $\vect{AG} = \frac56\,\vect{AM}$ : $G$ ligt op het segment $\intcc AM$ op vijf zesden ervan vanaf $A$ . Omdat $A \notin (BC)$ , snijdt de lijn $(AG) = (AM)$ de lijn $(BC)$ in het enige punt $M$ , met $\vect{BM} = \frac35\,\vect{BC}$ . Evenzo, met $N = \operatorname{bar}(C, 3;\ A, 1)$ (totaalgewicht $4$ , $\vect{CN} = \frac14\,\vect{CA}$ ), geeft associativiteit $G = \operatorname{bar}(B, 2;\ N, 4)$ : de lijn $(BG)$ snijdt $(CA)$ in $N$ , en $\vect{BG} = \frac46\,\vect{BN} = \frac23\,\vect{BN}$ .

Oefening 17.10 ★★

Voor $\lambda \neq 0$ is de homothetie $h_{\Omega, \lambda}$ de affiene afbeelding die $\Omega$ vast laat met lineair deel $\lambda\,\mathrm{id}$ . Bewijs dat de samenstelling $h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ een homothetie is van verhouding $\lambda\mu$ wanneer $\lambda\mu \neq 1$ , en een translatie wanneer $\lambda\mu = 1$ ; in het geval $\lambda = \mu = -1$ (twee puntsymmetrieën), bereken de translatievector.

Oplossing

Oplossing van Oefening 17.10.

Vectorialiseer in een oorsprong $O$ en schrijf punten als vectoren: $h_{\Omega, \lambda}(x) = \omega + \lambda(x - \omega)$ met $\omega = \vect{O\Omega}$ . De samenstelling $g = h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ is affien met lineair deel $\mu\lambda\,\mathrm{id}$ . Als $\lambda\mu \neq 1$ : $1 \notin \operatorname{Sp}(\lambda\mu\,\mathrm{id})$ , dus levert Propositie 17.17 een uniek vast punt $\Omega''$ en, daar gevectorialiseerd, $g = \lambda\mu\,\mathrm{id}$ : de homothetie $h_{\Omega'', \lambda\mu}$ . Als $\lambda\mu = 1$ is het lineaire deel de identiteit, dus is $g$ een translatie; uitwerken geeft

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

Voor $\lambda = \mu = -1$ (puntsymmetrieën) is de vector $2\omega' - 2\omega = 2\,\vect{\Omega\Omega'}$ : de samenstelling van de puntsymmetrieën in $\Omega$ en daarna $\Omega'$ is de translatie over $2\,\vect{\Omega\Omega'}$ .

Oefening 17.11 ★★

(Menelaos) In een driehoek $ABC$ , zij $A' \in (BC)$ , $B' \in (CA)$ , $C' \in (AB)$ , alle verschillend van de hoekpunten, en definieer $\alpha, \beta, \gamma$ door $\vect{A'B} = \alpha\,\vect{A'C}$ , $\vect{B'C} = \beta\,\vect{B'A}$ , $\vect{C'A} = \gamma\,\vect{C'B}$ . Bewijs dat $A', B', C'$ collineair zijn dan en slechts dan als $\alpha\beta\gamma = 1$ . (Schrijf elk punt als barycentrum van twee hoekpunten; toon dat drie punten collineair zijn dan en slechts dan als hun barycentrische coördinatenrijen ten opzichte van $(A, B, C)$ een singuliere $3 \times 3$ -matrix vormen.)

Oplossing

Oplossing van Oefening 17.11.

$\vect{A'B} = \alpha\,\vect{A'C}$ zegt precies $1\cdot \vect{A'B} - \alpha\,\vect{A'C} = 0$ , d.w.z. $A' = \operatorname{bar}(B, 1;\ C, -\alpha)$ (totaalgewicht $1 - \alpha \neq 0$ omdat $B \neq C$ ); evenzo $B' = \operatorname{bar}(C, 1;\ A, -\beta)$ en $C' = \operatorname{bar}(A, 1;\ B, -\gamma)$ .

Het collineariteitscriterium. Geef elk punt $P$ zijn genormaliseerde barycentrische rij $p = (p_A, p_B, p_C)$ , $p_A + p_B + p_C = 1$ , ten opzichte van $(A, B, C)$ . Als $\sum_i c_i p_i = 0$ met $(c_1, c_2, c_3) \neq 0$ voor drie punten $P_1, P_2, P_3$ , dan geeft optellen van de entries $\sum c_i = 0$ , en $\sum_i c_i \vect{OP_i} = \sum_j \bigl(\sum_i c_ip_{ij}\bigr)\vect{OV_j} = 0$ : de $P_i$ zijn affien afhankelijk, d.w.z. collineair. Omgekeerd geeft een affiene afhankelijkheidsrelatie $(t_i)$ een $w = \sum t_ip_i$ met entries die tot $0$ sommeren en $\sum_j w_j\vect{OV_j} = 0$ ; ontwikkelen vanuit $A$ , $w_B \vect{AB} + w_C\vect{AC} = 0$ , dus $w = 0$ door affiene onafhankelijkheid van $(A, B, C)$ : de rijen zijn lineair afhankelijk. Dus komt collineariteit neer op een verdwijnende $3 \times 3$ -determinant, en schalen van rijen met de niet-nulle factoren $1 - \alpha$ , $1 - \beta$ , $1 - \gamma$ verandert niets:

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

Dus zijn $A', B', C'$ collineair dan en slechts dan als $\alpha\beta\gamma = 1$ : de stelling van Menelaos.

Oefening 17.12 ★★★

Bewijs dat de convexe omhulling van een compacte deelverzameling $K$ van $\R^n$ compact is. (Door Stelling 17.14 is $\operatorname{conv}(K)$ het beeld van een compacte verzameling onder een continue afbeelding.) Toon met een voorbeeld in $\R^2$ dat de convexe omhulling van een gesloten verzameling niet noodzakelijk gesloten is.

Oplossing

Oplossing van Oefening 17.12.

Zij $\Delta = \{\lambda \in \R^{n+1} : \lambda_i \geq 0,\ \sum\lambda_i = 1\}$ : gesloten en begrensd in $\R^{n+1}$ , dus compact, en $K^{n+1}$ is compact als eindig product. De afbeelding

\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 continu, en Stelling 17.14 zegt precies dat $\operatorname{conv}(K) = \Phi(\Delta \times K^{n+1})$ : een continu beeld van een compacte verzameling (Stelling 4.16), dus compact.

Voor een gesloten verzameling: neem $S = (\R \times \{0\}) \cup \{(0, 1)\}$ , gesloten in $\R^2$ . Een convexe combinatie die gewicht $t$ op $(0,1)$ en $1 - t$ op as-punten legt heeft tweede coördinaat $t$ , dus

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

(voor $0 \leq t < 1$ , $(x, t) = t\,(0,1) + (1-t)\,\bigl(\tfrac x{1-t}, 0\bigr)$ ). Het punt $(1, 1) = \lim_{t \to 1}(1, t)$ is adherent maar niet in de omhulling: niet gesloten.

17.5 Probleem: van Radon naar Helly, centrumspunten en de stelling van Jung

De twee Radon-types voor vier punten van het vlak in algemene ligging: één punt binnen de driehoek van de andere (partitie \A_4\ \A_1, A_2, A_3\), of convexe ligging, waar het Radon-punt (oranje) het snijpunt is van de twee diagonalen. — De twee Radon-types voor vier punten van het vlak in algemene ligging: één punt binnen de driehoek van de andere (partitie $\{A_4\} \mid \{A_1, A_2, A_3\}$ ), of convexe ligging, waar het Radon-punt (oranje) het snijpunt is van de twee diagonalen.

Probleem 17.1

Weekendprobleem — de stelling van Helly en twee van haar dividenden

Het lemma van Radon (Oefening 17.7) zegt dat $n + 2$ punten van een $n$ -dimensionale affiene ruimte zich altijd splitsen in twee groepen met snijdende convexe omhullingen. Dit probleem maakt van dat ene lineaire-algebrafeit een keten van stellingen van combinatorische meetkunde: de doorsnedestelling van Helly, de centrumspuntstelling (een tweedimensionale mediaan), en de overdekkingsstelling van Jung. Doorheen is het vlak $\R^2$ met zijn gebruikelijke euclidische structuur, en $\det$ is de determinant in de canonieke basis.

Deel I — Barycentrische coördinaten. Punten $A_0, \dots, A_k$ zijn affien onafhankelijk wanneer de vectoren $\vect{A_0A_1}, \dots, \vect{A_0A_k}$ lineair onafhankelijk zijn.

Toon dat affiene onafhankelijkheid niet afhangt van de keuze van het baspunt $A_0$ , en dat ze equivalent is aan: wanneer twee families van gewichten, elk met som $1$ , hetzelfde barycentrum van $(A_0, \dots, A_k)$ definiëren, vallen de gewichten samen.
Zij $(A, B, C)$ affien onafhankelijk in het vlak. Toon dat elk punt $M$ een unieke triple $(\alpha, \beta, \gamma)$ toelaat met $\alpha + \beta + \gamma = 1$ en $M = \operatorname{bar}(A, \alpha; B, \beta; C, \gamma)$ — haar barycentrische coördinaten.
Bewijs de determinantformules

$\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})} :$

barycentrische coördinaten zijn verhoudingen van georiënteerde oppervlakten.
De lijnen $BC$ , $CA$ , $AB$ zijn de coördinaatlijnen $\{\alpha = 0\}$ , $\{\beta = 0\}$ , $\{\gamma = 0\}$ . Toon dat $M$ in de gesloten driehoek $\operatorname{conv}\{A, B, C\}$ ligt dan en slechts dan als $\alpha, \beta, \gamma \geq 0$ , en dat de drie lijnen het vlak in precies zeven gebieden snijden, geclassificeerd door de tekens van $(\alpha, \beta, \gamma)$ (het tekenpatroon $(-,-,-)$ is onmogelijk).
Zij $u \colon \R^2 \to \R$ een affiene afbeelding (een affiene vorm). Toon $u(M) = \alpha\,u(A) + \beta\,u(B) + \gamma\,u(C)$ , dat de niveauverzamelingen van een niet-constante affiene vorm lijnen zijn, dat elke lijn zo ontstaat, en dat de gesloten halfvlakken $\{u \geq c\}$ convex zijn.

Deel II — Radon-partities, verfijnd. Een familie van $n + 2$ punten van $\R^n$ is in algemene ligging wanneer elke $n + 1$ ervan affien onafhankelijk zijn. Een affiene afhankelijkheidsrelatie van $(A_1, \dots, A_{n+2})$ is een familie $(\mu_i)$ met $\sum_i \mu_i = 0$ en $\sum_i \mu_i\,\vect{OA_i} = 0$ voor één (dus elke) oorsprong $O$ .

Bereken een niet-nulle affiene afhankelijkheidsrelatie van de vier punten $A_1 = (0,0)$ , $A_2 = (3,0)$ , $A_3 = (0,3)$ , $A_4 = (1,1)$ ; geef de Radon-partitie en het Radon-punt.
Toon dat voor punten in algemene ligging de vectorruimte van affiene afhankelijkheidsrelaties dimensie precies $1$ heeft, en dat een niet-nulle relatie geen verdwijnende coëfficiënt heeft.
Leid af dat de Radon-partitie van $n + 2$ punten in algemene ligging uniek is (op verwisseling van de twee blokken na), waarbij elk blok de verzameling indices is waar $\mu_i$ één vast teken heeft.
Voor vier punten van het vlak in algemene ligging, toon de dichotomie: ofwel heeft de partitie type $(1, 3)$ — één punt inwendig in de driehoek van de andere drie — of type $(2, 2)$ : de vier punten liggen convex en de segmenten die de twee paren verbinden (de diagonalen) snijden, in het Radon-punt.
Voer vraag 6 uit voor het eenheidsvierkant $(0,0)$ , $(1,0)$ , $(1,1)$ , $(0,1)$ : relatie, partitie, Radon-punt.

Deel III — De stelling van Helly in het vlak.

Zij $C_1, C_2, C_3, C_4$ convexe deelverzamelingen van $\R^2$ , waarvan elke drie een gemeenschappelijk punt hebben. Kies $x_i \in \bigcap_{j \neq i} C_j$ en pas het lemma van Radon toe op $x_1, \dots, x_4$ : toon dat het Radon-punt tot alle vier verzamelingen behoort. (Voor elke $k$ bestaat het blok dat $x_k$ niet bevat uit punten van $C_k$ .)
(Helly) Zij $C_1, \dots, C_m$ ( $m \geq 3$ ) convexe deelverzamelingen van $\R^2$ , waarvan elke drie snijden. Bewijs $\bigcap_{i=1}^m C_i \neq \emptyset$ , door inductie op $m$ : vervang $C_{m-1}$ en $C_m$ door $C_{m-1} \cap C_m$ en controleer de hypothese voor de nieuwe familie met vraag 11.
Drie tegenvoorbeelden, één per hypothese: (a) de drie gesloten randen van een driehoek snijden paarsgewijs maar hebben geen gemeenschappelijk punt ( $3$ kan niet tot $2$ worden verlaagd); (b) de vier verzamelingen $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ , voor vier punten in algemene ligging, voldoen aan de driedoorsnedehypothese maar niet aan de conclusie (convexiteit telt); (c) de gesloten halfvlakken $H_k = \intco{k}{+\infty} \times \R$ , $k \in \N$ , snijden paarsgewijs en drievoudig maar $\bigcap_k H_k = \emptyset$ (oneindige families hebben compactheid nodig).
(Compacte Helly) Zij $(K_i)_{i \in I}$ een willekeurige familie van compacte convexe deelverzamelingen van $\R^2$ , waarvan elke drie snijden. Met vraag 12 en de eigenschap van Borel–Lebesgue (Stelling 4.20), toon $\bigcap_{i \in I} K_i \neq \emptyset$ .
(Eerste dividend) Zij $S$ een eindige verzameling punten van het vlak en $r > 0$ . Toon: als elke drie punten van $S$ in een gesloten schijf van straal $r$ liggen, dan ligt $S$ in één gesloten schijf van straal $r$ . (Pas Helly toe op de schijven $\overline D(p, r)$ , $p \in S$ .)

Deel IV — De centrumspuntstelling. Een centrumspunt van een eindige verzameling $S$ van $n$ punten van het vlak is een punt $c$ (niet noodzakelijk in $S$ ) zodat elk gesloten halfvlak dat $c$ bevat ten minste $n/3$ punten van $S$ bevat.

(Dimensie $1$ ) Voor reële $x_1 \leq \dots \leq x_n$ , toon dat de mediaan $c = x_{\lceil n/2 \rceil}$ voldoet: elke gesloten halfrechte die $c$ bevat bevat ten minste $n/2$ van de $x_i$ .
(Tellemma) Als $A, B, C$ deelverzamelingen van $S$ zijn met $\abs A, \abs B, \abs C > \tfrac{2n}3$ , toon $A \cap B \cap C \neq \emptyset$ .
Zij $m = \floor{2n/3} + 1$ en zij $\mathcal F$ de (eindige) familie van de convexe omhullingen $\operatorname{conv}(T)$ , $T \subseteq S$ , $\abs T = m$ . Toon dat elke drie leden van $\mathcal F$ een gemeenschappelijk punt hebben, en leid uit Helly een punt $c$ af dat ze allemaal gemeen hebben.
Bewijs dat dit $c$ een centrumspunt van $S$ is: de centrumspuntstelling. (Als een gesloten halfvlak door $c$ minder dan $n/3$ punten bevatte, zou zijn open complement een verzameling $T$ van $m$ punten bevatten, en $\operatorname{conv}(T)$ zou $c$ mijden.)
Scherpte: zij $n = 3k$ en plaats $k$ punten in elk van drie schijven van kleine straal $\varepsilon$ gecentreerd in de hoekpunten van een grote driehoek. Toon dat voor elk punt $c$ van het vlak enig gesloten halfvlak dat $c$ bevat ten hoogste $n/3$ punten van $S$ bevat, zodat de constante $1/3$ niet verbeterd kan worden. (Onder de drie richtingen van $c$ naar de schijfcentra maken er twee een hoek van ten hoogste $2\pi/3$ .)

Deel V — De stelling van Jung en synthese.

(Driehoekslemma) Zij $P, Q, R$ drie punten met paarsgewijze afstanden $\leq 1$ . Toon dat ze in een gesloten schijf van straal $1/\sqrt3$ liggen. (Als enige hoek $\geq \pi/2$ is, neem de schijf op de langste zijde als diameter, met de mediaanformule $\norm{RM}^2 = \tfrac12\norm{RP}^2 + \tfrac12\norm{RQ}^2 - \tfrac14\norm{PQ}^2$ ; als de driehoek scherphoekig is, begrens de omgeschreven straal $a/(2\sin \widehat A)$ met haar grootste hoek, die in $\intco{\pi/3}{\pi/2}$ ligt.)
(Jung) Leid af: elke compacte deelverzameling van het vlak van diameter $\leq 1$ is bevat in een gesloten schijf van straal $1/\sqrt3$ .
Scherpte: voor de gelijkzijdige driehoek $A_1A_2A_3$ van zijde $1$ met zwaartepunt $G$ , bewijs de identiteit van Leibniz $\sum_i \norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + \sum_i \norm{\vect{GA_i}}^2$ voor elk punt $O$ , en concludeer dat elke schijf die de drie hoekpunten bevat straal $\geq 1/\sqrt3$ heeft, met gelijkheid alleen voor de omgeschreven schijf.
(Helly in $\R^n$ ) Formuleer en bewijs de stelling van Helly in $\R^n$ : als eindig veel convexe verzamelingen zo zijn dat elke $n + 1$ ervan snijden, dan snijden ze allemaal. (Het lemma van Radon Oefening 17.7 behandelt $n + 2$ verzamelingen; induceer daarna zoals in vraag 12.)
Synthese. Assembleer de keten

$\text{affiene afhankelijkheid} \Rightarrow \text{Radon} \Rightarrow \text{Helly} \Rightarrow \text{centrumspunt en Jung},$

met in één zin elk: waar lineaire algebra binnentreedt, waar de tekens van de gewichten binnentreden, waar convexiteit binnentreedt, en welke ene stap de dimensie van het vlak gebruikte. Wat worden de constanten $3$ (in Helly), $1/3$ (centrumspunt) en $1/\sqrt3$ (Jung) in $\R^n$ ? (Formuleer zonder bewijs.)

Oplossing

Oplossing van Probleem 17.1.

1. Herbaseer in $A_j$ : voor $i \neq j$ , $\vect{A_jA_i} = \vect{A_0A_i} - \vect{A_0A_j}$ . Als $\sum_{i \neq j} c_i\vect{A_jA_i} = 0$ , geeft ontwikkelen $\sum_{i \notin \{0, j\}} c_i\,\vect{A_0A_i} - \bigl(\sum_{i\neq j} c_i\bigr)\vect{A_0A_j} = 0$ ; onafhankelijkheid van de $\vect{A_0A_i}$ dwingt $c_i = 0$ voor $i \notin \{0, j\}$ , daarna $c_0 = 0$ : onafhankelijkheid in $A_j$ . Voor de equivalentie: twee gewichtenfamilies $(\lambda_i)$ , $(\lambda_i')$ met som $1$ en hetzelfde barycentrum geven, met $\nu = \lambda - \lambda'$ : $\sum\nu_i = 0$ en (oorsprong $A_0$ ) $\sum_{i \geq 1}\nu_i\,\vect{A_0A_i} = 0$ , dus $\nu = 0$ onder onafhankelijkheid. Omgekeerd laat een niet-triviale relatie $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ , voltooid met $\mu_0 = -\sum_{i\geq1} \mu_i$ , toe $t(\mu_i)$ op te tellen bij elke gewichtenfamilie zonder het barycentrum te verplaatsen: niet-uniciteit.

2. $(\vect{AB}, \vect{AC})$ is een basis van $\R^2$ : schrijf $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ (uniek) en stel $\alpha = 1 - \beta - \gamma$ ; de barycentrumvoorwaarde in oorsprong $A$ leest precies $\vect{AM} = \beta\,\vect{AB} + \gamma\,\vect{AC}$ . Uniciteit is vraag 1.

3. Uit $\alpha\vect{MA} + \beta\vect{MB} + \gamma\vect{MC} = 0$ en Chasles, $\vect{MA} = -\beta\,\vect{AB} - \gamma\,\vect{AC}$ . Met $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*}

met bilineariteit en $\det(\vect{MA}, \vect{AC}) = -\beta D$ , $\det(\vect{AB}, \vect{MA}) = -\gamma D$ . De andere twee formules volgen door dezelfde berekening met cyclisch verwisselde rollen.

4. Per definitie is $\operatorname{conv}\{A, B, C\}$ de verzameling barycentra met niet-negatieve gewichten; normaliseren van de gewichten tot som $1$ en uniciteit inroepen (vraag 2), $M \in \operatorname{conv}\{A,B,C\}$ dan en slechts dan als $\alpha, \beta, \gamma \geq 0$ . Elke coördinaat is een affiene functie van $M$ (vraag 3: een $2\times2$ -determinant met één kolom affien in $M$ ), dus definieert elke open tekenvoorwaarde een open halfvlak. Het patroon $(-,-,-)$ spreekt $\alpha + \beta + \gamma = 1$ tegen; elk van de overige zeven patronen is gerealiseerd: schaalt een teken-respecterend triple met ten minste één $+$ -entry zodat de (positieve) som $1$ is — bijv. $(-1, 1, 1)$ , $(3, -1, -1)$ , $(\frac13, \frac13, \frac13)$ , en permutaties.

5. Een affiene afbeelding behoudt barycentra (Definitie 17.5), dus $u(M) = \alpha u(A) + \beta u(B) + \gamma u(C)$ . Schrijvend $u(x, y) = ax + by + c$ met $(a, b) \neq (0,0)$ : $\{u = c'\}$ is een lijn, en elke lijn $ax + by = c'$ is zo’n niveauverzameling. Als $u(M), u(N) \geq c$ en $t \in \intcc01$ , dan $u\bigl(\operatorname{bar}(M, 1-t; N, t)\bigr) = (1-t)u(M) + tu(N) \geq c$ : halfvlakken zijn convex.

6. De voorwaarden $\sum\mu_i = 0$ , $3\mu_2 + \mu_4 = 0$ , $3\mu_3 + \mu_4 = 0$ geven (met $\mu_4 = 3$ ) de relatie $(\mu_1, \mu_2, \mu_3, \mu_4) = (-1, -1, -1, 3)$ . Tekens splitsen als $\{A_4\} \mid \{A_1, A_2, A_3\}$ , en normaliseren van elke zijde met $3$ :

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

het zwaartepunt van de driehoek: het Radon-punt is $A_4$ zelf, dat inderdaad binnen de driehoek $A_1A_2A_3$ ligt.

7. De lineaire afbeelding $\Phi \colon \R^{n+2} \to \R \times \R^n$ , $\mu \mapsto (\sum\mu_i,\ \sum\mu_i\vect{OA_i})$ , heeft rang $\leq n + 1$ , dus $\dim\ker \Phi \geq 1$ . Als twee onafhankelijke relaties $\mu, \mu'$ bestonden, zou een geschikte combinatie $\nu = \mu'_{n+2}\mu - \mu_{n+2}\mu'$ (of $\mu$ zelf als beide laatste coëfficiënten verdwijnen) een niet-nulle relatie met $\nu_{n+2} = 0$ zijn; beperking tot $A_1, \dots, A_{n+1}$ en herbaseren in $A_1$ geeft enige $\nu_i \neq 0$ met $i \geq 2$ (een enkel niet-nul gewicht kan niet tot nul sommeren), wat een niet-triviale relatie $\sum_{i\geq2}\nu_i\vect{A_1A_i} = 0$ oplevert: de $n+1$ punten zouden affien afhankelijk zijn, tegen algemene ligging. Dus $\dim\ker \Phi = 1$ . Hetzelfde beperkingsargument toont dat een niet-nulle relatie geen verdwijnende coëfficiënt heeft.

8. Zij $\mu \neq 0$ een relatie, $P = \{i : \mu_i > 0\}$ en $N = \{i : \mu_i < 0\}$ : beide niet-leeg ( $\sum\mu_i = 0$ , $\mu \neq 0$ ) en exhaustief (geen nulcoëfficiënt). De constructie van Radon (Oefening 17.7) produceert het gemeenschappelijke omhullingspunt precies uit deze partitie. Omdat de relatie uniek is op een niet-nulle scalar na (vraag 7), is het ongeordende paar $\{P, N\}$ — dus de Radon-partitie — uniek.

9. Blokken zijn niet-leeg, dus is het type $(1,3)$ of $(2,2)$ . Type $(1,3)$ , blok $\{j\}$ : het Radon-punt ligt in $\operatorname{conv}\{A_j\} = \{A_j\}$ , dus $A_j \in \operatorname{conv}$ van de andere drie; het kan niet op een rand liggen (drie van de punten zouden collineair zijn, tegen algemene ligging), dus is $A_j$ inwendig in de driehoek. Type $(2,2)$ , blokken $\{i,j\} \mid \{k,l\}$ : het Radon-punt $z$ ligt op $\intcc{A_i}{A_j} \cap \intcc{A_k}{A_l}$ , en $z$ is geen eindpunt (dat zou drie punten collineair maken): de twee segmenten kruisen in een inwendig punt. Bovendien ligt geen punt in de omhulling van de andere: zo’n insluiting $A_l = \operatorname{bar}(A_i, \lambda_i)_{i \neq l}$ met $\lambda_i \geq 0$ is een affiene relatie met tekenpatroon $(+,+,+,-)$ , die door uniciteit (vraag 8) de partitie $(1,3)$ zou maken. Dus liggen in het $(2,2)$ -geval de vier punten convex en zijn de kruisende segmenten de diagonalen.

10. De vergelijkingen $\mu_2 + \mu_3 = 0$ , $\mu_3 + \mu_4 = 0$ , $\sum\mu_i = 0$ geven de relatie $(1, -1, 1, -1)$ : partitie $\{(0,0), (1,1)\} \mid \{(1,0), (0,1)\}$ , en

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

het Radon-punt is het centrum van het vierkant, waar de twee diagonalen kruisen — type $(2,2)$ , zoals de tekening voorspelt.

11. Radon toegepast op $x_1, \dots, x_4$ geeft blokken $I \mid J$ en een punt $z \in \operatorname{conv}\{x_i : i \in I\} \cap \operatorname{conv}\{x_j : j \in J\}$ . Fixeer $k \in \{1, \dots, 4\}$ , zeg $k \in I$ . Elke $j \in J$ voldoet aan $j \neq k$ , dus $x_j \in C_k$ door de keuze $x_j \in \bigcap_{l \neq j}C_l$ ; omdat $C_k$ convex is, $z \in \operatorname{conv}\{x_j : j \in J\} \subseteq C_k$ . Omdat $k$ willekeurig was, $z \in C_1 \cap C_2 \cap C_3 \cap C_4$ .

12. Inductie op $m$ . Voor $m = 3$ is de hypothese de conclusie; $m = 4$ is vraag 11. Zij $m \geq 4$ , veronderstel de uitspraak voor $m$ verzamelingen, en neem $C_1, \dots, C_{m+1}$ met de driedoorsnede-eigenschap. Stel $C_m' = C_m \cap C_{m+1}$ , convex. De familie $C_1, \dots, C_{m-1}, C_m'$ heeft $m$ leden; een triple dat $C_m'$ mijdt snijdt per hypothese, en een triple $\{C_i, C_j, C_m'\}$ heeft doorsnede $C_i \cap C_j \cap C_m \cap C_{m+1}$ , niet-leeg door vraag 11 toegepast op $C_i, C_j, C_m, C_{m+1}$ (elke drie van deze snijden, per hypothese). De inductiehypothese levert nu een gemeenschappelijk punt van de nieuwe familie, d.w.z. van alle $m+1$ verzamelingen.

13. (a) De gesloten randen $\intcc PQ$ , $\intcc QR$ , $\intcc RP$ van een niet-ontaarde driehoek: elke twee delen een hoekpunt, maar een gemeenschappelijk punt van alle drie zou in $\intcc PQ \cap \intcc RP = \{P\}$ en in $\intcc QR$ liggen, wat $P$ uitsluit. (b) Elke drie van de verzamelingen $S_i = \{x_1, \dots, x_4\} \setminus \{x_i\}$ laten drie van de vier punten weg, en laten precies één gemeenschappelijk punt over; de totale doorsnede laat elk punt weg. De $S_i$ zijn eindig, niet convex: convexiteit is essentieel. (c) Eindig veel $H_k = \intco{k}{+\infty} \times \R$ snijden in $\intco{k_{\max}}{+\infty} \times \R \neq \emptyset$ , maar geen punt heeft $x \geq k$ voor alle $k \in \N$ : voor oneindige families is compactheid essentieel.

14. Stel $\bigcap_{i \in I}K_i = \emptyset$ en fixeer $i_0$ . Elk $x \in K_{i_0}$ mist enige $K_i$ , dus $K_{i_0} \subseteq \bigcup_{i \in I}(\R^2 \setminus K_i)$ , een overdekking door open verzamelingen ( $K_i$ is compact, dus gesloten). Door Borel–Lebesgue (Stelling 4.20) volstaan er eindig veel: $K_{i_0} \cap K_{i_1} \cap \dots \cap K_{i_N} = \emptyset$ . Maar elke drie leden van deze eindige familie van convexe verzamelingen snijden, dus maakt vraag 12 de doorsnede niet-leeg: contradictie.

15. Stel $D_p = \overline D(p, r)$ voor $p \in S$ : compacte convexe verzamelingen. Voor $p, q, s \in S$ geeft de hypothese een gesloten schijf $\overline D(z, r)$ die $p, q, s$ bevat; dan $\norm{\vect{zp}}, \norm{\vect{zq}}, \norm{\vect{zs}} \leq r$ , d.w.z. $z \in D_p \cap D_q \cap D_s$ . Door Helly (vraag 12; de familie is eindig) is er $c \in \bigcap_{p \in S}D_p$ : elke $p \in S$ voldoet aan $\norm{\vect{cp}} \leq r$ , dus $S \subseteq \overline D(c, r)$ .

16. Zij $c = x_{\lceil n/2\rceil}$ . Een gesloten halfrechte die $c$ bevat is $\intoc{-\infty}{t}$ met $t \geq c$ of $\intco{t}{+\infty}$ met $t \leq c$ . De eerste bevat $x_1, \dots, x_{\lceil n/2\rceil}$ : ten minste $\lceil n/2\rceil \geq n/2$ punten. De tweede bevat $x_{\lceil n/2\rceil}, \dots, x_n$ : precies $n - \lceil n/2\rceil + 1 = \floor{n/2} + 1 > n/2$ punten.

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$ , daarna

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

18. Merk op $m > 2n/3$ . Voor $T_1, T_2, T_3 \subseteq S$ van kardinaliteit $m$ levert vraag 17 een punt $x \in T_1 \cap T_2 \cap T_3$ ; dan $x \in \operatorname{conv}(T_i)$ voor elke $i$ : elke drie leden van $\mathcal F$ snijden. De familie is eindig (eindig veel deelverzamelingen van $S$ ) en bestaat uit convexe verzamelingen, dus geeft Helly (vraag 12) $c \in \bigcap_{\abs T = m}\operatorname{conv}(T)$ .

19. Stel enig gesloten halfvlak $H \ni c$ bevat minder dan $n/3$ punten van $S$ . Haar complement $U$ is een open halfvlak, convex, met $\abs{S \cap U} > 2n/3$ , dus $\abs{S \cap U} \geq \floor{2n/3} + 1 = m$ ; kies $T \subseteq S \cap U$ met $\abs T = m$ . Dan $\operatorname{conv}(T) \subseteq U$ door convexiteit van $U$ , dus $c \in \operatorname{conv}(T) \subseteq U$ : contradictie met $c \in H$ . Dus bevat elk gesloten halfvlak dat $c$ bevat ten minste $n/3$ punten: $c$ is een centrumspunt.

20. Neem de gelijkzijdige driehoek van zijde $L$ en $\varepsilon = L/100$ . Zij $c$ een willekeurig punt; we vertonen een gesloten halfvlak dat $c$ bevat en ten hoogste $k$ punten.

Geval 1: $c$ ligt binnen $L/10$ van een hoekpunt, zeg $B$ . Richtingen van $c$ naar $A$ en naar $C$ wijken van de richtingen $B \to A$ , $B \to C$ af met ten hoogste $\arcsin\bigl(\tfrac{L/10}{9L/10}\bigr) = \arcsin\tfrac19$ , dus maken ze een hoek $\leq \tfrac\pi3 + 2\arcsin\tfrac19 < \tfrac{2\pi}3$ . Geval 2: $c$ ligt op afstand $> L/10$ van alle hoekpunten. Als $c$ in de driehoek ligt, sommen de drie hoekgaten tussen de richtingen $u_A, u_B, u_C$ van $c$ naar de hoekpunten tot $2\pi$ , dus is enig gat $\leq 2\pi/3$ ; als $c$ buiten ligt, liggen de drie richtingen in een open halfvlak van richtingen en maken twee ervan een hoek $< \pi/2$ . In elk geval maken twee richtingen, zeg naar $X$ en $Y$ , een hoek $\leq 2\pi/3$ ; zij $w$ hun eenheidsbissectrice, zodat $\langle u_X, w\rangle, \langle u_Y, w\rangle \geq \cos\tfrac\pi3 = \tfrac12$ . Voor elk punt $b$ van de schijf rond $X$ :

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

omdat $\norm{\vect{cX}} \geq L/10 > 2\varepsilon$ (en evenzo voor $Y$ ): het open halfvlak $\{\langle \vect{cx}, w\rangle > 0\}$ slokt beide clusters op. Haar gesloten complement bevat $c$ en ten hoogste de $k$ punten van het derde cluster. Dus verslaat geen punt van het vlak $n/3$ : met vraag 19 is de centrumspuntconstante precies $1/3$ .

21. Orden de hoeken; de grootste, $\theta$ , voldoet aan $\theta \geq \pi/3$ (de drie sommeren tot $\pi$ ). Als $\theta \geq \pi/2$ , zeg in $R$ , zij $M$ het midden van de overstaande zijde $\intcc PQ$ . De mediaanformule ( $\vect{RM} = \tfrac12(\vect{RP} + \vect{RQ})$ , ontwikkel en elimineer $\langle\vect{RP}, \vect{RQ}\rangle$ met de cosinusregel) geeft

\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,

met $\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$ (het inwendig product is $\leq 0$ ). Dus bevat de schijf van diameter $\intcc PQ$ , van straal $\leq \tfrac12 < \tfrac1{\sqrt3}$ , alle drie de punten (ontaarde collineaire triples vallen onder $\theta = \pi$ ). Als $\theta < \pi/2$ is de driehoek scherphoekig; door de sinusregel is de omgeschreven straal $R_c = a/(2\sin\theta)$ met $a \leq 1$ de zijde tegenover $\theta$ , en $\theta \in \intco{\pi/3}{\pi/2}$ geeft $\sin\theta \geq \sqrt3/2$ , dus $R_c \leq 1/\sqrt3$ : de omgeschreven schijf doet het werk.

22. Voor $p \in S$ zij $K_p = \overline D(p, 1/\sqrt3)$ : compact convex. Elke drie punten $p, q, s$ van $S$ liggen paarsgewijs op afstand $\leq 1$ , dus geeft vraag 21 een schijf van straal $1/\sqrt3$ die ze bevat: haar centrum ligt in $K_p \cap K_q \cap K_s$ . Door compacte Helly (vraag 14, willekeurige families toegestaan) is er $c \in \bigcap_{p\in S}K_p$ : elke $p \in S$ ligt binnen $1/\sqrt3$ van $c$ , d.w.z. $S \subseteq \overline D(c, 1/\sqrt3)$ . Dit is de stelling van Jung in het vlak.

23. Met $G$ het zwaartepunt, $\sum_i\vect{GA_i} = 0$ , dus

\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,

en de middelste term verdwijnt: de identiteit van Leibniz. Voor de gelijkzijdige driehoek van zijde $1$ , $\norm{\vect{GA_i}} = 1/\sqrt3$ (twee derden van de hoogte $\sqrt3/2$ ), dus $\sum_i\norm{\vect{GA_i}}^2 = 1$ . Als $\overline D(O, r)$ de hoekpunten bevat, dan $3r^2 \geq \sum_i\norm{\vect{OA_i}}^2 = 3\norm{\vect{OG}}^2 + 1 \geq 1$ : $r \geq 1/\sqrt3$ , met gelijkheid die $O = G$ dwingt en alle drie de afstanden gelijk aan $r$ — de omgeschreven schijf. De Jung-constante $1/\sqrt3$ is scherp.

24. Helly in $\R^n$ : als $C_1, \dots, C_m$ ( $m \geq n + 1$ ) convexe deelverzamelingen van $\R^n$ zijn en elke $n + 1$ ervan snijden, dan snijden ze allemaal. Basisgeval $m = n + 2$ : kies $x_i \in \bigcap_{j\neq i}C_j$ ; het lemma van Radon (Oefening 17.7) splitst $x_1, \dots, x_{n+2}$ in blokken $I \mid J$ met een gemeenschappelijk omhullingspunt $z$ , en voor elke $k$ bestaat het blok dat $k$ niet bevat uit punten van $C_k$ , dus $z \in C_k$ door convexiteit, precies als in vraag 11. Inductiestap voor $m \geq n + 2$ : vervang $C_m, C_{m+1}$ door $C_m \cap C_{m+1}$ ; een $(n+1)$ -tupel van de nieuwe familie dat het gesneden lid bevat komt neer op $n + 2$ van de oude verzamelingen, behandeld door het basisgeval, en de andere tuples zijn door de hypothese gedekt. Concludeer met de inductiehypothese.

25. Lineaire algebra treedt één keer binnen: $n + 2$ vectoren in de $(n+1)$ -dimensionale ruimte van paren (totaalgewicht, gewogen positie) moeten afhankelijk zijn — dat is de affiene afhankelijkheidsrelatie. De tekens van haar coëfficiënten splitsen de punten in de twee Radon-blokken en maken van één lineaire relatie een gelijkheid van twee niet-negatieve barycentra. Convexiteit wordt precies twee keer gebruikt: in de Helly-stap (de omhulling van punten van $C_k$ blijft in $C_k$ ) en in de toepassingen (halfvlakken en schijven zijn convex). De dimensie van het vlak trad alleen binnen via het getal $4 = 2 + 2$ van punten gevoed aan Radon, d.w.z. de “ $3 = 2 + 1$ ” in de Helly-hypothese; al het overige was dimensievrij, zoals vraag 24 bevestigt. In $\R^n$ worden de constanten: Helly-getal $n + 1$ ; centrumspuntconstante $\frac1{n+1}$ (elke eindige verzameling heeft een punt waarvan elk gesloten halfvlak erdoor een fractie $\geq \frac1{n+1}$ ervan bevat); Jung-straal $\sqrt{\frac{n}{2(n+1)}}$ voor verzamelingen van diameter $1$ — gelijk aan $1/\sqrt3$ wanneer $n = 2$ .