Title: Matfyz / Lineární algebra 1 / Důkazové

Q: Uveďte a dokažte vztah mezi elementárními řádkovými operacemi a soustavami rovnic.
A: Nechť \(Ax=b\) a \(A'x=b'\) jsou dvě soustavy splňující \((A|b)\sim\sim(A'|b')\). Pak obě soustavy mají totožné množiny řešení.
Stačí dokázat, že množina řešení je zachována, pokud je provedena jediná úprava prvního nebo druhého typu. Cílem je ukázat \(\{x\in\mathbb{R}^n:Ax=b\}=\{x\in\mathbb{R}^n:A'x=b'\}\). Rovnost množin plyne ze dvou inkluzí \(\subseteq\) a \(\supseteq\), které přepíšeme do implikací a: \(Ax=b\Rightarrow A'x=b\), a za b, \(A'x='b\Rightarrow Ax=b\).
\(Ax=b\Rightarrow A'x=b'\) pro vynásobení \(i\)-tého řádku \(t\neq 0\):
Protože se změní pouze \(i\)-tý řádek/rovnice, každé řešení \(Ax=b\) vyhovuje nezměněným rovnicím \(A'x=b'\). Zbývá ověřit \(i\)-tou rovnici soustavy \(A'x=b'\).
Přechod z levé strany na pravou: \({\color{lime}a'_{i1}}x_1+\ldots+{a'_{in}}\color{lime}x_n={\color{lime}ta_{i1}}x_1+\ldots+{\color{lime}ta_{in}}x_n=t({\color{red}a_{i1}x_1+\ldots+a_{in}x_n}){\color{red}=}{\color{lime}t}{\color{red}b_i}{\color{lime}=b'_i}\) Použito: \(\color{lime}a'_{il}=ta_{il}\) (definice), \(tc+td=t(c+d)\) (vytknutí), \(\color{red}a_{i1}x_1+\ldots+a_{in}x_n=b_i\) (předpoklad), \(\color{lime}tb_i=b'_i\) (definice). Zelená barva označuje vztah mezi \((A|b)\) a \((A'|b')\) neboli elementární úpravu; červená pak předpoklad \(Ax=b\).
Shrnutí případů jedné elementární úpravy prvního nebo druhého druhého typu a \(i\)-té rovnice:
1. \(\begin{multline*} Ax=b\Rightarrow A'x=b': a'_{i1}x_1+\ldots+a'_{in}x_n\\ \mathbin{\color{lime}=}ta_{i1}x_1+\ldots+ta_{in}x_n=t(a_{i1}x_1+\ldots+a_{in}x_n)\mathbin{\color{red}=}tb_i\mathbin{\color{lime}=}b'_i \end{multline*}\)
2. \(\begin{multline*} A'x=b'\Rightarrow Ax=b: a_{i1}x_1+\ldots+a_{in}x_n\\ =\tfrac{1}{t}(ta_{i1}x_1+\ldots+ta_{in}x_n)\mathbin{\color{lime}=}\tfrac{1}{t}(a'_{i1}x_1+\ldots+a'_{in}x_n)\mathbin{\color{red}=}\tfrac{1}{t}b'_i\mathbin{\color{lime}=}\tfrac{1}{t}tb_i=b_i \end{multline*}\)
3. \(\begin{multline*} Ax=b\Rightarrow A'x=b': a'_{i1}x_1+\ldots+a'_{in}x_n\\ \mathbin{\color{lime}=}(a_{i1}+a_{j1})x_1+\ldots+(a_{in}+a_{jn})x_n\\ =(a_{i1}x_1+\ldots+a_{in}x_n)+(a_{j1}x_1+\ldots+a_{jn}x_n)\mathbin{\color{red}=}b_i+b_j\mathbin{\color{lime}=}b'_i \end{multline*}\)
4. \(\begin{multline*} A'x=b'\Rightarrow Ax=b: a_{i1}x_1+\ldots+a_{in}x_n\\ =a_{i1}x_1+\ldots+a_{in}x_n+b_j-b_j\\ \mathbin{\color{red}=}(a_{i1}x_1+\ldots+a_{in}x_n)+(a_{j1}x_1+\ldots+a_{jn}x_n) - b_j\\ =(a_{i1} + a_{j1})x_1 + \ldots + (a_{in}+a_{jn})x_n-b_j\\ \mathbin{\color{lime}=}(a'_{i1}x_1+\ldots+a'_{in}x_n)-b_j\mathbin{\color{red}=}b'_i-b_j\mathbin{\color{lime}=}b_i+b_j-b_j=b_i \end{multline*}\)
Barva rovnítka \(=\) unamená elementární úpravu \((A|b)\) na \((A'|b')\), nebo předpoklad daného případu nebo algebraickou úpravu členů.

Q: Vyslovte a dokažte větu o jednoznačnosti volných a bazických proměnných.
A: Pro \(A'x=b'\) s \((A'|b')\) v REF a bez pivotů v \(b'\) lze jakoukoli volbu volných proměnných jednoznačně rozšířit na řešení.
Důkaz indukcí podle \(i=r,r-1,\ldots,1\). V \(i\)-té rovnici: \(0x_1+\ldots+0x_{j(i)-1}+a'_{i,j(i)}x_{j(i)}+a'_{i,j(i)+1}x_{j(i)+1}+\ldots+a'_{in}x_n=b'_i\) hodnoty všech následujících bázických proměnných \(x_{j(i+1)},\ldots,x_{j(r)}\) jsou známy z indukčního předpokladu (i hodnoty všech volných proměnných), proto je hodnota \(x_{j(i)}\) dána jednoznačně výrazem:\[x_{j(i)}=\tfrac{1}{a'_{i,j(i)}}(b'_i-a'_{i,j(i)+1}x_{j(i)+1}-\ldots-a'_{in}x_n)\]

Q: Vyslovte a dokažte Frobeniovu větu o existenci řešení soustavy.
A: Soustava \(Ax=b\) má řešení právě tehdy, když se hodnost matice \(A\) rovná hodnosti rozšířené matice \((A|b)\).
Řešení existuje \(\Leftrightarrow\) \(b'\) nemá žádný pivot \(\Leftrightarrow\) pivoty \(A'\) se shodují s pivoty \((A'|b')\) \(\Leftrightarrow\) \(\operatorname{rank}(A)=\operatorname{rank}(A|b)\)
... protože převod \(A\sim\sim A'\) lze provést stejnými elementárními úpravami jako \((A|b)\sim\sim(A'|b')\). (Stačí "zapomenout" poslední sloupec.)

Q: Vyslovte a dokažte větu o vztahu mezi řešeními \(Ax=b\) a \(Ax=0\).
A: Jsou-li \(x\) a \(y\) dvě řešení soustavy \(Ax=b\), potom \(\overline{x}=x-y\) je řešením homogenní soustavy \(A\overline{x}=0\).
\(A\overline{x}=A(x-y)\overset{\color{lime}*}{=}Ax-Ay=b-b=0\)
\({\color{lime}*}:a_{i1}(x_1-y_1)+\ldots+a_{in}(x_n-y_n)=(a_{i1}+\ldots+a_{in}x_n)-(x_{i1}y_1+\ldots+a_{in}y_n)\)
Pokud \(y\) je řešením \(Ax=b\) a \(\overline{x}\) je řešením \(A\overline{x}=0\), pak \(x=\overline{x}+y\) je řešením \(Ax=b\).
Důkaz analogicky: \(Ax=A(\overline{x}+y)=A\overline{x}+Ay=0+b=b\)
***

Q: Vyslovte a dokažte větu o znaménku složené permutace.
A: Pro libovolné \(p,q\in S_n:\operatorname{sgn}(q\circ p)=\operatorname{sgn}(p)\operatorname{sgn}(q)\).
počet inverzí \((q\circ p)\) = počet inverzí \(p\) \(+\) počet inverzí \(q-2|\{(i,j):i<j\land p(i)>p(j)\land q(p(i))<q(p(j))\}|\)

Q: Uveďte a dokažte větu charakterizující, kdy \(\mathbb{Z}_n\) je těleso.
A: \(\mathbb{Z}_p\) je těleso, právě když je \(p\) prvočíslo.
\(\Rightarrow\) Pokud by \(p\) bylo složené \(p=ab\), pak \(ab\equiv0\ (\operatorname{mod}p)\), což je spor s následujícím pozorováním:
Pokud \(ab=0\), pak \(a=0\) nebo \(b=0\).
Důkaz sporem, pokud by \(ab=0\) pro \(a,b\neq0\), pak \(\exists a^{-1},b^{-1}\). Pak \(1=aa^{-1}bb^{-1}=aba^{-1}b^{-1}=0a^{-1}b^{-1}=0\), což je spor.
\(\Leftarrow\) Většina axiomů plyne z vlastností \(+\) a \(\cdot\) na \(\mathbb{Z}\), kromě existence inverzních prvků \(a^{-1}\), protože \(\mathbb{Z}\) není uzavřená na dělení. Cíl: \(\forall a\in\{1,\ldots,p-1\}\exists a^{-1}\in\{1,\ldots,p-1\}:aa^{-1}\equiv1\mod p\).
Nechť \(f_a:\{1,\dots,p-1\}\to\{1,\dots,p-1\}\) taková, že \(f_a(x)=(ax)\mod p\). Hledané \(a^{-1}\) splňuje \(f_a(a^{-1})=1\), čili stačí ukázat, že 1 je v oboru hodnot \(f_a\). Dokážeme dokonce, že \(f_a\) je surjektivní (neboli "na").
Protože \(f_a\) zobrazuje konečnou množinu na sebe samu, pak platí, že je surjektivní, právě když je prosté.
Pokud by pro spor \(f_a\) nebylo prosté, pak \(\exists b,c\) bez újmy na obecnosti \(b>c\) takové, že \(f_a(b)=f_a(c)\Rightarrow0=f_a(b)-f_a(c)\equiv ab-ac=a(b-c)\mod p\), což je spor s tím, že \(p\) je prvočíslo, neboť \(a,b-c\in\{1,\ldots,p-1\}\).

Q: Vyslovte a dokažte malou Fermatovu větu.
A: Pro prvočíslo \(p\) a každé \(a\in\{1,\ldots,p-1\}:a^{p-1}\equiv 1\mod p\).
Zobrazení \(f_a:x\to ax\) je v \(\mathbb{Z}_p\) bijekcí na \(\{1,\ldots,p-1\}\):
Protože  \(f_a\) zobrazuje konečnou množinu na sebe samu, pak platí, že je surjektivní, právě když je prosté.
Pokud by pro spor  \(f_a\) nebylo prosté, pak  \(\exists b,c\) bez újmy na obecnosti  \(b>c\) takové, že  \(f_a(b)=f_a(c)\Rightarrow0=f_a(b)-f_a(c)\equiv ab-ac=a(b-c)\mod p\) , což je spor s tím, že  \(p\) je prvočíslo, neboť \(a,b-c\in\{1,\ldots,p-1\}\) .
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}\).

Q: Vyslovte a dokažte větu o průniku vektorových prostorů.
A: Nechť \((U_i,i\in I)\) je libovolný systém podprostorů prostoru \(V\). Průnik tohoto systému \(\bigcap_{i\in I}U_i\) je také podprostorem \(V\).
Nechť \(W=\bigcap_{i\in I}U_i\). Ukážeme, že \(W\) je uzavřen na \(+\) i \(\cdot\).
\[\forall u,b\in W:u,v\in W\Rightarrow\forall i\in I:u,v\in U_i\Rightarrow\forall i \in I: u+v\in U_i\Rightarrow u+v\in W\]\[\forall t\in T,v\in W: v\in W\Rightarrow\forall i\in I: v\in U_i\Rightarrow\forall i\in I:tv\in U_i\Rightarrow tv\in W\]

Q: Vyslovte a dokažte větu o ekvivalentních definicích lineárního obalu.
A: Nechť \(V\) je vektorový prostor nad \(T\) a \(M\) je podmnožina \(V\). Pak \(\operatorname{span}(M)\) je množina všech lineárních kombinací vektorů z \(M\).
Označme \(W_1=\bigcap\{U>M\subseteq U, U\text{ je podprostor }V\}=\operatorname{span}(M)\) a \(W_2=\left\{\sum_{i=1}^ka_iv_i:k\in\mathbb{N},a_i\in T,v_i\in M\right\}\). Cíl: \(W_1=W_2\).
\(W_2\) je podprostor, protože je uzavřen na skalární násobky\[u\in W_2\Rightarrow u=\sum_{i=1}^ka_iv_i\Rightarrow tu=t\sum_{i=1}^ka_iv_i=\sum_{i=1}^k(ta_i)v_i\Rightarrow tu\in W_2\]a analogicky také na součty \(u,w\in W_2\Rightarrow\ldots\Rightarrow u+w\in W_2\)
Protože \(M\subseteq W_2\) máme \(W_2\) mezi protínajícími se podprostory \(U\). Odtud \(W_1\subseteq W_2\).
Každý \(U\) obsahuje \(M\) a je uzavřen na sčítání a skalární násobky. Tudíž každý \(U\) obsahuje všechny lineární kombinace vektorů \(M\). Proto \(\forall U:W_2\subseteq U\Rightarrow W_2\subseteq W_1\).

Q: Vyslovte a dokažte tvrzení o mohutnostech lineárně nezávislé množiny a generující množiny.
A: Jestliže \(C\) je konečná generující množina prostoru \(V\) a \(B\) je lineárně nezávislá ve \(V\), potom \(|B|\leq|C|\).
Předpokládejme, že \(C=\{c_1,\ldots,c_n\}\) a pro spor, že z \(B\) lze vybrat různá \(b_1,\ldots,b_{n+1}\). Každé \(b_i\) vyjádříme jako \(b_i=\sum_{j=1}^na_{ij}c_j\). Odpovídající matice \(A\) má \(n+1\) řádků a \(n\) sloupců, proto je některý řádek lineární kombinací ostatních. Tato kombinace také potvrzuje lineární závislost \(b_1,\ldots,b_{n+1}\).
Formálně:\[\exists d=(d_1,\ldots,d_{n+1})^\top\in T^{n+1}\setminus0:d^\top A=0^\top\Rightarrow\sum_{i=1}^{n+1}d_ib_i=\sum_{i+1}^{n+1}d_i\sum_{j=1}^na_{ij}c_j=\sum_{j=1}^n\left(\sum_{i=1}^{n+1}d_ia_{ij}\right)c_j=\sum_{j=1}^n0c_j=0\]

Q: Uveďte a dokažte Steinitzovu větu o výměně. (včetně lemmatu a jeho důkazu, pokud jej potřebujete).
A: Lemma o výměně:
Bu'd \(y_1,\ldots,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\neq0\), je \(y_1,\ldots,y_{k-1},x,y_{k+1},\ldots,y_n\) systém generátorů prostoru \(V\).
Ze vztahu \(x=\sum_{i=1}^n\alpha_iy_i\) vyjádříme \(y_k\):\[y_k=\frac{1}{\alpha_k}\left(x-\sum_{i\neq k}\alpha_iy_i\right)\]Chceme dokázat, že vektory \(y_1,\ldots,y_{k-1},x,y_{k+1},\ldots,y_n\) generují prostor \(V\). Vezměme libovolný vektor \(z\in V\). Pro vhodné koeficienty \(\beta_i\) můžeme vektor vyjádřit jako\[\begin{align*} z&=\sum_{i=1}^n\beta_iy_i=\beta_ky_k+\sum_{i\neq k}\beta_iy_i=\frac{\beta_k}{\alpha_k}\left(x-\sum_{i\neq k}\alpha_iy_i\right) \\ &= \frac{\beta_k}{\alpha_k}x+\sum_{i\neq k}\left(\beta_i-\frac{\beta_k}{\alpha_k}\alpha_i\right)y_i \end{align*}\]
Steinitzovu větu o výměně:
Nechť \(B\) konečná lineárně nezávislá množina ve vektorovém prostoru \(V\) a \(C\) generuje \(V\). Pak existuje \(D\) taková, že
- \(\operatorname{span}(D)=V\)
- \(B\subseteq D\)
- \(|D|=|C|\)
- \(D\setminus B\subseteq C\)
Důkaz indukcí podle \(|B\setminus C|\). Když \(B\setminus C=\varnothing\), lze vzít \(D=C\). Jinak zvolíme libovolné \(b\in B\setminus C\) a položíme \(B'=B\setminus b\). Protože množina \(B'\) je lineárně nezávislá a \(|B'\setminus C|<|B\setminus C|\), podle indukčního předpokladu existuje \(D'\) pro \(B'\) a \(C\) taková, že:
- \(\operatorname{span}(D')=V\)
- \(B'\subseteq D'\)
- \(|D'|=|C|\)
- \(D'\setminus B'\subseteq C\)
Vyjádříme \(b\) vůči \(\{d_1,\ldots,d_n\}\subseteq D'\). Množina \(B\) je lineárně nezávislá, a tak \(a_i\neq 0\) pro nějaké \(d_i\notin B\). Potom \(D=(D'\setminus d_i)\cup b\) splňuje všechny čtyři vlastnosti (první z nich z lemmatu o výměně).

Q: Vyslovte a dokažte větu o dimenzi průniku vektorových prostorů.
A: Jsou-li \(U, V\) podprostory konečně generovaného prostoru \(W\), pak \(\operatorname{dim}(U)+\operatorname{dim}(V)=\operatorname{dim}(U\cap V)+\operatorname{dim}(\operatorname{span}(U\cup V))\).
Rozšíříme bázi \(B\) průniku \(U\cap V\) na bázi \(C\) prostoru \(U\) a také na bázi \(D\) prostoru \(V\). Potom \(|C|+|D|=|B|+|C\cup D|\). Lineární nezávislost \(B\cup C\cup D\): kdyby \(u\in\operatorname{span}(B\cup C)\cap\operatorname{span}(D)\), pak \(u\in U\cap V\Rightarrow [u]_D+0_{|D|}\Rightarrow u=0\Rightarrow[u]_{B\cup C}=0_{|B\cup C|}\).

Q: Vyslovte a dokažte větu o vektorových prostorech souvisejících s maticí \(A\) (včetně lemmatu o sloupcovém prostoru a jeho důkazu, pokud jej potřebujete).
A: Lemma o sloupcovém prostoru:
Jsou-li \(A\sim\sim A'\), kde \(A'\) je v odstupňovaném tvaru, potom sloupce \(A\) odpovídající bázickým proměnným tvoří bázi \(S_A\).
Označme \(\operatorname{rank}A=r\), indexy bázických proměnných \(j(1),\ldots,j(r)\) a příslušné sloupce matice \(A\) pomocí \(c_{j(1)},\ldots,c_{j(r)}\). Pro každé \(b\in S_A\) má soustava \(Ax=b\) právě jedno řešení \(x\), v němž všechny volné proměnné mají hodnotu 0.
Ze vztahu \(b=\sum_{i=1}^rx_{j(i)}c_{j(i)}\) plyne, že \(\operatorname{span}(\{c_{j(1)},\ldots,c_{j(r)}\}) = S_A\). Z jednoznačnosti \(x\) plyne, že \(\{c_{j(1)},\ldots,c_{j(r)}\}\) je lineárně nezávislá.
Věta: Každá \(A\) splňuje: \(\operatorname{dim}R_A=\operatorname{dim}S_A\), čili \(\operatorname{rank}A=\operatorname{rank}(A^\top)\).

Q: Vyslovte a dokažte větu o jedinečnosti lineárního zobrazení.
A: Nechť \(U\) a \(V\) jsou prostory nad \(T\) a \(B\) je báze \(U\). Pak pro jakékoli zobrazení \(f_0:B\to V\) existuje jediné lineární zobrazení \(f:U\to V\) rozšiřující \(f_0\), t.j. \(\forall b\in B:f(b)=f_0(b)\).
Pro jakékoli \(u\in U\) existují jednoznačná \(n\in\mathbb{N}_0\), \(a_1,\ldots,a_n\in T\setminus 0\) a \(b_1,\ldots,b_n\in B\) taková, že \(u=\sum_{i=1}^na_ib_i\). Potom \(f(u)=f(\sum_{i=1}^na_ib_i)=\sum_{i=1}^na_if(b_i)=\sum_{i=1}^na_if_0(b_i)\).

Q: Vyslovte a dokažte tvrzení, že převod na vektor souřadnic je lineární zobrazení.
A: Nechť \(U\) je prostor nad \(T\) s bazí \(B=(b_1,\ldots,b_n)\). Potom zobrazení \(f:U\to T^n\) definované \(f(u)=[u]_B\) je lineární.
Pro \(u,b\in U\) vyjádříme \(u=\sum_{i=1}^na_ib_i\) a \(v=\sum_{i=1}^nc_ib_i\), čili vektory souřadnic jsou \([u]_B=(a_1,\ldots,a_n)^\top\), \([v]_B=(c_1,\ldots,c_n)^\top\).
Linearita součtu: \[\begin{multline*} f(u+v)=[u+v]_B=\left[\sum_{i=1}^na_ib_i+\sum_{i=1}^nc_ib_i\right]_B\\ =\left[\sum_{i=1}^n(a_i+c_i)b_i\right]_B=(a_1+c_1,\ldots,a_n+c_n)^\top\\ =(a_j,\ldots,a_n)^\top+(c_1,\ldots,c_n)^\top=[u]_B+[v]_B=f(u)+f(v) \end{multline*}\]
Linearita skalárního násobku: pro \(t\in T\) \[\begin{multline*} f(tu)=[tu]_B=\left[t\sum_{i=1}^na_ib_i\right]_B=\left[\sum_{i=1}^nta_ib_i\right] =(ta_1, \ldots, ta_n)^\top=t(a_1,\ldots,a_n)^\top=t[u]_B=tf(u) \end{multline*}\]

Q: Vyslovte a dokažte větu o charakterizaci isomorfismu mezi vektorovými prostory pomocí matic.
A: Lineární zobrazení \(f:U\to V\) je isomorfismus prostorů \(U\) a \(V\) s konečnými bázemi \(B\) a \(C\), právě když \([f]_{B,C}\) je regulární.
\(\Leftarrow\): Uvažme \(g:V\to U\) takové, že \([g]_{C,B}=([f]_{B,C})^{-1}\). Pak:
\([g\circ f]_{B,B}=([f]_{B,C})^{-1}[f]_{B,C}=I_{|B|}=[\operatorname{id}]_{B,B}\Rightarrow\) je prosté,
\([f\circ g]_{C,C}=[f]_{B,C}([f]_{B,C})^{-1}=I_{|C|}=[\operatorname{id}]_{C,C}\Rightarrow\) je na.
\(\Rightarrow\): Protože \(f(U)=V\) a \(f^{-1}(V)=U\), máme \(\operatorname{dim}(U)=\operatorname{dim}(V)\). Matice \([f]_{B,C}\) je čtvercová a splňuje \([f^{-1}]_{C,B}[f]_{B,C}=[id]_{B,B}=I\).

Q: Vyslovte a dokažte větu o řešení rovnice s lineárním zobrazením.
A: Nechť \(f:U\to V\) je lineární zobrazení. Pro libovolné \(v\in V\), rovnice \(f(x)=v\) buď nemá žádné řešení, nebo řešení tvoří afinní prostor \(u+\operatorname{ker}(f)\), kde \(u\) je libovolné řešení rovnice \(f(x)=v\).
Když \(x\in u+\operatorname{ker}(f)\), pak \(x=u+w\) pro \(w\in\operatorname{ker}(f)\). Nyní \(f(x)=f(u+w)=f(u)+f(w)=v+0=v\).
Naopak, pro \(f(x)=v\) platí \(f(x-u)=f(x)-f(u)=v-v=0\), čili \(x-u\in\operatorname{ker}(f)\), a odtud \(x\in u+\operatorname{ker}(f)\).