Sbírka řešených úloh

Odstupňovaný tvar, Gaussova eliminace

Úloha číslo: 1326

• Teoretický základ

• Řádkově odstupňovaný tvar matice a bázové sloupce

  (i) Řádkově odstupňovaná matice

  Matice \(A=(a_{ij})_{m \times n}\) se nazývá řádkově odstupňovaná, jestliže pro její prvky platí

  1. Je-li \( m > 1 \), pak \( a_{21}=0\)

  2. Jestliže pro nějaké \(i \in \left\{ 1,\dots , m-1\right\}\) a \(k \in \left\{ 1,\dots , n-1\right\}\) je

     \[a_{i,1}=a_{i,2}=\dots=a_{i,k}=0,\]

     potom je také

     \[a_{i+1{,}1}=a_{i+1{,}2}=\dots=a_{i+1,k+1}=0.\]

  V řádkově odstupňované matici tedy začíná každý nenulový řádek větším počtem nul, než řádek předchozí (pokud tento existuje).

  První podmínka říká, že druhý řádek (pokud existuje) začíná alespoň jednou nulou. Třetí řádek tedy začíná alespoň dvěma nulami a obecně \(i\)-tý řádek alespoň \((i-1)\) nulami. Snadno usoudíme, že hodnost odstupňované matice je rovna počtu jejích nenulových řádků, právě tolik lineárně nezávislých řádků totiž můžeme v matici najít.

  Pro matici \(A\) můžeme dostat například řádkově odstupňovaný tvar

  \[A= \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \end{pmatrix} \ \overset{\mathrm{G.e.}}{\sim} \ \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & 4 & 3 \end{pmatrix}. \]

  (ii) Bázové sloupce

  Je-li matice v řádkově odstupňovaném tvaru, pak bázovými sloupci rozumíme první nenulový sloupec a dále ty sloupce matice, které začínají větším počtem nul než sloupce předchozí.

  Hodnost matice nemusíme určovat pouze jako počet nenulových řádků v řádkově odstupňovaném tvaru, neboť platí následující věta.

  (iii) Hodnost pomocí bázových sloupců

  Počet bázových sloupců matice v řádkově odstupňovaném tvaru udává rovněž hodnost matice.

  V odstupňovaném tvaru matice \(A\) jsou bázovými sloupci první až čtvrtý sloupec.

• Gaussův eliminační algoritmus (metoda)

  (iv) Gaussova eliminace

  Gaussovou eliminací rozumíme algoritmus (postup), kterým zadanou matici \(A=(a_{ij})_{m \times n}\) pomocí řádkových úprav převádíme do řádkově odstupňovaného tvaru.

  Nyní si ukažme algoritmus, který na odstupňovaný tvar vede.

  (v) Gaussův eliminační algoritmus

  Řádkově odstupňovaný tvar matice \(A=(a_{ij})_{m \times n}\) získáme následovně.

  Nechť \(j=1\) a \(k=1\) jsou počáteční hodnoty.

  1. V \(j\)-tém sloupci hledejte od \(i=k\) do \(i=m\) první nenulový prvek. Najdete-li jej, fixujte \(i\) a pokračujte krokem 2. V opačném případě přiřaďte \(j\) hodnotu \(j+1\). Pokud je nyní \(j\) rovno \(n\), algoritmus ukončete, jinak pokračujte krokem 1.

  2. Prohoďte \(i\)-tý a \(k\)-tý řádek, poté pomocí nově přiřazeného \(k\)-tého řádku za pomoci 3. řádkové úpravy vynulujte prvky na pozicích \(kj\) až \(mj\) a nakonec přiřaďte \(k\) hodnotu \(k+1\) pro další postup a \(j\) hodnotu \(j+1\). Pokud je nyní \(k=m\) nebo \(j=n\), algoritmus ukončete, jinak pokračujte krokem 1.

  Pozor, v průběhu vždy zkoumáme prvek na pozici \(a_{ij}\)!

