Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

18Vectorruimten

Hier begint de lineaire algebra: de axioma’s van vectorruimten isoleren wat $\R^2$ , $\R^3$ , veeltermruimten en functieruimten gemeen hebben — men kan optellen en schalen. Twee hoofdstukken bouwen de theorie op (Hoofdstuk 19 voegt de dimensie toe); de taal die zij opzetten — opspansel, vrije familie, basis, directe som — is het dagelijks brood van elk hoofdstuk daarna. Overal staat $K$ voor $\R$ of $\C$ (de scalairen).

18.1 Definitie en voorbeelden

Definitie 18.1 (Vectorruimte)

Een $K$ -vectorruimte is een verzameling $E$ met een optelling die $(E, +)$ tot een abelse groep maakt (nulelement genoteerd $0_E$ of $0$ ), en een scalaire vermenigvuldiging $K \times E \to E$ zodat voor alle $\lambda, \mu \in K$ en $x, y \in E$

\lambda(x + y) = \lambda x + \lambda y,\quad (\lambda + \mu) x = \lambda x + \mu x,\quad \lambda(\mu x) = (\lambda\mu) x,\quad 1\,x = x .

Gevolgen: $0\,x = 0_E$ , $\lambda\,0_E = 0_E$ , $(-1)x = -x$ , en $\lambda x = 0_E \implies \lambda = 0$ of $x = 0_E$ (vermenigvuldig met $\lambda^{-1}$ ).

Bewijs van de gevolgen. Voor $0\,x = 0_E$ : uit $(0 + 0)x = 0x + 0x$ en $(0+0)x = 0x$ mag men $0x$ in de groep $(E, +)$ wegstrepen. Voor $\lambda\,0_E$ : dezelfde kunstgreep op $\lambda(0_E + 0_E)$ . Voor $(-1)x$ : tel $x$ erbij op,

x + (-1)x = 1\,x + (-1)x = \bigl(1 + (-1)\bigr)x = 0\,x = 0_E ,

zodat $(-1)x$ de tegengestelde van $x$ is. Ten slotte, is $\lambda x = 0_E$ met $\lambda \neq 0$ , vermenigvuldig dan met $\lambda^{-1}$ (de scalairen vormen een lichaam) en gebruik de twee axioma’s $\lambda^{-1}(\lambda x) = (\lambda^{-1}\lambda)x = 1x = x$ samen met $\lambda^{-1}0_E = 0_E$ : $x = 0_E$ . Hoe klein ook, deze vier regels worden stilzwijgend gebruikt op elke bladzijde die volgt — en de laatste is precies waar lichamen nodig zijn: over de scalairen $\Z$ zou de “ruimte” $\Z/2\Z$ haar schenden met $2\,x = 0$ . ∎

Voorbeeld 18.2

$K^n$ (coördinaatsgewijze bewerkingen); de veeltermen $K[X]$ ; de functies $\mathcal{F}(A, K)$ van een willekeurige verzameling $A$ naar $K$ (puntsgewijze bewerkingen) — met daarin de continue functies, de rijen $\mathcal{F}(\N, \R)$ enzovoort; en $\C$ als $\R$ -vectorruimte. In elk geval worden de axioma’s geërfd van die van $K$ .

Definitie 18.3 (Deelruimte)

$F \subseteq E$ is een deelruimte wanneer $0_E \in F$ en $F$ stabiel is onder optelling en scalaire vermenigvuldiging — equivalent:

F \neq \emptyset \qquad\text{en}\qquad \forall x, y \in F,\ \forall \lambda \in K,\quad x + \lambda y \in F .

Een deelruimte is zelf een vectorruimte. Elke doorsnede van deelruimten is een deelruimte; een vereniging bijna nooit (hetzelfde bewijs als Oefening 7.6).

Voorbeeld 18.4

In $\mathcal{F}(\R, \R)$ : de continue functies, de afleidbare, de veeltermen van graad $\leq n$ (genoteerd $K_n[X]$ binnen $K[X]$ ), de oplossingen van een homogene lineaire differentiaalvergelijking (Stelling 5.10 zei precies dat). Geen voorbeelden: $\{f : f(0) = 1\}$ (geen nulelement), graad precies $n$ (niet stabiel onder optelling).

Voorbeeld 18.5 (Deelruimte of niet: vier oordelen, beargumenteerd)

In de ruimte van reële rijen:

$\{u : u \text{ begrensd}\}$ is een deelruimte: $0$ is begrensd, en is $\abs{u_n} \leq M$ en $\abs{v_n} \leq M'$ , dan is $\abs{u_n + \lambda v_n} \leq M + \abs\lambda M'$ .
$\{u : u_n \to 1\}$ is geen deelruimte: de nulrij ontbreekt (en de som van twee leden nadert tot $2$ ).
$\{u : u \text{ monotoon}\}$ is er geen: $u_n = n$ en $v_n = -n + (-1)^n$ zijn monotoon, hun som $(-1)^n$ niet; de stabiliteit onder optelling is het axioma dat faalt, ook al bevat de verzameling $0$ en alle scalaire veelvouden van haar leden.
$\{u : u_{n+1} = u_n^2\}$ is er geen: zij bevat $0$ , maar $2u$ ontsnapt zodra $u$ een lid ongelijk aan nul is ( $2u_{n+1} \neq (2u_n)^2$ in het algemeen) — het kwadrateren is de niet-lineariteit.

De werkvolgorde is altijd dezelfde: toets eerst $0$ (het goedkoopst), daarna de stabiliteit — en om te weerleggen verslaat één expliciet paar tegenvoorbeelden elke hoeveelheid twijfel.

18.2 Opspansel, sommen, directe sommen

Definitie 18.6 (Lineaire combinaties, opspansel)

Een lineaire combinatie van de familie $(x_1, \dots, x_p)$ vectoren van $E$ is elke $\lambda_1 x_1 + \dots + \lambda_p x_p$ ( $\lambda_i \in K$ ). De verzameling van al deze combinaties is het opspansel $\operatorname{Vect}(x_1, \dots, x_p)$ : het is een deelruimte, en wel de kleinste die de familie bevat.

Bewijs van de twee beweringen. Stabiliteit: een som van twee lineaire combinaties $\sum\lambda_i x_i + \sum\mu_i x_i = \sum(\lambda_i + \mu_i)x_i$ is er weer een, en een scalair veelvoud $\mu\sum\lambda_i x_i = \sum(\mu\lambda_i) x_i$ ook; de nulcombinatie toont dat $0$ erbij hoort: het opspansel is een deelruimte. Minimaliteit: zij $H$ een willekeurige deelruimte die $x_1, \dots, x_p$ bevat. Wegens de stabiliteit onder scalaire vermenigvuldiging ligt elke $\lambda_i x_i$ in $H$ , en wegens de stabiliteit onder optelling hun som: elke lineaire combinatie hoort bij $H$ , dat wil zeggen $\operatorname{Vect}(x_1, \dots, x_p) \subseteq H$ . Het opspansel is dus bevat in elke deelruimte die de familie bevat: het is de kleinste. ∎

Definitie 18.7 (Som, directe som)

Voor deelruimten $F, G$ van $E$ is

F + G = \{\,u + v : u \in F,\ v \in G\,\}

een deelruimte (de kleinste die $F \cup G$ bevat). De som is direct, genoteerd $F \oplus G$ , wanneer elk element van $F + G$ zich op precies één manier als $u + v$ laat schrijven; equivalent (zie hieronder) wanneer $F \cap G = \{0\}$ . Geldt $E = F \oplus G$ , dan heten de deelruimten complementair in $E$ .

Voorbeeld 18.8 (Een som van twee rechten)

Zij in $\R^3$ $F = \operatorname{Vect}\bigl((1,0,1)\bigr)$ en $G = \operatorname{Vect}\bigl((0,1,1)\bigr)$ . Hun som is

F + G = \{\,a(1,0,1) + b(0,1,1)\,\} = \{(a,\ b,\ a + b)\} = \{(x, y, z) : z = x + y\},

het vlak door de oorsprong dat beide rechten bevat. Het is strikt groter dan de vereniging $F \cup G$ (het loutere kruis van de twee rechten): de vector $(1, 1, 2) = (1,0,1) + (0,1,1)$ ligt in de som maar op geen van beide rechten. En $F \cap G = \{0\}$ (een gemeenschappelijke vector vereist $a(1,0,1) = b(0,1,1)$ , waarvan de eerste twee coördinaten $a = b = 0$ afdwingen): de som is direct, en $F \oplus G$ is precies dat vlak.

Propositie 18.9

$F + G$ is direct dan en slechts dan als $F \cap G = \{0\}$ .

