Rivimuunnokset ja redusoitu riviporrasmuoto¶

Kun yhtälöryhmä voidaan nyt kirjoittaa lyhyemmin kokonaismatriisin avulla, ryhdytään kehittämään tätä esitystä hyödyntävää systemaattista ratkaisumenetelmää. Ratkaisun etsiminen on erityisen helppoa silloin, kun yhtälöryhmä ja vastaava kokonaismatriisi ovat

$\begin{split}\begin{cases} x_1 = c_1 \\ x_2 = c_2 \\ \phantom{x_3\ } \vdots \\ x_n = c_n \end{cases} \qquad\text{ja}\qquad \begin{bmatrix} 1 & 0 & \cdots & 0 & c_1 \\ 0 & 1 & \cdots & 0 & c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_n \end{bmatrix}.\end{split}$

Läheskään aina näin yksinkertaiseen tapaukseen ei päästä, mutta sitä voidaan imitoida mahdollisimman tarkasti.

Määritelmä.

Kutsutaan matriisin rivin vasemmalta luettuna ensimmäistä nollasta poikkeavaa alkiota johtavaksi alkioksi. Matriisi on redusoidussa riviporrasmuodossa (reduced row echelon form, rref), jos

vain nollia sisältävät rivit ovat alimmaisina,
jokaisen nollasta poikkeavan rivin johtava alkio on edeltävän rivin johtavan alkion oikealla puolella,
jokainen johtava alkio on $1$ (johtava ykkönen),
jokaisen johtavan ykkösen ylä- ja alapuolella samassa sarakkeessa on vain nollia.

Esimerkki.

Matriisit

$\begin{split}\begin{bmatrix} 1 & 2 & 0\\ 0 & 0 & 1 \end{bmatrix},\qquad \begin{bmatrix} 1 & 0 & -3\\ 0 & 1 & 1\\ 0 & 0 & 0 \end{bmatrix},\qquad \begin{bmatrix} 1 & 2 & 0 &0\\ 0 & 0 & 1&0\\ 0 & 0 & 0 &1\\ \end{bmatrix}\qquad\text{ja}\qquad \begin{bmatrix} 1 & 2 & 0 &1&0&2\\ 0 & 0 & 1&-2&0&-3\\ 0 & 0 & 0 &0&1&1\\ 0 & 0 & 0 &0&0&0\\ \end{bmatrix}\end{split}$

ovat redusoidussa riviporrasmuodossa, mutta

$\begin{split}\begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 1 \end{bmatrix},\qquad \begin{bmatrix} 1 & 0 & -3\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix},\qquad \begin{bmatrix} 1 & 2 & 1 &0\\ 0 & 0 & 1&0\\ 0 & 0 & 0 &1\\ \end{bmatrix}\qquad\text{ja}\qquad \begin{bmatrix} 1 & 2 & 0 &1&1&2\\ 0 & 0 & 1&-2&0&-3\\ 0 & 0 & 0 &0&1&1\\ 0 & 0 & 0 &0&0&0\\ \end{bmatrix}\end{split}$

eivät ole, sillä niissä on nollasta poikkeavia alkioita johtavien ykkösten sarakkeissa.

Jos kokonaismatriisi on esitetty redusoidussa riviporrasmuodossa, niin vastaavan yhtälöryhmän yleinen ratkaisu voidaan lukea suoraan siitä. Yhtälöryhmä on siis ratkaistu, jos sen kokonaismatriisi osataan muuntaa redusoituun riviporrasmuotoon. Kuten edellä tehtiin yhtälöryhmälle, myös matriiseille löydetään rivimuunnoksia.

Määritelmä.

Matriiseille määritellään seuraavat rivimuunnokset ja niiden merkintätavat.

Rivit $i$ ja $j$ vaihdetaan keskenään, $R_i \leftrightarrow R_j$ .
Rivin $i$ alkiot kerrotaan vakiolla $k \not= 0$ , $kR_i$ .
Riviin $i$ lisätään vakiolla $k$ kerrottu rivi $j$ , $R_i+kR_j$ .

