Bonusový test

Definice (41)

definujte…

• rozšířená matice soustavy
  • soustava m lineárních rovnic o n neznámých … Ax = b
  • rozšířená matice soustavy … $(A|b) \in \mathbb{R}^{m×(n+1)}$
  • matice soustavy … $A \in \mathbb{R}^{m×n}$
  • vektor pravých stran … $b \in \mathbb{R}^m$
  • vektor neznámých … $x = (x_1,\dots,x_n)^T$
  • vektor $x \in \mathbb{R}^n$ je řešení soustavy Ax = b, pokud splňuje všechny její rovnice
  • soustavy Ax = 0 se nazývají homogenní a vždy umožňují x = 0
• elementární řádkové operace
  • definujeme základní dvě elementární řádkové úpravy
    • vynásobení i-tého řádku nenulovým $t \in \mathbb R \setminus \lbrace0\rbrace$
    • přičtení j-tého řádku k i-tému řádku
  • z těch lze odvodit další dvě úpravy
    • přičtení t-násobku j-tého řádku k i-tému řádku (t může být i nulové)
    • záměna dvou řádků
  • provedení jedné elementární úpravy značíme $A\sim A'$
  • provedení posloupnosti úprav značíme $A\sim\sim A'$
• odstupňovaný tvar matice
  • matice je v řádkově odstupňovaném tvaru (REF = row echelon form), pokud jsou nenulové řádky seřazeny podle počtu počátečních nul a nulové řádky jsou pod nenulovými
  • první nenulový prvek nenulového řádku se nazývá pivot, pod pivotem jsou v REF všechny prvky nulové
• napište pseudokód pro Gaussovu eliminaci
  • // input: matice A
  • // output: matice A v REF
  • foreach i do určete j(i)
    • // j(i) = sloupec s pivotem daného řádku, $j(i) = min\lbrace j: a_{i,j}\neq 0\rbrace$
    • // prázdný řádek má j(i) = $\infty$
  • seřaďte řádky A podle j(i)
  • forever
    • if $\exists i: j(i) = j(i+1) \lt \infty$ then
      • // i-tý a (i+1)-ní řádky jsou nenulové a mají stejně počátečních nul
      • přičtěte $–a_{i+1,j(i)}/a_{i,j(i)}$-násobek i-tého řádku
      • // nyní je prvek ve sloupci j(i) řádku i+1 nulový
      • aktualizujte j(i + 1) a zařaďte (i + 1)-tý řádek na místo
    • else
      • // všechny nenulové řádky mají různý počet počátečních nul
      • return A
  • // konečnost: v každé iteraci roste celkový počet počátečních nul
• pivot
  • označme $j(i)=\text{min}\lbrace j:a_{i,j}\neq 0 \rbrace$
  • pivot = první nenulový prvek $a_{i,j(i)}$ v i-tém řádku matice v REF
• volné a bázické proměnné
  • pro soustavu $A'x = b'$ s A' v REF jsou proměnné odpovídající sloupcům s pivoty bázické, ostatní jsou volné
• hodnost matice
  • hodnost matice A, značená jako rank(A), je počet pivotů v libovolné A' v REF takové, že $A\sim\sim A'$
• jednotková matice
  • pro $n \in \mathbb{N}$ je jednotková matice $I_n \in \mathbb{R}^{n×n}$ definovaná tak, že $(I_n)_{i,j} = 1 \iff i=j$, ostatní prvky jsou nulové
• transponovaná matice
  • transponovaná matice k matici $A \in \mathbb{R}^{m×n}$ je matice $A^T \in \mathbb R^{n×m}$ splňující $(A^T)_{i,j}=a_{j,i}$
• symetrická matice
  • čtvercová matice A je symetrická, pokud $A^T =A$, tedy $a_{i,j}=a_{j,i}$
• maticový součin
  • pro $A \in \mathbb R^{m\times n},B\in \mathbb R^{n\times p}$ je součin $(AB) \in \mathbb R^{m×p}$ definován $(AB)_{i,j}=\sum^{n}_{k=1}a_{i,k}b_{k,j}$
• inverzní matice
  • pokud pro čtvercovou matici $A \in \mathbb R^{n\times n}$ existuje $B \in \mathbb R^{n\times n}$ taková, že $AB=I_n$, pak se $B$ nazývá inverzní matice a značí se $A^{-1}$
  • výpočet: $(A|I_n)\sim\sim (I_n|A^{-1})$
• regulární/singulární matice
  • pokud má matice $A$ inverzi, pak se nazývá regulární, jinak je singulární
• binární operace
  • binární operace na množině X je zobrazení X × X → X
  • tedy např. podíl není binární operace na $\mathbb R$, rozdíl není binární operace na $\mathbb N$
• komutativní a asociativní binární operace
  • asociativní bin. operace na množině G: $\forall a,b,c\in G: (a \circ b)\circ c = a \circ(b\circ c)$
  • komutativní bin. operace na množině G: $\forall a,b \in G: a \circ b = b \circ a$
• neutrální prvek
  • $(\exists e \in G)(\forall a \in G): a\circ e = e\circ a = a$
• inverzní prvek
  • $(\forall a \in G)(\exists b \in G): a\circ b = b\circ a = e$
  • inverzní prvek se obvykle značí $a^{-1}$ (u aditivních grup jako $-a$)
• grupa
  • grupa $(G,\circ)$ je množina G spolu s binární operací $\circ$ na G splňující asociativitu operace $\circ$, existenci neutrálního prvku a existenci inverzních prvků
  • pokud je navíc operace $\circ$ komutativní, pak se jedná o abelovskou grupu
• permutace
  • permutace na množině $\lbrace1,2,\dots,n\rbrace$ je bijektivní zobrazení $p:\lbrace1,2,\dots,n\rbrace\rightarrow \lbrace1,2,\dots,n\rbrace$