Bewijs. Ligt een $w \neq 0$ in $F \cap G$ , dan zijn $w = w + 0 = 0 + w$ twee ontbindingen van $w$ . Omgekeerd, is $u + v = u' + v'$ met $u, u' \in F$ en $v, v' \in G$ , dan hoort $u - u' = v' - v$ bij $F \cap G = \{0\}$ : de ontbindingen zijn eenduidig. ∎

Methode 18.10 (Bewijzen dat $E = F \oplus G$ )

Twee dingen na te gaan, elk met zijn standaardopening.

Triviale doorsnede. Neem $x \in F \cap G$ , schrijf beide voorwaarden voor het lidmaatschap uit, en knijp $x = 0$ eruit. (Redeneer nooit met een tekening: zie de valkuilen hieronder.)
De som is alles. Neem een willekeurige $x \in E$ en produceer de ontbinding $x = f + g$ — ofwel door $f$ te raden vanuit het doel ( $f$ moet aan de definiërende eigenschap van $F$ voldoen, wat gewoonlijk haar formule dicteert), ofwel door het lineaire stelsel op te lossen dat $x$ tegen voortbrengers van $F$ en $G$ uitdrukt.

Wordt de formule voor de ontbinding geraden, dan is de eenduidigheid automatisch dankzij stap 1; is alleen het bestaan onduidelijk, dan zit het werk in stap 2. De twee voorbeelden hieronder laten de methode lopen: voor even en oneven functies wordt de formule voor $f$ afgedwongen door de gewenste identiteit in $x$ en in $-x$ te evalueren; voor veeltermen die in een punt nul worden, door in $a$ te evalueren.

Voorbeeld 18.11

In $\mathcal{F}(\R, \R)$ zijn de even functies $\mathcal{P}$ en de oneven functies $\mathcal{I}$ complementair: elke $f$ schrijft zich als

f(x) = \underbrace{\frac{f(x) + f(-x)}{2}}_{\text{even}} + \underbrace{\frac{f(x) - f(-x)}{2}}_{\text{oneven}},

en een functie die zowel even als oneven is, is nul. (Toegepast op $\exp$ is dit het paar $(\cosh, \sinh)$ van Hoofdstuk 4.)

Voorbeeld 18.12 (Een complementair paar in $K_n[X]$ )

Leg $a \in K$ vast en stel $F = \{P \in K_n[X] : P(a) = 0\}$ en $G = \operatorname{Vect}(1)$ (de constanten). Dan is $K_n[X] = F \oplus G$ . Inderdaad bestaat $F \cap G$ uit de constanten die in $a$ nul worden, dus uit $\{0\}$ ; en elke $P$ ontbindt als

P = \underbrace{\bigl(P - P(a)\bigr)}_{\in F} + \underbrace{P(a)}_{\in G} .

De ontbinding is het onthouden waard: de waarde in een punt aftrekken is de standaardmanier om op “functies die in $a$ nul worden” te projecteren. Merk op dat $F$ een grote deelruimte is en $G$ een kleine; een complementair paar hoeft in geen enkele zin in evenwicht te zijn.

Voorbeeld 18.13 (Een complementaire deelruimte is nooit eenduidig)

Zij in $\R^2$ $F = \operatorname{Vect}\bigl((1,0)\bigr)$ (de $x$ -as). Zowel $G = \operatorname{Vect}\bigl((0,1)\bigr)$ als $G' = \operatorname{Vect}\bigl((1,1)\bigr)$ is complementair met $F$ : elk snijdt $F$ alleen in $0$ , en elk paar sommeert tot $\R^2$ . De ontbindingen van eenzelfde vector verschillen:

(2,\ 1.5) = \underbrace{(2, 0)}_{\in F} + \underbrace{(0, 1.5)}_{\in G} = \underbrace{(0.5,\ 0)}_{\in F} + \underbrace{(1.5,\ 1.5)}_{\in G'} .

In feite is elke rechte behalve $F$ zelf een complementaire van $F$ in $\R^2$ : complementairen zijn er in overvloed, en spreken over “de” complementaire is betekenisloos zolang geen extra structuur (een inproduct, Hoofdstuk 23) er één uitkiest.

Twee ontbindingen van hetzelfde punt van ℝ2 langs F (de x-as): met complementaire G (verticale val) en met complementaire G' (schuine val). De F-componenten verschillen: een projectie hangt af van de richting van de afdaling. — Twee ontbindingen van hetzelfde punt van $\R^2$ langs $F$ (de $x$ -as): met complementaire $G$ (verticale val) en met complementaire $G'$ (schuine val). De $F$ -componenten verschillen: een projectie hangt af van de richting van de afdaling.

18.3 Vrije families, voortbrengende families, bases

Definitie 18.14

Een familie $(x_1, \dots, x_p)$ vectoren van $E$ heet:

voortbrengend (voor $E$ ) wanneer $\operatorname{Vect}(x_1,\dots,x_p) = E$ ;
vrij (haar vectoren lineair onafhankelijk) wanneer

$\lambda_1 x_1 + \dots + \lambda_p x_p = 0 \implies \lambda_1 = \dots = \lambda_p = 0 ;$

in het andere geval afhankelijk;
een basis wanneer zij vrij en voortbrengend is.

Propositie 18.15 (Coördinaten)

$(e_1, \dots, e_n)$ is een basis van $E$ dan en slechts dan als elke $x \in E$ zich op precies één manier als combinatie $x = \lambda_1 e_1 + \dots + \lambda_n e_n$ laat schrijven; de scalairen $\lambda_i$ zijn de coördinaten van $x$ in de basis.

Bewijs. Voortbrengend $=$ het bestaan van de ontbinding. Eenduidigheid $=$ vrijheid: twee ontbindingen van dezelfde $x$ verschillen met een combinatie die gelijk is aan $0$ ; de vrijheid dwingt al haar coëfficiënten — de verschillen van de coördinaten — tot nul. Omgekeerd geeft een niet-triviale nulcombinatie de twee ontbindingen $0 = \sum \lambda_i e_i = \sum 0\,e_i$ . ∎

Voorbeeld 18.16

De canonieke basis van $K^n$ : $e_i = (0, \dots, 1, \dots, 0)$ (een $1$ op plaats $i$ ). De monomen $(1, X, X^2, \dots, X^n)$ : een basis van $K_n[X]$ (vrijheid: een nulcombinatie is de nulveelterm, dus zijn alle coëfficiënten nul, Definitie 8.1). In $\C$ over $\R$ : de basis $(1, \iu)$ .

Opmerking 18.17 (Coördinaten zijn teamwerk)

De eerste coördinaat van $x$ in een basis $(e_1, \dots, e_n)$ hangt af van alle basisvectoren, niet alleen van $e_1$ . In $\R^2$ : de vector $(3, 1)$ heeft eerste coördinaat $3$ in de canonieke basis, maar eerste coördinaat $2$ in de basis $\bigl((1,0), (1,1)\bigr)$ — los $(3,1) = a(1,0) + b(1,1)$ op: $b = 1$ , $a = 2$ . Eén basisvector veranderen schudt elke coördinaat door elkaar; Hoofdstuk 21 zal dat door elkaar schudden in de basisovergangsmatrix verpakken.

Voorbeeld 18.18 (Een kandidaat-basis toetsen, van begin tot eind)

Is $\mathcal{F} = (1 + X,\ 1 + X^2,\ X + X^2)$ een basis van $\R_2[X]$ ? Schrijf $u_1, u_2, u_3$ voor de drie veeltermen. Vrijheid: een nulcombinatie $a\,u_1 + b\,u_2 + c\,u_3 = 0$ geeft, coëfficiënt na coëfficiënt,

a + b = 0, \qquad a + c = 0, \qquad b + c = 0 ;

door de eerste twee af te trekken volgt $b = c$ , en dan geeft de derde $2b = 0$ : $a = b = c = 0$ , dus vrij. Voortbrengend: in plaats van drie stelsels op te lossen, merk je de symmetrische combinatie op

u_1 + u_2 - u_3 = (1 + X) + (1 + X^2) - (X + X^2) = 2 ,

dus $1 = \frac12(u_1 + u_2 - u_3)$ ; vervolgens

X = u_1 - 1 = \tfrac12\bigl(u_1 - u_2 + u_3\bigr), \qquad X^2 = u_2 - 1 = \tfrac12\bigl(-u_1 + u_2 + u_3\bigr).

De monomen liggen in het opspansel, dus alles ligt erin: $\mathcal{F}$ is een basis. Als toegift geeft het samenvoegen van de drie formules de coördinaten van elke $P = \alpha + \beta X + \gamma X^2$ :

P = \frac{\alpha + \beta - \gamma}{2}\,u_1 + \frac{\alpha - \beta + \gamma}{2}\,u_2 + \frac{-\alpha + \beta + \gamma}{2}\,u_3 .

(Controle met $P = X$ : coördinaten $\bigl(\frac12, -\frac12, \frac12\bigr)$ , zoals hierboven gevonden.) Twee lessen: symmetrie in de familie verbergt gewoonlijk een kortere weg; en zodra de dimensie beschikbaar is (Hoofdstuk 19) komt de hele voortbrengende helft van dit werk gratis — drie vrije vectoren van een $3$ -dimensionale ruimte vormen altijd een basis.

Propositie 18.19 (Handige vrijheidscriteria)

Een familie veeltermen ongelijk aan nul met paarsgewijs verschillende graden is vrij.
Een vector aan een vrije familie toevoegen houdt haar vrij dan en slechts dan als die vector buiten het opspansel van de familie ligt.
Elke deelfamilie van een vrije familie is vrij; elke familie die een voortbrengende familie bevat, is voortbrengend.

Bewijs. (1) Kijk in een nulcombinatie naar de hoogste aanwezige graad: zijn coëfficiënt moet nul zijn (niets heft die graad op), en zo cascadeer je naar beneden.

(2) Is $x \in \operatorname{Vect}(x_1, \dots, x_p)$ , dan is de betrekking $x - \sum\lambda_i x_i = 0$ niet-triviaal. Omgekeerd moet een niet-triviale nulcombinatie van $(x_1, \dots, x_p, x)$ de $x$ met een coëfficiënt ongelijk aan nul bevatten (anders is zij in tegenspraak met de vrijheid van de kleine familie), en het oplossen naar $x$ plaatst die in het opspansel.

(3) Deelfamilie: een nulcombinatie van de deelfamilie is er een van de hele familie met de ontbrekende coëfficiënten op $0$ gezet; de vrijheid van de grote familie doodt ze alle. Overfamilie: elke vector van $E$ is al een combinatie van het voortbrengende deel; geef de extra vectoren de coëfficiënt $0$ . ∎

Voorbeeld 18.20 (Het trapprincipe)

Zij $P_0, P_1, \dots, P_n \in K_n[X]$ met $\deg P_k = k$ voor elke $k$ (een “trap” van graden). Dan is $(P_0, \dots, P_n)$ een basis van $K_n[X]$ . De vrijheid is Propositie 18.19 (1). Voor de voortbrengende eigenschap redeneren we met eindige afdaling op de graad: zij $Q \in K_n[X]$ , $Q \neq 0$ , van graad $d$ met kopcoëfficiënt $a$ , en zij $b \neq 0$ de kopcoëfficiënt van $P_d$ . Dan heeft $Q - \frac ab P_d$ graad $< d$ (de kopterm valt weg); vervang $Q$ door dat verschil en herhaal: na hoogstens $n + 1$ stappen bereikt men de nulveelterm, en het terugdraaien van de aftrekkingen drukt $Q$ uit als combinatie van de $P_k$ . Twee trappen kwamen we al tegen: de verschoven machten $\bigl((X-a)^k\bigr)_{0 \leq k \leq n}$ (Oefening 18.4), en de producten van Newton $\bigl((X - x_0)(X - x_1)\cdots(X - x_{k-1})\bigr)_{0 \leq k \leq n}$ , die in de weekendopgave aan het werk worden gezet.

Voorbeeld 18.21 (Vrijheid in functieruimten)

In $\mathcal{F}(\R,\R)$ is de familie $(\eu^{a_1 x}, \dots, \eu^{a_p x})$ met $a_1 < \dots < a_p$ vrij: deel een nulcombinatie door $\eu^{a_p x}$ en laat $x \to +\infty$ ; de laatste coëfficiënt sterft, en zo cascadeer je naar beneden (Oefening 18.8 werkt dit en varianten uit). Vrijheid van functies bewijst men door te evalueren: in goedgekozen punten, in het oneindige, of na afleiden.

Voorbeeld 18.22 (Een verborgen betrekking krimpt een opspansel)

Wat is in $\mathcal{F}(\R, \R)$ het opspansel $\operatorname{Vect}(1,\ \cos^2,\ \sin^2)$ ? De identiteit $\cos^2 + \sin^2 = 1$ is een niet-triviale nulcombinatie

1\cdot\mathbf{1} + (-1)\cos^2 + (-1)\sin^2 = 0 :

de familie is afhankelijk, en het opspansel wordt al voortgebracht door $(1, \cos^2)$ alleen ( $\sin^2 = 1 - \cos^2$ ). Die kleinere familie is vrij: $a + b\cos^2 x = 0$ voor alle $x$ geeft, in $x = 0$ en $x = \frac\pi2$ : $a + b = 0$ en $a = 0$ . Het opspansel is dus een vlak binnen de functieruimte — en het bevat ook $\cos 2x = 2\cos^2 x - 1$ : families goniometrische functies die lineair lijken, storten routinematig in onder identiteiten, en daarom moet vrijheid worden bewezen, nooit uit de lengte van de lijst worden aangenomen.

Opmerking 18.23 (Veelgemaakte fouten)

Vier klassieke vallen. Paarsgewijs is niet genoeg: in $\R^2$ zijn de vectoren $(1,0)$ , $(0,1)$ , $(1,1)$ paarsgewijs niet evenredig en toch afhankelijk — vrijheid is een eigenschap van de hele familie, getoetst met één globale combinatie, nooit twee aan twee. De nulvector vergiftigt alles: elke familie die $0$ bevat is afhankelijk ( $1\cdot 0 = 0$ is een niet-triviale betrekking), hoe onschuldig de andere vectoren ook zijn. Vereniging is geen som: $F \cup G$ is vrijwel nooit een deelruimte (Definitie 18.3); de kleinste deelruimte die beide bevat is $F + G$ , gewoonlijk veel groter dan de vereniging — in $\R^2$ hebben twee verschillende rechten een kruis als vereniging en het hele vlak als som. Direct vereist triviale doorsnede, geen disjunctheid: twee deelruimten zijn nooit disjunct (beide bevatten $0$ ); de juiste voorwaarde is $F \cap G = \{0\}$ , en die moet worden bewezen, niet van een tekening afgelezen — vergelijk Voorbeeld 18.13, waar vele verschillende $G$ voldoen. Vrijheid hangt af van de scalairen: het paar $(1, \iu)$ is vrij in $\C$ opgevat als $\R$ -vectorruimte, maar afhankelijk in $\C$ opgevat als $\C$ -vectorruimte ( $\iu\cdot 1 + (-1)\cdot\iu = 0$ ). Weet altijd welk lichaam werkt voordat je een familie vrij noemt — de weekendopgave van Hoofdstuk 19 maakt van precies deze gevoeligheid irrationaliteitsbewijzen.

Opmerking 18.24 (Waar deze taal heen gaat)

Alles na dit hoofdstuk spreekt de taal die hier is opgezet. Hoofdstuk 19 telt basisvectoren en zet “vrij” en “voortbrengend” om in ongelijkheden voor één geheel getal, de dimensie. Hoofdstuk 20 bestudeert de afbeeldingen die met de twee bewerkingen verenigbaar zijn; directe sommen worden daar projectoren. Hoofdstuk 21 codeert vectoren door hun coördinaten in een basis — Propositie 18.15 is de vergunning voor die codering — en Hoofdstuk 23 legt lengten en hoeken bovenop de lineaire structuur. In het volume van bachelorjaar 2 draaien dezelfde axioma’s, woordelijk, over willekeurige lichamen en in oneindige dimensie; nergens in dit hoofdstuk werd eindigheid gebruikt.

Opmerking 18.25 (Drie draden om door boek 3 heen te volgen)

Volg drie bepaalde ideeën uit dit hoofdstuk terwijl zij groeien. Het trapprincipe (Voorbeeld 18.20) keert terug als de Newton-basis in de weekendopgave van dit hoofdstuk, als de binomiale basis $(B_k)$ aldaar, en als de kunstgreep met de alternant van veeltermen in de weekendopgave van Hoofdstuk 22: één lemma, drie determinantvrije dividenden. Evalueren als vrijheidstoets (Voorbeeld 18.21) wordt het interpolatie-isomorfisme van Hoofdstuk 20, daarna het criterium van Vandermonde uit Hoofdstuk 22, en daarna de Gram-toets van Hoofdstuk 23: dezelfde reflex, drie keer aangescherpt. Directe sommen (Definitie 18.7) worden projectoren in Hoofdstuk 20, orthogonale splitsingen $E = F \oplus F^\perp$ in Hoofdstuk 23, en de ontbinding in verklaard deel plus rest van de kleinste kwadraten in de weekendopgave van Hoofdstuk 25. Erg weinig in dit boek is niet, in de grond, een van deze drie ideeën in nieuwe kleren.

18.4 Oefeningen

Oefening 18.1 ★

Welke van de volgende verzamelingen zijn deelruimten?

$\{(x, y, z) \in \R^3 : x + 2y - z = 0\}$ ;
$\{(x, y, z) \in \R^3 : x + 2y - z = 1\}$ ;
$\{(x, y) \in \R^2 : xy \geq 0\}$ ;
$\{P \in \R[X] : P(1) = 0\}$ ;
$\{f \in \mathcal{F}(\R,\R) : f \text{ begrensd}\}$ .

Oplossing

Oplossing van Oefening 18.1.

Ja: bevat $0$ , en de definiërende vergelijking is lineair (stabiel onder $x + \lambda y$ ).
Nee: bevat $(0,0,0)$ niet.
Nee: $(1, 0)$ en $(0, -1)$ horen erbij ( $xy = 0$ ), hun som $(1, -1)$ niet ( $xy = -1 < 0$ ).
Ja: $0$ wordt nul in $1$ ; $(P + \lambda Q)(1) = P(1) + \lambda Q(1) = 0$ .
Ja: de nulfunctie is begrensd; is $\abs f \leq M$ en $\abs g \leq M'$ , dan is $\abs{f + \lambda g} \leq M + \abs\lambda M'$ .

Oefening 18.2 ★

Ligt $(1, 2, 1)$ in $\operatorname{Vect}\bigl((1,0,1),\, (1,1,0)\bigr)$ in $\R^3$ ? En $(2, 1, 1)$ ? Beschrijf $\operatorname{Vect}\bigl((1,0,1),(1,1,0)\bigr)$ met een vergelijking.

Oplossing

Oplossing van Oefening 18.2.

$(1,2,1) = a(1,0,1) + b(1,1,0)$ vereist $a + b = 1$ , $b = 2$ , $a = 1$ : onverenigbaar ( $a + b = 3 \neq 1$ ): niet in het opspansel. $(2,1,1) = a(1,0,1) + b(1,1,0)$ : $b = 1$ , $a = 1$ , $a + b = 2$ : verenigbaar, dus $(2,1,1) = (1,0,1) + (1,1,0)$ , wel in het opspansel.

Vergelijking: $(x, y, z) = (a + b, b, a)$ betekent $x = y + z$ : het opspansel is het vlak $\{x - y - z = 0\}$ .

Oefening 18.3 ★

Beslis over de vrijheid in $\R^3$ : $\;\bigl((1,1,0), (1,0,1), (0,1,1)\bigr)$ ; $\;\bigl((1,2,3), (2,4,6)\bigr)$ ; $\;\bigl((1,0,0), (1,1,0), (1,1,1), (0,1,1)\bigr)$ .

Oplossing

Oplossing van Oefening 18.3.

Eerste familie: $\lambda(1,1,0) + \mu(1,0,1) + \nu(0,1,1) = 0$ geeft $\lambda + \mu = 0$ , $\lambda + \nu = 0$ , $\mu + \nu = 0$ : optellen geeft $2(\lambda + \mu + \nu) = 0$ , en door elke vergelijking af te trekken $\lambda = \mu = \nu = 0$ : vrij.

Tweede: $(2,4,6) = 2(1,2,3)$ : afhankelijk.

Derde: vier vectoren in $\R^3$ — noodzakelijk afhankelijk zodra de dimensie beschikbaar is (Hoofdstuk 19); rechtstreeks: $(0,1,1) = -(1,0,0) + 0\cdot(1,1,0) + (1,1,1)$ , inderdaad $(-1,0,0) + (1,1,1) = (0,1,1)$ : een niet-triviale betrekking.

Oefening 18.4 ★

Bewijs dat $(1, X - 1, (X-1)^2, (X-1)^3)$ een basis is van $\R_3[X]$ , en geef de coördinaten van $X^3$ daarin. (Taylor in $1$ !)

Oplossing

Oplossing van Oefening 18.4.

De veeltermen $1, (X-1), (X-1)^2, (X-1)^3$ hebben verschillende graden $0, 1, 2, 3$ : vrij (Propositie 18.19 (1)); vier vrije vectoren die voortbrengen (elke $P \in \R_3[X]$ ontwikkelt in machten van $X - 1$ , bijvoorbeeld via Taylor voor veeltermen, vergelijk het bewijs van Propositie 8.11): een basis. Voor $X^3$ , Taylor in $1$ : $P = X^3$ , $P(1) = 1$ , $P'(1) = 3$ , $P''(1) = 6$ , $P'''(1) = 6$ :

X^3 = 1 + 3(X - 1) + 3(X-1)^2 + (X-1)^3 ,

coördinaten $(1, 3, 3, 1)$ (een rij van Pascal, zoals te verwachten uit $X^3 = ((X-1)+1)^3$ ).

Oefening 18.5 ★★

Zij in $\R^4$ $F = \{(x,y,z,t) : x = y = z\}$ en $G = \{(x,y,z,t) : x = t = 0\}$ . Bewijs dat $F \oplus G = \R^4$ , en ontbind $(1,2,3,4)$ overeenkomstig.

Oplossing

Oplossing van Oefening 18.5.

$F \cap G$ : de voorwaarden $x = y = z$ en $x = t = 0$ geven samen $x = 0$ , dus $y = z = 0$ , en $t = 0$ : de doorsnede is $\{0\}$ . Som: zoek bij gegeven $(x,y,z,t)$ een $(a,a,a,b) \in F$ en een $(0,c,d,0) \in G$ die daartoe sommeren: $a = x$ , $b = t$ , $c = y - x$ , $d = z - x$ : altijd mogelijk. Dus $\R^4 = F \oplus G$ , en

(1,2,3,4) = (1,1,1,4) + (0,1,2,0) .

Oefening 18.6 ★★

Zij in de ruimte van de rijen $F$ de verzameling van de convergente rijen en $G = \operatorname{Vect}(u)$ met $u_n = (-1)^n$ . Bewijs dat $F \cap G = \{0\}$ . Is $F + G$ de hele ruimte van de rijen?

Oplossing

Oplossing van Oefening 18.6.

Een element van $G$ is $\lambda u$ ; convergeert het, dan is noodzakelijk $\lambda = 0$ (want $\lambda u_n = \lambda(-1)^n$ heeft de twee deelrijlimieten $\pm \lambda$ ): $F \cap G = \{0\}$ .

$F + G$ is niet alles: die som bestaat uit rijen van de vorm $c_n + \lambda(-1)^n$ met $(c_n)$ convergent. De rij $v_n = n$ is niet van die vorm ( $v_n - \lambda(-1)^n$ is onbegrensd, nooit convergent). Dus $F \oplus G \subsetneq$ (de ruimte van alle rijen).

Oefening 18.7 ★★

Zij $F, G, H$ deelruimten van $E$ . Bewijs dat

F \cap (G + (F \cap H)) = (F \cap G) + (F \cap H),

en toon met een voorbeeld in $\R^2$ aan dat de onbeperkte distributiviteit $F \cap (G + H) = (F\cap G) + (F \cap H)$ faalt.

Oplossing

Oplossing van Oefening 18.7.

( $\supseteq$ ) Zowel $F \cap G$ als $F \cap H$ ligt in $F$ , en hun som ligt in $G + (F \cap H)$ : de insluiting volgt omdat het linkerlid een deelruimte is die beide stukken bevat — concreet ligt een element $g + h$ met $g \in F\cap G$ en $h \in F \cap H$ in $F$ (som van twee elementen van $F$ ) en in $G + (F \cap H)$ .

( $\subseteq$ ) Zij $x \in F$ met $x = g + h$ , $g \in G$ , $h \in F \cap H$ . Dan is $g = x - h \in F$ (verschil van elementen van $F$ ), dus $g \in F \cap G$ , en $x = g + h \in (F \cap G) + (F \cap H)$ .

Tegenvoorbeeld tegen de volledige distributiviteit in $\R^2$ : $F = \operatorname{Vect}(1,1)$ , $G = \operatorname{Vect}(1,0)$ , $H = \operatorname{Vect}(0,1)$ . Dan is $G + H = \R^2$ , dus $F \cap (G+H) = F$ , terwijl $F \cap G = F \cap H = \{0\}$ : het rechterlid is $\{0\} \neq F$ .

Oefening 18.8 ★★★

Bewijs dat de volgende families van $\mathcal{F}(\R, \R)$ vrij zijn:

$(\eu^{a_1 x}, \dots, \eu^{a_p x})$ voor $a_1 < \dots < a_p$ ;
$(\cos x, \sin x, \cos 2x, \sin 2x)$ ;
$(x \mapsto \abs{x - a_1}, \dots, x \mapsto \abs{x - a_p})$ voor verschillende $a_i$ (de afleidbaarheid faalt in precies één punt per functie).

Oplossing

Oplossing van Oefening 18.8.

Stel $\sum_{i} \lambda_i \eu^{a_i x} = 0$ voor alle $x$ . Vermenigvuldig met $\eu^{-a_p x}$ : $\lambda_p + \sum_{i < p} \lambda_i \eu^{(a_i - a_p)x} \to \lambda_p$ als $x \to +\infty$ (elke exponent $a_i - a_p < 0$ ). Het linkerlid is identiek $0$ , dus $\lambda_p = 0$ ; herhaal naar beneden.
Zij $a\cos x + b \sin x + c \cos 2x + d\sin 2x = 0$ voor alle $x$ . Evalueer in $x = 0$ : $a + c = 0$ ; in $x = \pi$ : $-a + c = 0$ ; dus $a = c = 0$ , en de betrekking herleidt zich tot $b\sin x + d \sin 2x = 0$ . Evalueer in $x = \frac\pi2$ : $b = 0$ ; daarna in $x = \frac\pi4$ : $d = 0$ .
Stel $\sum \lambda_i \abs{x - a_i} = 0$ voor alle $x$ . De functie $\sum_{i \neq j} \lambda_i\abs{x - a_i}$ is afleidbaar in $a_j$ (elke term is dat, buiten zijn eigen knik), dus moet $-\lambda_j \abs{x - a_j}$ , hun verschil, eveneens afleidbaar zijn in $a_j$ — wat $\lambda_j = 0$ afdwingt ( $\abs{\,\cdot\,}$ heeft daar een knik). Dit geldt voor elke $j$ .

Oefening 18.9 ★★★

Zij $E$ een $K$ -vectorruimte en $F, G, H$ deelruimten met $F + G = F + H$ , $F \cap G = F \cap H$ en $G \subseteq H$ . Bewijs dat $G = H$ . Geef een tegenvoorbeeld zonder de hypothese $G \subseteq H$ .

Oplossing

Oplossing van Oefening 18.9.

Zij $h \in H$ . Omdat $h \in H \subseteq F + H = F + G$ , schrijf $h = f + g$ met $f \in F$ , $g \in G$ . Dan is $f = h - g \in H$ (beide termen in $H$ , met $G \subseteq H$ ), dus $f \in F \cap H = F \cap G \subseteq G$ , en $h = f + g \in G$ . Bijgevolg $H \subseteq G$ , en met de hypothese $G \subseteq H$ : gelijkheid.

Tegenvoorbeeld zonder $G \subseteq H$ : neem in $\R^2$ $F = \operatorname{Vect}(1,0)$ , $G = \operatorname{Vect}(0,1)$ , $H = \operatorname{Vect}(1,1)$ : dan is $F + G = F + H = \R^2$ en $F \cap G = F \cap H = \{0\}$ , en toch $G \neq H$ .

Oefening 18.10 ★★

Zij in $\R[X]$ $\mathcal P$ de verzameling van de even veeltermen ( $P(-X) = P(X)$ ) en $\mathcal I$ die van de oneven ( $P(-X) = -P(X)$ ). Bewijs dat $\R[X] = \mathcal P \oplus \mathcal I$ , en toon aan dat $\mathcal P = \operatorname{Vect}(1, X^2, X^4, \dots)$ , dat wil zeggen dat de even veeltermen precies de veeltermen in $X^2$ zijn.

Oplossing

Oplossing van Oefening 18.10.

Beide verzamelingen zijn deelruimten (de definiërende voorwaarden zijn lineair en gelden voor $0$ ). Ontbinding: voor $P \in \R[X]$ ,

P(X) = \underbrace{\frac{P(X) + P(-X)}{2}}_{\in\,\mathcal P} + \underbrace{\frac{P(X) - P(-X)}{2}}_{\in\,\mathcal I},

en een veelterm die zowel even als oneven is voldoet aan $P = -P$ , dus $P = 0$ : de som is direct en gelijk aan $\R[X]$ .

Zij nu $P = \sum_k a_k X^k$ even. Dan is $P(X) - P(-X) = 2 \sum_{k \text{ oneven}} a_k X^k$ de nulveelterm, dus verdwijnt elke coëfficiënt van oneven graad (Definitie 8.1): $P \in \operatorname{Vect}(1, X^2, X^4, \dots)$ , dat wil zeggen $P = Q(X^2)$ voor een veelterm $Q$ . Omgekeerd is elke veelterm in $X^2$ even.

Oefening 18.11 ★★

Zij $(x_1, x_2, x_3)$ een vrije familie van een reële vectorruimte $E$ . Bewijs dat $(x_1 + x_2,\ x_2 + x_3,\ x_3 + x_1)$ vrij is. Is de overeenkomstige familie van vier vectoren $(x_1 + x_2,\ x_2 + x_3,\ x_3 + x_4,\ x_4 + x_1)$ vrij wanneer $(x_1, x_2, x_3, x_4)$ dat is?

Oplossing

Oplossing van Oefening 18.11.

Stel $a(x_1 + x_2) + b(x_2 + x_3) + c(x_3 + x_1) = 0$ . Hergroeperen op de vrije familie $(x_1, x_2, x_3)$ geeft

(a + c)\,x_1 + (a + b)\,x_2 + (b + c)\,x_3 = 0 \implies a + c = a + b = b + c = 0 .

Aftrekken van de eerste twee vergelijkingen geeft $c = b$ ; de derde geeft dan $2b = 0$ , dus $b = c = 0$ , en daarna $a = 0$ : de familie is vrij.

Voor vier vectoren is de overeenkomstige familie altijd afhankelijk:

(x_1 + x_2) - (x_2 + x_3) + (x_3 + x_4) - (x_4 + x_1) = 0

is een niet-triviale nulcombinatie (coëfficiënten $1, -1, 1, -1$ ), wat $(x_1, x_2, x_3, x_4)$ ook is. De pariteit van de cycluslengte beslist.

Oefening 18.12 ★★★

Zij $E$ een vectorruimte over $\R$ (of $\C$ ) en $F_1, \dots, F_k$ echte deelruimten van $E$ (elke $F_i \neq E$ ).

Behandel het geval $k = 2$ rechtstreeks: geldt $F_1 \not\subseteq F_2$ en $F_2 \not\subseteq F_1$ , kies dan $x \in F_1 \setminus F_2$ en $y \in F_2 \setminus F_1$ en lokaliseer $x + y$ .
Bewijs in het algemeen dat $E \neq F_1 \cup \dots \cup F_k$ : een vectorruimte over een oneindig lichaam is nooit een eindige vereniging van echte deelruimten. (Neem $k$ minimaal, kies $x \in F_1$ buiten de overige $F_i$ , kies $y \notin F_1$ , en volg de rechte $t \mapsto y + tx$ .)

Oplossing

Oplossing van Oefening 18.12.

Geldt $F_1 \subseteq F_2$ of $F_2 \subseteq F_1$ , dan is de vereniging een van beide, en dus echt. Kies anders $x \in F_1 \setminus F_2$ en $y \in F_2 \setminus F_1$ , en beschouw $x + y$ . Is $x + y \in F_1$ , dan is $y = (x + y) - x \in F_1$ : tegenspraak. Is $x + y \in F_2$ , dan is $x \in F_2$ : tegenspraak. Dus $x + y \notin F_1 \cup F_2$ , en $E \neq F_1 \cup F_2$ .
Stel voor een bewijs uit het ongerijmde dat $E = F_1 \cup \dots \cup F_k$ , met $k$ minimaal gekozen onder alle zulke overdekkingen. De minimaliteit verbiedt $F_1 \subseteq F_2 \cup \dots \cup F_k$ (anders laat men $F_1$ vallen), dus is er een $x \in F_1$ met $x \notin F_i$ voor alle $i \geq 2$ . Omdat $F_1$ echt is, kies $y \notin F_1$ . Voor elke scalair $t$ ligt de vector $y + t x$ in een zekere $F_i$ . Hij ligt nooit in $F_1$ : anders zou $y = (y + tx) - tx \in F_1$ (want $x \in F_1$ ). Het lichaam is oneindig, dus kies $k$ verschillende scalairen $t_1, \dots, t_k$ : de $k$ vectoren $y + t_j x$ vallen in de $k - 1$ deelruimten $F_2, \dots, F_k$ , en twee ervan, zeg $y + t x$ en $y + t' x$ met $t \neq t'$ , liggen in dezelfde $F_i$ ( $i \geq 2$ ). Dan is hun verschil $(t - t')x \in F_i$ , dus $x \in F_i$ : tegenspraak. Er bestaat dus geen eindige overdekking door echte deelruimten.

18.5 Opgave: interpolatie, drie bases voor één ruimte

Probleem 18.1

Leg $n + 1$ verschillende punten $x_0, x_1, \dots, x_n$ van $\R$ vast. Deze opgave herbekijkt de Lagrange-interpolatie (Stelling 8.23) met de ogen van dit hoofdstuk: de ruimte $\R_n[X]$ draagt drie natuurlijke bases — die van Lagrange, die van Newton, en (voor gelijkmatig verdeelde punten) de binomiale basis — en elke basis maakt één vraag gemakkelijk. De weg eindigt bij een echte rekenkundige stelling: de karakterisering van Pólya van de veeltermen die $\Z$ in $\Z$ afbeelden.

Deel I — De Lagrange-basis. Stel voor $0 \leq i \leq n$

L_i \;=\; \prod_{j \neq i} \frac{X - x_j}{x_i - x_j} \;\in\; \R_n[X].

Ga na dat $\deg L_i = n$ en dat $L_i(x_j) = 1$ als $j = i$ , en $0$ als $j \neq i$ .
Bewijs dat de familie $(L_0, \dots, L_n)$ vrij is.
Bewijs dat voor elke $P \in \R_n[X]$

$P \;=\; \sum_{i=0}^{n} P(x_i)\, L_i ,$

en besluit dat $(L_0, \dots, L_n)$ een basis is van $\R_n[X]$ . (Beschouw het verschil van de twee leden en tel zijn wortels, Gevolg 8.8.)
Leid de interpolatiestelling af: voor willekeurige waarden $y_0, \dots, y_n \in \R$ bestaat er precies één $P \in \R_n[X]$ met $P(x_i) = y_i$ voor alle $i$ . Wat zijn de coördinaten van een veelterm $P$ in de Lagrange-basis?
Bewijs de identiteiten

$\sum_{i=0}^{n} L_i = 1 \qquad\text{en, voor } 0 \leq k \leq n,\qquad \sum_{i=0}^{n} x_i^{k}\, L_i = X^{k} .$

Deel II — De Newton-basis en de gedeelde differenties. Stel $N_0 = 1$ en $N_k = (X - x_0)(X - x_1) \cdots (X - x_{k-1})$ voor $1 \leq k \leq n$ . Definieer voor een functie $f$ die in de knooppunten is gedefinieerd de gedeelde differenties door $f[x_i] = f(x_i)$ en

f[x_i, \dots, x_{i+k}] \;=\; \frac{f[x_{i+1}, \dots, x_{i+k}] - f[x_i, \dots, x_{i+k-1}]} {x_{i+k} - x_i} .

Bewijs dat $(N_0, N_1, \dots, N_n)$ een basis is van $\R_n[X]$ .
Bereken $f[x_0, x_1]$ en $f[x_0, x_1, x_2]$ in termen van de waarden van $f$ , en bereken daarna alle gedeelde differenties van $f(x) = x^2$ in drie willekeurige knooppunten.
(Lemma van Aitken) Zij $R$ de interpolant van $f$ in $x_0, \dots, x_{n-1}$ en $Q$ die van $f$ in $x_1, \dots, x_n$ , beide van graad $\leq n - 1$ . Bewijs dat

$S \;=\; \frac{(X - x_0)\,Q - (X - x_n)\,R}{x_n - x_0}$

$f$ interpoleert in $x_0, x_1, \dots, x_n$ .
Leid met inductie op het aantal knooppunten af dat de coëfficiënt van $X^{k}$ in de interpolant van $f$ in $x_0, \dots, x_k$ precies $f[x_0, \dots, x_k]$ is.
Bewijs de interpolatieformule van Newton: de interpolant van $f$ in $x_0, \dots, x_n$ is

$P \;=\; \sum_{k=0}^{n} f[x_0, \dots, x_k]\, N_k ,$

en leid de gesloten formule

$f[x_0, \dots, x_k] \;=\; \sum_{i=0}^{k} \frac{f(x_i)}{\prod_{j \neq i,\, j \leq k} (x_i - x_j)}$

af, waaruit blijkt dat $f[x_0, \dots, x_k]$ niet afhangt van de volgorde van de knooppunten.

Deel III — Gelijkmatig verdeelde knooppunten: de differentieoperator. Vanaf nu zijn de knooppunten $0, 1, 2, \dots$ en stellen we, voor een veelterm $P$ ,

\Delta P(X) = P(X + 1) - P(X), \qquad B_k = \frac{X(X-1)\cdots(X-k+1)}{k!} \quad (B_0 = 1).

Toon aan dat als $\deg P = m \geq 1$ met kopcoëfficiënt $a$ , dan $\deg \Delta P = m - 1$ met kopcoëfficiënt $m\,a$ , en dat $\Delta$ constanten doodt.
Toon aan dat $(B_0, B_1, \dots, B_n)$ een basis is van $\R_n[X]$ en dat $\Delta B_k = B_{k-1}$ voor $k \geq 1$ .
(Voorwaartse-differentieformule van Newton) Bewijs dat elke $P \in \R_n[X]$ voldoet aan

$P \;=\; \sum_{k=0}^{n} \bigl(\Delta^{k} P\bigr)(0)\, B_k .$
Bewijs dat voor elke $k \geq 0$

$\bigl(\Delta^{k} P\bigr)(0) \;=\; \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} P(j) .$
Toon aan dat als $\deg P = n$ met kopcoëfficiënt $a_n$ , dan $\Delta^{n} P$ de constante $n!\,a_n$ is en $\Delta^{n+1} P = 0$ .

Deel IV — Geheelwaardige veeltermen. Een veelterm $P \in \R[X]$ heet geheelwaardig wanneer $P(m) \in \Z$ voor elke $m \in \Z$ .

Bewijs dat elke $B_k$ geheelwaardig is. (Behandel $m \geq k$ , $0 \leq m < k$ en $m < 0$ afzonderlijk; toon voor $m = -q < 0$ aan dat $B_k(-q) = (-1)^k \binom{q + k - 1}{k}$ .)
Bewijs de karakterisering van Pólya: $P \in \R_n[X]$ is geheelwaardig dan en slechts dan als zijn coördinaten in de basis $(B_0, \dots, B_n)$ gehele getallen zijn.
Leid af: neemt $P \in \R_n[X]$ gehele waarden aan in $n + 1$ opeenvolgende gehele getallen $a, a+1, \dots, a+n$ , dan is $P$ geheelwaardig. (Verschuif: pas het onderzoek toe op $Q(X) = P(X + a)$ .)
Leid uit vraag 16 af dat een product van $k$ opeenvolgende gehele getallen altijd deelbaar is door $k!$ .
Zij $P = \dfrac{X(X+1)(2X+1)}{6}$ . Bereken zijn Newton-tabel in $0, 1, 2, 3$ , schrijf $P$ in de basis $(B_k)$ , en besluit dat $P$ geheelwaardig is hoewel geen van zijn monomiale coëfficiënten geheel is. Ga na dat $\Delta P = (X+1)^2$ en leid af dat $P(m) = 1^2 + 2^2 + \dots + m^2$ voor $m \in \N$ .

Deel V — Dividenden.

Zij $P \in \R_n[X]$ de interpolant van de waarden $2^i$ in $i = 0, 1, \dots, n$ . Toon aan dat $P = B_0 + B_1 + \dots + B_n$ en dat $P(n + 1) = 2^{n+1} - 1$ : het “verdubbelingspatroon” breekt altijd in het eerstvolgende punt.
(Discrete primitieve) Bewijs dat voor alle gehele getallen $m \geq 1$ en $k \geq 0$

$\sum_{j=0}^{m-1} B_k(j) \;=\; B_{k+1}(m),$

dat wil zeggen de hockeystick-identiteit $\sum_{j=k}^{m-1} \binom{j}{k} = \binom{m}{k+1}$ .
Ontwikkel $X^2$ en $X^3$ in de basis $(B_k)$ en leid gesloten formules af voor $\sum_{j=0}^{m-1} j^2$ en $\sum_{j=0}^{m-1} j^3$ ; vind de identiteit van Nicomachus $1^3 + \dots + m^3 = (1 + \dots + m)^2$ terug.
Neem $n = 2$ en knooppunten $0, 1, 2$ . Schrijf de coördinaten van $X^2$ in de drie bases van deze opgave: de monomiale basis, de Lagrange-basis en de Newton-basis. Toets de drie antwoorden aan de vragen 4 en 9.
Synthese. In vier zinnen: welk begrip uit de theorie van de vectorruimten vraag 4 automatisch maakt; waarom de Newton-basis coördinaten recursief berekent terwijl de Lagrange-basis ze onmiddellijk aflezen laat; welk vrijheidscriterium beide bases delen; en in welke precieze zin de stelling van Pólya zegt dat de geheeltalligheid van een veelterm een eigenschap is van zijn coördinaten in de juiste basis.

Oplossing

Oplossing van Probleem 18.1.

1. $L_i$ is een product van $n$ lineaire factoren gedeeld door een constante ongelijk aan nul (de $x_i$ zijn verschillend), dus $\deg L_i = n$ . Evaluatie in $x_j$ met $j \neq i$ : de factor $X - x_j$ van de teller wordt nul, dus $L_i(x_j) = 0$ . In $x_i$ vallen teller en noemer samen: $L_i(x_i) = 1$ .

2. Stel $\sum_i \lambda_i L_i = 0$ . Evalueer in $x_j$ : alle termen sterven behalve $\lambda_j L_j(x_j) = \lambda_j$ , dus $\lambda_j = 0$ voor elke $j$ : de familie is vrij.

3. Zij $D = P - \sum_i P(x_i) L_i$ . Dan is $\deg D \leq n$ en, volgens vraag 1, $D(x_j) = P(x_j) - P(x_j) = 0$ in de $n + 1$ verschillende punten $x_0, \dots, x_n$ . Een veelterm ongelijk aan nul van graad $\leq n$ heeft hoogstens $n$ wortels (Gevolg 8.8), dus $D = 0$ . Elke $P \in \R_n[X]$ is dus een combinatie van de $L_i$ : de familie is voortbrengend, en met vraag 2 een basis.

4. Gegeven $y_0, \dots, y_n$ heeft de veelterm $P = \sum_i y_i L_i$ graad $\leq n$ en interpoleert hij. Eenduidigheid: een interpolerende $P$ heeft volgens vraag 3 coördinaten $(P(x_0), \dots, P(x_n)) = (y_0, \dots, y_n)$ in de basis $(L_i)$ , en coördinaten in een basis zijn eenduidig (Propositie 18.15). De coördinaten van $P$ in de Lagrange-basis zijn zijn waarden in de knooppunten — dat is het hele punt van die basis.

5. Pas vraag 3 toe op $P = X^k$ ( $0 \leq k \leq n$ ):

X^k = \sum_{i=0}^{n} x_i^{k} L_i ,

en $k = 0$ geeft $\sum_i L_i = 1$ .

6. $\deg N_k = k$ precies: de familie $(N_0, \dots, N_n)$ is een trap van graden in $\R_n[X]$ , dus een basis volgens Voorbeeld 18.20 (vrijheid uit Propositie 18.19 (1), voortbrenging met eindige afdaling op de graad).

7. Uit de recursie:

f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0}, \qquad f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}.

