\chyph

\hoffset=-1cm \voffset=-1.2cm \hsize=18cm

\ifx\pdfoutput\undefined \else
\pdfpagewidth=21cm
\pdfpageheight=15cm
\fi


\headline={\setfonts[/10]\rm\hfill [\the\pageno]}
\footline={}

\input ofs [a35]  %\def\fomenc{CM}  

%\showfonts \end
%\displayfontmessages
\setfonts[NewCentury/17]  \setmath[17/12/8]  
\baselineskip=22pt \normalbaselineskip=\baselineskip

\message{\fontname\tenit}

\medskipamount=9pt
\let\ms=\medskip

\parskip=\medskipamount

\def\n#1\par{\vfill\break}

\def\g#1\par{{\null \vskip-31pt \baselineskip=30pt\setfonts[/23]\bf #1\par}\medskip}
\def\gg#1\par{{\setfonts[/55]\bf #1}\medskip}
\def\hb{\hfil\break}

\def\emerge{{\emergencystretch=2em\par}}

\parindent=0pt

\catcode`\*=13 
\def* {\par \hangindent=15pt \hangafter=1 
   \noindent \hbox to\hangindent {$\bullet$\hss}}

\let\em=\it

\def\C{{\bf C}}
\def\R{{\bf R}}
\def\Q{{\bf Q}}
\def\a{{A}}
\def\A{{\bf A}}
\def\B{{\bf B}}
\def\D{{\bf D}}
\def\E{{\bf E}}
\def\P{{\bf P}}
\def\L{{\bf L}}
\def\U{{\bf U}}
\def\X{{\bf X}}
\def\ker{\mathop{\rm Ker}}
\def\st{\mathop{\rm St}}
\def\hod{\mathop{\rm hod}}
\def\vecc #1_#2{\vec#1_1, \vec#1_2, \ldots, \vec#1_{#2}}
\def\lob<#1>{\langle #1\rangle}

% ===============================================================

\vglue 2cm

\gg Determinant

\bigskip\bigskip

* je ��slo jist�m zp�sobem charakterizuj�c� �tvercovou matici

* $\det\A=0$ pro singul�rn� matici, $\det\A\not=0$ pro regul�rn� matici

* pou��v� se p�i �e�en� line�rn�ch soustav

* \dots\ a v mnoha dal��ch aplikac�ch

\n ---------------------------------------------------------------

\g Definice determinantu

{\bf Definice:} Nech� $\A=(a_{i,j})\in\R^{n,n}$ je �tvercov� matice. ��slo
$$
  \sum_{\hbox{\setfonts[/mag.7] permutace}\ \pi=(i_1,i_2,\ldots,i_n)} 
  \hskip-3em{\rm sgn}\,\pi\cdot a_{1,i_1}\,a_{2,i_2}\cdots\,a_{n,i_n}
$$
naz�v�me {\em determinantem matice $\A$} a zna��me je $\det\A$.

{\bf Pozn�mka:} Abychom tomu vzorci porozumn�li a dok�zali z n�j
odvodit z�kladn� vlastnosti determinant�, pot�ebujeme si p�ipomenout
vlastnosti permutac�\dots


\n ---------------------------------------------------------------


\g Permutace

Permutace $n$ prvk� je uspo��dan� $n$-tice ��sel z mno�iny\hb
$\{1,2,\ldots,n\}$, p�itom k�d� ��slo je v $n$-tici zastoupeno pr�v�
jednou. 

P��klad: $(3,1,2,5,4)$ je permutace p�ti prvk�.

$(i_1,i_2,\ldots,i_n)$ je permutace z $n$ prvk�, pokud
$i_j\in\{1,2,\ldots,n\}$ a $i_j\not=i_k$ pro $j\not=k$.

{\bf Jin� pohled:} Permutace 
je bijektivn� zobrazen� na $\{1,2,\ldots,n\}$.

Vztah mezi t�mito pohledy: Je-li d�na $n$-tice $(i_1,i_2,\ldots,i_n)$, 
pak je d�no zobrazen� $z:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ p�edpisem
$z(j)=i_j$. Je-li d�no zobrazen� $z$, pak lze sestrojit $n$-tici
$(z(1),z(2),\ldots,z(n))$.


\n -----------------------------------------------------------------

\g Permutace, vlastnosti

* Skl�d�n�m permutac� (jako zobrazen�) dost�v�me permutaci.

* Generick� (jednotkov�) permutace je $(1,2,\ldots,n)$.

* Ka�d� permutace m� svou inverzn� permutaci.

* Po�et permutac� $n$ prvk� je $n!\,$.

\n -----------------------------------------------------------------

\g Znam�nko permutace

{\em inverze v permutaci} $(i_1,i_2,\ldots,i_n)$ je v�skyt jevu:

\hfil $i_j>i_k$ a sou�asn� $j<k$.

P��klad: inverze permutace $(3,1,2,5,4)$ jsem vyzna�il pomoc�
oblou�k�:
$$
  \let\braceru=\relax \let\bracelu=\relax 
  \def\o#1{\setbox0=
    \hbox{$\kern2pt\overbrace{\kern-2pt#1\kern-2pt}\kern2pt$}\ht0=2.1ex\box0}
  \def\to#1{\hbox{#1\rlap{\t{}}}}
  %
  (\o{\o{3,1},2},\o{5,4})
%  (1,2,3),\quad (1,\o{3,2}), \quad
%  (\o{2,1},3),\quad (\o{2,\o{3,1}}),\quad (\o{\o{3,1},2}),
%  \quad (\o{\o{3,2},\kern-8pt\o{\kern8pt 1}}). 
$$
Tato permutace m� t�i inverze.

{\bf Definice:} M�-li permutace $\pi$ sud� po�et inverz�, je 
${\rm sgn}\,\pi=+1$,\hb
m�-li $\pi$ lich� po�et inverz�, je ${\rm sgn}\,\pi=-1$.\hb 
��slu
${\rm sgn}\,\pi$ ��k�me {\em znam�nko permutace}.

P��klad: ${\rm sgn} (3,1,2,5,4) = -1$.\hb
Znam�nko generick� permutace je $+1$.

Cvi�en�: jak� znam�nko m� permutace $(n,n-1,\ldots,3,2,1)$? 


\n -------------------------------------------------------

\g P�echod sud� -- lich�

Prohozen� dvou prvk� v permutaci zm�n� znam�nko permutace.

D�kaz: V n�sleduj�c� permutaci prohod�m prvky $x$ a $y$:
$$
  (\ldots\hbox{prvky vlevo}\ldots,x,\ldots
    \hbox{prvky uvnit�}\ldots,y,\ldots\hbox{prvky vpravo}\ldots)
$$
Inverze, kter� nenavazuj� na prvek $x$ nebo $y$ z�st�vaj� nezm�n�ny.
Inverze mezi prvky vlevo a $x$ nebo $y$ z�st�vaj� nezm�n�ny. Inverze
mezi $x$ nebo $y$ a prvky vpravo z�st�vaj� nezm�n�ny. Inverze mezi $x$
nebo $y$ a prvky uvnit� po dvou vznikaj� nebo zanikaj� nebo se
nem�n�. Inverze mezi $x$ a $y$ vznikne nebo zanikne.

{\bf D�sledek:} Znam�nko permutace pozn�me podle po�tu {\em transpozic\/}
(jednoho prohozen� dvou prvk�), kter� je pot�eba na permutaci prov�st,
aby byla p�evedena na generickou permutaci.

\n ---------------------------------------------------------

\g N�vrat k definici deterinantu

{\bf Definice:} Nech� $\A=(a_{i,j})\in\R^{n,n}$ je �tvercov� matice. ��slo
$$
  \det\A = \hskip-3em \sum_{\hbox{\setfonts[/mag.7] permutace}\ \pi=(i_1,i_2,\ldots,i_n)} 
  \hskip-3em {\rm sgn}\,\pi\cdot a_{1,i_1}\,a_{2,i_2}\cdots\,a_{n,i_n}
$$


\bigskip

* U�ite�n� je p�edstava �achov�ch v��.

* P��klad pro matice typu $(1,1)$, $(2,2)$, $(3,3)$ \dots\ Sarrusovo pravidlo.

* Pozor, pro matice v�t��ch typ� Sarrusovo pravidlo nelze pou��t!

\n ------------------------------------------------------------------

\g Determinant horn� troj�heln�kov� matice

$$
  \det \pmatrix{a_{1,1}, & a_{1,2}, &\ldots, & a_{1,n-1}, & a_{1,n} \cr
                      0, & a_{2,2}, &\ldots, & a_{2,n-1}, & a_{2,n} \cr
                      0, &       0, &\ldots, & a_{3,n-1}, & a_{3,n} \cr
                         &          &\vdots  & & \cr
                      0, &       0, &\ldots, &         0, & a_{n,n} \cr}
$$

je roven sou�inu prvk� na diagon�le: \ $a_{1,1}\cdot a_{2,2}\cdot a_{3,3}\cdots a_{n,n}$.

Vid� v�ichni pro�?

\n ------------------------------------------------------------------

\g Z�kladn� vlastnosti determinantu

* Prohozen� ��dk� zm�n� znam�nko determinantu

* Matice se dv�ma stejn�mi ��dky m� nulov� determinant

* Pron�soben� jedin�ho ��dku $\alpha$-kr�t zv�t�� $\alpha$-kr�t i determinant

* Je-li jeden ��dek zapsan� jakou sou�et dvou ��st�, pak determinat
  takov� matice je roven sou�tu determinant� matic, ve kter�ch jsou
  m�sto tohoto ��dku jen jeho ��sti:
$$
  \det\pmatrix{\vdots\cr\vec a_i\cr\vdots} + 
          \det\pmatrix{\vdots\cr\vec b_i\cr\vdots} =
          \det\pmatrix{\vdots\cr\vec a_i+\vec b_i\cr\vdots}.
$$

* T�et� typ kroku elimina�n� metody nezm�n� determinant.


\n ------------------------------------------------------------------

\g Metoda v�po�tu determinantu

{\bf Algoritmus:} Eliminac� p�evedeme danou matici $\A$ na horn�
troj�heln�kovou matici $\U$. Pokud b�hem eliminace pou�ijeme prvn�
nebo druh� typ kroku eliminace, je pot�eba si poznamenat, jak se
zm�nil determinant. T�et� typ kroku nem�n� determinant v�bec.
Kone�n� $\det\U$ je sou�in prvk� na diagon�le.

Slo�itost algoritmu: $n^3$. V�razn� �spora proti vzorci v
definici, kter� ma slo�itost $n!\,$.


\n ---------------------------------------------------------

\g P��klad

$$
  \def\d#1{\left\|\matrix{#1}\right\|}
  \displaylines{
  \d{1&2&3&3\cr 2&4&1&4\cr 4&2&1&2\cr 3&1&2&1} =
  \d{1&2&3&3\cr 0&0&-5&-2\cr 0&-6&-11&-10\cr 0&-5&-7&-8} =
  (-1)^4\d{1&2&3&3\cr 0&6&11&10\cr 0&0&5&2\cr 0&5&7&8} = \cr\noalign{\bigskip}
  {1\over6}\d{1&2&3&3\cr 0&6&11&10\cr 0&0&5&2\cr 0&30&42&48} =
  {1\over6}\d{1&2&3&3\cr 0&6&11&10\cr 0&0&5&2\cr 0&0&-13&-2} = \cr\noalign{\bigskip}
  {1\over6}\cdot{1\over 5} \d{1&2&3&3\cr 0&6&11&10\cr 0&0&5&2\cr 0&0&-65&-10} =
  {1\over30} \d{1&2&3&3\cr 0&6&11&10\cr 0&0&5&2\cr 0&0&0&16}
  = 16.
}
$$
Za chv�li uvid�me, �e to lze spo��tat jednodu�eji\dots


\n ------------------------------------------------------------------

\g ��dky a sloupce jedno jest

{\bf Tvrzen�:} $\det\A = \det\A^T$.

D�kaz: M�m permutaci $(i_1,i_2,\ldots,i_n)$ a podle n� provedu
sloupcov� v�b�r prvk� matice a vyn�sob�m mezi sebou:
$$
  a_{i_1,1}\cdot a_{i_2,2}\cdots a_{i_n,n}  = a_{1,j_1}\cdot a_{2,j_2}\cdots a_{n,j_n}
$$
Sou�in re�ln�ch ��sel je komutativn�, tak jsem �initele uspo��dal podle
velikosti ��dkov�ho indexu. Jak� je vztah mezi permutacemi:
$(i_1,i_2,\ldots,i_n)$ a  $(j_1,j_2,\ldots,j_n)$? Jsou si vz�jmn�
inverzn�. A inverzn� permutace maj� stejn� znam�nko. Tak�e vzorce
s ��dkov�m i sloupcov�m v�b�rem d�vaj� stejn� v�sledek.

{\bf D�sledek:} P�i eliminaci za ��elem v�po�tu determinantu lze
libovoln� p�ech�zet mezi ��dkov�mi a sloupcov�mi �pravami.


\n -----------------------------------------------------------------

\g Regul�rn� a singul�rn� matice

{\bf V�ta:} Matice $\A$ je regul�rn�, pr�v� kdy� $\det\A\not=0$.

D�kaz: $\A$ je regul�rn� pr�v� kdy� $\A\sim\E$. D�le si sta�� uv�domit,
�e Gaussova eliminace nem�n� {\it nulovost\/} determinantu.

\n ----------------------------------------------------------------

\g Determinant sou�inu matic

{\bf V�ta:} Pro dv� �tvercov� matice typu $(n,n)$ plat�
$$
  \det(\A\cdot\B) = (\det\A)\cdot(\det\B).
$$

D�kaz\char`\*: Lze prov�st $\A\sim\U_1$ ��dkov�mi elimina�n�mi �pravami, aby
se nezm�nil determinant. D�le lze p�ev�st $\B$ na $\U_2$ sloupcov�mi 
elimina�n�mi �pravami tak, �e se nezm�n� determinant. Snadno se uk�e, �e
$$
  \det(\U_1\cdot\U_2) = (\det\U_1)\cdot(\det\U_2)