• permutační matice
  • permutace může být popsána pomocí permutační matice $P$
  • $(P)_{i,j} = \begin{cases} 1 &\text{pokud } p(i)=j \\ 0 &\text{jinak}\end{cases}$
• transpozice
  • transpozice je permutace, která má pouze jeden netriviální cyklus o délce 2
  • jakoukoliv permutaci lze rozložit na transpozice
    • cyklus $(1,2,3,4)$ lze rozložit na $(1,4)\circ(1,3)\circ(1,2)$ nebo na $(1,2)\circ(2,3)\circ(3,4)$
• inverze v permutaci
  • inverze v $p$ je dvojice prvků $(i,j):i \lt j \land p(i) \gt p(j)$
• znaménko permutace
  • znaménko permutace $p$ je $\text{sgn}(p)=(-1)^{\text{počet inverzí}\ p}$
  • permutace s kladným znaménkem jsou sudé, se záporným liché
  • v exponentu může být # inverzí, # transpozic, # sudých cyklů, $n-$# cyklů
• těleso
  • těleso je množina $\mathbb K$ spolu se dvěma komutativními binárními operacemi $+$ a $\cdot$, kde $(\mathbb K, +)$ a $(\mathbb K \setminus \lbrace0\rbrace, \cdot)$ jsou abelovské grupy a navíc platí distributivita $\forall a,b,c \in \mathbb K : a\cdot (b+c)=(a\cdot b)+(a\cdot c)$
• charakteristika tělesa
  • v tělese $\mathbb K$, pokud $\exists n \in \mathbb N: \underbrace{1+1+\dots+1}_{n}=0$, pak nejmenší takové $n$ je charakteristika tělesa $\mathbb K$
  • jinak má těleso $\mathbb K$ charakteristiku 0
  • značí se $\text{char}(\mathbb K)$
• vektorový prostor
  • vektorový prostor $(V,+,\cdot)$ nad tělesem $(\mathbb K, +,\cdot)$ je množina spolu s binární operací $+$ na $V$ a binární operací skalárního násobku $\cdot: \mathbb K \times V \rightarrow V$
  • $(V,+)$ je abelovská grupa
  • $\forall \alpha,\beta \in \mathbb K, \forall u,v \in V$
    • asociativita … $(\alpha \cdot \beta) \cdot u = \alpha \cdot (\beta \cdot u)$
    • neutrální prvek (skalár) vůči násobení skalárem … $1 \cdot u = u$
    • distributivita … $(\alpha + \beta) \cdot u = (\alpha \cdot u) + (\beta \cdot u)$
    • distributivita … $\alpha \cdot (u+v)=(\alpha \cdot u)+(\alpha \cdot v)$
  • prvky $\mathbb K$ se nazývají skaláry, prvky $V$ vektory
  • rozlišujeme nulový skalár $0$ a nulový vektor $o$
• podprostor vektorového prostoru
  • nechť V je vektorový prostor na $\mathbb K$, potom podprostor U je neprázdná podmnožina V splňující uzavřenost na součet vektorů a uzavřenost na násobení skalárem (z $\mathbb K$) – z toho nutně vyplývá $o \in U$
• lineární kombinace
  • lineární kombinace vektorů $v_1,\dots,v_k \in V$ nad $\mathbb K$ je libovolný vektor $u = \alpha_1v_1+\dots+\alpha_kv_k$, kde $\alpha_1,\dots,\alpha_k \in \mathbb K$
• lineární obal (podprostor generovaný množinou)
  • lineární obal $\mathcal L(X)$ podmnožiny X vektorového prostoru V je průnik všech podprostorů U z V, které obsahují X
  • alternativní značení: span(X)
  • pro $X \subseteq V$ platí $\text{span}(X)=\bigcap U:U\Subset V, X\subseteq U$
  • jde o podprostor generovaný X, vektory v množině X se označují jako generátory podprostoru
• řádkový a sloupcový prostor matice $A \in \mathbb K^{m\times n}$
  • sloupcový prostor $\mathcal S(A) \subseteq \mathbb K^m$ je lineární obal sloupců $A$
  • řádkový prostor $\mathcal R(A) \subseteq \mathbb K^n$ je lineární obal řádků $A$
  • $\mathcal S(A)=\lbrace u \in \mathbb K^m:u=Ax,x\in \mathbb K^n \rbrace$
  • $\mathcal R(A)=\lbrace v \in \mathbb K^n:v=A^Ty,y\in \mathbb K^m \rbrace$
• jádro matice $A \in \mathbb K^{m\times n}$
  • $\text{ker}(A) = \lbrace x \in \mathbb K^n: Ax=0\rbrace$
• lineárně nezávislé vektory
  • množina vektorů X je lineárně nezávislá, pokud nulový vektor nelze získat netriviální lineární kombinací vektorů z X; v ostatních případech je množina X lineárně závislá
  • vektory $v_1,\dots,v_n$ jsou lineárně nezávislé $\equiv$ $\sum_{i=1}^n \alpha_iv_i=o \iff \alpha_1=\dots=\alpha_n=0$
• báze vektorového prostoru
  • báze vektorového prostoru V je lineárně nezávislá množina X, která generuje V (tedy $\text{span}(X)=V$)
• dimenze vektorového prostoru
  • dimenze konečně generovaného vektorového prostoru V je mohutnost kterékoli z jeho bází; značí se dim(V)
• vektor souřadnic
  • nechť $X=(v_1,\dots,v_n)$ je uspořádaná báze vektorového prostoru V nad $\mathbb K$, potom vektor souřadnic $u \in V$ vzhledem k bázi $X$ je $[u]_x=(\alpha_1,\dots,\alpha_n)^T \in \mathbb K^n$, kde $u=\sum_{i=1}^n\alpha_iv_i$
• lineární zobrazení
  • nechť U a V jsou vektorové prostory nad stejným tělesem $\mathbb K$
  • zobrazení $f:U\rightarrow V$ nazveme lineární, pokud splňuje $\forall u,v \in U, \forall \alpha \in \mathbb K:$
    • $f(u+v)=f(u)+f(v)$
    • $f(\alpha\cdot u)=\alpha \cdot f(u)$
      • z toho vyplývá, že pro lineární zobrazení obecně platí $f(o) = o$
• jádro lineárního zobrazení
  • $\text{ker}(f)=\lbrace w \in U:f(w)=o\rbrace$
• matice lineárního zobrazení
  • nechť U a V jsou vektorové prostory nad stejným tělesem $\mathbb K$ s bázemi $X=(u_1,\dots,u_n)$ a $Y=(v_1,\dots,v_m)$
  • matice lineárního zobrazení $f:U\rightarrow V$ vzhledem k bázím X a Y je $[f]_{X,Y} \in \mathbb K^{m\times n}$, jejíž sloupce jsou vektory souřadnic obrazů vektorů báze X vzhledem k bázi Y, tedy $[f(u_1)]_Y,\dots,[f(u_n)]_Y$
  • pro $w \in U$ tedy platí, že $[f(w)]_Y=[f]_{X,Y}[w]_X$
• matice přechodu
  • nechť X a Y jsou dvě konečné báze vektorového prostoru U
  • matice přechodu od X k Y je $[id]_{X,Y}$
  • pro $u \in U$ tedy platí, že $[u]_Y=[id(u)]_Y=[id]_{X,Y}[u]_X$
  • matice přechodu je regulární, platí $[id]_{Y,X}=([id]_{X,Y})^{-1}$
  • výpočet: $[id]_{X,Y}=Y^{-1}X$ nebo také $(Y|X)\sim\sim(I_n|[id]_{X,Y})$
• isomorfismus vektorových prostorů
  • vektorové prostory jsou isomorfní, pokud mezi nimi existuje isomorfismus, tedy bijektivní (vzájemně jednoznačné) lineární zobrazení
  • pro isomorfismus $f$ platí, že existuje $f^{-1}$ a je také isomorfismem
  • isomorfní prostory mají shodné dimenze
• afinní prostor a jeho dimenze
  • nechť $W$ je podprostor vektorového prostoru $U$ a $u \in U$
  • afinní podprostor $u+W$ je množina $\lbrace u+w:w \in W\rbrace$
  • dimenze afinního prostoru $u+W$ je $\text{dim}(u+W)=\text{dim}(W)$
  • prvky afinního prostoru se nazývají body

Věty a důkazy (15)

vyslovte a dokažte… / uveďte a dokažte…

• vztah mezi elementárními řádkovými operacemi a soustavami rovnic

  • věta
    • Nechť $Ax = b$ a $A'x = b'$ jsou dvě soustavy splňující $(A|b) \sim \sim (A'|b')$.
    • Pak obě soustavy mají totožné množiny řešení.
  • důkaz
    • dokážeme, že množina řešení je zachována, pokud je provedena jediná úprava prvního nebo druhého typu (1. typ = vynásobení řádku, 2. typ = přičtení jiného řádku)
    • ukazujeme rovnost $\lbrace x \in \mathbb R^n : Ax=b\rbrace = \lbrace x \in \mathbb R^n : A'x=b' \rbrace$
    • rovnost plyne ze dvou inkluzí, které převedeme na implikace
      • $Ax=b \implies A'x=b'$
      • $A'x=b' \implies Ax=b$
    • elementární úpravou se vždy mění jenom i-tý řádek matice, ostatní zůstávají zachovány, tedy ověříme dvakrát dvě implikace pro i-tý řádek
    • násobení
      • $Ax=b \implies A'x=b'$
        • předpoklad: $a_{i,1}x_1+\dots+a_{i,n}x_n=b_i$
        • chceme: $a'_{i,1}x_1+\dots+a'_{i,n}x_n=b_i'$
        • víme: $\forall k \in \lbrace 1,\dots,n\rbrace: a'_{i,k}=ta_{i,k},b'_i=tb_i$
        • důkaz: $a'_{i,1}x_1+\dots+a'_{i,n}x_n=ta_{i,1}x_1+\dots+ta_{i,n}x_n$ $=t(a_{i,1}x_1+\dots+a_{i,n}x_n)=tb_i=b'_i$
      • $a_{i,1}x_1+\dots+a_{i,n}x_n=\frac{1}{t}(ta_{i,1}x_1+\dots+ta_{i,n}x_n)$ $=\frac{1}{t}(a'_{i,1}x_1+\dots+a'_{i,n}x_n)=\frac{1}{t}b'_i=\frac{1}{t}tb_i=b_i$
    • přičtení
      • $a'_{i,1}x_1+\dots+a'_{i,n}x_n=(a_{i,1}+a_{j,1})x_1+\dots+(a_{i,n}+a_{j,n})x_n$ $=(a_{i,1}x_1+\dots+a_{i,n}x_n)+(a_{j,1}x_1+\dots+a_{j,n}x_n)=b_i+b_j=b'_i$
      • $a_{i,1}x_1+\dots+a_{i,n}x_n=a_{i,1}x_1+\dots+a_{i,n}x_n+b_j-b_j$ $= (a_{i,1}x_1+\dots+a_{i,n}x_n)+(a_{j,1}x_1+\dots+a_{j,n}x_n) - b_j$ $=(a_{i,1}+a_{j,1})x_1+\dots+(a_{i,n}+a_{j,n})x_n-b_j$ $=(a'_{i,1}x_1+\dots+a'_{i,n}x_n)-b_j=b'_i-b_j=b_i+b_j-b_j=b_i$
      • pozor, druhá implikace se dokazuje pomocí $+b_j-b_j$

