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 gereedschappen voor de klassering die in de meetkundige hoofdstukken hierna 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 \text{ is } B \mapsto \vect{AB} \text{ 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 een 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$ belandt het verschil $\vect{AB} = B - A$ in $E$ (de sommen heffen elkaar op), Chasles wordt van $\R^3$ geërfd, en $B \mapsto \vect{AB}$ is bijectief op $E$ . Geen enkel punt van $\mathcal E$ is onderscheiden — elke keuze van een “oorsprong” $O \in \mathcal E$ werkt even goed, en alle identificaties $M \mapsto \vect{OM}$ verschillen slechts met translaties. Dit is de typische toestand: oplossingsverzamelingen van inhomogene lineaire problemen (lineaire stelsels, lineaire differentiaalvergelijkingen in Hoofdstuk 16) zijn affien, nooit lineair, en de leuze “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}$ een familie 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{gelijkwaardig}\qquad \vect{OG} = \frac{1}{\sum\lambda_i}\sum_i \lambda_i\,\vect{OA_i} \quad (\text{voor elke } O).

Barycentra zijn associatief (deelgroepen van punten mogen worden vervangen door hun deelbarycentrum met het gesommeerde gewicht) en invariant onder het herschalen van alle gewichten.

Bewijs van het bestaan en van de formules. Houd $O$ vast en schrijf $s = \sum_i\lambda_i \neq 0$ . Volgens Chasles is

\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}$ eenduidig vastlegt. Onafhankelijkheid van $O$ : voor een andere oorsprong $O'$ is

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

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. Herschalen: elke $\lambda_i$ vervangen 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: sommeren de gewichten tot nul, dan 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 codeert $(A, -1;\ B, 1)$ de vector $\vect{AB}$ . Bijhouden welk van de twee objecten een berekening voortbrengt, is de helft van de barycentrische hygiëne. Ten tweede: gewichten hebben alleen betekenis op een gemeenschappelijke factor ongelijk aan nul na; formules als “de coördinaten van $G$ zijn $\lambda_1, \dots, \lambda_k$ ” veronderstellen een normalisatie (gewoonlijk $\sum\lambda_i = 1$ ), en vergeten te normaliseren is de standaardbron van verkeerde 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); gelijkwaardig: een niet-lege verzameling die stabiel is onder barycentra. De affiene deelruimten van $\R^n$ zijn precies de oplossingsverzamelingen van lineaire stelsels $MX = B$ (bachelorjaar 1: particuliere oplossing plus kern). Een afbeelding $f \colon \mathcal{E} \to \mathcal{E}'$ heet affien wanneer zij barycentra bewaart — gelijkwaardig 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 gelijkwaardigheid voor afbeeldingen. Geldt $f(A + u) = f(A) + \varphi(u)$ : voor een barycentrum $G$ van $(A_i, \lambda_i)$ geeft alle punten vanuit $A$ uitwerken dat $f(G) = f(A) + \varphi(\vect{AG})$ met $\varphi(\vect{AG}) = \frac{\sum\lambda_i\varphi(\vect{AA_i})}{\sum\lambda_i}$ : $f(G)$ is het barycentrum van de beelden. Omgekeerd, houd $A$ vast 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 het bewaren van barycentra (met willekeurige reële gewichten, zoals verondersteld) geeft rechtstreeks $\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)$ , met de homogeniteit. Bijgevolg is $\varphi$ lineair. ∎

Opmerking 17.6

Het bewijs gebruikte barycentra met willekeurige reële gewichten: de stap met de homogeniteit neemt $t$ buiten $\intcc01$ . Wordt van een afbeelding alleen verondersteld dat zij barycentra met niet-negatieve gewichten bewaart — gelijkwaardig: middelpunten en segmenten — dan komt de lineariteit van de vectorafbeelding niet meer gratis: men krijgt slechts $\Q$ -lineariteit, en er is een hypothese van continuïteit nodig om te besluiten, precies als in Oefening 17.5. “Alle barycentra bewaren” onderscheiden van “convexe combinaties bewaren” is een kleine maar echte 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)$ . De associativiteit met het middelpunt $A' = \operatorname{bar}(B, 1; C, 1)$ toont dat

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

$G$ ligt op de zwaartelijn $AA'$ op twee derde ervan — en evenzo voor de twee andere zwaartelijnen: de drie zwaartelijnen gaan door één punt, in één regel barycentrische rekenkunde.

Voorbeeld 17.8 (De bimediaan van een vierhoek)

Zij $ABCD$ een willekeurige vierhoek (vlak of niet!) en beschouw haar bimedianen: de segmenten die de middelpunten van overstaande zijden verbinden, $M_{AB}M_{CD}$ en $M_{BC}M_{DA}$ . Voer het barycentrum $G$ van $(A,1; B,1; C,1; D,1)$ in 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 middelpunt van beide bimedianen — de twee bimedianen delen elkaar dus altijd middendoor, en de vierhoek van de vier middelpunten is een parallellogram (haar diagonalen zijn de bimedianen). Geen gevalsonderscheid, geen coördinaten, en het argument blijft woordelijk overeind voor een scheve vierhoek in $\R^3$ , waar een bewijs op een tekening al kies zou zijn: de associativiteit trekt zich niets van de dimensie aan.