$$
Existuj� matice $\P_1$, $\P_2$ tak, �e $\U_1=\P_1\A$, $\U_2=\B\P_2$.
Stejn� ��dkov� i sloupcov� �pravy provedeme na $\A\cdot\B$,
tedy $\P_1\A\cdot\B\P_2=\U_1\cdot\U_2$. �pravy nem�n� determinant,
tak�e
$$
  \eqalign{
  \det(\A\cdot\B) &= \det(\P_1\A\cdot\B\P_2) = \det(\U_1\cdot\U_2)
  =\cr &=
  (\det\U_1)\cdot(\det\U_2) = (\det\A)\cdot(\det\B).
  }
$$

\n -------------------------------------------------------------------

\iffalse

\g D�sledky v�ty o determinantu sou�inu

* $\det\A^{-1} = 1/\det\A$

* Je-li $\A=\L\U$ rozklad matice $\A$, pak $\det\A = \det\U$, tedy
  $\det\A$ je roven sou�inu diagon�ln�ch prvk� v matici $\U$.\hb
  (p�ipom�n�m, �e matice $\L$ m� na diagon�le jedni�ky).

\fi

\g D�sledek v�ty o determinantu sou�inu

$\det\A^{-1} = 1/\det\A$


\n -----------------------------------------------------------------

