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 ze vastleggen — opspansel, vrije familie, basis, directe som — is het dagelijks brood van elk hoofdstuk daarna. Overal duidt $K$ op $\R$ of $\C$ (scalairen).

18.1 Definitie en voorbeelden

Definitie 18.1 (Vectorruimte)

Een $K$ -vectorruimte is een verzameling $E$ met een optelling die van $(E, +)$ een abelse groep maakt (nul geschreven $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$ , schrap $0x$ in de groep $(E, +)$ . Voor $\lambda\,0_E$ : dezelfde truc op $\lambda(0_E + 0_E)$ . Voor $(-1)x$ : tel $x$ op,

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

dus $(-1)x$ is het additieve invers van $x$ . Ten slotte, als $\lambda x = 0_E$ met $\lambda \neq 0$ : vermenigvuldig 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 ze ook zijn, 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$ hem 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) — die continue functies, rijen $\mathcal{F}(\N, \R)$ , enz. bevatten; $\C$ als $\R$ -vectorruimte. In elk geval worden de axioma’s overgeë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 (zelfde bewijs als Oefening 7.6).

Voorbeeld 18.4

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

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

In de ruimte van reële rijen:

$\{u : u \text{ begrensd}\}$ is een deelruimte: $0$ is begrensd, en als $\abs{u_n} \leq M$ , $\abs{v_n} \leq M'$ , dan $\abs{u_n + \lambda v_n} \leq M + \abs\lambda M'$ .
$\{u : u_n \to 1\}$ is het niet: de nulrij ontbreekt (en de som van twee leden gaat naar $2$ ).
$\{u : u \text{ monotoon}\}$ is het niet: $u_n = n$ en $v_n = -n + (-1)^n$ zijn monotoon, hun som $(-1)^n$ is het niet; 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 het niet: ze bevat $0$ maar $2u$ ontsnapt zodra $u$ een niet-nul lid is ( $2u_{n+1} \neq (2u_n)^2$ in het algemeen) — kwadrateren is de niet-lineariteit.

De werkvolgorde is altijd dezelfde: test eerst $0$ (goedkoopst), dan stabiliteit — en om te weerleggen verslaat één expliciet tegenvoorbeeldpaar 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)$ van vectoren van $E$ is een willekeurige $\lambda_1 x_1 + \dots + \lambda_p x_p$ ( $\lambda_i \in K$ ). De verzameling van al deze is het opspansel $\operatorname{Vect}(x_1, \dots, x_p)$ : het is een deelruimte, 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 zo ook een scalair veelvoud $\mu\sum\lambda_i x_i = \sum(\mu\lambda_i) x_i$ ; 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. Door stabiliteit onder scalaire vermenigvuldiging ligt elke $\lambda_i x_i \in H$ , en door stabiliteit onder optelling ligt hun som in $H$ : elke lineaire combinatie hoort bij $H$ , d.w.z. $\operatorname{Vect}(x_1, \dots, x_p) \subseteq H$ . Dus het opspansel is bevat in elke deelruimte die de familie bevat: het is de kleinste. ∎

Definitie 18.7 (Som, directe som)

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

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

is een deelruimte (de kleinste die $F \cup G$ bevat). De som is direct, geschreven $F \oplus G$ , wanneer elk element van $F + G$ zich uniek ontbindt als $u + v$ ; equivalent (zie hieronder) wanneer $F \cap G = \{0\}$ . Wanneer $E = F \oplus G$ , zijn de deelruimten complementair in $E$ .

Voorbeeld 18.8 (Een som van twee rechten)

In $\R^3$ , zij $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 als en slechts als $F \cap G = \{0\}$ .

Bewijs. Als een $w \neq 0$ in $F \cap G$ ligt: $w = w + 0 = 0 + w$ zijn twee ontbindingen van $w$ . Omgekeerd, als $u + v = u' + v'$ met $u, u' \in F$ , $v, v' \in G$ , dan hoort $u - u' = v' - v$ bij $F \cap G = \{0\}$ : ontbindingen zijn uniek. ∎

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

Twee dingen om na te gaan, elk met zijn standaard openingszet.

