Skip to content

Latest commit

 

History

History
557 lines (545 loc) · 37.9 KB

bonusovy-test.md

File metadata and controls

557 lines (545 loc) · 37.9 KB
Raw

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$

Přehledy (13)

přehledově sepište, co víte o…

uveďte definice, tvrzení, věty, příklady a souvislosti – důkazy nejsou vyžadovány

  • elementární řádkové operace a Gaussova eliminace
    • rozšířená matice soustavy
    • 4 typy elementárních řádkových úprav
      • elementární matice
    • odstupňovaný tvar matice
    • věta o totožnosti řešení
    • Gaussova eliminace
    • zpětná substituce
    • věta o libovolné volbě volných proměnných (jakoukoli volbu volných proměnných lze jednoznačně rozšířit na řešení)
    • věta o jednoznačnosti sloupců s pivoty (o jednoznačnosti volných a bázických proměnných)
    • bázické a volné proměnné
    • hodnost matice
    • Frobeniova věta
  • řešení homogenních a nehomogenních soustav lineárních rovnic
    • homogenní × nehomogenní soustava rovnic
    • věta o vztahu mezi řešeními $Ax = b$ a $Ax = 0$
    • věta popisující všechna řešení $Ax = b$
    • homogenní soustava má triviální řešení $x = 0$, když $\text{rank}(A) = n$
    • provedení zkoušky (dosazení řešení včetně parametrů do původní soustavy)
    • redukovaný odstupňovaný tvar
  • maticové operace
    • nulová matice, jednotková matice, hlavní diagonála
    • transponovaná matice, symetrická matice
    • součet matic, α-násobek matice
    • součin matic, jeho asociativita
    • elementární matice
    • inverzní matice
    • maticové rovnice (viz níže)
  • regulární a singulární matice
    • inverzní matice, její jednoznačnost
    • regulární × singulární matice
    • věta o ekvivalentních definicích regulárních matic
    • výpočet inverzní matice
    • vlastnosti regulárních matic
      • pro $R$ regulární: $A=B \iff AR=BR \iff RA=RB$
      • pro $A,B$ regulární (stejného řádu)
        • $(A^{-1})^{-1}=A$
        • $AB$ je regulární
        • $(AB)^{-1}=B^{-1}A^{-1}$
        • $(A^T)^{-1}=(A^{-1})^T$
    • maticové rovnice (viz prezentace)
      • $A+X=B \implies X=B-A$
      • $\alpha X=B \implies X=\frac{1}{\alpha}B$
      • $AX=B \implies X=A^{-1}B$ pro regulární A
      • $XA=B \implies X=BA^{-1}$ pro regulární A
  • binární operace a jejich vlastnosti
    • binární operace jako zobrazení
    • komutativita, asociativita
    • neutrální prvek, inverzní prvek
  • (obecné) grupy
    • definice grupy
    • binární operace a jejich vlastnosti
    • aditivní a multiplikativní grupy
    • vlastnosti grup (jednoznačnost neutrálního prvku, jednoznačnost inverzního prvku, ekvivalentní úpravy, jednoznačnost řešení rovnic)
  • permutační grupy
    • permutace jako zobrazení (bijekce)
    • způsob popisu permutace (tabulkou, jejím druhým řádkem, pomocí bipartitního grafu, podle grafu cyklů, seznamem cyklů, pomocí permutační matice P)
    • množina $S_n$ všech permutací na $n$ prvcích s operací skládání tvoří symetrickou grupu
      • identita je neutrální prvek
    • pevný bod, transpozice, inverze
    • znaménko permutace (sudé/liché permutace)
    • věta o znaménku složené permutace
  • tělesa
    • definice tělesa
    • distributivita
    • konečná tělesa – zbytkové třídy modulo prvočíslo $p$, Galoisovo těleso (těleso o velikosti $n$ existuje $\iff n$ je mocninou prvočísla)
    • metavěta – tvrzení o soustavách rovnic, maticích a výpočtech nad reálnými čísly platí i v libovolném tělese
    • vlastnosti tělesa (jednoznačnost neutrálních a inverzních prvků, korektnost ekvivalentních úprav, řešitelnost rovnic)
    • pokud $ab = 0$, pak $a = 0$ nebo $b = 0$
    • charakteristika tělesa
    • věta charakterizující, kdy $\mathbb Z_n$ je těleso
    • malá Fermatova věta
  • vektorové prostory a jejich podprostory
    • definice vektorového prostoru nad tělesem
    • binární operace ve vektorovém prostoru
    • aritmetický vektorový prostor, vektorový prostor matic, triviální vektorový prostor (pouze nulový vektor)
    • vlastnosti vektorových prostorů (jednoznačnost nulového a opačného vektoru, korektnost ekvivalentních úprav, řešitelnost rovnic)
    • definice podprostoru
    • věta o průniku podprostorů
    • lineární obal, generátory podprostoru
    • lineární kombinace
    • věta o ekvivalentních definicích lineárního obalu
  • vektorové prostory určené maticí A
    • jádro, řádkový prostor, sloupcový prostor
    • elementární úpravy nemění jádro ani řádkový prostor
    • (technické) lemma o dimenzích sloupcového prostoru
    • věta o dimenzích sloupcového a řádkového prostoru matice
    • počet řádků matice je roven součtu dimenze jádra a hodnosti matice (tedy dimenzi sloupcového/řádkového prostoru)
  • lineární závislost
    • definice lineární nezávislosti (LN)
    • lineární nezávislost řádků matice v odstupňovaném tvaru
    • lineární nezávislost podmnožin (podmnožina lineárně nezávislé množiny bude rovněž nezávislá apod.)
    • báze vektorového prostoru
  • báze vektorových prostorů
    • definice báze
    • lineární nezávislost
    • vektor souřadnic
    • kanonická báze v aritmetickém vektorovém prostoru
    • věta o existenci báze (každý vektorový prostor má bázi)
    • lemma o výměně
    • Steinitzova věta o výměně
    • jakoukoliv LN množinu lze rozšířit na bázi
    • všechny báze konečně generovaného prostoru mají stejnou mohutnost
    • dimenze vektorového prostoru
  • lineární zobrazení a jejich matice
    • definice lineárního zobrazení
    • triviální lineární zobrazení (na nulový vektor), identita
    • geometrická lineární zobrazení (rotace, osová souměrnost podle osy procházející počátkem, stejnolehlost se středem v počátku)
    • skládání lineárních zobrazení, existence inverze pro bijektivní zobrazení (isomorfismus)
    • transformace na vektor souřadnic
    • věta o rozšiřitelnosti (jedinečnosti) lineárního zobrazení
    • afinní prostor a jeho dimenze
    • matice lineárního zobrazení
    • matice přechodu
    • isomorfismus vektorových prostorů