03.10.2017: Grupy - cz. I

1. Pojęcia działania binarnego. Łączność, przemienność
2. Jeśli $\cdot$ jest łączne, to $$ x\cdot(y\cdot(u\cdot v)) = (x\cdot y)\cdot (u \cdot v) = (x\cdot (y\cdot u))\cdot v = ((x\cdot y) \cdot u)\cdot v $$
3. Pojęcie grupy
4. Przykłady grup: $(\RR,+)$, $(\RR\setminus\{0\},\cdot)$, $((0,\infty),\cdot)$, $(\ZZ,+)$.
5. 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}$ (lub $-x$, gdy stosujemy notację addytywną).
6. Tw. $(a^{-1})^{-1} = a$
7. Tw. $(a\cdot b)^{-1} = b^{-1}\cdot a^{-1}$
8. Grupa $C_n = (\{0,\ldots,n-1\},\oplus)$, gdzie $x \oplus y = (x+y) \quad \mathrm{mod} \quad n$.

04.10.2017: Grupy - cz. II

1. Definicja $a^k$ dla $k\in\ZZ$
2. 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} $$
3. Def. Funkcja $f:G\to H$ jest homomorfizmem grup $(G,\cdot)$ i $(H,\star)$ jeśli $$ (\forall x,y\in G)(f(x\cdot y) = f(x)\star f(y))~. $$
4. Pojęcie monomorfizmu, epimorfizmu i izomorfizmu
5. Tw. Jeśli $(G,\cdot)$ jest grupą taką, że $|G|=2$, to $(G,\cdot)$ jest izomorficzna z grupą $C_2$.
6. Tw. (na razie bez dowodu) Jeśli $(G,\cdot)$ jest taką grupą skończoną, że $|G|=p$ jest liczbą pierwszą, to $(G,\cdot)$ jest izomorficzna z grupą $C_p$.
7. Przykład: grupy $(\RR,+)$ oraz $((0,\infty),\cdot)$ są izomorficzne (izomorfizm: np. $f(x)=2^x$)
8. Grupa $Sym(X)$ permutacji zbioru $X$; $S_n=Sym(\{1,2,\ldots,n\})$.
9. Jeśli $n\geq 3$ to grupa $S_n$ jest nieprzemienna.
10. Konstrukcja produktu grup: $(G,\cdot) \times (H,+) = (G\times H, *)$, gdzie $(a,b)*(c,d) = (a\cdot c,b+d)$.
11. Tw. Jeśli $(G,\cdot)$ i $(H,+)$ są grupami to $(G,\cdot) \times (H,+)$ też jest grupą.

10.10.2017: Grupy, pierścienie i ciała

1. Grupy $C_2\times C_2$ i $C_4$ nie są izomorficzne.
2. Tw. Niech $f:(G,\cdot)\to (H,\star)$ będzie homomorfizmem. Niech $e_1$ będzie elementem neutralnym w $(G,\cdot)$ oraz niech $e_2$ będzie elementem neutralnym w $(H,\star)$. Wtedy
   1. $f(e_1) = e_2$
   2. $(\forall x\in G)(f(x^{-1})= f(x)^{-1})$
3. Jeśli $(G,\cdot)$ jest grupą skończoną i $|G|=n$, to $(\forall x\in G)(ord(x)\leq n)$
4. Pojęcie pierścienia; pierścienia z jednością; pierścienia przemiennego
5. Pierścień $\ZZ_n = (\{0,1,\ldots,n-1\}, +_n,\cdot_n)$
6. Podstawowe własności działań w pierścieniach: $0\cdot x = x \cdot 0 = 0$, $(-x)\cdot y = -(x\cdot y)$, $(-x)\cdot(-y) = x\cdot y$
7. Definicja ciała
8. Proste obliczenia w ciele $\ZZ_5$

11.10.2017: Pierścienie i ciała

1. Pojęcie homorfizmu struktur algebraicznych
2. Twierdzenie: Dla każdego ustalonego $n\in\NN\setminus\{0\}$ funkcja $\phi_n: \ZZ \to \{0,\ldots,n-1\}$ określona wzorem $\phi_n(x) = x \mod n$ jest homorfizmem z pierścienia $(\ZZ,+,\cdot)$ na pierścień $\ZZ_n$.
   Uwaga: dowód zrobiliśmy tylko dla $+$.
3. Zasada podzielności przez $3$: $\phi_3(\sum_{k=0}^n a_k 10^k) = \ldots = \phi_n(\sum_{k=0}^n a_k)$; zasady podzielności przez $9$, $11$.
4. Wzory prawdziwe w pierścieniach:
   1. $(x+y)^2 = x^2 + x\cdot y + y\cdot x + y^2$
   2. w pierścieniach przemiennych mamy: $(x+y) = x^2 + 2 x y + y^2$, $(x+y)(x-y)=x^2-y^2$
   3. w ciele $\ZZ_p$ (p - liczba pierwsza) mamy $(x+y)^p = x^p + y^p$
5. Proste układy równań w $\ZZ_5$
6. Równania kwadratowe w takich ciałach, że $1+1\neq 0$

1. Dokończ dowód twierdzenia o homomorfiżmie z $\ZZ$ w $\ZZ_n$
2. Zbadaj kryteria podzielności przez $2$, $5$, $10$, $7$.

17.10.2017: Liczby naturalne

1. Konstrukcja ciała $\QQ(\sqrt{2})$.
2. Zasada dobrego porządku (WO): każdy niepusty podzbiór zbioru liczb naturalnych ma element najmniejszy.
3. Zasada indukcji matematycznej (ZIM): jeśli $A\subseteq \NN$, $a\in A$ oraz $(\forall n\in\NN)((a\leq n \land n\in A) \to n+1\in A)$, to $(\forall n\in\NN)(n\geq a \to a \in A)$.
4. Tw. WO $\to$ ZIM
5. Tw. Nie istnieje ostro malejący nieskończony ciąg liczb naturalnych
6. Tw (o dzieleniu z resztą). Jeśli $a,n\in\NN$ i $n>0$ to istnieją liczby naturalne $q,r$ takie, że $a = q\cdot n + r$ i $0\leq r \lt n$.
7. Def. $a|b \equiv (\exists k)(b=k\cdot a)$
8. Podstawowe własności relacji podzielności: $a|a$, $(a|b\land b|c) \to a|c$
9. Def. $NWD(a,b) = \max\{k: k|a \land k|b\}$.
10. Tw. Jeśli $a = q\cdot b + r$, to $NWD(a,b) = NWD(b,r)$
11. ALGORYTM EUKLIDESA (pseudokod z wykorzystaniem operacji jednoczesnego podstawiania)

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

18.10.2017: Największy wspólny dzielnik

1. Tw. Dla dowolnych dodatnich liczb naturalnych $a, b$ istnieją liczby całkowite $X,Y$ takie, że $$ a\cdot X + b \cdot Y = NDW(a,b)~. $$ Dowód: Definiujemy $z = \min(\{aX+bY:X,Y\in\ZZ\}\cap(\NN\setminus\{0\}))$ i pokazujemy, że $z = NWD(a,b)$.
2. Tw. Jeśli $n\geq 2$ to pierścień $\ZZ_n$ jest ciałem wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą.
3. Tw. Jeśli $NWD(a,b)=1$ oraz $a|b\cdot c$ to $a|c$.
   Dowód: Mnożymy równanie $aX+bY=1$ przez $c$.
4. Tw. Jeśli $p$ jest pierwsza i $p|a\cdot b$ to $p|a$ lub $b|c$.
5. Tw. Każda liczba naturalna większa od $1$ podzielna jest przez jakąś liczbę pierwszą.
   Dowód: Zakładamy, że teza nie jest prawdziwa i rozważamy najmnieją liczbę naturalną dla której to nie jest prawdą (korzystamy z WO).
6. Tw. (Euklides) Istnieje nieskończenie wiele liczb pierwszych.
   Dowód: Rozważamy liczbę $(p_1\cdot p_2\cdots p_n) +1$
   Uwaga: Euklides żył w Alksandrii ok 300 lat p.n.e. Twierdzenie Euklidesa ma więc około 2300 lat. Musicie znać jego dowód.
7. Rozszerzony Algorytm Euklidesa:

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

Zagadka: podczas wylicznia NWD(21,13) pojawiają 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ę? Możesz spróbować skorzystać ze Sloane Online Encyclopedia of Integer Sequences.

24.10.2017: Liczby naturalne - II

1. Tw. Jeśli $p$ jest liczbą pierwszą oraz $p|(a_1\cdot \ldots\cdot a_n)$ to $(p|a_1)\lor\cdots\lor (p|a_n)$ .
2. Tw. Każdą liczbę naturalną $n\geq 2$ można przedstawić jednoznacznie w postaci $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$.
3. Tw. $NWD\left(\prod_{i=1}^{k} p_i^{\alpha_i}, \prod_{i=1}^{k} p_i^{\beta_i}\right) = \prod_{i=1}^{k} p_i^{\min(\alpha_i,\beta_i)}$.
4. Def. $NWW(a,b) = \min\{k \gt 0: a|k \land b|k\}$
5. Tw. $NWW\left(\prod_{i=1}^{k} p_i^{\alpha_i}, \prod_{i=1}^{k} p_i^{\beta_i}\right) = \prod_{i=1}^{k} p_i^{\max(\alpha_i,\beta_i)}$.
6. Fakt: $\min(a,b)+\max(a,b) = a+b$
7. Tw. $NWW(a,b) = \frac{a\cdot b}{NWD(a,b)}$.
8. Def. $\ZZ_n^* = \left(\{a\in\{1,\ldots,n-1\}: NDW(n,a)=1\},\cdot_n\right)$, gdzie $\cdot_n$ oznacza mnożenie modulo $n$
9. Tw. $\ZZ_n^*$ jest grupą.
10. Przykład. $\ZZ_8^*$ jest grupą izomorficzną z grupą $C_2\times C_2$
11. Przykład. $\ZZ_5^*$ jest grupą izomorficzną z grupą $C_4$

25.10.2017: Liczby zespolone - I

1. Analiza dowodu niewymierności liczby $\sqrt{2}$ (sprawdzliśmy, gdzie tam jest ukryta indukcja)
2. Liczby zespolone: $\mathbb{C} =\{a+b\cdot i:a,b\in\mathbb{R}\}$, gdzie $i$ jest takim elemetem, że $i^2=-1$
3. 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$
4. Def. (sprzężenie) $\overline{a+b\cdot i} = a - b\cdot i$
5. Def: (moduł, norma) $|a+b\cdot i| = \sqrt{a^2+b^2}$
6. Twierdzenie. Dla dowolnych $z_1,z_2 \in \mathbb{C}$ mamy:
   1. $\overline{z_1 + z_2}$ = $\overline{z_1} + \overline{z_2}$;
   2. $\overline{z_1 \cdot z_2}$ = $\overline{z_1} \cdot \overline{z_2}$.
   3. $z\cdot\overline{z} = |z|^2$
7. Interpretacja geometryczna i formalna konstrukcja $\CC$.
8. Wniosek: Funkcja $f(z) = \overline{z}$ jest automorfizmem $\CC$.
9. Fakt. Jeśli $c>0$ to $\sqrt{-c} = \{\sqrt{c} \cdot i, -\sqrt{c}\cdot i\}$
10. Fakt. Dla dowolnej liczby zespolonej $z$ istnieją dwie liczby zespolone $u$ takie, że $u^2 = z$.
11. Wniosek. Równania kwadratowe o współczynnikach z $\CC$ mają rozwiązania w $\CC$.
12. ZASADNICZE TWIERDZENIE ALGEBRY. Jeśli $n\geq 1$ oraz $f(x) = a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1 x + a_0$, gdzie $a_0, a_1, \ldots, a_{n-1}, a_n \in \CC$ oraz $a_n \neq 0$ to istnieje $w\in\CC$ takie, że $f(w) = 0$.
    Dowód będzie zrobiony póżniej.
13. Tw. $|z_1\cdot z_2| = |z_1|\cdot |z_2|$.
14. Wniosek. Struktura $T = \left(\{z\in\CC:|z|=1\},\cdot\right)$ jest grupą abelową. Jeśli $|z|=1$, to $z^{-1}=\overline{z}$.

30.10.2017: Liczby zespolone - II

1. Tw. (Nierówność trójkąta) Dla dowolnych $z_1,z_2 \in \mathbb{C}$ mamy $|z_1 + z_2| \leq |z_2| + |z_2|$.
2. Def: $d(z_1,z_2) = |z_1-z_2|$
3. Interpretacja geometryczna: $d(z_1,z_2)$ interpretujemy jako odległość między liczbami $z_1$ oraz $z_2$
4. 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)
5. Wniosek: Para $(\CC,d)$ jest przestrzenią metryczną
6. Definicja
   $$ \exp(z) = \sum_{n=0}^{\infty} \frac{z^n}{n!} $$
7. Potęgi liczby $i$: $$ i^n = \begin{cases} 1 &: n = 4k\\ i &: n= 4k+1\\ -1 &: n = 4k+2 \\ -i &: n=4k+3 \end{cases} $$ Uwaga: na wykładzie na tablicy pojawił się błąd - dziękuję Panu Karolowi Kobiałce za zauważenie błędu!!!
8. Tw. (dowód będzie na Analizie) $\exp(z) = e^z$
9. $$ (\forall t \in \RR)(\exp(i t) = \cos(t) + i\cdot \sin(t))~. $$
10. Tw. (dowód będzie na Analizie) $\exp(z) = e^z$
11. $$ e^{i\pi}+ 1 = 0 $$
12. Twierdzenie (Postać trygonometryczna liczby zespolonej). Dla dowolnej liczby $z\in\CC\setminus\{0\}$ istnieją liczby $\rho\in \RR$ oraz $\alpha \in \RR$ takie, że $\rho>0$ oraz $$ z = \rho(\cos(\alpha) + i\sin(\alpha))~. $$ Liczbę $\alpha$ nazywamy argumentem liczby $z$. Oczywiście: $\rho = |z|$.
13. Wniosek: $$\left(\rho_1(\cos(\alpha) + i\sin(\alpha))\right)\cdot \left(\rho_2(\cos(\beta) + i\sin(\beta))\right)\cdot = (\rho_1\rho_2)(\cos(\alpha+\beta) + i\sin(\alpha+\beta))$$

Zadania domowe

1. Przyglądaj się tak długo apletowi Twierdzenie Pitagorasa aż zobaczysz, że dowód tego twierdzenia jest oczywisty.
2. Samodzielnie (bez patrzenia do notatek) wyprowdź wzory na $\sin(\alpha+\beta)$ i $\cos(\alpha+\beta)$. Wyprowadź wzory na $\sin(2\alpha)$ i $\cos(2\alpha)$.

07.11.2017: Liczby zespolone - II

1. Uwagi o NWD: Z obliczeń NWD(22,6) = NWD(6,4) = NWD(4,2) = 2 możemy wyznaczyć rozwiązania równania $22\cdot X + 6\cdot Y = 2$ w liczbach całkowitych: 2 = 1*6 - 1*4 = 1*6 - (22-3*6) = 4*6 + (-1)*22.
2. Def. $arg(z) = \{\alpha\in\RR: z = |z|(\cos(\alpha)+i\cdot\sin(\alpha)$
3. Def. $Arg(z) = \alpha$ jeśli $\alpha \in arg(z) \land 0\leq \alpha \lt 2\pi$
4. Wniosek: $arg(z) = Arg(z) + 2\cdot\pi\cdot\ZZ$
5. Wzór de Moivre'a: $\left(\rho(\cos(\alpha)+i\cdot\sin(\alpha))\right)^n = \rho^n(\cos(n\cdot\alpha)+i\cdot\sin(n\cdot\alpha))$
6. Wzór de Moivre'a (bardziej zwarta wersja): $(r\cdot e^{i\alpha})^n= r^n\cdot e^{i(n \alpha}$
7. Tw (pierwiastki z jedności). $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)
8. Obserwacja: $\epsilon_{n,k}\cdot\epsilon_{n,l} = \epsilon_{n,(k+l)\mod n}$
9. Wniosek: Grupa $(\{z\in\mathbb{C}: z^n=1\},\cdot)$ jest izomorficzna z grupą $C_n$.
10. Zaczęliśmy przyglądać się pierwiastkom z dowolnej liczby zespolonym. Dokończymy to na następnym wykładzie.

08.11.2017: Liczby zespolone - III

1. 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\}~. $$
2. Definicja ciała liniowo uporządkowanego
3. Przykład: Ciało $\ZZ_7$ nie jest liniowo porządkowalne
4. Tw. Ciała liczb zespolonych nie można liniowo uporządkować
5. Kwaterniony: zbiór $\mathbb{K}$ wszystkich wyrażeń postaci $a+b\cdot i + c\cdot j +d\cdot k$, gdzie
   1. $i^2 - j^2 = k^2 = -1$
   2. $i\cdot j = k$, $j\cdot k = i$, $k\cdot i = j$
   3. $(\forall x,y\in\{i,j,k\})(x\cdot y = - y\cdot x)$
6. Własności kwaterninów:
   1. Sprzężenie kwaternionu: $\overline{a+b\cdot i + c\cdot j +d\cdot k} = a - b\cdot i - c\cdot j - d\cdot k$
   2. Norma kwaternionu: $|a+b\cdot i + c\cdot j +d\cdot k| = \sqrt{a^2+b^2+c^2+d^2}$
   3. Fakt: $z\cdot \overline{z} = |z|^2$
   4. Odwrotność kwarernionu: $$ \frac{1}{a+b\cdot i + c\cdot j +d\cdot k} = \frac{a - b\cdot i - c\cdot j - d\cdot k}{a^2+b^2+c^2+d^2}~. $$
   5. Wniosek: Struktura $(\mathbb{K},+,\cdot)$ spełnie wszystkie własności ciała, za wyjątkiem przemienności mnożenia.
7. Pierścień liczb zespolonych Gaussa: $\mathbb{Z}[i] = \{a+b\cdot i: a,b \in \mathbb{Z}\}$
   1. Pojęcie liczby pierwszej w pierścieniu Gaussa
   2. Norma elementu: $N(a+bi) = a^2+b^2$
   3. Fakt: $N(z_1z_2)= N(z_1)N(z_2)$
8. Elementy odwracalne pierścienia $R$: $\mathcal{E}(R) = \{x \in R: (\exists y\in R)(x\cdot y = 1)\}$
9. Przykłady: $\mathcal{E}(\ZZ) = \{-1,1\}$, $\mathcal{E}(\RR) = \RR\setminus\{0\}$.

14.11.2017

Liczby Gaussa - c.d

1. Elementy odwracalne w $\ZZ[i]$: $\{1,-1,i,-i\}$
2. Def. Element $a$ pierścienia $R$ jest nierozkładalny jeśli $$ (\forall c,d \in R)(a = b\cdot c \to (a\in \mathcal{E}(R) \lor b \in \mathcal{E}(R))) $$ oraz $a \notin \mathcal{E}(R)$.
3. Przykład: Elementy nierozkładalne w $\ZZ$: liczby postaci $\{\pm p: p\mbox{ jest pierwsza} \}$
4. Tw. Każda liczba $z\in\mathbb{Z}[i]\setminus \mathcal{E}$ jest podzielna przez jakąś liczbę nierozkładalną
5. 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)$.
6. Przykład: $(1+i)(1-i) = 2$, zatem $2$ nie jest nierozkładalna w $\mathbb{Z}[i]$.
7. Przykład: liczba $3+0\cdot i$ jest nierozkładalna w $\mathbb{Z}[i]$.
8. Tw (bez dowodu) Liczba pierwsza $p$ jest liczbą nierozkładalną w pierścieniu $\mathbb{Z}[i]$ wtedy i tylko wtedy gdy $p = 4k +3$ dla pewnej liczby naturalnej $k$.

Wielomiany - I

1. Dziedzina całkowitości: piecień przemienny z jednością, bez dzielników zera
2. Definicja pierścienia $R[x]$
   1. $R[x] = \{\sum_{n=0}^{\infty} a_n x^n: (\forall n)(a_n\in R) \land (\exists N)(\forall n\gt N)(a_n=0)\}$
   2. $(\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$
   3. $(\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$
3. Tw. Struktura $R[x]$ jest pierścieniem.
   Uwaga: pokazaliśmy tylko łączność mnożenia.
4. Def. Jeśli $w = \sum_{n=0}^{\infty} a_n x^n$, to $$ deg(w) = \begin{cases} \max\{k:a_k\neq 0\} &: (\exists k)(a_k\neq 0)\\-\infty &: (\forall k)(a_k=0)\end{cases} $$
5. Przykład: w $\ZZ_6[x]$: jeśli $w = 1+2\cdot x$ oraz $v = 1+3\cdot x$ to $u\cdot v = 1+5\cdot x$, więc $deg(w\cdot v) \lt deg(w) + deg(v)$.

15.11.2017

Wielomiany - II

1. Def. $w|v$ wtedy i tlko wtedy, gdy istnieje wielomian $\alpha$ taki, że $v = \alpha\cdot w$
2. 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)$.
3. Fakt: Wielomiany pierwszego stopnia (liniowe) są nierozkładalne
4. Tw. Każdy wielomian stopnia większego lub równego jeden jest iloczynem wielomianów nierozkładalnych.

Wielomiany nad ciałami

1. 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)$
2. Wniosek: Jeśli $w\in K[x]$, to $w(a)=0$ wtedy i tylko wtedy, gdy $(x-a)|w$
3. 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)
4. Lemat. Załóżmy, że $w \in \RR[x]$ oraz, że dla $\zeta \in \CC$ mamy $w(\zeta)=0$. Wtedy $w(\overline{\zeta}) = 0$.

21.11.2017: Wielomiany

1. 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$.
2. Wniosek. Każdy wielomian z $\RR[x]$ stopnia nieparzystego ma pierwiastek rzeczywisty.
3. NWD wielomianów (uwaga: dla uzyskania jednoznaczności wynikiem ma być wielomian moniczny).
4. 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$
5. Twierdzenie o jednoznaczności rozkładu dla $K[x]$, gdy $K$ jest ciałem

Wielomiany z $\ZZ[x]$

1. Fakt: 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$
2. Def. (homomorfim indukowany) Niech $R_1$ i $R_2$ będą pierścieniami; niech $\phi:R_1\to R_2$ bedzie homomorfizmem. Definiujemy funkcję $$ \overline{\phi}(\sum_n a_n x^n) = \sum_n \phi(a_n)x^n~. $$ Łatwo można pokazać, że to jest homomorfizmem z $R_1[x]$ w $R_2[x]$. Nazywamy go homomorfizmem indukowanym.
3. Kryterimu Eisensteina nierozkładalności wielomianów w $\ZZ[x]$.
   Dowód: następny wykład.
4. Przykład: Jeśli $p$ jest liczbę pierwszą i $n \gt 0$, to wielomian $x^n + p$ jest nierozkładalny w $\ZZ[x]$
5. Przykład: Jeśli $p$ jest liczbę pierwszą i $n \gt 0$, to wielomian $1+x+x^2+\ldots +x^{p-1}$ jest nierozkładalny w $\ZZ[x]$.
   W dowodzie skorzystaliśmy z tego, że jeśli $p$ jest pierwsza i $1\leq k\leq p-1$ to liczba $\binom{p}{k}$ jest podzielna przez $p$.

22.11.2017: Wielomiany

1. Dowód tego, że homomorfizm indukowany jest homomorfizmem
2. Wielomiany nierozkładalne w $\ZZ_2[x]$:
   1. Stopnia 1: $w(x)=x$, $w(x)=x+1$
   2. Stopnia 2: $w(x)=x^2 + x + 1$
   3. Stopnia 3: $w(x)=x^3 + x^2 + 1$, $w(x)=x^3 + x + 1$
   4. Stopnia 4: $w(x)=x^4 + x^3 + x^2 + x + 1$, $w(x)=x^4 + x^3 + 1$, $w(x)=x^4 + x + 1$
3. Przykład: Wielomian $w(x) = 3x^4 + 7x^3+ 5$ jest nierozkładalny w $\ZZ[x]$ - stosujemy homomorfizm $f(x) = x \mod 2$.
4. Dowód kryterium Eisensteina
5. Def. Zawartość wielomianu: $c(a_0+a_1x+\ldots a_nx^n) = NWD(a_0,a_1,\ldots,a_n)$
6. Def. Wielomian prymitywny $\equiv$ wielomian o zawartości 1
7. Lemat: Iloczy dwóch wielomianów prymitywnych jest prymitywny.
8. Tw (Gauss). Wielomian z $\ZZ[x]$ jest nierozkładalny w $\ZZ[x]$ wtedy i tylko wtedy, gdy jest nierozkładalny w $\QQ[x]$.

28.11.2017

Rozwiązywanie równań stopnia trzeciego z $\CC[x]$

1. Za pomocą podstawienia $x = y-\frac13 a$ sprowadzamy równanie $x^3+ax^2+b^x+c=0$ do równania postaci $x^3+A^x+B=0$
2. Szukamy rozwiązania postaci $x = u+v$. Dobieramy $u$ i $v$ tak aby otrzymać równania postaci $u^3+ c v^3 +d$ i $uv=e$
3. Otrzymamy równania postaci $u^6+ K u^3 + L=0$, które rozwiązauje się już łatwo.

Ciało ułamków dziedziny całkowitej

1. Konstrukcja
   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}$
2. Ciało $\RR(x)$$ funkcji wymiernych o współczynnikach rzeczywistych. Ciało to można uporządkowac liniowo. To ciała nie jest archmiedesowskie

Przestrzenie liniowe

1. Definicja przetrzen liniowej nad ciałem $K$
2. Przykłady: $\RR^n$, $K^n$, $C([a,b])$
3. Def (otoczka liniowa). $span(X) = \{\sum_{i=1}^{n} \lambda_i x_i: n\in\NN, \lambda_i\in K, x_i \in X\}$
4. Własności i przykłady $span$

29-11-2017: Przestrzenie wektorowe

1. 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$
2. Własności liniowej otoczki
   1. $span(span(A)) = span(A)$
   2. $A\subseteq B \to span(A) \subseteq span(B)$
   3. Jeśli $B \subseteq span(A)$ to $span(A\cup B) = span(A)$
3. 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) $$
4. Przykład: $V=\RR^n$, $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.
5. Przykład: $V=\RR^2$; $f_1 = (1,1)$, $f_2 = (-1,1)$; Zbiór $\{f_1,f_2\}$ jest bazą $\RR^2$
6. Jeśli $x_1,\ldots,x_n$ są liniowo niezależne oraz $\sum_{i=1}^{n}\lambda_i x_i = \sum_{i=1}^{n}\mu_i x_i$ to $(\forall i)(\lambda_i = \mu_i)$.
7. Def. Baza: maksymalny w sensie zawierania zbiór liniowo niezależny.
8. Lemat. Jeśli $E$ jest liniowo niezależny oraz $x\in V\setminus\span{E}$, to $E\cup\{x\}$ jest liniowo niezależny.
9. Wniosek. Jeśli $E$ jest bazą to $\span{E} = V$.
10. Tw (Steinera o wymianie) Jeśli $\span{A} = V$ oraz $B$ jest liniowo niezależny i skończony to istnieje $A_1 \subseteq A$ taki, że $|A_1|=|B|$ oraz $\span{B\cup(A\setminus A_1)} = V$.

05-12-2017: Przekształcenia liniowe

1. Wniosek. Jeśli $V$ ma bazę mocy $n$, to dowolna inna baza $V$ jest mocy $n$.
2. Tw (bez dowodu) Każda nietrywialna przestrzeń liniowa ma bazę.
   Dowód będzie na Wstępie do Logiki i Struktur Formalnych (będzie to zastosowanie Lematu Kuratowskiego-Zorna)
3. Def. $dim(V)$= moc bazy przestrzeni $V$.
4. Def. Ciąg $(e_1,\ldots,e_n)$ jest bazą uporządkowaną jeśli $\{e_1,\ldots,e_n\}$ jest bazą.
5. 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}$.
6. 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)$.
7. 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$
8. Wymiary podprzestrzeni przestrzeni $K^n$
9. Podprzestrzenie jednowymiarowe w $(\ZZ_p)^2$
10. 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$.
11. $Lin(V_1,V_2)$ = zbiór wszystkich przekształceń liniowych z $V_1$ do $V_2$
12. Jeśli $F$ jest liniowa, to $F(0) = 0$
13. 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$
14. Fakt: $Lin(V_1,V_2)$ jest przestrzenią liniową
15. 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$.
16. 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\}$
17. Macierz przekształcenia liniowego: mamy bazy uporządowane $\mathcal{E} = (e_1,\ldots,e_n)$ i $\mathcal{F} = (f_1,\ldots,f_m)$ przestrzeni $V_1$ i $V_2$. Mamy $F\in Lin(V_1,V_2)$. Znajdujemy $a_{ij}\in K$ takie, że $$ F(e_j) = \sum_{i=1}^{m} a_{ij} f_i~. $$ Macierz $A =(a_{ij})_{i=1,\ldots m; j=1,\ldots,n}$ nazywamy macierzą odwzorowania $F$ w bazach $(\mathcal{F},\mathcal{E})$ i oznaczamy ją $M_{\mathcal{F};\mathcal{E}}(F)$.
18. Wniosek $$ [F(x)]_{\mathcal{F}} = M_{\mathcal{F};\mathcal{E}}(F)\circ [x]_{\mathcal{E}}~. $$

06-12-2017: Przekształcenia liniowe

1. 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)$.
2. Przykłady: Obrót o kąt $\alpha$ $$ O_\alpha = \begin{bmatrix}\cos(\alpha)&-\sin(\alpha)\\\sin(\alpha)&\cos(\alpha)\end{bmatrix} $$
3. 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
4. Twierdzenie. Jeśli $F:V_1\to V_2$ oraz $G:V_2\to V_3$ są liniowe, to $G\circ F:V_1\to V_3$ jest liniowe.
5. Twierdzenie. Jeśli $F:V_1\to V_2$ oraz $G:V_2\to V_3$ są liniowe, $\mathcal{E}$, $\mathcal{F}$ i $\mathcal{G}$ są bazami uporzadkowaneymi przestrzeni $V_1$, $V_2$ i $V_3$, to $$ M_{\mathcal{G};\mathcal{E}}(G\circ F) = M_{\mathcal{G};\mathcal{F}}(G) \circ M_{\mathcal{F};\mathcal{E}}(F) ~. $$
6. Przykład: Z równości $O_{\alpha} \circ O_{\beta} = O_{\alpha+\beta}$ wynikają podstawowe tożsamości trygonometryczne.
7. Def. $ker(F) = \{x\in V_1: F(x)=0\}$
8. Def. $img(F) = \{F(x): x\in V_1\}$
9. Fakt: Jeśli $F:V_1\to V_2$ jest liniowe, to $ker(F)$ jest podprzestrzenią liniową przestrzeni $V_1$
10. Fakt: Załóżmy, że $F:V_1\to V_2$ jest odwzorowaniem liniowym. Odwzorowanie $F$ jest różnowartościowe wtedy i tylko wtedy, gdy $ker(F) = \{0\}$.
11. Fakt: Jeśli $F:V_1\to V_2$ jest liniowe, to $img(F)$ jest podprzestrzenią liniową przestrzeni $V_2$

12.12.2017: Równania liniowe

1. Definicja sumy prostej podprzestrzeni liniowych.
2. Twierdzenie. Niech $F:V_1\to V_2$ będzie odwzorowaniem liniowym. Wtedy
   $$dim(V_1) = dim(ker(F)) + dim(img(F))$$
3. Macierzowa reprezentacja układu równań liniowych
4. Definicja: Niech $\sigma \in S_n$:
   1. $n(\sigma) = \{(i,j):1\leq i \lt j \leq n \land \sigma(i)\gt\sigma(j)\}$
   2. $N(\sigma) = |n(\sigma)|$
   3. znak permutacji: $\sgn{\sigma} = (-1)^{N(\sigma)}$
5. Tw. Jeśli $T_{a,b}$ jest transpozycją elementów $a$ i $b$, to $\sgn{T_{a,b}} = -1$
6. Tw. $\sgn{\sigma\circ\pi} = \sgn{\sigma}\sgn{\pi}$

12.12.2017: Wyznacznik

1. Wniosek: Jeśli $n\geq 2$ to funkcja $\mathrm{sgn}:S_n \to (\{-1,1\},\cdot)$ jest epimorfizmem
2. Def. Dla $A = [a_{ij}] \in M_{n\times n}(K)$ określamy
   $$ \det{A} = \sum_{\sigma \in S_n} \sgn{\sigma}\prod_{i=1}^{n}a_{i\sigma(i)} $$
3. Wniosek: $\det{I_n} = 1$
4. Wniosek: $\det{A} = \sum_{\sigma \in S_n} \sgn{\sigma}\prod_{i=1}^{n}a_{\sigma(i)i}$
5. WNiosek: $\det{A} = det{A^T}$, gdzie $A^T$ oznacza macierz transponowaną macierzy $A$
6. Tw. Jeśli przestawiamy dwie kolumny (dwa wiersze) w kwadratowej macierzy, to zmieniam znak wyznacznika na przeciwny
7. Tw. $\det{[\lambda k_1|k_2|\ldots|k_n]} = \lambda\det{[k_1|k_2|\ldots|k_n]}$
8. Tw. $\det{[u+v|k_2|\ldots|k_n]} =\det{[u|k_2|\ldots|k_n]} + \det{[v|k_2|\ldots|k_n]}$
9. Tw. $\det{[k_1|\lambda k_1 + k_2|\ldots|k_n]} =\det{[k_1|k_2|\ldots|k_n]}$
10. Zaczęliśmy dobierać się do wzoru na rozwinięcie Laplace'a

19.12.2017: Wyznacznik

1. Rozwinięcie Laplace'a: Dla każdego ustalonego $i$ mamy $$ \det{A} = \sum_{j=1}^{n} a_{ij}(-1)^{i+j}\det{A_{ij}} $$ gdzie $A_{ij}$ jest macierzą którą otrzymuje się z macierzy $A$ po usunięciu $i$-tego wiersza i $j$-tej kolumny.
2. Wniosek: Jeśli $1\leq \alpha,\beta \leq n$ to $$ \sum_{j=1}^{n} a_{\alpha j}(-1)^{\beta+j}\det{A_{\beta j}} = \det{A} ||\alpha=\beta||~. $$
3. Wniosek. Niech $a_{ij}^{*} = (-1)^{i+j}\det{A_{ij}}$ oraz $A^* = [a_{ij}^{*}]$. Wtedy $$ A \cdot (A^*)^T = \det{A}\cdot I_n, \quad (A^*)^T \cdot A = \det{A}\cdot I_n $$
4. Wniosek. Załóżmy, że $\det{A}\neq 0$. Wtedy $$ A^{-1} = \frac{1}{\det{A}} (A^*)^T $$
5. Przykład: $$ \begin{bmatrix}a & b\\c & d\end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix}d & -b\\-c & a\end{bmatrix} $$
6. Wzory Cramera: Jeśli $A= [k_1|k_2|\ldots|k_n]$ to $\det{A}\neq 0$, to równanie $A\cdot x = b$ ma dokładnie jedno rozwiązanie o współrzędnych $$ x_i = \frac{\det{A[k_i/b]}}{\det{A}} $$ gdzie $A[k_i/b]$ oznacza macierz która powstaje z $A$ przez zamianę $i$-tej kolumny przez wektor (kolumnowy) $b$.
7. Wzór: $$ \prod_{i=1}^{n} \sum_{j=1}^{m} c_{ij} = \sum_{f\in\mathcal{F}} \prod_{i=1}^{n} c_{if(i)}~. $$ gdzie $\mathcal{F}$ oznacza rodzinę wszystkich funkcji $f:\{1,\ldots,n\} \to \{1,\ldots,m\}$.

20.12.2017: Wyznaczniki

1. Tw. $\det{A\cdot B} = \det{A}\det{B}$
2. Wniosek: Macierz $A\in M_{n\times n}$ jest odwracalna wtedy i tylko wtedy, gdy $\det{A}\neq 0$
3. Wniosek: Jeśli $A=[k_1|\ldots|k_n]$ i $\det{A} \neq 0$, to $span(\{k_1,\ldots,k_n\}) = K^n$
4. Tw. Jeśli $A = \begin{bmatrix}a & c\\b & d\end{bmatrix}$, to $$ |\det{A}| = vol_2 \left(\{\lambda f_1 + \mu f_2: 0\leq \lambda,\mu \leq 1\}\right) $$ gdzie $f_1 = [a,b]$ i $f_2 = [c,d]$.
5. Def. Rządem wierszowym macierzy $A$ ($rank_w(A)$) nazywamy wymiar podprzestrzeni generowanej przez wiersze macierzy $A$.
6. Def. Rządem kolumnowym macierzy $A$ ($rank_k(A)$) nazywamy wymiar podprzestrzeni generowanej przez kolumny macierzy $A$.
7. Tw. Dla dowolnej macierzy $A$ mamy $rank_w(A) = rank_k(A)$.

09.01.2018: Układy równań liniowych

Wykład prowadził dr K. Majcher

1. Fakt. Rząd macierzy = wymiar max niezdegenerowanego minora.
2. Twierdzenie Kroneckera-Capellego.
3. Fakt. Zbiór rozwiązań układu jest przesunięciem podprzestrzeni.
4. Metoda eliminacji Gaussa.

10.01.2018: Wartości własne

Wykład prowadził dr K. Majcher

1. Fakt. Funkcja liniowa $V \to V$ jest różnowartościowa wtedy i tylko wtedy, gdy jej macierz jest niezdegenerowana.
2. Definicja. Wartość i wektor własny macierzy, przekształcenia.
3. Fakt. wartości własne = pierwiastki wielomianu charakterystycznego.
4. Współrzędne wektora w bazie, macierz przejścia, macierz przekształcenia w bazie, wzór na macierz przekształcenia po zamianie bazy.
5. Diagonalizacja za pomocą bazy wektorów własnych.
6. Potęgowanie macierzy diagonalnej i diagonalizowalnej.
7. Przykład: zastosowanie do wyznaczania wyrazów ciągu Fibonacciego.

