\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{7}

\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\E{{\bf E}}
\def\P{{\bf P}}
\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 N�soben� matic

\bigskip\bigskip

* je asociativn�, nen� komutativn�

* k regul�rn�m matic�m existuj� inverzn� matice

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

\g Maticov� n�soben�

{\bf Definice:} Pro matice $\A\in\R^{m,n}$ a $\B\in\R^{n,p}$ existuje
maticov� sou�in $\A\cdot\B=\C\in\R^{m,p}$ (v tomto po�ad�). Jednotliv�
prvky sou�inu $c_{i,k}$ jsou d�ny vzorcem:
$$
  c_{i,k} = a_{i,1}b_{1,k}+a_{i,2}b_{2,k}+\cdots+a_{i,n}b_{n,k}
  = \sum_{j=1}^n a_{i,j}b_{j,k}.
$$ 

{\bf P��klad:} Je-li $\A\in\R^{3,4}$ a $\B\in\R^{4,5}$, pak
$\A\cdot\B$ je definov�no, ale $\B\cdot\A$ nen� definov�no. 

{\bf Pozorov�n�:} Aby bylo definov�no $\A\cdot\B$, mus� m�t $\A$
stejn� po�et sloupc� jako m� $\B$ ��dk�. V�sledn� matice m� tolik
��dk�, jako m� ��dk� matice $\A$ a tolik sloupc�, jako m� sloupc� matice $\B$.


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


\g P��klady n�soben�

$$\pmatrix{1&2&3}\cdot\pmatrix{4\cr5\cr6} = \pmatrix{1\cdot4+2\cdot5+3\cdot6}$$

$$\pmatrix{4\cr5\cr6}\cdot\pmatrix{1&2&3} = \pmatrix{4&8&12\cr5&10&15\cr6&12&18}$$

$$\pmatrix{1&1\cr-1&-1}\cdot\pmatrix{1&1\cr1&1} = \pmatrix{2&2\cr-2&-2}$$

$$\pmatrix{1&1\cr1&1}\cdot\pmatrix{1&1\cr-1&-1} = \pmatrix{0&0\cr0&0}$$

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

\g Poznatky z p�edchoz�ch p��klad�:

* Maticov� n�soben� nen� komutativn� ani pro �tvercov� matice

* Neplat� pravidlo: sou�in nenulov�ch matic mus� b�t nenulov� matice

* Co tedy plat�? \dots

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

\g Vlastnosti maticov�ho n�soben�:

* $(\A\cdot\B)\cdot\C = \A\cdot(\B\cdot\C)$ \dots\ asociativn� z�kon

* $(\A+\B)\cdot\C = \A\cdot\C + \B\cdot\C$ \dots\ distributivn� z�kon

* $\C\cdot(\A+\B) = \C\cdot\A + \C\cdot\B$ \dots\ distributivn� z�kon

* $\alpha(\A\cdot\B) = (\alpha\A)\cdot\B = \A\cdot(\alpha\B)$
  \dots\ konstanta

* $(\A\cdot\B)^T = \B^T\cdot \A^T$ \dots\ transponovan� matice

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

\g P��klad: soustavy lin. rovnic

Nech� $\A\in\R^{m,n}$.

$$\A\cdot\pmatrix{x_1\cr x_2\cr \vdots\cr x_n} =
    \pmatrix{b_1\cr b_2\cr \vdots\cr b_m}$$

Toto je soustava line�rn�ch rovnic s $m$ rovnicemi a $n$ nezn�m�mi.
  
Stru�n� zapisujeme: $\A\cdot{\bf x} = {\bf b}$.
Matice $\A$ se naz�v� {\em matice soustavy}, jednosloupcov� matice
${\bf b}$ je {\em vektor prav�ch stran}. �kolem je nal�zt
v�echny jednosloupcov� matice ${\bf x}$, kter� vyhovuj� 
maticov� rovnici.


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

\g Blokov� n�soben�

Nech� $\A$ a $\B$ jsou matice sestaven� po bloc�ch takto:
$$
  \A = \pmatrix {\A_{1,1}& \A_{1,2} \cr \A_{2,1} & \A_{2,2}}, \quad
  \B = \pmatrix {\B_{1,1}& \B_{1,2} \cr \B_{2,1} & \B_{2,2}}