Voor $f(x) = x^2$ :

f[x_0, x_1] = \frac{x_1^2 - x_0^2}{x_1 - x_0} = x_0 + x_1,

en vervolgens

f[x_0, x_1, x_2] = \frac{(x_1 + x_2) - (x_0 + x_1)}{x_2 - x_0} = \frac{x_2 - x_0}{x_2 - x_0} = 1 .

8. $\deg S \leq n$ omdat $Q$ en $R$ graad $\leq n - 1$ hebben. In $x_0$ : $S(x_0) = \frac{-(x_0 - x_n) R(x_0)}{x_n - x_0} = R(x_0) = f(x_0)$ . In $x_n$ : $S(x_n) = \frac{(x_n - x_0) Q(x_n)}{x_n - x_0} = Q(x_n) = f(x_n)$ . In een inwendig knooppunt $x_i$ ( $1 \leq i \leq n-1$ ) nemen zowel $Q$ als $R$ de waarde $f(x_i)$ aan, dus

S(x_i) = \frac{(x_i - x_0) - (x_i - x_n)}{x_n - x_0}\, f(x_i) = f(x_i) .

9. Inductie op het aantal knooppunten. Eén knooppunt: de interpolant is de constante $f(x_0) = f[x_0]$ . Neem de bewering aan voor $k$ knooppunten en zij $S$ de interpolant in $x_0, \dots, x_k$ ; wegens de eenduidigheid (vraag 4) wordt $S$ gegeven door het lemma van Aitken uit $R$ (knooppunten $x_0, \dots, x_{k-1}$ ) en $Q$ (knooppunten $x_1, \dots, x_k$ ). De coëfficiënt van $X^{k}$ in $S$ is