Voorbeeld 17.9 (Een affiene afbeelding klasseren, 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 waarde $1$ vermijdt: volgens het criterium voor vaste punten dat hieronder wordt bewezen (Propositie 17.17) heeft $f$ precies één vast punt, gevonden door

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

op te lossen. Hercentreren in $\Omega$ (zet $x = 1 + u$ , $y = 2 + v$ ):

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

in het assenstelsel met oorsprong $\Omega$ is $f$ haar lineaire deel, een anisotrope uitrekking die vanuit het middelpunt $(1, 2)$ horizontaal met $2$ en verticaal met $3$ vermenigvuldigt. De algemene les: een affiene afbeelding is “lineaire afbeelding plus plaatsgegevens”, en die plaatsgegevens klappen ineen tot één goedgekozen oorsprong zodra $1$ geen eigenwaarde is. Omgekeerd maakt de oorsprong slecht verplaatsen de constante termen: affiene meetkunde is de kunst van het kiezen waar je $0$ legt.

Opmerking 17.10 (Methode: samenloop en collineariteit via barycentra)

Voorbeeld 17.7 is een geval van een algemeen recept. Om te bewijzen dat drie hoektransversalen van een driehoek door één punt gaan, geef je één enkel gewogen stelsel $(A, \alpha; B, \beta; C, \gamma)$ en gebruik je de associativiteit op drie manieren: $(B, C)$ groeperen toont dat het barycentrum op de transversale uit $A$ ligt, $(C, A)$ groeperen dat het op die uit $B$ ligt, en $(A, B)$ groeperen op de derde. Voor de zwaartelijnen doet het stelsel $(A, 1; B, 1; C, 1)$ al het werk; voor transversalen die de zijden in voorgeschreven verhoudingen snijden, leest men de gewichten van die verhoudingen af. Om te bewijzen dat drie punten op één rechte liggen, schrijf je er één als barycentrum van de twee andere (Oefening 17.2), of gebruik je het determinantcriterium van Oefening 17.11. Beide recepten vervangen meetkundig vernuft door boekhouding met gewichten — en daar dient de barycentrische rekenkunde precies voor.

17.2 Convexiteit, affien bekeken

Definitie 17.11

Een deelverzameling $C$ van een affiene ruimte heet convex wanneer zij elk barycentrum met niet-negatieve gewichten van haar punten bevat — gelijkwaardig: elk segment $\intcc{A}{B} = \{\operatorname{bar}(A, 1-t; B, t) : t \in \intcc{0}{1}\}$ tussen haar punten. Het convexe omhulsel $\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 de epigrafen als woordenboek. Dit is de meetkundige reden waarom convexe functies steunrechten hebben, het feit dat in Hoofdstuk 22 de ongelijkheid van Jensen zal bewijzen.

Voorbeeld 17.13 (Overbodige voortbrengers)

Zij $S = \{(0,0), (2,0), (2,2), (0,2), (1,1)\}$ . Het vijfde punt is het barycentrum

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

en ligt dus al in het omhulsel van de vier andere: $\operatorname{conv}(S)$ is het vierkant met de vier hoeken als hoekpunten. In het algemeen mag een punt van $S$ dat een barycentrum met niet-negatieve gewichten van de overige punten van $S$ is, worden geschrapt zonder het omhulsel te veranderen; de punten die nooit geschrapt kunnen worden (hier de vier hoeken) zijn de extreme punten van het omhulsel. Ze bepalen is een zuivere berekening met barycentra: $(2,0)$ bijvoorbeeld laat zich niet als $\operatorname{bar}$ van de overige punten met niet-negatieve gewichten schrijven, omdat de eerste coördinaat al het gewicht op punten met $x = 2$ zou leggen, waarna de tweede coördinaat faalt. Vragen over convexiteit herleiden telkens opnieuw 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 hoogstens $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 afhankelijk ( $k > n$ ): $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ op niet-triviale wijze; zetten we $\mu_0 = -\sum_{i\geq1}\mu_i$ , dan krijgen we gewichten $(\mu_i)$ met $\sum\mu_i = 0$ en $\sum \mu_i\,\vect{OA_i} = 0$ (voor elke $O$ ), niet alle nul. Dan sommeren de gewichten $\lambda_i - t\mu_i$ voor elke reële $t$ nog altijd tot $1$ en geldt, 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} :

zij brengen hetzelfde punt $G$ voort. Laat $t$ nu vanaf $0$ lopen: een zekere $\mu_i$ is positief (zij sommeren tot nul en zijn niet alle nul), dus is

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

welgedefinieerd en positief. In $t = t^*$ : voor de indices met $\mu_i > 0$ is $\lambda_i - t^*\mu_i \geq 0$ wegens de minimaliteit, met gelijkheid in een minimaliserende index; voor de indices met $\mu_i \leq 0$ is $\lambda_i - t^*\mu_i \geq \lambda_i > 0$ . Alle gewichten blijven niet-negatief en minstens één is gestorven: $G$ is herschreven als barycentrum van minder punten. Herhaal zolang er meer dan $n + 1$ punten overblijven. ∎

Voorbeeld 17.15

In het vlak ( $n = 2$ ): elk punt van het convexe omhulsel van een eindige verzameling ligt in een driehoek met hoekpunten in die verzameling — de meetkundige inhoud van Carathéodory, evenzeer gebruikt in de optimalisatie als in de kansrekening (mengsels).

Voorbeeld 17.16 (Het algoritme van Carathéodory uitvoeren)

Schrijf het middelpunt van het vierkant uit Voorbeeld 17.13 met zijn 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 gewichten $(\mu_i)$ met $\sum\mu_i = 0$ en $\sum\mu_i\vect{OA_i} = 0$ : hier voldoet $\mu = (1, -1, 1, -1)$ (de twee diagonalen delen hun middelpunt). De schuif $\lambda_i \mapsto \lambda_i - t\mu_i$ houdt het barycentrum voor elke $t$ vast; de uiterste 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 met twee punten — zelfs beter dan de drie die de stelling waarborgt, omdat het middelpunt toevallig op een segment tussen voortbrengers ligt. Het algoritme is volstrekt mechanisch: zoek een afhankelijkheid, schuif tot een gewicht sterft, herhaal.

17.3 Gereedschappen voor de affiene klassering

Propositie 17.17 (Vaste punten van affiene afbeeldingen)

Zij $f$ een affien endomorfisme van een eindigdimensionale affiene ruimte met lineair deel $\varphi$ . Geldt $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 zonder vast punt, zijn de basisobstructie.)

Bewijs. Houd $O$ vast 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)$ , dat wil zeggen

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

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

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

zodat de afbeelding in het assenstelsel met oorsprong $\Omega$ luidt als $u \mapsto \varphi(u)$ : zuiver lineair. Geldt $1 \in \operatorname{Sp}\varphi$ , dan bestaat er ofwel geen vast punt (de getoonde vergelijking kan onoplosbaar zijn, zoals voor een translatie), ofwel een hele affiene deelruimte vaste punten (tel bij een oplossing een willekeurige eigenvector bij eigenwaarde $1$ op): de eenduidigheid is precies de spectrale voorwaarde. ∎

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

Een affiene isometrie van het euclidische vlak heeft haar lineaire deel in $O(2)$ : een rotatie $R_\theta$ of een spiegeling (volume van bachelorjaar 1). Is $\theta \neq 0$ , dan is $1 \notin \operatorname{Sp} R_\theta$ , dus is de afbeelding een rotatie om een uniek middelpunt (Propositie 17.17). Is het lineaire deel een spiegeling, dan is zij ofwel een spiegeling in een as (er bestaan vaste punten) ofwel een schuifspiegeling (een spiegeling samengesteld met een translatie langs de as, zonder vast punt). Samen met de translaties is dit de volledige klassering van de isometrieën van het vlak.

Opmerking 17.19 (De isometrieën van het vlak, in één oogopslag)