• Řádkové úpravy

  Nechť \(A=(a_{ij})_{m \times n}\) je matice nad okruhem \(M\), pak řádkovými úpravami rozumíme:

  1. Prohození \(i\)-tého a \(j\)-tého řádku, čemuž odpovídá přenásobení matice \(A\) zleva elementární transformační maticí řádu \(n\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,n} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 0_{i,i} & \cdots & 1_{i,j} & \cdots & 0_{i,n}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 1_{j,i} & \cdots & 0_{j,j} & \cdots & 0_{j,n} \\ \vdots & & & & & \ddots & \vdots \\ 0_{n,1} & \cdots & 0_{n,i} & \cdots & 0_{n,j} & \cdots & 1_{n,n} \end{pmatrix}.\]
  2. Přičtení \(j\)-tého k \(i\)-tému řádku, čemuž odpovídá přenásobení matice \(A\) zleva elementární transformační maticí řádu \(n\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,n} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 1_{i,i} & \cdots & 1_{i,j} & \cdots & 0_{i,n}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 0_{j,i} & \cdots & 1_{j,j} & \cdots & 0_{j,n} \\ \vdots & & & & & \ddots & \vdots \\ 0_{n,1} & \cdots & 0_{n,i} & \cdots & 0_{n,j} & \cdots & 1_{n,n} \end{pmatrix}.\]
  3. Přičtení \(a\)-násobku \(j\)-tého k \(i\)-tému řádku, kde \(a\) je prvkem okruhu \(M\), čemuž odpovídá přenásobení matice \(A\) zleva elementární transformační maticí řádu \(n\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,n} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 1_{i,i} & \cdots & a_{i,j} & \cdots & 0_{i,n}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 0_{j,i} & \cdots & 1_{j,j} & \cdots & 0_{j,n} \\ \vdots & & & & & \ddots & \vdots \\ 0_{n,1} & \cdots & 0_{n,i} & \cdots & 0_{n,j} & \cdots & 1_{n,n} \end{pmatrix}.\]

  Řádkové úpravy nemění hodnost matice!

• Sloupcové úpravy

  Nechť \(A=(a_{ij})_{m \times n}\) je matice nad okruhem \(M\), pak sloupcovými úpravami rozumíme:

  1. Prohození \(i\)-tého a \(j\)-tého sloupce, čemuž odpovídá přenásobení matice \(A\) zprava elementární transformační maticí řádu \(m\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,m} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 0_{i,i} & \cdots & 1_{i,j} & \cdots & 0_{i,m}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 1_{j,i} & \cdots & 0_{j,j} & \cdots & 0_{j,m} \\ \vdots & & & & & \ddots & \vdots \\ 0_{m,1} & \cdots & 0_{m,i} & \cdots & 0_{m,j} & \cdots & 1_{m,m} \end{pmatrix}.\]
  2. Přičtení \(j\)-tého k \(i\)-tému sloupci, čemuž odpovídá přenásobení matice \(A\) zprava elementární transformační maticí řádu \(m\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,m} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 1_{i,i} & \cdots & 1_{i,j} & \cdots & 0_{i,m}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 0_{j,i} & \cdots & 1_{j,j} & \cdots & 0_{j,m} \\ \vdots & & & & & \ddots & \vdots \\ 0_{m,1} & \cdots & 0_{m,i} & \cdots & 0_{m,j} & \cdots & 1_{m,m} \end{pmatrix}.\]
  3. Přičtení \(a\)-násobku \(j\)-tého k \(i\)-tému sloupci, kde \(a\) je prvkem okruhu \(M\), čemuž odpovídá přenásobení matice \(A\) zprava elementární transformační maticí řádu \(m\) ve tvaru \[ \begin{pmatrix} 1_{1{,}1} & \cdots & 0_{1,i} & \cdots & 0_{1,j} & \cdots & 0_{1,m} \\ \vdots & \ddots & & & & & \vdots \\ 0_{i,1} & \cdots & 1_{i,i} & \cdots & a_{i,j} & \cdots & 0_{i,m}\\ \vdots & & & \ddots & & &\vdots \\ 0_{j,1} & \cdots & 0_{j,i} & \cdots & 1_{j,j} & \cdots & 0_{j,m} \\ \vdots & & & & & \ddots & \vdots \\ 0_{m,1} & \cdots & 0_{m,i} & \cdots & 0_{m,j} & \cdots & 1_{m,m} \end{pmatrix}.\]

  Sloupcové úpravy nemění hodnost matice!

