WIADOMOŚCI WSTĘPNE
1. PODSTAWOWE STRUKTURY ALGEBRAICZNE
Definicja Działaniem 2-argumentowym na niepustym zbiorze A nazywamy dowolne odwzorowanie Wartość f(a,b) nazywamy rezultatem (wynikiem) działania f na elementach a, b ze zbioru A.
Jeśli f jest działaniem w A, X ⊆ A oraz dla dowolnych elementów x, y ∈ X f(x,y) ∈ X, to mówimy, że zbiór X jest zamknięty ze względu na działanie f. Możemy wtedy zdefiniować działanie g na X, g(x,y) := f(x,y), dla x, y ∈ X.
Przykłady : + , −, ⋅ są działaniami w zbiorze liczb rzeczywistych R. Podzbiór N zbioru R jest zamknięty ze względu na + oraz ⋅ a nie jest zamknięty ze względu na −.
Definicja Grupą nazywamy parę (G,•), gdzie G jest niepustym zbiorem a • jest działaniem 2-argumentowym w G, takim że następujące warunki są spełnione:
G1. x•(y•z) = (x•y) •z (łączność •)
G2. x•e = e•x = x (istnienie elementu neutralnego)
G3. x•x-1 = x-1•x = e (istnienie elementu odwrotnego).
Przykłady : (R,+), (Q,+), (Z,+), (r-{0}, ⋅), ({x∈R; x > 0}, ⋅}
1.6. Definicja . Niech (G,•) będzie grupą a H podzbiorem G, takim że e ∈ H oraz dla dowolnych x, y ∈ H element x•y ∈ H. Jeżeli H wraz z działaniem • grupy (G,•) jest grupą to mówimy, że (H,•) jest podgrupą grupy (G,•).
TWIERDZENIE. Niech (G,•) będzie grupą a H niepustym podzbiorem G. (H,•) jest podgrupą grupy (G,•) wtedy i tylko wtedy gdy dla dowolnych x, y ∈ H element x•y-1 ∈ H.
1.7. DEFINICJA. Ciałem nazywamy trójkę (K,+, ⋅), taką że
C1. (K,+) jest grupą przemienną z elementem neutralnym 0.
C2. (K-{0},⋅) jest grupą przemienną .
C2. x ⋅ (y + z) = x ⋅ y + x ⋅ z (rozdzielność mnożenia względem dodawania).
1.8. PRZYKŁADY. Ciało liczb rzeczywistych (R, +, ⋅), ciało liczb wymiernych (Q,+, ⋅).
2. GRUPY PERMUTACJI
Niech A = {1, ...,n} oraz Sn := {f: A → A, f odwracalne}. Wtedy (Sn, •) gdzie • jest składanie odwzorowań jest grupą. Nazywamy ją grupą permutacji zbioru n-elementowego A. Niech a, b ∈ A oraz a ≠ b. Transpozycją nazywamy permutację τ ∈ Sn zdefiniowaną następująco
τ(x) = . Permutację τ oznaczamy <a,b>.
TWIERDZENIE. Każdą permutację ze zbioru Sn można przedstawić jako złożenie skończonej liczby transpozycji.
TWIERDZENIE. Każdą transpozycję można przedstawić jako złożenie nieparzystej liczby transpozycji wyrazów sąsiednich ( <k,k+1>)
LEMAT. Niech P: Sn → Z, P(σ) :=
Wtedy dla dowolnej permutacji σ i dowolnej transpozycji τ ze zbioru Sn , P(σ•τ) = − P(σ).
TWIERDZENIE. Niech σ ∈ Sn. Jeśli σ =
oraz σ =
, gdzie
są transpozycjami z Sn, to (-1)r = (-1)s.
DEFINICJA. Niech σ ∈ Sn i σ =
gdzie
są transpozycjami z Sn. Liczbę (-1)r nazywamy znakiem permutacji σ i oznaczamy sgnσ. Jeśli sgnσ = 1 to permutację σ nazywamy permutacją parzystą, Jeśli sgnσ = -1 to permutację σ nazywamy permutacją nieparzystą,
3. LICZBY ZESPOLONE
DEFINICJA Liczbą zespoloną nazywamy uporządkowaną parę liczb rzeczywistych. Zbiór wszystkich liczb zespolonych oznaczamy przez C. Mamy zatem C:= {z=(x,y) : x,y ∈ R}. Niech z1 = (x1,y1), z2 = (x2,y2) będą liczbami zespolonymi.
Sumę liczb zespolonych określamy wzorem: z1 + z2 := (x1 + x2, y1 + y2).
Iloczyn liczb zespolonych określamy wzorem: z1 ⋅ z2 := (x1x2 - y1y2, x1y2 + x2y1).
FAKT (Własności działań w zbiorze liczb zespolonych). Niech z = (x,y) oraz z1, z2, z3 będą dowolnymi liczbami zespolonymi. Wtedy
dodawanie liczb zespolonych jest przemienne, tzn. z1 + z2 = z2 + z1;
dodawanie liczb zespolonych jest łączne, tzn. (z1 + z2) + z3 = z1 + (z2 + z3);
liczba zespolona 0:= (0,0) jest elementem neutralnym dodawania, tzn. 0 + z =z;
dla każdej liczby zespolonej z istnieje liczba -z := (-x,-y), taka że z + (-z) = 0;
mnożenie liczb zespolonych jest przemienne, tzn. z1⋅z2 = z2 ⋅z1;
mnożenie liczb zespolonych jest łączne, tzn. (z1⋅z2)⋅z3 = z1⋅(z2⋅z3);
liczba zespolona 1 := (1,0) jest elementem neutralnym mnożenia, tzn. z⋅1 = z;
dla każdej liczby zespolonej z ≠ 0 istnieje liczba z-1 :=
odwrotna do niej, tj. taka że z-1⋅z = 1;
mnożenie liczb zespolonych jest rozdzielne względem dodawania, tzn. z1⋅(z2 + z3) = z1⋅z2 + z1⋅z3.
FAKT. (C, +, ⋅) jest ciałem.
3.3. Liczbę zespoloną (0,1) nazywamy jednostką urojoną i oznaczamy ją przez i; i := (0,1). Liczba i jest pierwiastkiem równania x2 + 1 = 0. Każdą liczbę zespoloną postaci (a,0) utożsamiamy z liczbą rzeczywistą a. Po tym utożsamieniu każdą liczbę zespoloną (x,y) można jednoznacznie przedstawić w postaci z = x + yi, gdzie x, y ∈R. Ten sposób przedstawienia liczb zespolonych nazywa się ich postacią algebraiczną.
MACIERZE I WYZNACZNIKI
1. OPERACJE NA MACIERZACH.
1.1. DEFINICJA. Niech K = (K, +, ⋅) będzie ciałem. Macierzą typu m×n nad K lub m×n - macierzą nad K nazywamy funkcję A: {1, ..., m} × {1, ..., n} → K.
Najczęściej zamiast A(i,j) piszemy aij dla i ∈ {1, ..., m} oraz j ∈ {1, ..., n} i przedstawiamy macierz A w postaci tablicy
A =
Wartości aij nazywamy wyrazami macierzy A. Często piszemy krócej A =
lub A =
. Symbolem
będziemy oznaczali zbiór wszystkich macierzy typu m × n nad K.
Niech A ∈
oraz niech i1, ...,ip ∈ {1, ..., m} i j1, ...,jr ∈ {1, ..., n}. Wtedy p × r macierz B, taką że B(k,l) := A(ik,jl) dla k = 1, ...,p, j = 1,... ,r oznaczamy symbolem . W przypadku gdy (i1,...,ip) = (1,...,m) zamiast piszemy , a gdy (j1,...,jr) = (1,...,n) zamiast piszemy . Jeśli 1 ≤ i1 < ... <ip ≤ m oraz 1 ≤ j1 < ... <jr ≤ n, to nazywa się podmacierzą macierzy A. Podmacierze typu 1 × n nazywamy wierszami a podmacierze typu m × 1 kolumnami macierzy A. Oznaczamy je odpowiednio: cj(A) = A(j) = j-ta kolumna macierzy A oraz ri(A) = A(i) = [ai1...ain] i-ty wiersz macierzy A.
Niech A ∈ , B ∈ . Wtedy symbolem AB będziemy oznaczali m × (n + p)-macierz taką że cj(AB) = .
Niech A ∈ , C ∈ . Wtedy symbolem oznaczamy (m + r) × n-macierz, taką że ri() = .
Każdą macierz n × n nazywamy macierzą kwadratową. Wyrazy a11, ...,ann tworzą główną przekątną macierzy A.
Macierz kwadratową której wszystkie wyrazy poza główną przekątną są równe 0 nazywamy macierzą diagonalną. Macierz diagonalną mającą wyrazy a1, ..., an na głównej przekątnej oznaczamy symbolem diag(a1, ..., an).
1.2. DEFINICJA. Niech A, B ∈ , c ∈ K. Sumą macierz A i B nazywamy m × n macierz A + B, (A + B)(i,j) := A(i.j) + B(i,j), i = 1,...,m, j = 1, ...,n. Iloczynem macierzy A przez c nazywamy m × n macierz cA, cA(i,j) := cA(i,j), i = 1,...,m, j = 1, ...,n.
Symbolem lub 0 oznaczamy macierz której wszystkie wyrazy są równe 0.
TWIERDZENIE. Niech A, B, C ∈ , a, b ∈ K. Wtedy:
0 + A = A + 0, A + (-1)A = 0,
(A + B) + C = A + (B + C),
A + B = B + A,
1A = A,
a(bA) = (ab)A,
(a + b)A = aA + bA, a(A + B) = aA +aB.
TWIERDZENIE. (,+) jest grupą przemienną.
Macierz (-1)A oznaczamy -A.
1.3. DEFINICJA. Niech A ∈ , B ∈ . Iloczynem macierzy A i B nazywamy macierz C typu m × p nad K, taką że C(i,j) = , dla i = 1 ,..., m, j = 1 ,..., p. Iloczyn macierzy A i B oznaczamy symbolem AB.
TWIERDZENIE. Niech A, A'∈ , B, B' ∈ , C ∈ , a ∈ K. Wtedy
(AB)C = A(BC),
(A + A')B = AB + A'B oraz A(B + B') = AB + AB',
(aA)B = A(aB) = a(AB),
ImA = A = AIn , gdzie In ∈ oraz In = diag(1,...,1).
1.4. TWIERDZENIE. Jeśli A ∈ i B ∈ , to
cj(AB) = Acj(B) dla j = 1, ..., p,
ri(AB) = ri(A)B dla i = 1, ..., m.
WNIOSEK. Jeśli A ∈ i B ∈ , to
cj(AB) = dla j = 1, ..., p,
ri(AB) = dla i = 1, ..., m.
TWIERDZENIE. Niech A ∈ oraz B ∈ . Jeśli {k1, ..., kr} ∪ {l1,...,lp} = {1, ...,n}, gdzie n = p + r, to AB = .
1.5. DEFINICJA. Niech A ∈ . Macierz A nazywamy macierzą odwracalną, jeśli istnieje macierz B ∈ , taka że AB = BA = In. Macierz B spełniającą powyższy warunek nazywamy macierzą odwrotną do A i oznaczamy symbolem A-1.
TWIERDZENIE. Zbiór wszystkich odwracalnych macierzy n × n nad ciałem K tworzy grupę ze względu na mnożenie macierzy oraz:
macierz In jest macierzą odwracalną i (In)-1 = In,
jeśli A jest macierzą odwracalną to A-1 jest macierzą odwracalną i (A-1)-1 = A,
jeśli A, B są odwracalnymi macierzami n × n nad ciałem K, to AB jest macierzą odwracalną i (AB)-1= B-1A-1.
1.6. DEFINICJA. Niech A ∈ . Macierzą transponowaną do macierzy A nazywamy macierz AT∈ , taką że AT(i,j) := A(j,i) dla i = 1, ...,n, j = 1,..., m. Odwzorowanie przyporządkowujące macierzy A macierz AT nazywamy transpozycją.
TWIERDZENIE. Niech A , B ∈ , c ∈ K. Wtedy
(A + B)T = AT + BT,
(cA)T = cAT,
(AT)T = A,
IT = I.
TWIERDZENIE. Niech A ∈ oraz B ∈ . Wtedy (AB)T = BTAT.
TWIERDZENIE. Jeśli macierz A jest odwracalna, to macierz AT jest również odwracalna i (AT)-1 = (A-1)T.
2. Operacje Elementarne
2.1. DEFINICJA. Elementarnymi operacjami na wierszach macierzy A o współczynnikach w ciele K nazywamy:
mnożenie dowolnego wiersza macierzy przez niezerowy element ciała,
dodawanie do dowolnego wiersza macierzy dowolnego innego pomnożonego przez dowolny element ciała K,
zamianę dwóch różnych wierszy miejscami .
Będziemy posługiwali się następującymi oznaczeniami:
A A' oznacza, że macierz A' powstaje z macierzy A przez pomnożenie i-tego wiersza przez element a ∈ K, (a ≠ 0)
A A' oznacza, że macierz A' powstała z macierzy A w wyniku dodania do i-tego wiersza macierzy A wiersza k-tego A pomnożonego przez a ∈ K, gdzie i ≠ k,
A A' oznacza, że macierz A' powstała z macierzy A przez zamianę miejscami wierszy i-tego oraz k-tego (gdzie i ≠ k).
Analogicznie definiujemy operacje elementarne na kolumnach A.
TWIERDZENIE. Dla każdej operacji elementarnej istnieje odwrotna do niej operacja będąca operacją elementarną tego samego typu.
2.2. TWIERDZENIE. Niech f będzie złożeniem skończonej liczby operacji elementarnych na wierszach oraz g będzie złożeniem skończonej liczby operacji elementarnych na kolumnach macierzy. Wtedy
f(AB) = f(A)B oraz g(AB) =Ag(B),
dla dowolnych macierzy A i B (oczywiście jeśli zdefiniowany jest iloczyn AB).
WNIOSEK. Niech A ∈ oraz niech f będzie złożeniem skończonej liczby operacji elementarnych na wierszach a g będzie złożeniem skończonej liczby operacji elementarnych na kolumnach macierzy. Wtedy
f(A) = NA, gdzie N = f(Im)
g(A) = AN, gdzie N = g(In).
WNIOSEK. Jeśli f jest złożeniem skończonej liczby operacji elementarnych na wierszach i N = f(I), to N jest macierzą odwracalną i N-1 = f-1(I).
2.3. TWIERDZENIE. Niech f będzie operacją elementarną na wierszach a g będzie operacją elementarną na kolumnach macierzy. Wtedy jeśli A = (B C), to f(A) = (f(B)f(C)) oraz jeśli A =
TWIERDZENIE. Niech A ∈ oraz niech f będzie złożeniem skończonej liczby operacji elementarnych na wierszach. Jeśli f(AI) = (IB), to B = A-1. Podobnie jeśli g jest złożeniem skończonej liczby operacji elementarnych na kolumnach i g, to B = A-1.
2.4 DEFINICJA. Macierzą elementarną nazywamy każdą macierz otrzymaną w wyniku wykonania jednej elementarnej operacji na wierszach macierzy jednostkowej.
TWIERDZENIE. Niech E będzie macierzą elementarną. Wtedy
E jest macierzą odwracalną oraz E-1 jest macierzą elementarną,
ET jest macierzą elementarną.
3. MACIERZE RÓWNOWAŻNE
3.1.DEFINICJA. Mówimy, że macierz A' jest wierszowo równoważna (kolumnowo równoważna) macierzy A i piszemy A' ≈w A (A' ≈k A), jeśli A' można otrzymać z A przy pomocy skończonej liczby operacji elementarnych na wierszach (kolumnach).
TWIERDZENIE. Relacje ≈w i ≈k są relacjami równoważności na zbiorze .
TWIERDZENIE. A' ≈w A ⇔ istnieje skończony ciąg E1, ..., Ek macierzy elementarnych, takich że A' = E1...EkA. Podobnie, A' ≈k A ⇔ istnieje skończony ciąg E1, ..., Ek macierzy elementarnych, takich że A' = AE1...Ek.
3.2. DEFINICJA. Niech A ∈ . Macierz A nazywamy macierzą wierszowo zredukowaną, jeśli istnieje liczba całkowita r, 1 ≤ r ≤ m, oraz liczby całkowite k1, ... , kr , 1 ≤ k1 < ... < kr ≤ n, takie że
,
jeśli r < m, to A(r+1,...,m) = 0.
TWIERDZENIE. Jeśli A jest odwracalną macierzą wierszowo zredukowaną to A = I.
TWIERDZENIE. Każda niezerowa macierz A ∈ jest wierszowo równoważna pewnej macierzy wierszowo zredukowanej.
3.3. TWIERDZENIE. Niech A ∈ .Wtedy następujące warunki są równoważne:
A jest macierzą odwracalną,
A jest wierszowo równoważna macierzy jednostkowej,
A jest iloczynem macierzy elementarnych,
A jest kolumnowo równoważna macierzy jednostkowej.
4. WYZNACZNIKI
4.1. DEFINICJA. Niech A ∈ . Wyznacznikiem macierzy A nazywamy element ciała K, DetA :=
LEMAT. Niech A ∈ . Wtedy DetA =
TWIERDZENIE. Jeśli A ∈ , to DetA = DetAT.
4.2. TWIERDZENIE. Niech A ∈ , α ∈ Sn, a ∈ K. Wtedy:
DetA(α(1),..., α(n)) = sgnαDetA,
Det(A(1),...,aA(j),...,A(n)) = aDet(A(1),...,A(j),...,A(n)),
Det(A(1),..., A(j)+A'(j), ...,A(n)) = Det(A(1),..., A(j), ...,A(n)) + Det(A(1),..., A'(j), ...,A(n)),
Jeśli macierz A ma dwie jednakowe kolumny (wiersze), to DetA = 0.
WNIOSEK.
Jeśli w macierzy A zmienimy kolejność kolumn (wierszy), to wyznacznik zmieni znak.
Wyznacznik macierzy nie ulegnie zmianie jeśli do dowolnej kolumny macierzy dodamy inną pomnożoną przez dowolny element ciała.
TWIERDZENIE. Niech A, B ∈ . Wtedy Det(AB) = DetADetB.
4.3. DEFINICJA. Dopełnieniem algebraicznym wyrazu aij macierzy A nazywamy element ciała K oznaczany Aij, Aij := (-1)i+jDet
. Macierz nazywamy się macierzą dopełnień macierzy A i oznaczamy AD.
LEMAT. Niech A = [aij]nn oraz ri(A) = [0,...,0,aij,0,...,0]. Wtedy
DetA = aijAij = aij(-1)i+jDet
.
TWIERDZENIE. Niech A = [aij]nn. Wtedy dla dowolnego i, j = 1, ...,n
DetA = ai1Ai1 + ... + ainAin, (rozwinięcie Laplace'a wyznacznika A względem i-tego wiersza)
DetA = a1jA1j + ... + anjAnj, (rozwinięcie Laplace'a wyznacznika A względem j-tej kolumny).
4.4. TWIERDZENIE. Niech A = [aij]nn. Wtedy macierz A jest odwracalna wtedy i tylko wtedy gdy DetA ≠0. Ponadto, jeśli DetA ≠0, to A-1 = AD(DetA)-1, oraz DetA-1 = (DetA)-1.
Układy Równań liniowych
1. DEFINICJA. Układem m równań liniowych z n niewiadomymi o współczynnikach w ciele K nazywamy każdy układ równań postaci:
(*)
,
gdzie aij , bi ∈ K, dla i =1,..., m, j = 1, ..., n.
Jeśli dla dowolnego i, bi = 0, to układ (*) nazywamy układem jednorodnym.
Dowolny ciąg x1, ...,xn elementów z ciała K spełniający (*) nazywamy rozwiązaniem układu.
Macierz A =
nazywamy macierzą układu, macierz B =
macierzą wyrazów wolnych, a macierz (AB) macierzą rozszerzoną układu.
Rozw(AB) oznacza zbiór wszystkich rozwiązań układu równań liniowych o macierzy rozszerzonej (AB), (u.r.l. (AB)).
Ciąg (x1, ...,xn) jest rozwiązaniem u.r.l. (AB) ⇔ macierz [x1, ...,xn]T jest rozwiązaniem równania macierzowego AX = B.
2. Będziemy teraz rozwiązywać równania macierzowe postaci AX = B, gdzie A ∈ , oraz B ∈ Oczywiste jest że szukana macierz X ∈
Jeśli q = 1, to otrzymujemy układ równań liniowych.
TWIERDZENIE. Niech A, A'∈ , B, B'∈ Jeśli A'B' ≈w AB, to macierz X jest rozwiązaniem równania AX = B wtedy i tylko wtedy, gdy X jest rozwiązaniem równania A'X = B'.
WNIOSEK. Jeśli A'B' ≈w AB, to Rozw(A'B' ) = Rozw(AB).
3. Niech A ∈ , B ∈ , oraz niech AB ≈w A'B', gdzie macierz A' jest wierszowo zredukowana. Niech r będzie liczbą niezerowych wierszy macierzy A'. Wtedy istnieją 1 ≤ j1 < ... < jr ≤ n, takie że Jeśli r = n, to 1= j1, ..., jn = n. Jeśli r < n to p = n-r oraz niech k1, ...,kp będą ustawionymi w porządku rosnącym numerami pozostałych kolumn A', tj. 1 ≤ k1 < ... < kp ≤ n, oraz {j1 ,... ,jr }∪ { k1 , ... , kp} = {1, ... ,n}.
TWIERDZENIE. Przy powyższych oznaczeniach otrzymujemy:
I. Jeśli r < m i B'(r+1,...,m) ≠ 0, to równanie AX = B nie ma rozwiązań.
II. Jeśli r = m lub r < m i B'(r+1,...,m) ≠ 0, to równanie AX = B ma conajmniej jedno rozwiązanie, przy czym:
1. Jeśli r = n, to rozwiązanie jest dokładnie jedno i ma postać X = B'(1,...,n).
2. Jeśli r < n, to dla dowolnej p × q macierzy S o współczynnikach w K macierz X zdefiniowana następująco: jest rozwiązaniem AX = B i nie ma innych rozwiązań.
4. TWIERDZENIE (Cramera). Niech A = [aij]nn oraz b ∈ . Układ równań Ax = b ma dokładnie jedno rozwiązanie wtedy i tylko wtedy gdy DetA ≠0. Wtedy x = [x1,...xn]T, xj = DetBj(DetA)-1, gdzie Bj = (A(1),...,A(j-1),b,A(j+1),...,A(n)) jest rozwiązaniem tego układu.
1
3