Skip to content

Latest commit

 

History

History
700 lines (694 loc) · 51.4 KB

bonusovy-test.md

File metadata and controls

700 lines (694 loc) · 51.4 KB
Raw

Bonusový test

Definice (37)

  • 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$
  • 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ů
  • determinant
    • determinant matice $A\in\mathbb K^{n\times n}$ je dán výrazem $$\text{det }A=\sum_{p\in S_n}\text{sgn}(p)\prod_{i=1}^na_{i,p(i)}$$
  • adjungovaná matice
    • $A^{ij}$ je podmatice získaná z $A$ odstraněním $i$-tého řádku a $j$-tého sloupce
    • pro $A\in\mathbb K^{n\times n}:(\text{adj }A)_{ji}=(-1)^{i+j}\cdot\text{det }A^{ij}$
    • tzn. faktory Laplaceova rozvoje podél i-tého řádku matice $A$ ukládáme do i-tého sloupce $\text{adj }A$
  • Laplaceova matice
    • Laplaceova matice grafu $G$ na $V_G=\lbrace v_1,\dots,v_n\rbrace$ je $L_G\in\mathbb R^{n\times n}$ taková, že $$(L_G)_{ij}= \begin{cases} \text{deg}(v_i) &\text{pro } i=j \ -1 &\text{jestliže }i\neq j\land (v_i,v_j)\in E_G \ 0 &\text{jinak}\end{cases}$$
  • polynom nad tělesem
    • polynom stupně $n$ v proměnné $x$ nad tělesem $\mathbb K$ je výraz $p(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_2x^2+a_1x+a_0$, kde $a_n\neq 0$ a $a_n,\dots,a_0\in\mathbb K$
    • píšeme $p\in\mathbb K(x)$
  • kořen polynomu a jeho násobnost
    • kořen polynomu $p\in\mathbb K(x)$ je $r\in\mathbb K$ takové, že $p(r)=0$
    • násobnost kořene $r$ z $p\in\mathbb K(x)$ je největší kladné celé číslo $k$ takové, že $(x-r)^k$ dělí $p$
  • algebraicky uzavřené těleso
    • pokud každý polynom $p\in\mathbb K(x)$ stupně alespoň jedna má alespoň jeden kořen, pak je těleso $\mathbb K$ algebraicky uzavřené
  • Vandermondova matice
    • značí se $V_{n+1}(x_0,\dots,x_n)$, přičemž prvky jsou určeny takto: $v_{ij}=x_{i-1}^{j-1}$
    • v každém řádku je geometrická posloupnost s kvocientem $x_i$ (posloupnost začíná jedničkou a končí $x_i^n$)
  • vlastní číslo a vlastní vektor lineárního zobrazení
    • mějme vektorový prostor $V$ nad tělesem $\mathbb K$ a lineární zobrazení $f:V\to V$
    • vlastní číslo zobrazení $f$ je jakékoliv $\lambda\in\mathbb K$, pro které existuje vektor $u\in V\setminus \lbrace 0\rbrace$ takový, že $f(u)=\lambda u$
    • vlastní vektor odpovídající vlastnímu číslu $\lambda$ je libovolný vektor $u\in V$ takový, že $f(u)=\lambda u$
    • množina všech vlastních čísel matice je jejím spektrem
  • vlastní číslo a vlastní vektor matice
    • mějme vektorový prostor $V$ nad tělesem $\mathbb K$ a matici $A\in\mathbb K^{n\times n}$
    • vlastní číslo matice $A$ je jakékoliv $\lambda\in\mathbb K$, pro které existuje vektor $x\in V\setminus \lbrace 0\rbrace$ takový, že $Ax=\lambda x$
    • vlastní vektor odpovídající vlastnímu číslu $\lambda$ je libovolný vektor $x\in V$ takový, že $Ax=\lambda x$
    • množina všech vlastních čísel matice je jejím spektrem
  • charakteristický polynom
    • charakteristický polynom matice $A\in\mathbb K^{n\times n}$ je $p_A(t)=\text{det}(A-tI_n)$
  • algebraická násobnost vlastního čísla
    • odpovídá násobnosti daného vlastního čísla jako kořene charakteristického polynomu
  • geometrická násobnost vlastního čísla
    • geometrická násobnost vlastního čísla je dimenze podprostoru jeho vlastních vektorů
  • podobné matice
    • matice $A,B\in\mathbb K^{n\times n}$ jsou si podobné, pokud existuje regulární matice $R$ taková, že $A=R^{-1}BR$
  • diagonalizovatelná matice
    • matice podobná diagonální matici je diagonalizovatelná
  • Jordanův blok
    • Jordanův blok je čtvercová matice, která má na hlavní diagonále dané vlastní číslo, na diagonále nad ní má jedničky a všude jinde má nuly
  • Jordanův normální tvar matice
    • matice v Jordanově normálním tvaru má na diagonále Jordanovy bloky (a všude jinde nuly)
  • zobecněný vlastní vektor
    • zobecněný vlastní vektor matice $A$ k vlastnímu číslu $\lambda$ je libovolný vektor $x$ splňující $(A-\lambda I)^ix=0$ pro nějaké $i\in\mathbb N$
    • lze je řadit do řetězců $x_k,\dots,x_2,x_1,0$, kde $(A-\lambda I)x_i=x_{i-1}$
  • hermitovská matice
    • hermitovská transpozice komplexní matice $A\in\mathbb C^{m\times n}$ je matice $A^H\in\mathbb C^{n\times m}$, kde $(A^H){ij}=\overline{a{ji}}$
    • matice $A$ je hermitovská, pokud $A=A^H$
  • unitární matice
    • matice $A$ je unitární, pokud $A^{-1}=A^H$ (tedy $A^HA=I_n$)
  • skalární součin pro vektorové prostory nad komplexními čísly
    • skalární součin na vektorovém prostoru $V$ nad $\mathbb C$ je zobrazení, které přiřadí každé dvojici vektorů $u,v\in V$ skalár $\langle u|v\rangle\in\mathbb C$ tak, že jsou splněny následující axiomy:
      • $\forall u\in V:\langle u|u\rangle\in\mathbb R^+_0$ (reálné číslo $\geq 0$)
      • $\forall u\in V:\langle u|u\rangle=0\iff u=0$
      • $\forall u,v\in V: \langle v|u\rangle=\overline{\langle u|v\rangle}$ (komplexně sdružené)
      • $\forall u,v,w \in V: \langle u+v|w\rangle=\langle u|w\rangle+\langle v|w\rangle$
      • $\forall u,v\in V,,\forall \alpha\in\mathbb C: \langle \alpha u|v\rangle=\alpha\langle u|v\rangle$
    • formálně je každý skalární součin zobrazení $V\times V\to\mathbb C$
    • skalární součin na $V$ nad $\mathbb R$ je zobrazení $V\times V\to\mathbb R$, přičemž $\langle v|u\rangle = \langle u|v\rangle$ (ve třetím axiomu), $\alpha\in\mathbb R$ (v posledním axiomu)
    • standardní skalární součin na $\mathbb R^n$: $\langle u|v\rangle=v^Tu$
    • standardní skalární součin na $\mathbb C^n$: $\langle u|v\rangle=v^Hu$
  • norma spojená se skalárním součinem
    • je-li $V$ prostor se skalárním součinem, pak norma odvozená ze skalárního součinu je zobrazení $V\to R^+_0$ přiřazující vektoru $u$ jeho normu $||u||=\sqrt{\langle u|u\rangle}$
    • geometrická interpretace v euklidovském prostoru $\mathbb R^n$
      • $||u||$ … délka (velikost) $u$
      • $||u-v||$ … vzdálenost bodů $u,v$
      • $\langle u|v\rangle$ souvisí s „úhlem“ $\varphi$ mezi $u,v$ a délkami $u,v$
        • $\langle u|v\rangle=||u||\cdot||v||\cos\varphi$
        • to vyplývá z kosinové věty, kde $a=||u||,,b=||v||,,c=||u-v||$
  • kolmé vektory
    • vektory $u,v$ z prostoru se skalárním součinem jsou kolmé, pokud $\langle u|v\rangle=0$
    • kolmé vektory značíme $u\perp v$
  • ortonormální báze
    • bázi $Z=\lbrace v_1,\dots,v_n \rbrace$ prostoru $V$ se skalárním součinem nazveme ortonormální, pokud platí $v_i\perp v_j$ pro každé $i\neq j$ a také $||v_i||=1$ pro každé $v_i\in Z$
    • pozorování: matice, jejichž sloupce tvoří vektory ortonormální báze $\mathbb C^n$ vzhledem ke std. skal. součinu, splňují $A^HA=I_n\implies$ jsou unitární
  • Fourierovy koeficienty
    • nechť $Z=\lbrace v_1,\dots,v_n\rbrace$ je ortonormální báze prostoru $V$
    • tvrzení: pro každé $u\in V$ platí $u=\langle u|v_1\rangle v_1+\dots+\langle u|v_n\rangle v_n$
    • $\langle u|v_i\rangle$ … Fourierovy koeficienty
    • důkaz: (vyplývá z toho, že $\langle v_i|v_j\rangle$ se rovná jedné pro $i=j$, jinak nule) $$u=\sum^n_{i=1} \alpha_iv_i\implies\langle u|v_j\rangle=\left\langle \sum^n_{i=1} \alpha_iv_i\middle|v_j\right\rangle=\sum^n_{i=1}\alpha_i\langle v_i|v_j\rangle=\alpha_j$$
  • kolmá projekce
    • nechť $W$ je prostor se skalárním součinem a $V$ je jeho podprostor s ortonormální bází $Z=(v_1,\dots,v_n)$
    • zobrazení $p_Z:W\to V$ definované $p_Z(u)=\sum^n_{i=1}\langle u|v_i \rangle v_i$ je ortogonální (kolmá) projekce $W$ na $V$
  • izometrie
    • lineární zobrazení $f$ mezi prostory $V$ a $W$ je izometrie, pokud zachovává skalární součin, neboli $\langle u|w\rangle = \langle f(u)|f(w)\rangle$
  • ortogonální doplněk
    • ortogonální doplněk podmnožiny $V$ prostoru se skalárním součinem $W$ je $V^\perp=\lbrace u\in W\mid\forall v\in V: u\perp v\rbrace$
  • Gramova matice
    • nechť $V$ je prostor se skalárním součinem a bází $X=(v_1,\dots,v_n)$
    • Gramova matice $A$ je definovaná jako $a_{ij}=\langle v_i|v_j\rangle$
    • dle věty platí $\forall u,w\in V:\langle u|w\rangle=[w]_X^HA^T[u]_X$
  • pozitivně definitní matice
    • pokud hermitovská matice $A$ řádu $n$ vyhovuje $\forall x\in\mathbb C^n\setminus \lbrace 0\rbrace: x^HAx\gt 0$, pak je pozitivně definitní
  • Choleského rozklad
    • věta: pro každou pozitivně definitní matici $A$ existuje unikátní horní trojúhelníková matice $U$ s kladnou diagonálou taková, že $A=U^HU$
    • matice $U$ se nazývá Choleského rozklad
  • bilineární forma
    • nechť $V$ je vektorový prostor nad tělesem $\mathbb K$ a nechť zobrazení $f:V\times V\to \mathbb K$ splňuje
      • $\forall u,v\in V,,\forall \alpha\in\mathbb K:f(\alpha u,v)=f(u,\alpha v)=\alpha f(u,v)$
      • $\forall u,v,w\in V:f(u+v,w)=f(u,w)+f(v,w)$
      • $\forall u,v,w\in V:f(u,v+w)=f(u,v)+f(u,w)$
    • poté se $f$ nazývá bilineární forma na $V$
    • bilineární forma je symetrická, když $\forall u,v\in V:f(u,v)=f(v,u)$
  • kvadratická forma
    • zobrazení $g:V\to\mathbb K$ se nazývá kvadratická forma, pokud existuje bilineární forma $f$ taková, že $g(u)=f(u,u)$ pro všechny $u\in V$
  • matice bilineární formy vzhledem k bázi
    • nechť $V$ je vektorový prostor nad tělesem $\mathbb K$ s bází $X=(v_1,\dots,v_n)$
    • matice bilineární formy $f$ vzhledem k bází $X$ je matice $B$ definovaná $b_{ij}=f(v_i,v_j)$
    • matice kvadratické formy $g$ je matice symetrické bilineární formy $f$ odpovídající $g$, pokud taková symetrická $f$ existuje
    • pozorování o použití matic forem: $f(u,w)=[u]^T_XB[w]_X$ (důkaz pomocí vyjádření z bázických vektorů)
  • analytické vyjádření formy
    • analytické vyjádření bilineární formy $f$ nad $\mathbb K^n$ s maticí $B$ je homogenní polynom $f((x_1,\dots,x_n)^T,(y_1,\dots,y_n)^T)=\sum^n_{i=1}\sum^n_{j=1}b_{ij}x_iy_j$
  • signatura formy
    • nechť reálná kvadratická forma $g$ má diagonální matici $B$ obsahující pouze $1,-1$ a $0$
    • signatura formy $g$ je trojice (počet jedniček, počet minus jedniček, počet nul), počítáno na diagonále matice $B$

Věty a důkazy (30)

  • věta o linearitě determinantu
    • věta
      • Determinant matice je lineárně závislý na každém jejím řádku a sloupci, tj vzhledem ke skalárnímu násobku řádku: $$\begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & & \vdots \ \alpha\cdot a_{i1} & \alpha\cdot a_{i2} & \cdots & \alpha\cdot a_{in}\ \vdots & \vdots & & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} \end{vmatrix}=\alpha\cdot \begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & & \vdots \ a_{i1} & a_{i2} & \cdots & a_{in}\ \vdots & \vdots & & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} \end{vmatrix}$$ a vzhledem ke sčítání řádků: $$\begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & & \vdots \ b_{i1}+c_{i1} & b_{i2}+c_{i2} & \cdots & b_{in}+c_{in}\ \vdots & \vdots & & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} \end{vmatrix}=$$ $$=\begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & & \vdots \ b_{i1} & b_{i2} & \cdots & b_{in}\ \vdots & \vdots & & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} \end{vmatrix}+\begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & & \vdots \ c_{i1} & c_{i2} & \cdots & c_{in}\ \vdots & \vdots & & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} \end{vmatrix}$$
    • důkaz
      • důkaz pro skalární násobek
        • poznámka: počáteční matici označím jako $A$, koncovou jako $B$, obě matice viz výše
        • $\alpha$ bude v každém součinu právě jednou (pro $i=j$) a ze součtu ho můžu vytknout, tedy $$\text{det }A=\sum_{p\in S_n}\text{sgn}(p)\left(\alpha\cdot\prod_{j=1}^na_{j,p(j)}\right)=$$ $$=\alpha\cdot\sum_{p\in S_n}\text{sgn}(p)\prod_{j=1}^na_{j,p(j)}=\text{det }B$$
      • důkaz pro součet
        • mějme matice $A,B,C$
        • přičemž platí $a_{kl}=b_{kl}+c_{kl}$ pro $k= i$, jinak $a_{kl}=b_{kl}=c_{kl}$
        • chceme $\text{det }A=\text{det }B+\text{det }C$
        • aplikujeme algebraické úpravy: $$\begin{gather*}\text{det }A=\sum_{p\in S_n}\text{sgn}(p)\prod_{j}a_{j,p(j)}=\sum_{p\in S_n}a_{i,p(i)}\cdot\text{sgn}(p)\prod_{j\neq i}a_{j,p(j)}= \ =\sum_{p\in S_n}(b_{i,p(i)}+c_{i,p(i)})\cdot\text{sgn}(p)\prod_{j\neq i}a_{j,p(j)}=\ =\sum_{p\in S_n}b_{i,p(i)}\cdot\text{sgn}(p)\prod_{j\neq i}b_{j,p(j)}+\sum_{p\in S_n}c_{i,p(i)}\cdot\text{sgn}(p)\prod_{j\neq i}c_{j,p(j)}=\ =\sum_{p\in S_n}\text{sgn}(p)\prod_{j}b_{j,p(j)}+\sum_{p\in S_n}\text{sgn}(p)\prod_{j}c_{j,p(j)}=\text{det }B+\text{det }C\end{gather*}$$
      • z toho lze za použití dalšího lemmatu (že matice se dvěma stejnými řádky nebo dvěma stejnými sloupci má nulový determinant) odvodit, že přičtení násobku řádku k jinému řádku matice nezmění determinant
      • v konečném důsledku z toho vyplývá, že singulární matice má nulový determinant
  • věta o determinantu součinu dvou matic
    • věta: Pro libovolné $A,B\in\mathbb K^{n\times n}:\text{det}(AB)=\text{det }A\cdot\text{det }B$.
    • důkaz
      • $A,B$ jsou BÚNO regulární (jinak dostaneme $0=0$)
      • pro součin s elementárními maticemi věta platí, protože
        • pro přičtení řádku k jinému řádku: $\text{det }E=1$
        • pro vynásobení řádku $\alpha$: $\text{det }E=\alpha$
        • z těchto lze odvodit ostatní operace
      • rozložíme regulární $A$ na elementární matice $A=E_1\dots E_k$
      • $\text{det}(AB)=\text{det}(E_1\dots E_kB)=\text{det }E_1\cdot\text{det}(E_2\dots E_kB)=$
      • $=\text{det }E_1\dots\text{det }E_k\cdot\text{det }B=\text{det}(E_1\dots E_k)\cdot\text{det }B=$
      • $=\text{det }A\cdot\text{det }B$
    • důsledek: $\text{det}(A^{-1})=(\text{det }A)^{-1}$, neboť $\text{det }A\cdot\text{det}(A^{-1})=\text{det}(AA^{-1})=\text{det }I=1$
    • důsledek: $A$ je regulární $\iff\text{det }A\neq0$
  • věta o Laplaceově rozvoji determinantu
    • notace: $A^{ij}$ je podmatice získaná z $A$ odstraněním i-tého řádku a j-tého sloupce
    • věta: Pro libovolné $A\in\mathbb K^{n\times n}$ a jakékoli $i\in \lbrace 1,\dots,n\rbrace$ platí $$\text{det }A=\sum^n_{j=1}a_{ij}(-1)^{i+j}\text{ det }A^{ij}$$
    • důkaz
      • vyjádříme i-tý řádek jako lineární kombinaci vektorů kanonické báze (transponované do řádků) a použijeme linearitu
      • $(a_{i1},a_{i2},\dots,a_{in})=a_{i1}e^T_1+a_{i2}e^T_2+\dots+a_{in}e^T_n$
      • z linearity vyplývá, že se determinant původní matice rovná součtu $n$ členů, kde j-tý člen je roven $a_{ij}$-násobku determinantu matice, která má místo i-tého řádku j-tý kanonický vektor, tedy $$\begin{vmatrix} &&& \ a_{i1} & a_{i2} & \cdots & a_{in} \ &&& \end{vmatrix}=a_{i1}\begin{vmatrix} &&& \ 1 & 0 & \cdots & 0 \ &&& \end{vmatrix}+a_{i2}\begin{vmatrix} &&& \ 0 & 1 & \cdots & 0 \ &&& \end{vmatrix}+\cdots$$
      • pro j-tou matici provedeme dvě úpravy: posuneme i-tý řádek na první pozici a posuneme j-tý sloupec na první pozici
      • tím dostaneme na prvním řádku $e_1$
      • determinant matice, která má na prvním řádku $e_1$, odpovídá determinantu podmatice vzniklé odebráním prvního řádku a prvního sloupce
      • při posunutí k-tého řádku/sloupce na první pozici je potřeba determinant výsledné vynásobit $(-1)^{k+1}$, aby se rovnal determinantu původní matice
        • poznámka: podle mého názoru by to mělo být spíše $(-1)^{k-1}$, ale na tom nezáleží
      • po obou posunech dostaneme $(-1)^{i+1+j+1}=(-1)^{i+j}$
  • Cramerovo pravidlo (řešení systémů s determinanty)
    • věta
      • Nechť $A\in\mathbb K^{n\times n}$ je regulární matice.
      • Pro jakékoliv $b\in\mathbb K^{n}$ řešení $x$ soustavy $Ax=b$ splňuje $x_i=\frac 1{\text{det }A}\text{ det }A_{i\to b}$, kde $A_{i\to b}$ získáme z $A$ nahrazení i-tého sloupce vektorem $b$.
    • důkaz
      • označme $a_1,\dots,a_n$ sloupce matice $A$
      • soustavu $Ax=b$ lze přepsat po sloupcích na vztah $\sum^n_{j=1}x_ja_j=b$
        • $x_j$ je skalár
      • z linearity determinantu podle i-tého sloupce (funguje díky linearitě součtu v řádku a díky tomu, že transpozice nemění determinant) dostáváme $$\text{det }A_{i\to b}=\text{det }A_{i\to\sum^n_{j=1}x_ja_j}=\sum^n_{j=1}x_j\text{ det }A_{i\to a_j}=x_i\text{ det }A$$
      • pro $i\neq j$ je totiž determinant nulový, neboť v dané matici se jeden sloupec opakuje
  • věta o adjungované matici
    • věta: Pro regulární matici $A\in\mathbb K^{n\times n}:A^{-1}=\frac1{\text{det }A}\text{ adj }A$.
    • důkaz
      • Laplaceovým rozvojem $\text{det }A$
      • (i-tý řádek z $A$) $\cdot$ (i-tý sloupec z $\text{adj }A$) $=\text{det }A$
        • to vyplývá z definice – faktory Laplaceova rozvoje podél i-tého řádku $A$ ukládáme do i-tého sloupce $\text{adj }A$
        • přičemž tyto faktory jsou v Laplaceově rozvoji násobeny postupně prkvy i-tého řádku $A$ a sečteny – výsledkem je determinant $A$
        • z toho vyplývá, že součin $A$ a k ní adjungované bude mít na diagonále determinant $A$
      • pro $j\neq i$: (j-tý řádek z $A$) $\cdot$ (i-tý sloupec z $\text{adj }A$) $=\text{det}(A')=0$
        • $A'$ se totiž získá nahrazením i-tého řádku tím j-tým
        • u toho vyplývá, že součin $A$ a k ní adjungované bude mít mimo diagonálu nuly
      • $A\cdot\text{adj }A=\text{det }A\cdot I\implies A\cdot(\frac1{\text{det }A}\text{ adj }A)=I$
  • věta o počtu koster grafu
    • věta: Každý multigraf $G$ s $|V_G|\geq 2$ splňuje $\kappa(G)=\text{det }L_G^{11}.$
    • důkaz
      • pomocné lemma: $\kappa(G)=\kappa(G-e)+\kappa(G\circ e)$
        • všechny kostry grafu $G$ lze rozdělit podle toho, zda obsahují hranu $e$
        • kostry grafu $G-e$ jsou ty kostry $G$, které hranu $e$ neobsahují
        • kostry grafu $G\circ e$ jsou kostry $G$, které hranu $e$ obsahují ($\circ$ značí kontrakci hrany)
      • $G$ je BÚNO souvislý, důkaz indukcí podle $|E_G|$
      • základní případ
        • pro $|E_G|=1$ má $G$ jen dva vrcholy a $\kappa(G)=1=\text{deg}(v_2)=(L_G)_{22}=\text{det }L_G^{11}$
      • indukční krok
        • zvolme libovolnou $e\in E_G$, BÚNO $e=(v_1,v_2)$
          • předpokládáme, že jsou vrcholy očíslovány tak, aby zvolená hrana vedla právě takto
        • označme $A=L_G^{11},,B=L_{G-e}^{11},,C=L_{G\circ e}^{11}$
        • $C$ je podmatice $L_G$ odpovídající $v_3,\dots,v_n$, tedy $C=A^{11}=B^{11}$
        • z indukčního předpokladu: $\kappa(G-e)=\text{det }B,,\kappa(G\circ e)=\text{det }C$
        • $A,B$ jsou shodné kromě $b_{11}=a_{11}-1$, protože vypuštěním $e$ klesne stupeň $v_2$ o jedna
        • první sloupec $A$ vyjádříme jako součet prvního sloupce $B$ a vektoru $e_1$
        • linearitou determinantu matice $A$ podél tohoto rozkladu prvního sloupce získáme $\text{det }A=\text{det }B+\text{det }C$
        • $\kappa(G)=\kappa(G-e)+\kappa(G\circ e)=\text{det }L_{G-e}^{11}+\text{det }L_{G\circ e}^{11}=\text{det }L_G^{11}$
  • malá Fermatova věta
    • věta: Pro libovolné $x\in\mathbb Z_p\setminus\lbrace 0\rbrace:x^{p-1}=1$.
    • důkaz
      • zobrazení $f_a:x\mapsto ax$ je v $\mathbb Z_p$ bijekcí na $\lbrace 1, \dots, p-1 \rbrace$
      • 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$), případně $a^p-a=0$
    • důsledek: pro každý $q\in\mathbb Z_p(x)$ existuje $r\in\mathbb Z_p(x)$ stupně nejvýše $p-1$ takový, že $\forall x\in\mathbb Z_p:q(x)=r(x)$
  • věta o Vandermondově matici
    • věta: Vandermondova matice $V_{n+1}(x_0,\dots,x_n)$ je regulární $\iff x_0,\dots,x_n$ jsou různá.
    • jak vypadá V. matice: v každém řádku je geometrická posloupnost s kvocientem $x_i$ (posloupnost začíná jedničkou a končí $x_i^n$)
    • důkaz
      • odečteme první řádek matice od všech ostatních (vzniklou matici označme $A$)
      • v prvním soupci je jedna jednička a pod ní $n$ nul, takže podle Laplaceova rozvoje dostaneme determinant matice bez prvního řádku a prvního sloupce (matice $A^{11}$)
      • z každého řádku vytkneme $(x_i-x_0)$, matici označme jako $B$
      • tedy $$\text{det }V_{n+1}=\text{det }A=\text{det }A^{11}=\left(\prod^n_{i=1}(x_i-x_0)\right)\cdot\text{det }B$$
      • nyní odzadu odečteme od každého sloupce $x_0$-násobek předchozího, tak eliminujeme všechny sčítance obsahující $x_0$
      • získáme rekurenci $$\text{det}(V_{n+1}(x_0,\dots,x_n))=\left(\prod_{i=1}^n(x_i-x_0)\right)\cdot\text{det}(V_n(x_1,\dots,x_n))$$
      • z toho plyne $$\text{det}(V_{n+1}(x_0,\dots,x_n))=\prod_{i\lt j}(x_j-x_i)$$
  • Lagrangeova interpolace (a její správnost)
    • Lagrangeova interpolace je alternativní způsob interpolace polynomu $p\in\mathbb K(x)$ stupně $n$ skrz $n+1$ bodů $(x_i,y_i)$
    • určení polynomu (a důkaz správnosti)
      • určíme $n+1$ pomocných polynomů stupně $n$ $$p_i(x)=\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}$$
        • v čitateli je součin dvojčlenů, jmenovatel je konstanta
        • všimneme si, že $p_i(x_i)=1$ a že $p_i(x_j)=0$ pro $i\neq j$
          • to je vidět po dosazení za $x$
      • sestavíme $p(x)$ jako lineární kombinaci $p(x)=\sum^{n+1}_{j=1}y_jp_j(x)$
        • tzn. každý z pomocných polynomů vynásobím odpovídajícím $y_i$
      • potom platí $p(x_i)=y_ip_i(x_i)=y_i$, protože ve všech ostatních sčítancích je $p_j(x_i)$ roven nule
  • věta o podprostoru vlastních vektorů
    • věta: Vlastní vektory odpovídající stejnému vlastnímu číslu tvoří podprostor.
    • důkaz
      • uvažme vlastní číslo $\lambda$ lineárního zobrazení $f:V\to V$ a množinu $U=\lbrace u \in V: f(u)=\lambda u\rbrace$
        • tedy $U$ je množina vlastních vektorů odpovídajících danému vlastnímu číslu
      • pro jakékoli $u,v\in U$ a $\alpha\in \mathbb K$ dostaneme
        • $f(\alpha u)=\alpha f(u)=\alpha\lambda u=\lambda(\alpha u)$
        • $f(u+v)=f(u)+f(v)=\lambda u+\lambda v=\lambda(u+v)$
      • z toho plyne, že je $U$ uzavřen na sčítání a skalární násobky, tedy je podprostorem $V$
  • věta o lineární nezávislosti vlastních vektorů
    • věta: Nechť $f:V\to V$ je lineární zobrazení a $\lambda_1,\dots,\lambda_k$ jsou různá vlastní čísla $f$ a $u_1,\dots,u_k$ odpovídající netriviální vlastní vektory. Potom $u_1,\dots,u_k$ jsou lineárně nezávislé.
    • důkaz
      • pro spor přepdokládejme, že $k$ je nejmenší číslo, pro které existují vlastní čísla a vektory odporující větě
      • tedy $\sum^k_{i=1}\alpha_iu_i=0$, přičemž alespoň jedno $\alpha_i$ je nenulové, tedy $\exists i:\alpha_i\neq 0$
      • nulový vektor vyjádříme dvěma způsoby
        • $0=\lambda_k0=\lambda_k\sum^k_{i=1}\alpha_iu_i=\sum^k_{i=1}\lambda_k\alpha_iu_i$
        • $0=f(0)=f\left(\sum^k_{i=1}\alpha_iu_i\right)=\sum^k_{i=1}\alpha_if(u_i)=\sum^k_{i=1}\lambda_i\alpha_iu_i$
      • z toho plyne $0=0-0=\sum^k_{i=1}\lambda_i\alpha_iu_i-\sum^k_{i=1}\lambda_k\alpha_iu_i=\sum^{k-1}_{i=1}(\lambda_i-\lambda_k)\alpha_iu_i$
        • poslední členy obou součtů jsou stejné, proto se odečtou
      • $\left(\sum^{k-1}_{i=1}(\lambda_i-\lambda_k)\alpha_iu_i=0\right)\land(\forall i:\lambda_i\neq\lambda_k)\land(\exists i:\alpha_i\neq0)$
      • $\implies\left(\sum^{k-1}_{i=1}\beta_iu_i=0\right)\land(\exists i:\beta_i\neq0)$
      • tedy již prvních $k-1$ vektorů je lineárně závislých, což je spor s minimalitou $k$
  • věta o kořenech charakteristického polynomu
    • věta: Číslo $\lambda\in\mathbb K$ je vlastním číslem matice $A\in\mathbb K^{n\times n}\iff\lambda$ je kořenem jeho charakteristického polynomu $p_A(t)$.
    • definice charakteristického polynomu: $p_A(t)=\text{det}(A-tI_n)$
    • důkaz
      • $\lambda$ je vlastní číslo $A$
      • $\iff\exists x\in\mathbb K^n\setminus\lbrace0\rbrace:Ax=\lambda x$
      • $\iff\exists x\in\mathbb K^n\setminus\lbrace0\rbrace: 0=Ax-\lambda x=Ax-\lambda I_nx=(A-\lambda I_n)x$
      • $\iff$ matice $A-\lambda I_n$ je singulární
      • $\iff0=\text{det}(A-\lambda I_n)=p_A(\lambda)$
  • Cayley-Hamiltonova věta
    • věta: Pro matici $A\in\mathbb K^{n\times n}$ a její charakteristický polynom $p_A(t)=(-1)^nt^n+a_{n-1}t^{n-1}+\dots+a_2t^2+a_1t+a_0$ platí, že $p_A(A)=(-1)^nA^n+a_{n-1}A^{n-1}+\dots+a_2A^2+a_1A+a_0I_n=0_n$.
    • důkaz
      • použijeme větu (o adjungované matici), že $M\cdot\text{adj }M=(\text{det }M)\cdot I_n$ pro $M=A-tI_n$
      • složky $\text{adj}(A-tI_n)$ jsou determinanty podmatic, tj. polynomy v $t$ stupně nejvýše $n-1$
      • matici lze tedy rozepsat takto: $\text{adj}(A-tI_n)=t^{n-1}B_{n-1}+\dots+tB_1+B_0$ pro $B_{n-1},\dots,B_0\in\mathbb K^{n\times n}$
      • nyní máme $(A-tI_n)(t^{n-1}B_{n-1}+\dots+tB_1+B_0)$ $=p_A(t)I_n=(-1)^nt^nI_n+a_{n-1}t^{n-1}I_n+\dots+a_2t^2I_n+a_1tI_n+a_0I_n$
      • získáme $n+1$ rovnic (porovnáváme koeficienty u $t^i$ na levé a pravé straně rovnice)
        • pro $t^n$: $-B_{n-1}=(-1)^nI_n$
        • pro $t^i$ ($0\lt i\lt n$): $AB_i-B_{i-1}=a_iI_n$
        • pro $t^0$: $AB_0=a_0I_n$
      • všechny rovnice kromě té poslední vynásobíme zleva $A^i$ (respektive $A^n$) a všechny je sečteme
      • na levé straně dostaneme $-A^nB_{n-1}+A^{n-1}(AB_{n-1}-B_{n-2})+\dots+A(AB_1-B_0)+AB_0=0_n$
        • členy se navzájem poodčítají
      • pravá strana: $(-1)^nA^n+a_{n-1}A^{n-1}+\dots+a_2A^2+a_1A+a_0I_n=p_A(A)$
  • nezbytná a postačující podmínka, kdy je matice diagonalizovatelná
    • věta: Matice $A\in\mathbb K^{n\times n}$ je podobná diagonální matici (tzn. diagonalizovatelná), právě když prostor $\mathbb K^n$ má bázi sestávající z vlastních vektorů $A$.
    • důkaz: $AR=RD$ s diagonální maticí $D$, pokud pro každé $i$ existuje vektor $x$ (i-tý sloupec $R$) takový, že $Ax=\lambda x=d_{ii}x$
    • důležitá „pozorování“
      • vlastní vektory matice $A$ tvoří bázi prostoru $\mathbb K^n\iff$ je jich $n$ a jsou lineárně nezávislé
      • matice $R$ je regulární (z definice podobnosti)
      • vlastní čísla diagonální matice jsou její prvky na diagonále
      • dvě podobné matice mají stejná vlastní čísla, důkaz:
        • $A=R^{-1}BR$
        • $Ax=\lambda x$
        • $R^{-1}BRx=\lambda x$
        • $BRx=\lambda Rx$
        • $By=\lambda y$
    • H. důkaz
      • $\implies$
        • $AR=RD$, porovnáváme j-té sloupce
        • levá strana: $(AR){*j}=AR{*j}$
        • pravá strana: $(RD){*j}=\lambda_j R{*j}$
        • $AR_{*j}=\lambda_j R_{*j}\implies R_{*j}$ je vlastní vektor matice $A$
        • z regularity $R$ vyplývá lineární nezávislost
      • $\impliedby$
        • $R$ sestavíme z vlastních vektorů matice $A$ (dáme je do sloupců)
        • tedy platí $AR_{*j}=\lambda_j R_{*j}$
        • z toho odvodíme $AR=RD$
    • důsledek – matice $R$ je tvořena vlastními vektory matice $A$, matice $D$ ma na diagonále vlastní čísla matice $A$
  • věta o diagonalizaci speciálních komplexních matic
    • věta: Každá hermitovská matice $A$ má všechna vlastní čísla reálná. Navíc existuje unitární matice $R$ taková, že $R^{-1}AR$ je diagonální.
    • pozorování o hermitovských a unitárních maticích
      • hermitovské matice mají reálnou úhlopříčku
      • $A$ je unitární $\iff A^H$ je unitární
      • součin unitárních matic je unitární
      • unitární $A$ splňuje $A^HA=I$, tj. pro sloupce $x_1,\dots,x_n$ platí $x_i^Hx_i=1$ a $x_i^Hx_j=0$ pro $i\neq j$
    • důkaz: indukcí dle $n$ (řádu matice)
      • pro $n=1$ věta platí
      • označme $A_n=A$
      • v tělese $\mathbb C$ má matice $A_n$ vlastní číslo $\lambda$ s vlastním vektorem $x$
      • zvětšíme $x$ faktorem $\frac1{\sqrt{x^Hx}}$, aby platilo $x^Hx=1$
        • normalizace vektoru
      • doplníme $x$ na unitární matici $P_n$
        • doplnění lze provést
      • mějme matici $P_n^HA_nP_n$, ta je hermitovská: $(P^H_nA_nP_n)^H=P^H_nA^H_n(P^H_n)^H=P^H_nA_nP_n$
      • $($první sloupec $P_n$ je $x)\land (A_nx=\lambda x)\implies$ první sloupec $A_nP_n$ je $\lambda x$
      • $P_n$ je unitární $\implies$ první sloupec $P^H_nA_nP_n$ je $P^H_n\lambda x=\lambda P^H_nx=\lambda e_1$
        • protože součin i-tého řádku a sloupce je jedna, jinak nula (a vektor $x$ odpovídá prvnímu řádku matice $P^H_n$)
      • $(P^H_nA_nP_n)_{11}=\lambda$, zbytek prvního řádku a prvního sloupce tvoří nuly
        • nuly v prvním sloupci jsme odvodili
        • z hermitovskosti vyplývá, že $\lambda\in\mathbb R$ (protože je na diagonále) a že jsou nuly i v prvním řádku
      • $(P_n^HA_nP_n)^{11}=A_{n-1}$ hermitovská
      • podle indukčního předpokladu: $R_{n-1}^{-1}A_{n-1}R_{n-1}=D_{n-1}$ pro nějakou unitární $R_{n-1}$ a diagonální $D_{n-1}$
      • položíme $R_n=P_n\cdot\begin{pmatrix}1 & 0^T \ 0 & R_{n-1} \end{pmatrix}$
        • součiny unitárních matic jsou unitární
      • $R^{-1}nA_nR_n=R^H_nA_nR_n=\begin{pmatrix}1 & 0^T \ 0 & R^H{n-1} \end{pmatrix}\cdot P^H_nA_nP_n\cdot \begin{pmatrix}1 & 0^T \ 0 & R_{n-1} \end{pmatrix}=$
      • $=\begin{pmatrix}1 & 0^T \ 0 & R^H_{n-1} \end{pmatrix}\cdot \begin{pmatrix}\lambda & 0^T \ 0 & A_{n-1} \end{pmatrix}\cdot \begin{pmatrix}1 & 0^T \ 0 & R_{n-1} \end{pmatrix}=\begin{pmatrix}\lambda & 0^T \ 0 & D_{n-1} \end{pmatrix}=D_n$
  • Cauchy-Schwarzova nerovnost
    • věta: Skalární součin libovolných dvou vektorů $u$ a $v$ ve vektorovém prostoru nad $\mathbb C$ splňuje $|\langle u|v\rangle|\leq\sqrt{\langle u|u\rangle\langle v|v\rangle}$.
      • tedy $|\langle u|v \rangle|\leq ||u||\cdot ||v||$ (vůči odpovídající normě)
    • důkaz
      • pro $u=0$ nebo $v=0$ dostaneme $0\leq 0$
      • pro libovolné $a\in\mathbb C$ platí:
        • $||u+a v||^2\geq 0$
        • $||u+a v||^2=\langle u+a v|u+a v\rangle$ $=\langle u|u\rangle + a \langle v|u\rangle +\overline{a}\langle u|v\rangle + a\overline{a}\langle v|v\rangle$
      • pro vzájemné odečtení posledních dvou členů zvolíme $$a=-\frac{\langle u|v\rangle}{\langle v|v\rangle}$$
      • dostaneme
        • $0\leq\langle u|u\rangle-\frac{\langle u|v\rangle}{\langle v|v\rangle}\langle v|u\rangle$
        • $\langle u|v\rangle\langle v|u\rangle\leq\langle u|u\rangle\langle v|v\rangle$
          • na $\mathbb C$ platí $a\overline{a}=|a|^2$
        • $|\langle u|v\rangle|^2\leq||u||^2\cdot||v||^2$
        • $|\langle u|v\rangle|\leq||u||\cdot||v||$
  • trojúhelníková nerovnost
    • tvrzení: Každá norma odvozená ze skalárního součinu splňuje trojúhelníkovou nerovnost: $||u+v||\leq||u||+||v||$
    • důkaz
      • $||u+v||=\sqrt{\langle u+v|u+v\rangle}=\sqrt{\langle u|u\rangle+\langle v|u\rangle+\langle u|v\rangle+\langle v|v\rangle}\leq$
      • $\leq\sqrt{||u||^2+2|\langle u|v\rangle|+||v||^2}\leq\sqrt{||u||^2+2||u||\cdot||v||+||v||^2}=$
      • $=||u||+||v||$
      • první nerovnost platí, neboť
        • $(a+bi)+(a-bi)\leq 2|a+bi|$
        • $2a\leq2\sqrt{a^2+b^2}$
        • $a^2\leq a^2+b^2$
      • druhá nerovnost vyplývá z Cauchy-Schwarzovy nerovnosti
  • věta o Fourierových koeficientech
    • nechť $Z=\lbrace v_1,\dots,v_n\rbrace$ je ortonormální báze prostoru $V$
    • tvrzení: pro každé $u\in V$ platí $u=\langle u|v_1\rangle v_1+\dots+\langle u|v_n\rangle v_n$
    • $\langle u|v_i\rangle$ … Fourierovy koeficienty
    • důkaz: (vyplývá z toho, že $\langle v_i|v_j\rangle$ se rovná jedné pro $i=j$, jinak nule) $$u=\sum^n_{i=1} \alpha_iv_i\implies\langle u|v_j\rangle=\left\langle \sum^n_{i=1} \alpha_iv_i\middle|v_j\right\rangle=\sum^n_{i=1}\alpha_i\langle v_i|v_j\rangle=\alpha_j$$
  • Gram-Schmidtova ortonormalizace (a její správnost) – včetně lemmatu, pokud jej potřebujete
    • algoritmus – převede libovolnou bázi $(u_1,\dots,u_n)$ prostoru $V$ se skalárním součinem na ortonormální bázi $(v_1,\dots,v_n)$
      • for $i=1,\dots,n$ do
        • $w_i=u_i-\sum^{i-1}_{j=1}\langle u_i|v_j\rangle v_j$
        • $v_i=\frac1{||w_i||}w_i$
      • end
    • důkaz správnosti
      • $v_i\perp v_j\iff i\neq j$ plyne z $w_i\perp v_j$ pro každé $j\lt i$, což dokazuje následující lemma
        • lemma: Nechť $p_Z$ je ortogonální projekce $W$ na $V$, potom $u-p_Z(u)\perp v_i$ pro každé $v_i\in Z$.
        • důkaz
          • $\langle u-p_Z(u)|v_i\rangle=\left\langle u-\sum^n_{j=1}\langle u|v_j\rangle v_j\middle|v_i\right\rangle=$
          • $=\langle u|v_i\rangle-\sum^n_{j=1}\langle u|v_j\rangle\langle v_j|v_i\rangle=\langle u|v_i\rangle-\langle u|v_i\rangle=0$
            • $\langle v_j|v_i\rangle =0\iff i\neq j$
            • $\langle v_j|v_i\rangle =1\iff i=j$
      • $||v_i||=\left\Vert\frac1{||w_i||}w_i\right\Vert=\frac{||w_i||}{||w_i||}=1$
      • pomocí lemmatu o výměně dokážeme, že po výměně $u_i$ za $w_i$, respektive $v_i$ dané vektory stále generují stejný prostor
        • 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$
  • věta o izometrii a normě
    • věta: Lineární zobrazení mezi prostory $V$ a $W$ je izometrie, právě když zachovává související normu, tj. $||u||=||f(u)||$.
    • definice: lineární zobrazení je izometrie, pokud zachovává skalární součin, tedy $\langle u|w\rangle=\langle f(u)|f(w)\rangle$
    • důkaz
      • $\implies$ vychází z definice normy (norma závisí na skalárním součinu)
      • pro $\impliedby$ porovnáme
        • $||u+aw||^2=||f(u+aw)||^2$
        • levá strana: $||u||^2+a\langle w|u\rangle + \overline{a}\langle u|w\rangle + a\overline{a}||w||^2$
        • pravá strana: $||f(u)||^2+a\langle f(w)|f(u)\rangle + \overline{a}\langle f(u)|f(w)\rangle + a\overline{a}||f(w)||^2$
        • první a poslední členy se zjevně rovnají
        • pro konkrétní $a$ porovnáme obě strany
        • pro $a=1$: $\langle w|u\rangle+\langle u|w\rangle=\langle f(w)|f(u)\rangle+\langle f(u)|f(w)\rangle$
        • pro $a=i$: $\langle w|u\rangle-\langle u|w\rangle=\langle f(w)|f(u)\rangle-\langle f(u)|f(w)\rangle$
        • obě rovnice sečteme a dostaneme $\langle u|w\rangle=\langle f(u)|f(w)\rangle$
  • věta o izometrii a vlastnostech její matice
    • věta
      • Nechť $V$ a $W$ jsou prostory se skalárním součinem konečné dimenze a $X,Y$ jsou jejich ortonormální báze.
      • Lineární zobrazení $f:V\to W$ je bijektivní izometrie, právě když $[f]_{XY}$ je unitární.
    • důkaz
      • lineární bijekce implikuje stejné dimenze a naopak
      • $X$ je ortonormální $\implies\langle u|w\rangle=[w]^H_X[u]_X$, důkaz:
        • $u=\sum^n_{i=1}\langle u|v_i\rangle v_i;\quad w=\sum^n_{j=1}\langle w|v_j\rangle v_j$
        • $\langle u|w\rangle =\left\langle \sum^n_{i=1}\langle u|v_i\rangle v_i\middle|\sum^n_{j=1}\langle w|v_j\rangle v_j\right\rangle=$
        • $=\sum^n_{i=1}\sum^n_{j=1}\langle u|v_i\rangle\overline{\langle w|v_j\rangle}\langle v_i|v_j\rangle=\sum^n_{i=1}\langle u|v_i\rangle\overline{\langle w|v_i\rangle}=[w]^H_Z[u]_Z$
          • ($\langle w|v_k\rangle$ je komplexně sdružené)
      • $Y$ je ortonormální $\implies\langle f(u)|f(w)\rangle=[f(w)]^H_Y[f(u)]Y=[w]^H_X[f]^H{XY}[f]_{XY}[u]_X$
      • maticová rovnost $x^Ty=x^TAy$ obecně platí, pouze když je $A$ jednotková matice
      • $f$ je izometrie pokud $[w]^H_X[u]X=[w]X^H[f]^H{XY}[f]{XY}[u]_X$ platí pro všechna $u$ a $w$
      • to platí právě když $[f]^H_{XY}[f]{XY}=I$, tedy je-li $[f]{XY}$ unitární
  • věta o ortogonálním doplňku
    • věta: Pro konečně generovaný prostor $W$ se skalárním součinem a podprostor $V$ platí $(V^\perp)^\perp=V$ a $\text{dim }V+\text{dim }V^\perp=\text{dim }W$.
    • důkaz
      • zvolíme nějakou ortonormální bázi $X$ prostoru $V$ a doplníme ji na ortonormální bázi $Z$ prostoru $W$
      • označme $Y=Z\setminus X,,X=(x_1,\dots,x_k),,Y=(y_1,\dots,y_l)$
      • každé $u\in\mathcal L(X)=V$ je kolmé ke každému $v\in\mathcal L(Y)$
        • $\langle u|v\rangle=\left\langle\sum_{i=1}^ka_ix_i\middle|\sum^l_{j=1}b_jy_j\right\rangle=\sum^k_{i=1}\sum^l_{j=1}a_i\bar{b_j}\langle x_i|y_j\rangle=0$
        • protože $Z$ je ortonormální báze
        • proto $\mathcal L(Y)\subseteq V^\perp$
      • vezměme $w\in V^\perp$ a uvažme $[w]_Z$
      • $Z$ je ortonormální $\implies ([w]_Z)_i=\langle w|z_i\rangle$
      • $w\in V^\perp\implies\langle w|x_i\rangle =0\implies w\in\mathcal L(Y)\implies V^\perp\subseteq\mathcal L(Y)$
      • tedy $V^\perp=\mathcal L(Y)$
      • $\text{dim }V+\text{dim }V^\perp=|X|+|Y|=|Z|=\text{dim }W$
      • $(V^\perp)^\perp=\mathcal L(Z\setminus Y)=\mathcal L(X)=V$
  • věta o skalárním součinu dvou vektorů a Gramově matici
    • věta
      • Nechť $V$ je prostor se skalárním součinem a bází $X=(v_1,\dots,v_n)$.
      • Potom tzv. Gramova matice $A$ definované $a_{ij}=\langle v_i|v_j\rangle$ splňuje $\forall u,w\in V:\langle u|w\rangle =[w]^H_XA^T[u]_X$.
    • pozorování: když je $X$ ortonormální báze, pak $A=I_n$
    • důkaz
      • označme $[u]_X=(b_1,\dots,b_n)^T,,[w]_X=(c_1,\dots,c_n)^T$
      • $\langle u|v\rangle=\left\langle\sum_{i=1}^nb_iv_i\middle|\sum^n_{j=1}c_jv_j\right\rangle=$
      • $=\sum^n_{i=1}\sum^n_{j=1}b_i\bar{c_j}\langle v_i|v_j\rangle=[w]^H_XA^T[u]_X$
  • věta o třech ekvivalentních podmínkách pro pozitivně definitní matice
    • věta: Pro hermitovskou matici $A$ jsou následující podmínky ekvivalentní:
      1. $A$ je pozitivně definitní,
      2. $A$ má všechna vlastní čísla kladná,
      3. existuje regulární matice $U$ taková, že $A=U^HU$.
    • důkaz
      • $1\implies 2$
        • protože $A$ je hermitovská, má vlastní čísla reálná
        • mějme netriviální vlastní vektor $x$ odpovídající vl. číslu $\lambda$
        • potom $0\lt x^HAx=\lambda x^Hx=\lambda\langle x|x\rangle$
          • $\langle x|x\rangle\gt 0\implies\lambda\gt 0$
      • $2\implies 3$
        • protože $A$ je hermitovská, existují unitární $R$ a diagonální $D$ takové, že $A=R^HDR$
        • vezměme diagonální $\tilde D:\tilde d_{ii}=\sqrt{d_{ii}}$
        • vezměme $U=\tilde DR$
        • $U^HU=(\tilde DR)^H\tilde DR=R^H\tilde D^H\tilde DR=R^HDR=A$
        • $U$ je regulární, protože unitární i diagonální matice jsou regulární
      • $3\implies 1$
        • pro regulární $U$ platí $x\in\mathbb C^n\setminus\lbrace0\rbrace\implies Ux\neq0$
        • $x^HAx=x^HU^HUx=(Ux)^HUx=\langle Ux|Ux\rangle \gt 0$
  • věta o rekurentní podmínce pro pozitivně definitní matice
    • věta: Bloková matice $A=\begin{pmatrix}\alpha & a^H \ a & \tilde A \end{pmatrix}$ je pozitivně definitní $\iff \alpha\gt 0\land\tilde A-\frac1\alpha aa^H$ je pozitivně definitní.
    • pozorování: Gaussova eliminace prvního sloupce pomocí prvního řádku dává v hermitovské matici $\begin{pmatrix}\alpha & a^H \ a & \tilde A \end{pmatrix}\sim\sim\begin{pmatrix}\alpha & a^H \ 0 & \tilde A-\frac1\alpha aa^H \end{pmatrix}$
    • pozorování: pokud je $A$ pozitivně definitní a $R$ je regulární, pak $R^HAR$ je také pozitivně definitní
      • důkaz: $x^HR^HARx=y^HAy\gt0$ pro $y=Rx\neq 0$
    • pozorování: hermitovská bloková matice $C=\begin{pmatrix}A & 0 \ 0 & B \end{pmatrix}$ je pozitivně definitní, právě když jsou $A$ i $B$ pozitivně definitní, důkaz:
      • mějme $z=(x_1,\dots,x_n,y_1,\dots,y_m)^T$
      • $\impliedby:\quad z^HCz=x^HAx+y^HBy$
        • když jsou oba sčítance kladné, tak je kladný i součet
      • $\implies:\quad$ doplníme $x$ nulami na $z$, dostaneme $x^HAx=z^HCz\gt 0$
        • podobně pro $y$ a $B$
    • důkaz
      • Gaussova eliminace prvního sloupce $A$ odpovídá součinu $$\begin{pmatrix}1 & 0^H \ -\frac1\alpha a & I \end{pmatrix}\cdot\begin{pmatrix}\alpha & a^H \ a & \tilde A \end{pmatrix}=\begin{pmatrix}\alpha & a^H \ 0 & \tilde A-\frac1\alpha aa^H \end{pmatrix}$$
        • matici elementárních úprav označme $R^H$ (je regulární)
      • $R^HAR=\begin{pmatrix}\alpha & 0^H \ 0 & \tilde A-\frac1\alpha aa^H \end{pmatrix}$
        • $A$ je pozitivně definitní, právě když je výsledná bloková matice pozitivně definitní (což nastává, když má oba nenulové bloky pozitivně definitní)
  • věta o pozitivně definitních maticích a determinantech
    • věta (Sylvesterova podmínka, hlavní vedoucí podmatice): Hermitovská matice $A$ řádu $n$ je pozitivně definitní, právě když matice $A_1,\dots,A_n$ mají kladné determinanty, kde $A_i$ sestává z prvních $i$ řádku a sloupců $A$.
    • důkaz
      • použijeme Gaussovu eliminaci $A\sim\sim A'$ pro test, zda je $A$ pozitivně definitní
      • $\alpha_1,\dots,\alpha_n$ jsou prvky na diagonále výsledné horní trojúhelníkové matice $A'$
      • eliminaci jsme prováděli přičítáním násobku řádku shora dolů, tedy $\text{det }A_i=\text{det }A'i=\prod{j\leq i}\alpha_j=\text{det }A_{i-1}\alpha_i$
      • $A$ je pozitivně definitní $\iff\alpha_1,\dots,\alpha_n\gt0\iff\text{det }A_1,\dots,\text{det }A_n\gt0$
  • algoritmus pro výpočet Choleského rozkladu (a jeho správnost)
    • máme $A$, hledáme $U$ takové, že $U^HU=A$
    • algoritmus
      • input: hermitovská $A$
      • output: $U$, pokud je $A$ pozitivně definitní
      • for $i=1,\dots,n$ do
        • $u_{ii}=\sqrt{a_{ii}-\sum^{i-1}{k=1}\bar u{ki}u_{ki}}$
        • if $u_{ii}\notin\mathbb R^+$ then return $A$ není pozitivně definitní
        • for $j=i+1,\dots,n$ do
          • $u_{ij}=\frac1{u_{ii}}\left(a_{ij}-\sum^{i-1}{k=1}\bar u{ki}u_{kj}\right)$
        • end
      • end
    • správnost
      • předpokládejme, že algoritmus selže během i-té iterace, tj. $\alpha-u^Hu\leq 0$
        • $\alpha$ odpovídá $a_{ii}$
      • $u$ je vektor o $i-1$ složkách v horní trojúhelníkové matici
      • máme částečný rozklad hlavní vedoucí podmatice $A'=V^HV$ a rovněž sloupec nad $\alpha$ (a řádku vlevo) $a=V^Hu$
      • trikově zvolíme $x=-V^{-1}u$
      • $x$ má $i-1$ složek, tedy jej doplníme o jednu jedničku (na pozici $i$) a jinak samé nuly na vektor $y$
      • $y^HAy=x^HA'x+x^Ha+a^Hx+\alpha=$
        • tento rozklad vychází z toho, jak vypadá vektor $y$
          • první člen součtu násobí dvakrát vektorem $x$
          • druhý a třetí člen násobí jednou $x$ a jednou jedničkou (na i-té pozici)
          • čtvrtý člen násobí dvakrát jedničkou
          • ostatní členy násobí nulou (proto v součtu chybí)
      • $=(-V^{-1}u)^H(V^HV)(-V^{-1}u)+$
      • $+(-V^{-1}u)^H(V^Hu)+(V^Hu)^H(-V^{-1}u)+\alpha=$
      • $=u^H(V^H)^{-1}V^HVV^{-1}u-u^H(V^H)^{-1}V^Hu-u^HVV^{-1}u+\alpha=$
      • $=u^Hu-u^Hu-u^Hu+\alpha=\alpha-u^Hu\leq 0$
      • proto $A$ není pozitivně definitní
  • věta o diagonalizovatelnosti matic forem
    • věta: Pokud je $g$ kvadratická forma na vektorovém prostoru $V$ konečné dimenze $n$ nad tělesem $\mathbb K$ jiné charakteristiky než 2, pak má forma $g$ diagonální matici $B$ vzhledem k vhodné bázi $X$. (To platí i pro symetrické bilineární formy.)
    • definice: Polární báze dává diagonální matici kvadratické formy.
    • přeformulováno z hlediska matic:
      • věta: Pro jakoukoliv symetrickou matici $A\in\mathbb K^{n\times n}$ s $\text{char}(\mathbb K)\neq 2$ existuje regulární matice $R$ taková, že $R^TAR$ je diagonální.
    • důkaz
      • indukcí dle $n$ (řádu matice)
      • označme $A=A_n=\begin{pmatrix}\alpha & a^T \ a & \tilde A \end{pmatrix}$
      • když $\alpha\neq 0$, volíme $P^T_n=\begin{pmatrix}1 & 0^T \ -\frac1\alpha a & I_{n-1} \end{pmatrix}$
      • pak $P^T_nA_nP_n=\begin{pmatrix}\alpha & 0^H \ 0 & \tilde A-\frac1\alpha aa^T \end{pmatrix}$
      • označíme $A_{n-1}=\tilde A-\frac1\alpha aa^T$, tato matice je symetrická
      • dle indukčního předpokladu existuje $R_{n-1}$ pro $A_{n-1}$
      • zvolíme $R_n=P_n\cdot \begin{pmatrix}1 & 0^T \ 0 & R_{n-1}\end{pmatrix}$
      • pak $R^T_nA_nR_n=\begin{pmatrix}1 & 0^T \ 0 & R^T_{n-1}\end{pmatrix}\cdot P^T_nA_nP_n \cdot \begin{pmatrix}1 & 0^T \ 0 & R_{n-1}\end{pmatrix}=$
      • $=\begin{pmatrix}\alpha & 0^T \ 0 & R^T_{n-1}A_{n-1}R_{n-1}\end{pmatrix}$, což je dle IP diagonální matice
      • pokud $\alpha=0$, ale první sloupec není nulový ($a_{i1}$ je nenulové pro nějaké $i$), tak použijeme elementární matici $E$ pro přičtení i-tého sloupce k prvnímu → vezmeme $A'=E^TAE$ místo $A$
      • pokud je celý první řádek (i sloupec) nulový, tak $R_n=\begin{pmatrix}1 & 0^T \ 0 & R_{n-1}\end{pmatrix}$
  • Sylvesterův zákon setrvačnosti – o diagonalizaci kvadratických forem
    • věta
      • Každá kvadratická forma na konečně generovaném reálném vektorovém prostoru má vzhledem k vhodné bázi diagonální matici pouze s 1, –1 a 0.
      • Všechny takové diagonální matice odpovídající téže formě mají stejný počet 1 a stejný počet –1.
    • důkaz existence
      • nechť $B$ je maticí formy vzhledem k bázi $Y$
      • pro reálnou symetrickou matici existuje spektrální rozklad (lze ji diagonalizovat), tedy $B=R^TDR$ pro regulární $R$
      • rozložíme $D=S^TD'S$
        • všechny matice jsou diagonální
        • $d'{ii}=\text{sgn}(d{ii})$
        • $s_{ii}=\sqrt{|d_{ii}|}$ pro nenulové $d_{ii}$
          • pro $d_{ii}=0:s_{ii}=1$, aby $S$ byla regulární
      • $SR$ je regulární, $B=(SR)^TD'SR$
      • zvolíme bázi $X$ tak, že $[id]{X,Y}=SR,,[id]{Y,X}=(SR)^{-1}$
      • $[id]^T_{Y,X}B[id]_{Y,X}=D'$ je hledaná matice formy
    • důkaz jednoznačnosti signatury (počtu jedniček, minus jedniček, nul)
      • mějme báze $X=(u_1,\dots,u_n),,Y=(v_1,\dots,v_n)$
      • mějme dvě různé „sylvesterovské“ matice $B,B'$ formy $g$ uspořádané tak, že nejdříve jsou jedničky, pak minus jedničky a nakonec nuly
      • součin s regulární maticí přechodu nemění hodnost, tedy i počet nul musí být v obou maticích stejný
      • nechť $r$ je počet jedniček v $B$, $s$ je počet jedniček v $B'$
      • BÚNO $r\gt s$
      • uvažme podprostory $\mathcal L(u_1,\dots,u_r)$ a $\mathcal L(v_{s+1},\dots,v_n)$
      • z $r\gt s$ vyplývá, že součet jejich dimenzí přesahuje $n$, tedy mají netriviální průnik
      • zvolme nenulový vektor $w$ z tohoto průniku
        • $[w]_X=(x_1,\dots,x_r,0,\dots,0)$
        • $[w]Y=(0,\dots,0,y{s+1},\dots,y_n)$
        • alespoň jedno $x_i$ a alespoň jedno $y_i$ je nenulové
      • $g(w)=[w]^T_XB[w]_X=x_1^2+\dots+x^2_r\gt 0$
        • protože alespoň jedno $x_i$ je nenulové
      • $g(w)=[w]^T_YB[w]_Y=-y_1^2-\dots-y^2_r\lt 0$
        • protože alespoň jedno $y_i$ je nenulové
      • musí však platit $g(w)=g(w)$, což neplatí → to je spor
      • tedy $r=s$
  • věta o počtu přímek svírajících stejný úhel
    • věta: V $\mathbb R^d$ může nevýše $d+1\choose 2$ přímek svírat stejný úhel $\varphi$.
    • důkaz
      • předpokládejme, že existuje $n$ takových přímek
      • zvolíme vektory jednotkové délky $v_1,\dots,v_n$, z každé přímky po jednom
      • platí $\langle v_i|v_j\rangle=\cos \varphi$ pro $i\neq j$ (jinak 1, protože jsou jednotkové délky)
      • dokážeme, že matice $v_1v_1^T,\dots,v_nv_n^T\in\mathbb R^{d\times d}$ jsou lineárně nezávislé
        • předpokládejme, že $\sum_{i=1}^n\alpha_iv_iv_i^T=0$ (lineární kombinace matic se rovná nulové matici)
        • pak musí platit pro každé $j\in\lbrace1,\dots,n\rbrace:0=v_j^T0v_j=v^T_j\left(\sum^n_{i=1}\alpha_iv_iv_i^T\right)v_j=$
        • $=\sum^n_{i=1}\alpha_iv_j^Tv_iv_i^Tv_j=\sum^n_{i=1}\alpha_i\langle v_i|v_j\rangle^2=\alpha_j+\cos^2\varphi\sum_{i\neq j}\alpha_i$
        • to lze přepsat na soustavu rovnic $Ax=0$
          • $A$ má na diagonále jedničky, všude jinde $\cos^2\varphi$
          • $x=(\alpha_1,\dots,\alpha_n)^T$
        • matice této soustavy je regulární, proto je jediným řešením $\alpha_1=\dots=\alpha_n=0$, z toho plyne lineární nezávislost matic
      • dimenze prostoru symetrických matic z $\mathbb R^{d\times d}$ je $d+1\choose 2$
        • proto $n\leq {d+1\choose 2}$