\frac{[X^{k-1}]\,Q - [X^{k-1}]\,R}{x_k - x_0} = \frac{f[x_1, \dots, x_k] - f[x_0, \dots, x_{k-1}]}{x_k - x_0} = f[x_0, \dots, x_k]

volgens de inductiehypothese en de definiërende recursie.

10. Zij $P_k$ de interpolant van $f$ in $x_0, \dots, x_k$ . Het verschil $P_k - P_{k-1}$ heeft graad $\leq k$ en wordt nul in $x_0, \dots, x_{k-1}$ , dus is het volgens de $k$ keer toegepaste factorstelling (Stelling 8.7) gelijk aan $c\,N_k$ voor een constante $c$ ; vergelijking van de coëfficiënten van $X^{k}$ en vraag 9 geven $c = f[x_0, \dots, x_k]$ . Telescoperen vanaf $P_0 = f(x_0) N_0$ levert de formule van Newton. Voor de gesloten vorm schrijf $P_k = \sum_{i \leq k} f(x_i) L_i$ (Lagrange, op de knooppunten $x_0, \dots, x_k$ ) en lees de coëfficiënt van $X^{k}$ af: elke $L_i$ draagt $\frac{1}{\prod_{j \neq i}(x_i - x_j)}$ bij, waaruit