\g Rozvoj determinantu podle ��dku

{\bf Terminologie:} Vy�ad�me-li ze �tvercov� matice $\A\in\R^{n,n}$ $i$-t� ��dek a
$j$-t� sloupec, dost�v�me matici $\A_{i,j}\in\R^{n-1,n-1}$. ��slo
$$
  D_{i,j} = (-1)^{i+j}\det\A_{i,j}
$$
se naz�v� {\em dopln�k matice $\A$ v pozici $(i,j)$}.

{\bf V�ta o rozvoji:} Nech� $D_{i,j}$ jsou dopl�ky �tvercov� matice
$\A=(a_{i,j})$. Pak plat�
$$
     \det\A = a_{r,1}\,D_{r,1} + a_{r,2}\,D_{r,2} + \cdots + 
               a_{r,n}\,D_{r,n}.
$$

N�znak d�kazu: vytkn�te ze sou�tu z definice determinantu $a_{r,1}$
(jen z t�ch s��tanc�, kde se $a_{r,1}$ vyskytuje), d�le vytkn�te
$a_{r_2}$ atd. a� $a_{r,n}$. V z�vork�ch po vytknut� dostanete $D_{r,i}$.

\n -----------------------------------------------------------------

\g Rozj�m�n� nad v�tou o rozvoji

