\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage[latin2]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[mathscr]{eucal}


\newcommand{\Conj}[1]{\overline{#1}}
\newcommand{\Halm}[1]{\mathbbm{#1}}

\newcommand{\mo}{{\bf Megoldás:}\\}

\newcommand{\V}{\underline}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Lek}[1]{{\cal #1}}
\newcommand{\im}{\mathop{\mathrm{Im}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}

\addtolength{\textwidth}{5cm}
\addtolength{\textheight}{6cm}
\setlength{\hoffset}{-2.5cm}
\setlength{\voffset}{-3cm}


\frenchspacing

\begin{document}
\begin{center}
{\LARGE \bf Bevezetés a számításelméletbe (kieg.)}\\
{\bf Első zárthelyi, megoldások}
\end{center}
\Large


\begin{enumerate}

\item Oldjuk meg az alábbi lineáris egyenletrendszert:

\[ 
\begin{array}{rcl}
x+2y+5w&=&5\\
4x+2y+6w&=&12\\
5x+y+z+4w&=&16\\
2x+y+z+3w&=&9
\end{array}
\]

\mo
Vonjuk ki az első sor a másodikból, az utolsót pedig a harmadikból, így 
a kapott mátrix második és harmadik sora megegyezik, tehát egyiküket 
elhagyjuk.
\[ \left(
\begin{array}{rrrrr}
1&2&0&5&5\\
3&0&0&1&7\\
2&1&1&3&9
\end{array}
\right) \]
Most szorozzuk az utolsó sort kettővel, vonjuk ki belőle az első és
második sor, végül osszuk le kettővel. (Azaz a harmadik sorból a két 
felette álló sor felét vontuk ki.) Így kapjuk, hogy $z=3$. Mivel a többi 
egyenletben $z$ együtthatója már $0$, ezért elhagyjuk az oszlopát és 
az így érdektelenné vált harmadik sort is. A kapott mátrix:
$\left(
\begin{array}{rrrr}
1&2&5&5\\
3&0&1&7
\end{array}
\right)$
Most a második sor $5$-szörösét vonjuk ki az elsőből, majd a kapott sort 
kettővel osztva kapjuk, hogy 
$\left(
\begin{array}{rrrr}
-7&1&0&-15\\
3&0&1&7
\end{array}
\right)$,
azaz $y=7x-15$, $w=-3x+7$, $x$ tetszőleges és --- amint fent kiszámoltuk 
$z=3$.

\item Egy adott $100 \times 100$-as valós elemű mátrixban tetszőleges számú
elem helyére általunk választott számokat írhatunk. Legkevesebb hány elem
módosításával tudjuk elérni, hogy a keletkező determináns 0 legyen?

\mo
Fejtsük ki a mátrixot az első sora szerint, így 
\[
\det A= \sum_{j=1}^{100} a_{1,j}A_{1,j}\hbox{,}
\]
ahol $A$ a mátrixunk, $i$. sorának $j$. eleme $a_{1,j}$, $A_{1,j}$ pedig 
a megfelelő előjeles aldetermináns. Ha most minden $j$-re $A_{1,j}=0$, 
akkor nyilvánvalóan $\det A=0$. Ellenkező esetben legyen például 
$A_{1,j_{0}} \ne 0$. Ekkor változtassuk meg $a_{1,j_{0}}$ elemet $b$-re, úgy 
hogy 
\[
b:=\frac{-\sum_{j=1, j\ne j_{0}}^{100} a_{1,j}A_{1,j}}{A_{1,j_{0}}}
\]
A megváltoztatott mátrixot kifejtve az első sor szerint azt kapjuk, hogy 
\[
\det A'= \sum_{j=1, j\ne j_{0}}^{100} a_{1,j}A_{1,j} + 
bA_{1,j_{0}} =
\] \[
= \sum_{j=1, j\ne j_{0}}^{100} a_{1,j}A_{1,j} + 
\frac{-\sum_{j=1, j\ne j_{0}}^{100} a_{1,j}A_{1,j}}{A_{1,j_{0}}}A_{1,j_{0}} = 0
\]
Egy elem megváltoztatása tehát elég.

\item Mennyi a rangja az alábbi mátrixnak?
\[ \left (
\begin{array}{rrrr}
4&1&3&2\\
5&5&3&1\\
6&4&2&0\\
0&0&1&1
\end{array}
\right ) \]

\mo
Gauss eliminációval átalakítjuk a mátrixot olyan alakra, amelyből már 
látszik a rangja. Például a következő lépéseket végrehajtva viszonylag 
szép alakhoz jutunk: Vonjuk ki a negyedik sort a másodikból, majd 
kétszeresét az elsőből. Vonjuk ki a második sort a harmadikból, utána 
az elsőt kétszeresét a másodikból, végül a harmadik sor háromszorosát 
adjuk hozzá a második sorhoz. Cseréljük fel az első és második sorokat.
\[ \left(
\begin{array}{rrrr}
0&0&0&0\\
4&1&1&0\\
1&-1&0&0\\
0&0&1&1
\end{array}
\right) \]
A kapott mátrix determinánsa $0$, hiszen van egy csupa $0$ sora, tehát 
a rangja legfeljebb három. Könnyen ellenőrizhetjük, hogy a ,,jobb alsó''
$3\times 3$-as rész\-mát\-rix determinánsa $1$, azaz nem $0$, emiatt a rang 
legalább $3$. Következésképp pontosan $3$.


\item Mennyi az $A_{n \times n}$ mátrix determinánsa, ha
$A[i,i-1]=A[i,i]=A[i,i+1]=1$, minden további eleme pedig nulla?

\mo
Jelölje a kérdéses determináns értékét $A_n$. Ha kifejtjük az első sor
szerint, azt kapjuk, hogy $A_n=A_{n-1}-A_{n-2}$, amennyiben $n\ge 3$.
$A_{1}=1$, $A_{2}=0$ könnyen kiszámolható. A rekurzió megoldása nem 
különösen nehéz, mivel $A$ értékei az  alábbiak szerint alakulnak:
$A_{1}=1$, $A_{2}=0$, $A_{3}=-1$, $A_{4}=-1$, $A_{5}=0$, $A_{6}=1$, 
$A_{7}=1$, $A_{8}=0$, innen pedig már látható, hogy az $1$-től $6$-ig 
levő értékek ismétlődnek periodikusan, hiszen a rekurzióban csak az előző 
két tag szerepel, amik a $7$. és $8$. helyen már ismétlődnek. 

\item 
\begin{enumerate}
\item Bizonyítsuk be, hogy ha $A$ és $B$ valós mátrixok összeszorozhatóak,
akkor $(AB)^T=B^{T}A^T$.
\item Egy $A$ valós négyzetes mátrixot ortogonálisnak nevezünk, ha
$AA^T=E$. Bizonyítsuk be, hogy ortogonális mátrix transzponáltja is
ortogonális.
\end{enumerate}

\mo
Ha $M$ egy mátrix, jelöljük $(M)_{i,j}$-vel az $M$ $i$-edik sorának 
$j$-edik elemét.
Tegyük fel, hogy $A$ $n\times k$-as, így $B$-vel pontosan akkor 
összeszorozható, ha $B$ $k\times m$-es, valamilyen $m$-re.
$(AB)_{i,j}=\sum_{r=1}^k (A)_{i,r}(B)_{r,j}$ a mátrixszorzás definíciója 
alapján, tehát $((AB)^T)_{i,j} = (AB)_{j,i} = \sum_{r=1}^k (A)_{j,r}(B)_{r,i}$. 
Nézzük most a másik oldalt. $B^TA^T = \sum_{r=1}^k (B^T)_{i,r}(A^T)_{r,j} = 
\sum_{r=1}^k (B)_{r,i}(A)_{j,r}$, azaz a két oldal valóban megegyezik.

$A^T$ a fenti definíció alapján akkor ortogonális, ha transzponáltjával 
jobbról megszorozva az egységmátrixot kapjuk, azaz ellenőrizendő $A^T(A^T)^T=E$, 
azaz $A^TA=E$. Ez viszont teljesül, hiszen ha $A$ mátrixnak ,,jobbról'' 
inverze $A^T$, akkor ,,balról'' is az.

\item Igazoljuk, hogy ha az $\V u_1, \V u_2, \dots, \V u_m$ vektorok
között \emph{pontosan} egy van, amely lineárisan függ a többi
$m-1$-től, akkor ez szükségképpen a nullvektor.

\mo
Tegyük fel az egyszerűbb jelölés kedvéért, hogy az $\V u_1$ az az egyetlen 
vektor, amely a többivel kifejezhető, és $\V u_1 = 
\sum_{i=2}^m \lambda_i \cdot\V u_i$. Ha most minden $\lambda_i$ nulla, akkor 
$\V u_1$ valóban nullvektor. Ellenkező esetben valamelyik $\lambda_i$ 
nem $0$, szintén az egyszerűbbség kedvéért feltehető, hogy ez a $\lambda_2$.
A fenti egyenlet ezek szerint átrendezhető az alábbi módon:
\[
-\lambda_2 \cdot\V u_2 = -\V{u_1}+\sum_{i=3}^m \lambda_i \cdot\V u_i
\] \[
\V{u_2} = \frac{1}{\lambda_2}\cdot\V{u_1}+
\sum_{i=3}^m -\frac{\lambda_i}{\lambda_2}\cdot\V{u_i}
\]

\item (pluszfeladat) Legyen $A$ olyan négyzetes mátrix, amely felírható 
\[ 
T^{-1}\left (
\begin{array}{rrr}
d_1&&0\\
&\ddots&\\
0&&d_k
\end{array} \right ) T \]
alakban, $p(x)=a_{n}x^n+a_{n-1}x^{n-1}+\ldots+a_0$
pedig tetszőleges valós együtthatós polinom. Az $A$ mátrix polinomba való
behelyettesítését úgy értelmezzük, hogy
$p(A)=a_{n}A^n+a_{n-1}A^{n-1}+\ldots+a_{0}E$. Bizonyítsuk be, hogy 
\[
p(A)=T^{-1}
\left( \begin{array}{rrr}
p(d_1)&&0\\
&\ddots&\\
0&&p(d_k)
\end{array} \right)
T
\]

\mo
Legyen $D=\left(\begin{array}{rrr}d_1&&0\\&\ddots&\\0&&d_k\end{array}\right)$.
Először vizsgáljuk $A^m$-et.
Teljes indukcióval látható, hogy $A^m=T^{-1} D^mT$, hiszen $m=1$-re világos, és
feltételezve, hogy $A^{m-1}=T^{-1} D^{m-1}T$, 
\[
A^m = A^{m-1}A = (T^{-1}D^{m-1}T)(T^{-1}DT) = T^{-1}D^{m-1}(TT^{-1})DT =
\] \[
T^{-1}D^{m-1}DT = T^{-1} D^mT
\]
Szintén teljes indukcióval lehet bebizonyítani, hogy 
\[
D^m = \left(\begin{array}{rrr}d_1^m&&0\\&\ddots&\\0&&d_k^m\end{array}\right)
\]
Ezzel tehát készen vagyunk a $p(x)=x^m$ polinomokkal. Most megnézzük 
a  $p(x)=a_{m}x^m$ alakúakat. $p(A) = a_m A^m = a_m T^{-1}D^mT = 
T^{-1}a_mD^mT = T^{-1}a_mD^mT = T^{-1} 
\left(\begin{array}{rrr}a_md_1^m&&0\\&\ddots&\\0&&a_md_k^m\end{array}\right)T =
T^{-1}\left(\begin{array}{rrr}p(d_1)&&0\\&\ddots&\\0&&p(d_k)\end{array}\right)T$

Végül egy $p(x)=a_{n}x^n+a_{n-1}x^{n-1}+\ldots+a_0$ polinomot írjuk fel 
$p_m(x)=a_mx^m$ polinomok összegeként: $p(x)=p_n(x)+p_{n-1}(x)+\ldots+p_0(x)$.
Tudjuk, hogy $p(A)=p_n(A)+p_{n-1}(A)+\ldots+p_0(A)$. Innen:
%\begin{multline*}
\begin{equation*}\begin{split}
p_n(A)+p_{n-1}(A)+\ldots+p_0(A) =\\
T^{-1}
\left(\begin{array}{rrr}p_n(d_1)&&0\\&\ddots&\\0&&p_n(d_k)\end{array}\right)
T + \ldots + T^{-1}
\left(\begin{array}{rrr}p_0(d_1)&&0\\&\ddots&\\0&&p_0(d_k)\end{array}\right)
T =\\ T^{-1}
\left(\begin{array}{rrr}p_n(d_1)+\ldots+p_0(d_1)&&0\\&\ddots&\\0&&p_n(d_k)+\ldots+p_0(d_k)\end{array}\right)
T =\\ T^{-1}\left(\begin{array}{rrr}p(d_1)&&0\\&\ddots&\\0&&p(d_k)\end{array}\right)T\quad
\end{split}\end{equation*}
%\end{multline*}
és így állításunkat beláttuk.

\end{enumerate}

Minden feladat 10 pontot ér, 100 \%-os teljesítményhez 60 pontot kell
elérni. Részeredményekért is jár pont, bizonyítás nélküli eredményközlésért
azonban nem. Ponthatárok: 0--23: 1; 24--32: 2; 33--42: 3; 43--51: 4; 52--60+: 5.

\end{document}