f[x_0, \dots, x_k] = \sum_{i=0}^{k} \frac{f(x_i)}{\prod_{j \neq i,\, j \leq k}(x_i - x_j)} .

Het rechterlid is invariant onder elke permutatie van de knooppunten, dus hangt de gedeelde differentie niet van hun volgorde af.

11. Is $P = a X^m + (\text{lagere graden})$ , dan geeft het binomium

\Delta P = a\bigl((X+1)^m - X^m\bigr) + \dots = a\,m\,X^{m-1} + (\text{lagere graden}),

omdat $(X+1)^m - X^m = m X^{m-1} + \dots$ en het deel van $P$ van lagere graad na $\Delta$ hoogstens graad $m - 2$ bijdraagt. Dus $\deg \Delta P = m - 1$ met kopcoëfficiënt $m a$ . Een constante $c$ geeft $\Delta c = c - c = 0$ .

12. $\deg B_k = k$ : een trap, dus een basis van $\R_n[X]$ (Voorbeeld 18.20). Voor $\Delta B_k$ ( $k \geq 1$ ) zonder je het gemeenschappelijke product af:

\begin{align*} k!\,\Delta B_k &= (X+1)X\cdots(X-k+2) - X(X-1)\cdots(X-k+1) \\ &= X(X-1)\cdots(X-k+2)\,\bigl[(X+1) - (X-k+1)\bigr] \\ &= k\,X(X-1)\cdots(X-k+2), \end{align*}