* Proto�e $\det\A = \det\A^T$, plat� analogick� v�ta o rozvoji podle sloupce

* Je-li v ��dku/sloupci hodn� nul, je v sou�tu podle v�ty o rozvoji
  hodn� nulov�ch s��tanc�. Sta�� zapsat jen ty nenulov� a redukovat
  v�po�et determinantu matice typu $(n,n)$ na n�kolik (m�lo)
  determinant� matic typu $(n-1,n-1)$.

* Pozor: rekurzivn� vol�n� v�po�tu determinantu podle v�ty o rozvoji
  m� slo�itost $n!$, tak�e tento algoritmus je nepou�iteln�.

* D�sledkem v�ty o rozvoji je tvrzen�:
$$
  0 = a_{r,1}\,D_{k,1} + a_{r,2}\,D_{k,2} + \cdots + 
               a_{r,n}\,D_{k,n} \quad \hbox{pro $r\not=k$}.
$$
Sta�� prov�st v�tu o rozvoji na matici se dv�ma stejn�mi ��dky.

* V�ta o rozvoji m� �adu dal��ch teoretick�ch d�sledk�, n�kter� se dozv�me pozd�ji\dots


\n ---------------------------------------------------------------

\g P��klad

$$
  \def\d#1{\left\|\matrix{#1}\right\|}
  \displaylines{
  \d{1&2&3&3\cr 2&4&1&4\cr 4&2&1&2\cr 3&1&2&1} =
  \d{1&2&3&1\cr 2&4&1&0\cr 4&2&1&0\cr 3&1&2&0} =
  -\d{2&4&1\cr 4&2&1\cr 3&1&2} = \cr\noalign{\bigskip}
  -\d{2&4&1\cr 2&-2&0\cr -1&-7&0} =
  2\d{1&-1\cr 1&7} = 2\cdot8 = 16.
}
$$