De gevallen verzameld: de identiteit; translaties ( $\vec f = \mathrm{id}$ , zonder vast punt behalve in het triviale geval); rotaties (lineair deel $R_\theta$ met $\theta \neq 0$ : één middelpunt); spiegelingen (lineair deel een spiegeling, een rechte vaste punten); schuifspiegelingen (hetzelfde lineaire deel, geen vast punt). Vier families plus de identiteit, elk herkend aan slechts twee gegevens: het lineaire deel en de verzameling vaste punten — het patroon van Propositie 17.17, uitputtend gemaakt.

Voorbeeld 17.20 (Een schuifspiegeling, 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 is $1 \in \operatorname{Sp}\vec f$ en zwijgt Propositie 17.17. Vaste punten zouden tegelijk $x = y + 1$ en $y = x + 1$ vereisen: onmogelijk — er zijn er geen, dus $f$ is geen spiegeling. Kwadrateren beslist de klassering:

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

de translatie over $(2, 2)$ : $f$ is de schuifspiegeling met als as de rechte $y = x$ (passend verschoven: het middelpunt van $M$ en $f(M)$ ligt altijd op $y = x + {}$ constante, hier $y = x$ , zoals men op $M = (0, 0) \mapsto (1,1)$ nagaat) en met schuifvector $(1, 1)$ , de helft van $f \circ f$ . Vergelijk met Oefening 17.6, waar hetzelfde lineaire deel maar een andere constante een echte spiegeling opleverde: is de eigenwaarde $1$ aanwezig, dan 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 rechte, waarvan het lineaire deel $a$ de eigenwaarde $1$ vermijdt: er is een uniek vast punt $\omega = \frac{b}{1-a}$ , en daar hercentreren (het eendimensionale geval van de propositie hierboven) maakt van $f$ een 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 in Hoofdstuk 7 voor zulke recursies wordt geleerd — “trek het vaste punt af” — is precies de vectorialisatie van een affiene afbeelding in haar vaste punt; de convergentie voor $\abs a < 1$ is het contractieverschijnsel dat Hoofdstuk 4 tot de vastepuntsstelling van Banach maakte. Eén idee, drie hoofdstukken.

Voorbeeld 17.22 (Het middelpunt van een rotatie vinden)

Zij $f(x, y) = (-y + 2,\ x)$ . Het lineaire deel is $\varphi(x, y) = (-y, x)$ : de rotatie over de hoek $\frac\pi2$ , waarvan het spectrum $\{\iu, -\iu\}$ de waarde $1$ vermijdt. Volgens 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 middelpunt $(1, 1)$ over de hoek $\frac\pi2$ . De algemene les: is $1 \notin \operatorname{Sp}\vec f$ , dan kost het klasseren van $f$ één lineair stelsel — de meetkunde zit volledig in het lineaire deel, de rekenkunde volledig in het lokaliseren van het middelpunt.

Opmerking 17.23 (Waar de affiene taal hierna wordt gebruikt)

Barycentra en affiene afbeeldingen zijn de grammatica van de meetkundige hoofdstukken hierna: raaklijnen en raakvlakken zijn affiene objecten (Hoofdstukken 18 en 19), een affiene verandering van veranderlijke vermenigvuldigt oppervlakten en volumes met $\abs{\det \vec f}$ (Hoofdstuk 20), en de verwachtingswaarde is een barycentrum met gewichten die door een kansverdeling worden gegeven, en daarom beheerst de convexiteit de ongelijkheid van Jensen (Hoofdstuk 22). In het volume van bachelorjaar 3 draagt dezelfde woordenschat van de convexiteit de studie van de $L^p$ -normen en van de integraalongelijkheden.

Opmerking 17.24 (Vooruitblik binnen dit volume)

Twee draden verlaten dit hoofdstuk. De affiene draad: raaklijnen (Hoofdstuk 18) en raakvlakken (Hoofdstuk 19) zijn affiene deelruimten die aan niet-lineaire objecten hangen, en de klassering van de kwadrieken in het hoofdstuk over oppervlakken draait op de middelpuntsvergelijking $A\Omega = -b$ van dit hoofdstuk. De convexe draad is langer: de convexiteit van halfvlakken en schijven drijft de theorie van Helly in de weekendopgave aan; de convexiteit van functies geeft de ongelijkheid van Jensen (Hoofdstuk 22); en de laatste stelling van het boek — het uitstervingscriterium 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 kansrekening. Ook barycentra keren daar terug: een verwachtingswaarde is een barycentrum met kansgewichten.

17.4 Oefeningen

Oefening 17.1 ★

Zijn de volgende verzamelingen affiene deelruimten van $\R^3$ ? 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 verenigbaar stelsel.

Oplossing

Oplossing van Oefening 17.1.

$\{x + y + z = 1\}$ : affien vlak, met als richting het vectorvlak $\{x + y + z = 0\}$ , dimensie $2$ . Voegen we $x - z = 3$ toe, dan krijgen we een affiene rechte (twee onafhankelijke vergelijkingen), met 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 middelpunt van $(1,0,0)$ en $(-1,0,0)$ is de oorsprong, die niet op de cilinder ligt): niet affien. Een verenigbaar stelsel $MX = B$ : affiene deelruimte $X_0 + \ker M$ van dimensie $\dim\ker M$ , zoals in Definitie 17.5 in herinnering gebracht.

Oefening 17.2 ★

Bewijs dat drie verschillende punten $A, B, C$ van een affiene ruimte op één rechte liggen dan en slechts dan als $C$ een barycentrum van $A$ en $B$ is, en dan en slechts dan als de vectoren $\vect{AB}, \vect{AC}$ afhankelijk zijn. Leid daaruit boekhouding met gewichten in de stijl van Menelaos af: is $C = \operatorname{bar}(A, 1 - t; B, t)$ , lokaliseer $C$ dan voor $t = \frac12$ , $t = 2$ en $t = -1$ .

Oplossing

Oplossing van Oefening 17.2.

$C = \operatorname{bar}(A, 1-t; B, t)$ betekent $\vect{AC} = t\,\vect{AB}$ : het bestaan van zulk een $t$ is precies de afhankelijkheid van $\vect{AC}$ met $\vect{AB} \neq 0$ , dat wil zeggen collineariteit. Liggingen: $t = \frac12$ : het middelpunt; $t = 2$ : voorbij $B$ , op de afstand van $B$ tot $A$ ( $\vect{AC} = 2\vect{AB}$ ); $t = -1$ : het spiegelbeeld 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 (als die er zijn) en $f \circ f$ .

Oplossing

Oplossing van Oefening 17.3.