Triviale doorsnede. Neem $x \in F \cap G$ , schrijf beide lidmaatschapsvoorwaarden uit, en pers $x = 0$ eruit. (Redeneer nooit via een tekening: vgl. de valkuilen hieronder.)
Som is alles. Neem een willekeurige $x \in E$ en produceer de ontbinding $x = f + g$ — ofwel door $f$ te raden uit het doel ( $f$ moet voldoen aan de definiërende eigenschap van $F$ , die meestal zijn formule dicteert) ofwel door het lineair stelsel op te lossen dat $x$ uitdrukt tegenover voortbrengers van $F$ en $G$ .

Wanneer de ontbindingsformule geraden is, is uniciteit automatisch uit stap 1; wanneer alleen het bestaan onduidelijk is, is stap 2 waar het werk zit. De twee voorbeelden hieronder laten de methode lopen: voor even/oneven functies wordt de formule voor $f$ afgedwongen door de gewenste identiteit te evalueren in $x$ en $-x$ ; voor veeltermen die in een punt verdwijnen, door te evalueren in $a$ .

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]$ )

Kies $a \in K$ en stel $F = \{P \in K_n[X] : P(a) = 0\}$ , $G = \operatorname{Vect}(1)$ (de constanten). Dan $K_n[X] = F \oplus G$ . Inderdaad bestaat $F \cap G$ uit de constanten die in $a$ verdwijnen, d.w.z. $\{0\}$ ; en elke $P$ ontbindt zich 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 te projecteren op “functies die in $a$ verdwijnen”. Merk op dat $F$ een grote deelruimte is en $G$ een kleine; een complementair paar hoeft in geen enkele zin gebalanceerd te zijn.

Voorbeeld 18.13 (Een complementaire deelruimte is nooit uniek)

In $\R^2$ , zij $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)$ zijn complementair aan $F$ : elk snijdt $F$ enkel in $0$ , en elk paar telt op 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 van “de” complementaire is zinloos totdat een extra structuur (een inwendig product, Hoofdstuk 23) er één uitkiest.

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

18.3 Vrije families, voortbrengende families, bases

Definitie 18.14

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

voortbrengend (van $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 ;$

anders gebonden;
een basis wanneer ze vrij en voortbrengend is.

Propositie 18.15 (Coördinaten)

$(e_1, \dots, e_n)$ is een basis van $E$ als en slechts als elke $x \in E$ uniek een combinatie $x = \lambda_1 e_1 + \dots + \lambda_n e_n$ is; de scalairen $\lambda_i$ zijn de coördinaten van $x$ in de basis.

Bewijs. Voortbrengend $=$ bestaan van de ontbinding. Uniciteit $=$ vrijheid: twee ontbindingen van dezelfde $x$ verschillen door een combinatie gelijk aan $0$ ; vrijheid dwingt al haar coëfficiënten — de verschillen van coördinaten — af 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)$ ( $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 alle coëfficiënten verdwijnen, 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 $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$ . Het veranderen van één basisvector herschikt elke coördinaat; Hoofdstuk 21 zal deze herschikking verpakken in de basisveranderingsmatrix.

Voorbeeld 18.18 (Een kandidaat-basis testen, 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 per coëfficiënt,

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

door de eerste twee af te trekken, $b = c$ , dan geeft de derde $2b = 0$ : $a = b = c = 0$ , vrij. Voortbrengend: in plaats van drie stelsels op te lossen, merk 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)$ ; dan

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 bonus 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 meestal een verkortende combinatie; 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 (Nuttige vrijheidscriteria)

Een familie van niet-nul veeltermen met paarsgewijs verschillende graden is vrij.
Een vector toevoegen aan een vrije familie houdt haar vrij als en slechts als de 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) Bekijk in een nulcombinatie de hoogste aanwezige graad: zijn coëfficiënt moet verdwijnen (niets heft die graad op), en cascadeer naar beneden.