dus $\Delta B_k = \frac{X(X-1)\cdots(X-k+2)}{(k-1)!} = B_{k-1}$ .

13. Schrijf $P = \sum_{k=0}^{n} c_k B_k$ (basis, vraag 12). Pas $\Delta^{j}$ toe: volgens vraag 12 is $\Delta^{j} P = \sum_{k \geq j} c_k B_{k-j}$ . Evalueer in $0$ : $B_0(0) = 1$ en $B_m(0) = 0$ voor $m \geq 1$ (de factor $X$ wordt nul), dus $\bigl(\Delta^{j}P\bigr)(0) = c_j$ . Dat is de voorwaartse-differentieformule.

14. Inductie op $k$ . Voor $k = 0$ luidt de identiteit $P(0) = P(0)$ . Neem haar aan voor $k$ en pas haar toe op $\Delta P$ :

\bigl(\Delta^{k+1} P\bigr)(0) = \sum_{j=0}^{k} (-1)^{k-j}\binom kj \bigl(P(j+1) - P(j)\bigr).

Verzamel de coëfficiënt van $P(i)$ : die is $(-1)^{k-i+1}\binom k{i-1}\cdot(-1)^{0}$ uit de eerste som (verschoven) en $-(-1)^{k-i}\binom ki$ uit de tweede — samen

