# 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