(2) Als $x \in \operatorname{Vect}(x_1, \dots, x_p)$ , dan is de relatie $x - \sum\lambda_i x_i = 0$ niet-triviaal. Omgekeerd moet een niet-triviale nulcombinatie van $(x_1, \dots, x_p, x)$ $x$ bevatten met een niet-nul coëfficiënt (anders spreekt ze de vrijheid van de kleine familie tegen), en $x$ oplossen legt het 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; vrijheid van de grote familie doodt ze allemaal. Superfamilie: 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]$ . Vrijheid is Propositie 18.19 (1). Voor de voortbrengende eigenschap, redeneer via eindige afdaling op de graad: zij $Q \in K_n[X]$ , $Q \neq 0$ , van graad $d$ , met leidende coëfficiënt $a$ , en zij $b \neq 0$ de leidende coëfficiënt van $P_d$ . Dan heeft $Q - \frac ab P_d$ graad $< d$ (de topterme heffen op); door $Q$ te vervangen door dit verschil en te itereren bereikt men na hoogstens $n + 1$ stappen de nulveelterm, en het afwikkelen van de aftrekkingen drukt $Q$ uit als een combinatie van de $P_k$ . Twee trappen die we al tegenkwamen: de verschoven machten $\bigl((X-a)^k\bigr)_{0 \leq k \leq n}$ (Oefening 18.4), en de Newton-producten $\bigl((X - x_0)(X - x_1)\cdots(X - x_{k-1})\bigr)_{0 \leq k \leq n}$ , aan het werk gezet in het weekendprobleem.

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 men cascadeert naar beneden (Oefening 18.8 werkt dit en varianten uit). Vrijheid van functies wordt bewezen door te evalueren: in welgekozen punten, in het oneindige, of na afleiden.

Voorbeeld 18.22 (Een verborgen relatie krimpt een opspansel)

In $\mathcal{F}(\R, \R)$ , wat is $\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 gebonden, 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$ . Dus het opspansel is een vlak binnen de functieruimte — en het bevat ook $\cos 2x = 2\cos^2 x - 1$ : lineair ogende families van trigonometrische functies storten routineus in onder identiteiten, en daarom moet vrijheid bewezen worden, nooit verondersteld uit de lengte van de lijst.

Opmerking 18.23 (Veelvoorkomende valkuilen)

Vier klassieke valstrikken. Paarsgewijs is niet genoeg: in $\R^2$ zijn de vectoren $(1,0)$ , $(0,1)$ , $(1,1)$ paarsgewijs niet-proportioneel, en toch gebonden — vrijheid is een eigenschap van de hele familie, getest door één globale combinatie, nooit twee aan twee. De nulvector vergiftigt alles: elke familie die $0$ bevat is gebonden ( $1\cdot 0 = 0$ is een niet-triviale relatie), hoe onschuldig de andere vectoren ook zijn. Vereniging is geen som: $F \cup G$ is bijna nooit een deelruimte (Definitie 18.3); de kleinste deelruimte die beide bevat is $F + G$ , meestal 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 bewezen worden, niet afgelezen van een tekening — vgl. Voorbeeld 18.13, waar veel verschillende $G$ werken. Vrijheid hangt af van de scalairen: het paar $(1, \iu)$ is vrij in $\C$ gezien als $\R$ -vectorruimte, maar gebonden in $\C$ gezien als $\C$ -vectorruimte ( $\iu\cdot 1 + (-1)\cdot\iu = 0$ ). Weet altijd welk lichaam werkzaam is voordat je een familie vrij verklaart — het weekendprobleem van Hoofdstuk 19 zet precies deze gevoeligheid om in irrationaliteitsbewijzen.

Opmerking 18.24 (Waar deze taal naartoe gaat)

Alles na dit hoofdstuk spreekt de taal die hier wordt vastgelegd. Hoofdstuk 19 telt basisvectoren en zet “vrij” en “voortbrengend” om in ongelijkheden over één enkel geheel getal, de dimensie. Hoofdstuk 20 bestudeert de afbeeldingen die compatibel zijn met de twee bewerkingen; directe sommen worden daar projectoren. Hoofdstuk 21 codeert vectoren door hun coördinaten in een basis — Propositie 18.15 is het licentie voor die codering — en Hoofdstuk 23 voegt lengtes en hoeken toe bovenop de lineaire structuur. In het Jaar 2-volume lopen dezelfde axioma’s, woordelijk, over willekeurige lichamen en in oneindige dimensie; niets in dit hoofdstuk gebruikte ergens eindigheid.

Opmerking 18.25 (Drie draden om doorheen Boek 3 te volgen)