Přehledy (14)

  • výpočet determinantů
    • permutační grupa, znaménko permutace
    • vzorec pro výpočet determinantu
    • Sarrusovo pravidlo pro matice 3×3
    • determinant matice s nulovým řádkem
    • determinant trojúhelníkové matice
    • vliv elementárních úprav a transpozice na determinant
    • věta o linearitě determinantu
    • determinant singulární matice je roven nule
    • věta o determinantu součinu dvou matic
    • věta o Laplaceově rozvoji determinantu
    • adjungovaná matice
    • věta o adjungované matici
    • Cramerovo pravidlo (řešení systémů s determinanty)
  • determinanty a jejich geometrický význam
    • viz výpočet determinantů
    • objem rovnoběžnostěnu určeného $k$ vektory je roven absolutní hodnotě determinantu matice, jejíž sloupce tyto vektory tvoří
    • po provedení lineárního zobrazení se objemy těles změní úměrně absolutní hodnotě determinantu matice zobrazení
  • počet koster grafu
    • kostra je podgraf souvislého grafu, který je stromem a obsahuje všechny vrcholy
    • Laplaceova matice
    • věta o počtu koster grafu
    • úplný graf $K_n$ má $n^{n-2}$ koster
  • polynomy
    • polynom nad tělesem
    • operace s polynomy – sčítání, odčítání, skalární násobek, součin, dělení se zbytkem
    • malá Fermatova věta
    • kořen polynomu a jeho násobnost
    • algebraicky uzavřené těleso
    • Vandermondova matice
    • věta o Vandermondově matici
    • Lagrangeova interpolace
  • vlastní čísla a vlastní vektory
    • vlastní číslo a vlastní vektor lineárního zobrazení
    • vlastní číslo a vlastní vektor matice
    • spektrum (množina vlastních čísel matice)
    • algebraická násobnost vlastního čísla
    • geometrická násobnost vlastního čísla
    • věta o podprostoru vlastních vektorů
    • věta o lineární nezávislosti vlastních vektorů
    • vlastní vektory a vlastní čísla diagonální matice
    • matice řádu $n$ může mít nejvýše $n$ různých vlastních čísel
  • charakteristický polynom a jeho koeficienty
    • charakteristický polynom matice
    • vlastní čísla jako kořeny charakteristického polynomu
    • algebraická násobnost vlastního čísla
    • věta o kořenech charakteristického polynomu
    • spektrální rozklad pomocí charakteristického polynomu
    • Geršgorinovy kruhy
    • Cayley-Hamiltonova věta
  • podobné matice a diagonalizace
    • podobné matice
      • idea: matice stejného zobrazení vzhledem k různým bázím jsou podobné
      • mají stejná vlastní čísla
      • rovnají se jejich charakteristické polynomy
    • diagonalizovatelná matice
    • nezbytná a postačující podmínka, kdy je matice diagonalizovatelná
    • Jordanova normální forma (každá čtvercová komplexní matice je podobná matici v Jordanově normální formě)
    • Jordanův blok
    • Jordanův normální tvar matice
    • zobecněný vlastní vektor
      • pro rozklad $AR=RJ$ se zobecněné vlstní vektory objevují ve sloupcích $R$ společně s vlastními vektory
  • speciální komplexní matice
    • transpozice, hermitovská transpozice
    • symetrická matice, hermitovská matice
    • ortogonální matice, unitární matice
    • věta o diagonalizaci speciálních komplexních matic
  • skalární součin a související norma
    • skalární součin pro vektorové prostory nad komplexními čísly
      • kdy je reálný
    • norma spojená se skalárním součinem (odvozená ze součinu, indukovaná součinem)
      • geometrická interpretace
    • kolmé vektory
    • ortonormální báze
    • Fourierovy koeficienty
    • kolmá projekce
    • izometrie
    • ortogonální doplněk
    • Gramova matice
    • Cauchy-Schwarzova nerovnost
    • trojúhelníková nerovnost
    • věta o Fourierových koeficientech
    • metoda nejmenších čtverců
    • Gram-Schmidtova ortonormalizace
    • věta o izometrii a normě
    • věta o izometrii a vlastnostech její matice
    • věta o ortogonálním doplňku
    • věta o skalárním součinu dvou vektorů a Gramově matici
  • ortogonalita a kolmá projekce
  • ortonormální báze
  • ortogonální doplněk
  • pozitivně definitní matice
    • definice pozitivně definitní matice
    • Choleského rozklad
    • věta o třech ekvivalentních podmínkách pro pozitivně definitní matice
    • věta o rekurentní podmínce pro pozitivně definitní matice
    • věta o pozitivně definitních maticích a determinantech (Sylvesterova podmínka)
    • výpočet Choleského rozkladu
  • bilineární a kvadratické formy a jejich matice
    • bilineární forma
    • kvadratická forma
    • matice bilineární formy vzhledem k bázi
    • analytické vyjádření formy
    • signatura formy
    • věta o diagonalizovatelnosti matic forem
    • polární báze
    • Sylvesterův zákon setrvačnosti – o diagonalizaci kvadratických forem