Jos matriisiin $A$ sovelletaan rivimuunnosta $Q$ ja tuloksena saadaan matriisi $B$ , niin kirjoitetaan

$A \xrightarrow{Q} B.$

Tärkeä rivimuunnosten ominaisuus on, että ne ovat kääntyviä. Jos matriisille $A$ tehtiin muunnos $Q$ , niin aina löydetään käänteismuunnos $Q^{-1}$ , jolla päädytään takaisin matriisiin $A$ . Rivien vaihto on oma käänteismuunnoksensa, eli

$A \xrightarrow{R_i \leftrightarrow R_j} B \xrightarrow{R_i \leftrightarrow R_j} A.$

Kertominen nollasta poikkeavalla vakiolla voidaan puolestaan kääntää kertomalla samaa riviä käänteisluvulla, eli

$A \xrightarrow{kR_i} B \xrightarrow{\frac{1}{k}R_i} A,$

ja vakiolla kerrottu rivi voidaan vähentää alkuperäisen palauttamiseksi, eli

$A \xrightarrow{R_i + kR_j} B \xrightarrow{R_i - kR_j} A.$

Matriiseja voidaan luokitella rivimuunnosten avulla.

Määritelmä.

Matriisit $A$ ja $B$ ovat riviekvivalentteja, jos löydetään sellainen rivimuunnosten jono $Q_1,Q_2,\ldots,Q_k$ , että

$A \xrightarrow{Q_1} A_1 \xrightarrow{Q_2} \cdots \xrightarrow{Q_k} A_k = B, \qquad\text{eli}\qquad A \xrightarrow{Q_1, Q_2, \ldots, Q_k} B.$

Esimerkki.

Osoita matriisit $\begin{bmatrix} 1 & 2 & -1\\ 0 & -2 & 3\\ 0 & 3 & 3 \end{bmatrix}$ ja $\begin{bmatrix} 1 & 0 & 2\\ 1 & 0 & -3\\ 0 & 1 & 1 \end{bmatrix}$ riviekvivalenteiksi.

Ratkaisu.

Suoralla laskulla nähdään, että

$\begin{split}\begin{aligned} \begin{bmatrix} 1 & 2 & -1\\ 0 & -2 & 3\\ 0 & 3 & 3 \end{bmatrix} &\xrightarrow{R_2 + R_1} \begin{bmatrix} 1 & 2 & -1\\ 1 & 0 & 2\\ 0 & 3 & 3 \end{bmatrix} \xrightarrow{\frac{1}{3}R_3} \begin{bmatrix} 1 & 2 & -1\\ 1 & 0 & 2\\ 0 & 1 & 1 \end{bmatrix} \xrightarrow{R_1 - 2R_3} \begin{bmatrix} 1 & 0 & -3\\ 1 & 0 & 2\\ 0 & 1 & 1 \end{bmatrix} \\ &\xrightarrow{R_1 \leftrightarrow R_2} \begin{bmatrix} 1 & 0 & 2\\ 1 & 0 & -3\\ 0 & 1 & 1 \end{bmatrix},\end{aligned}\end{split}$

joten matriisit ovat riviekvivalentteja. Huomaa, että löytyy muitakin rivimuunnosten yhdistelmiä, jotka tuottavat saman tuloksen.

Huomautus.

Kaksi yhtälöryhmää ovat ekvivalentteja täsmälleen silloin, kun niiden kokonaismatriisit ovat riviekvivalentteja.

Tähän asti on siis tunnistettu, että tietynlaisesta kokonaismatriisista on erityisen helppo lukea yhtälöryhmän ratkaisu, ja että matriiseillekin voidaan soveltaa rivimuunnoksia. Seuraava todistamatta käyttöön otettava keskeinen tulos yhdistää nämä kaksi lankaa.

Lause.

Matriisia $A$ kohti löydetään toinen, yksikäsitteinen matriisi $B$ , jolle