Volg drie specifieke ideeën van dit hoofdstuk in hun groei. Het trapprincipe (Voorbeeld 18.20) verschijnt opnieuw als de Newton-basis in het weekendprobleem van dit hoofdstuk, als de binomiale basis $(B_k)$ daar, en als de veelterm-alternanttruc in het weekendprobleem van Hoofdstuk 22: één lemma, drie determinantvrije dividenden. Evaluatie als vrijheidstest (Voorbeeld 18.21) wordt het interpolatie- isomorfisme van Hoofdstuk 20, dan het Vandermonde-criterium van Hoofdstuk 22, dan de Gram-test 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 verklaarde-plus-residuele ontbinding van kleinste kwadraten in het weekendprobleem van Hoofdstuk 25. Heel weinig van dit boek is, ten diepste, niet één van deze drie ideeën in nieuwe kleren.

18.4 Oefeningen

Oefening 18.1 ★

Welke van de volgende 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$ verdwijnt in $1$ ; $(P + \lambda Q)(1) = P(1) + \lambda Q(1) = 0$ .
Ja: de nulfunctie is begrensd; als $\abs f \leq M$ en $\abs g \leq M'$ , dan $\abs{f + \lambda g} \leq M + \abs\lambda M'$ .

Oefening 18.2 ★

Ligt in $\R^3$ de vector $(1, 2, 1)$ in $\operatorname{Vect}\bigl((1,0,1),\, (1,1,0)\bigr)$ ? En $(2, 1, 1)$ ? Beschrijf $\operatorname{Vect}\bigl((1,0,1),(1,1,0)\bigr)$ door 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$ : consistent, dus $(2,1,1) = (1,0,1) + (1,1,0)$ , 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 ★

Bepaal 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$ : optellend, $2(\lambda + \mu + \nu) = 0$ , en elke vergelijking aftrekkend, $\lambda = \mu = \nu = 0$ : vrij.

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

Derde: vier vectoren in $\R^3$ — noodzakelijk gebonden 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 relatie.

Oefening 18.4 ★

Bewijs dat $(1, X - 1, (X-1)^2, (X-1)^3)$ een basis van $\R_3[X]$ is, en geef de coördinaten van $X^3$ erin. (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$ , bijv. via Taylor voor veeltermen, vgl. 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)$ (Pascals rij, zoals verwacht uit $X^3 = ((X-1)+1)^3$ ).

Oefening 18.5 ★★

In $\R^4$ , zij $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)$ dienovereenkomstig.

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: gegeven $(x,y,z,t)$ , zoek $(a,a,a,b) \in F$ en $(0,c,d,0) \in G$ die er samen op optellen: $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 ★★

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

Oplossing

Oplossing van Oefening 18.6.

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