(-1)^{k+1-i}\Bigl(\binom k{i-1} + \binom ki\Bigr) = (-1)^{k+1-i}\binom{k+1}i

volgens de regel van Pascal, en dat is de identiteit op rang $k + 1$ .

15. Herhaal vraag 11 vanaf graad $n$ met kopcoëfficiënt $a_n$ : na één $\Delta$ graad $n-1$ met kopcoëfficiënt $n a_n$ ; na twee $n(n-1)a_n$ ; na $n$ stappen graad $0$ met waarde $n(n-1)\cdots 1\, a_n = n!\,a_n$ , een constante. Nog één $\Delta$ doodt haar: $\Delta^{n+1}P = 0$ .

16. Is $m \geq k$ , dan is $B_k(m) = \binom mk \in \N$ . Is $0 \leq m < k$ , dan is één factor van $m(m-1)\cdots(m-k+1)$ nul, dus $B_k(m) = 0$ . Is $m = -q$ met $q \geq 1$ , dan is

B_k(-q) = \frac{(-q)(-q-1)\cdots(-q-k+1)}{k!} = (-1)^k\,\frac{q(q+1)\cdots(q+k-1)}{k!} = (-1)^k \binom{q+k-1}{k},

een geheel getal. Elke $B_k$ beeldt dus $\Z$ in $\Z$ af.

17. ( $\Leftarrow$ ) Is $P = \sum_k c_k B_k$ met $c_k \in \Z$ , dan is voor $m \in \Z$ de waarde $P(m) = \sum_k c_k B_k(m) \in \Z$ volgens vraag 16. ( $\Rightarrow$ ) Is $P$ geheelwaardig, dan zijn zijn coördinaten $c_k = \bigl(\Delta^k P\bigr)(0) = \sum_{j=0}^k (-1)^{k-j}\binom kj P(j)$ (de vragen 13 en 14), een gehele combinatie van de gehele getallen $P(0), \dots, P(k)$ . Dat is de karakterisering van Pólya van de geheelwaardige veeltermen.

18. Stel $Q(X) = P(X + a)$ , een veelterm van graad $\leq n$ met $Q(0), Q(1), \dots, Q(n) \in \Z$ . Zijn coördinaten in $(B_k)_{k \leq n}$ zijn $c_k = \sum_{j \leq k}(-1)^{k-j}\binom kj Q(j) \in \Z$ (vraag 14 gebruikt alleen de waarden in $0, \dots, k \leq n$ ). Volgens vraag 17 ( $\Leftarrow$ ) is $Q$ geheelwaardig op heel $\Z$ , en dus ook $P(X) = Q(X - a)$ .

19. Een product van $k$ opeenvolgende gehele getallen is $m(m-1)\cdots(m-k+1) = k!\,B_k(m)$ voor zekere $m \in \Z$ , en $B_k(m) \in \Z$ volgens vraag 16: het product is deelbaar door $k!$ .

20. Waarden van $P = \frac{X(X+1)(2X+1)}{6}$ in $0,1,2,3$ : $0, 1, 5, 14$ . Differentietabel: de $\Delta$ -rij is $1, 4, 9$ ; de $\Delta^2$ -rij $3, 5$ ; de $\Delta^3$ -rij $2$ . Bijgevolg is volgens vraag 13

P = 0\cdot B_0 + 1\cdot B_1 + 3\,B_2 + 2\,B_3 ,

met gehele coördinaten: $P$ is geheelwaardig (vraag 17), terwijl zijn monomiale coëfficiënten $\frac13, \frac12, \frac16$ dat niet zijn. Rechtstreekse berekening:

\begin{align*} \Delta P &= \frac{(X+1)(X+2)(2X+3) - X(X+1)(2X+1)}{6} \\ &= \frac{(X+1)\bigl[(X+2)(2X+3) - X(2X+1)\bigr]}{6} = \frac{(X+1)(6X+6)}{6} = (X+1)^2 . \end{align*}

Telescoperen geeft $P(m) = \sum_{j=0}^{m-1}\Delta P(j) = \sum_{j=1}^{m} j^2$ (met $P(0) = 0$ ): de formule voor de som van de kwadraten.

21. De waarden $2^i$ in $i = 0, \dots, n$ hebben een differentietabel die op de linkerrand constant $1$ is: $\Delta^k$ van de rij $(2^i)$ is opnieuw $(2^i)$ (want $2^{i+1} - 2^i = 2^i$ ), dus $\bigl(\Delta^k P\bigr)(0) = 2^0 = 1$ voor alle $k \leq n$ , en $P = B_0 + B_1 + \dots + B_n$ volgens vraag 13. Dan is

P(n+1) = \sum_{k=0}^{n}\binom{n+1}{k} = 2^{n+1} - \binom{n+1}{n+1} = 2^{n+1} - 1 \neq 2^{n+1}:

het patroon breekt in het eerste onbeheerste punt.

22. Volgens vraag 12 is $B_k = \Delta B_{k+1}$ , dus

\sum_{j=0}^{m-1} B_k(j) = \sum_{j=0}^{m-1}\bigl(B_{k+1}(j+1) - B_{k+1}(j)\bigr) = B_{k+1}(m) - B_{k+1}(0) = B_{k+1}(m).

Voor $j < k$ zijn de termen $B_k(j)$ nul, dus begint de som in werkelijkheid bij $j = k$ : $\sum_{j=k}^{m-1}\binom jk = \binom m{k+1}$ , de hockeystick-identiteit.

23. Differentietabellen (of rechtstreeks ontwikkelen) geven

X^2 = B_1 + 2 B_2, \qquad X^3 = B_1 + 6 B_2 + 6 B_3

(controle: $B_1 + 2B_2 = X + X(X-1) = X^2$ ; in $X = 1, 2, 3$ geeft de tweede $1, 8, 27$ ). Vraag 22 levert dan

\sum_{j=0}^{m-1} j^2 = B_2(m) + 2B_3(m) = \binom m2 + 2\binom m3 = \frac{m(m-1)(2m-1)}{6},

\sum_{j=0}^{m-1} j^3 = B_2(m) + 6B_3(m) + 6B_4(m) = \binom m2 + 6\binom m3 + 6\binom m4 .

Uitwerken van de laatste uitdrukking: $\binom m2 + 6\binom m3 + 6\binom m4 = \frac{m(m-1)}{2}\bigl[1 + 2(m-2) + \frac{(m-2)(m-3)}{2}\bigr] = \frac{m^2(m-1)^2}{4} = \binom m2^2$ . Vervang $m$ door $m + 1$ : $1^3 + \dots + m^3 = \bigl(\frac{m(m+1)}2\bigr)^2 = (1 + \dots + m)^2$ , de identiteit van Nicomachus.

24. Knooppunten $0, 1, 2$ , veelterm $X^2$ . Monomiale basis $(1, X, X^2)$ : coördinaten $(0, 0, 1)$ . Lagrange-basis: de coördinaten zijn de waarden $(0, 1, 4)$ (vraag 4). Newton-basis $(1, X, X(X-1))$ : gedeelde differenties $f[0] = 0$ , $f[0,1] = 1$ , $f[0,1,2] = \frac{3 - 1}{2} = 1$ (vraag 9), dus coördinaten $(0, 1, 1)$ — inderdaad $X + X(X-1) = X^2$ . Drie bases, drie coördinaatvectoren, één veelterm.

25. (i) Vraag 4 is automatisch omdat $(L_i)$ een basis is: het bestaan en de eenduidigheid van de interpolatie zijn precies het bestaan en de eenduidigheid van coördinaten. (ii) De Newton-basis is een trap, zodat coördinaten door opeenvolgende delingen worden berekend — elk nieuw knooppunt voegt één term toe zonder de vorige te verstoren — terwijl de Lagrange-coördinaten van $P$ de waarden $P(x_i)$ zijn, zonder enige berekening beschikbaar. (iii) Beide bases zijn vrij volgens dezelfde twee criteria van Propositie 18.19: verschillende graden voor Newton, evaluatie in de knooppunten voor Lagrange. (iv) De stelling van Pólya zegt dat “ $P(\Z) \subseteq \Z$ ”, een eigenschap van waarden, equivalent is met de geheeltalligheid van de coördinaten in de basis $(B_k)$ — de rekenkunde van een veelterm wordt pas zichtbaar in de basis die aan de vraag is aangepast.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst