\documentclass[12pt,a4paper,leqno]{amsart}

\pagestyle{myheadings}

\textwidth=154mm

\hoffset=-14mm

\usepackage{latexsym,amsmath,amsfonts,amssymb,xypic}

\usepackage{czech}

\newtheorem*{thm}{V�ta}

\newtheorem{thmn}{V�ta}[section]

\newtheorem*{cor}{D�sledek}

\newtheorem*{lemma}{Lemma}

\newtheorem{lemman}[thmn]{Lemma}

\newtheorem*{prop}{Tvrzen�}

\newtheorem{propn}[thmn]{Tvrzen�}

\newtheorem*{ap*}{Appendix}

\theoremstyle{definition}

\newtheorem*{defin}{Definice}

\newtheorem*{remark}{Pozn�mka}

\newtheorem{remarkn}[thmn]{Pozn�mka}

\newtheorem*{example}{P��klad}

\newtheorem{examplen}{P��klad}

\newtheorem*{exerc}{Cvi�en�}

\newtheorem*{notat}{Ozna�en�}
%%
%%
\newenvironment{mylist}{\begin{list}{(\/\alph{enumi}\/)}{\usecounter{enumi}
\setlength{\rightmargin}{0pt}
\setlength{\leftmargin}{5pt}
\setlength{\itemindent}{0pt}
\setlength{\itemsep}{.5\jot}
%\setlength{\topsep}{-12pt}
}}{\end{list}}

\def\id{\operatorname{id}}

\def\const{\operatorname{const}}

\def\im{\operatorname{Im}}

\def\re{\operatorname{Re}}

\def\tr{\operatorname{tr}}

\def\lin{\operatorname{Lin}}

\def\af{\operatorname{Af}}

\def\sign{\operatorname{sign}}

\newcommand{\card}{\operatorname{card}}

\def\hom #1 #2;{\operatorname{Hom}(#1,#2)}

\def\st{\operatorname{st}}

\def\mat{\operatorname{Mat}}

\def\diag{\operatorname{diag}}

\def\rr{\mathbb{R}}

\def\cc{\mathbb{C}}

\def\kk{\mathbb{K}}

\def\ee{\mathbb{E}}

\def\zz{\mathbb{Z}}

\def\qq{\mathbb{Q}}

\def\nn{\mathbb{N}}

\def\ss{\mathbb{S}}

\def\A{{\mathcal A}}

\def\B{{\mathcal B}}

\def\P{{\mathcal P}}

\def\E{{\mathcal E}}

\def\N{{\mathcal N}}

\def\jj{\mathbb{J}}

\def\s #1{{\mathcal S}_{#1}}

\newcommand{\dd}[2][]{\frac{\partial #1}{\partial #2}}

\def\vek #1{\/{\mathbf#1}\/} %vektory psane tucne
%\def\vek #1{{\boldkey #1}} vyzkouset, jak tohle funguje
 
\def\sour #1{\/{\mathbf#1}\/} %souradnice vektoru v neuvedene bazi, 
%take tucne, casem bud bude vypadat jinak, nebo prejmenuj na \vek

\def\bod #1{[#1]}	%linearni obal aritmetickeho zastupce, bod v \P_n
%\def\bod #1{\langle #1\rangle} %a puvodni definice, ktera se libila mne

\def\vct #1{\overrightarrow{#1}} %-> oznacujici vektor z bodu do bodu

\def\vctc #1{\overrightarrow{#1}
{\lower-1.5ex\hbox{$\mathbb{\scriptstyle C}$}}}
	%->cc oznacujici vektor z bodu do bodu v komplexifikaci

\newcommand{\skal}{\cdot} %skalarni soucin -- mozna bude chtit tlustsi tecku

%\newcommand{\df}[1]{{\em #1}\index{#1}} %definovany pojem v definici
\newcommand{\df}[1]{{\em #1}} %definovany pojem v definici

%\makeindex

\newcommand{\trid}[1]{[#1]} % trida ekvivalence

\catcode`\"=13 \def"{\begingroup\clqq \def"{\crqq\endgroup}} %ceske uvozovky 

%\setlength{\parskip}{1ex}

%\setlength{\belowdisplayskip}{24pt plus 3pt minus 9pt}

%% konec definic a maker
%%
%%



\begin{document}
\begin{center}{\large\bf Letm� �vod k algebraick�m struktur�m}\\
\sc Prvn� pracovn� verze\end{center}

\bigskip

\noindent{\small\em 
Tento text na p��kladech ukazuje vlastnosti z�kladn�ch algebraick�ch struktur
-- grup, okruh�, pol�, vektorov�ch prostor� a algeber.  Zvl�tn� d�raz je
kladen na vysv�tlen� operac� v okruhu matic.
Nejde o u�ebnici line�rn� algebry, tak�e n�kter� d�le�it� pojmy jsou opomenuty
nebo nen� dostate�n� vysv�tlen jejich v�znam.}


\section{Matice a algebraick� struktury}
\begin{defin} \df{Matic� typu $k \times l$ nad mno�inou $S$} rozum�me zobrazen�
$$M:\{1,\dots,k\}\times\{1,\dots,l\}\to S.$$
��k�me t�, �e matice $M$ m� $k$ ��dk� a $l$ sloupc�.
Hodnot� $M(i,j)$ ��k�me \df{prvek matice $M$ v $i$-t�m ��dku a $j$-t�m
sloupci}. 
Matice �asto zapisujeme prost�ednictv�m obd�ln�kov� tabulky s $k$ ��dky a $l$
sloupci.
Poznamenejme, �e v tomto textu v rozporu se zaveden�m zna�en�m (ale
v souladu s logiku edice {\em Letm� �vod}) nebudeme prvky matic zna�it mal�mi
p�smeny.  
\end{defin}



Nyn� uk�eme, �e mno�iny matic maj� ur�itou strukturu, ani� bychom
p�esn� definovali, co se strukturou rozum�.  Tento pojem v�ak osv�tl�me na �ad�
p��klad�.

\medskip
V mno�in� p�irozen�ch ��sel $\nn=\{0,1,\dots\}$ lze prvky s��tat a n�sobit.  To
znamen�, �e existuj� dv� \df{(bin�rn�) operace}, ��m� rozum�me zobrazen� 
\begin{align*}&+: \nn\times\nn\to\nn\\&\cdot:\nn\times\nn\to\nn.
\end{align*}
P��eme ale pro p�ehlednost $a+b$ nam�sto $+(a,b)$ a podobn� pro n�soben�.

P��kladem struktury je mno�ina p�irozen�ch ��sel s t�mito 
dv�ma (bin�rn�mi) operacemi.

Od��t�n� ani d�len� nejsou operacemi na $\nn$, proto�e rozd�l
nebo pod�l dvou p�irozen�ch ��sel nemus� b�t p�irozen� ��slo. 

Pokud chceme, aby od��t�n� byla operace, mus�me roz���it ��seln� obor, s n�m�
pracujeme.  Dostaneme cel� ��sla $\zz$.  Podobn� se n�m ale nepoda�� roz���it
p�irozen� ��sla na n�jak� ��seln� obor, aby bylo operac� i d�len� -- nulou
d�lit nejde.

S��t�n� v $\zz$ je operace, kter� m� tyto vlastnosti:
\begin{align} \forall a,b,c\in\zz: a+(b+c)=(a+b)+c&\qquad\text{(asociativita)}
\label{asoc}\\
\exists 0\in\zz\forall a\in\zz: 0+a=a+0=a&\qquad\text{(existence neutr�ln�ho
prvku)}\label{neutralni prvek}\\
\forall a\in\zz\exists b\in\zz: a+b=0&\qquad\text{(existence inverzn�ho prvku)}
\label{inverze}\\
\forall a,b\in\zz: a+b=b+a&\qquad\text{(komutativita)}\label{komut}
\end{align} 

\begin{defin} �ekneme, �e mno�ina $S$ spolu s operac� $\star$ je \df{grupa}, pokud
spl�uje vlastnosti \ref{asoc}--\ref{inverze}, a \df{komutativn� grupa}, pokud
spl�uje \ref{asoc}--\ref{komut}.  Mno�inu $S$ s operac� $\star$ zapisujeme dvojic�
$(S,\star)$.
\end{defin}

\begin{examplen}
Tedy s��t�n� v $\zz$ je komutativn� grupa.
S��t�n� v $\nn$ vlastnosti komutativn� grupy nem� a n�soben� v $\nn$ ani v
$\zz$ tak� ne.  Pov�imn�te si ale, kter� z vlastnost� komutativn� grupy
n�soben� v $\nn$ a v $\zz$ spl�uje: je asociativn�, existuje neutr�ln� prvek a
je komutativn�.  Kdybychom p�idali zlomky a pracovali s racion�ln�mi ��sly
$\qq$, stejn� nebude existovat inverzn� prvek pro ka�d� $a\in\qq$.  

N�soben� na $\qq-\{0\}$ je grupa.

Od��t�n� v $\zz$ nen� grupa.  Tak� d�len� v $\qq$ nen� grupa a ani v
$\qq-\{0\}$ to nen� grupa.

Mno�ina $\zz_3=\{-1,0,1\}$ zbytkov�ch t��d po d�len� 3 je komutativn� 
grupa vzhledem k operaci s��t�n� definovan� tabulkou
$$\begin{array}{c|ccc}
+&-1&0&1\\\hline
-1&1&-1&0\\
0&-1&0&1\\
1&0&1&-1
\end{array}$$
Mno�ina $S_0=\{-1,1\}\subseteq \zz$ s n�soben�m definovan�m stejn� jako v $\zz$
je komutativn� grupa.  Pov�imn�te si, �e $S_0=\zz_3-\{0\}$ -- je to ur�it�
analogie s $\qq-\{ 0\}$, kter� bude pozd�ji d�le�it�.
\end{examplen}

Nyn� se pokus�me definovat operace tak� na mno�in�ch matic.  Ozna�me
$$\mat_{k \times l}(S)=\Big\{M:\{1,\dots,k\}\times\{1,\dots,l\}\to S\Big\}$$
mno�inu v�ech matic typu $k \times l$.  

Pokusme se definovat s��t�n� v $\mat_{k \times l}(S)$ "po slo�k�ch" p�edpisem
$$(M+N)(i,j)=M(i,j)+N(i,j),$$
kde $M,N\in\mat_{k \times l}(S)$, $i=1,\dots,k$, $j=1,\dots,l$.


Uv�domte si, �e tato definice ned�v� ��dn� smysl, proto�e v obecn� mno�in� $S$
neum�me s��tat.  V $\mat_{k\times l}(\nn)$ jde ale o operaci.

\begin{exerc} Doka�te, �e je-li $(G,+)$ grupa, je $\mat_{k \times l}(G)$ s v��e
definovan�m s��t�n�m tak� grupa, a je-li $(G,+)$ komutativn�, je i 
$\mat_{k \times l}(G)$ komutativn� grupa.
\end{exerc}

Podobn� jako s��t�n� lze v $\mat_{k \times l}(\nn)$ definovat operaci n�soben�
$$(M\ast N)(i,j)=M(i,j)\cdot N(i,j).$$  

\begin{remark} 
Toto n�soben� nem� velk� vyu�it� a to, �e jej zde uv�d�me, je matouc� a
nepedagogick�.
\end{remark}

\begin{exerc} Rozhodn�te, zda $\big(\mat_{k \times l}(\zz),\ast\big)$,
$\big(\mat_{k \times l}(\qq),\ast\big)$ nebo $\big(\mat_{k \times
l}(\qq-\{0\}),\ast\big)$ jsou
grupy, p��padn� komutativn� grupy.
\end{exerc}

Vra�me se nyn� k cel�m ��sl�m.  Nic n�m nebr�n� uva�ovat operace s��t�n� a
n�soben� sou�asn�.  V�me, �e $(\zz,+)$ je komutativn� grupa  a $(\zz,\cdot)$
nikoli.  Plat� v�ak n�kolik vlastnost�, kter� svazuj� tyto dv� bin�rn� operace
dohromady:
\begin{align} \forall a,b,c\in\zz: a\cdot(b+c)=a\cdot b+a\cdot c&
\qquad\text{(lev� distributivita)}\label{leva distrib}\\
\forall a,b,c\in\zz: (a+b)\cdot c=a\cdot c+b\cdot c&\qquad\text{(prav�
distributivita)}\label{prava distrib}
\end{align}
Nav�c, jak jsme ji� podotkli v��e, je n�soben� v $\zz$ asociativn� a
komutativn� a m� neutr�ln� prvek.

\begin{defin} Mno�ina $S$ s dv�ma (bin�rn�mi) operacemi $+$ a $\cdot$ se naz�v�
\df{okruh}, pokud $(S,+)$ je komutativn� grupa, operace $\cdot$ je na $S$
asociativn� a m� neutr�ln� prvek a pokud $+$ a $\cdot$ spl�uj� \ref{leva
distrib}--\ref{prava distrib}.  Je-li nav�c $\cdot$ komutativn�, mluv�me o
\df{komutativn�m okruhu}.
\end{defin}

\begin{remark} Pov�imn�te si, �e $+$ v okruhu je podle na�� definice komutativn� 
v�dy.  Okruhy lze definovat obecn�ji, ale v na�ich �vah�ch to nebudeme
pot�ebovat.  Nekomutativn� $+$ vede k takov�m komplikac�m, �e rad�ji vol�me
m�n� obecnou definici.
\end{remark}

\begin{notat} V p��pad�, �e nem��e b�t pochyb o tom, kter� operace v grup�ch �i
okruz�ch uva�ujeme, budeme m�sto ozna�en� grupy �i okruhu pou��vat pouze
ozna�en� mno�iny bez operac�.  Budeme se sna�it ozna�ovat abstraktn� 
mno�iny p�smenem $S$ (set), grupy $G$ a okruhy $R$ (ring).  

Neutr�ln� prvek
vzhledem k operaci $+$ budeme ozna�ovat $0$ a inverzn� prvek vzhledem k $+$
budeme naz�vat opa�n� prvek.  Neutr�ln� prvek vzhledem k $\cdot$ budeme
ozna�ovat $1$.  Tato konvence odpov�d� ozna�en� prvk� v ��seln�ch oborech,
tak�e by nem�la b�t p��li� matouc�.  Rad�ji se zamyslete, zda v�s v p�edchoz�m
textu nem�tlo, �e nap�. neutr�ln�m prvkem  v grup� $(\qq-\{0\},\cdot)$ byl prvek
$1$.  N�zev inverzn� prvek vyhrad�me v okruz�ch pro inverzn� prvek v��i
$\cdot$.
\end{notat}

\begin{examplen} P��kladem okruh� je $(\zz,+,\cdot)$, $(\qq,+,\cdot)$, nikoli
$(\qq-\{0\},+,\cdot)$.  Okruhem je tak� $(\zz_3,+,\cdot)$, kde n�soben� je
stejn� jako v $\zz$.

Mno�ina 
$\big(\mat_{k \times l}(\nn),+,\ast\big)$ okruhem nen�, ale 
$\big(\mat_{k \times l}(\zz),+,\ast\big)$ a
$\big(\mat_{k \times l}(\qq),+,\ast\big)$ ano.

Dal��m p��kladem okruhu jsou polynomy $\nn[x]$, $\zz[x]$ a $\qq[x]$ s
koeficienty v mno�in� p�irozen�ch, resp. cel�ch a racion�ln�ch ��sel.
Operacemi na polynomech jsou b�n� s��t�n� a n�soben� polynom�.

Ve v�ech p��kladech okruh� jde o komutativn� okruhy.  S podstatn�m p��kladem
nekomutativn�ho okruhu se setk�me v p��kladu \ref{definice GLn}.
\end{examplen}

\medskip
Pov�imn�te si, �e n�kter� okruhy se m�rn� li�� od jin�ch  v tom, jak "dobr�" je
v nich n�soben�, resp. kolik prvk� m� inverzi vzhledem k n�soben�.

\begin{defin} Nech� v komutativn�m okruhu $(R,+,\cdot)$ je spln�na vlastnost
\begin{align} \forall r\in R, r\neq 0 \exists s\in R: r\cdot s=s\cdot
r=1&\qquad\text{(vlastnost pole)}\label{pole}
\end{align}
Pak $(R,+,\cdot)$ naz�v�me \df{pole}.
\end{defin}

\begin{remark} Je-li vlastnost \ref{pole} spln�na v nekomutativn�m okruhu,
naz�v�me jej \df{t�leso}.  V dal��m textu se v�ak budeme v�novat v�hradn�
pol�m, proto�e teorie t�les je zna�n� komplikovan� a nem� pro ��ely tohoto
textu valn� v�znam.  
\end{remark}

\begin{examplen} P��kladem pole je $(\qq,+,\cdot)$ nebo $(\zz_3,+,\cdot)$.
��dn� dal�� okruh z uveden�ch p��klad� polem nen�.  Zamyslete se p�edev��m,
pro� nespl�uje vlastnost \ref{pole} mno�ina matic
$\big(\mat_{k \times l}(\qq),+,\ast\big)$.  Toto je tak� patrn� vhodn� m�sto na
to, abyste si p�ipomn�li, jak vypadaj� prvky $0$ a $1$ v matic�ch a jak� jsou
tam opa�n� a inverzn� prvky.
\end{examplen}

\begin{exerc} Doka�te tvrzen� obsa�en� v p�ede�l�m p��kladu.
\end{exerc}

\begin{exerc} Nech� v $(R,+,\cdot)$ plat� siln�j�� vlastnost ne� \ref{pole}:
$$\forall r\in R\exists s\in r: r\cdot s=s\cdot r=1.
$$
Doka�te, �e pak $R=\{1\}$ je tzv. \df{trivi�ln� okruh}, kter� nen� p��li�
zaj�mav�.  To znamen�, �e vlastnost \ref{pole} nen� "slab�" a definice pole je
"rozumn�".
\end{exerc}

\begin{remark} Pole pro n�s budou d�le�it� pozd�ji.  Slu�� se tak� vysv�tlit,
pro� neuv�d�me jako p��klady pol� dal�� ��seln� obory, re�ln� a komplexn�
��sla.  D�vodem je to, �e z hlediska line�rn� algebry nep�in�� tyto mno�iny
nic podstatn� odli�n�ho od mno�iny racion�ln�ch ��sel.  D�vodem dal��ho roz�i�ov�n�
��seln�ho oboru je bu� snaha o metrickou �plnost, nebo o p�id�n� ko�en�
polynom� vy���ho ��du, co� pro ��ely tohoto textu nem� ��dn� v�znam.
\end{remark}

\bigskip
Grupy a okruhy p�edstavovaly struktury s (bin�rn�mi) operacemi.  Nyn� se budeme
v�novat struktur�m zcela odli�n�m.

\medskip
Uv�domte si, �e pro $a\in\zz$ a polynom $p\in\qq[x]$ m� smysl uva�ovat polynom
s racion�ln�mi koeficienty $a\cdot p$, ��m� rozum�me pro $p=b_nx^n+\dots
b_1x+b_0$ polynom
$$a\cdot p=(a\cdot b_n)x^n+\dots +(a\cdot b_1) x+(a\cdot b_0).$$
Toto n�soben� ale nen� v ��dn�m p��pad� bin�rn� operace, nebo� m�ch�me prvky dvou
r�zn�ch mno�in.  Form�ln� toto n�soben� p�edstavuje zobrazen�, kter� pro v�t��
p�ehlednost ozna��me jin�m symbolem
$$\odot : \zz \times\qq[x]\to\qq[x].$$

Pov�imn�te si, �e toto zobrazen� spl�uje
\begin{align} \forall p\in\qq[x]: 1\odot p=p&\qquad\text{(vlastnost jednotky)}
\label{jednotka}\\
\forall a,b\in\zz \forall p\in\qq[x]: a\odot (b\odot p)=
(a\cdot b)\odot p&\qquad\text{(vn�j�� asociativita)}\label{vnejsi asoc}
\end{align}

Pov�imn�te si vlastnosti \ref{jednotka}.  Zde 1 ch�peme jako prvek $\zz$ a
nikoli jako polynom nulov�ho stupn� z $\qq[x]$.

\begin{remark} 
Nech� $G$ je libovoln� grupa a  $S$ libovoln�
mno�ina.  Pak zobrazen� $G\times S\to S$ spl�uj�c� \ref{jednotka} a
\ref{vnejsi asoc} naz�v�me \df{akce grupy $G$ na mno�in� $S$}.  Akc�m grup je
z podstatn� ��sti v�nov�n {\em Letm� �vod k afinn�m prostor�m}, tak�e je
nebudeme rozeb�rat p��li� podrobn�.
\end{remark}

V na�em p��pad� jsou v�ak $\zz$ a $\qq[x]$ okruhy a d�ky tomu m� akce $\odot$
dal�� v�znamn� vlastnosti:
\begin{align}
\forall a\in \zz\forall p,q\in\qq[x]: a\odot(p+q)=a\odot p+a\odot q&
\quad\text{(lev� vn�j�� distributivita)}\label{leva vne distrib}\\
\forall a,b\in\zz\forall p\in\qq[x]:
(a+b)\odot p=a\odot p+b\odot p&\quad\text{(prav� vn�j�� distributivita)}
\label{prava vne distrib}
\end{align}

\begin{exerc} Pokuste se pochopit, kter� operace $+$ je na kter�m m�st�
ve vlastnostech \ref{jednotka}--\ref{prava vne distrib} pou�ita.  V dal��m
textu budeme u� op�t pro jednoduchost ozna�ovat akci $\odot$ symbolem b�n�ho
n�soben�, tak�e si dob�e rozmyslete vlastnost \ref{vnejsi asoc}, kde vystupuj�
oba tyto symboly.
\end{exerc}

\begin{remark} Pov�imn�te si, �e vlastnosti \ref{jednotka}--\ref{prava vne
distrib} nevyu��vaj� toho, �e $\qq[x]$ je okruh.  Ve skute�nosti bychom tak
m�li mluvit o vlastnosti \ref{vnejsi asoc} jako o lev� vn�j�� asociativit�,
p�i�em� prav� vn�j�� asociativita by vyu��vala n�soben� v $\qq[x]$.  Vlastnosti
formulovan� v��e v�ak u�ijeme v n�sleduj�c� definici.
\end{remark}

\begin{defin} Nech� $(R,+,\cdot)$ je libovoln� okruh a $(G,+)$ komutativn�
grupa.  Nech� je definov�na akce $\odot:R\times G\to G$ spl�uj�c� vlastnosti
\ref{jednotka}--\ref{prava vne distrib}.  Pak �ekneme, �e \df{$G$ je modul nad
$R$}, prvky $R$ naz�v�me \df{skal�ry} a 
akci $\odot$ nazveme \df{vn�j�� n�soben�} nebo t� \df{n�soben�
skal�rem}.  
\end{defin}

\begin{examplen}
\label{moduly}
Tak� $\zz[x]$ je modul nad $\zz$, ale $\zz[x]$ nen� modul nad
$\qq$.  Pov�imn�te si, �e tak� $\qq$ je modul nad $\zz$ a $\zz$ je modul nad
$\zz$.  To je p��kladem hned dvou d�le�it�ch fakt�.

P�edn�, 
ka�d� okruh $(R,+,\cdot)$ je modulem nad $(R,+,\cdot)$, p�i�em� vn�j�� n�soben�
splyne s n�soben�m $\cdot$.

M�n� evidentn� je druh� tvrzen�: Ka�d� komutativn� grupa $(G,+)$ je modul nad $\zz$,
p�i�em� operace $\odot: \zz\times G\to G$ je definov�na n�sledovn�.  Nech�
$g\in G$ je libovoln� a $a\in\zz$ je kladn� ��slo, pak
$$a\odot g=g+g+\dots+g,$$
kde $g$ se�teme $a$-kr�t.  Nech� $a=0$, pak polo�me $a\odot g=0\in G$.  Nech�
kone�n� $a$ je z�porn�, pak 
$$a\odot g=(-g)+(-g)+\dots+(-g),$$
kde $-g$ ozna�uje inverzn� prvek k $g$ a s��t�me $(-a)$-kr�t.

Je p�itom samoz�ejm�, �e ka�d� modul nad $\zz$ je z�rove� komutativn� grupou,
tedy mezi komutativn�mi grupami a moduly nad $\zz$ nen� ��dn� rozd�l.
\end{examplen}

\begin{exerc} Uva�te p��klady r�zn�ch okruh� a grup, s nimi� jsme se ji�
setkali, a pokuste se rozhodnout, zda jsou n�kter� z nich modulem nad n�kter�mi
z t�chto okruh�.  P�edev��m si v��mejte maticov�ch okruh� a grup.
\end{exerc}

\begin{examplen} Ozna�me symbolem $\qq[x]_n$ mno�inu v�ech polynom� stupn�
nejv��e $n$, tedy
$$\qq[x]_n=\{a_nx^n+\dots+a_1x+a_0;a_n,\dots,a_0\in \qq\}.$$
Tato mno�ina je z�ejm� komutativn� grupou vzhledem k operaci s��t�n�.  Je to
tedy modul nad $\zz$.  Je to ov�em tak� modul nad $\qq$.  Na $\qq[x]_n$ lze
definovat n�soben� podobn� jako v p��pad� zbytkov�ch t��d $\zz_n$, ale t�m se
zab�vat nebudeme.  Pro na�e ��ely jde o vhodn� p��klad modulu nad $\qq$.
\end{examplen}

\begin{exerc} Nech� $(R,+,\cdot)$ je okruh, $(G,+)$ komutativn� grupa a 
$\odot: R \times G\to G$ definov�no pro ka�d� $r\in R$ a ka�d� $g\in G$
p�edpisem $r\odot g=g$.  M��e b�t $G$ modulem nad $R$ vzhledem k tomuto
vn�j��mu n�soben�?
\end{exerc}

\begin{examplen} 
Pov�imn�me si nyn� rozd�lu mezi moduly nad $\zz$ 
a moduly nad $\qq$.  V�me ji�, �e $\qq$ je modul nad $\zz$ i nad $\qq$.
Ch�pejme nyn� $\qq$ jako modul nad $\qq$ a zvolme
libovoln� nenulov� skal�r $p\in\qq$ a prvek $q\in\qq$.  Pak
z�ejm� existuje skal�r $p^{-1}\in\qq$ tak, �e
$$q=(p^{-1}\cdot p)\cdot q=p^{-1}\cdot(p\cdot q).$$
Nyn� ale ch�pejme $\qq$ jako modul nad $\zz$ a zvolme libovoln� nenulov� skal�r
$a\in\zz$.  Pak ale 
$$q=(a^{-1}\cdot a)\cdot q=a^{-1}\cdot(a\cdot q)$$
jen v t�ch p��padech, kdy existuje inverzn� prvek k $a$, tedy pouze tehdy,
je-li $a=\pm 1$.
\end{examplen}

\begin{defin} Modul nad polem naz�v�me \df{vektorov� prostor}.  Prvky
vektorov�ho prostoru naz�v�me \df{vektory}.
\end{defin}

\begin{notat} Abstraktn� pole budeme ozna�ovat symbolem $\kk$ a budeme mluvit o
vektorov�ch prostorech nad polem $\kk$.
\end{notat}

\begin{remark} Vektorov� prostory jsou z�kladn�m pojmem line�rn� algebry.
Prostor, kter� jim v�nujeme v tomto textu, pochopiteln� nen� dostate�n�.
Doporu�ujeme proto d�kladn� studium tohoto pojmu v n�kter� z u�ebnic, nap�.
\cite{hefferon} nebo \cite{slovak}.
\end{remark}

\begin{examplen} Grupy $\qq$, $\qq[x]$ a $\qq[x]_n$ jsou vektorov�mi prostory
nad polem $\qq$.  Grupa matic $\mat_{k \times l}(\qq)$ je vektorov� prostor nad
$\qq$.  Obecn� ka�d� pole je vektorov�m prostorem nad sebou sam�m.  Mno�ina
$\{0\}$ je vektorov� prostor nad ka�d�m polem.
\end{examplen}

Pojem vektorov�ho prostoru se m��e na prvn� pohled zd�t pon�kud zbyte�n�m.
Oproti modul�m nad obecn�m okruhem v�ak m�me mo�nost formulovat n�kter�
d�le�it� pojmy.

\begin{defin} �ekneme,  �e mno�ina vektor� $S \subseteq V$ je \df{line�rn�
nez�visl�}, pokud pro ka�dou jej� kone�nou podmno�ina $\{v_1,\dots,v_k\}\subseteq S$ 
a ka�dou mno�inu skal�r� $\{a_1,\dots, a_k\}$ plat�, �e 
$$a_1\cdot v_1+\dots +a_k\cdot v_k=0\qquad\implies\qquad a_1=\dots=a_k=0.$$
�ekneme, �e mno�ina je \df{line�rn� z�visl�}, pokud nen� line�rn� nez�visl�.
\end{defin}

\begin{examplen}\label{jeden nezav}
Mno�ina $\{0\} \subseteq V$ je v�dy line�rn� z�visl�, obecn�ji
ka�d� mno�ina vektor� obsahuj�c� nulov� vektor je line�rn� z�visl�.
Jednoprvkov� mno�ina $\{v\}$, kde $v\in V$ je nenulov� vektor, je v�dy line�rn�
nez�visl�.
\end{examplen}

\begin{examplen} Ozna�me $\zz_6=\{0,1,\dots,5\}$ a definujme s��t�n� a n�soben�
na $\zz_6$ n�sledovn�: nech� pro $a,b\in\zz_6$ je $a+b$ rovno zbytku po d�len�
$6$ ze sou�tu $a+b$ v $\nn$, podobn� nech� $a\cdot b$ je rovno zbytku po d�len�
$6$ ze sou�inu $a\cdot b$ v $\nn$.  Takto je nap�. $4+3=1$ nebo $2\cdot 5=4$.
Lze snadno uk�zat, �e $(\zz_6,+,\cdot)$ je okruh.  Z p��kladu \ref{moduly}
v�me, �e ka�d� okruh je modulem s�m nad sebou.  P�itom $\zz_6$ nen� pole, nebo�
jen $1$ a $5$ m� v $\zz_6$ inverzi.  Tedy $\zz_6$ nen� vektorov� prostor nad
$\zz_6$.

Srovnejte to se $\zz_3$, kter� je vektorov�m prostorem nad $\zz_3$.  (Lze
uk�zat, �e $\zz_n$ je pole pr�v� tehdy, kdy� $n$ je prvo��slo.)

Uva�me nyn� mno�inu $\{2\} \subseteq \zz_6$.  Proto�e $3\cdot 2=0$, 
vid�me, �e na rozd�l od vektorov�ch prostor� m��e b�t jeden prvek modulu line�rn�
z�visl�.  Tedy v modulech nemus� m�t pojem line�rn� nez�vislosti smysl.
\end{examplen}

\begin{examplen} Ve skute�nosti byl hlavn� probl�m p�edchoz�ho p��kladu v tom,
�e v $\zz_6$ existuj� tzv. \df{d�litel� nuly}, tedy nenulov� prvky, kter� lze
vyn�sobit vhodn�m nenulov�m prvkem tak, �e v�sledkem je nula.  Uv�domte si, �e
nap�. v $\zz$ d�litel� nuly nejsou.  Okruhu bez d�litel� nuly ��k�me \df{obor
integrity}.  V modulech nad oborem integrity m� line�rn� z�vislost a nez�vislost smysl,
nicm�n� z�hy dosp�jeme k dal��mu pojmu, kter� uk�e, pro� je v�hodn�j��
pracovat s vektorov�mi prostory.
\end{examplen}

\begin{defin} Nech� $V$ je vektorov� prostor nad $\kk$
a $v_1,\dots,v_k\in V$.  Nech� $a_1,\dots,a_k\in\kk$.  V�raz tvaru 
$$a_1\cdot v_1+\dots+a_k\cdot v_k$$
nazveme \df{line�rn� kombinac� vektor� $v_1,\dots,v_k$}.
\end{defin}

\begin{remark} Plat� z�ejm� $0\cdot v_1+\dots +0\cdot v_k=0$
pro libovoln� vektory $v_1,\dots,v_k$.  Line�rn� kombinaci s nulov�mi skal�ry
��k�me \df{trivi�ln� line�rn� kombinace}.  To tedy znamen�, �e vektory
$v_1,\dots,v_k$ jsou line�rn� nez�visl� pr�v� tehdy, je-li ka�d� jejich
netrivi�ln� line�rn� kombinace r�zn� od nuly.
\end{remark}

\begin{remark} Line�rn� kombinace jsou jen kone�n� sou�ty.  To plyne z toho, �e
operace sou�tu v�ce vektor� je vlastn� definov�na pomoc� indukce, tedy pro
$v_1,\dots,v_n\in V$ mus�me ch�pat
$v_1+\dots+v_n$ jako $v_1+(v_2+(\dots+(v_{n-1}+v_n)\dots)$, p�i�em� na
uz�vorkov�n� nez�le��, nebo� s��t�n� je asociativn�.  Jinak �e�eno, d�ky tomu,
�e um�me se��st dva vektory, um�me jich se��st kone�n� mnoho.  

Proto�e �asto pracujeme s nekone�n�mi mno�inami, nab�z� se chybn� p�edstava, �e
i operace mohou b�t nekone�n�kr�t opakov�ny.  U� v nejjednodu���m p��kladu
vektorov�ho prostoru $\qq$ nad $\qq$ dob�e v�me, �e nekone�n� sou�et
racion�ln�ch ��sel nen� racion�ln� ��slo, ale n�jak� podivn� nekone�n� �ada.

Promyslete si, zda podobnou chybu ned�l�te p�i pr�ci s libovoln�mi operacemi,
nejen s line�rn�mi kombinacemi ve vektorov�m prostoru.
\end{remark}

\begin{examplen}
\label{zavisly komb ostatnich}
Nech� $v_1,\dots,v_k\in V$ jsou line�rn� z�visl�.  Pak lze
n�kter� z vektor� $v_1,\dots,v_k$ vyj�d�it jako line�rn� kombinaci ostatn�ch.
Skute�n�, je-li
$$a_1\cdot v_1+\dots+a_k\cdot v_k=0$$
pro vhodn� skal�ry  a $a_i\neq 0$ pro n�kter� $i=1,\dots,k$, pak
$$v_i=a_i^{-1}\cdot (a_1\cdot v_1+\dots+a_{i-1}\cdot v_{i-1}
+a_{i+1} \cdot v_{i+1}+\dots +a_k\cdot v_k).$$
Uv�domte si, �e ne ka�d� vektor $v_i$ lze takto vyj�d�it, nebo� je-li p��slu�n� 
skal�r
$a_i$ roven nule, neexistuje k n�mu inverzn� prvek.

Rozmyslete si pe�liv� situaci, kdy je jedin� skal�r v line�rn�
kombinaci nenulov�.  
\end{examplen}

\begin{examplen} 
Pov�imn�te si, �e toto tvrzen� neplat� v modulech nad obory integrity, proto�e
ne ka�d� nenulov� prvek oboru integrity m� inverzn� prvek.
Nech� $\zz$ je vektorov� prostor nad $\zz$.  Pak $2$ a $3$
jsou line�rn� z�visl�, proto�e $-3\cdot 2+2\cdot 3=0$, ale $3$ nelze vyj�d�it
jako line�rn� kombinaci $2$ a naopak.
(Line�rn� kombinace jednoho vektoru je jeho
skal�rn� n�sobek.)  Pokud ale budeme $2$ a $3$ ch�pat jako prvky vektorov�ho
prostoru $\qq$ nad polem $\qq$, lze $2$ vyj�d�it snadno jako $2=2/3\cdot
3$ a podobn� $3=3/2\cdot 2$.  
Pokud ale ch�peme $2$ a $3$ jako prvky modulu $\qq$ nad okruhem $\zz$,
jsme ve stejn� situaci, jako by �lo o prvky $\zz$.
\end{examplen}


\begin{defin} Nech� $V$ je vektorov� prostor nad $\kk$ a $S \subseteq V$
libovoln� podmno�ina.  \df{Line�rn�m obalem mno�iny $S$} nazveme mno�inu
$$\lin(S)=\{a_1\cdot v_1+\dots+a_k\cdot v_k; k\in\nn, a_1,\dots,a_k\in\kk,
v_1,\dots,v_k\in S\},$$
je-li $S\neq\emptyset$, line�rn� obal pr�zdn� mno�iny
$\lin(\emptyset)$ klademe roven $\{0\}$.
Mno�inu $S$ naz�v�me \df{mno�inou gener�tor�} prostoru $V$, pokud $\lin(S)=V$.
\end{defin}

\begin{examplen} Pov�imn�te si p�edev��m, �e ka�d� 
vektorov� prostor je mno�inou gener�tor� sebe sama.\label{generuje se sam}
\end{examplen}

\begin{defin} Line�rn� nez�visl� mno�ina gener�tor� se naz�v� \df{b�ze}.
\end{defin}

\begin{remark} Pov�imn�te si, �e mno�inou gener�tor�  vektorov�ho 
prostoru $\{0\}$ je pr�zdn� mno�ina.  Ta je jist� line�rn� nez�visl�, tedy je
to b�ze $\{0\}$.
\end{remark}

\begin{examplen}
\label{v mod baze ne}
Pojem line�rn�ho obalu m� smysl i pro moduly.
Uva�me $\zz$ jako modul nad $\zz$.  Mno�ina $\{2,3\}$ je mno�inou gener�tor�.
Jin�m p��kladem je mno�ina $\{1\}$.  Zat�mco $\{1\}$ je line�rn� nez�visl�
mno�ina (a tedy "b�ze" v $\zz$), mno�ina $\{2,3\}$ je line�rn� z�visl�.
\end{examplen}

\begin{thm} Je-li mno�ina gener�tor� vektorov�ho prostoru $V$ 
kone�n�, lze z n� vybrat b�zi.
\end{thm}
\begin{proof}
D�kaz provedeme indukc� vzhledem k po�tu gener�tor�.  
Vektorov� prostor~$\{0\}$ m� pr�zdnou b�zi.
V p��kladu \ref{jeden nezav} jsme vid�li, �e 
jednoprvkov� mno�ina gener�tor� je line�rn�
nez�visl�, tedy b�ze.  

Nech� v�ta plat� pro $k-1$ gener�tor� a 
nech� $V=\lin(\{v_1,\dots,v_k\})$.  Pokud jsou gener�tory line�rn�
nez�visl�, jsme hotovi, pokud ne, lze podle p��kladu \ref{zavisly komb
ostatnich} n�kter� gener�tor, �ekn�me $v_1$, vyj�d�it jako line�rn� kombinaci 
ostatn�ch.  

Pak ale $V=\lin(\{v_2,\dots,v_k\})$ a podle induk�n�ho p�edpokladu
lze vybrat b�zi.
\end{proof}

\begin{remark} Pov�imn�te si, �e tvrzen� plat� pouze pro kone�nou mno�inu
gener�tor�.  Kdyby toto omezen� v p�edpokladech v�ty nebylo, �lo by vybrat b�zi 
ze v�ech prvk� vektorov�ho prostoru vzhledem k p��kladu \ref{generuje se sam}.
V�ta tedy ne��k�, �e m� ka�d� vektorov� prostor b�zi.  Ve skute�nosti je
existence b�ze nekone�n�rozm�rn�ho vektorov�ho prostoru ekvivalentn� s axiomem
v�b�ru.
\end{remark}

\begin{examplen} Vra�me se k p��kladu \ref{v mod baze ne}.  Z mno�iny $\{2,3\}$
nelze vybrat b�zi, proto�e ani $2$, ani $3$ negeneruj� cel� $\zz$ (nap��klad
jimi nelze vygenerovat prvek $1$).
\end{examplen}


\begin{examplen}
\label{priklady bazi}
Ch�pejme $\qq$ jako vektorov� prostor nad $\qq$.  Pak
je ka�d� jednoprvkov� 
mno�ina $\{q\in\qq; q\neq 0\}$ b�ze v $\qq$.  Obecn�ji, ch�peme-li pole 
$\kk$ jako vektorov� prostor nad $\kk$, je mno�ina $\{k\in\kk;k\neq 0\}$ jeho
baz�.

Mno�ina $\{1,x,x^2,\dots,x^n,\dots\}$ je baz� v $\qq[x]$, podobn�
$\{1,x,\dots,x^n\}$ je baz� v $\qq[x]_n$.

Nech� $O_{i,j}$ ozna�uje matici typu $k\times l$ definovanou p�edpisem
$$O_{i,j}(p,q)=\begin{cases}1\text{ pro }p=i, q=j\\0\text{ jinak}
\end{cases}$$
Pak mno�ina $\big\{O_{i,j}\/;\ i=1,\dots,k,\ j=1,\dots, l\big\}$ je baz� v
$\mat_{k \times l}(\kk)$.

\begin{exerc} Doka�te v�echna tvrzen� z p�ede�l�ho p��kladu.
\end{exerc}
\end{examplen}

\begin{examplen} 
\label{souradnice jednoznacne}
P��klad \ref{zavisly komb ostatnich} lze nahl�dnout je�t� z
jin� strany.   Nech� $\{v_1,\dots,v_k\} \subseteq V$ je line�rn� nez�visl� mno�ina
a $u\in\lin(\{v_1,\dots,v_k\})$.  Pak mno�ina $\{u,v_1,\dots,v_k\}$ je line�rn�
z�visl�, nebo� 
$$u=a_1\cdot v_1+\dots +a_k\cdot v_k$$
pro vhodn� skal�ry a tedy
$$(-1)\cdot u+a_1\cdot v_1+\dots +a_k\cdot v_k=0.$$
Nech� nyn� specieln� $\{v_1,\dots, v_n\}\subseteq V$ je b�ze 
a $u\in V$ libovoln� vektor.
Proto�e b�ze generuje $V$, plat� $u\in\lin(\{v_1,\dots,v_n\})$.  To ale
znamen�, �e $u$ je line�rn� kombinac� vektor� b�ze, tedy
$$u=a_1\cdot v_1+\dots+a_n\cdot v_n.$$
Je toto vyj�d�en� jednozna�n�?  Kdyby existovaly skal�ry $b_1,\dots,b_n\in\kk$
tak, �e
$$u=b_1\cdot v_1+\dots +b_n\cdot v_n,$$
pak by platilo
$$a_1\cdot v_1+\dots+a_n\cdot v_n-(b_1\cdot v_1+\dots +b_n\cdot v_n)=
(a_1-b_1)\cdot v_1+\dots+(a_n-b_n)\cdot v_n=0,$$
proto�e jsou ale vektory $v_1,\dots,v_n$ line�rn� nez�visl�, znamen� to, �e 
$a_i=b_i$ pro $i=1,\dots,n$.
\end{examplen}


\section{Vektorov� prostory a matice p�echodu}
\begin{notat} Z praktick�ch d�vod� budeme nad�le pracovat nikoli s b�zemi jako 
mno�inami, ale jako s uspo��dan�mi $n$-ticemi, co� se ob�as naz�v�
\df{uspo��dan� b�ze}.  My nicm�n� budeme ��kat pouze b�ze a budeme velmi voln�
nakl�dat s t�m, kdy mysl�me baz� uspo��danou a kdy neuspo��danou mno�inu a
nech�me na �ten��i, aby rozd�l vyrozum�l z kontextu.
B�ze budeme
zapisovat jako ��dky a ozna�ovat mal�mi p�smeny �eck� abecedy.
\end{notat}

\begin{defin} Nech� $\alpha=(v_1,\dots,v_n)$ je b�ze $V$ nad $\kk$ 
a $u\in V$ libovoln� vektor.
Pak podle p��kladu \ref{souradnice jednoznacne} existuj� jednozna�n� ur�en� 
skal�ry $a_1,\dots,a_n\in\kk$ tak, �e
$$u=a_1\cdot v_1+\dots +a_n\cdot v_n.$$
Tyto skal�ry budeme naz�vat \df{sou�adnice vektoru $u$ vzhledem k b�zi
$\alpha$} a zapisovat jako sloupec 
$$(u)_\alpha=\begin{pmatrix} a_1\\\vdots\\a_n
\end{pmatrix}.$$
\end{defin}

\begin{examplen}
\label{souradnice baze v sobe same}
Pov�imn�te si p�edev��m, �e pro ka�dou b�zi
$\alpha=(v_1,\dots,v_n)$ ve $V$ plat�
$$(v_1)_\alpha=\begin{pmatrix} 1\\0\\0\\\vdots\\0\\0
\end{pmatrix},\quad
(v_2)_\alpha=\begin{pmatrix} 0\\1\\0\\\vdots\\0\\0
\end{pmatrix},\quad\dots\quad
(v_{n-1})_\alpha=\begin{pmatrix} 0\\0\\0\\\vdots\\1\\0
\end{pmatrix},\quad
(v_n)_\alpha=\begin{pmatrix} 0\\0\\0\\\vdots\\0\\1
\end{pmatrix}.$$
\end{examplen}

\begin{examplen}
\label{baze v poly mod n}
M�jme dv� b�ze, nap�. $\alpha=(1,x,x^2,\dots,x^n)$ a
$\beta=(1,1+x,1+x+x^2,\dots,1+x+\dots+x^n)$ v $\qq[x]_n$.  Uv�domte si, �e
podle p��kladu \ref{souradnice jednoznacne} lze ka�d� vektor b�ze $\beta$ 
jednozna�n� vyj�d�it jako line�rn� kombinace vektor� z $\alpha$ a tak� naopak.
P�esv�d�te se o tom a sou�adnice jednotliv�ch b�zov�ch vektor� vypo�t�te.

Uva�me b�zi $\gamma=(1+x,x+x^2,x^2+x^3,\dots,x^{n-1}+x^n)$.  Jako cvi�en� 
vyj�d�ete
ka�d� z vektor� $\gamma$ v sou�adnic�ch vzhledem k $\alpha$ a $\beta$.  Jde to
i naopak?

Nem�li byste b�t p�ekvapeni, �e nikoli.  Vektor $1$ toti� nen� v
$\lin(\gamma)$, tedy $\gamma$ nen� b�ze.  Pov�imn�te si p�edev��m, �e zat�mco
$\alpha$ a $\beta$ jsou $(n+1)$-tice vektor�, je $\gamma$ jen $n$-tice.
Znamen� to tedy, �e b�ze mus� m�t stejn� po�et prvk�?
\end{examplen}

\begin{lemma}Nech� $\alpha=(v_1,\dots,v_n)$ je b�ze $V$ nad $\kk$
a $u\neq 0$ libovoln� vektor.  Pak existuje $i=1,\dots,n$ takov�, �e
$(u,v_1,\dots,v_{i-1},v_{i+1},\dots,v_n)$ je b�ze $V$.
\end{lemma}
\begin{proof} Proto�e $\alpha$ je b�ze, plat� $u\in\lin(\alpha)$, p�esn�ji
$$u=a_1\cdot v_1+\dots+a_n\cdot v_n.$$
Nech� $a_i\neq 0$, pak 
\begin{equation}v_i=a_i^{-1}(u-a_1\cdot v_1-\dots-a_{i-1}\cdot v_{i-1}
-a_{i+1}\cdot v_{i+1}-a_n\cdot v_n).\label{lin komb naopak}
\end{equation}
Nech� $w\in V$ je libovoln� vektor.  Dosad�me do 
line�rn� kombinace $$w=b_1\cdot v_1+\dots +b_n\cdot v_n$$
za $v_i$ vyj�d�en� \ref{lin komb naopak}.  T�m jsme ale vyj�d�ili 
vektor $w$ jako line�rn� kombinaci 
mno�iny $\{u,v_1,\dots,v_{i-1},v_{i+1},\dots,v_n\}$,  
tedy $\{u,v_1,\dots,v_{i-1},v_{i+1},\dots, v_n\}$ generuje $V$.

Kdyby nyn� byla $\{u,v_1,\dots,v_{i-1},v_{i+1},\dots, v_n\}$ line�rn� z�visl�
mno�ina, znamenalo by to, �e $u\in\lin(\alpha-\{v_i\})$.  Vzhledem k \ref{lin
komb naopak}
by ale pak tak� $v_i\in\lin(\alpha-\{v_i\})$ a 
$\alpha$ by nebyla b�ze, co� nen� mo�n�.

Tedy $(u,v_1,\dots,v_{i-1},v_{i+1},\dots,v_n)$ je b�ze $V$.
\end{proof}

\begin{thm}[Steinitz] Nech� $\alpha=(v_1,\dots,v_n)$ je b�ze $V$ nad $\kk$ a
$\{u_1,\dots,u_k\}$ je line�rn� nez�visl� mno�ina vektor�.  Pak $k\leq n$ a 
mezi vektory b�ze existuje takov� $(n-k)$-tice $v_{i_1},\dots,v_{i_{n-k}}$, �e
$(u_1,\dots,u_k,v_{i_1},\dots,v_{i_{n-k}})$ je b�ze $V$.
\end{thm}
\begin{proof} 
D�kaz provedeme indukc� vzhledem ke $k$ 
s vyu�it�m p�ede�l�ho lemmatu, kter� p�edstavuje prvn� krok.

Nech� $k\leq n$ a v�ta plat� pro $k-1$, tedy plat�, �e 
$(u_1,\dots,u_{k-1},v_{i_1},\dots,v_{i_{n-k+1}})$ je b�ze $V$.  Pak ale
$$
u_k=a_1\cdot u_1+\dots +a_{k-1}\cdot u_{k-1} + a_k \cdot v_{i_1}
+ \dots +a_n \cdot v_{i_{n-k+1}}.$$
Kdyby $a_j=0$ pro $j\geq k$, znamenalo by to, �e mno�ina $\{u_1,\dots,u_k\}$
nen� line�rn� nez�visl�, proto�e 
$$a_1\cdot u_1+\dots+a_{k-1}\cdot u_{k-1}+(-1)\cdot u_k=0.$$
To ale odporuje p�edpoklad�m, tedy n�kter� $a_j$ pro $j\geq k$ je nenulov�.
Nyn� m��eme stejn� jako v lemmatu nahradit 
$v_{i_{j-k}}$ vektorem $u$ a dostaneme b�zi.

Zb�v� uk�zat, �e $k$ nem��e b�t v�t�� ne� $n$.  Vzhledem k tomu, �e v $n$-t�m
induk�n�m kroku obdr��me b�zi $(u_1,\dots,u_n)$, 
musela by b�t mno�ina $\{u_1,\dots,u_k\}$
line�rn� z�visl�.
\end{proof}

\begin{cor} M�-li vektorov� prostor kone�nou b�zi, maj� v�echny jeho b�ze
stejn� po�et prvk�.
\end{cor}

\begin{defin} Nech� $V$ je vektorov� prostor.  Mohutnost b�ze nazveme
\df{dimenz� vektorov�ho prostoru $V$}.
\end{defin}

\begin{remark}  V definici b�ze stoj� proti sob� dva principy.  B�ze je mno�ina
gener�tor�, ale z�rove� je line�rn� nez�visl�.  Gener�tor� mus� b�t "dost",
line�rn� nez�visl�ch vektor� nesm� b�t "zbyte�n� mnoho".  B�ze je 
minim�ln� mno�ina gener�tor� a z�rove� maxim�ln� line�rn� nez�visl� mno�ina.
\end{remark}


\begin{examplen}
\label{radek krat sloupec}
Nyn� se vra�me k definici sou�adnic a k z�pisu baz� a
sou�adnic do ��dk� a sloupc�.  Nech� ve vektorov�m prostoru $V$ nad polem $\kk$
je b�ze $\alpha=(v_1,\dots,v_n)$ a nech� $u\in V$ je vektor se
sou�adnicemi 
$$(u)_\alpha=\begin{pmatrix} a_1\\\vdots\\a_n
\end{pmatrix}.$$
To znamen�, �e $$u=a_1\cdot v_1+\dots +a_n\cdot v_n.$$
Tuto line�rn� kombinaci budeme symbolicky zapisovat
\begin{equation}\label{baze krat souradnice}
u=\alpha\cdot(u)_\alpha
\end{equation}
a ch�pat $\cdot$ jako ur�itou operaci.  V striktn� algebraick�m smyslu to
operace nen�, nen� to ani akce nebo n�co podobn�ho.  

Pov�imn�te si zejm�na, �e 
pomoc� z�pisu \ref{baze krat souradnice} lze p�epsat line�rn� nez�vislost
vektor� b�ze $\alpha$ form�ln� v�razem
\begin{equation}
\label{lin nezav jako vektory}
\forall c\in\mat_{n \times 1}(\kk): \alpha\cdot c=0\implies c=0.
\end{equation}

Pod�vejme se na "n�soben�" v \ref{baze krat souradnice} bl��e.
Zde je situace komplikovan� t�m, �e m�ch�me
dohromady r�zn� v�ci -- vektory a skal�ry.  Zkoumejme proto jednodu��� situaci.
Nech� $R$ je libovoln� okruh.
Matic�m $\mat_{1 \times n}(R)$ ��kejme \df{$n$-��dky} a matic�m $\mat_{n
\times 1}(R)$ podobn� \df{$n$-sloupce}.  Nech� $M$ je $n$-��dek a $N$ je
$n$-sloupec, definujme jejich \df{sou�in} jako $a\in R$,
$$a=\sum_{i=1}^n \big(M(1,i)\cdot N(i,1)\big).$$
Sou�in $n$-��dku s $n$-sloupcem je tedy zobrazen�
$$\cdot:\mat_{1 \times n}(R)\times\mat_{n \times 1}(R)\to R.$$
\end{examplen}

\begin{remark} 
Nyn� se nab�z� ot�zka, pro� rad�ji nepsat b�ze i sou�adnice oboje do ��dk� (�i
sloupc�) a nedefinovat sou�in pro dva stejn� dlouh� ��dky �i dva stejn� dlouh�
sloupce.  Odpov�� bude pochopiteln� po ur�it�m zobecn�n�  sou�inu ��dk� se
sloupci.  Dal�� vt�rav� ot�zka, pro� nepsat naopak sou�adnice do ��dk� a matice
do sloupc�, bude vysv�tlena o n�co pozd�ji.
\end{remark}


\begin{examplen}
\label{definice matice prechodu}
Pov�imn�me si nyn� dvou baz�, nap�. baz� $\alpha$ a $\beta$ v
$\qq[x]_n$ z p��kladu \ref{baze v poly mod n}.  Vezm�me si po �ad� sou�adnice
vektor� z $\alpha$ vzhledem k b�zi $\beta$, tedy
$$(1)_\beta=\begin{pmatrix} 1\\0\\0\\0\\\vdots\\0
\end{pmatrix},
\quad
(x)_\beta=\begin{pmatrix} -1\\1\\0\\0\\\vdots\\0
\end{pmatrix},
\quad
(x^2)_\beta=\begin{pmatrix} 0\\-1\\1\\0\\\vdots\\0
\end{pmatrix},
\quad
\dots,
\quad
(x^n)_\beta=\begin{pmatrix} 0\\0\\\vdots\\0\\-1\\1
\end{pmatrix}.$$
Pokud postupn� aplikujeme na b�zi $\beta$ a jednotliv� sloupce sou�in \ref{baze
krat souradnice}, dostaneme vektory b�ze $\alpha$.

Sestavme nyn� z t�chto sloupc� �tvercovou matici a definujme dal��
sou�in, op�t obecn� pro matice nad okruhem $R$.  
Nech� $M$ je $n$-��dek a $N\in\mat_{n \times n}(R)$, jejich
sou�inem nazveme $n$-��dek $P$ spl�uj�c� pro ka�d� $i=1,\dots,n$ vztah
$$P(1,i)=M\cdot N(-,i).$$
Symbolem $N(-,i)$ zde mysl�me $i$-t� sloupec $N$ a sou�in na prav� stran�
rovnosti je tedy sou�in $n$-��dku s $n$-sloupcem.  Poznamenejme, �e podobn�
budeme symbolem $X(i,-)$ ozna�ovat $i$-t� ��dek matice $X$, podtr��tko zde
znamen� pr�zdn� m�sto, do n�ho� lze dosazovat, tedy form�ln� je
$$N(-,i):\{1,\dots,n\}\to R,\qquad \Big(N(-,i)\Big)(j)=N(j,i).$$
Pov�imn�te si, �e sou�in $n$-��dku s matic� $n \times n$ odpov�d� tomu, jak
jsme vyj�d�ili b�zi $\alpha$ z b�ze $\beta$.  Tam jsme vlastn� n�sobili takto:
$$\alpha=\beta\cdot \Big(\begin{array}{c|c|c|c}
(1)_\beta&(x)_\beta&\dots&(x^n)_\beta
\end{array}\Big),$$
p�i�em� symbolem vpravo rozum�me matici $n \times n$ vzniklou tak, �e sloupce
nap��eme vedle sebe, tedy
$$\Big(\begin{array}{c|c|c|c}
(1)_\beta&(x)_\beta&\dots&(x^n)_\beta
\end{array}\Big)(-,i)=(x^{i-1})_\beta.$$

Pov�imn�me si nyn� velmi d�le�it� v�ci.  Nech� $u\in\qq[x]_n$.  Pak
\begin{equation}\label{zmena souradnic}
u=\alpha\cdot(u)_\alpha=
\bigg(\beta\cdot \Big(\begin{array}{c|c|c|c}
(1)_\beta&(x)_\beta&\dots&(x^n)_\beta
\end{array}\Big)\bigg)\cdot(u)_\alpha.
\end{equation}
Definujme dal�� sou�in, velmi podobn� jako p�ede�l�.  Nech� $M$ je matice $n
\times n$ a $N$ je $n$-sloupec.  Jejich sou�inem nazveme $n$-sloupec $P$
spl�uj�c� pro $i=1,\dots,n$
$$P(i,1)=M(i,-)\cdot N.$$
Pak lze v�raz \ref{zmena souradnic} p�epsat jako
$$u=\alpha\cdot(u)_\alpha=
\beta
\cdot\bigg( \Big(\begin{array}{c|c|c|c}
(1)_\beta&(x)_\beta&\dots&(x^n)_\beta
\end{array}\Big)\cdot(u)_\alpha\bigg)$$
a vzhledem k jednozna�nosti sou�adnic vzhledem k dan� b�zi to znamen�, �e
$$(u)_\beta=\Big(\begin{array}{c|c|c|c}
(1)_\beta&(x)_\beta&\dots&(x^n)_\beta
\end{array}\Big)\cdot (u)_\alpha$$
\end{examplen}

\begin{remark} Poznamenejme, �e jsme v p�edchoz�m p��kladu n�kolikr�t
aplikovali nov� definovan� sou�iny v situac�ch, kdy ��dkem nebyl $n$-��dek, ale
uspo��dan� b�ze.  V t�chto p��padech jsme v�ak k sou�inu p�istupovali jako k
v�razu  \ref{baze krat souradnice}.
\end{remark}

\begin{defin} Nech� $\alpha=(v_1,\dots,v_n)$ a $\beta$ jsou b�ze ve vektorov�m
prostoru $V$.  �tvercovou matici $(\id)_{\beta\alpha}$ spl�uj�c�
$$(\id)_{\beta\alpha}(-,i)=(v_i)_\beta,$$
tedy
$$(\id)_{\beta\alpha}=
\big(\begin{array}{c|c|c|c}(v_1)_\beta&(v_2)_\beta&\dots&(v_n)_\beta
\end{array}\big)$$
naz�v�me \df{matice p�echodu od b�ze $\alpha$ k b�zi $\beta$}.
\end{defin}

\begin{remark} Uv�domte si, �e
vzhledem k jednozna�nosti sou�adnic je tak� matice p�echodu ur�ena jednozna�n�.
Ozna�en� matice p�echodu bude jasn� pozd�ji, pov�imn�te si
obr�cen�ho po�ad� baz� v indexu $(\id)_{\beta\alpha}$.
\end{remark}

\begin{examplen}
\label{soucin ctvercovych matic}
Nyn� uk�eme motivaci pro definov�n� dal��ho sou�inu.  Nech�
$\alpha$, $\beta$ a $\gamma$ jsou t�i b�ze ve $V$.  Nov� sou�in bude definov�n
tak, �e matice p�echodu od $\alpha$ ke $\gamma$ bude sou�inem matice p�echodu
od $\beta$ ke $\gamma$ s matic� p�echodu od $\alpha$ k $\beta$.

Nech� tedy $M$ a $N$ jsou matice $n \times n$.  Jejich sou�inem nazveme matici
$P$ typu $n \times n$ spl�uj�c� pro $i=1,\dots,n$ a $j=1,\dots, n$ vztah
$$P(i,j)=M(i,-)\cdot N(-,j),$$
tedy v $i$-t�m ��dku a $j$-t�m sloupci sou�inu je sou�in $i$-t�ho ��dku $M$ s
$j$-t�m sloupcem matice $N$.

Vra�me se k motivaci.  V�me, �e pro ka�d� $u\in V$ je
\begin{align*} 
u&=\alpha\cdot(u)_\alpha=\gamma\cdot(\id)_{\gamma\alpha}\cdot(u)_\alpha.
\intertext{Z�rove� ale}
u&=\alpha\cdot (u)_\alpha=\beta\cdot (\id)_{\beta\alpha}(u)_\alpha=
\gamma\cdot(\id)_{\gamma\beta}\cdot(\id)_{\beta\alpha}\cdot(u)_\alpha
\end{align*}
Proto�e matice p�echodu je d�na jednozna�n�, mus� platit
$$(\id)_{\gamma\alpha}=(\id)_{\gamma\beta}\cdot(\id)_{\beta\alpha}.$$
Sou�in na prav� stran� je pak pr�v� sou�in �tvercov�ch matic definovan� v��e.
\end{examplen}

\begin{remark} Uv�domte si, �e sou�in �tvercov�ch matic je operace z
algebraick�ho hlediska, nebo� je to zobrazen�
$$\cdot:\mat_{n \times n}(R)\times\mat_{n \times n}(R)\to
\mat_{n \times n }(R).$$
\end{remark}

\begin{examplen}
\label{asociativita soucinu matic}
Sou�in matic $n \times n$ je asociativn� operace, nebo�
pro ka�d� $M,N,P\in\mat_{n \times n}(R)$ je
$$\Big((M\cdot N)\cdot P\Big)(i,j)=
\big(M\cdot N\big)(i,-)\cdot P(-,j)=
M(i,-)\cdot N\cdot P(-,j)$$
$$\Big(M\cdot (N\cdot P)\Big)(i,j)=
M(i,-)\cdot\big( N\cdot P\big)(-,j)=
M(i,-)\cdot N\cdot P(-,j)$$
Ujist�te se, �e dob�e rozum�te v��e uveden�mu z�pisu.  Uv�domte si tak�, �e
ze z�pisu plyne, �e $i$-t� ��dek sou�inu matic $M$ a $N$ je sou�inem 
$i$-t�ho ��dku $M$ s matic� $N$.  Promyslete si, jak tento fakt
plyne z definice n�soben� $n$-��dku matic� $n \times n$ (viz 
p��klad~\ref{definice matice prechodu}).  D�le si rozmyslete
podobn� fakt pro sloupce.
\end{examplen}

\begin{remark} V pozn�mce k p��kladu \ref{radek krat sloupec} jsme se zam��leli
nad t�m, pro� nedefinovat sou�in $n$-��dku s $n$-��dkem �i naopak $n$-sloupce s
$n$-sloupcem.  Nyn�, kdy� zn�te sou�in �tvercov�ch matic, se m��ete zamyslet,
s jak�mi obt��emi by se definoval sou�in matic, pokud bychom cht�li vyj�t nap�.
od sou�inu $n$-��dk�.  Uva�me takov� sou�in "po ��dc�ch".
P�edev��m v�bec nen� jasn�, kter� prvek ve v�sledn� matici kam ps�t, na rozd�l
od sou�inu, kter� jsme definovali my.  P�ipus�me ale, �e bychom zavedli n�jakou
konvenci, nap�. takovou, �e v $i$-t�m ��dku a $j$-t�m sloupci sou�inu je sou�in
$i$-t�ho ��dku s $j$-t�m ��dkem, tedy nap�. u matic $2 \times 2$ dostaneme
$$\begin{pmatrix} a&b\\c&d
\end{pmatrix}\cdot \begin{pmatrix} e&f\\g&h
\end{pmatrix}=
\begin{pmatrix} ae+bf&ag+bh\\ce+df&cg+dh
\end{pmatrix}.$$  Takov� sou�in ale nebude asociativn�!
Vyzkou�ejte 
$$\begin{pmatrix} a&b\\c&d
\end{pmatrix}\cdot \begin{pmatrix} e&f\\g&h
\end{pmatrix}\cdot \begin{pmatrix} i&j\\k&l
\end{pmatrix}$$
a okam�it� vid�te, �e v prvn�m ��dku prvn�m sloupci v�sledn� matice je p�i
jednom uz�vorkov�n� $aei+bfi+agj+bhj$ a p�i druh�m $aei+afj+bek+bfl$.

Promyslete si dob�e, �e asociativitu nez�sk�te ani p�i jin� konvenci uspo��d�n�
prvk�.  Form�ln� d�kaz tohoto tvrzen� by byl zdlouhav� a nebudeme jej
uv�d�t.
\end{remark}

\begin{exerc} Ov��te, �e matice $E_n$ typu $n \times n$ definovan� p�edpisem
$$E_n(i,j)=\begin{cases}1\text{ pro } i=j\\0\text{ jinak,}
\end{cases}$$
je jednotkov�m prvkem vzhledem k n�soben� matic $n \times n$.
\end{exerc}

\begin{remark} Z
 p��kladu
\ref{souradnice baze v sobe same} plyne, �e
pro ka�dou b�zi $\alpha$ ve vektorov�m
prostoru $V$ dimenze $n$ je $(\id)_{\alpha\alpha}=E_n$.
\end{remark}

\begin{examplen}
\label{distrib nasobeni matic}
Vra�me se na chv�li k n�soben� ��dk� sloupci.
N�soben� $n$-��dku $n$-sloupcem je zleva i zprava distributivn� operace, co�
plyne p��mo z distributivity n�soben� v $R$.  P�esn�ji, pro libovoln� $M,N\in\mat_{1
\times n}(R)$ a $P,Q\in\mat_{n \times 1}(R)$ plat�
\begin{align*} M\cdot(P+Q)&=\sum_{i=1}^n M(1,i)\cdot\big(P(i,1)+Q(i,1)\big)\\
&=\sum_{i=1}^n \big(M(1,i)\cdot P(i,1)+M(1,i)\cdot Q(i,1)\big)=
M\cdot P+M\cdot Q
\intertext{a podobn�}
(M+N)\cdot P&=\sum_{i=1}^n \big(M(1,i)+N(1,i)\big)\cdot P(i,1)\\
&=\sum_{i=1}^n \big(M(1,i)\cdot P(i,1)+N(1,i)\cdot P(i,1)\big)=
M\cdot P+N\cdot P
\end{align*}
P�edev��m z toho plyne, �e pro libovolnou line�rn� kombinaci
vektor� $v_1,\dots,v_k\in V$ a libovolnou b�zi
$\alpha$ ve $V$ plat�
$$ (c_1\cdot v_1+\dots +c_k\cdot v_k)_\alpha=
c_1\cdot (v)_1+\dots+c_k\cdot(v)_k.$$
Nech� nyn� $A,B,C\in\mat_{n \times n}(R)$.
Proto�e sou�in �tvercov�ch matic je definov�n tak, �e v $i$-t�m ��dku a
$j$-t�m sloupci matice $A\cdot B$ je sou�in $i$-t�ho sloupce $A$ s $j$-t�m
sloupcem $B$, plyne z distributivity n�soben� ��dk� sloupci tak� 
\begin{align*} A\cdot(B+C)&=A\cdot B+A\cdot C\\
(A+B)\cdot C&=A\cdot C+B\cdot C.
\end{align*}
\end{examplen}

\begin{cor}
Z �vah v p�edchoz�ch dvou p��kladech a z p�edchoz�ho cvi�en� vypl�v�, �e
$(\mat_{n \times n}(R),+,\cdot)$ tvo�� okruh, p�i�em�
nulov� matice $0_n$ je nulov� prvek a jednotkov� matice $E_n$ je jednotkov�
prvek.
\end{cor}

\begin{remark} Zd�razn�me, �e tento okruh je podstatn� v�znamn�j�� ne� v��e
uveden� okruh
$(\mat_{n \times n}(R),+,\ast)$ s n�soben�m po slo�k�ch, jeho� zaveden�
nem�lo jin� smysl ne� ilustrovat na p��kladech pojem okruhu.
\end{remark}

\begin{examplen}
\label{definice GLn}
Nech� $V$ je vektorov� prostor nad polem $\kk$ dimenze $n$
Nech� $\alpha$, $\beta$ jsou libovoln� b�ze.  Pak vzhledem k p��kladu
\ref{souradnice baze v sobe same} a z jednozna�nosti matice p�echodu plyne
$$(\id)_{\beta\alpha}\cdot (\id)_{\alpha\beta}=(\id)_{\beta\beta}=E_n$$
a tedy $(\id)_{\beta\alpha}$ je inverzn� prvek k $(\id)_{\alpha\beta}$ vzhledem
k n�soben� matic.  Specieln� to znamen�, �e ka�d� matice p�echodu m� inverzn�
prvek.

Tedy mno�ina matic p�echodu tvo�� grupu vzhledem k n�soben�, naz�v� se
\df{obecn� line�rn� grupa} a zna��me ji $GL(n,\kk)$.  Tato grupa
nen�
komutativn�, nap�.
$$
\begin{pmatrix} 1&2\\3&4
\end{pmatrix}
\cdot \begin{pmatrix} 1&1\\1&2
\end{pmatrix}= \begin{pmatrix} 3&5\\7&11
\end{pmatrix}\neq
\begin{pmatrix} 4&6\\7&10
\end{pmatrix}=
\begin{pmatrix} 1&1\\1&2
\end{pmatrix}\cdot
\begin{pmatrix} 1&2\\3&4
\end{pmatrix}
$$
To p�edev��m znamen�, �e $(\mat_{n \times n}(\kk),+,\cdot)$ nen� komutativn�
okruh a �e obecn�ji pro libovoln� $R$ okruh $(\mat_{n \times n}(R),+,\cdot)$ 
nen� komutativn�.

Jak ale uk�zat, �e v��e uveden� matice jsou skute�n� maticemi
p�echodu?  Existuj� v�bec n�jak� matice typu $n \times n$, kter� by nebyly
maticemi p�echodu?

P�edev��m lze uk�zat, �e pro libovoln� $n$ nem� nulov� matice $0_n$ inverzn�
prvek.  Skute�n�, pro ka�d� $M\in\mat_{n \times n}(\kk)$ je 
$$0_n\cdot A=A\cdot 0_n=0_n.$$ 
Proto�e u� v�me, �e ka�d� matice p�echodu m� inverzn� prvek, nem��e b�t
nulov� matice matic� p�echodu.
\end{examplen}

\begin{remark} 
Podobn� jako $GL(n,\kk)$ v $(\mat_{n \times n}(\kk),+,\cdot)$ je
v ka�d�m okruhu mno�ina prvk�, kter� maj� inverzi (tzv. \df{invertibiln�ch
prvk�}) grupou vzhledem k n�soben�.  
P�ipome�me, �e v
netrivi�ln�m poli je jedin�m prvkem bez inverze nulov� prvek.  Naopak nap�. v
$\zz$ jsou invertibiln�mi prvky pouze $1$ a $-1$.  V dal��m textu budeme
postupn� sm��ovat k tomu, zda je invertibiln�ch matic (tedy matic p�echodu) sp��e
"m�lo" podobn� jako v $\zz$, nebo "v�t�ina" podobn� jako v poli.
\end{remark}

\begin{exerc} Nech� $M$ a $N$ jsou matice p�echodu.  Doka�te, �e pak 
$$(M\cdot N)^{-1}=N^{-1}\cdot M^{-1}.$$
\end{exerc}

\begin{examplen}
\label{gauss}
Bu� $\alpha=(v_1,\dots,v_n)$ b�ze $V$.  Ozna�me 
\begin{align*} 
\beta&=(v_1,\dots,v_{i-1}, v_j, v_{i+1},\dots,v_{j-1},v_i,v_{j+1},\dots,v_n),\\
\gamma&=(v_1,\dots,v_{i-1},v_i+v_j,v_{i+1},\dots,v_n),\\
\delta&=(v_1,\dots,v_{i-1},a\cdot v_i,v_{i+1},\dots,v_n), \text{ kde } a\neq 0.
\end{align*}
Z�ejm� $\beta,\gamma$ a $\delta$ jsou b�ze.  Pak
\begin{align*} 
(\id)_{\beta\alpha}(-,k)&=
\begin{cases} E_n(-,k)\text{ pro }k\neq i,j\\
E_n(-,i)\text{ pro } k=j\\
E_n(-,j)\text{ pro } k=i
\end{cases}\\
(\id)_{\gamma\alpha}(-,k)&=
\begin{cases} E_n(-,k)\text{ pro }k\neq i\\
E_n(-,i)+E_n(-,j)\text{ pro } k=i
\end{cases}\\
(\id)_{\delta\alpha}(-,k)&=
\begin{cases} E_n(-,k)\text{ pro }k\neq i\\
a\cdot E_n(-,i)\text{ pro } k=i
\end{cases}
\end{align*}
Pov�imn�te si, jak se li�� $\beta$, $\gamma$ a $\delta$ od $\alpha$.  Uv�domte
si, �e  
\begin{align*} (\id)_{\alpha\beta}&=(\id)_{\beta\alpha}\\
(\id)_{\alpha\gamma}(-,k)&=
\begin{cases} E_n(-,k)\text{ pro }k\neq i\\
E_n(-,i)-E_n(-,j)\text{ pro } k=i
\end{cases}\\
(\id)_{\alpha\delta}(-,k)&=
\begin{cases} E_n(-,k)\text{ pro }k\neq i\\
a^{-1}\cdot E_n(-,i)\text{ pro } k=i
\end{cases}
\end{align*}
Pov�imn�te si, �e pro ka�dou matici p�echodu $M$ se $(\id)_{\beta\alpha}\cdot M$
li�� od $M$ t�m, �e je vym�n�n $i$-t� a $j$-t� ��dek,
$M\cdot(\id)_{\beta\alpha}$ se od $M$ li�� t�m, �e je vym�n�n $i$-t� a $j$-t�
sloupec.  Podobn� $(\id)_{\gamma\alpha}\cdot M$ je shodn� s $M$ a� na to, �e
k $i$-t�mu ��dku je p�i�ten $j$-t�, $(\id)_{\delta\alpha}\cdot M$ m� v $i$-t�m
��dku $a$-n�sobek $i$-t�ho ��dku $M$, p�i n�soben� $(\id)_{\gamma\alpha}$ a
$(\id)_{\delta\alpha}$ zprava podobn� pro sloupce.

Matic�m $(\id)_{\beta\alpha}$, $(\id)_{\gamma\alpha}$ a$(\id)_{\delta\alpha}$
��k�me \df{matice element�rn�ch �prav} nebo \df{element�rn� matice}.

Je snadn� odvodit algoritmus (a p�edev��m dok�zat jeho kone�nost), 
p�i n�m� budeme matici p�echodu  $M$ postupn�
n�sobit zleva vhodn�mi element�rn�mi maticemi tak, �e
nakonec dostaneme jednotkovou matici $E_n$, p�esn�ji
$$E_n=U_s\cdot U_{s-1}\cdot \dots \cdot U_1\cdot M,$$
kde $U_k$ ozna�uje p��slu�nou element�rn� matici.
Pak ale 
$$M^{-1}=U_s\cdot U_{s-1}\cdot \dots \cdot U_1$$
a tedy v��e uveden� algoritmus je vlastn� efektivn�m algoritmem na v�po�et
inverzn� matice.  Tento algoritmus naz�v�me \df{Gauss�v elimina�n� algoritmus}.
\end{examplen}

\begin{remark} 
Uv�domte si, �e podle p�edchoz�ho cvi�en� a p��kladu je
$$M=U_1^{-1}\cdot\dots\cdot U_s^{-1},$$
tedy ka�d� matice p�echodu je sou�inem element�rn�ch matic, nebo� inverzn�
matice k element�rn�m matic�m jsou op�t element�rn� matice -- u matic tvaru
$(\id)_{\alpha\beta}$ a $(\id)_{\alpha\delta}$ je to z�ejm�, matici
$(\id)_{\alpha\gamma}$ dostaneme vyn�soben�m element�rn� matice pro p�i�ten�
$j$-t�ho k $i$-t�mu ��dku matic� pro n�soben� $j$-t�ho ��dku skal�rem $-1$.
\end{remark}

\begin{exerc} Formulujte p�esn� algoritmus Gaussovy eliminace
a doka�te jeho kone�nost.
\end{exerc}

\begin{examplen}
\label{primy vypocet regularity}
Uva�me v $\qq[x]_1$ b�zi $\varepsilon=(1,x)$. 
Prozkoum�me, zda je matice
$$M=\begin{pmatrix} 1&2\\3&4
\end{pmatrix}$$
matic� p�echodu.  Proto�e
$$(1,x)\cdot \begin{pmatrix} 1&2\\3&4
\end{pmatrix}=(1+3x,2+4x),$$
ov���me, zda vektory $1+3x$ a $2+4x$ jsou line�rn� nez�visl�.  P�edpokl�dejme,
�e
$$a\cdot(1+3x)+b\cdot(2+4x)=0,$$
pak 
$a+2b=0$ a $3a+4b=0$
porovn�n�m koeficient� u stejn�ch mocnin.  To je ale mo�n� jedin� tehdy,
pokud $a=b=0$ a tedy $1+3x$ a $2+4x$ jsou line�rn� nez�visl� vektory.  Proto�e
je jich stejn� po�et jako vektor� b�ze $(1,x)$, je tak� $\alpha=(1+3x,2+4x)$ b�ze v
$\qq[x]_1$ a tedy matice~$M$ je matic� p�echodu, $M=(\id)_{\alpha\varepsilon}$.  
Jej� inverz� je pak matice
p�echodu od $\alpha$ k $\varepsilon$, tedy matice slo�en� ze sloupc� sou�adnic
$(1)_\alpha$ a $(x)_\alpha$, kter� z�sk�me z rovnic
\begin{align*} 1&=a\cdot(1+3x)+b\cdot(2+4x)\\x&=c\cdot(1+3x)+d\cdot(2+4x)
\end{align*} 
Dost�v�me pak $$(1)_\alpha=\begin{pmatrix} a\\b
\end{pmatrix},(x)_\alpha=\begin{pmatrix} c\\d
\end{pmatrix},
(\id)_{\varepsilon\alpha}=\begin{pmatrix} a&c\\b&d
\end{pmatrix}$$
a ov��te v�po�tem, �e v�sledn� matice p�echodu je skute�n� inverzn� k $M$.
\end{examplen}

\begin{remark} 
Promyslete si, jak jsme v p�edchoz�m p��kladu dok�zali, �e
matice $M$ je matic� p�echodu.  J�drem d�kazu je to, zda jsou vektory
uspo��dan� $n$-tice $\varepsilon\cdot M$ line�rn� nez�visl�.  To je v jist�m
smyslu vn�j�� krit�rium, proto�e zkoum�me, jak se matice  chov�.  N�sleduj�c�
tvrzen� popisuje vnit�n� krit�rium, zda je matice $M$ matic� p�echodu, tedy
krit�rium vyu��vaj�c� jen prvk� matice $M$. 
\end{remark}


\begin{prop} 
Nech� $\alpha=(v_1,\dots,v_n)$ je b�ze ve $V$ nad $\kk$ a $M\in\mat_{n \times
n}(\kk)$.  Pak uspo��dan� $n$-tice vektor� $\alpha\cdot M$ je line�rn�
nez�visl� ve $V$ pr�v� tehdy, kdy� jsou sloupce matice $M$ line�rn� 
nez�visl� jako vektory v $\mat_{n \times 1}(\kk)$.
\end{prop}

\begin{remark} Uv�domte si dob�e, �e line�rn� nez�vislost sloupc� $M$
znamen�, �e ka�d� line�rn� kombinace
$$c_1\cdot M(-,1)+\dots +c_n\cdot M(-,n)=0$$
je trivi�ln�, tedy $c_1=\dots=c_n=0$.  Zapi�me form�ln� skal�ry $c_1,\dots,c_n$
jako $n$-sloupec $c$, tedy $c(i,1)=c_i$ pro $i=1,\dots,n$.  Proto�e n�soben� v
$\kk$ je komutativn�, lze p�epsat p�edchoz� v�raz jako
$$M(-,1)\cdot c(1,1)+\dots+M(-,n)\cdot c(n,1)=M\cdot c.$$
To je mimochodem jeden z d�vod�, pro� jsme po�adovali v definici pole
komutativitu (tedy komutativitu n�soben�).  Uv�domte si tak�, �e jsme �pln� stejnou
zm�nu z�psiu provedli ji� ve v�razu \ref{baze krat souradnice}.

\smallskip
M��eme tedy ��ci, �e sloupce matice $M$ jsou line�rn� nez�visl� pr�v� tehdy, 
pokud jedin� $n$-sloupec $c$ spl�uj�c� $M\cdot c=0$ je nulov�.
\end{remark}

\smallskip  Nyn� dok�eme tvrzen�.

\begin{proof}
K d�kazu vy�ijeme z�pis line�rn� nez�vislosti v \ref{lin nezav jako vektory}.
P�edpokl�dejme, �e $\alpha\cdot M$ je line�rn� nez�visl�.  Nech� pro $n$-sloupec
$c$ plat� $M\cdot c=0$.  Pak ale $\alpha\cdot M\cdot c=0$ a tedy $c$ je
line�rn� kombinace, kter� nuluje $\alpha\cdot M$.  Z line�rn� nez�vislosti
$\alpha\cdot M$ je potom $c=0$ a tedy $M$ m� line�rn� nez�visl� sloupce.  

Naopak, nech� $M$ m� line�rn� nez�visl� sloupce
a $(\alpha\cdot M)\cdot c=0$ pro n�jak� $n$-sloupec $c$.  Pak ale z line�rn�
nez�vislosti $\alpha$ plyne, �e $M\cdot c=0$ a z line�rn� nez�vislosti sloupc�
$M$ dost�v�me $c=0$, tedy $\alpha\cdot M$ je line�rn� nez�visl�.  T�m je d�kaz ukon�en.
\end{proof}

\begin{examplen}
\label{sloupce E_n}
Pov�imn�me si nyn� prostoru $n$-sloupc� nad $\kk$.  Nen� t�k�
ov��it, �e sloupce jednotkov� matice $E_n$ tvo�� b�zi tohoto prostoru, ozna�me
ji $\varepsilon$.  P�esn�ji,
$$\varepsilon=\big(E_n(-,1),\dots,E_n(-,n)\big).$$
V t�to
b�zi je $i$-t� sou�adnice vektoru $c$ rovna prvku $c(i,1)$, tedy $i$-t�mu prvku
sloupce.  To m��e b�t siln� matouc�, proto�e p�i nevhodn�m z�pisu m��e b�t
probl�m odli�it vektor sou�adnic od vektoru samotn�ho.  Skute�n�,
$(c)_\varepsilon=c$.

Uva�me nyn� $n$-sloupec $d$, kter� m� v�echny prvky $d(i,1),\dots,d(n,1)$ rovny 
nule.  Uv�domte si, �e pak $d\in\lin\big(E_n(-,1),\dots,E_n(-,i-1)\big)$.  
Tedy matice, kter� m� v $i$-t�m sloupci na $i$-t�m m�st� nenulov� prvek a d�le
nuly, m� line�rn� nez�visl� sloupce.
\end{examplen}


\begin{thebibliography}{xxx}
\bibitem[H]{hefferon} Hefferon, J., Linear Algebra,
kniha dostupn� na webov� str�nce autora\\
{\tt http://joshua.smcvt.edu/pub/hefferon/book/book.pdf}
\bibitem[S]{slovak} Slov�k, J., Line�rn� algebra,
skripta dostupn� na webov� str�nce autora\\
{\tt http://www.math.muni.cz/\~{}slovak}
\end{thebibliography}



\vfill
\hrule\medskip
\noindent{\footnotesize
Tento text podl�h� licenci {\em Letm�ho �vodu\/}: jeho kop�rov�n�, zm�ny a
�pravy �i publikov�n� pod vlastn�m jm�nem jsou dovoleny.  Nen� dovoleno do
vyti�t�n�ho textu balit masn� v�robky.  O chyb�ch �i nedostatc�ch
ve verzi textu na na�ich  str�nk�ch pros�m informujte na adresu {\tt
elvis@spiknuti.org}.}

\end{document}
