\def\bari{\bar{i}}% \def\barj{\bar{j}}% \section*{Inleiding} In {\bf Lineaire Algebra 1} heb je al kennis gemaakt met het begrip {\it vectorruimte}. In dit hoofdstuk gaan we dat begrip generaliseren, en wel door toe te staan dat de {\it scalairen} uit andere objecten bestaan dan slechts de re\"ele getallen, waartoe ze tot dusverre beperkt waren. De scalairen moeten aan zekere eisen voldoen om de gegeneraliseerde definitie zinnig te maken; zo moet je scalairen kunnen optellen en met elkaar vermenigvuldigen, en moeten er scalaire elementen $1$ en $0$ zijn. Je krijgt de eigenschappen van vectorruimten terug wanneer je eist dat de scalairen een {\it lichaam} vormen. Onze eerste taak zal zijn om lichamen te defini\"eren en er voorbeelden van te geven. \section{Lichamen} Voor een algemenere definitie van vectorruimte zullen we eigenschappen van de re\"ele getallen bestuderen en proberen in een abstracte definitie te vangen. Vervolgens zullen we kijken naar andere objecten die aan diezelfde eigenschappen voldoen. De eigenschappen waar we op doelen zijn niet uitsluitend die van de getallen zelf, maar ook van de bewerkingen die je er op uit kunt voeren: je kunt re\"ele getallen bij elkaar optellen, en je kunt ze met elkaar vermenigvuldigen. Een lichaam zal een verzameling zijn waar we op soortgelijke manier 2 operaties hebben die aan overeenkomstige eigenschappen voldoen. Die eigenschappen zijn dat het niet uitmaakt in welke volgorde je getallen optelt (of vermenigvuldigt), dat er speciale re\"ele getallen zijn (namelijk 0 en 1) die bij optelling of vermenigvuldiging geen effect hebben, en de manier waarop de vermenigvuldiging zich `verdeelt' over de optelling (we maken dat precies in \ref{def:lich}). Maar eerst defini\"eren we wat een {\it bewerking} is, omdat we meer algemene operaties willen toestaan dan alleen optelling en vermenigvuldiging. Als $V$ een verzameling is, geven we met $V\times V$ de verzameling {\it geordende paren} $(v_1, v_2)$ met $v_1, v_2\in V$, aan. \begin{dfs}\rm Een {\it bewerking ${}\cdot{}$ op een verzameling $V$} is een afbeelding van $V\times V$ naar $V$. Een bewerking is {\it commutatief} als $v_1\cdot v_2=v_2\cdot v_1$ voor elk tweetal $v_1, v_2\in V$, en een bewerking~$\cdot$ heet {\it associatief} als $(v_1\cdot v_2)\cdot v_3=v_1\cdot (v_2\cdot v_3)$, voor elk drietal $v_1, v_2, v_3$. \end{dfs} Met andere woorden: een bewerking voegt aan elk paar elementen van $V$ een derde element toe. Bij een commutatieve bewerking maakt het niet uit in welke volgorde je de bewerking uitvoert en voor een associatieve bewerking maakt het niet uit hoe je de haakjes zet in $v_1\cdot v_2\cdot v_3$. \begin{vbn}\rm Je kent al heel veel voorbeelden van bewerkingen: we keken al naar de optelling en vermenig\-vul\-diging van re\"ele getallen. Let wel op: bij een bewerking hoort een verzameling. Je kunt niet zeggen dat $+$ een bewerking is, maar wel dat $+$ een bewerking is op de re\"ele getallen (of gehele getallen, enz.). \newcounter{vvv} \begin{list}{\rm (\roman{vvv})}{\usecounter{vvv} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item Optellen vormt een bewerking op de natuurlijke getallen $\N$. Evenzo vermenigvuldigen. \item Aftrekken is een bewerking op de gehele getallen $\Z$, maar niet op $\N$. \item Delen is een bewerking op de verzameling $\Q^*$ van rationale getallen die ongelijk aan nul zijn (maar niet op de gehele getallen ongelijk $0$). \item De gebruikelijke optelling en vermenigvuldiging van polynomen vormen bewerkingen op de verzameling $\R[x]$ van polynomen met re\"ele co\"effici\"enten. \item Zowel optellen als vermenigvuldigen is een bewerking op $\Mat_n(\R)$, de $n\times n$ matrices met re\"ele co\"effici\"enten. \item Als $X$ een verzameling is, dan kun je aan twee {\it afbeeldingen} $f$ en $g$ van $X$ naar zichzelf een nieuwe afbeelding $g\circ f$ toevoegen, door $(g\circ f)(x) = g(f(x))$. Deze {\it samenstelling} $g\circ f$ van de afbeeldingen $f$ en $g$ is zelf ook weer een afbeelding $X\rightarrow X$. Dus is $\circ$ een bewerking op de verzameling afbeeldingen $X^X$ van $X$ naar zichzelf. Als speciaal geval kun je bijvoorbeeld kijken naar alle functies van $\R$ naar $\R$. \end{list} \end{vbn} \opgave{Opgave}{Laat zien dat de samenstelling $\circ$ van functies $\R\rightarrow\R$ niet commutatief is maar wel associatief.} \begin{dfn}\label{def:lich}\rm Een {\it lichaam} is een verzameling $V$ met daarop twee bewerkingen $+$ en $\times$, die voldoen aan: \newcounter{lich} \begin{list}{\rm [L\arabic{lich}]}{\usecounter{lich} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item $+$ op $V$ is associatief: $(x+ y)+ z=x+(y+ z)$, voor alle $x,y,z\in V$; \item er is een (nul)element $0\in V$ zodanig dat $0+ x=x+ 0=x$ voor alle $x\in V$; \item bij elke $x\in V$ is er een {\it tegengestelde} $-x\in V$ zodanig dat $x+(-x)=(-x) + x=0$; \item $+$ op $V$ is commutatief: $x+y=y+x$ voor alle $x,y\in V$; \item $\times$ op $V$ is associatief: $(x\times y)\times z=x\times(y\times z)$, voor alle $x,y,z\in V$; \item er is een (eenheids)element $1\in V$ zodanig dat $1\times x=x\times 1=x$ voor alle $x\in V$; \item bij elke $x\in V$ met $x\neq 0$ is er een {\it inverse} $x^{-1}\in V$ zodanig dat $x\times x^{-1}=x^{-1} \times x=1$; \item $\times$ op $V$ is commutatief: $x\times y=y\times x$ voor alle $x,y\in V$; \item de operatie $\times$ is {\it distributief} over $+$, dat wil zeggen: $x\times (y+z)=(x\times y)+(x\times z)$ en $(x+y)\times z = (x\times z)+(y\times z)$, voor alle $x,y,z\in V$. \end{list} \end{dfn} \begin{opn}\rm Een lichaam bestaat dus uit een drietal $(V, +, \times)$, namelijk een verzameling $V$ met twee be\-wer\-kingen daarop. In deze definitie hebben we de bewerkingen met $+$ en $\times$ aangegeven, omdat in voorbeelden die we kennen (zoals de re\"ele getallen) dat natuurlijk is. Maar de bewerkingen hoeven helemaal geen optelling of vermenigvuldiging te zijn --- daarvan zien we zo voorbeelden. Er zijn heel veel belangrijke algebra\"ische strukturen die bestaan uit een verzameling $V$, en \'e\'en of twee operaties die voldoen aan een {\it deelverzameling} van de axioma's L1--9. Zo is een {\it groep} een verzameling met een bewerking die voldoet aan L1--3, en een {\it commutatieve groep} (die meestal {\it abelse group} wordt genoemd) voldoet bovendien aan L4. Een {\it ring met 1} is een verzameling $V$ met operaties $+$ en $\times$ die voldoen aan L1--6 en aan L9; als deze bovendien aan L8 voldoet, is het een {\it commutatieve ring met $1$}. Meer hierover in Hoofdstuk 2. In een lichaam kun je dus elk tweetal elementen optellen en aftrekken, vermenigvuldigen en delen (mits je niet door nul deelt). Een lichaam vormt een abelse groep ten opzichte van de optelling $+$, en de elementen die niet nul zijn vormen een abelse groep ten opzichte van de vermenigvuldiging $\times$. Als $(V, +, \times)$ een lichaam is en een deelverzameling $U\subset V$ vormt met {\it dezelfde bewerkingen} ook een lichaam, dan zeggen we dat $(U, +, \times)$ een {\it deel\-lichaam} van $V$ is. We zeggen wel dat $U$ een deellichaam is van $V$ (en bedoelen dan: met dezelfde bewerkingen). In een lichaam (en algemener, in een ring) $(V, +, \times)$ defini\"eren we de {\it aftrekking} van twee elementen nu door $a-b=a+(-b)$, en de {\it deling} van $a$ door een element $b\neq 0$ door $a/b=a\times b^{-1}$. \end{opn} \opgave{Opgave}{Bewijs dat wanneer $(V, +, \times)$ een lichaam is, en $U$ een deelverzameling van $V$ is die $0$ en $1$ bevat, geldt: $(U, +, \times)$ is een lichaam dan en slechts dan als voor elk tweetal elementen $a, b\in U$ met $b\neq 0$ geldt $a-b\in U$ en $a/b\in U$.} \begin{vbn}\label{vb:lich}\rm We geven de belangrijkste voorbeelden van lichamen. \setcounter{vvv}{1} \begin{list}{\rm (\roman{vvv})}{\usecounter{vvv} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.2ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\listparindent 3.6ex} \setlength{\leftmargin 6.0ex} } \item $(\R, +, \times)$: de re\"ele getallen vormen onder optelling en vermenigvuldiging een lichaam. Om dat te bewijzen moet je nagaan dat de eigenschappen L1--9 gelden. De meeste daarvan zijn flauw. \item $(\Q, +, \times)$: de rationale getallen (breuken) vormen onder optelling en vermenigvuldiging een lichaam. Natuurlijk kun je weer alle eigenschappen waaraan een lichaam moet voldoen gaan verifi\"eren, maar het is eenvoudiger om de eigenschap uit de opgave te gebruiken die zegt dat $(\Q, +, \times)$ een {\it deellichaam} is van $(\R, +, \times)$: het is duidelijk dat de breuken een deelverzameling van de re\"ele getallen vormen die gesloten is onder het nemen van verschillen en quoti\"enten. \item[(iii)] $(\C, +, \times)$: de complexe getallen vormen onder optelling en vermenigvuldiging een lichaam met $(\R, +, \times)$ als deellichaam! We defini\"eren hier de complexe getallen als paren $(a, b)\in\R^2$ van re\"ele getallen die we optellen als vectoren in $\R^2$ en vermenigvuldigen volgens $$(a, b)\times (c, d) = ((a\times c)-(b\times d), (a\times d)+(b\times c)),$$ gebruik makend van de vermenigvuldiging (en optelling) in $\R$. Vaak schrijven we $a+b\ii$ voor $(a, b)$ in $\C$, waarbij dan $\ii^2=-1$. De re\"ele getallen kunnen we dan vereenzelvigen met de deelverzameling van paren $(a, 0)$. \item[(iv)] De verzameling $V=\{0\}$ met de gewone optelling en vermenigvuldiging vormt een lichaam dat uit maar 1 element bestaat; in het bijzonder is $0=1$ in deze ring! Omdat dit speciale geval soms tot complicaties leidt, zullen we het vanaf nu expliciet uitsluiten, en eisen: {\it de ringen en lichamen die wij beschouwen hebben ten minste twee verschillende elementen $0\neq 1$}.\label{vbd:nul} \item[(v)] De gehele getallen vormen geen lichaam onder optelling en vermenigvuldiging omdat je van $z\in\Z$ geen inverse in $\Z$ kunt vinden, tenzij $z\in\{-1, 1\}$. \end{list} \end{vbn} \begin{vbd}[$\Z/m\Z$]\rm\label{vbd:zmz} \noindent We construeren de commutatieve ring (met 1) $\Z/m\Z$, de {\it restklassenring modulo $m$}, als volgt. Laat $m>1$ een vast natuurlijk getal zijn (de {\it modulus}). We delen $\Z$ op in {restklassen modulo $m$}, namelijk de deelverzamelingen $$R_i=\{ z : z\in \Z\ |\ \exists k\in\Z : z = i + k\cdot m\}$$ voor $i\in\Z$. Dan is duidelijk dat $R_i=R_j$ wanneer $i-j$ een veelvoud van $m$ is, en dat $R_i\cap R_j=\emptyset$ wanneer $R_i\neq R_j$. We hebben zo precies $m$ disjuncte restklassen gemaakt, $R_0, R_1, \ldots, R_{m-1}$. Vaak geven we de restklasse $R_i$, waar $i$ zelf in zit, aan met $\bar i$. Als $i$ en $j$ in dezelfde restklasse zitten, schrijven we $i\equiv j\bmod m$, en zeggen dat {\it $i$ congruent $j$ modulo $m$} is. Dus $$i\equiv j\bmod m\quad\iff\quad R_i=R_j\quad\iff\quad\bari=\barj\quad\iff\quad m\ \vert\ i-j.$$ We defini\"eren optelling en vermenigvuldiging van $\bari$ en $\barj$ door $\bari+\barj=\overline{i+j}$ en $\bari\times \barj=\overline{i\times j}$. Nu is $\Z/m\Z$ de verzameling van de $m$ restklassen modulo $m$ met deze optelling en vermenigvuldiging. Niet alle elementen (ongelijk $0$) hebben een inverse in $\Z/m\Z$ tenzij $m$ een priemgetal is. Voor een priemgetal $p$ is de ring $\Z/p\Z$ wel een lichaam dat uit precies $p$ verschillende elementen bestaat. Zo'n eindig lichaam $\Z/p\Z$ wordt ook wel met $\F_p$ aangegeven. Later zullen we zien dat voor elke {\it macht} $q=p^k$ van een priemgetal $p$ er een eindig lichaam $\F_q$ van $q$ elementen bestaat (en voor geen enkel ander natuurlijk getal). Bovendien is er in essentie maar \'e\'en zo'n lichaam\label{opm:uniek}. \end{vbd} \opgave{Opgave}{Maak een opteltabel en een vermenigvuldigingstabel voor $\Z/7\Z$. Hoe lees je aan deze tabel de eigenschappen L2--4, L6--8 af? Laat zien dat $\Z/7\Z$ een lichaam vormt.} \opgave{Opgave}{De quaternionen van Hamilton $\H$ worden gedefinieerd als uitdrukkingen van de vorm $a+b\ii+c\jj+d\kk$ met $a,b,c,d\in\R$. Twee zulke uitdrukkingen $a_1+b_1\ii+c_1\jj+d_1\kk$ en $a_2+b_2\ii+c_2\jj+d_2\kk$ zijn hetzelfde dan en slechts dan als $a_1=a_2$ en $b_1=b_2$ en $c_1=c_2$ en $d_1=d_2$. Optellen geschiedt componentsgewijs, hetgeen som $a_1+a_2+(b_1+b_2)\ii+(c_1+c_2)\jj+(d_1+d_2)\kk$ geeft, en vermenigvuldiging vindt plaats met de regels: $$\begin{array}{ccccccc} \ii^2&=&\jj^2&=&\kk^2&=&-1\cr \ii\cdot \jj&=&\kk& &\jj\cdot \ii&=&-\kk\cr \jj\cdot \kk&=&\ii& &\kk\cdot \jj&=&-\ii\cr \kk\cdot \ii&=&\jj& &\ii\cdot \kk&=&-\jj.\cr \end{array} $$ Laat zien dat $\H$ met deze bewerkingen een niet-commutatieve ring vormt. (Voor het bewijs van associativiteit van vermenigvuldiging helpt het om $a+b\ii+c\jj+d\kk=(a+b\ii)+(c+d\ii)\jj$ te schrijven.) Geef een isomorfisme aan van $\H$ met de deelring van $\Mat_2(\C)$ bestaande uit matrices $A\cdot I+B\cdot J+C\cdot K+D\cdot L$, waar $A,B,C,D\in\R$ en $$ I=\left(\begin{array}{cc}1&0\cr 0&1\cr\end{array}\right),\quad J=\left(\begin{array}{cc}\ii&0\cr 0&-\ii\cr\end{array}\right),\quad K=\left(\begin{array}{cc}0&1\cr -1&0\cr\end{array}\right),\quad L=\left(\begin{array}{cc}0&\ii\cr \ii&0\cr\end{array}\right). $$ Laat ook zien dat $a+b\ii+c\jj+d\kk$ een inverse heeft tenzij $a=b=c=d=0$, door te kijken naar $(a+b\ii+c\jj+d\kk)\cdot (a-b\ii-c\jj-d\kk)$. De quaternionen vormen een {\it scheeflichaam}: een ring die aan alle axioma's voor een lichaam voldoet behalve de commutativiteit {\rm [L8]}.} \vfill\eject \section{Vectorruimten} Nu zijn we in staat definities en stellingen uit {\bf Lineaire Algebra 1} en {\bf 2} te generaliseren. \begin{dfn}\label{def:vr}\rm Zij $L$ een lichaam. Een {\it $L$-vectorruimte} is een verzameling $V$ met een bewerking $+$ en een afbeelding die aan elk paar $(\lambda, v)\in L\times V$ een element $\lambda v\in V$ toevoegt, die voldoen aan: \newcounter{vr} \begin{list}{\rm [V\arabic{vr}]}{\usecounter{vr} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item de operatie $+$ op $V$ is associatief: $(u+ v)+ w=u+(v+ w)$, voor alle $u, v,w\in V$; \item er is een (nul)element $0\in V$ zodanig dat $0+ v=v+ 0=v$ voor alle $v\in V$; \item bij elke $v\in V$ is er een {\it tegengestelde} $-v \in V$ zodanig dat $v +(-v)=(-v) + v =0$; \item de operatie $+$ op $V$ is commutatief: $v+w=w+v$ voor alle $v,w\in V$; \item $1v=v$ voor alle $v\in V$; \item $\lambda (v+w)=\lambda v+\lambda w$ voor alle $\lambda \in L$ en $v,w\in V$; \item $(\lambda +\mu)v=\lambda v+\mu v$ voor alle $\lambda ,\mu \in L$ en $v\in V$; \item $(\lambda \mu )v=\lambda (\mu v)$ voor alle $\lambda ,\mu \in L$ en $v\in V$. \end{list} \end{dfn} \begin{opn}\rm Vergeet niet dat de eis dat $+$ een bewerking is oplegt dat \begin{list}{\rm [V0]}{ \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item $v_1+v_2\in V$ voor alle $v_1, v_2\in V$. \end{list} Een afbeelding $L\times V\rightarrow V$, voor een lichaam $L$ en een verzameling $V$, die aan V$[5-8]$ voldoet wordt een {\it scalaire vermenigvuldiging} genoemd. Kort samengevat kunnen we dan zeggen dat een $L$-vectorruimte niets anders is dan een additieve groep $(V, +)$ met daarop een scalaire vermenigvuldiging gedefinieerd. De elementen van $L$ heten {\it scalairen}, die van $V$ {\it vectoren}. Merk op dat bij een vectorruimte dus een lichaam hoort waaruit de scalairen komen. In {\bf Lineaire Algebra 1} werd onder vectorruimte het speciale geval van $\R$-vectorruimte of {\it re\"ele vectorruimte} verstaan. Het is ook mogelijk een struktuur analoog aan een vectorruimte maar dan algemener over een ring te defini\"eren, een zogenaamd {\it $R$-moduul}. \end{opn} \begin{vbn}\rm \noindent \setcounter{vvv}{1} \begin{list}{\rm (\roman{vvv})}{\usecounter{vvv} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.5ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\listparindent 3.6ex} \setlength{\leftmargin 6.0ex} } \item Uit {\bf Lineaire Algebra 1} ken je de ruimte $\R^n$ bestaande uit $n$-tallen re\"ele getallen (geschreven als {\it rij}vector of {\it kolom}vector) met de co\"ordinaatsgewijze optelling en scalaire vermenigvuldiging. Net zo is de verzameling van alle rijtjes van $n$ elementen uit een lichaam $L$ een $L$-vectorruimte, die we met $L^n$ aangeven (voor $n\geq 1$). Per definitie is $L^0=\{0\}$. \item De verzameling van {\it oneindige rijtjes} elementen $x_1, x_2, \ldots$ van $L$ is een $L$-vectorruimte onder co\"ordinaatsgewijze optelling en vermenigvuldiging, die we met $L^\infty$ aangeven. \item De verzameling van elementen van $L[x]$ vormt met optelling en scalaire vermenigvuldiging $\lambda (a_mx^m+\cdots +a_1x+a_0)=(\lambda a_m)x^m+\cdots + (\lambda a_1)x+\lambda a_0$ een $L$-vectorruimte, voor elk lichaam $L$. \item Laat $\Mat_{m\times n}(L)$ voor een lichaam $L$ en positieve gehele getallen $m,n$ de verzameling van $m\times n$ matrices met co\"effici\"enten in $L$ zijn. Dan is $\Mat_{m\times n}(L)$ een $L$-vectorruimte (onder optelling), als de scalaire vermenigvuldiging $\lambda M$ eruit bestaat elke co\"effici\"ent van de matrix $M$ met $\lambda $ te vermenigvuldigen. \item Voor een willekeurige verzameling $S$ vormt de verzameling van afbeeldingen $\phi:\ S\rightarrow L$ naar een lichaam $L$ een vectorruimte als we optelling defini\"eren door $(\phi_1+\phi_2)(s)=\phi_1(s)+\phi_2(s)$ voor $s\in S$, en scalaire vermenigvuldiging door $(\lambda\phi)(s)=\lambda\cdot\phi(s)$ voor $s\in S$, $\lambda\in L$. We geven die ruimte wel aan met $L^S$. Merk op dat met $S=\{1, 2, \ldots, n\}$ we $L^n$ vinden, dat $L^\N=L^\infty$ en dat $\Mat_{m\times n}(L)$ hetzelfde is als $L^S$ voor $S=\{1, 2, \ldots, m\}\times \{1, 2, \ldots, n\}$. \item Met $L=\R$ en $I$ een open interval van $\R$ is $L^S=\R^I$ de vectorruimte van {\it re\"eelwaardige functies} op $I$. Leggen we op dat de functies $k$-maal continu differentieerbaar zijn, dan geven we die ruimte wel met ${\cal C}^{(k)}(I)$ aan. Zo bestaat ${\cal C}^{(0)}(\R)$ uit de continue re\"ele functies. \end{list} \end{vbn} \opgave{Opgave}{Laat zien dat $\R^n$ een $\Q$-vectorruimte is. Is $\C^n$ een $\R$-vectorruimte? En is $\Q^n$ een $\R$-vectorruimte?} \begin{dfn}\label{def:deelr}\rm Een {\it $L$-lineaire deelruimte} van een $L$-vectorruimte $V$ is een deel\-ver\-za\-meling $U\subset V$ met de eigenschap dat: \setcounter{vvv}{1} \begin{list}{\rm (\roman{vvv})}{\usecounter{vvv} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.5ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\listparindent 3.6ex} \setlength{\leftmargin 6.0ex} } \item $0\in U$; \item $u_1+u_2\in U$ voor alle $u_1, u_2\in U$; \item $\lambda u\in U$ voor elke $\lambda\in L$ en $u\in U$. \end{list} \end{dfn} \begin{opn}\rm Net als in het re\"ele geval geldt hier weer dat de naam $L$-lineaire deelruimte terecht suggereert dat het een deelverzameling $U\subset V$ is die met de van $V$ {\it ge\"erfde} optelling en scalaire vermenigvuldiging zelf een $L$-vectorruimte vormt. In veel van de definities laten we de toevoeging $L$- wel weg als het onbelangrijk is, of duidelijk uit de context om welk lichaam het gaat. \end{opn} \opgave{Opgave}{Laat zien dat de eerste voorwaarde uit \ref{def:deelr} gemist kan worden mits we eisen dat $U$ niet-leeg is; laat door twee voorbeelden zien dat geen van beide andere voorwaarden gemist kan worden.} \opgave{Opgave}{Laat zien dat de {\it convergente rijtjes} $y_1, y_2, \ldots$ een lineaire deelruimte vormen van $\R^\infty$.} \begin{dfs}\rm Een {\it $L$-lineaire combinatie} van elementen $v_1, \ldots, v_k$ uit een $L$-vectorruimte $V$ is een element $\lambda_1v_1+\cdots+\lambda_k v_k\in V$, waar $\lambda_i\in L$. Het {\it $L$-opspansel} van $v_1, \ldots, v_k$ is de verzameling van alle $L$-lineaire combinaties van $v_1, \ldots, v_k$: $$\langle v_1, \ldots, v_k\rangle=\{\lambda_1v_1+\cdots+\lambda_k v_k\ \vert\ \lambda_1, \ldots, \lambda_k \in L\}.$$ Een {\it volledig stelsel} (of ook wel {\it opspannend stelsel}) vectoren voor een vectorruimte $V$ is een verzameling $\{ v_1, v_2, \ldots, v_k\}\subset V$ zodat $V=\langle v_1, v_2, \ldots, v_k\rangle$; we zeggen dat de $v_i$ de ruimte $V$ {\it opspannen (over $L$)}. Een {\it $L$-basis} voor een vectorruimte $V$ is een volledig stelsel dat bovendien {\it onafhankelijk} is over $L$; hier heet $v_1, v_2, \ldots, v_k$ een onafhankelijk stelsel over $L$ als voor $\lambda_1, \ldots, \lambda_k \in L$ geldt: $$\lambda_1v_1+\cdots+\lambda_k v_k=0\quad\Rightarrow\quad \lambda_1=\lambda_2=\cdots=\lambda_k=0.$$ Een stelsel dat niet onafhankelijk is heet natuurlijk {\it afhankelijk}. Op grond van de onderstaande stelling kunnen we voor de {\it dimensie} $\dim V$ van een vectorruimte $V\neq \{0\}$ het maximale aantal $n$ van onafhankelijke vectoren in $V$ nemen als zo'n eindig getal $n$ bestaat; als dat niet bestaat is de dimensie {\it oneindig}. De nulruimte $\{0\}$ heeft per definitie dimensie 0. Zodra een basis ${\cal B}=\{b_1, \ldots, b_n\}$ voor een $L$-vectorruimte is gekozen, kan elk element $v\in V$ op unieke manier gerepresenteerd worden door een {\it co\"ordinatenvector} $v=(v_1, \ldots, v_n)_{\cal B}\in L^n$, namelijk zo dat $$v=v_1b_1+\cdots+v_nb_n.$$ \end{dfs} \begin{opm}\rm %{Opmerkingen} Eigenlijk is het beter om een basis niet als verzameling te defini\"eren, want de {\it volgorde} doet er wel degelijk toe (voor de co\"ordinatenvector bijvoorbeeld)! (Zie ook de opgave na \ref{opg:basis}.) \end{opm} \begin{thm}[Hoofdstelling van de Lineaire Algebra]\label{st:hfd} Als er een $L$-basis van de $L$-vectorruimte $V$ is die uit $n>0$ elementen bestaat, dan heeft elke $L$-basis van $V$ precies $n$ elementen. \end{thm} \begin{thm}Zij $V$ een vectorruimte en $n\geq 1$. Als $\{v_1, \ldots, v_n\}\subset V$ een volledig stelsel vormen, is elk stelsel $\{w_1, \ldots, w_m\}\subset V$ met $m>n$ afhankelijk. \end{thm} De bewijzen van deze twee stellingen in {\bf Lineaire Algebra 1} voor het geval $L=\R$ blijken op een enkel detail na (lees $L$ in plaats van $\R$) ook in het algemene geval te gelden: de laatste stelling bewijs je door te laten zien dat een homogeen stelsel van $n$ vergelijkingen in $m$ onbekenden altijd een oplossing heeft (in $L$) die niet de nul-oplossing is. Dan bewijs je de Hoofdstelling door te laten zien dat $\#{\cal B}_1\leq \#{\cal B}_2$ en $\#{\cal B}_2\leq\#{\cal B}_1$ als ${\cal B}_1$ en ${\cal B}_2$ allebei bases voor $V$ zijn, en dus moet $\#{\cal B}_1=\#{\cal B}_2$. \begin{vbn}\rm %{Voorbeelden} \noindent \setcounter{vvv}{1} \begin{list}{\rm (\roman{vvv})}{\usecounter{vvv} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.5ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\listparindent 3.6ex} \setlength{\leftmargin 6.0ex} } \item De dimensie van $L^n$ is $n$, en $L^\infty$ heeft oneindige dimensie. De {\it standaardbasis} ${\cal E}=\{e_1, \ldots, e_n\}$ van $L^n$ bestaat uit de vectoren $$ e_1=\left(\begin{array}{c}1\\0\\\vdots\\0\\\end{array}\right),\quad e_2=\left(\begin{array}{c}0\\1\\\vdots\\0\\\end{array}\right),\quad \cdots,\quad e_n=\left(\begin{array}{c}0\\0\\\vdots\\1\\\end{array}\right). $$ \item $\Mat_{m\times n}(L)$ is een vectorruimte van dimensie $mn$. \item $L[x]$ is oneindig dimensionaal, voor elk lichaam $L$. \end{list} \end{vbn} \opgave{Opgave}{Is het over een willekeurig lichaam waar dat een homogeen stelsel van $n$ vergelijkingen in $m$ onbekenden (met $m>n$) oneindig veel oplossingen heeft?} \opgave{Opgave}{Bewijs dat een homogeen stelsel van $n$ vergelijkingen in $m$ onbekenden over $\Z$ altijd oplossingen in $\Z$ heeft. Is het waar dat er altijd oneindig veel oplossingen in $\Z$ zijn als $m>n$?} \opgave{Opgave}{Laat zien dat $\Q[x]$ een oneindig-dimensionale $\Q$-vectorruimte vormt, door voor elke $n>0$ een onafhankelijk stelsel van $n$ elementen uit $\Q[x]$ aan te geven.} \begin{thm} Elke lineaire deelruimte $U$ van een eindig-dimensionale vectorruimte $V$ is eindig-dimensionaal, en er geldt $\dim U\leq \dim V$. \end{thm} Ook het bewijs van deze stelling verloopt precies zo als voor het speciale geval $L=\R$: bewijs eerst een lemma. \begin{lem} Als $\{ v_1, \ldots, v_n\}$ een onafhankelijk stelsel vormen in de vectorruimte $V$, en $w\in V\setminus\langle v_1, \ldots, v_n\rangle$, dan is $\{ v_1, \ldots, v_n, w\}$ onafhankelijk. \end{lem} Vervolgens laat je zien dat een maximaal onafhankelijk stelsel in $U\subset V$ ten hoogste $n=\dim V$ elementen kan bevatten. Ook dat gaat over een willekeurig lichaam. \opgave{Opgave}{Het bewijs van het lemma over $\R$ gebruikte dat met $a_i, a\in\R$: $$a_1u_1+\cdots+a_nu_n+av=0\quad\Rightarrow\quad v=b_1 u_1+\cdots+ b_nu_n,$$ met $b_i\in\R$. Laat met een voorbeeld zien dat dit niet waar is als je eist dat $a_i, a, b_i\in\Z$.} \begin{gvn} In een eindig-dimensionale vectorruimte is elk onafhankelijk stelsel aan te vullen tot een basis, en is elk volledig stelsel uit te dunnen tot een basis. \end{gvn} \opgave{Opgave}{Bewijs dat (voor elke $n\geq1$ en elk lichaam $L$) de diagonaalmatrices (met alleen niet-nul elementen toegestaan op de diagonaal) een lineaire deelruimte van $\Mat_{n\times n}(L)$ vormen. Bepaal de dimensie van deze ruimte en geef een basis.} \opgave{Opgave}{Laat zien dat $W_1$ en $W_2$ lineaire deelruimten van $\Q^5$ zijn en $W_3$ niet; bepaal ook de dimensie en een basis voor $W_1$ en $W_2$. Hier is $W_1=\{\ (a, b, c, d, e)\in \Q^5\ \vert\ a+b=c+d\ \}$, en $W_2=\{\ (a, b, c, d, e)\in \Q^5\ \vert\ a=b=c\ \mbox{en}\ a+d+e=0\ \}$, en $W_3=\{\ (a, b, c, d, e)\in \Q^5\ \vert\ a^2 = b + 1\ \}$.} \opgave{Opgave}{Bewijs dat de doorsnede van twee lineaire deelruimten van een $L$-vector\-ruim\-te $V$ weer een lineaire deelruimte van $V$ is. Laat zien dat zelfs geldt dat $\cap_{i\in I} W_i$ een lineaire deelruimte van $V$ is als alle $W_i$ dat zijn, voor $i\in I$.} \opgave{Opgave}{Geef een voorbeeld waaruit blijkt dat de vereniging van twee lineaire deelruimten van een $L$-vectorruimte $V$ niet weer een lineaire deelruimte van $V$ hoeft te zijn. Bewijs dat zelfs geldt voor lineaire deelruimten $W_1, W_2$ van $V$ dat: $W_1\cup W_2$ is een lineaire deelruimte van $V$ dan en slechts dan als $W_1\subset W_2$ of $W_2\subset W_1$.} \opgave{Opgave}{Laat zien dat voor elk lichaam $L$ en elk geheel getal $n\geq 0$ de deelverzameling $\{\ f\in L[x]\ \vert\ \deg f\leq n\ \}$ een lineaire deelruimte is van $L[x]$; deze ruimte zullen we wel met $L[x]^{(n)}$ aangeven. Bepaal de dimensie van $L[x]^{(n)}$ en geef een basis.} \vfill\eject \section{Toepassing: Codes} Als toepassing van vectorruimten over eindige lichamen kijken we naar foutenverbeterende codes. We benutten slechts elementaire kennis van vectorruimten, en van het standaardinproduct. \begin{dfn}\rm Als $R$ een commutatieve ring met $1$ is en $R^n$ de verzameling van rijtjes elementen van $R$ ter lengte $n$ (voor een $n\geq 1$), dan is het {\it standaardinproduct} op $R^n$ de functie $\langle v, w\rangle \rightarrow R$ die aan twee elementen $v, w\in R^n$ het element $\sum_{i=1}^nv_iw_i\in R$ toevoegt. \end{dfn} \begin{opm}\rm Het is gebruikelijk om het standaardinproduct te defini\"eren voor het speciale geval dat $R$ een lichaam is, en $R^n$ de standaard vectorruimte van dimensie $n$. Het is voor enkele van de voorbeelden verderop prettig deze algemenere definitie te hebben. Een algemenere definitie van inproducten voor een vectorruimte volgt nog in Hoofdstuk 6. \end{opm} \opgave{Opgave}{Is het met bovenstaande definitie altijd waar dat het inproduct $\langle v, v\rangle$ van een vector ongelijk aan $0$ is (wanneer $v$ niet uit louter nullen bestaat)?} \begin{dfs}\rm Een {\it lineaire (foutenverbeterende) code over} $\F_q$ is een lineaire deelruimte van $\F_q^n$, voor een $n\geq 1$. We zullen meestal simpelweg over een {\it code} $\Co$ over $\F_q$ spreken. De {\it codewoorden} zijn de elementen van $\F_q^n$ die bevat zijn in $\Co$. De {\it dimensie} $\dim \Co$ van de code is de dimensie van de deelruimte. De {\it lengte} van de code is de dimensie $n$ van de ruimte waaruit de vectoren afkomstig zijn, dus de lengte van de codewoorden. \end{dfs} \begin{opn}\rm %{Opmerkingen} Merk op dat per definitie het nulwoord altijd in een code zit. Het aantal elementen van de code is gelijk aan $q^k$, als $k=\dim\Co$ en $q$ het aantal elementen van het lichaam. De verhouding tussen $k$ en $n$ wordt wel de `rate' van de code genoemd: van de $n$ co\"ordinaten van elk codewoord dragen er $k$ bij aan de informatie, de overige $n-k$ zijn `opvulsel', redundantie. Het doel van {\it codetheorie} is om die $n-k$ extra co\"ordinaten effici\"ent te gebruiken om ervoor te zorgen dat de informatie uit het codewoord nog te achterhalen is wanneer een deel van het codewoord onderweg verminkt of verloren is geraakt, bijvoorbeeld door `ruis' op de transmissielijn. Het uitgangspunt van het model dat ten grondslag ligt aan codetheorie is steeds dat de kans klein is dat informatie verminkt overkomt. \end{opn} \begin{vbn}\rm Het eenvoudigste voorbeeld van een foutenverbeterende code is de {\it repetitiecode} ter lengte $n$ over $\F_2$: om een bit informatie ($0$ of $1$) over te sturen wordt die bit $n$ maal verzonden. De codewoorden zijn hier dus slechts de vectoren $(1, 1, \ldots, 1)$ en $(0, 0, \ldots 0)$ in $\F_2^n$, en de dimensie $k$ is $1$. Wanneer de ontvanger nu het woord $(1, 1, 0, 1, 1)$ ontvangt terwijl de binaire repetitiecode van lengte $5$ gebruikt wordt, zal onder de aanname dat fouten vrij zelden op treden, de conclusie moeten luiden dat hoogstwaarschijnlijk het codewoord $(1, 1, 1, 1, 1)$ werd uitgezonden, maar dat op de derde positie een fout optrad. Ook wanneer er onderweg de uitzonderlijke pech optreedt dat twee bits worden omgezet kan de ontvanger hier nog tot de juiste conclusie komen met betrekking tot de bedoelde waarde van de bit. De repetitiecode ter lengte $n$ is dus $(n-1)/2$ foutenverbeterend als $n$ oneven is: we komen tot de juiste conclusie over het bit dat overgezonden moest worden mits de kans op $i$ fouten maar (veel) kleiner is dan de kans op $n-i$ fouten. Deze aanname, dat elk cijfer van de code met kleine waarschijnlijkheid onderweg wordt veranderd, en dat het uitgezonden codewoord de vector zal zijn geweest die in de code zit en op het kleinst mogelijke aantal plaatsen van de ontvangen vector afwijkt, leidt tot de methode om de informatie te achterhalen die {\it maximale waarschijnlijkheidsdecodering} wordt genoemd. \end{vbn} \begin{dfs}\rm %{Definities} Het {\it gewicht} van een vector $v$ uit $\F_q^n$ is het aantal posities $i$ waarvoor de co\"ordinaat $v_i\in\F_q$ niet nul is. De {\it Hammingafstand} $h(v, w)$ tussen twee vectoren $v, w$ uit $\F_q^n$ is het aantal posities $j$ waarop de co\"ordinaten $v$ en $w$ verschillen: $h(v,w)=\#\{j:\ 1\leq j\leq n\ |\ v_j\neq w_j\}$, dus $0\leq h(v, w)\leq n$. De {\it minimumafstand} van een code $\Co$ is het kleinste positieve getal $d$ waarvoor codewoorden $v, w\in\Co$ bestaan met $h(v,w)=d$. \end{dfs} \opgave{Opgave}{Bewijs dat $h(v, w)$ gelijk is aan het gewicht van de vector $v-w$. Laat ook zien dat de minimumafstand van een code gelijk is aan het minimumgewicht van de code, dat wil zeggen, de kleinste positieve $g$ waarvoor een codewoord van gewicht $g$ bestaat.} \opgave{Opgave}{Bewijs dat de Hammingafstand een metriek definieert, dat wil zeggen, voor alle $u, v, w\in\F_q^n$ geldt: \begin{hwitemize} \item $h(v, w)\geq 0$;\ \ en $\qquad[ h(v, w)=0\quad\iff\quad v=w ]$; \item $h(v, w)=h(w, v)$; \item $h(u, v)+h(v, w)\geq h(u,w)$. \end{hwitemize}} \begin{dfn}\rm %{Definitie} Een code $\Co$ van lengte $n$ over $\F_q$ heet {\it $e$-foutenverbeterend} als geldt dat voor elke vector $v\in\F_q^n$ er hoogstens \'e\'en codewoord $c\in\Co$ is met $h(c,v)\leq e$. Dat betekent dat wanneer een codewoord op precies $e$ plaatsen wordt verminkt, er nog steeds een uniek codewoord op afstand $\leq e$ is. De code heet dan bovendien {\it $e+1$-foutendetecterend} als geldt dat elke op $e+1$ plaatsen verminkte vector afstand minstens $e+1$ tot alle codewoorden heeft. Het is mogelijk dat er dan meerdere codewoorden op afstand $e+1$ liggen, zodat unieke decodering onmogelijk is, maar er liggen geen codewoorden op afstand $\leq e$. \end{dfn} \begin{vbd}[parity check]\rm Een simpel voorbeeld van een code die $1$-fout\-detecterend is, maar niet foutenverbeterend, is een code van lengte (zeg) $3$ over $\F_2$ die bestaat uit alle woorden van even gewicht. Wanneer er dan een woord van oneven gewicht wordt ontvangen is het duidelijk dat er minstens 1 fout is opgetreden, maar w\'a\'ar is niet duidelijk. \end{vbd} \opgave{Opgave}{Ga na dat voor elke lengte $n$ de vectoren van even gewicht in $\F_2^n$ een code vormen, en dat de codewoorden precies die vectoren zijn waarvoor het inproduct met de vector die uit allemaal enen bestaat, nul is.} \begin{vbd}[UPC]\rm %{Voorbeeld: UPC} Een eenvoudig voorbeeld van foutendetectie wordt gebruikt in de {\it streepjescode} die hoort bij de {\it Universal Product Code}, UPC. Deze codering, sinds 1973 in gebruik, is terug te vinden op heel veel consumptie\-goe\-deren, en bestaat uit 12 decimale cijfers, hier te representeren als een element $v\in\Z/10\Z)^{12}$. Het eerste cijfer geeft een indicatie van het type product, de volgende 5 cijfers geven de fabrikant aan, en daarna volgen 5 cijfers voor het product. Het laatste cijfer $v_{12}$ is het zogenaamde {\it check}-cijfer en wordt geheel bepaald door de regel $$\langle (3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1), v\rangle = 0\in\Z/10\Z,$$ dat wil zeggen, $$3\sum_{i=1}^6v_{2i-1}+\sum_{i=1}^6v_{2i}= 0\in\Z/10\Z.$$ \end{vbd} \begin{vbd}\rm %{Voorbeeld: ISBN} Het {\it international standard book number} (ISBN) is een ander voorbeeld van een `codering' die van een check-cijfer gebruik maakt. Het ISBN is (op te vatten als) een vector $w$ uit $(\Z/11\Z)^{10}$ met de restriktie dat de eerste 9 co\"ordinaten ongelijk aan $\overline{10}$ zijn; ze worden elk weergegeven als decimale cijfers, en representeren land (1 tot 3 cijfers), uitgever (1 tot 5 cijfers), en boek. Het allerlaatste cijfer is weer een element dat als check-digit dient, en dat w\'el elk element uit $\Z/11\Z$ kan zijn, weergegeven door een decimaal (de kleinste niet-negatieve representant van de restklasse) of de letter X (die de restklasse $\overline{10}$ representeert. De waarde ervan wordt volledig bepaald door de regel $$\langle (10, 9, 8, 7, 6, 5, 4, 3, 2, 1), w\rangle =\sum_{i=1}^{10}(11-i)w_{i} = 0\in\Z/11\Z.$$ \end{vbd} \begin{vbd}\rm %{Voorbeeld: EAN-13} Op de meeste producten wordt sinds 1 januari 2005 het {\it European Article Number} vermeld in plaats van de UPC. Dit EAN bestaat uit een vector $x$ ter lengte 13 over $\Z/10\Z$, waar het laatste cijfer $x_{13}$ een check-digit is, bepaald door $$\langle (1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1), x\rangle =3\sum_{i=1}^6v_{2i}+ \sum_{i=1}^7v_{2i-1}= 0\in\Z/10\Z.$$ Oude UPC aanduidingen kunnen simpel vervangen worden door een EAN door de oude vector vooraf te laten gaan door een $0$. De nieuwe EAN aanduidingen geven land, fabrikant, en product met een wisselend aantal cijfers weer. Per 1 januari 2007 worden ook de oude ISB nummers vervangen door een 13-cijferige ISBN-13, die net zo is opgebouwd als de EAN; de eerste 3 cijfers van de nieuwe aanduiding (die voorlopig altijd 978 zullen zijn) staan voor het universele `Bookland'. \end{vbd} \opgave{Opgave}{Ga na dat elke $e$ foutenverbeterende code ook $e-1$ foutenverbeterend is.} \begin{thm} Een code met minimumafstand $d$ is $e$-foutenverbeterend dan en slechts dan wanneer $d\geq 2e+1$. \end{thm} \smallskip\noindent {\bf Bewijs.} Veronderstel dat er een vector $v$ bestaat op afstand kleiner of gelijk $e$ van twee codewoorden $w_1$ en $w_2$. Dan is $$h(w_1, w_2)\leq h(w_1, v)+h(v, w_2)\leq 2e,$$ hetgeen in tegenspraak is met $d\geq 2e+1$, tenzij $w_1=w_2$. Dus is er hoogstens \'e\'en vector op afstand ten hoogste $e$ als de minimumafstand ten minste $2e+1$ is. Is daarentegen de minimumafstand $d$ hoogstens $2e$, dan zijn er twee code\-woorden $u, w$ op afstand $d\leq 2e$ van elkaar. Vorm nu een rij $$u=x_1, x_2, \ldots, x_{d}, x_{d+1}=w$$ ter lengte $d+1$ van vectoren, waarbij $x_{i+1}$ steeds op precies 1 co\"ordinaat van $x_i$ verschilt. Dan is er een vector $v=x_{\lfloor d/2\rfloor}$ die op hoogstens $e$ co\"ordinaten van $u$ en op niet meer dan $e$ co\"ordinaten van $w$ verschilt. Dus kunnen $e$ fouten niet uniek verbeterd worden. \opgave{Opgave}{Laat zien dat een andere formulering van dezelfde stelling is: een code is $e$ foutenverbeterend dan en slechts dan als alle verschillende bollen met straal $e$ om codewoorden disjunct zijn.} \medskip\noindent De centrale vraag voor de coderingstheorie is gelegen in de spanning tussen de twee eisen die we graag aan codes zouden opleggen. In de eerste plaats willen we zoveel mogelijk informatie oversturen, dat wil zeggen de rate $k/n$ zo groot mogelijk maken (en de redundantie klein). Anderzijds willen we graag zoveel mogelijk fouten kunnen herstellen, dus $e$ (en daarmee $d$ volgens de Stelling) zo groot mogelijk kiezen; maar een grote minimumafstand betekent veel vectoren buiten de codewoorden, dus juist een lage rate. Er bestaan heel veel grenzen op de omvang van goede codes. We geven hier een bekende bovengrens op het aantal codewoorden als de dimensie en het aantal fouten $e$ dat verbeterd moet kunnen worden gegeven is. \begin{thm}[Hamming grens] Een code over $\F_q$ van lengte $n$ en minimumafstand groter of gelijk $2e+1$ heeft hoogstens $$\frac{q^n}{\sum_{i=0}^e\left({n\atop i}\right)(q-1)^i}$$ codewoorden. \end{thm} \smallskip\noindent {\bf Bewijs.} Alle bollen met straal $e$ rond codewoorden moeten disjunct zijn. Deze bevatten in totaal $$\#\Co\cdot \sum_{i=0}^e\left({n\atop i}\right)(q-1)^i$$ vectoren, omdat een woord op afstand $i$ van codewoord $w$ op $\left({n\atop i}\right)$ plaatsen op $(q-1)^i$ manieren van $v$ kan verschillen. Dit aantal vectoren is begrens door $q^n$, waaruit de grens volgt. \begin{opn}\rm Veronderstel nu dat we een $k$-dimensionale code willen construeren in een $n$-dimensionale vectorruimte over $\F_q$ (met $k