$F + G$ is niet alles: het bestaat uit rijen van de vorm $c_n + \lambda(-1)^n$ met $(c_n)$ convergent. De rij $v_n = n$ is niet van deze vorm ( $v_n - \lambda(-1)^n$ is onbegrensd, nooit convergent). Dus $F \oplus G \subsetneq$ (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$ 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$ liggen in $F$ , en hun som ligt in $G + (F \cap H)$ : de inclusie volgt aangezien het linkerlid een deelruimte is die beide stukken bevat — concreet is een element $g + h$ met $g \in F\cap G$ , $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 $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 voor volledige distributiviteit in $\R^2$ : $F = \operatorname{Vect}(1,1)$ , $G = \operatorname{Vect}(1,0)$ , $H = \operatorname{Vect}(0,1)$ . Dan $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$ (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$ ; itereer 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 relatie reduceert tot $b\sin x + d \sin 2x = 0$ . Evalueer in $x = \frac\pi2$ : $b = 0$ ; dan 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, weg van zijn eigen knik), dus $-\lambda_j \abs{x - a_j}$ , hun verschil, moet ook afleidbaar zijn in $a_j$ — wat $\lambda_j = 0$ afdwingt ( $\abs{\,\cdot\,}$ heeft 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 $G = H$ . Geef een tegenvoorbeeld zonder de hypothese $G \subseteq H$ .

Oplossing

Oplossing van Oefening 18.9.

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

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

Oefening 18.10 ★★

In $\R[X]$ , zij $\mathcal P$ de verzameling van even veeltermen ( $P(-X) = P(X)$ ) en $\mathcal I$ de verzameling van oneven ( $P(-X) = -P(X)$ ). Bewijs dat $\R[X] = \mathcal P \oplus \mathcal I$ , en toon dat $\mathcal P = \operatorname{Vect}(1, X^2, X^4, \dots)$ , d.w.z. 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 elke coëfficiënt van oneven graad verdwijnt (Definitie 8.1): $P \in \operatorname{Vect}(1, X^2, X^4, \dots)$ , d.w.z. $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 analoge 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)$ het is?

Oplossing

Oplossing van Oefening 18.11.

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

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

De eerste twee vergelijkingen aftrekken geeft $c = b$ ; de derde geeft dan $2b = 0$ , dus $b = c = 0$ , dan $a = 0$ : de familie is vrij.

Voor vier vectoren is de analoge familie altijd gebonden:

(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$ eigenlijke deelruimten van $E$ (elke $F_i \neq E$ ).

Behandel het geval $k = 2$ rechtstreeks: als $F_1 \not\subseteq F_2$ en $F_2 \not\subseteq F_1$ , kies $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 eigenlijke deelruimten. (Neem $k$ minimaal, kies $x \in F_1$ buiten de andere $F_i$ , kies $y \notin F_1$ , en volg de rechte $t \mapsto y + tx$ .)

Oplossing

Oplossing van Oefening 18.12.

Als $F_1 \subseteq F_2$ of $F_2 \subseteq F_1$ , dan is de vereniging een van de twee, dus eigenlijk. Anders kies $x \in F_1 \setminus F_2$ en $y \in F_2 \setminus F_1$ , en beschouw $x + y$ . Als $x + y \in F_1$ , dan $y = (x + y) - x \in F_1$ : tegenspraak. Als $x + y \in F_2$ , dan $x \in F_2$ : tegenspraak. Dus $x + y \notin F_1 \cup F_2$ , en $E \neq F_1 \cup F_2$ .
Stel ter contradictie dat $E = F_1 \cup \dots \cup F_k$ , met $k$ minimaal gekozen onder al zulke overdekkingen. Minimaliteit verbiedt $F_1 \subseteq F_2 \cup \dots \cup F_k$ (anders laat $F_1$ weg), dus is er een $x \in F_1$ met $x \notin F_i$ voor alle $i \geq 2$ . Aangezien $F_1$ eigenlijk is, kies $y \notin F_1$ . Voor elke scalair $t$ ligt de vector $y + t x$ in een of andere $F_i$ . Ze ligt nooit in $F_1$ : anders $y = (y + tx) - tx \in F_1$ (daar $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 hun verschil $(t - t')x \in F_i$ , dus $x \in F_i$ : tegenspraak. Dus bestaat er geen eindige overdekking door eigenlijke deelruimten.

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

Probleem 18.1

Fixeer $n + 1$ verschillende punten $x_0, x_1, \dots, x_n$ van $\R$ . Dit probleem herbekijkt 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 verspreide punten) de binomiale basis — en elke basis maakt één vraag gemakkelijk. De weg eindigt bij een echte rekenkundige stelling: Pólya’s karakterisatie van de veeltermen die $\Z$ in $\Z$ afbeelden.

Deel I — De Lagrange-basis. Voor $0 \leq i \leq n$ stel

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 van $\R_n[X]$ is. (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 een unieke $P \in \R_n[X]$ met $P(x_i) = y_i$ voor alle $i$ . Wat zijn, in de Lagrange-basis, de coördinaten van een veelterm $P$ ?
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 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$ . Voor een functie $f$ gedefinieerd in de knopen, definieer 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 van $\R_n[X]$ is.
Bereken $f[x_0, x_1]$ en $f[x_0, x_1, x_2]$ in termen van de waarden van $f$ , en bereken dan alle gedeelde differenties van $f(x) = x^2$ in drie willekeurige knopen.
(Lemma van Aitken) Zij $R$ interpolant van $f$ in $x_0, \dots, x_{n-1}$ en $Q$ interpolant 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, door inductie op het aantal knopen, 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 Newtons interpolatieformule: 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 af

$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)} ,$

die toont dat $f[x_0, \dots, x_k]$ niet afhangt van de ordening van de knopen.

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

\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 dat als $\deg P = m \geq 1$ met leidende coëfficiënt $a$ , dan $\deg \Delta P = m - 1$ met leidende coëfficiënt $m\,a$ , en dat $\Delta$ constanten doodt.
Toon dat $(B_0, B_1, \dots, B_n)$ een basis van $\R_n[X]$ is en dat $\Delta B_k = B_{k-1}$ voor $k \geq 1$ .
(Newtons voorwaartse-verschilformule) 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 dat als $\deg P = n$ met leidende coë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]$ is 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$ apart; voor $m = -q < 0$ , toon $B_k(-q) = (-1)^k \binom{q + k - 1}{k}$ .)
Bewijs Pólya’s karakterisatie: $P \in \R_n[X]$ is geheelwaardig als en slechts als zijn coördinaten in de basis $(B_0, \dots, B_n)$ gehele getallen zijn.
Leid af: als $P \in \R_n[X]$ gehele waarden aanneemt in $n + 1$ opeenvolgende gehele getallen $a, a+1, \dots, a+n$ , dan is $P$ geheelwaardig. (Verschuiving: pas de studie 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 een geheel getal is. Verifieer $\Delta P = (X+1)^2$ en leid af $P(m) = 1^2 + 2^2 + \dots + m^2$ voor $m \in \N$ .

Deel V — Dividenden.

Zij $P \in \R_n[X]$ interpolant van de waarden $2^i$ in $i = 0, 1, \dots, n$ . Toon dat $P = B_0 + B_1 + \dots + B_n$ en dat $P(n + 1) = 2^{n+1} - 1$ : het “verdubbelingspatroon” breekt altijd bij het allervolgende 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),$

