JCI: Algebra

Zagadnienia omówione na wykładzie

04.10.2016: Grupy - cz. I

Pojęcia działania binarnego. Łączność, przemienność
Pojęcie grupy
Przykłady grup. Grupa $C_n = (\{0,\ldots,n-1\},\oplus)$, gdzie $x \oplus y = (x+y) \quad \mathrm{mod} \quad n$.
Tw. W grupie istnieje dokładnie jeden element neutralny. Dla każdego elementu $x$ istnieje dokładnie jeden element odwrotny. Oznaczany jest on symbolem $x^{-1}$
Pojęcie izomorfizmu grup

05.10.2016: Grupy - cz. II

Tw. Jeśli $|\mathcal{G}|=2$, to $\mathcal{G}$ jest izomorficzna z $C_2$.
Tw. (1) $(a^{-1})^{-1} = a$; (2) $(a\cdot b)^{-1} = b^{-1} a^{-1}$.
Def. $(G,\cdot) \times (H,+) = (G\times H, *)$, gdzie $(a,b)*(c,d) = (a\cdot c,b+d)$.
Tw. Jeśli $(G,\cdot)$ i $(H,+)$ są grupami to $(G,\cdot) \times (H,+)$ też jest grupą.
Pojęcie rzędu elementu w grupie $$ ord(x) = \begin{cases} \min\{k\geq 1: x^k =e\} &: (\exists k\geq 1)(x^k = e) \\ \infty &: (\forall k\geq 1)(x^k \neq e) \end{cases} $$
Grupa $Sym(X)$ permutacji zbioru $X$; $S_n=Sym(\{1,2,\ldots,n\})$.
Jeśli $n\geq 3$ to grupa $S_n$ jest nieprzemienna.
Pojęcie homomorfizmu, monomorfizmu i epimorfizmu grup.

Zadanie do zrobienia w weekend: nauczyć się alfabetu greckiego:
$\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$, $\zeta$, $\eta$, $\theta$, $\iota$, $\kappa$, $\lambda$, $\mu$, $\nu$, $\xi$, $\pi$, $\rho$, $\sigma$, $\tau$, $\upsilon$, $\phi$, $\chi$, $\psi$, $\omega$;
$A$, $B$, $\Gamma$, $\Delta$, $E$, $Z$, $H$, $\Theta$, $I$, $K$, $\Lambda$, $M$, $N$, $\Xi$, $\Pi$, $R$, $\Sigma$, $T$, $\Upsilon$, $\Phi$, $X$, $\Psi$, $\Omega$;

11.10.2016: Grupy, pierścienie i ciała

Tw. Niech $n\geq 1$ oraz $\phi_n(x) = x \mod n$. Wtedy $\phi_n$ jest homomorfizmem z $(\mathbf{Z},+)$ na grupę $C_n$.
Pojęcie pierścienia i podstawowe własności działań w pierścieniach: $0\cdot x = x \cdot 0 = 0$, $(-x)\cdot y = -(x\cdot y)$, $(x+y)^2 = x^2 + x\cdot y + y\cdot x + y^2$
Pojęcie dzielnika zera
Pojęcie ciała liczbowego.
Tw. W ciele nie ma dzielników zera.
Tw (na razie bez dowodu). Pierścień $\mathbf{Z}_n$ jest ciałem wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą.
Rozwiązywanie prostych równań liniowych w ciałach $\mathbf{R}$, $\mathbf{Z}_5$ i $\mathbf{Z}_7$.

12.10.2016: Pierścienie i ciała

Rozwiązywanie prostych równań liniowych w ciałach skończonych za pomocą wyznaczników.
Rozwiązywanie równań kwadratowych w takich ciałach $K$, w których $1_K+1_K \neq 0_K$:
$$ a x^2 + b x + c = \ldots = a\left(\left(x+\frac{b}{2 a}\right)^2 - \frac{b^2 - 4 a c}{(2 a^2)^2}\right) $$
Uwaga: $2_K = 1_K+1_K$; $4_K = 1_K+1_K+1_K+1_K$.
Tw. Niech $n\geq 1$ oraz $\phi_n(x) = x \mod n$. Wtedy $\phi_n$ jest homomorfizmem z $(\mathbf{Z},+,\cdot)$ na pierścień $\mathbf{Z}_n$.
Przykład zastosowania pojęcia homomorfizmu: $$ \phi_3\left(\sum_{k=0}^{n} a_k 10^k\right) = \ldots = \phi_3\left(\sum_{k=0}^{n} a_k\right) ~, $$ zatem $3|(a_k a_{k-1}\ldots a_1a_0)_{(10)}$ wtedy i tylko wtedy, gdy $3|(a_0+a_1+\ldots+a_k)$.
Wniosek: $9|(a_k a_{k-1}\ldots a_1a_0)_{(10)}$ wtedy i tylko wtedy, gdy $9|(a_0+a_1+\ldots+a_k)$
Wniosek: $11|(a_k a_{k-1}\ldots a_1a_0)_{(10)}$ wtedy i tylko wtedy, gdy $11|(a_0-a_1+a_2-a_3 + \ldots+(-1)^ka_k)$

18.10.2016: Liczby naturalne - I

