Metoda opearacji elementarnych
c
G.Cieciura
0.1 Macierze
De nicja
. Niech
Z b¦dzie zbiorem, a m;n | liczbami naturalnymi; zwykle
w tym kontek±cie
Z =
K
jest ciaªem.
Macierz¡
wymiaru
m
n o
wyrazach
ze zbioru
Z nazywa si¦ ukªad mn elementów A
ij
zbioru
Z, indeksowanych
dwoma wska¹nikami:
i
2
1
;m, j
2
1
;n. Do oznaczania macierzy u»ywa¢
b¦dziemy zwykle liter wytªuszczonych, pisz¡c
A
= [
A
ij
]
(
i;j
)21
;m
1
;n
b¡d¹ te»,
w bardziej rozwini¦tej lecz obrazowej postaci,
A
=
2
6
6
6
6
4
A
1
1
A
1
2
::: A
1
n
A
2
1
A
2
2
::: A
2
n
... ...
...
A
m
1
A
m
2
::: A
mn
3
7
7
7
7
5
.
Ta ostatnia konwencja uzasadnia nazywanie wska¹ników i;j numerami
wiersza
i
kolumny
wyrazu A
ij
, za± liczb m;n |
liczb¡ wierszy i kolumn
macierzy(
1
).
Przykªad
. Je±li
A
=
2
1 1
3 0 4
, to
m = 2; n = 3; A
1
1
= 2; A
1
2
= 1
A
1
3
= 1; A
2
1
= 3; A
2
2
= 0; A
2
3
= 4
.
Uw
aga
. Spotyka si¦ cz¦sto tak»e dwie inne konwencje zwi¡zane z macierzami: niektórzy
zamiast A
ij
wol¡ pisa¢ A
i;j
(lub A
ij
, pami¦taj¡c, »e ij jest tu uproszczon¡ form¡ zapisu
pary (i;j), a nie iloczynem); inni z kolei wol¡ zapis A
ij
. Nasza notacja ma t¦ zalet¦, »e po jej
przyswojeniu ªatwo si¦ przestawi¢ na ka»d¡ z dwu pozostaªych, np. A
3
4
= A
3
4
, A
3
;
1
= A
3
1
.
Oznaczenia
. Dla
m;n
2
N
symbol
K
m
n
oznacza zbiór wszystkich macierzy
wymiaru
m
n (tzn. maj¡cych m wierszy i n kolumn) o wyrazach z
K
. Je±li
A
2
K
m
n
, to wektory
A
1
;:::;
A
m
s¡ kolejnymi wierszami, natomiast wektory
A
1
;:::;
A
n
| kolumnami macierzy
A
. Np. je±li
A
=
"
1 3 2
7 4 5
#
2
R
2
3
, to
A
1
= [1
;3; 2],
A
2
= [7
; 4;5],
A
1
=
"
1
7
#
,
A
2
=
"
3
4
#
,
A
3
=
"
2
5
#
.
Oznaczmy dla skrótu
K
n
:=
K
1
n
,
K
m
:=
K
m
1
, wtedy w ogólnym przypadku
A
i
= [
A
i
1
;:::;A
in
]
2
K
n
(
2
)
oraz
A
j
=
2
6
6
4
A
1
j
...
A
mj
3
7
7
5
2
K
m
.
1
Mówi¡c ±ci±lej macierz
A
jest odwzorowaniem (i;j)
7!
A
ij
zbioru 1;m
1;n w zbiór
Z; element A
ij
2
Z, zwany (i;j)-wyrazem macierzy
A
, jest warto±ci¡ tego odwzorowania
w punkcie (i;j) jego dziedziny. Jak si¦ przekonamy, oznaczanie (i;j)-wyrazu symbolem
A
(i;j) (zamiast A
ij
) byªoby mniej por¦czne i mogªo by prowadzi¢ do niejasno±ci.
2
Piszemy [A
1
;:::;A
n
] zamiast
A
1
::: A
n
, by wyra¹niej wyodr¦bni¢ wyrazy;
niektórzy lubi¡ rozdziela¢ przecinkami tak»e wyrazy macierzy wielowierszowych.
1
Operacje algebraiczne na macierzach
K
m
n
jest przypadkiem szczególnym zbioru
K
X
wszystkich funkcji
X
!
K
,
mianowicie dla
X := 1;m
1
;n. Zatem mo»emy w tym zbiorze `w zwyczajny
sposób' (jak dla funkcji) okre±li¢ operacje dodawania i mno»enia przez liczby:
A
+
B
:= [
A
ij
+
B
ij
]
(
i;j
)2
X
,
tzn.
A
+
B
=
C
def
(
)
8
(
i;j)
2
X : C
ij
=
A
ij
+
B
ij
,
czyli
2
6
6
4
A
1
1
::: A
1
n
...
...
A
m
1
::: A
mn
3
7
7
5
+
2
6
6
4
B
1
1
::: B
1
n
...
...
B
m
1
::: B
mn
3
7
7
5
:=
2
6
6
4
A
1
1
+
B
1
1
::: A
1
n
+
B
1
n
...
...
A
m
1
+
B
m
1
::: A
mn
+
B
mn
3
7
7
5
;
A
:= [
A
ij
]
(
i;j
)2
X
, tzn.
2
6
6
4
A
1
1
::: A
1
n
...
...
A
m
1
::: A
mn
3
7
7
5
:=
2
6
6
4
A
1
1
::: A
1
n
...
...
A
m
1
::: A
mn
3
7
7
5
.
Jak wiemy,
K
mn
z tak okre±lonymi dziaªaniami stanowi przestrze« wektorow¡.
Podkre±lmy, »e sum¦
A
+
B
de niujemy jedynie wtedy, gdy macierze
A
i
B
maj¡ ten sam
wymiar: obie musz¡ mie¢ jednakow¡ liczb¦ wierszy, a tak»e jednakow¡ liczb¦ kolumn;
w szczególno±ci np. nie de niuje si¦ sumy wektora kolumnowego i wektora wierszowego.
De nicja
. Je±li
f
= [
f
1
;:::;f
n
]
2
K
n
jest wektorem wierszowym, natomiast
x
=
2
6
6
4
x
1
...
x
n
3
7
7
5
2
K
n
| wektorem kolumnowym tego samego wymiaru, to ich
iloczynem
(w obligatoryjnej kolejno±ci
wiersz
kolumna
) nazywamy liczb¦
f
x
:=
f
1
x
1
+
::: + f
n
x
n
2
K
.
Je±li
A
2
K
m
n
, to wektor
A x
:=
2
6
6
4
A
1
x
...
A
m
x
3
7
7
5
=
2
6
6
4
A
1
1
x
1
+
::: + A
1
n
x
n
...
A
m
1
x
1
+
::: + A
mn
x
n
3
7
7
5
=
A
1
x
1
+
:::
A
n
x
n
2
K
m
nazywa si¦
iloczynem
macierzy
A
i wektora kolumnowego
x
. Podobnie okre±la
si¦ iloczyn wektora wierszowego
f
= [
f
1
; :::; f
m
]
2
K
m
przez macierz
A
:
f
A
:= [
f
A
1
;:::;
f
A
n
] = [
P
f
i
A
i
1
;:::;
P
f
i
A
in
] =
f
1
A
1
+
:::+f
m
A
m
2
K
n
.
Uogólnienie tych de nicji stanowi iloczyn macierzy
A
2
K
mn
przez macierz
B
2
K
np
, zde niowany jako macierz, której wyrazami s¡ wszelkie mo»liwe
iloczyny wierszy pierwszego czynnika przez kolumny drugiego czynnika:
AB
:=
2
6
6
4
A
1
B
1
A
1
B
2
:::
A
1
B
p
...
...
...
A
m
B
1
A
m
B
2
:::
A
m
B
p
3
7
7
5
2
K
mp
.
Wobec tego wyrazy macierzy
C
:=
A B
wyra»aj¡ si¦ nast¦puj¡cymi wzorami
C
ij
=
A
i
B
j
=
n
P
k
=1
A
ik
B
kj
;
2
widoczne s¡ te» nast¦puj¡ce wzory na kolumny i wiersze powy»szej macierzy:
C
j
=
AB
j
oraz
C
i
=
A
i
B
.
Przykªady
.
2
6
4
1 2
4 6
5
3
3
7
5
"
4
3
#
=
2
6
4
10
2
11
3
7
5
,
[2
; 5]
"
3 5
1 2
2 6 3 4
#
= [16
; 20; 13; 16] ,
2
6
4
1 2
4 6
5
3
3
7
5
"
3 5
1 2
2 6 3 4
#
=
2
6
4
7
7
5
6
0 56 22 32
9 43
14 22
3
7
5
.
atwo sprawdzi¢, »e mno»enie macierzy jest
rozdzielne wzgl¦dem dodawania
:
A
(
B
+ ~
B
) =
AB
+
A
~
B
,
(
A
+ ~
A
)
B
=
AB
+ ~
AB
,
je±li
A
; ~
A
2
K
m
n
;
B
; ~
B
2
K
n
p
.
Fakt
. Mno»enie macierzy jest
ª¡czne
, tzn. (
AB
)
C
=
A
(
B
C
), o ile wymiary
macierzy dopuszczaj¡ stosowne iloczyny:
A
2
K
m
n
,
B
2
K
n
p
,
C
2
K
p
q
.
Istotnie, (i;j)-wyraz (
AB
)
C
jest równy
P
l
P
k
A
ik
B
kl
C
lj
=
P
l
P
k
A
ik
B
kl
C
lj
=
=
P
k;l
A
ik
B
kl
C
lj
; identyczne wyra»enie dostaje si¦ na (i;j)-wyraz macierzy
A
(
B
C
), QED.
Wniosek
. Dla
n
2
N
zbiór
macierzy kwadratowych
M
n
(
K
) :=
K
n
n
jest pier-
±cieniem (z jedynk¡) wzgl¦dem dziaªa« dodawania i mno»enia macierzy.
Zauwa»my, »e
1 0
0 0
0 1
1 0
=
0 1
0 0
,
0 1
1 0
1 0
0 0
=
0 0
1 0
,
1 0
0 0
0 0
0 1
=
0 0
0 0
=
0
,
wi¦c pier±cie« M
2
(
K
) jest nieprzemienny i ma nietrywialne dzielniki zera. To samo dotyczy
pier±cieni M
n
(
K
) dla n > 2, gdy» podzbiór M
n
(
K
), zªo»ony z macierzy
A
o wªasno±ci
i > 2 lub j > 2
)
A
ij
= 0, jest podpier±cieniem M
n
(
K
) izomor cznym z M
2
(
K
).
Zastosowanie macierzy do zapisywania ukªadu równa« liniowych
.
Je±li s¡ dane macierz
A
2
K
m
n
oraz wektor kolumnowy
b
2
K
m
, to mo»emy
napisa¢ nast¦puj¡ce równanie `wektorowe' na wektor
x
2
K
n
:
A x
=
b
.
W postaci rozpisanej jest ono równowa»ne ukªadowi
m równa« `skalarnych'
na `skªadowe'
x
1
;:::;x
n
wektora
x
:
8
>
>
>
<
>
>
>
:
A
1
1
x
1
+
A
1
2
x
2
+
::: +A
1
n
x
n
=
b
1
A
2
1
x
1
+
A
2
2
x
2
+
::: +A
2
n
x
n
=
b
2
::::::::::::::::: ::: :::::::: : ::
A
m
1
x
1
+
A
m
2
x
2
+
::: +A
mn
x
n
=
b
m
(U)
A
nazywa si¦
macierz¡ gªówn¡
(lub
macierz¡ cz¦±ci jednorodnej
) ukªadu (U),
b
|
wektorem prawych stron ukªadu
, natomiast macierz [
Ajb
], powstaªa z
A
przez doª¡czenie wektora
b
jako dodatkowej kolumny:
3
[
Ajb
] :=
2
6
4
A
1
1
::: A
1
n
b
1
:::: ::: :::: ::
A
m
1
::: A
mn
b
m
3
7
5
,
nazywa si¦
macierz¡ rozrzerzon¡
ukªadu (U). Zauwa»my, »e
równaniom ukªadu (U) odpowiadaj¡
wiersze
macierzy [
Ajb
];
`zwykªym' operacjom algebraicznym na równaniach, przeksztaªcaj¡cym
ukªad (U) do równowa»nej postaci, np. takim, jak dodanie stronami do
jednego z równa« kombinacji innych równa«, odpowiadaj¡ analogiczne
operacje na wierszach macierzy [
A
jb
] (s¡ to, jak zobaczymy dalej, tzw.
operacje elementarne
lub zªo»enia takich operacji elementarnych).
De nicja
(
obraz
i
j¡dro
macierzy). Niech
A
2
K
mn
.
Przestrze« im
A
, rozpi¦t¡ przez kolumny
A
, nazywa si¦
obrazem
(ang.
image
) macierzy
A
:
im
A
:=
hA
1
;:::;
A
n
i
K
m
.
Przestrze« rozwi¡za« równania
Ax
=
0
nazywa si¦
j¡drem
(ang.
kernel
)
macierzy
A
:
ker
A
:=
fx
2
K
n
:
Ax
= 0
g
K
n
.
0.2 Dwa sposoby opisu podprzestrzeni
V
K
m
Spotyka si¦ kilka ró»nych postaci opisu podprzestrzeni, lecz w gruncie rzeczy
s¡ tylko dwa typy, wyst¦puj¡ce w kilku równowa»nych wariantach:
I. Opis wektorami rozpinaj¡cymi II. Opis ukªadem równa« liniowych
I. Opis typu `wektory rozpinaj¡ce'
(w skrócie `opis typu W' lub `W-opis')
ma posta¢
V =
h v
1
;:::;
v
r
i
(
v
j
2
K
m
dane); stanowi on
parametryzacj¦
V ,
gdy» jak pami¦tamy
h v
1
;:::;
v
r
i
=
f
t
1
v
1
+
:::+t
r
v
r
:
t
1
;:::;t
r
2
K
g
. Wzór
typu
V = im
A
' tak»e, z de nicji obrazu macierzy, jest opisem typu W.
Przykªad
. Poni»sze wzory s¡ W-opisem pewnej podprzestrzeni w
K
3
i ró»ni¡ si¦ mi¦dzy
sob¡ jedynie notacj¡: V :=
2
4
2
3
1
3
5
;
2
4
3
2
5
3
5
; V :=
2
4
2
3
1
3
5
t
1
+
2
4
3
2
5
3
5
t
2
: t
1
;t
2
2
K
;
V := im
2
4
2 3
3 2
1 5
3
5
;
V :=
2
4
2 3
3 2
1 5
3
5
t
:
t
2
K
2
.
II. Opis typu `ukªad równa«'
(w skrócie `opis typu R' lub `R-opis')
ma posta¢
V =
fx
2
K
m
:
'
1
x
=
::: =
'
s
x
= 0
g
, gdzie
'
1
;:::;
'
s
2
K
m
s¡
danymi wektorami wierszowymi. Równie» wzór postaci
V = ker
B
, z de nicji
j¡dra macierzy, jest opisem typu R.
Przykªad
. Oto cztery R-opisy pewnej podprzestrzeni
K
3
, ró»ni¡ce si¦ jedynie notacj¡:
V =
x
2
K
3
: [2;3; 4]
x
= [1; 4;3]
x
=
0
; V =
x
2
K
3
: 2x
1
+ 3x
2
4x
3
= 0
x
1
4x
2
+ 3x
3
= 0
;
V =
x
2
K
3
:
2 3 4
1 4 3
x
=
0
;
V = ker
2 3 4
1 4 3
.
4
0.3 Operacje elementarne na ukªadach wektorów
Niech
V
b¦dzie ustalon¡ przestrzeni¡ wektorow¡ nad ciaªem
K
.
De nicja
. W zbiorze
V
n
=
V
:::
V n-elementowych ukªadów (v
1
;:::;v
n
)
okre±lmy
operacje elementarne
jako operacje trzech nast¦puj¡cych rodzajów:
1
0
Przestawienie danych wektorów:
(
v
1
;:::;v
n
)
7!
(
v
(1)
;:::;v
(
n
)
)
;
2
S
n
.
2
0
Pomno»enie poszczególnych wektorów przez dowolne
6
= 0 liczby
i
2
K
:
(
v
1
;:::;v
n
)
7!
(
1
v
1
;:::;
n
v
n
).
3
0
Dodanie krotno±ci jednego z wektorów ukªadu (powiedzmy wektora
v
j
)
do pozostaªych wektorów ukªadu:
(
v
1
;:::;v
j
;:::;v
n
)
7!
(
v
1
+
1
v
j
;:::;v
j
;:::;v
n
+
n
v
j
);
tutaj wspóªczynniki
1
;:::;
j
1
;
j
+1
;:::;
n
2
K
mog¡ by¢ dowolne.
Fakt
. Ka»da operacja elementarna jest odwracalna, a jej odwrotno±¢ jest
operacj¡ elementarn¡ tego samego typu (1
0
, 2
0
lub 3
0
).
Gdy (w
1
;:::;w
n
) = (v
(1)
;:::;v
(
n
)
), wtedy (v
1
;:::;v
n
) = (w
1
(1)
;:::;w
1
(
n
)
).
Gdy (w
1
;:::;w
n
) = (
1
v
1
;:::;
n
v
n
), wtedy (v
1
;:::;v
n
) = (
1
1
w
1
;:::;
1
n
w
n
).
Wreszcie gdy (w
1
;:::;w
n
) = (v
1
+
1
v
j
;:::;v
j
;:::;v
n
+
n
v
j
), wtedy
(v
1
;:::;v
n
) = (w
1
1
w
j
;:::;w
j
;:::;w
n
n
w
j
).
De nicja
. Dwa ukªady (
v
1
;:::;v
n
) i (
w
1
;:::;w
n
) nazywamy
równowa»nymi
,
pisz¡c (
v
1
;:::;v
n
)
(
w
1
;:::;w
n
), je»eli ukªad (
w
1
;:::;w
n
) mo»na otrzyma¢
z ukªadu (
v
1
;:::;v
n
) stosuj¡c pewn¡ liczb¦ operacji elementarnych.
Przykªad
(n=3): (
v
1
;v
2
;v
3
)
(9
v
2
+ 2
v
3
;4v
3
+ 3
v
1
; 2v
1
+ 3
v
2
) gdy»
(
v
1
;v
2
;v
3
)
3
0
7
!
(
v
1
;v
2
2
3
v
1
;v
3
+
3
4
v
1
)
3
0
7
!
(
v
1
+ 2
v
2
4
3
v
1
;v
2
2
3
v
1
;v
3
+
3
4
v
1
)
3
0
7
!
(
1
3
v
1
+ 2
v
2
+
4
9
(
v
3
+
3
4
v
1
)
;v
2
2
3
v
1
;v
3
+
3
4
v
1
)
2
0
7
!
(9
v
2
+ 2
v
3
;3v
2
2
v
1
;4v
3
+ 3
v
1
)
1
0
7
!
(9
v
2
+ 2
v
3
;4v
3
+ 3
v
1
; 2v
1
+ 3
v
2
)
:
Fakt
. Okre±lona powy»ej relacja
jest relacj¡ równowa»no±ci w zbiorze
V
n
.
Zwrotno±¢ i przechodnio±¢ s¡ oczywiste, natomiast symetria wynika z poprzedniego faktu:
Odwrotno±ci¡ zªo»enia E
1
E
2
E
k
operacji elementarnych E
1
;_;E
k
jest zªo»enie
E
1
1
E
1
2
E
1
k
(równie» operacji elementarnych).
Fakt
. Je±li (
v
1
;:::;v
n
)
(
w
1
;:::;w
n
), to
(a) (
v
1
;:::;v
n
s¡ liniowo niezale»ne)
(
)
w
1
;:::;w
n
s¡ liniowo niezale»ne,
(b)
h
v
1
;:::;v
n
i
=
h
w
1
;:::;w
n
i
.
Inaczej mówi¡c,
liniowa (nie)zale»no±¢ ukªadu, a tak»e przestrze« rozpinana
przez ukªad, s¡ niezmiennikami operacji elementarnych
.
Charakter okre±lenia relacji
powoduje, »e wystarczy sprawdzi¢ (a) i (b) w przypadku,
5
gdy ukªad (w
1
;:::;w
n
) jest rezultatem podziaªania na (v
1
;:::;v
n
) jedn¡ operacj¡ ele-
mentarn¡. Dla operacji typu 1
lub 2
(a) i (b) s¡ oczywiste, zajmijmy si¦ wi¦c operacj¡
typu 3
. Niech wi¦c, przy ustalonym j
2
1;n, w
j
= v
j
oraz w
i
= v
i
+
i
v
j
dla i
2
1;n
n
f
j
g
.
Je±li v
1
;:::;v
r
s¡ l.niezale»ne oraz
1
;:::;
n
2
K
, to w :=
1
w
1
+ ::: +
n
w
n
jest równe
~
1
v
1
+ :::+ ~
n
v
n
, gdzie ~
j
=
1
1
+ :::+
j
+ :::+
n
n
oraz ~
i
=
i
dla i
2
1;n
n
f
j
g
.
Wida¢ z tego, »e równo±ci ~
1
= 0;:::; ~
n
= 0, b¦d¡ce konsekwencj¡ w = 0, implikuj¡
równo±ci
1
= 0;:::;
n
= 0, a wi¦c w
1
;:::;w
n
s¡ l.niezale»ne, co ko«czy dowód (a). Po-
wy»szy rachunek pokazuje te», »e ka»dy element w
2
h
w
1
;:::;w
n
i
nale»y do
h
v
1
;:::;v
n
i
,
wi¦c
h
v
1
;:::;v
n
i
h
w
1
;:::;w
n
i
; to wraz z symetri¡ relacji
ko«czy dowód (b).
Uwaga
. Okazuje si¦, »e równo±¢ przestrzeni rozpinanych przez dwa ukªady
jest warunkiem nie tylko koniecznym, ale i dostatecznym ich równowa»no±ci:
(
v
1
;:::;v
n
)
(
w
1
;:::;w
n
)
(
)
h
v
1
;:::;v
n
i
=
h
w
1
;:::;w
n
i
;
jest to jednak trudniejsze do wykazania, a zarazem niezbyt przydatne do
celów rachunkowych, wi¦c dowód odªo»ymy na pó¹niej (zob. Appendix).
0.4 Operacje elementarne na kolumnach
i na wierszach macierzy
W dalszym ci¡gu zajmiemy si¦ przypadkiem, gdy
V jest przestrzeni¡
K
m
(macierzy wymiaru
m
1, tzn. wektorów kolumnowych) lub
K
n
(macierzy
wymiaru 1
n, tzn. wektorów wierszowych); wygodnie jest wtedy ukªad
(
v
1
;:::;v
n
) opisa¢ macierz¡, której kolumnami lub wierszami s¡ wektory
v
i
.
Macierz
A
mo»na traktowa¢ jako ukªad jej kolumn, tzn. ukªad (
A
1
;:::;
A
n
),
b¡d¹ jako ukªad wierszy (
A
1
;:::;
A
m
); prowadzi to do nast¦puj¡cych poj¦¢:
De nicja
. Dwie macierze
A
;
B
2
K
mn
s¡:
(a)
kolumnowo równowa»ne
, co zapisujemy w postaci
A
K
B
, je»eli
(
A
1
;:::;
A
n
)
(
B
1
;:::;
B
n
).
(b)
wierszowo równowa»ne
, co zapisujemy w postaci
A
W
B
, je»eli
(
A
1
;:::;
A
n
)
(
B
1
;:::;
B
n
).
Przykªad
.
1 2
3 4
K
1 2 2
3 4 6
=
1 0
3 2
K
1 0
3 1
K
1 3
0 0
3 3
1 1
=
1 0
0 1
;
2 3
4 5
W
2
3
4 2
2 5 2
3
=
2 3
0 1
W
2 3
0 1
W
W
2 3
0 3 3
1
0
1
W
2 0
0 1
W
1 0
0 1
.
Fakt
.
A
K
B
)
im
A
= im
B
;
A
W
B
)
ker
A
= ker
B
:
Wynika to natychmiast z punktu (b) poprzedniego Faktu.
Okazuje si¦, »e w wielu sytuacjach szczególnie wygodne s¡ tzw.
macierze
6
zredukowane
(kolumnowo lub wierszowo) i, co wi¦cej, »e z ka»dej macierzy
A
mo»na, stosuj¡c operacje elementarne na jej kolumnach (wierszach) otrzyma¢
równowa»n¡ jej macierz kolumnowo (wierszowo) zredukowan¡.
0.5 Macierze zredukowane
De nicja
.
Samotnikiem wierszowym
macierzynazwijmytaki jej wyraz, który
jest jedynym
6
= 0 elementemzawieraj¡cego go wiersza; analogicznie okre±lmy
samotniki kolumnowe
macierzy.
Tak wi¦c np. macierz
A
:=
2
6
4
0 1 2
3 0 0
0 0 4
3
7
5
ma dwa samotniki wierszowe:
A
2
1
= 3 i
A
3
3
= 4, oraz dwa samotniki kolumnowe:
A
1
2
= 1 i
A
2
1
= 3.
Fakt
. Ukªad zªo»ony z takich kolumn macierzy
A
, które zawieraj¡ samotniki
wierszowe, jest liniowo niezale»ny. Podobnie, ukªad zªo»ony z takich wierszy
macierzy
A
, które zawieraj¡ samotniki kolumnowe, jest liniowo niezale»ny.
Niech kolumna
A
j
1
ma samotnika wierszowego c
1
:= A
i
1
j
1
,
A
j
2
| samotnika wierszowego
c
2
:= A
i
2
j
2
, itd. Wtedy komb. liniowa
v
=
1
A
j
1
+
2
A
j
2
+::: ma wspóªrz¦dne o numerach
i
1
; i
2
; ::: równe
1
c
1
;
2
c
2
; :::, wi¦c skoro c
k
6
= 0, to
v
= 0 implikuje
1
= 0;
2
= 0;:::.
De nicja
.
Macierz¡ kolumnowo zredukowan¡
(w skrócie: KZ-macierz¡)
nazywamy tak¡ macierz, której ka»da niezerowa kolumna ma samotnika
wierszowego. Podobnie,
macierz wierszowo zredukowana
(WZ-macierz) jest
tak¡ macierz¡, której ka»dy niezerowy wiersz ma samotnika kolumnowego.
Przykªad
. Po zast¡pieniu znaków `?' dowolnymi liczbami, a znaków `?' | liczbami
6
= 0,
poni»sza macierz
M
stanie si¦ KZ-macierz¡, natomiast macierz
N
| WZ-macierz¡:
M
:=
2
6
6
6
6
6
6
6
6
4
0 0 0 0 0 ?
? ? 0 ? 0 ?
0 ? 0 0 0 0
? ? 0 ? 0 ?
? 0 0 0 0 0
? ? 0 ? 0 ?
0 0 0 ? 0 0
3
7
7
7
7
7
7
7
7
5
,
N
:=
2
6
6
6
6
6
6
6
6
4
0 0 0 0 0 0 0 0
? 0 ? ? 0 ? 0 ?
? 0 ? 0 ? ? 0 ?
0 0 0 0 0 0 0 0
? ? ? 0 0 ? 0 ?
0 0 0 0 0 0 0 0
? 0 ? 0 0 ? ? ?
3
7
7
7
7
7
7
7
7
5
.
Oczywist¡ konsekwencj¡ poprzedniego faktu jest
Fakt
. (1) Niezerowe kolumny KZ{macierzy s¡ liniowo niezale»ne.
(2) Niezerowe wiersze WZ{macierzy s¡ liniowo niezale»ne.
Macierze zredukowane mo»na tak»e opisa¢ w inny sposób, u»ywaj¡c poj¦-
cia
macierzy permutacyjnej
(w skrócie: P-macierzy). P
-macierz¡
nazywa¢
b¦dziemy macierz, maj¡c¡ zarówno w ka»dym wierszu, jak i w ka»dej ko-
lumnie, dokªadnie jeden wyraz ró»ny od 0; jasne, »e taka macierz musi by¢
kwadratowa (tzn. mie¢ tyle wierszy, co kolumn). Przykªadami P-macierzy s¡:
2
6
4
0 5 0
3 0 0
0 0 7
3
7
5
;
2
6
4
0 1 0
0 0 1
2 0 0
3
7
5
;
2
6
4
2 0 0
0 0 5
0 3 0
3
7
5
;
2
6
4
0 0 3
2 0 0
0 7 0
3
7
5
.
7
Podmacierz¡
macierzy
A
nazywamy macierz, otrzyman¡ przez (ewentualne)
wykre±lenie z
A
pewnych wierszy i/lub kolumn. Na przykªad
2
6
4
1 2 3
4 5 6
7 8 9
3
7
5
zawiera nast¦puj¡ce podmacierze wymiaru 2
2:
1 2
4 5
;
1 3
4 6
;
2 3
5 6
;
1 2
7 8
;
1 3
7 9
;
2 3
8 9
;
4 5
7 8
;
4 6
7 9
;
5 6
8 9
.
atwo teraz przekona¢ si¦, »e zachodzi nast¦puj¡cy
Fakt
. Macierz
A
2
K
m
n
jest KZ-macierz¡
(
)
zawiera pewn¡ podmacierz,
b¦d¡c¡ P-macierz¡ wymiaru
r
r, gdzie r = (liczba
6
= 0-kolumn
A
).
Analogicznie jest dla WZ-macierzy: tym razem
r = (liczba
6
= 0-wierszy
A
).
Przykªad
. Powy»sze macierze
M
i
N
zawieraj¡ nast¦puj¡ce podmacierze permutacyjne:
dla
M
:
2
6
6
4
0 0 0 ?
0 ? 0 0
? 0 0 0
0 0 ? 0
3
7
7
5
,
dla
N
:
2
6
6
4
0 ? 0 0
0 0 ? 0
? 0 0 0
0 0 0 ?
3
7
7
5
;
przy tym
M
ma 4 niezerowe kolumny,
N
| 4 niezerowe wiersze, wi¦c
M
jest KZ-macierz¡,
a
N
| WZ-macierz¡.
2
6
6
4
1 0 4
0 0 5
2 0 6
3 0 0
3
7
7
5
jest KZ-macierz¡, gdy» ma P-podmacierz
0 5
3 0
,
za±
2
6
6
4
1 2 0
0 0 0
0 3 4
0 0 0
3
7
7
5
jest WZ-macierz¡, gdy» ma P-podmacierz
1 0
0 4
.
De nicja
. Ustalmy wska¹niki
i;j, dla których A
ij
jest niezerowym wyrazem
macierzy
A
. Operacja elementarna (typu 3
, na kolumnach), okre±lona jako
dodanie takich krotno±ci kolumny
A
j
do pozostaªych
kolumn, »eby wyraz
A
ij
staª si¦ samotnikiem wierszowym
nazywa si¦
redukcj¡ kolumnow¡ wzgl¦dem wyrazu
A
ij
, zwanego
wyrazem
bazowym
dla tej operacji.
De nicja
redukcji wierszowej wzgl¦dem wyrazu bazowego
A
ij
jest analogiczna:
dodanie takich krotno±ci wiersza
A
i
do pozostaªych
wierszy, »eby wyraz
A
ij
staª si¦ samotnikiem kolumnowym .
Przykªad
(
3
). Dla
A
=
2
4
2 3 4
1 2 5
3 5 6
3
5
i wyrazu bazowego A
2
1
= 1 redukcja kolumnowa
wyprodukuje z macierzy
A
macierz
2
4
2 3 2
2 4 5
2
1 2 2
1 5 5
1
3 5 2
3 6 5
3
3
5
=
2
4
2
1
6
1 0
0
3
1
9
3
5
,
redukcja wierszowa za± | macierz
2
4
2 2
1 3 2
2 4 2
5
1
2
5
3 3
1 5 3
2 6 3
5
3
5
=
2
4
0 1 6
1 2 5
0 1 9
3
5
.
Zgodnie z de nicj¡ w redukcji kolumnowej zast¦puje si¦ ka»d¡ kolumn¦
A
k
,
dla
k
6
=
j, wektorem
A
k
+
k
A
j
, ze wspóªczynnikiem
k
wyznaczonym z
3
Wybrany wyraz bazowy macierzy b¦dziemy w dalszym ci¡gu wyró»nia¢ ramk¡ . .
8
warunku 0 = (
i-ta wspóªrz¦dna
A
k
+
k
A
j
) =
A
ik
+
k
A
ij
, tzn.
k
= A
ik
A
ij
.
Wygodnie jest zapami¦ta¢ ten rezultat w formie nast¦puj¡cego schematu:
2
6
6
6
6
6
6
6
4
... ...
a
b
... ...
c
d
... ...
3
7
7
7
7
7
7
7
5
7
!
2
6
6
6
6
6
6
6
4
...
...
a
0
...
...
c
d
bca
...
...
3
7
7
7
7
7
7
7
5
|
{z
}
dla redukcji kolumnowej
lub
2
6
6
6
6
6
6
6
4
...
...
a
b
...
...
0
d
bca
...
...
3
7
7
7
7
7
7
7
5
|
{z
}
dla redukcji wierszowej
;
wymaga on oczywistej mody kacji, gdy wyraz bazowy le»y w innym `rogu'.
Algorytm Redukcji Kolumnowych
Polega on na przeprowadzaniu redukcji kolumnowych wzgl¦dem kolejnych
wyrazów bazowych, wybieranych zgodnie z dwiema nast¦puj¡cymi zasadami:
(K) nie mog¡ si¦ powtarza¢ numery kolumn wyrazów bazowych;
(W) nie mog¡ si¦ powtarza¢ numery wierszy wyrazów bazowych.
Przestrzegaj¡c zasady (K) nie da si¦ naruszy¢ zasady (W) (
4
), wi¦c mo»na by opu±ci¢ (W),
jako konsekwencj¦ (K); jednak powy»sza symetryczna posta¢ `wytycznych' jest ªatwiejsza
do zapami¦tania i por¦czniejsza w u»yciu. Uzupeªniaj¡c¡ (ju» nie obligatoryjn¡) zasad¡
jest wybór takich wyrazów bazowych, przez które `ªatwo' jest dzieli¢.
Ka»da redukcja kolumnowa sprawia, »e jej wyraz bazowy staje si¦ samotni-
kiem wierszowym, a przy tym samotniki z innych (np. wcze±niej wybranych)
kolumn pozostan¡ samotnikami. Wobec tego po zako«czeniu procedury, gdy
nie jest ju» mo»liwy wybór nowego wyrazu bazowego, ka»da niezerowa ko-
lumna ma samotnika wierszowego, czyli otrzymana macierzjest KZ-macierz¡.
Algorytm Redukcji Wierszowych
ró»ni si¦ od powy»szego
jedynie tym,»e redukcje kolumnowenale»y zast¡pi¢ redukcjamiwierszowymi.
Z powy»szych rozwa»a« wynika natychmiast nast¦puj¡ce
Twierdzenie
. Z dowolnej macierzy
A
mo»na otrzyma¢, stosuj¡c operacje
elementarne typu 3
0
na kolumnach, równowa»n¡ jej kolumnowo KZ-macierz.
Analogicznie,ka»da macierzjest wierszowo równowa»na pewnej WZ-macierzy.
Przykªad
.
2
6
6
4
2 3 3 4
3 5 5 6
1 2 1 1
2 1 5 2
3
7
7
5
K
2
6
6
4
2 1 1 2
3 1 2 3
1 0 0 0
2 3 7 4
3
7
7
5
K
2
6
6
4
0 0 1 0
1 1 2
1
1 0 0 0
16 10 7 10
3
7
7
5
K
2
6
6
4
0 0 1 0
0 1 0 0
1 0 0 0
6 10 13 0
3
7
7
5
.
2
6
6
4
2 3 3 4
3 5 5 6
1 2 1 1
2 1 5 2
3
7
7
5
W
2
6
6
4
0 1 1 2
0 1 2 3
1 2 1 1
0 3 7 4
3
7
7
5
W
2
6
6
4
0
1 1 2
0 1 0 1
1 3 0 1
0 10 0 10
3
7
7
5
W
2
6
6
4
0 0 1 1
0 1 0 1
1 0 0 2
0 0 0 0
3
7
7
5
.
Obie ko«cowe macierze s¡ zredukowane (kolumnowo w 1., a wierszowo w 2. przypadku).
4
Wiersz, `u»yty' ju» poprzednio, ma
6
= 0 wyraz jedynie w `u»ytej' poprzednio kolumnie.
9
0.6 Zastosowanie operacji elementarnych
do podstawowych zada« numerycznych
algebry wektorowej
Omówimy teraz kolejno nast¦puj¡ce zagadnienia:
1. Uproszczenie opisu typu W. Obliczanie wymiaru im
A
. Badanie liniowej
niezale»no±ci danych wektorów z
K
m
1
. Uproszczenie opisu typu R. Obliczanie wymiaru ker
B
. Badanie liniowej
niezale»no±ci danych równa«, tzn. wektorów z
K
n
2. Przej±cie od opisu typu R do opisu typu W, czyli Rozwi¡zywanie jedno-
rodnego ukªadu równa« liniowych
2
. Przej±cie od opisu typu W do opisu typu R, czyli Znajdowanie zupeªnego
ukªadu równa« liniowych speªnianych przez dane wektory
3. Rozwi¡zywanie ukªadu równa« liniowych niejednorodnych
4. Odwracanie macierzy kwadratowej
5. Znajdowanie przeci¦cia
V
1
\
V
2
dwóch podprzestrzeni
6. Znajdowanie sumy algebraicznej
V
1
+
V
2
dwóch podprzestrzeni
1. Uproszczenie opisu typu W. Obliczanie wymiaru
im
A
.
Badanie liniowej niezale»no±ci danych wektorów z
K
m
.
Poniewa»
A
0
K
A
)
im
A
= im
A
0
, wi¦c w opisie
V = im
A
mo»emy
A
za-
st¡pi¢ KZ-macierz¡
A
0
, otrzyman¡ z
A
przez zastosowanie algorytmu reduk-
cji kolumnowych; zatem dim
V jest liczb¡
6
= 0-kolumn
A
0
oraz
V = im
A
00
,
gdzie
A
00
jest rezultatem usuni¦cia z
A
0
ewentualnych kolumn zerowych.
Przykªad
1
. Niech V =
2
6
6
4
7
4
0
5
3
7
7
5
;
2
6
6
4
3
2
2
1
3
7
7
5
;
2
6
6
4
1
2
10
5
3
7
7
5
;
2
6
6
4
0
1
7
4
3
7
7
5
; wtedy V = im
2
6
6
4
7 3 1 0
4 2 2 1
0 2 10 7
5 1 5 4
3
7
7
5
,
za±
2
6
6
4
7 3 1 0
4 2 2 1
0 2 10 7
5 1 5 4
3
7
7
5
K
2
6
6
4
0 0 1 0
10 4 2 {1
70 28 10 7
40 16 5 4
3
7
7
5
K
2
6
6
4
0 0 1 0
0 0 0 1
0 0 4 7
0 0 3 4
3
7
7
5
; st¡d V = im
2
6
6
4
1 0
0 1
4 7
3 4
3
7
7
5
=
2
6
6
4
1
0
4
3
3
7
7
5
;
2
6
6
4
0
1
7
4
3
7
7
5
, dimV = 2, wi¦c cztery wektory z pocz¡tkowego opisu V s¡ lin. zale»ne.
Przykªad
2
. Dla V =
2
6
6
4
4
3
1
2
3
7
7
5
;
2
6
6
4
1
2
4
3
3
7
7
5
;
2
6
6
4
2
4
3
1
3
7
7
5
mamy
A
=
2
6
6
4
4 1 2
3 2 4
1 4 3
2 3 1
3
7
7
5
K
2
6
6
4
0 1 0
5 2 0
15 4 5
10 3 5
3
7
7
5
K
K
2
6
6
4
0 1 0
1 2 0
3 4 1
2 3 1
3
7
7
5
K
2
6
6
4
0 1 0
1 0 0
3 2 1
2 1 1
3
7
7
5
K
2
6
6
4
0 1 0
1 0 0
1 1 1
0 0 1
3
7
7
5
; ostatnia macierz jest KZ, wi¦c jej kolumny(nie-
zerowe!) s¡ l.niezale»ne; st¡d dimV = 3 i wektory
2
6
6
4
4
3
1
2
3
7
7
5
;
2
6
6
4
1
2
4
3
3
7
7
5
;
2
6
6
4
2
4
3
1
3
7
7
5
te» s¡ l.niezale»ne.
10
1
. Uproszczenie opisu typu R. Obliczanie wymiaru
ker
B
.
Badanie liniowej niezale»no±ci danych równa«, tzn. wektorów z
K
n
Poniewa»
B
W
B
0
)
ker
B
0
= ker
B
, wi¦c w opisie
V = ker
B
mo»emy
B
zast¡pi¢ WZ-macierz¡
B
0
, otrzyman¡ z
B
przez zastosowanie algorytmu
redukcji wierszowych; wynika st¡d(
5
), »e dim
V = m r, gdzie r jest liczb¡
niezerowych wierszy
B
0
(jak poprzednio,
V
K
m
, tzn.
m jest liczb¡ `nie-
wiadomych', tzn. liczb¡ kolumn
B
i
B
0
); ponadto
V = ker
B
00
, gdzie
B
00
jest
rezultatem opuszczenia w
B
0
ewentualnych wierszy zerowych.
Przykªad
3
. Je±li V
K
4
jest zde niowana jako przestrze« rozwi¡za« ukªadu równa«
8
>
>
<
>
>
:
7x
1
+3x
2
+x
3
= 0;
4x
1
+2x
2
+2x
3
x
4
= 0;
2x
2
+10x
3
7x
4
= 0;
5x
1
+x
2
5x
3
+4x
4
= 0;
(U)
to V = ker
B
, gdzie
B
=
2
6
6
4
7 3 1 0
4 2 2 1
0 2 10 7
5 1 5 4
3
7
7
5
W
2
6
6
4
8 0 16 12
{6 0 12 9
10 0 20 15
5 1 5 4
3
7
7
5
W
2
6
6
4
0 0 0 0
6 0 12 9
0 0 0 0
0 1 5
7
2
3
7
7
5
W
2
6
6
4
0 0 0 0
2 0 4 3
0 0 0 0
0 2 10 7
3
7
7
5
,
wi¦c V =
x
2
K
4
: 2x
1
4x
3
+3x
4
= 0
2x
2
+10x
3
7x
4
= 0
= ker
2 0 4 3
0 2 10 7
; ostatnia macierz
jest WZ, wi¦c jej wiersze (niezerowe) s¡ liniowo niezale»ne, sk¡d dimV = 4 2 = 2.
2. Przej±cie od opisu typu R do opisu typu W
czyli
Rozwi¡zywanie jednorodnego ukªadu równa« liniowych
Po uproszczeniu zgodnie z punktem 1
dostajemy opis
V = ker
C
, gdzie
C
jest WZ-macierz¡ (bez zerowych wierszy). Niech
K
1
;m b¦dzie zbiorem
numerów kolumn jakiej± maksymalnej P-podmacierzy
C
(
6
). Wtedy ukªad
C
x
=
0
mo»na przepisa¢ w postaci
x
k
=
P
j
62
K
D
kj
x
j
dla
k
2
K
(*)
(mianowicie
D
kj
=
C
i
j
C
i
k
, gdzie
C
ik
= jedyny niezerowy wyraz
k-kolumny),
wi¦c jego rozwi¡zanie ogólne ma posta¢
(
x
j
)
j
62
K
| dowolne z
K
, (
x
k
)
k
2
K
| okre±lone wzorami (*).
Zauwa»my teraz, »e je±li zast¡pimy w wektorze
x
wspóªrz¦dne
x
k
,
k
2
K,
wyra»eniami
P
j
62
K
D
kj
x
j
, to otrzymamy przedstawienie postaci
x
=
P
j
62
K
x
j
v
j
;
zatem
tak znalezione wektory
v
j
tworz¡ baz¦
V , czyli daj¡ jej W-opis(
7
).
Przykªad
4.
Dla V z przykªadu 3. dostali±my
C
=
2 0 4 3
0 2 10 7
, wi¦c K =
f
1;2
g
oraz
5
Np. przez przej±cie od opisu typu R do opisu typu W, patrz dalej punkt 2.
6
K mo»na uzyska¢ jako zbiór numerów kolumn zestawu samotników kolumnowych,
wybranych po jednym z ka»dego wiersza macierzy
C
.
7
Wektory
v
j
s¡ liniowo niezale»ne, gdy»
x
zale»y injektywnie od zestawu x
j
j
21
;m
n
K
.
11
V =
x
2
K
4
: x
1
= 2x
3
3
2
x
4
x
2
= 5x
3
+
7
2
x
4
=
x
=
2
6
6
4
2x
3
3
2
x
4
5x
3
+
7
2
x
4
x
3
x
4
3
7
7
5
: x
3
;x
4
2
K
=
=
x
= x
3
2
6
6
4
2
5
1
0
3
7
7
5
+
1
2
x
4
2
6
6
4
3
7
0
2
3
7
7
5
: x
3
;x
4
2
K
=
2
6
6
4
2
5
1
0
3
7
7
5
;
2
6
6
4
3
7
0
2
3
7
7
5
= im
2
6
6
4
2 3
5 7
1 0
0 1
3
7
7
5
.
Jest to W-opis przestrzeni V rozwi¡za« ukªadu (U); tym samym rozwi¡zali±my ukªad (U).
Warto zauwa»y¢, »e znaleziony W-opis V jest maksymalnie uproszczony, tzn. odpowiada
macierzy KZ; nietrudno dowie±¢, »e jest tak zawsze przy stosowaniu powy»szej procedury.
Uw
aga
. Oczywi±cie
v
j
mo»na znale¹¢ jako takie rozwi¡zanie
x
ukªadu
C
x
=
0
(lub (*)),
w którym s¡ zerami wszystkie wspóªrz¦dne o indeksach z 1;m
n
K, oprócz x
j
= 1.
2
. Przej±cie od opisu typu W do opisu typu R
czyli
Znajdowanie zupeªnego ukªadu równa« liniowych
speªnianych przez dane wektory
Po uproszczeniu (punkt 1.) dostajemy opis
V = im
C
, gdzie
C
2
K
mn
jest
KZ-macierz¡ (bez zerowych kolumn). Cz¦±¢ zale»no±ci
x
i
=
P
j
C
ij
u
j
, odpo-
wiadaj¡cych rozkªadowi
x
=
P
j
C
j
u
j
, ma nader prost¡ posta¢
x
k
j
=
c
j
u
j
;
tych prostych zale»no±ci wystarcza do wyra»enia
wszystkich
u
j
(samotniki
wierszowe!) przez wspóªrz¦dne
x
. Wstawiaj¡c teraz
u
j
=
1
c
j
x
j
do
pozostaªych
(tzn. dla
i spoza zbioru K =
f
k
1
;:::;k
n
g
) zale»no±ci
x
i
=
P
j
C
ij
u
j
dostajemy
równania na
x
, równowa»ne oczywi±cie warunkowi
x
2
im
C
.
Przykªad
5
. W przykªadzie 1. dostali±my
x
2
V
,
9
u
1
;u
2
:
x
=
2
6
6
4
1
0
4
3
3
7
7
5
u
1
+
2
6
6
4
0
1
7
4
3
7
7
5
u
2
;
zatem
x
1
= u
1
;
x
2
= u
2
; wstawiaj¡c
u
1
= x
1
;
u
2
= x
2
do pozostaªych zale»no±ci
x
3
= 4u
1
7u
2
;
x
4
= 3u
1
+ 4u
2
dostajemy
x
3
= 4x
1
+ 7x
2
;
x
4
= 3x
1
4x
2
: Zatem
V =
x
2
K
4
: 4x
1
7x
2
+ x
3
= 0
3x
1
4x
2
x
4
= 0
= ker
4 7 1 0
3 4 0 1
.
Zauwa»my, »e uzyskany w ten sposób opis V = ker
B
ma posta¢ mo»liwie najwygodniejsz¡:
B
=
4 7 1 0
3 4 0 1
jest WZ-macierz¡. atwo uzasadni¢, »e jest to ogólna prawidªowo±¢.
3. Rozwi¡zywanie ukªadu równa« liniowych niejednorodnych.
Post¦powanie polega na przeprowadzeniu algorytmu redukcji wierszowych(
8
)
dla macierzy rozszerzonej ukªadu, przy czym w ka»dym kroku bazowe wyrazy
nale»y wybiera¢ jedynie z cz¦±ci gªównej tej macierzy(
9
).
8
Gdy» operacje na wierszach s¡ w istocie operacjami na równaniach ukªadu, takimi jak
np. dodawanie równa« stronami czy ich odejmowanie.
9
Gdy» celem jest wyra»enie niewiadomych poprzez prawe strony, a nie na odwrót.
12
Przykªad
6
.
8
>
>
<
>
>
:
2x
2
+ x
3
+ 3x
4
= 2
x
1
+ x
2
+ x
3
+ 3x
4
= 2
5x
1
+ 10x
2
+ 6x
3
+ 15x
4
= 1
x
1
+ 2x
2
+ x
3
+ 2x
4
= 1
9
>
>
=
>
>
;
, tzn.
2
6
6
4
0 2 1 3
1 1 1 3
5 10 6 15
1 2 1 2
3
7
7
5
x
=
2
6
6
4
2
2
1
1
3
7
7
5
.
Rozwi¡zanie:
2
6
6
4
0 2 1 3 2
1 1 1 3 2
5 10 6 15 1
1 2 1 2 1
3
7
7
5
W
2
6
6
4
0 2 1 3 2
1 1 0 0
4
5 2 0 3 11
1 0 0 1 1
3
7
7
5
W
2
6
6
4
0 2 1 3 2
1 1 0 0 4
0 3 0 3 9
0 1 0 1 3
3
7
7
5
W
2
6
6
4
0 0 1 5 4
1 0 0 1 1
0 0 0 0 0
0 1 0 1 3
3
7
7
5
,
czyli
8
<
:
x
1
= 1 + x
4
x
2
= 3 + x
4
;
x
3
= 4 5x
4
:
Zatem rozwi¡zaniem ogólnym jest
x
=
2
6
6
4
1
3
4
0
3
7
7
5
+
2
6
6
4
1
1
5
1
3
7
7
5
,
2
K
.
Przykªad
7
. Rozwi¡»my dwa ukªady, ró»ni¡ce si¦ jedynie prawymi stronami:
(a)
2
4
3 4 1
5 2 3
2 1 3
3
5
x
=
2
4
1
2
3
3
5
,
(b)
2
4
3 4 1
5 2 3
2 1 3
3
5
x
=
2
4
2
8
5
3
5
.
B¦dziemy oba ukªady rozwi¡zywa¢ równocze±nie:
2
4
3
4 1 1 2
5 2 3 2 8
2 1
3 3 5
3
5
W
2
4
11 0 11 13 22
9 0 9
4 18
2 1
3 3
5
3
5
W
2
4
0 0 0
73
9
0
9 0 9 4 18
1 1 0
5
3
1
3
5
.
Odpowied¹
. (a) Ukªad sprzeczny. (b)
x
2
= 1 + x
1
x
3
= 2 + x
1
, tzn.
x
=
2
4
0
1
2
3
5
+
2
4
1
1
1
3
5
,
2
K
.
4. Odwracanie macierzy kwadratowej
.
Jak wiemy (
AB
)
j
=
AB
j
, tzn.
j-t¡ kolumn¡ iloczynu
AB
jest iloczyn ma-
cierzy
A
przez
j-t¡ kolumn¦
B
j
macierzy
B
. Stosuj¡c ten wzór do przypadku,
gdy
A
;
B
2
K
n
n
i
AB
=
I
n
, tzn. gdy
B
=
A
1
, widzimy, »e wtedy
AB
j
=
j-ta kolumna
macierzy
I
n
!
=
e
j
=
j-ty wektor bazy standardowej
(zerojedynkowej) w
K
n
!
,
a wi¦c poszczególne kolumny
B
j
szukanej macierzy
B
mo»na znale¹¢ jako
rozwi¡zania
x
ukªadów równa«
Ax
=
e
j
. Poniewa» te ukªady ró»ni¡ si¦ je-
dynie prawymi stronami, wi¦c wygodnie jest tu (tak jak w przykªadzie 7)
zastosowa¢ metod¦ `kolektywnego' rozwi¡zywania takich ukªadów.
Przykªad
8
. Dla znalezienia odwrotno±ci
A
:=
2
4
3 1 4
5 2 1
6 2 7
3
5
post¦pujemy nast¦puj¡co:
2
4
3 1 4 1 0 0
5 2 1 0 1 0
6 2 7 0 0 1
3
5
W
2
4
3 1 4 1 0 0
{1 0 7 2 1 0
0 0 1 2 0 1
3
5
W
2
4
0 1 17 5 3 0
1 0 7 2 1 0
0 0 {1 2 0 1
3
5
W
W
2
4
0 1 0 29 3 17
1 0 0 12 1 7
0 0 1 2 0 1
3
5
W
2
4
1 0 0 12 1 7
0 1 0 29 3 17
0 0 1 2 0
1
3
5
, a wi¦c
A
1
=
2
4
12 1 7
29 3 17
2 0 1
3
5
.
Zwykle bardziej `por¦czny' bywa alternatywny (`wertykalny') wariant powy»-
szej metody, w którym role wierszy i kolumn s¡ odwrócone.
Przykªad
9
. Rezultat
2
4
2 3 4
3 5 6
1 2 1
3
5
1
=
2
4
7 5 2
3 2 0
1 1 1
3
5
mo»na otrzyma¢ nast¦puj¡co:
13
2
6
6
6
6
6
6
4
2 3 4
3 5 6
1 2 1
1 0 0
0 1 0
0 0 1
3
7
7
7
7
7
7
5
K
2
6
6
6
6
6
6
4
2 {1 2
3 1 3
1 0 0
1 2 1
0 1 0
0 0 1
3
7
7
7
7
7
7
5
K
2
6
6
6
6
6
6
4
0 1 0
1 1 1
1 0 0
1 2 5
2 1 2
0 0 1
3
7
7
7
7
7
7
5
K
2
6
6
6
6
6
6
4
0 1 0
0 0 1
1 0 0
2 7 5
0 3 2
1 1 1
3
7
7
7
7
7
7
5
K
2
6
6
6
6
6
6
4
1 0 0
0 1 0
0 0 1
7 5 2
3 2 0
1 1 1
3
7
7
7
7
7
7
5
.
Nietrudno sprawdzi¢, »e macierz kwadratowa
A
ma odwrotno±¢
(
)
A
K
I
n
, a wi¦c
A
1
nie istnieje
(
)
algorytmredukcji kolumnowychdaje macierz z zerow¡ kolumn¡
.
A oto jeszcze inne uzasadnienie powy»szej metody znajdowania odwrotno±ci:
Zauwa»my, »e ka»d¡ operacj¦ elementarn¡ na kolumnach macierzy
A
2
K
mn
mo»na opisa¢ wzorem
A
7!
AE
, gdzie
E
2
K
nn
jest pewn¡ macierz¡, odpo-
wiadaj¡c¡ danej operacji (tzw.
macierz¡ elementarn¡
(
10
)). Na przykªad
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
7!
2
4
a
2
a
1
a
3
b
2
b
1
b
3
c
2
c
1
c
3
3
5
=
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
2
4
0 1 0
1 0 0
0 0 1
3
5
(przestawienie 1. i 2. kolumny)
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
7!
2
4
1
a
1
2
a
2
3
a
3
1
b
1
2
b
2
3
b
3
1
c
1
2
c
2
3
c
3
3
5
=
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
2
4
1
0 0
0
2
0
0 0
3
3
5
pomno»enie kolumn
przez liczby
1
;
2
;
3
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
7!
2
4
a
1
a
2
+
2
a
1
a
3
+
3
a
1
b
1
b
2
+
2
b
1
b
3
+
3
b
1
c
1
c
2
+
2
c
1
c
3
+
3
c
1
3
5
=
2
4
a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3
3
5
2
4
1
2
3
0 1 0
0 0 1
3
5
dodanie krotn.
A
1
do
A
2
i
A
3
Z tego spostrze»enia wynika, »e je±li jaki± ci¡g E
1
;:::;E
r
elementarnych operacji na ko-
lumnach prowadzi od macierzy
A
do macierzy jednostkowej, to
AE
1
:::
E
r
=
I
n
; wtedy
(mno»¡c obie strony przez
A
1
) dostajemy równo±¢
I
n
E
1
:::
E
r
=
A
1
, która pokazuje,
»e ten sam ci¡g operacji elementarnych prowadzi od macierzy
I
n
do macierzy
A
1
, QED.
5. Znajdowanie przeci¦cia
V
1
\
V
2
dwóch podprzestrzeni
Gdy dla
V
1
znajdziemy opis typu W:
V =
hv
1
;:::;
v
n
i
, a dla
V
2
| opis typu
R, wówczas przeci¦cie
V
1
\
V
2
skªada si¦ z tych
v
=
P
i
i
v
i
, których wspóª-
czynniki
i
speªniaj¡ równanie indukowane z równa« opisuj¡cych
V
2
.
Przykªad
10
. Niech V
1
= ker
5 1 8 7 0
3 0 5 5 1
, V
2
= ker
1 1 0 1 0
4 1 3 0 1
; stosuj¡c
procedur¦ 2. dostajemy opis V
1
= im
A
, gdzie
A
=
2
6
6
6
6
4
1 0 0
5 8 7
0 1 0
0 0 1
3 5 5
3
7
7
7
7
5
. Przy tym wektor
v
=
1
2
6
6
6
6
4
1
5
0
0
3
3
7
7
7
7
5
+
2
2
6
6
6
6
4
0
8
1
0
5
3
7
7
7
7
5
+
3
2
6
6
6
6
4
0
7
0
1
5
3
7
7
7
7
5
=
A
2
4
1
2
3
3
5
2
V
1
speªnia równanie opisuj¡ce V
2
wtedy i tylko wtedy, gdy 0 =
1 1 0 1 0
4 1 3 0 1
A
2
4
1
2
3
3
5
=
6 8 6
12 16 12
2
4
1
2
3
3
5
, czyli
3
1
4
2
+3
3
= 0, tzn.
3
=
1
+
4
3
2
, tzn.
2
4
1
2
3
3
5
=
2
4
1 0
0 3
1 4
3
5
1
1
3
2
, gdzie
1
;
2
2
K
.
10
Macierz
E
jest oczywi±cie rezultatem podziaªania dan¡ operacj¡ na macierz
A
=
I
n
.
14
Odpowied¹
. V
1
\
V
2
= im
A
2
4
1 0
0 3
1 4
3
5
= im
2
6
6
6
6
4
1 0
2 4
0 3
1 4
2 5
3
7
7
7
7
5
.
6. Znajdowanie sumy algebraicznej
V
1
+
V
2
dwóch podprzestrzeni
Jest to metoda `dwoista' do poprzedniej: Tak jak w 5. znajdujemy dla jednej
z podprzestrzeni (powiedzmy
V
1
) W-opis, a dla drugiej (dla
V
2
) | R-opis;
nast¦pnie znajdujemy takie kombinacje liniowe równa« opisuj¡cych
V
2
, które
zeruj¡ wszystkie generatory
V
1
. Tak otrzymane równania opisuj¡
V
1
+
V
2
.
Przykªad
11
. Dla V
1
i V
2
z przykªadu 10. kombinacja liniowa o wspóªczynnikach
1
;
2
równa« opisuj¡cych V
1
ma posta¢
f
=
1
;
2
1 1 0 1 0
4 1 3 0 1
; takie
f
b¦dzie zero-
wa¢ generatory V
1
(czyli kolumny
A
)
(
)
0 =
f
A
=
1
;
2
1 1 0 1 0
4 1 3 0 1
A
=
=
1
;
2
6 8 6
12 16 6
=
6
1
+ 12
2
; 8
1
16
2
; 6
1
+ 12
2
, tzn.
1
= 2
2
,
czyli
1
;
2
=
2; 1
, gdzie
2
K
dowolne.
Odpowied¹
. V
1
+ V
2
= ker [ 2; 1]
1 1 0 1 0
4 1 3 0 1
= ker
2; 1; 3; 2; 1
.
Uwaga
. Alternatywne sposoby dla (5) i (6), polegaj¡ce na `poª¡czeniu' obu
zestawów równa« (dla
V
1
\
V
2
) lub generatorów (dla
V
1
+
V
2
) opisuj¡cych
V
1
i
V
2
, a nast¦pnie dokonaniu ich redukcji, s¡ na ogóª bardziej pracochªonne!
0.7 Appendix: Baza standardowa podprzestrzeni
K
m
De nicja
. Niech
e
1
;:::;
e
m
b¦dzie baz¡ standardow¡
K
m
.
Stopniem
wektora
0
6
=
v
=
m
P
i
=1
e
1
v
i
2
K
m
nazwijmy liczb¦ deg
v
:= max
f
i
2
1
;m : v
i
6
= 0
g
;
dodatkowo przyjmijmy deg
v
= 0 dla
v
=
0
. Baz¦
v
1
;:::;
v
r
podprzestrzeni
f
0
g
6
=
W
K
m
b¦dziemy nazywa¢
baz¡ standardow¡
W, je»eli:
(a) stopnie
d
i
= deg
v
i
speªniaj¡ nierówno±ci
d
1
< ::: < d
r
;
(b)
v
d
i
j
=
ij
dla
i;j
2
1
;r.
Fakt 1
. Ka»da podprzestrze«
f
0
g
6
=
W
K
m
ma, i to dokªadnie jedn¡, baz¦
standardow¡.
Indukcja wzgl¦dem r = dimW: Dla r = 1 teza jest trywialna. Zaªó»my, »e dimW = r > 1
i »e twierdzenie jest prawdziwe dla wymiaru r 1. Niech d
1
= min
f
deg
v
: 0
6
=
v
2
W
g
.
Jasne, »e istnieje dokªadnie jeden
w
2
W taki, »e deg
w
= d
1
oraz w
d
1
= 1; przy tym
W jest sum¡ prost¡
hw i
i
f
W :=
fv
2
W : v
d
1
= 0
g
, gdy» dla
v
2
W mamy
v
w
2
f
W
,
= v
d
1
. Dla zako«czenia dowodu wystarczy teraz zauwa»y¢, »e
v
1
;:::;
v
r
jest baz¡ standard. W
,
v
1
=
w
oraz
v
2
;:::;
v
r
jest baz¡ standard.
f
W
.
15
Przykªad
. Ka»da 3-wymiarowa podprzestrze« W
K
4
ma dokªadnie jedn¡ z czterech
poni»szych postaci (i zale»y od co najwy»ej trzech parametrów a;b;c
2
K
):
W = ker[1;a;b;c]; baz¡ standardow¡ W, maj¡c¡ stopnie 2,3,4, s¡ kolumny
2
6
6
4
a b c
1 0 0
0 1 0
0 0 1
3
7
7
5
;
W = ker[0;1;b;c]; baz¡ standardow¡ W, maj¡c¡ stopnie 1,3,4, s¡ kolumny
2
6
6
4
1 0 0
0 b c
0 1 0
0 0 1
3
7
7
5
;
W = ker[0;0;1;c]; baz¡ standardow¡ W, maj¡c¡ stopnie 1,2,4, s¡ kolumny
2
6
6
4
1 0 0
0 1 0
0 0 c
0 0 1
3
7
7
5
;
W = ker[0;0;0;1]; baz¡ standardow¡ W, maj¡c¡ stopnie 1,2,3, s¡ kolumny
2
6
6
4
1 0 0
0 1 0
0 0 1
0 0 0
3
7
7
5
.
Fakt 2
. Niech
v
1
;:::;
v
r
2
K
m
b¦dzie baz¡ standardow¡ podprzestrzeni
im
A
, gdzie 0
6
=
A
2
K
m
n
. Wówczas
A
K
[
0
;:::;
0
|
{z
}
n r
;
v
1
;:::;
v
r
].
Startuj¡c z
A
przeprowadzajmy kolejne redukcje kolumnowe przestrzegaj¡c dwóch zasad:
(K)
nie mog¡ si¦ powtarza¢ numery kolumn kolejnych wyrazów bazowych;
(W
) ka»dy kolejny wyraz bazowy wybieramy z wiersza o numerze maksymalnym,
jaki mo»liwy jest przy speªnieniu warunku (W).
[Wtedy speªnione s¡
a fortiori
zasady (K) i (W) z algorytmu redukcji kolumnowych].
atwo spostrzec, »e po zako«czeniu tej procedury ostatnie
6
= 0 wyrazy kolumn otrzyma-
nej macierzy s¡ samotnikami wierszowymi; zatem po stosownym przestawieniu jej kolumn
(operacja elementarna typu 1
0
) i ich unormowaniu (operacja elementarna typu 2
0
) uzy-
skamy macierz, której niezerowe kolumny tworz¡ baz¦ standardow¡ podprzestrzeni im
A
.
Przykªad
. Dla W := im
2
6
6
4
1 5
2 4
5 3
3 2
3
7
7
5
rachunek
2
6
6
4
1 5
2 4
5 3
3 2
3
7
7
5
K
2
6
6
6
4
13
2
5
4 4
1
2
3
0 2
3
7
7
7
5
K
2
6
6
4
13
2
44
4 28
1
2
0
0 2
3
7
7
5
K
2
6
6
4
13 22
8 14
1 0
0 1
3
7
7
5
pokazuje, »e baz¡ standardow¡ jest zestaw kolumn ostatniej macierzy. To samo dostaniemy
wybieraj¡c w pierwszym kroku 3 zamiast 2 :
2
6
6
4
1 5
2 4
5 3
3 2
3
7
7
5
K
2
6
6
4
1
13
3
2
8
3
5
1
3
3 0
3
7
7
5
K
2
6
6
4
1 13
2 8
5 1
3 0
3
7
7
5
K
2
6
6
4
66 13
42 8
0 1
3 0
3
7
7
5
K
2
6
6
4
13 22
8 14
1 0
0 1
3
7
7
5
.
Wniosek 1
. Niech
W b¦dzie przestrzeni¡ wektorow¡ oraz niech
v
i
;
w
i
2
V
dla
i
2
1
;n. Wówczas (por. Uwag¦ ze strony 6)
h v
1
;:::;
v
n
i
=
h w
1
;:::;
w
n
i
)
(
v
1
;:::;
v
n
)
(
w
1
;:::;
w
n
).
Mo»emy zakªada¢, »e V =
K
m
; niech
u
1
;:::;
u
r
b¦dzie baz¡ standardow¡ podprzestrzeni
hv
1
;:::;
v
n
i
=
hw
1
;:::;
w
n
i
. Wtedy Fakt 2. daje
v
1
;:::;
v
n
K
0
;:::;
0
;
u
1
;:::;
u
r
oraz
w
1
;:::;
w
n
K
0
;:::;
0
;
u
1
;:::;
u
r
, sk¡d natychmiast wynika teza.
16
Wniosek 2
. Gdy
A
2
K
mn
, wtedy
rk
A
=
m
)
A
K
[
0
;
I
m
]
oraz
rk
A
=
n
)
A
W
"
0
I
n
#
.
W szczególno±ci je±li macierz
A
2
K
n
n
jest nieosobliwa, to
A
K
I
n
i
A
W
I
n
.
Wniosek 3
. Ka»da klasa równowa»no±ci relacji
K
w
K
m
n
zawiera dokªad-
nie jedn¡ macierz postaci [
0
;:::;
0
;
v
1
;:::;
v
r
], gdzie
v
1
;:::;
v
r
jest ukªadem
niezerowych wektorów w
K
m
, speªniaj¡cych powy»sze warunki (a) i (b).
Macierz powy»szej postaci nazywana jest
macierz¡ zredukowan¡ kolumnowo do postaci
trójk¡tnej
, w skrócie KZT-
macierz¡
; posta¢ t¦ mo»na w peªni scharakteryzowa¢ nast¦pu-
j¡cymi warunkami,które s¡ oczywi±cie mocniejsze od warunków de niuj¡cych KZ-macierz:
(1) kolumny macierzy s¡ ustawione w kolejno±ci rosn¡cych stopni;
(2) w ka»dej
6
= 0 kolumnie ostatni
6
= 0 wyraz jest jedynk¡ i samotnikiem wierszowym.
Wniosek 4
. Grassmannian
G
r
(
K
m
) (którego elementami s¡
r-wymiarowe
podprzestrzenie
W
K
m
,
r
¬
m) ma rozkªad komórkowy
S
K(d
1
;:::;d
r
),
gdzie
1
¬
d
1
< ::: < d
r
¬
m,
K(d
1
;:::;d
r
) :=
f
W
K
m
: baza standardowa
W ma stopnie d
1
;:::;d
r
g
.
atwo sprawdzi¢, »e
K(d
1
;:::;d
r
) jako podprzestrze« topologiczna
K
n
jest
homeomor czna z
K
N
, gdzie
N =
r
P
k
=1
(
d
k
k) = d
1
+
::: + d
r
1
2
r(r + 1).
17
Wyszukiwarka
Podobne podstrony:
więcej podobnych podstron