\n ---------------------------------------------------------------

\g Inverzn� matice pomoc� dopl�k�

Je-li $\A\in\R^{n,n}$ regul�rn�, pak
$$
  \A^{-1} = {1\over\det\A}\,\D^T, 
$$
kde $\D=(D_{i,j})$ je matice dopl�k� $\A$ v pozic�ch $(i,j)$.

D�kaz: Ov���me, �e $\A\A^{-1} = \E$.\hb
Ozna��me $\A=(a_{i,j})$, $\D^T=(D_{k,j})$, $\E=(e_{i,k})$.
$$
 \eqalign{ 
   e_{i,k} &= \sum_{j=1}^n a_{i,j}\,{1\over\det\A}\,D_{k,j} =
            {1\over\det\A}\bigl(a_{i,1}D_{k,1} + a_{i,2}D_{k,2} + 
            \cdots + a_{i,n}D_{k,n}\bigr) = \cr &= 
  \cases {\displaystyle {1\over\det\A\mathstrut}\,\det\A = 1 &\hbox{pro $i=k$,}\cr
          \displaystyle {\mathstrut1\over\det\A}\cdot 0 = 0  &\hbox{pro $i\not=k$.}}
}
$$
Vyu�ili jsme v�tu o rozvoji determinantu podle $i$-t�ho ��dku.


\n ----------------------------------------------------------

\g P��klad: inverze k matici typu (2,\thinspace2)

Je d�na matice
$$
  \A=\pmatrix{a&b\cr c&d}
$$
Matice dopl�k� k t�to matici je
$$
  \D = \pmatrix{d&-c\cr -b&a}
$$ 
Tak�e
$$
  \A^{-1} = {1\over\det\A} \D^T =
  {1\over ad-bc}\pmatrix{d&-b\cr -c&a}.
$$

\n ---------------------------------------------------------

\g P��klad: inverze matice pomoc� dopl�k�

Je d�na matice $\A = \pmatrix{1&2&3\cr-1&0&1\cr2&2&1}.$

Matice dopl�k� je:
$$
  \def\+{\hphantom{-}}
  \def\dmatrix#1,#2,#3,#4,{\vcenter{\kern2pt
     \hbox{$\left|\matrix{#1&#2\cr#3&#4}\right|$}\kern2pt}}
  \D = 
  \pmatrix{+\dmatrix 0,1,2,1,&-\dmatrix-1,1,\+2,1,&+\dmatrix-1,0,\+2,2,\cr\noalign{\medskip}
           -\dmatrix 2,3,2,1,&+\dmatrix 1,3,2,1,&-\dmatrix 1,2,2,2,\cr\noalign{\medskip}
           +\dmatrix 2,3,0,1,&-\dmatrix \+1,3,-1,1,&+\dmatrix \+1,2,-1,0,}
  = \pmatrix{-2&\+3&-2\cr\+4&-5&\+2\cr\+2&-4&\+2},
$$
tak�e:
$
   \displaystyle
  \quad \def\+{\hphantom{-}}
  \det\A = -2, \qquad \A^{-1} = {1\over\det\A}\,\D^T =
  -{1\over2} \pmatrix{-2&\+4&\+2\cr \+3&-5&-4\cr-2&\+2&\+2}.
$


\end