ZASADA MINIMUM: każdy niepusty podzbiór $\mathbb{N}$ ma element najmniejszy.
ZASADA INDUKCJI MATEMATYCZNEJ: Jeśli $A \subseteq \mathbb{N}$, $0\in A$ oraz $(\forall n)(n\in A \to n+1\in A)$, to $A = \mathbb{N}$.
Tw. Z Zasady Minimum wynika Zasada Indukcji Matematycznej
Tw. Nie istnieje ciąg liczb naturalnych $(a_n)$ taki, że $(\forall n\in\mathbb{N})(a_{n+1} \lt a_n)$.
Tw (O dzieleniu z resztą) Jeśli $n\in\mathbb{N}$, $n\geq 1$ oraz $x \in \mathbb{Z}$ to istnieją liczby $q\in\mathbb{Z}$ i $r \in \mathbb{N}$ takie, że $x = q\cdot n + r$ oraz $0 \leq r \lt n$.
Def. $NWD(a,b) = \max\{k\in\mathbb{N}: k|a \land k|b\}$
Tw. Jeśli $a,b \in \mathbb{Z}$ oraz $a\neq 0$ lub $b\neq 0$ to istnieją takie liczby całkowite $X,Y$, że $$ a\cdot X + b \cdot Y = NDW(a,b)~.$$
Uwaga: $NWD(0,0)$ nie jest określone; jeśli $a\neq 0$ to $NWD(a,0) = |a|$
Tw. $\mathbb{Z}_n$ jest ciałem wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą.
Tw. Załóżmy, że $a,b,q,r \in \mathbb{Z}$ oraz $a = q\cdot b + r$. Wtedy $NWD(a,b) = NWD(b,r)$
Przykład: NWD(21,13) = NWD(13,8) = NWD(8,5) = NWD(5,3) = NWD(3,2) = NWD(2,1) = 1
Przykład c.d.: 1 = 3 - 2 = 3 - (5 - 3) = 2*3 - 5 = 2*(8-5) - 5 = 2*8 - 3*5 = 2*8 - 3*(13-8) = 5*8-2*13 = 5*(21-13)-3*13 = 5*21 + (-8)*13

Zagadka: podczas wylicznia NWD(21,13) pojawiły się następujące liczby: 1, 1, 2, 3, 5, 8, 13, 21. Co to jest za ciąg? Czy potrafisz sformułować jakąś hipotezę?

19.10.2016: Liczby naturalne - II

Algorytm Euklidesa

function NWD(a,b){
  while (a%b<>0){
    [a,b]:= [b,a%b];
  }
  return b;
}

Rozszerzony Algorytm Euklidesa

function ExtNWD(a,b){
  X0=1;Y0=0;
  X1=0;Y1=1;
  while (a%b<>0){
    q:= a/b; //dzielenie całkowito-liczbowe
    [a,b,X0,Y0,X1,Y1]:= [b,a%b, X1,Y1,X0-q*X1,Y0-q*Y1];
  }
  return [b,X1,Y1];
}

