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}$