\chyph

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

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

\font\logocvut=lev scaled400

\ifx\zkratka\undefined\edef\zkratka{\jobname}\fi
\def\cislo{9}

\headline={\setfonts[/10]\rm
   \ifnum\pageno>1 
   \hfill {\setfonts[/7] BI-LIN, \zkratka, \cislo, P. Olšák \quad}\else
   \firstpage\hfill\fi [\the\pageno]}
\footline={}

\def\firstpage{\vbox to0pt{\kern13.7cm\hbox{%
\setfonts[/8] a) \zkratka, \cislo, b) P. Olšák, FEL ČVUT, c) P. Olšák 2010,
  d) BI-LIN, e) L, f) 2009/2010, g) \lower1pt\hbox{\logocvut L}. 
  Viz p. d. 4/2010
}\vss}}

\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 kaž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 -------------------------------------------------------------------

\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).


\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