$$
Nech� uveden� bloky jsou matice takov�ho typu, �e n�soben� matic $\A_{i,j}\cdot\B_{j,k}$
je definov�no pro v�echny p��pady, kter� se vyskytuj� v~n�sleduj�c�m
vzorci. Pak
$$
  \A\cdot \B = \pmatrix {\A_{1,1}\cdot\B_{1,1}+ \A_{1,2}\cdot\B_{2,1}&\
                         \A_{1,1}\cdot\B_{1,2}+ \A_{1,2}\cdot\B_{2,2}\cr
                         \A_{2,1}\cdot\B_{1,1}+ \A_{2,2}\cdot\B_{2,1}&\
                         \A_{2,1}\cdot\B_{1,2}+ \A_{2,2}\cdot\B_{2,2}}
$$

\dots\ analogicky pro jinak vytvo�en� bloky. Nap��klad:

$$\A\cdot\pmatrix{\B_1&\B_2&\ldots&\B_p} =
  \pmatrix{\A\cdot\B_1&\A\cdot\B_2&\ldots&\A\cdot\B_p}$$

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

\g V�po�etn� slo�itost maticov�ho n�soben�

P�edpokl�dejme dv� matice $\A,\B\in\R^{n,n}$. K v�po�tu
$\A\cdot\B$ (podle definice) pot�ebujeme $n^3$ operac� (n�soben� dvou
��sel). Nedalo by se u�et�it?

* {\bf Rekurzivn� algoritmus n�soben� matic:} vych�z� 
  z blokov�ho n�soben�. Pot�ebuje $F(n)$ operac�:
$$
  \eqalign{
    F(n) &= 8F(n/2) = 8(8F(n/4)) = 8(8(8F(n/2^3))) = \cr &= \cdots = 
  8^m F(n/2^m) = 8^mF(1) =\cr &= 8^m = (2^3)^m =
  2^{3m} = (2^m)^3 = n^3.
}
$$

* {\bf Rekurzivn� Strassen�v algoritmus:} vych�z� z blokov�ho
  n�soben�, ale vysta�� si se sedmi sou�iny. Pot�ebuje $F(n)$ operac�:
$$
  \eqalign{
  F(n) &= 7F(n/2) = 7(7F(n/4)) = 7(7(7F(n/2^3))) = \cr &= \cdots = 
  7^m F(n/2^m) = 7^mF(1) =\cr &= 7^m = (2^{\log_2 7})^{\log_2 n} =
  2^{\log_2 7\,\cdot\,\log_2 n} = n^{\log_2 7} \doteq n^{2{,}807}.
}
$$

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

\g Strassen�v algoritmus

$$
\eqalign{
  &\X_1 = (\A_1 + \A_4)\cdot(\B_1+\B_4), \cr
  &\X_2 = (\A_3 + \A_4)\cdot\B_1, \cr
  &\X_3 = \A_1\cdot(\B_2-\B_4), \cr
  &\X_4 = \A_4\cdot(\B_3-\B_1), \cr
  &\X_5 = (\A_1+\A_2)\cdot\B_4, \cr
  &\X_6 = (\A_3-\A_1)\cdot(\B_1+\B_2), \cr
  &\X_7 = (\A_2-\A_4)\cdot(\B_3+\B_4)
}
$$
D� se ov��it, �e plat�:
$$
  \pmatrix{\A_1 &\A_2\cr \A_3&\A_4}\! \cdot\!
  \pmatrix{\B_1 &\B_2\cr \B_3&\B_4} =
  \pmatrix{\X_1+\X_4-\X_5+\X_7\ & \X_3+\X_5\cr \X_2+\X_4& \X_1-\X_2+\X_3+\X_6}
$$

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

\g Komutuj�c� matice

Kdy� plat�: $\A\cdot\B = \B\cdot\A$, ��k�me, �e matice $\B$ komutuje
s matic� $\A$.

{\bf Pozorov�n�:} Komutovat mohou pouze �tvercov� matice stejn�ho typu.

{\bf �loha:} Je pevn� d�na �tvercov� matice $\A$, je t�eba naj�t k n�
mno�inu v�ech matic $\B$, kter� komutuj� s $\A$.

{\bf Pozorovan�:} Uveden� mno�ina matic $\B$, kter� komutuj� s danou
matic� $\A$, tvo�� line�rn� podprostor line�rn�ho
prostoru matic $\R^{n,n}$.

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

\g Inverzn� matice

�tvercovou matici s jedni�kami na diagon�le a nulami jinde zna��me
  $\E$ a ��k�me ji {\em jednotkov� matice}.

{\bf Pozorov�n�:} $\A\cdot\E = \E\cdot\A = \A$, analogie s ��sly:
$a\cdot1 = 1\cdot a = a$.

{\bf Definice:} {\em Inverz� matice\/} ke �tvercov� matici $\A$ je
takov� matice $\B$, pro kterou je 
$$\A\cdot\B=\B\cdot\A=\E.$$
(viz t� analogie s ��sly). Invezn� matici zna��me $\A^{-1}$.