$M$ is de projectiematrix op $\operatorname{Vect}(1,1)$ langs $(1,-1)$ (ga $M^2 = M$ na). Beeld van $f$ : $\{MX + C\} = C + \operatorname{im} M$ : de affiene rechte door $(1,0)$ met richting $(1,1)$ . Vaste punten: $X = MX + C$ , dat wil zeggen $(I - M)X = C$ ; maar $C = (1, 0)^{\mathsf T}$ en $\operatorname{im}(I - M) = \operatorname{Vect}(1,-1)$ ; ligt $(1,0)$ daarin? $(1, 0) = \alpha(1,-1)$ dwingt $\alpha = 1$ en $0 = -1$ af: 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 beeldrechte — $f$ is een “schuifprojectie”: de projectie op de rechte, samengesteld met een verschuiving.

Oefening 17.4 ★★

(Associativiteit in actie) Verdeel in een driehoek $ABC$ de zijden $BC$ , $CA$ , $AB$ met $I, J, K$ 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 dat te voorzien?

Oplossing

Oplossing van Oefening 17.4.

$I = \operatorname{bar}(B, 2; C, 1)$ (want $\vect{BI} = \frac13\vect{BC}$ legt $I$ dichter bij $B$ : gewichten $2$ op $B$ en $1$ op $C$ — controle: $\vect{BI} = \frac{1}{3}\vect{BC}$ ). Evenzo $J = \operatorname{bar}(C, 2; A, 1)$ en $K = \operatorname{bar}(A, 2; B, 1)$ . Tellen we de drie gewogen stelsels samen, dan is het barycentrum van $(I, 1; J, 1; K, 1)$ (elk met totaal gewicht $3$ , dus vervang $I$ door zijn stelsel, enzovoort) gelijk aan

\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 — te voorzien, omdat de constructie $A, B, C$ cyclisch behandelt en het zwaartepunt het unieke vaste punt van de cyclische symmetrie van de gewichten is.

Oefening 17.5 ★★

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

Oplossing

Oplossing van Oefening 17.5.

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

Additiviteit: $\frac{(O + u) + (O + v)}{2} = O + \frac{u + v}{2}$ , dus het bewaren van middelpunten geeft $g\bigl(\frac{u+v}{2}\bigr) = \frac{g(u) + g(v)}{2}$ ; met $v = 0$ : $g(u/2) = g(u)/2$ ; samen: $g(u + v) = 2g\bigl(\frac{u+v}{2}\bigr) = g(u) + g(v)$ .

$\Q$ -homogeniteit: de additiviteit geeft $g(nu) = ng(u)$ ( $n \in \N$ , met inductie), dan $g(-u) = -g(u)$ (optellen), dan $g(\frac pq u) = \frac pq g(u)$ ( $q$ maal toepassen, en de injectiviteit van het schalen gebruiken).

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

Oefening 17.6 ★★

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

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 ene vergelijking $y = x - 1$ (de twee componenten zijn gelijkwaardig): elk punt van de rechte $y = x - 1$ is vast. Dus houdt $f$ die rechte puntsgewijs vast: $f$ is de spiegeling in die as (een isometrie met een rechte vaste punten en als lineair deel een spiegeling). Daarmee in overeenstemming is $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) Zijn $A_1, \dots, A_{n+2}$ punten van een affiene ruimte van dimensie $n$ . Bewijs dat zij in twee disjuncte groepen kunnen worden gesplitst waarvan de convexe omhulsels elkaar snijden. (Zoek, als in het bewijs van Carathéodory, gewichten $\mu_i$ , niet alle nul, met $\sum\mu_i = 0$ en $\sum\mu_i\vect{OA_i} = 0$ ; scheid de positieve van de negatieve gewichten en normaliseer beide kanten.)

Oplossing

Oplossing van Oefening 17.7.

De $n + 1$ vectoren $\vect{A_1A_i}$ ( $i \geq 2$ ) zijn afhankelijk in dimensie $n$ : er zijn $\mu_i$ , niet alle nul, met $\sum_{i\geq2} \mu_i\vect{A_1A_i} = 0$ ; zet $\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 de indices: $P = \{i : \mu_i > 0\}$ en $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 leden zijn wegens de betrekking gelijk aan het punt $X$ met $\vect{OX} = \frac1s\sum_{i\in P}\mu_i\vect{OA_i}$ ): een gemeenschappelijk punt van de twee convexe omhulsels, 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 omgekeerd dat al zulke projecties idempotent zijn. (Toon eerst aan dat $\operatorname{im} f$ uit vaste punten bestaat.)

Oplossing

Oplossing van Oefening 17.8.

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

Structuur van projectie: $\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). Beschouw voor een willekeurig punt $X$ de vector $\vect{f(X)\,X}$ ; $\vec f$ toepassen geeft

\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$ . Bijgevolg toont $X = f(X) + \vect{f(X)X}$ dat $X$ een punt van $\mathcal{F}$ is, 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 de associativiteit aan dat de rechte $AG$ de zijde $BC$ snijdt in $M = \operatorname{bar}(B, 2;\ C, 3)$ , en lokaliseer $G$ op het segment $\intcc AM$ ; lokaliseer op dezelfde manier het snijpunt van $BG$ met $CA$ .

Oplossing

Oplossing van Oefening 17.9.