d.w.z. 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$ ; herwin Nicomachus’ identiteit $1^3 + \dots + m^3 = (1 + \dots + m)^2$ .
Neem $n = 2$ en knopen $0, 1, 2$ . Schrijf de coördinaten van $X^2$ in de drie bases van dit probleem: de monomiale basis, de Lagrange-basis, de Newton-basis. Controleer de drie antwoorden tegen vragen 4 en 9.
Synthese. In vier zinnen: welk vectorruimtebegrip vraag 4 automatisch maakt; waarom de Newton-basis coördinaten recursief berekent terwijl de Lagrange-basis ze onmiddellijk afleest; welk vrijheidscriterium beide bases delen; en in welke precieze zin Pólya’s stelling 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 niet-nul constante (de $x_i$ zijn verschillend), dus $\deg L_i = n$ . Evaluerend in $x_j$ met $j \neq i$ : de factor $X - x_j$ van de teller verdwijnt, 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 $\deg D \leq n$ en, door vraag 1, $D(x_j) = P(x_j) - P(x_j) = 0$ voor de $n + 1$ verschillende punten $x_0, \dots, x_n$ . Een niet-nul veelterm van graad $\leq n$ heeft hoogstens $n$ wortels (Gevolg 8.8), dus $D = 0$ . Dus is elke $P \in \R_n[X]$ 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. Uniciteit: een interpolerende $P$ heeft, door 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 uniek (Propositie 18.15). De coördinaten van $P$ in de Lagrange-basis zijn zijn waarden in de knopen — dat is de hele bedoeling van de 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 door Voorbeeld 18.20 (vrijheid uit Propositie 18.19 (1), voortbrenging via eindige afdaling op de graad).

7. Uit de recurrentie,

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 dan

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$ aangezien $Q, 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 inwendige knoop $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 knopen. Eén knoop: de interpolant is de constante $f(x_0) = f[x_0]$ . Neem de bewering aan voor $k$ knopen en zij $S$ interpolant in $x_0, \dots, x_k$ ; door uniciteit (vraag 4) is $S$ gegeven door het lemma van Aitken uit $R$ (knopen $x_0, \dots, x_{k-1}$ ) en $Q$ (knopen $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]

door de inductiehypothese en de definiërende recurrentie.

10. Zij $P_k$ interpolant van $f$ in $x_0, \dots, x_k$ . Het verschil $P_k - P_{k-1}$ heeft graad $\leq k$ en verdwijnt in $x_0, \dots, x_{k-1}$ , dus door de factorstelling $k$ keer toegepast (Stelling 8.7) is het gelijk aan $c\,N_k$ voor een constante $c$ ; door de coëfficiënten van $X^{k}$ te vergelijken en vraag 9 te gebruiken, $c = f[x_0, \dots, x_k]$ . Telescoperend vanaf $P_0 = f(x_0) N_0$ geeft Newtons formule. Voor de gesloten vorm, schrijf $P_k = \sum_{i \leq k} f(x_i) L_i$ (Lagrange, op de knopen $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 knopen, dus de gedeelde differentie hangt niet af van hun ordening.

11. Als $P = a X^m + (\text{lagere graden})$ , 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 lagere-graad deel van $P$ graad $\leq m - 2$ bijdraagt na $\Delta$ (of termen van graad $\leq m-2$ ). Dus $\deg \Delta P = m - 1$ met leidende coëfficiënt $m a$ . Een constante $c$ geeft $\Delta c = c - c = 0$ .

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

\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: door vraag 12, $\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$ verdwijnt), dus $\bigl(\Delta^{j}P\bigr)(0) = c_j$ . Dit is de voorwaartse-verschilformule.

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

door Pascals regel, wat de identiteit op rang $k + 1$ is.

15. Vraag 11 itererend vanaf graad $n$ , leidende coëfficiënt $a_n$ : na één $\Delta$ , graad $n-1$ en leidende coëfficiënt $n a_n$ ; na twee, $n(n-1)a_n$ ; na $n$ stappen, graad $0$ en waarde $n(n-1)\cdots 1\, a_n = n!\,a_n$ , een constante. Nog één $\Delta$ doodt ze: $\Delta^{n+1}P = 0$ .

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

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. Dus beeldt elke $B_k$ $\Z$ in $\Z$ af.

17. ( $\Leftarrow$ ) Als $P = \sum_k c_k B_k$ met $c_k \in \Z$ , dan voor $m \in \Z$ , $P(m) = \sum_k c_k B_k(m) \in \Z$ door vraag 16. ( $\Rightarrow$ ) Als $P$ geheelwaardig is, zijn zijn coördinaten $c_k = \bigl(\Delta^k P\bigr)(0) = \sum_{j=0}^k (-1)^{k-j}\binom kj P(j)$ (vragen 13 en 14), een gehele combinatie van de gehele getallen $P(0), \dots, P(k)$ . Dit is Pólya’s karakterisatie van 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$ ). Door vraag 17 ( $\Leftarrow$ ) is $Q$ geheelwaardig op heel $\Z$ , 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 een zekere $m \in \Z$ , en $B_k(m) \in \Z$ door 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$ . Verschiltabel: $\Delta$ -rij $1, 4, 9$ ; $\Delta^2$ -rij $3, 5$ ; $\Delta^3$ -rij $2$ . Dus, door 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$ geen gehele getallen zijn. Directe 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*}

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

21. De waarden $2^i$ in $i = 0, \dots, n$ hebben een verschiltabel die constant $1$ is op de linkerrand: $\Delta^k$ van de rij $(2^i)$ is opnieuw $(2^i)$ (aangezien $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$ door vraag 13. Dan

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 bij het eerste ongecontroleerde punt.

22. Door vraag 12, $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$ verdwijnen de termen $B_k(j)$ , dus de som begint werkelijk bij $j = k$ : $\sum_{j=k}^{m-1}\binom jk = \binom m{k+1}$ , de hockeystick-identiteit.

23. Verschiltabellen (of directe ontwikkeling) 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 .

De laatste uitdrukking ontwikkelend: $\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$ . $m$ vervangend door $m + 1$ : $1^3 + \dots + m^3 = \bigl(\frac{m(m+1)}2\bigr)^2 = (1 + \dots + m)^2$ , Nicomachus’ identiteit.

24. Knopen $0, 1, 2$ , veelterm $X^2$ . Monomiale basis $(1, X, X^2)$ : coördinaten $(0, 0, 1)$ . Lagrange-basis: 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: bestaan en uniciteit van interpolatie zijn precies bestaan en uniciteit van coördinaten. (ii) De Newton-basis is een trap, dus coördinaten worden berekend door opeenvolgende delingen — elke nieuwe knoop voegt één term toe zonder de vorige te verstoren — terwijl de Lagrange-coördinaten van $P$ de waarden $P(x_i)$ zijn, beschikbaar zonder enige berekening. (iii) Beide bases zijn vrij door dezelfde twee criteria van Propositie 18.19: verschillende graden voor Newton, evaluatie in de knopen voor Lagrange. (iv) Pólya’s stelling 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.