{\bf Pozorov�n�:} Pokud k matici $\A$ inverzn� matice existuje, pak je
ur�ena jednozna�n�. D�vod je zde:
$$
  \B_1 = \E\cdot\B_1 = (\B_2\cdot\A)\cdot\B_1 =
   \B_2\cdot(\A\cdot\B_1) = \B_2\cdot\E = \B_2
$$ 
{\bf Ot�zka:} Jak pozn�me existenci inverzn� matice k matici $\A$?

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

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

{\bf Definice:} �tvercov� matice je {\em regul�rn�}, pokud m� inverzn�
matici.  
�tvercov� matice je {\em singul�rn�}, pokud nem� inverzn�
matici.

{\bf Pozorov�n�:} Sou�in regul�rn�ch matic je regul�rn�
matice. M�-li matice $\A$ inverzn� matici $\A^{-1}$ a d�le m�-li  
matice $\B$ inverzn� matici $\B^{-1}$, pak inverzn� matice k
$\A\cdot\B$ je $\B^{-1}\cdot\A^{-1}$. Plat� toti�:
$$\displaylines{
  (\B^{-1}\cdot\A^{-1})\cdot(\A\cdot\B) =
  \B^{-1}\cdot(\A^{-1}\cdot\A)\cdot\B = \B^{-1}\cdot\E\cdot\B =
  \B^{-1}\cdot\B = \E, \cr
  (\A\cdot\B)\cdot(\B^{-1}\cdot\A^{-1}) =
  \A\cdot(\B\cdot\B^{-1})\cdot\A^{-1} = \A\cdot\E\cdot\A^{-1} =
  \A\cdot\A^{-1} = \E .}
$$


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

\g V�po�et inverzn� matice eliminac�

{\bf Algoritmus:} M�-li $\A$ line�rn� nez�visl� ��dky, pak existuje 
$\A^{-1}$ a lze ji vypo��tat takto:
$$
  (\A\,|\,\E) \sim (\E\,|\,\A^{-1})
$$

Ke zd�vodn�n� t�to metody pot�ebujeme zav�st t�i typy �tvercov�ch
matic, kter� (pokud jimi n�sob�me vybranou matici zleva) \uv{emuluj�}
jednotliv� kroky elimina�n� metody. Sou�in t�chto element�rn�ch
matic emuluj�c� v�echny proveden� kroky je matice $\P$, pro kterou plat�:

{\bf V�ta:} Je-li $\A\sim\B$, pak existuje regul�rn� $\P$ takov�, �e
$\B=\P\cdot\A$. 


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

\g Podm�nky regularity matice

N�sleduj�c� podm�nky jsou ekvivalentn� s regularitou matice $\A\in\R^{n,n}$:

* $\A$ m� inverzn� matici (viz definice).

* Maticov� rovnice $\A\cdot\X=\B$ m� �e�en� pro ka�dou $\B\in\R^{n,m}$.

* Matice $\A$ m� line�rn� nez�visl� ��dky.

* $\hod\A=n$.

* existuje elimina�n� proces, kter� provede $\A\sim\E$.

* $\det\A\not=0$ (o determinantech pohovo��me pozd�ji)

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

\g Hodnost sou�inu

{\bf V�ta:} Je-li $\P$ regul�rn� a plat�-li $\B=\P\cdot\A$, pak
$\A\sim\B$.

D�kaz: $\P\sim\E$ a stejn� kroky eliminace pou�ijeme na $(\P\,|\,\B)$,
tj.:
$$
  (\P\,|\,\B) = (\P\,|\,\P\cdot\A) \sim (\E\,|\,\X) = \P^{-1}(\P\,|\,\P\cdot\A) =
            (\E\,|\,\A),
$$
tak�e $\A\sim\B$.

{\bf V�ta:} N�sob�me-li matici $\A$ jakoukoli regul�rn� matic�, 
nezm�n� se hodnost. Tedy: $\hod\A = \hod(\P\cdot\A)$. 


{\bf V�ta:} $\hod(\A\cdot\B) \le \min(\hod\A,\hod\B)$

D�kaz\char`\*: $\hod\A=k$, tj. $\A\sim\C$, $\C$ m� $k$ nenulov�ch
��dk�. Existuje tedy $\P$ regul�rn�, �e $\A=\P\cdot\C$.
D�le plat�:
$$
 \hod(\A\cdot\B) = \hod(\P\cdot\C\cdot\B) = 
 \hod(\C\cdot\B) \le k.
$$
 

\end
