Redukcja wierszowa macierzy

Definicja (#) Dwa układy $ m $ równań z $ n $ niewiadomymi nazywamy równoważnymi jeśli mają taki sam zbiór rozwiązań (w szczególności, jeśli oba są sprzeczne).

Opiszemy teraz trzy operacje na układach równań, które nie zmieniają zbioru rozwiązań i pozwalają zastąpić dany układ równań układem równoważnym o przejrzystej, ``schodkowej'' strukturze:

(I)$ _{a(i)+(k)} $    dodanie do $ k $-tego równania $ i $-tego równania pomnożonego przez $ a $,

(II)$ _{(i)(k)} $    zamiana miejscami $ i $-tego równania z $ k $-tym,

(III)$ _{c(i)} $    pomnożenie $ i $-tego równania przez liczbę $ c\neq 0 $.

Twierdzenie (#) Wykonanie na układzie równań liniowych jednej z wymienionych wyżej operacji nie zmienia zbioru rozwiązań tego układu.
Dowód: Teza jest oczywista dla operacji typu (II) i (III). Rozpatrzmy operację (I)$ _{a(i)+(k)} $ przeprowadzającą układ ($ \ast $) na układ $ (\ast)' $, w którym zmienia się jedynie $ k $-te równanie, otrzymane w wyniku dodania stronami do $ k $-tego równania układu $ (\ast) $ równania $ i $-tego, obustronnie pomnożonego przez $ a $.

Jest jasne, że każde rozwiązanie układu ($ \ast $) jest także rozwiązaniem układu $ (\ast)' $. Ponieważ operacja (I)$ _{(-a)(i)+(k)} $ (odwrotna do (I)$ _{a(i)+(k)} $) przeprowadza układ $ (\ast)' $ na układ $ (\ast) $, także rozwiązania układu $ (\ast)' $ są rozwiązaniami $ (\ast) $. To pokazuje równoważność obu układów. □

Przy takich przekształceniach układu równań $ AX=B $, celowe jest pomijanie zmiennych i wykonywanie operacji na wierszach {\em macierzy rozszerzonej} tego układu

$$[A|B]=[A_1,\ldots,A_n|B],$$

gdzie $ A_j $ są kolejnymi kolumnami macierzy $ A $, $ B $ jest dopisaną jako ostatnia kolumną wyrazów wolnych, a kreska oddzielająca $ B $ od poprzednich kolumn nie ma formalnego znaczenia i ma jedynie przypominać, że przy przejściu do układu równań, rola ostatniej kolumny jest inna niż pozostałych.

Operacjom na układach równań odpowiadają następujące {\em operacje elementarne na wierszach macierzy}:

(I)$ _{a(i)+(k)} $    dodanie do $ k $-tego wiersza $ i $-tego pomnożonego przez $ a $,

(II)$ _{(i)(k)} $    zamiana miejscami $ i $-tego wiersza z $ k $-tym,

(III)$ _{c(i)} $    pomnożenie $ i $-tego wiersza przez liczbę $ c\neq 0 $.

Opiszemy teraz pewne macierze o szczególnie prostej postaci i pokażemy, że każdą macierz można sprowadzić do macierzy takiej postaci operacjami typu (I) i (II), zob.\ Uwagę [link].

Definicja (#) Mówimy, że macierz jest w postaci schodkowej jeśli spełnione są dwa warunki:

     {(S1)}\ \ żaden wiersz zerowy tej macierzy nie poprzedza wiersza niezerowego,

     {(S2)}\ \ pierwsze niezerowe wyrazy (schodki) kolejnych niezerowych wierszy tej macierzy stoją w kolumnach o rosnących numerach.

Twierdzenie (#) Dowolną macierz można sprowadzić do postaci schodkowej operacjami elementarnymi typu {\em(I)} i {\em(II)} na wierszach tej macierzy.
Dowód: Niech $ A $ będzie $ (m\times n) $-macierzą mającą niezerowe wyrazy i niech $ j_1 $ będzie numerem pierwszej niezerowej kolumny $ A $. Zamieniając w razie potrzeby wiersze macierzy $ A $ miejscami (operacja typu (II)) można otrzymać macierz $ \widetilde{A} $ mającą niezerowy wyraz $ a_{1j_{1}} $ w pierwszym wierszu kolumny o numerze $ j_{1} $:

$$\widetilde{A} = \left[\begin{array}{rcrcrcc} 0&\ldots&0&a_{1j_{1}}&\ldots&a_{1n}\\ 0&\ldots&0&a_{2j_{1}}&\ldots&a_{2n}\\\vdots &  &\vdots &\vdots &  & \vdots\\ 0&\ldots&0&a_{mj_{1}}&\ldots&a_{mn}\\\end{array}\right].$$

Odejmując kolejno, dla $ i = 2,3,\ldots ,m $, od $ i $-tego wiersza macierzy $ \widetilde{A} $ pierwszy wiersz pomnożony przez $ a_i=\frac{a_{i j_{1}}}{a_{1j_{1}}} $ (czyli wykonując operację

(I)$ _{(-a_i)(1)+(i)} $) otrzymujemy macierz $ A' $, w której kolumny o numerach mniejszych niż $ j_{1} $ są zerowe, a jedynym niezerowym wyrazem w kolumnie o numerze $ j_{1} $ jest $ a_{1j_{1}} $:

$$A'= \left[\begin{array}{rcrccrc}  0&\ldots &0&a_{1j_{1}}&a_{1j_{1}+1}&\ldots&a_{1n}\\  0&\ldots&0&0&a_{2j_{1}+1}'&\ldots&a_{2n}'\\  \vdots &  &\vdots &\vdots&\vdots &  & \vdots \\  0&\ldots&0&0&a_{mj_{1}+1}'&\ldots&a_{mn}'\\  \end{array}\right].$$

W następnym kroku powtarzamy tę procedurę dla macierzy $ A' $ ignorując wyrazy pierwszego wiersza tej macierzy. Znajdujemy $ j_2>j_1 $ i macierz $ A''\in\M{m}{n}{\R} $ (pierwszy wiersz $ A'' $ jest taki jak pierwszy wiersz $ A' $) taką, że wyraz drugiego wiersza kolumny o numerze $ j_2 $ jest niezerowy, a wszystkie wyrazy pod nim oraz wyrazy z wcześniejszych kolumn (z wyjątkiem ignorowanych wyrazów pierwszego wiersza) są zerowe.

Po kolejnych analogicznych krokach dochodzimy do $ (m\times n) $-macierzy $ A^{(r)} $ w postaci schodkowej mającej w $ r $ niezerowych wierszach pierwsze niezerowe wyrazy (schodki) w kolumnach o numerach $ j_1<\ldots<j_r $. □

Uwaga (#) W twierdzeniu [link] można ograniczyć się do operacji typu (I). Operację (II)$ _{(1)(i)} $, którą stosowaliśmy przy przejściu od $ A $ do $ \widetilde{A} $ w przypadku, gdy w kolumnie o numerze $ j_1 $ pierwszy wyraz jest zerowy, a $ i $-ty różny od zera, można zastąpić operacją (I)$ _{1(i)+(1)} $. Analogicznie można postępować w kolejnych krokach.