Tw. Jeśli $NWD(a,b)=1$ oraz $a|b\cdot c$ to $a|c$.
Tw. Każda liczba $n\geq 2$ dzieli się przez jakąś liczbę pierwszą.
Tw [Euklides] Istnieje nieskończenie wiele liczb pierwszych.
Tw. Każdą liczbę naturalną $n\geq 2$ można przedstawić jednoznacznie w potaci $n = \prod_{i=1}^{k} (p_i)^{\alpha_i}$ dla pewnych liczb pierwszych $p_1 \lt p_2 \lt \ldots \lt p_k$ oraz dodatnich liczb naturalnych $\alpha_1, \ldots \alpha_k$.
Tw. $NWD(\prod_{i=1}^{k} (p_i)^{\alpha_i}, \prod_{i=1}^{k} (p_i)^{\beta_i} = \prod_{i=1}^{k} (p_i)^{\min(\alpha_i,\beta_i)}$.
Def. $NWW(a,b) = \min\{k \gt 0: a|k \land b|k\}$
Tw. $NWW(a,b) = \frac{a\cdot b}{NWD(a,b)}$.

25.10.2016: Liczby zespolone - I

Własności ciała $\mathbb{Q}(\sqrt{2}) = (\{a+b\sqrt{2}: a,b \in \mathbb{Q}\},+,\cdot)$.
Liczby zespolone: $\mathbb{C} =\{a+b\cdot i:a,b\in\mathbb{R}\}$, gdzie $i$ jest takim elemetem, że $i^2=-1$
Dodawanie, mnożenie (patrz aplety) i dzielenie liczb zespolonych: $\frac{1}{a+b\cdot i} = \frac{a}{a^2+b^2} + \frac{-b}{a^2+b^2} \cdot i$
Def: $|a+b\cdot i| = \sqrt{a^2+b^2}$
Tw. Dla dowolnych $z_1,z_2 \in \mathbb{C}$ mamy:
1. $|z_1 \cdot z_2| = |z_2|\cdot |z_2|$
2. $|z_1 + z_2| \leq |z_2| + |z_2|$
Def: $d(z_1,z_2) = |z_1-z_2|$
Tw. Dla dowolnych $z_1,z_2,z_3 \in \mathbb{C}$ mamy:
1. $(d(z_1,z_2) = 0) \equiv (z_1=z_2)$
2. $d(z_1,z_2) = d(z_2,z_1)$
3. $d(z_1,z_2) = d(z_2,z_1)$
4. $d(z_1,z_3) \leq d(z_1,z_2)+d(z_2,z_2)$ (nierówność trójkąta)

26.10.2016: Liczby zespolone - II

Def. (sprzężenie) $\overline{a+b\cdot i} = a-b\cdot i$
Twierdzenie. Dla dowolnych $z, z_1,z_2 \in \mathbb{C}$ mamy:
1. $\overline{} = z$
2. $\overline{z_1 + z_2}$ = $\overline{z_1} + \overline{z_2}$;
3. $\overline{z_1 \cdot z_2}$ = $\overline{z_1} \cdot \overline{z_2}$.
4. $z\cdot\overline{z} = |z|^2$
Wniosek. Jeśli $|z| = 1$ to $z^{-1} = \overline{z}$
Wniosek. Struktura $(\{z\in\mathbb{C}: |z|=1\},\cdot)$ jest grupą
Postać trygonometryczna: $z = |z|(\cos\phi + i\cdot\sin\phi)$
Oznaczenie: $\phi$ jest argumentem liczby $z$, jeśli $z = |z|(\cos\phi + i\cdot\sin\phi)$
Oznaczenie: $Arg(z)$ (argument główny liczby $z$) jest to taki argument $\phi$ liczby $z$, że $0\leq \phi \lt 2\pi$
Oznaczenie $e^{it} = \cos(t) + i \cdot \sin(t)$
Najpiękniejszy(?) wzór matematyczny: $e^{i\pi} + 1 = 0$
Tw (wzór de Moivre'a) $(r_1\cdot e^{i\alpha})\cdot(r_2 \cdot e^{i\beta}) = (r_1\cdot r_2)\cdot e^{i(\alpha+\beta)}$
Tw. $z^n=1$ wtedy i tylko wtedy, gdy $z \in \{\epsilon_{n,k}:k=0,\ldots,n-1\}$, gdzie $$ \epsilon_{n,k} = e^{\frac{2\pi k \cdot i}{n}}~. $$ (patrz aplet Pierwiastki liczby zespolonej)
Obserwacja: $\epsilon_{n,k}\cdot\epsilon_{n,l} = \epsilon_{n,(k+l)\mod n}$
Wniosek: Grupa $(\{z\in\mathbb{C}: z^n=1\},\cdot)$ jest izomorficzna z grupą $C_n$.
Tw. $1+\epsilon_{n,1}+\epsilon_{n,2} + \ldots + \epsilon_{n,n-1}$ = $0$

Wskazówka do rozwiązania zadania 27.5

Zauważamy najpierw, że teza jest równoważna pokazaniu, że $(b!)|(a+1)(a+2)\cdot\ldots\cdot(a+b)$ dla dowolnych $a$, $b$. Analizujemy przejście indukcyjne, czyli zakładamy, że jeśli $a+b=n$ to teza jest prawdziwa. Przechodzimy do przypadku $a+b=n+1$.
Stosujemy indukcję po a. Zastępujemy $a$ przez $a+1$. Chcemy pokazać, że $(b!)|((a+1)+1)((a+1)+2)\cdot\ldots\cdot((a+1)+b)$. A teraz bawimy się tak: $((a+1)+1)((a+1)+2)\cdot\ldots\cdot((a+1)+b)$ = $((a+1)+1)((a+1)+2)\cdot\ldots\cdot(a+b)(a+1)$ + $((a+1)+1)((a+1)+2)\cdot\ldots\cdot(a+b) b$ i przyglądamy się temu wyrażeniu.
Uwaga: to jest zadanie na "indukcję w indukcji"; oczywiście dowód prawdziwości tego faktu jest bardzo prosty, jeśli skorzysta się ze współczynników Newtona.

08.11.2016: Liczby zespolone - III

Pierwiastki z dowolnej liczby zespolonej: jeśli $z = r e^{\alpha i}$ ($r\geq$) to $$ \sqrt[n]{z} = \{\sqrt[n]{r} e^{\frac{\alpha}{n} i} \epsilon_{n,k}: k=0,\ldots,n-1\}~. $$
Definicja ciała liniowo uporządkowanego
Tw. Ciała liczb zespolonych nie można liniowo uporządkować
Pierścień liczb zespolonych Gaussa: $\mathbb{Z}[i] = \{a+b\cdot i: a,b \in \mathbb{Z}\}$
1. Elementy odwracalne: $\mathcal{E}=\{1,-1,i,-i\}$
2. Pojęcie liczby pierwszej w pierścieniu Gaussa
3. Norma elementu: $N(a+bi) = a^2+b^2$
4. Fakt: $N(z_1z_2)= N(z_1)N(z_2)$
5. Elementy odwracalne: $\{1,-1,i,-i\}$
6. Każda liczba $z\in\mathbb{Z}[i]\setminus \mathcal{E}$ jest podzielna przez jakąś liczbę pierwszą

16.11.2016

Liczby Gaussa - c.d

Twierdzenie o dzielemiu z resztą: dla dowolnych $a,b\in\mathbb{Z}[i]$, jeśli $b\neq 0$, to istnieją $p,q \in \mathbb{Z}[i]$ takie, że $a = p\cdot b + q$ oraz $N(q)\lt N(b)$.
Przykład: $(1+i)(1-i) = 2$, zatem $2$ nie jest pierwsza w $\mathbb{Z}[i]$.
Przykład: liczba $3=0\cdot i$ jest pierwsza w $\mathbb{Z}[i]$.
Tw (bez dowodu) Liczba pierwsza $p$ jest liczbą pierwszą w pierścieniu $\mathbb{Z}[i]$ jeśli $p = 4k +3$ dla pewnej liczby naturalnej $k$.

Wielomiany - I

Dziedzina całkowitości: piecień przemienny z jednością, bez dzielników zera
Definicja pierścienia $R[x]$
1. $(\sum_{n=0}^{\infty}a_n X^n)+(\sum_{n=0}^{\infty}b_n X^n) = \sum_{n=0}^{\infty}(a_n+b_n)X^n$
2. $(\sum_{n=0}^{\infty}a_n X^n)\cdot(\sum_{n=0}^{\infty}b_n X^n) = \sum_{n=0}^{\infty} \left(\sum_{k+l=n}(a_k\cdot b_l)\right) X^n$
Def. $\deg(\sum_{n=0}^{\infty}a_n X^n) = \max\{n: a_n\neq 0\}$
Tw. $\deg(w \cdot v) = \deg(w) + \deg(v)$

22.11.2016

Wielomiany - II

Def. $w|v$ wtedy i tlko wtedy, gdy istnieje wielomian $\alpha$ taki, że $v = \alpha\cdot w$
Def. Wielomian $w\in R[x]$ jest nierozkładalny, jeśli $deg(w)\geq 1$ oraz nie istnieją wielomiany $v_1,v_2 \in R[x]$ takie, że $w = v_1\cdot v_2$ oraz $\deg(v_1)\lt\deg(w)$ oraz $\deg(v_1)\lt\deg(w)$.
Fakt: Wielomiany pierwszego stopnia (liniowe) są nierozkładalne
Tw. Każdy wielomian stopnia większego lub równego jeden jest iloczynem wielomianów nierozkładalnych.

Wielomiany nad ciałami

Tw (o dzieleniu) z resztą) Niech $w,v\in K[x]$ oraz $v \neq 0$. Istnieją wtedy wielomiany $q,r\in K[x]$ takie, że $w = q\cdot v + r$ oraz $\deg(q) \lt \deg(v)$
Wniosek: Jeśli $w\in K[x]$, to $w(a)=0$ wtedy i tylko wtedy, gdy $(x-a)|w$
Tw. Jeśli $w\in \CC[x]$ oraz $\deg(w) = n \geq 1$, to istnieją liczby $\alpha_1, \ldots, \alpha_n\in\CC$ oraz liczba $c\in\CC$ takie, że $$ w(x) = c\cdot(x-\alpha_1)\cdot(x-\alpha_2)\cdot\ldots\cdot(x-\alpha_n)~. $$ (jest to prosta konsekwecja Zasadniczego Twierdzenia Algebry)
Tw. Jeśli $w\in \RR[x]$ oraz $\deg(w) = n \geq 1$, to istnieją liczby $\alpha_1, \ldots, \alpha_k\in\RR$ oraz wielomiany moniczne (największy niezerowy współczynniki jest równy 1) $p_1, \ldots, p_m$ stopnia drugiego, o wyróżnikach mniejszych od zera oraz liczba $c\in\RR$, takie, że $$ w(x) = c\cdot(x-\alpha_1)\cdot\ldots\cdot(x-\alpha_n)p_1(x) \cdot \ldots\cdot p_m(x)~. $$ Główna obserwacja wykorzystana w dowodzie: jeśli $w\in \RR[x]$ oraz $z\in\CC$ jest takie, że $w(z)=0$ to również $w(\overline{z})=0$.

Homomorfim indukowany

Niech $R_1$ i $R_2$ będą pierścieniami; rozważamy homomorfizm $\phi:R_1\to R_2$ bedzie homomorfizmem; wtedy funkcja $$ \overline{\phi}(\sum_n a_n x^n) = \sum_n \phi(a_n)x^n $$ jest homomorfizmem z $R_1[x]$ w $R_2[x]$.

23.11.2016

Wielomiany - III

Tw. Każdy wielomian z $\RR[x]$ stopnia nieparzystego ma pierwiastek rzeczywisty.
Rozwiązywanie równań stopnia trzeciego z $\CC[x]$
NWD wielomianów.
Tw. Jeśli wielomian $w \in K[x]$ (K - ciało) jest nierozkładalny, $w|(u\cdot) v$ oraz $\neg(w|u)$ to $u|v$
Twierdzenie o jednoznaczności rozkładu dla $K[x]$, gdy $K$ jest ciałem

Wielomiany z $\ZZ[x]$

Jeśli $w(x) = a_0+a_1x+\ldots+a_nx^n \in \ZZ[x]$, $\mathrm{nwd}(p,q)=1$ oraz $w(\frac{p}{q})=0$ to $p|a_0$ oraz $q|a_n$
Kryterimu Eisensteina nierozkladalności wielomianów w $\ZZ[x]$.

29.11.2016

Wielomiany - IV

Def. Zawartością wielomianu $w(x) = a_0 + a_1 x+\ldots+a_nx^n \in\ZZ[x]\setminus\{0\}$ nazywamy liczbę $z_w = \mathrm{NWD}(a_0,a_1,\ldots,a_n)$.
Def. Wielomian jest pierwotny:jeśli jego zawartość wynosi $1$.
Lemat. Iloczyn wielomianów pierwotnych jest wielomianem pierwotnym
Tw. (Gauss) Wielomian $w\in\ZZ[x]$ jest nierozkładalny w $\ZZ[x]$ wtedy i tylko wtedy, gdy jest nierozkładalny w $\QQ[x]$.
PRÓBNY ALARM.
Def. Charakterystyką ciała $K$ nazywamy liczbę $\chi(K) = \min\{k\in\NN: \underbrace{1+\ldots + 1}_{k} = 0\}$. Jeśli nie ma takiego $k$, że $\underbrace{1+\ldots + 1}_{k} = 0$ to kładziemy $\chi(K)=0$.
Tw. Dla każdego ciała $K$, jeśli $\chi(K)\neq 0$, to $\chi(K)$ jest liczbą pierwszą
Def. Niech $K$ bedzie ciałem o charakterystyce $0$. Dla $w(x) = \sum_{n} a_nx^n \in K[x]$ definiujemy $$ w'(x) = \sum_{n\geq 1} n a_n x^{n-1}~. $$
Tw: $(f\cdot g)' = f'\cdot g + f\cdot g$
Def. Liczba $a$ jest pierwiastkiem $k$-krotnym wielomianu $w$, jeśli $w(x) = (x-a)^v(x)$ oraz $v(a)\neq 0$
Tw. $a$ jest pierwiastkiem $k$-krotnym wielomianu $w$ wtedy i tylko wtedy, gdy $w(a)=0$, $w'(a)=0$, ... , $w^{(k-1)}(a) = 0$ oraz $w^{(k)}(a) \neq 0$
Początek konstrukcji ciała ułamków:
1. Bierzemy dziedzinę całkowitości $(R,+,\cdot)$
2. Na zbiorze $R\times(R\setminus\{0\}$ definiujemy relację $((p_1,q_1)\sim (p_2,q_2)) \equiv (p_1q_2 = p_2q_1)$
3. ZADANIE: Pokaż, że $\sim$ jest relacją równoważności na $R\times(R\setminus\{0\}$
4. Uwaga: intuicja $[(p,q)]_\sim = \frac{p}{q}$
5. c.d.n.

30-11-2016: Pierścienie i przestrzenie wektorowe

Definicja działań na $(R\times(R\setminus\{0\}))/\sim$ i sprawdzenie ich poprawności.
Tw (wniosek z twierdzena Gauss'a). Jeśli $n\in\NN$ to $\sqrt{n}\in\QQ$ wtedy i tylko wtedy, gdy $(\exists k\in\NN)(n =k^2)$.

Przestrzenie wektorowe

Przykłady przestrzeni wektorowych: $\RR^n$, $K^n$, $C([0,1])$
Definicja przestrzeni wektorowej nad ciałem $K$.
Własności: $0\cdot x = 0$, $(-a)\cdot x = -(a\cdot x)$
Def. Liniowa kombinacja elementów $x_1$, ... ,$x_n$: wyrażenie postaci $\sum_{i}^{n} \lambda_i x_i$ dla jakiś $\lambda_1, \ldots, \lambda_n \in K$
Otoczka liniowa zbioru $S$: $$ \span{S} = \{\sum_{i}^{n} \lambda_i x_i: n\in\NN \land x_1,\ldots x_n\in S \land \lambda_1,\ldots, \lambda_n\in K\} $$
Tak wygląda $\span{\{(2,1)\}}$ w $(\ZZ_5)^2$:

Zadanie: Wylicz inne linie w $(\ZZ_5)^2$. Ile jest różnych linii?. Ile jest na nich elementów?
Liniowa niezależność: elementy $x_1$, ... ,$x_n$ są liniowo niezależne, jeśli
$$ (\forall \lambda_1,\ldots\lambda_n\in K)\left( \left(\sum_{i}^{n} \lambda_i x_i=0\right) \to (\lambda_1=\lambda_2 = \ldots = \lambda_n = 0) \right) $$
Przykłady zbiorów liniowo niezależnych
Przykład: $V=\RR^3$, $e_1=(1,0,0)$, $e_2 = (0,1,0), e_3=(0,0,1)$. Zbiór $\{e_1,e_2,e_3\}$ jest maksymalnym zbiorem liniowo niezależnym.

Osobom, które są zainteresowanie głębszym poznaniem liczb całkowitych Gaussa proponuję zapoznanie się z artykułem "THE GAUSSIAN INTEGERS" Keith Conrad'a

06-12-2016: Bazy

Def. Baza: maksymalny w sensie zawierania zbiór liniowo niezależny.
Lemat. Jeśli $E$ jest liniowo niezależny oraz $x\in V\setminus\span{E}$, to $E\cup\{x\}$ jest liniowo niezależny.
Wniosek. Jeśli $E$ jest bazą to $\span{E} = V$.
Tw. (z wykładu ze Wstępu do logiki) Jeśli $A$ jest liniowo niezależny, to istnieje baza $E$ taka, że $A \subseteq E$.
Tw (Steinera o wymianie) Jeśli $\span{S} = V$ oraz $E$ jest liniowo niezależny i skończony to istnieje $S_1 \subseteq S$ taki, że $|S_1|=|E|$ oraz $\span{E\cup(S\setminus S_1)} = V$.
Wniosek. Jeśli $V$ ma bazę mocy $n$, to dowolna inna baza $V$ jest mocy $n$.
Def. $dim(V)$= moc bazy przestrzeni $V$.
Def. Ciąg $(e_1,\ldots,e_n)$ jest bazą uporządkowaną jeśli $\{e_1,\ldots,e_n\}$ jest bazą.
Def. Jeśli $\mathcal{E} = (e_1,\ldots,e_n)$ jest bazą uporządkowaną oraz $X=\lambda_1e_1+\ldots+\lambda_n e_n$ to $$ [x]_{\mathcal{E}} = \begin{bmatrix} \lambda_1\\ \vdots\\ \lambda_n \end{bmatrix} $$ nazywamy współrzędnymi $x$ w bazie $\mathcal{E}$.
Def: Zbiór $H\subseteq V$ jest podprzestrzenią $V$ jeśli $(\forall x,y\in H)(x+y\in H)$ oraz $(\forall x\in H)(\forall \lambda)(\lambda\cdot x\in H)$.
Tw. Załóżmy, że $H \subseteq V$. Następujące warunki sa równoważne:
1. $H$ jest podprzestrzenią przestrzeni $V$
2. $(\forall x,y \in H)(\forall \lambda,\mu\in K)(\lambda\cdot x + \mu\cdot y \in H)$
3. $\span{H} = H$

07-12-2016: Przekształcenia liniowe

Wymiary podprzestrzeni przestrzeni $K^n$
Podprzestrzenie jednowymiarowe w $(\ZZ_p)^2$
Def. Funkcja $F:V_1\to V_2$ jest przekształceniem liniowym jeśli $F(\lambda x+\mu y) = \lambda F(x)+\mu F(y)$ dla dowolnych $x,y\in V_1$ oraz $\lambda,\mu \in K$. $Lin(V_1,V_2)$ = zbiór wszystkich przekształceń liniowych z $V_1$ do $V_2$
Jeśli $F$ jest liniowa, to $F(0) = 0$
Opis przekształceń liniowych z $\RR^2\to\RR^2$: $$ F((x,y) = (ax+cy,bx+dy) $$ dla pewnych $a,b,c,d\in\RR$
Pojęcie macierzy wymiaru $m\times n$ elementów ciała $K$: $$ A = \begin{bmatrix}a_{11}&a_{12}&\ldots&a_{1n}\\ \vdots&\vdots&\ldots&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mn} \end{bmatrix} $$ Oznaczenie: $M_{m\times n}(K)$ = zbiór wszystkich macierzy wymiaru $m\times n$ nad ciałem $K$.
Mnożenie macierzy przez wektor: $$ \begin{bmatrix}a_{11}&a_{12}&\ldots&a_{1n}\\ \vdots&\vdots&\ldots&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mn} \end{bmatrix} \circ \begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix} \begin{bmatrix}\sum_{j=1}^{n}a_{1j}x_j\\\sum_{j=1}^{n}a_{2j}x_j\\\vdots\\\sum_{j=1}^{n}a_{mj}x_j\end{bmatrix} $$ czyli jeśli $A=(a_{ij}) \in M_{m\times n}$, $x\in K^n$, $y\in K^m$ oraz $y = A\circ x$, to $$ y_i = \sum\limits_{j=1}^{n} a_{ij}\cdot x_j $$ dla wszystkich $j\in\{1,\ldots,m\}$
Opis przekształceń z $Lin(\RR^2,\RR^2)$: jeśli $F((x_1,x_2))=(y_1,y_2)$, to $$ \begin{bmatrix}y_1\\y_2\end{bmatrix} = \begin{bmatrix}a&c\\b&d\end{bmatrix} \circ \begin{bmatrix}x_1\\x_2\end{bmatrix} $$ gdzie $F((1,0)) = (a,b)$ oraz $F((0,1))=(c,d)$.
Przykłady: Obrót o kąt $\alpha$ $$ M(O_\alpha) = \begin{bmatrix}\cos(\alpha)&-\sin(\alpha)\\\sin(\alpha)&\cos(\alpha)\end{bmatrix} $$

13.12.2016: Macierze i odwzorowania liniowe

Macierz odwzorowanie liniowego $F:K^n \to K^m$: $$ M(F) = [F(e_1)| \ldots | F(e_n)] \in M_{m\times n} $$ gdzie $e_1,\ldots,e_n$ jest bazą przestrzeni $K^n$.
Jeśli $F,G \in Lin(V_1,V_2)$ i $\lambda \in K$ to $\lambda F, F+G \in Lin(V_1,V_2).$
Wniosek: $lin(V_1,V_2)$ jest przestrzenią liniową
Mnożenie macierzy przez skalar, dodawanie dwóch macierzy tego samego rozmiaru.
Mnożenie macierzy: jeśli $A= (a_{ij})\in M_{k\times m}$, $B=(b_{j,k}) \in M_{m\times n}$ to $A\circ B = (c_{ik}) \in M_{k\times n}$ jest macierzą o elementach $$ c_{ik} = \sum\limits_{j=1}^{n} a_{ij} b_{jk} ~, $$ Patrz YouTube
Tw. $M(G\circ F) = M(G) \circ M(F)$
Przykład: $M(O_\alpha\circ O_\beta) = M(O_\alpha)\circ M(O_\beta)$
Dla $F\in Lin(V_1,V_2)$ określamy $ker(F) = \{x\in V_1: F(x)=0\}$ oraz $rng(F) = \{F(x): x\in V_1\}$
Tw. $ker(F)$ jest podprzestrzenią $V_1$ oraz $img(F)$ jest podprzestrzenią $V_2$

14.12.2016: Macierze i odwzorowania liniowe

Twierdzenie: Jeśli $f\in Lin(V_1,V_2)$ to $$ dim(V_1) = dim(ker(f)) + dim(img(f))~. $$ Dowód (szkic). Bierzemy taką bazę $\{e_1,\ldots,e_k,\ldots,e_n\}$ przestrzeni $V_1$, że $\span{\{e_1,\ldots,e_k\}} = ker(f)$. Pokazujemy, że zbiór $\{f(e_{k+1}),\ldots,f(e_n)\}$ jest bazą $img(f)$.
Niech $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$. Złóżmy, że $\Delta = ad-bc \neq 0$. Wtedy $$ A^{-1} = \frac{1}{\Delta}\begin{bmatrix}d&-b\\-c&a\end{bmatrix} $$ (pokazaliśmy to bezpośrednim sprawdzeniem, że dla tak określonego $A^{-1}$ mamy $A\cdot A^{-1} = I$; sprawdzenie tego, że $A^{-1}\cdot A=I$ zostawiliśmy jako ćwiczenie).
Przykład $M(O_\alpha))^{-1} = M(O_{-\alpha})$
Def. Pseudo-iloczyn skalarny: $\IS{a}{b} = a_1b_1+\ldots+a_nb_n$.
Zastosowanie: $$ \begin{bmatrix}w_1 \\ w_2\\ \vdots \\ w_k\end{bmatrix} \circ \begin{bmatrix}k_1 | k_2 | \cdots | k_n\end{bmatrix} = \begin{bmatrix}\IS{w_i}{k_j} \end{bmatrix} $$

Przestrzenie $\RR^n$

Def. Iloczynem skalarnym w przestrzeni $\RR^n$ nazywamy funkcję $\IS{\cdot}{\cdot}:\RR^n\cdot\RR^n\to \RR$ określoną wzorem $\IS{x}{y} = \sum_{i=1}^{n}x_i y_i$.
Uwaga: W przestrzeniach $\CC^n$ trzeba postępować trochę inaczej; określamy tam $\IS{x}{y} = \sum_{i=1}^{n} x_i \overline{y_i}$ - ale tym zajmiemy się później.
Własności $\langle\cdot,\cdot\rangle$: $\IS{x}{x}\geq 0$, $\IS{\lambda a}{c} = \lambda\IS{a}{c}$, $\IS{a+b}{c} = \IS{a}{c}+\IS{b}{c}$, $\IS{a}{b} = \IS{b}{a}$.
Def: $||x|| = \sqrt{\IS{x}{x}}$
Tw (dla $\RR^2$). $(\forall x,y \in \RR^2)(\IS{O_\alpha(x)}{O_\alpha(y)} = \IS{x}{y})$
Oznacza to niezmienniczość iloczynu skalarnego na obroty płaszczyzny.
Tw. $\IS{x}{y} = ||x||\cdot ||y|| \cos(\alpha)$

20.12.2016: Permutacje

Twierdzenie (dla $\RR^2)$: Jeśli $\vec{u}=(x_1,x_2)$ i $\vec{v}=(y_1,y_2)$, to $$ |\det\left(\begin{bmatrix}x_1&y_1\\x_2&y_2\end{bmatrix} \right)| = pow(\Pi_{\vec{u},\vec{v}}) $$ gdzie $\Pi_{\vec{u},\vec{v}} = \{t\cdot \vec{u} + s\cdot \vec{v}:0\leq s,t\leq 1\}$.
Def. Jeśli $\sigma\in S_n$, to parę $(i,j)$ nazywamy inwersją permutacji $\sigma$ jeśli $i\lt j$ oraz $\sigma(i) \gt \sigma(j)$
Def. $I(\sigma) = |\{(i,j): 1\leq i \lt j \leq n \land \sigma(i)\gt\sigma(j)\}$
Def. $\sgn{\sigma} = (-1)^{I(\sigma)}$
Def. Transpozycja: $$ T_{a,b}(i) = \begin{cases}b&i=a\\ a&i=b\\ i& i\notin \{1,\ldots,n\} \setminus\{a,b\}\end{cases} $$
Tw. $\sgn{T_{a,b}} = -1$
Tw. $\sgn{\sigma\circ\pi} = \sgn{\sigma} \sgn{\pi}$
Fakt. Funkcja $f(\sigma) = \sigma^{-1}$ jest bijekcją $S_n$
Fakt. Funkcja $g(\sigma) = \sigma\circ \tau$ jest bijekcją $S_n$

Wyznaczniki

Def: Jeśli $A=(a_{i,j}) \in M_{n\times n}(K)$, to $$ \det(A) = \sum_{\sigma\in S_n} \sgn{\sigma} \prod_{i=1}^{n} a_{i\sigma(i)} $$
Tw. $\det(A) = \sum_{\sigma\in S_n} \sgn{\sigma} \prod_{i=1}^{n} a_{\sigma(i)i}$

21.12.2016: Wyznaczniki

Def. Jeśli $A=(a_{ij})$ to $A^T = (b_{ij})$, gdzie $b_{i,j} = a_{ji}$.
Wniosek. $\det{A} = \det{A^T}$
Obserwacja: Jeśli coś udowodnimy o kolumnach wyznacznika, to będziemy mieli analogiczny wynik dla wierszy
Obserwacja: Liczenie wyznacznika bezpośrednio z definicji jest bardzo pracochłonne - wymaga rozważanie każdej permutacji, a ich mamy $n!$
Metoda Sarrusa
Tw. $\det{[k_1,\ldots,k_i,\ldots,k_j,\ldots,k_n]}$ = $(-1)^n \det{[k_1,\ldots,k_j,\ldots,k_1,\ldots,k_n]}$
Wniosek. Jeśli $A$ ma dwie takie same kolumny/wiersze, to $\det(A)=0$
Tw. $\det{[k_1,\ldots,b_i+c_i,\ldots,\ldots,k_n]}$ = $\det{[k_1,\ldots,b_i,\ldots,\ldots,k_n]}$ + $\det{[k_1,\ldots,c_i,\ldots,\ldots,k_n]}$
Tw. $\det{[k_1,\ldots,k_i+c\cdot k_j,\ldots,k_j,\ldots,k_n]}$ = $(-1)^n \det{[k_1,\ldots,k_n]}$
Przykłady obliczania wyznaczników
Przykład: $$ \det{ \begin{bmatrix} 1 & 0 & 0 & \ldots & 0\\ 0 & a_{22} & a_{23} & \ldots & a_{2n} \\ 0 & a_{32} & a_{33} & \ldots & a_{3n} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 0 & a_{n2} & a_{n3} & \ldots & a_{nn} \end{bmatrix} } = \det{ \begin{bmatrix} a_{22} & a_{23} & \ldots & a_{2n} \\ a_{32} & a_{33} & \ldots & a_{3n} \\ \vdots&\vdots&\vdots&\ddots \\ a_{n2} & a_{n3} & \ldots & a_{nn} \end{bmatrix} } $$
Oznaczenie: Jeśli $M\in M_{n\times n}(K)$, to $M_{i,j}$ jest macierzą, która powstaje z macierzy $M$ przez wykreslenie $i$-tego wiersza i $j$-tej kolumny (tak zwany minor)
Tw (Rozwinięcie Lalace'a). $$ \det(A) = \sum_{j=1}^{n} (-1)^{i+j} a_{ij} \det(M_{ij}) $$

10.01.2017: Wyznaczniki

Def. Element $A_{ij} = (-1)^{i+j} \det(M_{i,j})$ nazywamy elementem sprzężonym z elementem $a_{ij}$ macierzy $A = (a_{ij})$.
Uwaga: stosujemy oznaczenia z poprzedniego wykładu.
Tw: $$ \sum_{j=1}^{n} a_{ij} A_{kj} = \begin{cases} \det(A) & i=k\\ 0 & i \neq k \end{cases} $$
Def. $adj(A) = [A_{ij}]^T$
Tw. $A \cdot adj(T) = \det(A) I$
Tw. Jeśli $\det(A) \neq 0$ to istnieje macierz odwrotna $A^{1}$; mamy $A^{-1} = \frac{1}{\det(A)}adj(A)$
Tw. $\det(A\circ B) = \det(A)\cdot \det(B)$
Wniosek. $A$ jest odwracalna wtedy i tylko wtedy, gdy $\det(A)\neq 0$
Wniosek: Zbiór $\{A\in:M_{n\times n}(K): \det(A)\neq 0\}$ z działaniem $\circ$ (mnożenie macierzy) jest grupą. Oznaczana jest ona $GL_n(K)$ (General Linear Group)
Wzory Cramera: Jeśli $A= [k_1|\ldots|k_n]$ oraz $\det(A) \neq 0$, to rozwiązanie układu równań $A\circ[x_1,\ldots,x_n]^T = [b_1,\ldots, b_n]^T$ jest dane wzorami $$ x_i = \frac{\det[k_1|\ldots|k_{i-1}|b|k_{i+1}|\ldots|K_n]}{\det(A)} $$ (YouTube: uwaga: stosowana tam jest reguła Sarrusa w dosyć egzotycznej postaci

11.01.2017: Rząd macierzy

Def. Rząd kolumnowy macierzy $A$: $rank_c(A)$ = maksymalna moc niezależnego zbioru kolumn
Tw. $rank_c(A) = \dim(rng(F_A))$, gdzie $F_A(x) = A\circ x$
Def. Rząd wierszowy macierzy $A$: $rank_w(A)$ = maksymalna moc niezależnego zbioru wierszy.
Tw: $rank_c(A) = rank_w(A)$
Tw: $rank(A)$ jest równy maksymalnemu rozmiarowi kwadratowej podmacierzy macierzy $A$ o niezerowym wyznaczniku
Obserwacja: dla danej macierzy $A = [k_1|\ldots|k_n]$ oraz danego $b$ następujące warunki są równoważne:
1. $(\exists x)(A\cdot x = b)$
2. $b \in rng(F_A)$
3. $b \in \span{[k_1|\ldots|k_n]}$
4. $\dim(rng(F_A)) = dim(\span{[k_1|\ldots|k_n|b]})$
Wniosek. Dla danej macierzy $A = [k_1|\ldots|k_n]$ oraz danego $b$ następujące zdania sa równoważne:
1. $(\exists x)(A\cdot x = b)$
2. $rank([k_1|\ldots|k_n]) = rank([k_1|\ldots|k_n|b])$
Przykłady rozwiązywania układów równań liniowych

17.01.2017: Metoda eliminacji Gauss'a

Wykład prowadził prof. dr hab. Michał Morayne.

Tw. Załóżmy, że $A\cdot x_0 = b$. Wtedy $$ \{x: A\cdot x = b\} = x_0 + ker(F_A) $$ czyli $$ \{x: A\cdot x = b\} = x_0 + \{x: A\cdot x = 0\} $$ Uwaga: $\dim(ker(F_A)) = n - rank(A)$.
Metoda eliminacji Gauss'a: przykład - YouTube

18.01.2017: Wartości i macierze własne