$A$ ja $B$ ovat riviekvivalentteja,
$B$ on redusoidussa riviporrasmuodossa.

Jokainen matriisi voidaan siis muuntaa rivimuunnosten avulla redusoituun riviporrasmuotoon. Matriisin $A$ redusoitua riviporrasmuotoa merkitään $\operatorname{rref}(A)$ , ja lukemisen helpottamiseksi kokonaismatriisin $[A\mid\mathbf{b}]$ redusoitua riviporrasmuotoa merkitään myös $\operatorname{rref}[A\mid\mathbf{b}]$ . Koska $[A\mid\mathbf{b}]$ ja $\operatorname{rref}[A\mid\mathbf{b}]$ ovat riviekvivalentteja, niitä vastaavat yhtälöryhmät ovat ekvivalentteja.

Lause.

Matriisit $A$ ja $B$ ovat riviekvivalentteja, jos ja vain jos $\operatorname{rref}(A) = \operatorname{rref}(B)$ .

Todistus.

Oletetaan ensin, että matriisit $A$ ja $B$ ovat riviekvivalentteja, eli löydetään alkeisrivioperaatiot $Q_1,\ldots,Q_k$ , joilla matriisista $A$ saadaan $B$ . Oletetaan lisäksi, että $B$ voidaan muuntaa redusoituun riviporrasmuotoon rivimuunnoksilla $T_1,\ldots,T_l$ . Tällöin $A$ voidaan muuntaa samaan riviporrasmuotoon yhdistämällä edelliset, eli

$A \xrightarrow{Q_1, \ldots, Q_k} B \xrightarrow{T_1, \ldots, T_l} \operatorname{rref}(B) = \operatorname{rref}(A),$

missä yhtäsuuruus seuraa edellisestä lauseesta.

Oletetaan sitten, että $\operatorname{rref}(A) = \operatorname{rref}(B) = R$ . Tällöin siis löydetään rivimuunnokset $S_1,\ldots,S_m$ , joilla matriisista $A$ saadaan $R$ , ja vastaavasti rivimuunnokset $P_1,\ldots,P_n$ , joilla matriisista $B$ saadaan $R$ . Rivimuunnokset ovat aina kääntyviä, joten suorittamalla käänteismuunnokset käänteisessä järjestyksessä on mahdollista muuntaa $A$ ensin riviporrasmuotoon $R$ , ja siitä matriisiksi $B$ .

$A \xrightarrow{S_1, \ldots, S_m} R \xrightarrow{P_n^{-1}, \ldots, P_1^{-1}} B$

Täten $A$ ja $B$ ovat riviekvivalentteja. $\square$

Edellinen lause kertoo erityisesti sen, että yhtälöryhmä voidaan muodostaa monella eri tavalla muuttamatta ratkaisua.

Esimerkki.

Määritä edellisen esimerkin matriisien redusoidut riviporrasmuodot.

Ratkaisu.

Aiemmin osoitettiin, että matriisit ovat riviekvivalentteja, ja täten riittää määrittää jomman kumman redusoitu riviporrasmuoto. Esimerkiksi jälkimmäiselle matriisille

$\begin{split}\begin{aligned} \begin{bmatrix} 1 & 0 & 2\\ 1 & 0 & -3\\ 0 & 1 & 1 \end{bmatrix} &\xrightarrow{R_2 - R_1} \begin{bmatrix} 1 & 0 & 2\\ 0 & 0 & -5\\ 0 & 1 & 1 \end{bmatrix} \xrightarrow{R_2 \leftrightarrow R_3} \begin{bmatrix} 1 & 0 & 2\\ 0 & 1 & 1\\ 0 & 0 & -5 \end{bmatrix} \xrightarrow{-\frac{1}{5}R_3} \begin{bmatrix} 1 & 0 & 2\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix}\\ &\xrightarrow{R_1 - 2R_3} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{R_2 - R_3} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix},\end{aligned}\end{split}$

joten molempien matriisien redusoitu riviporrasmuoto on yksikkömatriisi $I_3$ .