Zij $M = \operatorname{bar}(B, 2;\ C, 3)$ , met totaal gewicht $5$ . De associativiteit geeft $G = \operatorname{bar}(A, 1;\ M, 5)$ , dus $\vect{AG} = \frac56\,\vect{AM}$ : $G$ ligt op het segment $\intcc AM$ , op vijf zesde ervan vanaf $A$ . Omdat $A \notin (BC)$ , snijdt de rechte $(AG) = (AM)$ de rechte $(BC)$ in het enkele punt $M$ , met $\vect{BM} = \frac35\,\vect{BC}$ . Evenzo geeft de associativiteit met $N = \operatorname{bar}(C, 3;\ A, 1)$ (totaal gewicht $4$ , $\vect{CN} = \frac14\,\vect{CA}$ ) dat $G = \operatorname{bar}(B, 2;\ N, 4)$ : de rechte $(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$ vasthoudt met lineair deel $\lambda\,\mathrm{id}$ . Bewijs dat de samenstelling $h_{\Omega', \mu} \circ h_{\Omega, \lambda}$ een homothetie met verhouding $\lambda\mu$ is wanneer $\lambda\mu \neq 1$ , en een translatie wanneer $\lambda\mu = 1$ ; bereken in het geval $\lambda = \mu = -1$ (twee puntspiegelingen) 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}$ . Is $\lambda\mu \neq 1$ , dan is $1 \notin \operatorname{Sp}(\lambda\mu\,\mathrm{id})$ , zodat Propositie 17.17 een uniek vast punt $\Omega''$ oplevert en $g$ , daar gevectorialiseerd, gelijk is aan $\lambda\mu\,\mathrm{id}$ : de homothetie $h_{\Omega'', \lambda\mu}$ . Is $\lambda\mu = 1$ , dan 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$ (puntspiegelingen) is de vector $2\omega' - 2\omega = 2\,\vect{\Omega\Omega'}$ : de samenstelling van de puntspiegelingen in $\Omega$ en vervolgens $\Omega'$ is de translatie over $2\,\vect{\Omega\Omega'}$ .

Oefening 17.11 ★★

(Menelaos) Zij in een driehoek $ABC$ $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'$ op één rechte liggen dan en slechts dan als $\alpha\beta\gamma = 1$ . (Schrijf elk punt als barycentrum van twee hoekpunten; toon aan dat drie punten op één rechte liggen dan en slechts dan als hun rijen barycentrische coördinaten 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 dat $1\cdot \vect{A'B} - \alpha\,\vect{A'C} = 0$ , dat wil zeggen $A' = \operatorname{bar}(B, 1;\ C, -\alpha)$ (totaal gewicht $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 criterium voor collineariteit. Geef elk punt $P$ zijn genormaliseerde barycentrische rij $p = (p_A, p_B, p_C)$ met $p_A + p_B + p_C = 1$ , ten opzichte van $(A, B, C)$ . Geldt $\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 het sommeren van de elementen dat $\sum c_i = 0$ , en is $\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, dat wil zeggen collineair. Omgekeerd geeft een affiene afhankelijkheid $(t_i)$ een rij $w = \sum t_ip_i$ waarvan de elementen tot $0$ sommeren en met $\sum_j w_j\vect{OV_j} = 0$ ; uitwerken vanuit $A$ geeft $w_B \vect{AB} + w_C\vect{AC} = 0$ , dus $w = 0$ wegens de affiene onafhankelijkheid van $(A, B, C)$ : de rijen zijn lineair afhankelijk. Collineariteit komt dus neer op een verdwijnende $3 \times 3$ -determinant, en de rijen schalen met de factoren $1 - \alpha$ , $1 - \beta$ , $1 - \gamma$ (die niet nul zijn) verandert niets:

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

Bijgevolg liggen $A', B', C'$ op één rechte dan en slechts dan als $\alpha\beta\gamma = 1$ : de stelling van Menelaos.

Oefening 17.12 ★★★

Bewijs dat het convexe omhulsel van een compacte deelverzameling $K$ van $\R^n$ compact is. (Volgens Stelling 17.14 is $\operatorname{conv}(K)$ het beeld van een compacte verzameling onder een continue afbeelding.) Toon met een voorbeeld in $\R^2$ aan dat het convexe omhulsel van een gesloten verzameling niet gesloten hoeft te zijn.

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}$ , en 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), en 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 punten van de as legt, heeft tweede coördinaat $t$ , dus is

\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 ligt niet in het omhulsel: niet gesloten.

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

De twee types van Radon 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, waarbij het punt van Radon (oranje) het snijpunt van de twee diagonalen is. — De twee types van Radon 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, waarbij het punt van Radon (oranje) het snijpunt van de twee diagonalen is.

Probleem 17.1

Weekendopgave — 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 altijd in twee groepen splitsen waarvan de convexe omhulsels elkaar snijden. Deze opgave maakt van dat ene feit uit de lineaire algebra een ketting van stellingen uit de combinatorische meetkunde: de doorsnedestelling van Helly, de stelling van het centrumpunt (een mediaan in twee dimensies) en de overdekkingsstelling van Jung. Overal is het vlak $\R^2$ met zijn gewone euclidische structuur, en is $\det$ de determinant in de canonieke basis.

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

Toon aan dat de affiene onafhankelijkheid niet van de keuze van het basispunt $A_0$ afhangt, en dat zij gelijkwaardig is met: telkens wanneer twee families gewichten, elk sommerend tot $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 aan dat elk punt $M$ een uniek drietal $(\alpha, \beta, \gamma)$ toelaat met $\alpha + \beta + \gamma = 1$ en $M = \operatorname{bar}(A, \alpha; B, \beta; C, \gamma)$ — zijn 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 rechten $BC$ , $CA$ , $AB$ zijn de coördinaatrechten $\{\alpha = 0\}$ , $\{\beta = 0\}$ , $\{\gamma = 0\}$ . Toon aan 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 rechten het vlak in precies zeven gebieden snijden, geklasseerd door de tekens van $(\alpha, \beta, \gamma)$ (waarbij het tekenpatroon $(-, -, -)$ onmogelijk is).
Zij $u \colon \R^2 \to \R$ een affiene afbeelding (een affiene vorm). Toon aan dat $u(M) = \alpha\,u(A) + \beta\,u(B) + \gamma\,u(C)$ , dat de niveauverzamelingen van een niet-constante affiene vorm rechten zijn, dat elke rechte zo ontstaat, en dat de gesloten halfvlakken $\{u \geq c\}$ convex zijn.

Deel II — Partities van Radon, verfijnd. Een familie van $n + 2$ punten van $\R^n$ ligt in algemene ligging wanneer elke $n + 1$ ervan affien onafhankelijk zijn. Een affiene afhankelijkheid 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 (en dus voor elke) oorsprong $O$ .

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

Deel III — De stelling van Helly in het vlak.

Zijn $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 aan dat het punt van Radon tot alle vier de verzamelingen behoort. (Voor elke $k$ bestaat het blok dat $x_k$ niet bevat, uit punten van $C_k$ .)
(Helly) Zijn $C_1, \dots, C_m$ ( $m \geq 3$ ) convexe deelverzamelingen van $\R^2$ waarvan elke drie elkaar snijden. Bewijs dat $\bigcap_{i=1}^m C_i \neq \emptyset$ , met inductie naar $m$ : vervang $C_{m-1}$ en $C_m$ door $C_{m-1} \cap C_m$ en ga de hypothese voor de nieuwe familie na met vraag 11.
Drie tegenvoorbeelden, één per hypothese: (a) de drie gesloten zijden van een driehoek snijden elkaar 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 hypothese over drievoudige doorsneden maar niet aan het besluit (convexiteit telt); (c) de gesloten halfvlakken $H_k = \intco{k}{+\infty} \times \R$ , $k \in \N$ , snijden elkaar 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 compacte convexe deelverzamelingen van $\R^2$ waarvan elke drie elkaar snijden. Toon met vraag 12 en de eigenschap van Borel–Lebesgue (Stelling 4.20) aan dat $\bigcap_{i \in I} K_i \neq \emptyset$ .
(Eerste dividend) Zij $S$ een eindige verzameling punten van het vlak en $r > 0$ . Toon aan: liggen elke drie punten van $S$ in een zekere gesloten schijf met straal $r$ , dan ligt $S$ in één gesloten schijf met straal $r$ . (Pas Helly toe op de schijven $\overline D(p, r)$ , $p \in S$ .)

Deel IV — De stelling van het centrumpunt. Een centrumpunt van een eindige verzameling $S$ van $n$ punten van het vlak is een punt $c$ (niet noodzakelijk in $S$ ) zodanig dat elk gesloten halfvlak dat $c$ bevat, minstens $n/3$ punten van $S$ bevat.

(Dimensie $1$ ) Toon voor reële getallen $x_1 \leq \dots \leq x_n$ aan dat de mediaan $c = x_{\lceil n/2 \rceil}$ hieraan voldoet: elke gesloten halfrechte die $c$ bevat, bevat minstens $n/2$ van de $x_i$ .
(Telhulpstelling) Zijn $A, B, C$ deelverzamelingen van $S$ met $\abs A, \abs B, \abs C > \tfrac{2n}3$ , toon dan aan dat $A \cap B \cap C \neq \emptyset$ .
Zij $m = \floor{2n/3} + 1$ en zij $\mathcal F$ de (eindige) familie van de convexe omhulsels $\operatorname{conv}(T)$ , $T \subseteq S$ , $\abs T = m$ . Toon aan dat elke drie leden van $\mathcal F$ een gemeenschappelijk punt hebben, en leid uit Helly een punt $c$ af dat aan alle gemeenschappelijk is.
Bewijs dat deze $c$ een centrumpunt van $S$ is: de stelling van het centrumpunt. (Bevatte een gesloten halfvlak door $c$ minder dan $n/3$ punten, dan zou zijn open complement een verzameling $T$ van $m$ punten bevatten, en zou $\operatorname{conv}(T)$ het punt $c$ mijden.)
Scherpte: zij $n = 3k$ en plaats $k$ punten in elk van drie schijven met kleine straal $\varepsilon$ rond de hoekpunten van een grote driehoek. Toon aan dat er voor elk punt $c$ van het vlak een gesloten halfvlak dat $c$ bevat, hoogstens $n/3$ punten van $S$ bevat, zodat de constante $1/3$ niet verbeterd kan worden. (Van de drie richtingen van $c$ naar de middelpunten van de schijven maken er twee een hoek van hoogstens $2\pi/3$ .)

Deel V — De stelling van Jung en synthese.

(Hulpstelling over driehoeken) Zijn $P, Q, R$ drie punten met paarsgewijze afstanden $\leq 1$ . Toon aan dat zij in een gesloten schijf met straal $1/\sqrt3$ liggen. (Is een hoek $\geq \pi/2$ , neem dan de schijf met de langste zijde als middellijn, met de formule voor de zwaartelijn $\norm{RM}^2 = \tfrac12\norm{RP}^2 + \tfrac12\norm{RQ}^2 - \tfrac14\norm{PQ}^2$ ; is de driehoek scherphoekig, begrens dan 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 met diameter $\leq 1$ is bevat in een gesloten schijf met straal $1/\sqrt3$ .
Scherpte: bewijs voor de gelijkzijdige driehoek $A_1A_2A_3$ met zijde $1$ en zwaartepunt $G$ 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 besluit 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$ : zijn eindig veel convexe verzamelingen zodanig dat elke $n + 1$ ervan elkaar snijden, dan snijden zij elkaar alle. (Het lemma van Radon Oefening 17.7 behandelt $n + 2$ verzamelingen; pas dan inductie toe als in vraag 12.)
Synthese. Zet de ketting

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

in elkaar en geef in telkens één zin aan: waar de lineaire algebra binnenkomt, waar de tekens van de gewichten binnenkomen, waar de convexiteit binnenkomt, en welke ene stap de dimensie van het vlak gebruikte. Wat worden de constanten $3$ (in Helly), $1/3$ (centrumpunt) en $1/\sqrt3$ (Jung) in $\R^n$ ? (Formuleer zonder bewijs.)

Oplossing

Oplossing van Probleem 17.1.

1. Neem $A_j$ als nieuw basispunt: voor $i \neq j$ is $\vect{A_jA_i} = \vect{A_0A_i} - \vect{A_0A_j}$ . Geldt $\sum_{i \neq j} c_i\vect{A_jA_i} = 0$ , dan geeft uitwerken dat $\sum_{i \notin \{0, j\}} c_i\,\vect{A_0A_i} - \bigl(\sum_{i\neq j} c_i\bigr)\vect{A_0A_j} = 0$ ; de onafhankelijkheid van de $\vect{A_0A_i}$ dwingt $c_i = 0$ af voor $i \notin \{0, j\}$ , en dan $c_0 = 0$ : onafhankelijkheid in $A_j$ . Voor de gelijkwaardigheid: twee families gewichten $(\lambda_i)$ , $(\lambda_i')$ die tot $1$ sommeren met hetzelfde barycentrum geven, met $\nu = \lambda - \lambda'$ : $\sum\nu_i = 0$ en (met oorsprong $A_0$ ) $\sum_{i \geq 1}\nu_i\,\vect{A_0A_i} = 0$ , dus $\nu = 0$ onder de onafhankelijkheid. Omgekeerd laat een niet-triviale betrekking $\sum_{i\geq1}\mu_i \vect{A_0A_i} = 0$ , aangevuld met $\mu_0 = -\sum_{i\geq1} \mu_i$ , toe om $t(\mu_i)$ bij elke familie gewichten op te tellen zonder het barycentrum te verplaatsen: geen eenduidigheid.

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

3. Uit $\alpha\vect{MA} + \beta\vect{MB} + \gamma\vect{MC} = 0$ en Chasles volgt $\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 de bilineariteit en $\det(\vect{MA}, \vect{AC}) = -\beta D$ , $\det(\vect{AB}, \vect{MA}) = -\gamma D$ . De twee andere formules volgen uit dezelfde berekening met de rollen cyclisch verwisseld.

4. Per definitie is $\operatorname{conv}\{A, B, C\}$ de verzameling barycentra met niet-negatieve gewichten; de gewichten tot som $1$ normaliseren en de eenduidigheid (vraag 2) inroepen geeft: $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 wordt gerealiseerd: schaal een drietal met het juiste teken en met minstens één $+$ -element zo dat de (positieve) som $1$ is — bijvoorbeeld $(-1, 1, 1)$ , $(3, -1, -1)$ , $(\frac13, \frac13, \frac13)$ en permutaties.

5. Een affiene afbeelding bewaart barycentra (Definitie 17.5), dus is $u(M) = \alpha u(A) + \beta u(B) + \gamma u(C)$ . Schrijven we $u(x, y) = ax + by + c$ met $(a, b) \neq (0,0)$ , dan is $\{u = c'\}$ een rechte, en elke rechte $ax + by = c'$ is zulk een niveauverzameling. Geldt $u(M), u(N) \geq c$ en $t \in \intcc01$ , dan is $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$ en $3\mu_3 + \mu_4 = 0$ geven (met $\mu_4 = 3$ ) de afhankelijkheid $(\mu_1, \mu_2, \mu_3, \mu_4) = (-1, -1, -1, 3)$ . De tekens splitsen als $\{A_4\} \mid \{A_1, A_2, A_3\}$ , en elke kant met $3$ normaliseren geeft

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

het zwaartepunt van de driehoek: het punt van Radon 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$ . Bestonden er twee onafhankelijke afhankelijkheden $\mu, \mu'$ , dan zou een geschikte combinatie $\nu = \mu'_{n+2}\mu - \mu_{n+2}\mu'$ (of $\mu$ zelf als beide laatste coëfficiënten verdwijnen) een afhankelijkheid ongelijk aan nul zijn met $\nu_{n+2} = 0$ ; beperken we ons tot $A_1, \dots, A_{n+1}$ en nemen we $A_1$ als basispunt, dan is een zekere $\nu_i \neq 0$ met $i \geq 2$ (één enkel gewicht ongelijk aan nul kan niet tot nul sommeren), wat een niet-triviale betrekking $\sum_{i\geq2}\nu_i\vect{A_1A_i} = 0$ geeft: de $n+1$ punten zouden affien afhankelijk zijn, tegen de algemene ligging in. Dus $\dim\ker \Phi = 1$ . Hetzelfde argument met beperking toont dat een afhankelijkheid ongelijk aan nul geen verdwijnende coëfficiënt heeft.

8. Zij $\mu \neq 0$ een afhankelijkheid, $P = \{i : \mu_i > 0\}$ en $N = \{i : \mu_i < 0\}$ : beide niet leeg ( $\sum\mu_i = 0$ , $\mu \neq 0$ ) en samen uitputtend (geen coëfficiënt is nul). De constructie van Radon (Oefening 17.7) brengt het gemeenschappelijke punt van de omhulsels precies uit deze partitie voort. Omdat de afhankelijkheid op een scalair ongelijk aan nul na uniek is (vraag 7), is het ongeordende paar $\{P, N\}$ — en dus de partitie van Radon — uniek.

9. De blokken zijn niet leeg, dus is het type $(1,3)$ of $(2,2)$ . Type $(1,3)$ , blok $\{j\}$ : het punt van Radon ligt in $\operatorname{conv}\{A_j\} = \{A_j\}$ , dus $A_j \in \operatorname{conv}$ van de drie andere; het kan niet op een zijde liggen (dan zouden drie punten collineair zijn, tegen de algemene ligging in), dus is $A_j$ inwendig aan de driehoek. Type $(2,2)$ , blokken $\{i,j\} \mid \{k,l\}$ : het punt van Radon $z$ ligt in $\intcc{A_i}{A_j} \cap \intcc{A_k}{A_l}$ , en $z$ is geen uiteinde (dat zou drie punten op één rechte leggen): de twee segmenten kruisen elkaar in een inwendig punt. Bovendien ligt geen enkel punt in het omhulsel van de andere: zulk een insluiting $A_l = \operatorname{bar}(A_i, \lambda_i)_{i \neq l}$ met $\lambda_i \geq 0$ is een affiene afhankelijkheid met tekenpatroon $(+,+,+,-)$ , wat wegens de eenduidigheid (vraag 8) de partitie $(1,3)$ zou maken. In het geval $(2,2)$ liggen de vier punten dus in convexe ligging en zijn de kruisende segmenten de diagonalen.

10. De vergelijkingen $\mu_2 + \mu_3 = 0$ , $\mu_3 + \mu_4 = 0$ en $\sum\mu_i = 0$ geven de afhankelijkheid $(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 punt van Radon is het middelpunt van het vierkant, waar de twee diagonalen elkaar kruisen — type $(2,2)$ , zoals de figuur 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\}$ . Houd $k \in \{1, \dots, 4\}$ vast, zeg $k \in I$ . Elke $j \in J$ voldoet aan $j \neq k$ , dus $x_j \in C_k$ wegens de keuze $x_j \in \bigcap_{l \neq j}C_l$ ; omdat $C_k$ convex is, is $z \in \operatorname{conv}\{x_j : j \in J\} \subseteq C_k$ . Omdat $k$ willekeurig was, is $z \in C_1 \cap C_2 \cap C_3 \cap C_4$ .

12. Inductie naar $m$ . Voor $m = 3$ is de hypothese het besluit; $m = 4$ is vraag 11. Zij $m \geq 4$ , neem de uitspraak voor $m$ verzamelingen aan, en neem $C_1, \dots, C_{m+1}$ met de eigenschap over drievoudige doorsneden. Zet $C_m' = C_m \cap C_{m+1}$ , convex. De familie $C_1, \dots, C_{m-1}, C_m'$ heeft $m$ leden; een drietal dat $C_m'$ mijdt, snijdt volgens de hypothese, en een drietal $\{C_i, C_j, C_m'\}$ heeft als doorsnede $C_i \cap C_j \cap C_m \cap C_{m+1}$ , niet leeg volgens vraag 11 toegepast op $C_i, C_j, C_m, C_{m+1}$ (elke drie daarvan snijden elkaar wegens de hypothese). De inductiehypothese levert nu een gemeenschappelijk punt van de nieuwe familie, dat wil zeggen van alle $m+1$ verzamelingen.

13. (a) De gesloten zijden $\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\}$ liggen én in $\intcc QR$ , dat $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 houden precies één gemeenschappelijk punt over; de totale doorsnede laat elk punt weg. De $S_i$ zijn eindig, niet convex: de 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 enkel punt heeft $x \geq k$ voor alle $k \in \N$ : voor oneindige families is de compactheid essentieel.

14. Stel dat $\bigcap_{i \in I}K_i = \emptyset$ en houd $i_0$ vast. Elke $x \in K_{i_0}$ mist een zekere $K_i$ , dus $K_{i_0} \subseteq \bigcup_{i \in I}(\R^2 \setminus K_i)$ , een overdekking met open verzamelingen ( $K_i$ is compact en dus gesloten). Volgens 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 convexe verzamelingen snijden elkaar, dus maakt vraag 12 de doorsnede niet leeg: tegenspraak.

15. Zet $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 is $\norm{\vect{zp}}, \norm{\vect{zq}}, \norm{\vect{zs}} \leq r$ , dat wil zeggen $z \in D_p \cap D_q \cap D_s$ . Volgens Helly (vraag 12; de familie is eindig) is er een $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}$ : minstens $\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$ , en dan

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

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

19. Stel dat een gesloten halfvlak $H \ni c$ minder dan $n/3$ punten van $S$ bevat. Zijn complement $U$ is een open halfvlak, convex, met $\abs{S \cap U} > 2n/3$ en dus $\abs{S \cap U} \geq \floor{2n/3} + 1 = m$ ; kies $T \subseteq S \cap U$ met $\abs T = m$ . Dan is $\operatorname{conv}(T) \subseteq U$ wegens de convexiteit van $U$ , dus $c \in \operatorname{conv}(T) \subseteq U$ : tegenspraak met $c \in H$ . Bijgevolg bevat elk gesloten halfvlak dat $c$ bevat, minstens $n/3$ punten: $c$ is een centrumpunt.

20. Neem de driehoek gelijkzijdig met zijde $L$ en $\varepsilon = L/100$ . Zij $c$ een willekeurig punt; wij geven een gesloten halfvlak dat $c$ en hoogstens $k$ punten bevat.

Geval 1: $c$ ligt binnen $L/10$ van een hoekpunt, zeg $B$ . De richtingen van $c$ naar $A$ en naar $C$ wijken van de richtingen $B \to A$ en $B \to C$ hoogstens $\arcsin\bigl(\tfrac{L/10}{9L/10}\bigr) = \arcsin\tfrac19$ af, dus maken zij een hoek $\leq \tfrac\pi3 + 2\arcsin\tfrac19 < \tfrac{2\pi}3$ . Geval 2: $c$ ligt op afstand $> L/10$ van alle hoekpunten. Ligt $c$ in de driehoek, dan sommeren de drie hoekgaten tussen de richtingen $u_A, u_B, u_C$ van $c$ naar de hoekpunten tot $2\pi$ , dus is een gat $\leq 2\pi/3$ ; ligt $c$ erbuiten, dan liggen de drie richtingen in een open halfvlak van richtingen en maken er twee 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$ is

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

want $\norm{\vect{cX}} \geq L/10 > 2\varepsilon$ (en evenzo voor $Y$ ): het open halfvlak $\{\langle \vect{cx}, w\rangle > 0\}$ verzwelgt beide trossen. Zijn gesloten complement bevat $c$ en hoogstens de $k$ punten van de derde tros. Geen enkel punt van het vlak verslaat dus $n/3$ : samen met vraag 19 is de constante van het centrumpunt precies $1/3$ .

21. Orden de hoeken; de grootste, $\theta$ , voldoet aan $\theta \geq \pi/3$ (de drie sommeren tot $\pi$ ). Is $\theta \geq \pi/2$ , zeg in $R$ , zij dan $M$ het middelpunt van de overstaande zijde $\intcc PQ$ . De formule voor de zwaartelijn ( $\vect{RM} = \tfrac12(\vect{RP} + \vect{RQ})$ , uitwerken en $\langle\vect{RP}, \vect{RQ}\rangle$ met de cosinusregel elimineren) 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 inproduct is $\leq 0$ ). De schijf met middellijn $\intcc PQ$ , met straal $\leq \tfrac12 < \tfrac1{\sqrt3}$ , bevat dus alle drie de punten (ontaarde collineaire drietallen vallen onder $\theta = \pi$ ). Is $\theta < \pi/2$ , dan is de driehoek scherphoekig; volgens 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 voldoet.

22. Zij $K_p = \overline D(p, 1/\sqrt3)$ voor $p \in S$ : compact en convex. Elke drie punten $p, q, s$ van $S$ liggen paarsgewijs op afstand $\leq 1$ , dus geeft vraag 21 een schijf met straal $1/\sqrt3$ die hen bevat: haar middelpunt ligt in $K_p \cap K_q \cap K_s$ . Volgens de compacte Helly (vraag 14, waar willekeurige families zijn toegestaan) is er een $c \in \bigcap_{p\in S}K_p$ : elke $p \in S$ ligt binnen $1/\sqrt3$ van $c$ , dat wil zeggen $S \subseteq \overline D(c, 1/\sqrt3)$ . Dit is de stelling van Jung in het vlak.

23. Met $G$ het zwaartepunt is $\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 met zijde $1$ is $\norm{\vect{GA_i}} = 1/\sqrt3$ (twee derde van de hoogte $\sqrt3/2$ ), dus $\sum_i\norm{\vect{GA_i}}^2 = 1$ . Bevat $\overline D(O, r)$ de hoekpunten, dan is $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$ afdwingt en alle drie de afstanden gelijk aan $r$ — de omgeschreven schijf. De constante $1/\sqrt3$ van Jung is scherp.

24. Helly in $\R^n$ : zijn $C_1, \dots, C_m$ ( $m \geq n + 1$ ) convexe deelverzamelingen van $\R^n$ waarvan elke $n + 1$ elkaar snijden, dan snijden zij elkaar alle. 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 punt $z$ van de omhulsels, en voor elke $k$ bestaat het blok dat $k$ niet bevat uit punten van $C_k$ , zodat $z \in C_k$ wegens de 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)$ -tal van de nieuwe familie dat het doorgesneden lid bevat, komt neer op $n + 2$ van de oude verzamelingen, wat het basisgeval afhandelt, en de overige tallen worden door de hypothese gedekt. Besluit met de inductiehypothese.

25. De lineaire algebra komt één keer binnen: $n + 2$ vectoren in de $(n+1)$ -dimensionale ruimte van paren (totaal gewicht, gewogen ligging) moeten afhankelijk zijn — dat is de affiene afhankelijkheid. De tekens van haar coëfficiënten splitsen de punten in de twee blokken van Radon en maken van één lineaire betrekking een gelijkheid van twee niet-negatieve barycentra. De convexiteit wordt precies tweemaal gebruikt: in de stap van Helly (het omhulsel van punten van $C_k$ blijft in $C_k$ ) en in de toepassingen (halfvlakken en schijven zijn convex). De dimensie van het vlak kwam alleen binnen via het aantal $4 = 2 + 2$ punten dat aan Radon werd gevoerd, dat wil zeggen via de “ $3 = 2 + 1$ ” in de hypothese van Helly; al het overige was dimensievrij, zoals vraag 24 bevestigt. In $\R^n$ worden de constanten: het getal van Helly $n + 1$ ; de constante van het centrumpunt $\frac1{n+1}$ (elke eindige verzameling heeft een punt waardoor elk gesloten halfvlakkig gebied een aandeel $\geq \frac1{n+1}$ ervan bevat); en de straal van Jung $\sqrt{\frac{n}{2(n+1)}}$ voor verzamelingen met diameter $1$ — gelijk aan $1/\sqrt3$ voor $n = 2$ .

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst