Bij rijreductie passen we elementaire rijoperaties toe; daarbij worden één of meer van de volgende bewerkingen toegepast:
- een rij met een getal ongelijk aan nul vermenigvuldigen
- een scalair veelvoud van een rij bij een andere rij optellen
- het veranderen van de volgorde van de rijen
Dit zijn de toegestane handelingen. We hebben daarmee het proces van rijreductie nog niet vastgelegd. Doel van rijreductie is de matrix in gereduceerde trapvorm te brengen. We laten dat eerst aan de hand van enkele voorbeelden zien.
Breng de volgende matrix in gereduceerde trapvorm: \[A=\left(\,\begin{array}{rrrr} {1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)\]
\(\left(\,\begin{array}{rrrr} {1} & {0} &{0} & 28\\ {0} & {1} & {0} & -6\\ {0} & {0} &{1} & 2 \end{array}\,\right)\)
We beginnen met de matrix: \[A=\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)\] Groene elementen willen we onveranderd laten. We proberen eerst met de eerste rij zo veel mogelijk nullen in de eerste kolom te krijgen. Dat doen we door de eerste rij bij de tweede op te tellen en van de derde af te trekken. We krijgen dan: \[\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -\,4 & 8\\ \color{green}{0} & 0 & 2 & 4\\ \color{green}{0} & 2 & 2 & -8 \end{array}\,\right)\] Nu proberen we met de tweede rij de tweede kolom `schoon te vegen'. Dat gaat niet omdat het tweede element #0# is. We verwisselen nu de tweede en derde rij (niet de tweede en eerste rij, want dan verstoren we het resultaat uit de eerste kolom!): \[\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & 2 & 2 & -8\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right) \]
en delen de tweede rij door #2#: \[\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} &\color{green}{0} & 2 & 4 \end{array}\,\right)\] Nu kunnen we met de tweede rij de tweede kolom schoonvegen. We trekken hem tweemaal van de eerste af; merk op dat daardoor de eerste kolom onveranderd blijft: \[\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right)\] Nu gaan we met de derde rij de derde kolom schoonvegen. Daartoe delen we hem eerst door #2#: \[\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2\end{array}\,\right)\] en tellen de nieuwe derde rij #6# maal bij de eerste rij op en trekken hem ook van de tweede rij af; merk weer op dat hierdoor de eerste twee kolommen onveranderd blijven: \[\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & \color{green}{0} & 28\\ \color{green}{0} & \color{green}{1} & \color{green}{0} & -6\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2 \end{array}\,\right)\]
Nu kunnen we niet meer verder vegen; iedere veegpartij in de vierde kolom verstoort het resultaat in de eerste drie kolommen. Het verkregen resultaat is de gereduceerde trapvorm van \(A\).
Uit het proces is het niet onmiddellijk duidelijk, maar rijreductie van een matrix levert een uniek resultaat op; we kunnen dus inderdaad spreken van de gereduceerde trapvorm van een matrix.
We beschrijven nu het algemene proces van rijreductie in de vorm van een algoritme. De lezer wordt aangeraden het zojuist gegeven voorbeeld te vergelijken met de volgende beschrijving.
Gauss-eliminatiemethode, of kortweg Gauss-eliminatie, is een methode om een matrix te reduceren tot een matrix in gereduceerde trapvorm door middel van elementaire rijbewerkingen.
Elke matrix kan gereduceerd worden tot een unieke gereduceerde trapvorm. De methode hieronder voert Gauss-eliminatie uit.
De eerste stap bestaat uit de volgende handelingen op een gegeven matrix met \(m\) rijen en \(n\) kolommen:
- Laat #n_1# het nummer van de eerste kolom zijn die niet uitsluitend uit nullen bestaat.
- Verwissel eventueel twee rijen zodanig dat het eerste element van kolom #n_1# niet nul is.
- Deel de eerste rij door het eerste element van de kolom #n_1#, zodat #a_{1n_1}=1#.
De matrix heeft nu de volgende vorm gekregen: \[ \left(\,\begin{array}{cccccccc} 0 & \ldots & 0 & 1 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_2 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_3 & \ast & \ast & \ldots & \ast \\ \vdots & & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & \ldots & 0 & \alpha_m & \ast & \ast & \ldots & \ast \end{array}\,\right)\] Met \(\ast\) noteren we de matrixelementen waarvan de waarde in de redenering niet belangrijk is.
- Veeg met de eerste rij kolom #n_1# verder schoon. We krijgen een matrix van de volgende vorm (met een omkaderde deelmatrix):
\[\left(\,\begin{array}{cc} \begin{array}{cccc} 0 & \ldots & 0 & 1\end{array} & \begin{array}{cccc} \ast & \ast & \ldots & \ast \end{array} \\ \begin{array}{cccc} 0 & \ldots & 0 & 0 \\ 0 & \ldots & 0 & 0 \\ \vdots & & \vdots & \vdots \\ 0 & \ldots & 0 & 0\end{array} & \boxed{\begin{array}{cccc}\ast & \ast & \ldots & \ast\\ \ast & \ast & \ldots & \ast\\ \vdots & \vdots & & \vdots\\ \ast & \ast & \ldots & \ast\end{array}} \end{array}\,\right)\]
De eerste stap is nu voltooid. In de vervolgstappen passen we dezelfde procedure toe op de omkaderde deelmatrix (maar wel met schoonvegen van hele kolommen in de laatste stap) en herhalen dit proces totdat we geen kader meer overhouden of een kader met enkel nullen, waarna het gehele proces van rijreductie is voltooid.
De genoemde vervolgstappen kunnen we als volgt formeler opschrijven: stel dat we #k# stappen gedaan hebben. In de resulterende matrix zijn dan de eerste #k# rijen al gebruikt om te vegen en de laatst geveegde kolom heeft nummer #n_k#. We doen nu het volgende:
- Laat #n_{k+1}# het nummer van de eerste kolom zijn die vanaf het #(k+1)#-ste element niet alleen uit nullen bestaat.
- Verwissel eventueel rij #k+1# met een volgende rij zodanig dat het #(k+1)#-ste element van kolom #n_{k+1}# ongelijk is aan nul.
- Deel rij #k+1# door dat element, zodat #a_{k+1,n_{k+1}}=1#.
- Veeg met rij #k+1# de kolom #n_{k+1}# verder schoon.
Het resultaat van dit veegproces kan er na bijvoorbeeld drie stappen als volgt uit zien: \[\left(\,\begin{array}{ccccccccccccccc}
0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\
0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\
0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast\\
\vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & 0 & \vdots & & \vdots\\
\vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots\\
0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 & \ast & \ldots & \ast \end{array}\,\right)
\] Op de plaatsen met #\ast# staan elementen die niet noodzakelijk #0# of #1# zijn.
Het proces stopt automatisch als alle rijen zijn gebruikt om te vegen of als de laatste rijen alleen nullen bevatten.
In het algoritme, kiezen we een niet-nul element, brengen de rij waarin het voorkomt zonodig naar boven, maken we er #1# van, en zorgen we ervoor dat het het enige niet-nul element in zijn kolom is. De elementen die we zo in bovenstaand algoritme gebruiken om tot een gereduceerde trapvorm te komen, heten scharnierelementen (in het Engels: pivots). Omdat rijen verwisseld kunnen worden, wordt het begrip scharnierkolom gebruikt om de kolom aan te geven waar een scharnierelement in voorkomt.
De Gauss-eliminatie in de uitspraak laat zien dat elke matrix gereduceerd kan worden tot een matrix in rijgereduceerde trapvorm. We concentreren ons op het bewijs dat deze laatste matrix uniek is. Laat #A# een #(m\times n)#-matrix zijn en stel dat zowel #B# als #C# matrices in gereduceerde trapvorm zijn die verkregen zijn uit #A# door reductie. We moeten laten zien dat #B = C#.
Als #n=1#, dan is de uniciteit duidelijk: de matrices #B# en #C# hebben precies één kolom met een uniek element ongelijk aan #0#, dat gelijk aan #1# is, en #B# kan alleen tot #C# gereduceerd worden als het element #1# van #B# op dezelfde plaats staat als in #C#.
We gaan door met behulp van inductie naar #n# en veronderstellen #n\gt 1#. Laat #A_n# de deelmatrix van #A# die verkregen wordt door de laatste kolom, kolom #n#, weg te laten, en net zo voor #B# en #C#. De elementaire bewerkingen die gebruikt zijn in reductie van #A# tot #B# zijn ook elementaire bewerkingen die #A_n# tot #B_n# reduceren, en net zo voor #C_n#. Uit de inductiehypothese naar #n# volgt daarom dat #B_n=C_n#, zodat #B# en #C# alleen kunnen verschillen in de laatste kolom. Stel nu dat #B\ne C#. Dan is er een index #j# met #1\le j \le m# zodanig dat #b_{jn} \ne c_{jn}#. Als #Bx = 0#, dan geldt, omdat #C# tot #B# gereduceerd kan worden, ook #Cx=0#. De component #j# van de kolomvector #(B-C)x# is gelijk aan # (b_{jn} -c_{jn})\cdot x_j#, dus #x_j = 0#. Alweer omdat de oplossingen van #Bx=0# en #Cx=0# samenvallen, moeten # b_{jn}# en #c_{jn}# de leidende elementen zijn van rij #j# in #B#, respectievelijk #C# (want anders zouden er oplossingen van de vergelijking zijn met #x_j\ne0#). Maar de kolom #n# van #B# zowel als #C# heeft dan een #1# op plaats #j# en nullen elders, zodat ze gelijk zijn, in tegenspraak met de aanname #B\ne C#. Hiermee is bewezen dat #B=C#.
De elementaire rijoperaties op de matrix #A# kunnen gezien worden als vermenigvuldiging van #A# van links met een vierkante matrix:
- \(R_i\rightarrow c\cdot R_i\;(c\neq 0)\): Vermenigvuldiging van rij #i# van #A# met een getal #c# staat gelijk aan vermenigvuldiging van links met de diagonaalmatrix #B# met een #c# op de #i#-de plaats van de diagonaal en verder op de diagonaal allemaal enen.
- \(R_i\rightarrow R_i+c\cdot R_j\): Het optellen van een veelvoud #c# van één rij #j# bij een van de andere rij #i# staat gelijk aan vermenigvuldiging van links met de matrix #I+c\cdot E_{ij}#, waarbij #E_{ij}# de matrix is waarvan het #(i,j)#-element gelijk is aan #c# en alle andere elementen gelijk zijn aan #0#.
- \(R_i\leftrightarrow R_j\): Het verwisselen van de rijen #i# en #j# van #A# staat gelijk aan vermenigvuldiging van links met de permutatiematrix #B# behorende bij de permutatie #(i,j)#.
Bovengenoemde matrices noemen we elementaire matrices.
Vermenigvuldigen we een matrix van links met een elementaire matrix, dan voeren we dus een elementaire bewerking (ook wel rijbewerking of veegoperatie genoemd) uit op die matrix. In
Elementaire bewerkingen op stelsels lineaire vergelijkingen zagen we dat twee stelsels lineaire vergelijkingen die elementaire herleidingen van elkaar zijn, dezelfde oplossing hebben. Elementaire bewerkingen veranderen de (on)afhankelijkheid van de rijen van een matrix dus niet.
Later zullen we zien dat elementaire bewerkingen ook de (on)afhankelijkheid van de kolommen van een matrix niet veranderen.
Rijreductie van een matrix