• CELKOVÉ ŘEŠENÍ

  Matici

  \[A= \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \\ \end{pmatrix} \]

  upravíme nad \(\mathbb{Z}_5\) pomocí Gaussova algoritmu na řádkově odstupňovaný tvar.

  ---

  Volíme \(k=1\), \(j=1\).

  V \(j\)-tém sloupci, tedy prvním, se podíváme na prvek na \(k\)-té řádkové souřadnici, v tomto případě na první. Tento prvek je nenulový, fixujeme tedy \(i=1\) a pokračujeme krokem 2.

  Prohazujeme \(k\)-tý a \(i\)-tý řádek – v našem případě první s prvním, takže neprovadíme žádnou úpravu. Této úpravě odpovídá přenásobení matice \(A\) zleva transformační maticí \(T_1\), která je jednotková.

  \[A_1= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \end{pmatrix} \]

  Nyní užijeme 3. řádkové úpravy. Tedy přičítáním násobků \(k\)-tého řádku vynulujeme v \(j\)-tém sloupci prvky s řádkovým indexem \(k+1\) až \(m\).

  Pro aktuální hodnoty \(j,k\) to znamená: Přičítáním násobků prvního řádku vynulujeme v prvním sloupci prvky s řádkovým indexem 2 až 4.

  \[ A_1 = \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \end{pmatrix} \begin{array}{l} \phantom{I}\\ II + 4I \\ III + I \\ IV + 3I \\ \end{array} \sim \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \end{pmatrix} =A_2 \]

  V řeči transformačních matic jsme právě provedli pronásobení matice \(A_1\) zleva součinem

  \[ T_4 T_3 T_2 = \left(\begin{smallmatrix} 1 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{smallmatrix}\right) \left(\begin{smallmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1& 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{smallmatrix}\right) \left(\begin{smallmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \end{smallmatrix}\right), \]

  čímž jsme dostali matici \(A_2\).

  Nakonec přiřadíme \(j\) hodnotu \(j+1\) a \(k\) hodnotu \(k+1\). Pro aktuální hodnoty \(j,k\) to znamená, že proměnným \(j,k\) přiřadíme hodnotu \(2\). Protože současné \(k\) i \(j\) dosud nepřekračuje maximální stanovenou hodnotu, pokračujeme krokem 1.

  V \(j\)-tém sloupci, tedy druhém, se podívám na prvek na \(k\)-té řádkové souřadnici, v tomto případě na druhé.

  Protože je tento prvek nulový, podíváme se na prvek na \(k+1\) pozici, v tomto případě na třetím řádku. Ten shledáváme také nulovým, proto \(i\) zvyšujeme na \(4\).

  Prvek na čtvrtém řádku (\(k+2\)) je již nenulový, proto \(i\) fixujeme jako \(4\) a pokračujeme krokem 2.

  Prohazujeme \(k\)-tý a \(i\)-tý řádek – v našem případě druhý se čtvrtým.

  \[A_2= \begin{array}{l} \phantom{I}\\ \downarrow \\ \phantom{III}\\ \uparrow \\ \end{array} \hspace{-0.9em} \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \end{pmatrix} \begin{array}{l} \phantom{I}\\ \downarrow \\ \phantom{III}\\ \uparrow \\ \end{array} \sim \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \end{pmatrix} = A_3 \]

  Provedené úpravě odpovídá přenásobení matice \(A_2\) zleva maticí \[T_5= \left(\begin{smallmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{smallmatrix}\right). \]

  Nyní užijeme 3. řádkové úpravy. Tedy přičítáním násobků \(k\)-tého řádku vynulujeme v \(j\)-tém sloupci prvky s řádkovým indexem \(k+1\) až \(m\).

  Pro aktuální hodnoty \(j,k\) to znamená: Přičítáním násobků druhého řádku vynulujeme v druhém sloupci prvky s řádkovým indexem 3 a 4.

  \[ A_3 = \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \end{pmatrix} \begin{array}{l} \phantom{I}\\ \phantom{II} \\ III + 0II\\ IV + 0II\\ \end{array} \sim \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \end{pmatrix} = A_4 \] Těmto „úpravám“ odpovídá přenásobení matice \(A_3\) zleva jednotkovými maticemi.

  Nakonec přiřadíme \(j\) hodnotu \(j+1\) a \(k\) hodnotu \(k+1\). Pro aktuální hodnoty \(j,k\) to znamená, že proměnným \(j,k\) přiřadíme hodnotu \(3\). Protože současné \(k\) i \(j\) dosud nepřekračuje maximální stanovenou hodnotu, pokračujeme krokem 1.

  V \(j\)-tém sloupci, tedy třetím, se podíváme na prvek na \(k\)-té řádkové souřadnici, v tomto případě na třetí.

  Protože je tento prvek nenulový, \(i\) fixujeme jako \(3\) a pokračujeme krokem 2.

  Prohazujeme \(k\)-tý a \(i\)-tý řádek – v našem případě třetí s třetím, takže vlastně neděláme žádnou úpravu.

  Této „úpravě“ odpovídá přenásobení matice \(A_4\) zleva jednotkovou maticí, čímž získáme opět matici \(A_4\).

  Nyní užijeme 3. řádkové úpravy. Tedy přičítáním násobků \(k\)-tého řádku vynulujeme v \(j\)-tém sloupci prvky s řádkovým indexem \(k+1\) až \(m\).

  Pro aktuální hodnoty \(j,k\) to znamená: Přičítáním násobků třetího řádku vynulujeme v třetím sloupci prvky s řádkovým indexem \(4\).

  \[ A_4 = \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 4 & 1 & 1 & 4 \end{pmatrix} \begin{array}{l} \phantom{I} \\ \phantom{II} \\ \phantom{III}\\ IV + 4III \\ \end{array} \sim \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 3 \end{pmatrix} =A_5 \] Provedené úpravě odpovídá pronásobení matice \(A_4\) zleva transformační maticí \[T_6 = \left(\begin{smallmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 4 & 1 \end{smallmatrix}\right). \]

  Nakonec přiřadíme \(j\) hodnotu \(j+1\) a \(k\) hodnotu \(k+1\). Pro aktuální hodnoty \(j,k\) to znamená, že proměnným \(j,k\) přiřadíme hodnotu \(4\). Protože současné \(k\) i \(j\) dosáhlo maximální hodnoty počtu řádků \(m=4\), algoritmus ukončujeme.

  Na výstupu máme matici v řádkově odstupňovaném tvaru

  \[A_V = A_5=\begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 3 \end{pmatrix}. \]

  Bázovými sloupci jsou první čtyři sloupce.

  Řádkové úpravy jsou zaznamenány v transformační čtvercové matici \(T\) řádu \(4\), která je dána součinem dílčích transformačních matic

  \[T=T_1 \cdot \dots \cdot T_6 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 3 & 1 & 4 & 0 \end{pmatrix}.\]

  Výsledný odstupňovaný tvar Gaussovy eliminace můžeme vyjádřit součinem transformační matice \(T\) a původní matice \(A\)

  \[A_V = T\cdot A=\] \[=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 3 & 1 & 4 & 0 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 1 & 2 & 2 & 1 & 3 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 0 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 3 \end{pmatrix}. \]

• Odpověď

  Řádkově odstupňovaný tvar matice je například \[ \begin{pmatrix} 1 & 2 & 3 & 0 & 2 & 1 \\ 0 & 2 & 0 & 2 & 1 & 0 \\ 0 & 0 & 4 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 3 \end{pmatrix}. \]