• věta o jednoznačnosti volných a bázických proměnných

  • věta: Pro libovolnou matici $A$ a libovolnou $A'$ v REF takovou, že $A\sim\sim A'$, jsou indexy sloupců s pivoty v $A'$ určeny jednoznačně podle $A$.
  • důkaz
    • Předpokládejme pro spor, že $A \sim\sim A' \sim\sim A''$.
    • Nechť $i$ je nejvyšší index, kde se charakter proměnných v $A'$ a $A''$ liší.
    • Předpokládejme BÚNO, že $x_i$ je bázická v $A'$ a volná v $A''$.
    • Pro libovolnou volbu proměnných $A'$ určuje soustava $A'x=0$ jednoznačnou hodnotu $x_i$ (protože $x_i$ je v $A'$ bázická).
    • Protože proměnná $x_i$ je volná v $A''$, můžeme její hodnotu zvolit odlišně. Všechny ostatní volné proměnné zvolíme u obou matic stejně.
    • Získáme řešení $A''x=0$, které není řešením $A'x=0$, což je spor.

• Frobeniova věta

  • věta: Soustava $Ax=b$ má řešení právě tehdy, když se hodnost matice $A$ rovná hodnosti rozšířené matice $(A|b)$.
  • důkaz
    • zvolíme libovolné $(A'|b')$ v REF takové, že $(A|b)\sim\sim (A'|b')$
    • řešení $x$ existuje $\iff b'$ nemá žádný pivot $\iff$ počet pivotů $A'$ se shoduje s počtem pivotů $(A'|b') \iff \text{rank}(A)=\text{rank}(A|b)$
    • protože převod $A\sim\sim A'$ lze provést stejnými elementárními úpravami jako $(A|b)\sim\sim (A'|b')$

• věta o vztahu mezi řešeními $Ax = b$ a $Ax = 0$

  • věta: Nechť $x^0$ splňuje $Ax^0=b$. Poté zobrazení $\bar x \mapsto \bar x + x^0$ je bijekce mezi množinami $\lbrace \bar x: A\bar x=0\rbrace$ a $\lbrace x: Ax=b\rbrace$.
  • důkaz
    • $U=\lbrace \bar x: A\bar x=0\rbrace,\quad V=\lbrace x: Ax=b\rbrace$
    • $f:U\to V,\quad\bar x \mapsto \bar x+x^0$
    • $g:V\to U,\quad x \mapsto x-x^0$
    • $f$ je bijekce, neboť
      • $g\circ f$ je identita na $U\implies f$ je prosté
      • $f\circ g$ je identita na $V\implies f$ je „na“
    • jiný mechanismus důkazu
      • $f$ je zobrazení: $A\bar x=0\implies A(\bar x+x_0)=A\bar x+Ax_0=0+b=b$
      • $f$ je prosté: $x\neq x' \implies x+x^0 \neq x'+x^0$, což zjevně platí
      • $f$ je na: $(\forall x \in V)(\exists \bar x\in U):x=\bar x + x^0$, takové $\bar x$ lze určit jako $\bar x = x - x^0$

• věta popisující všechna řešení $Ax = b$

  • věta
    • Nechť soustava $Ax=b$ má neprázdnou množinu řešení, kde $A \in \mathbb R^{m\times n}$ je matice hodnosti $r$.
    • Pak všechna řešení $Ax=b$ lze popsat jako $x=x^0+p_1\bar x^1+\dots+p_{n-r}\bar x^{n-r}$.
      • $p$ jsou libovolné reálné parametry
      • $\bar x$ jsou vhodná řešení soustavy $A\bar x=0$
      • $x^0$ je libovolné řešení soustavy $Ax=b$
    • Soustava $A\bar x=0$ má pouze triviální řešení $\bar x=o\iff \text{rank}(A)=n$.
  • důkaz
    • pro $A\bar x=0$
      • přejmenujeme volné proměnné na $p_1,\dots\,p_{n-r}$
      • zpětnou substitucí můžeme vyjádřit každou složku řešení jako lineární funkci volných proměnných
        • $\bar x_1=\alpha_{1,1}p_1+\dots+\alpha_{1,n-r}p_{n-r}$
        • …
        • $\bar x_n=\alpha_{n,1}p_1+\dots+\alpha_{n,n-r}p_{n-r}$
      • zvolíme $\bar x^1=(\alpha_{1,1},\dots,\alpha_{n,1})^T,\dots,\bar x^{n-r}=(\alpha_{1,n-r},\dots,\alpha_{n,n-r})^T$
      • ty řeší $A\bar x=0$, což lze ověřit tak, že pro každý z nich vynulujeme všechny volné proměnné (tedy parametry $p$) kromě toho s odpovídajícím indexem, který nastavíme jako 1
      • je-li $\text{rank}(A)=n$, proměnné jsou jen bázické a $o$ je jediné řešení
    • pro $Ax=b$ vztah plyne z přechozí věty a důkazu této věty pro $Ax=0$
      • ale lze dokázat také pomocí $x_1=\beta_1+\alpha_{1,1}p_1+\dots+\alpha_{1,n-r}p_{n-r}$

• věta o ekvivalentních definicích regulárních matic

  • věta: pro čtvercovou matici $A \in \mathbb R^{n\times n}$ jsou následující podmínky ekvivalentní
    1. matice A je regulární, tedy k ní existuje inverzní matice … $\exists B: AB=I_n$
    2. $\text{rank}(A) = n$
    3. $A\sim\sim I_n$
    4. systém $Ax = 0$ má pouze triviální řešení $x = 0$
  • důkaz
    • $2.\iff 4.$ vyplývá z předchozí věty
      • $\implies$ lze také dokázat tak, že do rovnic dosazujeme zespodu
      • $\impliedby$ lze dokázat sporem (matice s $\text{rank}(A)<n$ musí mít nutně více řešení, protože do volné proměnné lze dosadit libovolnou hodnotu)
    • $2.\implies 3.$ podle Gauss-Jordanovy eliminace, $2.\impliedby3.$ triviálně
    • $2.\implies1.$
      • označme $I_n=(e^1|\dots|e^n)$
      • pro $i\in\lbrace 1,\dots,n\rbrace$ uvažme soustavy $Ax^i=e^i$
      • z $\text{rank}(A)=n$ dostaneme $B=(x^1|\dots|x^n)$
    • $1.\implies2.$
      • pokud $\text{rank}(A)<n$, tak pro jedno (či více) $i$ bude i-tý řádek matice $A$ eliminován ostatními řádky
      • konkrétní rovnice $Ax^i=e^i$ tedy nebude mít žádné řešení, protože onu jedinou jedničku v $e^i$ není možné eliminovat nulami

• věta o znaménku složené permutace

  • věta: Pro libovolné $p,q \in S_n: \text{sgn}(q\circ p)=\text{sgn}(p)\cdot\text{sgn}(q)$.
  • důkaz
    • # inverzí $(q\circ p)=$ # inverzí $p\ +$ # inverzí $q$ $-\ 2|\lbrace(i,j):i\lt j \land p(i) \gt p(j) \land q(p(i)) \lt q(p(j))\rbrace|$
    • od součtu odečítáme dvojité inverze – ty se totiž ve složené permutaci „rozmotají“ (každou takovou inverzi odečítáme dvakrát – jednou za každou permutaci)
    • protože od součtu odečítáme sudé číslo, sudost/lichost součtu je zachována – tedy postačí součin znamének obou permutací (exponenty se sčítají)

• věta charakterizující, kdy $\mathbb{Z}_n$ je těleso

  • věta: $\mathbb Z_p$ je těleso, právě když je $p$ prvočíslo.
  • důkaz
    • $\implies$ pokud by $p$ bylo složené $p=ab$, pak $ab\equiv 0 \mod p$, což je spor s pozorováním, že pokud $ab=0$, pak $a=0$ nebo $b=0$
      • důkaz pozorování (sporem)
        • pro nenulová $a,b$ by existovaly inverzní prvky $a^{-1},b^{-1}$
        • $1=aa^{-1}bb^{-1}=aba^{-1}b^{-1}=0a^{-1}b^{-1}=0$
    • $\impliedby$
      • většina axiomů plyne z vlastností $+$ a $\cdot$ na $\mathbb Z$, kromě existence inverzních prvků $a^{-1}$, protože $\mathbb Z$ není uzavřená na dělení
      • $A = \lbrace 1, \dots, p-1 \rbrace$
      • chceme: $(\forall a \in A)(\exists a^{-1} \in A): aa^{-1} \equiv 1 \mod p$
      • nechť $f_a:A\to A,\quad x\mapsto ax \mod p$
      • hledané $a^{-1}$ splňuje $f_a(a^{-1})=1$
      • tedy stačí ukázat, že 1 je v oboru hodnot $f_a$
      • dokážeme dokonce, že $f_a$ je surjektivní („na“)
      • protože $f_a$ zobrazuje konečnou množinu na sebe samu, pak platí, že je surjektivní, právě když je prosté
      • pokud by pro spor $f_a$ nebylo prosté, pak $\exists b,c: b\gt c \land f_a(b)=f_a(c)$ $\implies 0=f_a(b)-f_a(c)=ab-ac=a(b-c) \mod p$
      • což je spor, neboť $a,(b-c)\in A$

• malá Fermatova věta

  • věta: Pro prvočíslo $p$ a každé $a \in \lbrace 1, \dots, p-1 \rbrace :a^{p-1}\equiv 1 \mod p$.
  • důkaz
    • zobrazení $f_a:x\mapsto ax$ je v $\mathbb Z_p$ bijekcí na $\lbrace 1, \dots, p-1 \rbrace$ (viz výše)
    • proto v $\mathbb Z_p$ platí $\prod_{x=1}^{p-1}x=\prod_{x=1}^{p-1}f_a(x)=\prod_{x=1}^{p-1}ax=a^{p-1}\prod_{x=1}^{p-1}x$
    • a po zkrácení $\prod_{x=1}^{p-1}x$ dostaneme $1=a^{p-1}$
  • důsledek: $a=a^p$ (v tělese $\mathbb Z_p$)

• věta o průniku vektorových prostorů

  • věta
    • Nechť $(U_i,i\in I)$ je libovolný systém podprostorů prostoru $V$
    • Průnik tohoto systému $\bigcap_{i\in I}U_i$ je také podprostorem $V$.
  • důkaz
    • nechť $W=\bigcap_{i\in I}U_i$, ukážeme, že $W$ je uzavřen na $+$ a $\cdot$
    • $\forall u,v \in W: u,v \in W \implies \forall i \in I: u,v \in U_i$ $\implies \forall i \in I: u+v \in U_i \implies u+v \in W$
    • $\forall \alpha \in \mathbb K, v \in W: v \in W \implies \forall i \in I: v\in U_i$ $\implies \forall i \in I: \alpha v \in U_i \implies \alpha v \in W$
    • věta platí i pro $I=\emptyset$, neboť prázdný průnik $\equiv V\Subset V$

• věta o ekvivalentních definicích lineárního obalu

  • věta
    • Nechť $V$ je vektorový prostor nad $\mathbb K$ a $X$ je podmnožina $V$.
    • Potom $\mathcal L(X)$ je množina všech lineárních kombinací vektorů z $X$.
  • důkaz
    • $W_1=\bigcap U:U\Subset V, X\subseteq U$
    • $W_2=\lbrace\sum_{i=1}^{k}\alpha_iv_i:k\in \mathbb N,\alpha_i \in \mathbb K,v_i\in X\rbrace$
    • chceme ukázat $W_1=\mathcal L(X)=W_2$
    • $W_2$ je podprostor, protože je uzavřen na skalární násobky $u\in W_2 \implies u = \sum_{i=1}^{k}\alpha_iv_i$ $\implies \beta u = \beta \sum_{i=1}^{k}\alpha_iv_i = \sum_{i=1}^{k}(\beta\alpha_i)v_i \implies \beta u \in W_2$
    • a analogicky také na součty
    • protože $X \subseteq W_2$, máme $W_2$ mezi protínajícími se podprostory $U_i$
    • z toho plyne $W_1 \subseteq W_2$
    • každý $U_i$ obsahuje $X$ a je uzavřen na sčítání a skalární násobky
    • každý $U_i$ tedy obsahuje všechny lineární kombinace vektorů $X$
    • proto $\forall U_i: W_2 \subseteq U_i \implies W_2 \subseteq W_1$

• Steinitzova věta o výměně (včetně lemmatu, pokud jej potřebujete)

  • lemma o výměně
    • Buď $y_1,\dots,y_n$ systém generátorů vektorového prostoru $V$ a nechť vektor $x \in V$ má vyjádření $x = \sum_{i=1}^n\alpha_iy_i$.
    • Pak pro libovolné $k$ takové, že $\alpha_k \neq 0$, je $y_1,\dots,y_{k-1},x,y_{k+1},\dots,y_n$ systém generátorů prostoru $V$.
  • důkaz lemmatu
    • $x = \sum_i\alpha_iy_i = \sum_{i\neq k}\alpha_iy_i + \alpha_ky_k$
    • $y_k=\frac{1}{\alpha_k}(x-\sum_{i\neq k}\alpha_iy_i)$
    • libovolný vektor $z \in V$ lze vyjádřit jako $z = \sum_i\beta_iy_i=\sum_{i\neq k}\beta_iy_i + \beta_ky_k=\sum_{i\neq k}\beta_iy_i + \frac{\beta_k}{\alpha_k}(x-\sum_{i\neq k}\alpha_iy_i)$ $=\frac{\beta_k}{\alpha_k}x+\sum_{i\neq k}(\beta_i-\frac{\beta_k}{\alpha_k}\alpha_i)y_i$
  • S. věta
    • Buď $V$ vektorový prostor, buď $x_1,\dots,x_m$ lineárně nezávislý systém ve $V$ a nechť $y_1,\dots,y_n$ je systém generátorů $V$.
    • Pak platí $m\leq n$ a existují navzájem různé indexy $k_1,\dots,k_{n-m}$ takové, že $x_1,\dots,x_m,y_{k_1},\dots,y_{k_{n-m}}$ tvoří systém generátorů $V$.
  • důkaz věty matematickou indukcí podle $m$
    • je-li $m=0$, tvrzení platí triviálně
    • předpokládejme, že tvrzení platí pro $m-1$ a ukážeme, že platí i pro $m$
    • kdyby $m-1=n$, pak by vektory $x_1,\dots,x_{m-1}$ byly generátory prostoru $V$, což by byl spor s lineární nezávislostí $x_1,\dots,x_{m}$
      • $\implies m-1\lt n \implies m \leq n\quad\square_1$
    • během indukce vektory postupně nahrazujeme pomocí lemmatu o výměně
    • vycházíme z toho, že věta platí pro $m-1$ vektorů z LN množiny a $n-m+1$ vektorů z množiny generátorů
    • takže m-tý vektor z LN množiny vyjádříme z ostatních a pomocí lemmatu o výměně jím nahradíme (n-m+1)-tý vektor z množiny generátorů
    • lemma o výměně bude možné uplatnit, protože alespoň u jednoho z $n-m+1$ vektorů z množiny generátorů bude ve vyjádření doplňovaného vektoru nenulový koeficient (jinak by to bylo ve sporu s LN) – viz skripta

• věta o jedinečnosti lineárního zobrazení

  • věta
    • Nechť $U$ a $V$ jsou prostory nad $\mathbb K$ a $X$ je báze $U$.
    • Pak pro jakékoliv zobrazení $f_0:X\to V$ existuje jediné lineární zobrazení $f:U\to V$ rozšiřující $f_0$, tj. $\forall u \in X: f(u)=f_0(u)$.
    • (Jinými slovy: To, kam se zobrazí vektory báze, jednoznačně definuje lineární zobrazení jako celek – tedy i zobrazení všech ostatních vektorů daného prostoru.)
  • důkaz
    • vektor $w\in U$ lze jednoznačně vyjádřit jako lineární kombinaci bázických vektorů, tedy $w=\sum_i\alpha_iu_i$
    • potom $f(w)=f(\sum_i\alpha_iu_i)=\sum_i\alpha_if(u_i)=\sum_i\alpha_if_0(u_i)$
  • důsledek: pokud je $f:U\to V$ lineární, pak $\text{dim}(U) \geq \text{dim}(f(U))$, protože obraz $f(X)$ báze $X$ prostoru $U$ generuje $f(U)$

• věta o charakterizaci isomorfismu mezi vektorovými prostory

  • věta: Lineární zobrazení $f:U\to V$ je isomorfismus prostorů $U$ a $V$ s konečnými bázemi $X$ a $Y$ právě tehdy, když $[f]_{X,Y}$ je regulární.
  • důkaz
    • $\impliedby$ uvažme $g:V\to U$ takové, že $[g]_{Y,X}=[f]^{-1}_{X,Y}$, pak
      • $[g \circ f]_{X,X}=[f]^{-1}_{X,Y}[f]_{X,Y}=I_{|X|}=[id]_{X,X}\implies f$ je prosté
      • $[f \circ g]_{Y,Y}=[f]_{X,Y}[f]^{-1}_{X,Y}=I_{|Y|}=[id]_{Y,Y}\implies f$ je „na“
    • $\implies$
      • $[f^{-1}]_{Y,X}[f]_{X,Y}=[id]_{X,X}=I_{|X|}\implies|Y|\geq|X|$
      • $[f]_{X,Y}[f^{-1}]_{Y,X}=[id]_{Y,Y}=I_{|Y|}\implies|X|\geq|Y|$
      • $\implies|X|=|Y|$
      • matice jsou navzájem inverzní (a čtvercové), takže jejich součinem získáváme jednotkovou matici – lze tedy říci, že jsou regulární
  • důsledek: když $f$ je isomorfismus, pak platí $[f^{-1}]_{Y,X}=[f]^{-1}_{X,Y}$

• věta o vektorových prostorech souvisejících s maticí A

  • lemma: Pokud $A'=BA$, pak $\text{dim}(\mathcal S(A'))\leq\text{dim}(\mathcal S(A))$.
  • zkrácený důkaz lemmatu
    • BÚNO předpokládejme, že bázi $\mathcal S(A)$ tvoří $d$ prvních sloupcových vektorů $u$
    • $w \in A, w' \in A'$
    • $w'=Bw=B\sum_{i=1}^d\alpha_iu_i=\sum_{i=1}^d\alpha_iBu_i=\sum_{i=1}^d\alpha_iu'_i$
    • bázi $\mathcal S(A')$ tedy tvoří nejvýše $d$ prvních sloupcových vektorů $u'$
  • věta: Jakákoli $A \in \mathbb K^{m\times n}$ splňuje $\text{dim}(\mathcal R(A))=\text{dim}(\mathcal S(A))$.
  • důkaz věty
    • nechť $A \sim \sim A'$ v odstupňovaném tvaru, neboli existuje regulární $R$ taková, že $A'=RA$
    • podle lemmatu $\text{dim}(\mathcal S(A'))\leq\text{dim}(\mathcal S(A))$
    • z $A=R^{-1}A'$ dostaneme $\text{dim}(\mathcal S(A'))\geq\text{dim}(\mathcal S(A))$, a tudíž i rovnost dimenzí
    • pro matice $A'$ v odstupňovaném tvaru platí věta přímo
      • $\text{dim}(\mathcal R(A'))=$ # pivotů $=\text{rank}(A')=\text{dim}(\mathcal S(A'))$
    • protože $\mathcal R(A)=\mathcal R(A')$, dostaneme
    • $\text{dim}(\mathcal R(A))=\text{dim}(\mathcal R(A'))=\text{dim}(\mathcal S(A'))=\text{dim}(\mathcal S(A))$

• tvrzení o mohutnostech lineárně nezávislé množiny a generující množiny

  • tvrzení: Jestliže $Y$ je konečná generující množina prostoru $V$ a $X$ je lineárně nezávislá ve $V$, potom $|X|\leq |Y|$.
  • důkaz (sporem)
    • předpokládejme, že $Y=\lbrace v_1,\dots,v_n \rbrace$ a že z $X$ lze vybrat různá $u_1,\dots,u_{n+1}$
    • každé $u_i$ vyjádříme jako $u_i=\sum_{j=1}^n a_{i,j}v_j$, přičemž $a_{i,j}\in A$
    • matice $A$ má $n+1$ řádků a $n$ sloupců, z čehož po Gaussově eliminaci nutně plyne nulový řádek, tedy je některý řádek lineární kombinací ostatních
    • to je spor s lineární nezávislostí vektorů $u_1,\dots,u_{n+1}$

• věta o dimenzi průniku vektorových prostorů

  • věta: Jsou-li $U,V$ podprostory konečné generovaného prostoru $W$, pak $\text{dim}(U)+\text{dim}(V)=\text{dim}(U\cap V)+\text{dim}(\mathcal L(U\cup V))$.
  • důkaz: rozšíříme bázi $X$ průniku $U\cap V$ na bázi $Y$ prostoru $U$ a také na bázi $Z$ prostoru $V$, potom $|Y|+|Z|=|X|+|Y\cup Z|$

• věta o dimenzi jádra matice

  • věta: Pro libovolné $A \in \mathbb K^{m\times n}:\text{dim}(\text{ker}(A))+\text{rank}(A)=n$.
  • důkaz
    • nechť $d=n-rank(A)$ je počet volných proměnných a $x_1,\dots,x_d$ jsou řešení soustavy $Ax=0$ daná zpětnou substitucí
    • tato řešení jsou lineárně nezávislá, protože pro každé $i$ platí, že $x_i$ je mezi $x_1,\dots,x_d$ jediné, které má složku odpovídající i-té volné proměnné nenulovou
    • vektory $x_1,\dots,x_d$ tudíž tvoří bázi $\text{ker}(A)$, a proto $\text{dim}(\text{ker}(A))=d=n-rank(A)$

• věta o řešení rovnice s lineárním zobrazením

  • věta: Nechť $f:U\to V$ je lineární zobrazení. Pro libovolné $v \in V$ rovnice $f(u)=v$ buď nemá žádné řešení, nebo řešení tvoří afinní podprostor $u_0+\text{ker}(f)$, kde $u_0$ je libovolné řešení $f(u)=v$.
  • poznámka: tato věta přímo souvisí s větou o vztahu $Ax=b$ a $Ax=0$
  • důkaz
    • když $u\in u_0+\text{ker}(f)$, pak $u=u_0+w$ pro $w \in \text{ker}(f)$
    • nyní $f(u)=f(u_0+w)=f(u_0)+f(w)=v+o=v$
    • naopak pro $f(u)=v$ platí $f(u-u_0)=f(u)-f(u_0)=v-v=0$
    • čili $u-u_0 \in \text{ker}(f)$, tudíž $u\in u_0+\text{ker}(f)$

• pozorování o matici složeného lineárního zobrazení

  • pozorování: Nechť $U,V,W$ jsou vektorové prostory nad $\mathbb K$ s konečnými bázemi $X,Y,Z$. Pro matice lineárních zobrazení $f:U\to V$ a $g:V\to W$ platí, že $[g\circ f]_{X,Z}=[g]_{Y,Z}[f]_{X,Y}$
  • důkaz
    • pro všechny $u \in U$ platí
      • $[(g\circ f)(u)]_Z=[g\circ f]_{X,Z}[u]_X$
      • $[(g\circ f)(u)]_Z=[g(f(u))]_Z=[g]_{Y,Z}[f(u)]_Y=[g]_{Y,Z}[f]_{X,Y}[u]_X$
      • tedy $[g\circ f]_{X,Z}[u]_X=[g]_{Y,Z}[f]_{X,Y}[u]_X$
    • dosadíme-li za $u$ i-tý vektor báze $X$, máme $[u]_X=e^i$ a tedy nám ze vztahu $[g\circ f]_{X,Z}e^i=([g]_{Y,Z}[f]_{X,Y})e^i$ plyne, že matice mají i-té sloupce shodné $\square$

• zformulujte problém o počtu sudých podgrafů a vyřešte jej

  • problém: Kolik sudých podgrafů obsahuje souvislý graf G?
  • řešení
    • sudý podgraf je podgraf, který má sudé stupně všech vrcholů
    • symetrický rozdíl $\bigtriangleup$ zachovává sudé stupně, protože symetrický rozdíl dvou množin sudé mohutnosti má také sudou mohutnost
    • proto $(U,\bigtriangleup,\cdot)$ tvoří vektorový prostor nad $\mathbb Z_2$
    • pro prostory konečné mohutnosti platí $|U|=|\mathbb K|^{\text{dim}(U)}$
    • ekvivalentní problém: sestrojte bázi U
    • zvolme libovolnou kostru T grafu G
    • pro každou hranu $e_i \in E_G \setminus E_T$ definujme $A_i$ jako unikátní cyklus z $T \cup e_i$
    • množina takových cyklů je lineárně nezávislá, protože hrana $e_i$ nemůže být eliminována symetrickým rozdílem $A_i$ s ostatními prvky množiny, neboť ty $e_i$ neobsahují
    • pro libovolný sudý podgraf $B$ označme $B \setminus E_T = \lbrace e_{i_1}, \dots, e_{i_k} \rbrace$
    • graf $B \bigtriangleup A_{i_1}\bigtriangleup\dots\bigtriangleup A_{i_k}$ je sudým podgrafem $G$, ale také je podgrafem $T$, neboť hrany $e_i$ jsou eliminovány
    • strom nemá žádné cykly, tudíž tento rozdíl (výše) je roven nule
    • odtud $B = A_{i_1}\bigtriangleup\dots\bigtriangleup A_{i_k}$
    • dostáváme, že $X$ generuje $U$
    • tedy $\text{dim}(U)=|X|=|E_G|-|E_T|=|E_G|-|V_G|+1$
    • každý souvislý graf $G$ má $2^{|E_G|-|V_G|+1}$ sudých podgrafů

• zformulujte problém o množinových systémech s omezeními na mohutnosti a vyřešte jej

  • problém: Kolik podmnožin může mít n-prvková množina, pokud každá podmnožina má mít lichou velikost, ale průnik každé dvojice různých podmnožin má mít sudou velikost?
  • věta: Vždy platí, že $k \leq n$, neboli existuje nejvýše $n$ takových podmnožin.
  • důkaz
    • uvažujme soustavu podmnožin, která splňuje zadání
    • sestrojíme matici incidence $M\in \mathbb Z^{k\times n}_2$ předpisem $m_{i,j} = \begin{cases} 1 &\text{pokud } j\in A_i \\ 0 &\text{pokud } j\notin A_i\end{cases}$
    • matice splňuje $MM^T=I_k$, protože v součinu řádku a sloupce se stejným indexem je prvků lichý počet (tedy 1 v $\mathbb Z_2$) a u nesouhlasných řádků a sloupců se prvky posčítají na nulu, protože průnik je sudý
    • nyní $k=\text{rank}(I_k)=\text{rank}(MM^T)\leq \text{rank}(M) \leq n$

• zformulujte problém o dělení obdélníku na čtverce a vyřešte jej

  • problém: Lze obdélník s iracionálním poměrem délek jeho stran rozdělit na konečně mnoho čtverců?
  • věta: Pro iracionální poměr žádné takové rozdělení neexistuje.
  • zjednodušený důkaz (sporem)
    • nechť má obdélník $R$ délky stran $1:x$, kde x je iracionální
    • $\mathbb R$ tvoří vektorový prostor nad $\mathbb Q$, zde jsou 1 a x lineárně nezávislé
    • zvolme libovolné lineární zobrazení $f:\mathbb R \to \mathbb R$, kde $f(1)=1$ a $f(x)=-1$
    • pro $A$ o stranách $a,b$ definujeme plochu jako $v(A)=f(a)f(b)$
    • $R$ rozdělíme na čtverce $A$ o stranách délek $a$
    • $-1=f(1)f(x)=v(R)=\sum v(A)=\sum f(a)^2 \geq 0$