16.01.2018: Wielomian charatkterystyczny

1. Def. $A\sim B$ iff istnieje odwracalna macierz $Q$ taka, że $B = Q^{-1}\cdot A \cdot Q$
2. Tw. Jeśli $A\sim B$ to $\det{A} = \det{B}$
3. Def. $tr(A) = \sum_{i} a_{ii}$
4. Tw. Jeśli $A\sim B$ to $tr(A) =tr(B)$
5. Tw. Jeśli $A\in M_{n\times n}(K)$ i $\det{A - \lambda I} = \sum_{k=0}^{n} c_k \lambda^{k}$ to
   1. $c_n = (-1)^n$
   2. $c_{n-1} = (-1)^{n-1} tr(A)$
   3. $c_0 = \det{A}$
6. Reprezentacja sieci WEB za pomocą macierzy przejść (linków) i wierzchołków wiszących
7. Pojęcie macierzy kolumnowo stochastycznej
8. MACIERZ PAGE RANK: $$ G_{\alpha} = \alpha\left(A + \frac1n e^T e_D\right) + \frac1n (1-\alpha)e^T e $$
9. Twierdzenie Frobeniusa-Perrona
10. Page rank: taki wektor stochastyczny $\pi$, że $G_\alpha \cdot \pi = \pi$

17.01.2018: Page rank i iloczyn skalarny

1. Tw. Jeśli $A$ jest kolumnowo stochastyczna i $x$ jest wektorem stochastycznym, to $A\cdot x$ jest wektorem stochastycznym.
2. Przykład obliczenia PageRank dla grafu $\{1\to 3,2\to 3\}$
3. Tw (Cauchy). Jeśli $f_A(\lambda) = \det{A-\lambda I}$ to $f_A(A) = 0$.
4. Deficja iloczynu skalarnego dla przestrzeni wektorowych nad $\RR$ lub $\CC$
5. Standardowe przykłady: $\IS{x}{y}=\sum_i x_i y_i$ dla $\RR^n$; $\IS{x}{y}=\sum_i x_i \overline{y_i}$ dla $\CC^n$; $\IS{f}{g} = \int_0^1 f(x)g(x) dx$ dla $C([0,1])$
6. Tw (nierównośc Cauchy'ego) $|\IS{x}{y}| \leq ||x||\cdot ||y||$
   Dowodu nie dokończyliśmy.

23.01.2018: Iloczyn skalarny i macierze ortogonalne

1. Nierówość trójkata: $||x+y||\leq ||x||\cdot||y||$
2. Def. $d(x,y) = ||x-y||$
3. Własności odległości:
   1. $(d(x,y) = 0) \equiv (x=y)$
   2. $d(x,y) = d(y,x)$ (symetria)
   3. $d(x,z) \leq d(x,y)+d(y,z)$ (nierowność trójkata)
4. Pojęcie bazy ortogonalnej i ortonormalnej
5. Proces ortogonalizacji Gramma-Schmit'a
6. Def. Macierz jest ortogonalna jeśli jej kolumny są ortonormalne
7. Tw. Załóżmy, że macierz $A$ jest ortogonalna. Wtedy
   1. $A^T\cdot A = Id$
   2. $A^{-1} = A^T$
   3. $\det{A} \in \{-1,1\}$
   4. $\IS{Ax}{Ay} = \IS{x}{y}$
   5. $||Ax|| = ||x||$

24.01.2018: Rozkład SVD

1. Fakt: Jeśli $A$ jet ortogonalna, to jej wiersze są ortonormalne
2. Def. $A$ jest symetryczna jeśli $A = A^T$
3. Fakt: $A$ jest symetryczna iff $(\forall x,y)(\IS{Ax}{y} = \IS{x}{Ay})$
4. Lemat 1. Jeśli $A$ jest symetryczna, $Ax=\lambda x$, $A y = \mu y$ oraz $\lambda \neq \mu$ to $\IS{x}{y} = 0$
5. Lemat 2. Jeśli $A\in M_n(\RR)$ jest symetryczna, $Ax=\lambda x$ to $\lambda \in \RR$ (więc i $x \in \RR^n$)
6. Twierdzenie: Jeśli $A\in M_n(\RR)$ oraz $A=A^T$ to istnieje macierz diagonalna $\sigma$ oraz macierz ortogonalna $U$ taka, że $$ A = U\cdot \Sigma \cdot U^T~. $$
7. Fakt. Dla dowolnej macierzy $A$ macierz $A^TA$ jest symetryczna.
8. Twierdzenie (rozkład SVD)
   Dla dowolnej macierzy $A \in M_{m\times n}(\RR)$ istnieją macierze ortogonalne $U\in M_{m\times m}(\RR)$, $V \in M_{n\times n}(\RR)$ oraz macierz diagonalna $\Sigma \in M_{m\times n}(\RR)$ takie, że $$ A = U\cdot \Sigma \cdot V^T $$
9. A na koniec zrobiliśmy sobie zdjęcie, przekształciliśmy je do zdjęcia monochromatycznego, wydobyliśmy z niego dane, przepuściliśmy je przez rozkład SVD, wzięliśmy 10% wartości singularnych, odtworzyliśmy prawie wiernie oryginalne zdjęcie i na tym zakończyliśmy wykład.