Kezdőlap


Cím:	Mátrixok
Szerző(k):	Hermann Péter
Füzet:	2006/május, 258 - 277. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az első egyenlet, amellyel a koordináta-geometriában találkozunk, az egyenes egyenlete: $a x + b y = c$ . Ennek segítségével határozhatjuk meg például két egyenes metszéspontjának a koordinátáit: ha az egyenesek egyenlete $a_{1} x + b_{1} y = c_{1}$ , illetve $a_{2} x + b_{2} y = c_{2}$ , akkor a metszéspont koordinátái azok az $x$ , $y$ számok, amelyek mind a két egyenletet kielégítik, vagyis az $x$ , $y$ számpár az

\begin{matrix} a_{1} x + b_{1} y & = c_{1} \\ a_{2} x + b_{2} y & = c_{2} \end{matrix}

lineáris egyenletrendszer megoldása.
Az

a x = b

egyenletek analógiájára érdemes az

(x, y)

párt egyetlen objektumnak tekinteni: így az egyenletrendszer bal oldala kiszámolja az ismeretlen

(x, y)

párhoz a

(c_{1}, c_{2})

számpárt. A feladat a megadott

(c_{1}, c_{2})

eredményhez tartozó pár megkeresése. Vizsgáljuk meg ezt a hozzárendelést.
Az egyismeretlenes elsőfokú egyenlet mintájára vezessük be a következő jelölést:

A \underset{̲}{x} = \underset{̲}{c}

, ahol

\underset{̲}{c}

az adott

(c_{1}, c_{2})

számpárt,

\underset{̲}{x}

pedig a keresett

(x, y)

számpárt jelenti, mindkettőt ,,függőleges'', oszlopszerű elrendezésben fölírva:

\underset{̲}{x} = (\begin{matrix} x \\ y \end{matrix})

\underset{̲}{c} = (\begin{matrix} c_{1} \\ c_{2} \end{matrix})

. Az

A

pedig az egyenletek bal oldalán álló együtthatók téglalap-szerű elrendezésben:

A = (\begin{matrix} a_{1} & b_{1} \\ a_{2} & b_{2} \end{matrix})

.
Vegyük észre, hogy ezzel nem csupán egy jelölést vezettünk be, amelynek révén számok bizonyos rendszereit mátrixokkal (esetünkben

A

\underset{̲}{c}

\underset{̲}{x}

) ábrázoljuk, hanem ‐ ezek egymás mellé írásával ‐ egy műveletet is, amely a két sorból és két oszlopból álló (röviden:

2 \times 2

-es)

A = (\begin{matrix} a_{1} & b_{1} \\ a_{2} & b_{2} \end{matrix})

és az egyetlen oszlopból álló

\underset{̲}{x} = (\begin{matrix} x \\ y \end{matrix})

oszlopmátrixokból kiszámolja a

\underset{̲}{c} = (\begin{matrix} c_{1} \\ c_{2} \end{matrix}) = (\begin{matrix} a_{1} x + b_{1} y \\ a_{2} x + b_{2} y \end{matrix})

oszlopmátrixot.
Nem kell innen túl messzire mennünk ahhoz, hogy további jelenségekre bukkanjunk, amelyek ugyancsak a fenti művelettel írhatók le. Tekintsük ehhez a sík különféle transzformációit: elforgatásokat, tükrözéseket, vetítéseket. Pontok helyett azonban vektorokra alkalmazzuk e transzformációkat, azaz rögzítsünk egy

O

origót, és a sík egy tetszőleges

P

pontjára tekintsük az

\vec{O P}

vektort. Tudjuk, hogy a

P (x, y)

pontba mutató

\vec{O P}

vektor felírható

\vec{O P} = x \underset{̲}{i} + y \underset{̲}{j}

alakban, ahol

\underset{̲}{i}

és

\underset{̲}{j}

a tengelyek irányába mutató egységvektorok. Ha

T

az említettek közül egy olyan geometriai transzformáció, amely az origót helyben hagyja és

\underset{̲}{i}

-t

\underset{̲}{i'}

-be,

\underset{̲}{j}

-t pedig

\underset{̲}{j}'

-be képezi, akkor

\vec{O P} = x \underset{̲}{i} + y \underset{̲}{j}

képe

x \underset{̲}{i}' + y \underset{̲}{j}'

. Írjuk fel ‐

\vec{O P}

-hez hasonlóan ‐ az

\underset{̲}{i}'

és

\underset{̲}{j}'

vektorokat is

\underset{̲}{i}' = t_{11} \underset{̲}{i} + t_{21} \underset{̲}{j}

\underset{̲}{j}' = t_{12} \underset{̲}{i} + t_{22} \underset{̲}{j}

alakban; ekkor

\vec{O P}

képe a

T

transzformációnál

T (\vec{O P}) = x \underset{̲}{i}' + y \underset{̲}{j}' = x (t_{11} \underset{̲}{i} + t_{21} \underset{̲}{j}) + y (t_{12} \underset{̲}{i} + t_{22} \underset{̲}{j}) = (t_{11} x + t_{12} y) \underset{̲}{i} + (t_{21} x + t_{22} y) \underset{̲}{j}

. Ekkor látható, hogy a képvektor

t_{11} x + t_{12} y

, illetve

t_{21} x + t_{22} y

koordinátáiból álló oszlopmátrix:

\begin{matrix} (\begin{matrix} t_{11} x + t_{12} y \\ t_{21} x + t_{22} y \end{matrix}) = (\begin{matrix} t_{11} & t_{12} \\ t_{21} & t_{22} \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) . \end{matrix}

T

transzformáció tehát egy mátrixszal ‐ a

(\begin{matrix} t_{11} & t_{12} \\ t_{21} & t_{22} \end{matrix})

mátrixszal ‐ adható meg, és egy tetszőleges vektor képének a koordinátáit ebből a mátrixból és a vektor koordinátáiból, mátrixszorzással kapjuk meg. Ennek a mátrixnak az oszlopai pedig éppen az

\underset{̲}{i}

és a

\underset{̲}{j}

vektorok képeként adódó vektorok.
A korábbi egyenletrendszert a transzformációk nyelvén megfogalmazva látható, hogy az egyenletmegoldás alaphelyzetébe kerültünk: ,,Gondoltam egy

(x, y)

számpárt, alkalmaztam rá a transzformációt, és a

(c_{1}, c_{2})

-t kaptam. Melyik számpárra gondoltam?''
Vizsgáljuk meg ezután, hogy az ismert geometriai transzformációknak mi a mátrix alakja. A legegyszerűbb talán az origó középpontú hasonlóság. Ha ennek aránya

λ

, akkor az

\underset{̲}{i}

és

\underset{̲}{j}

vektor egyaránt a

λ

-szorosára változik, sőt minden vektor mindkét koordinátája a

λ

-szorosára változik. Így a mátrixa

(\begin{matrix} λ & 0 \\ 0 & λ \end{matrix})

és valóban:

\begin{matrix} (\begin{matrix} λ & 0 \\ 0 & λ \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} λ x \\ λ y \end{matrix}) . \end{matrix}

Ennél kissé többet kell dolgozni az origó körüli forgatás mátrixáért. Ha az elforgatás szöge

α

, akkor ‐ a szögfüggvények definíciója alapján ‐ az

\underset{̲}{i}

vektor képe

cos α \underset{̲}{i} + sin α \underset{̲}{j}

, a mátrix első oszlopában tehát a

cos α

sin α

értékek állnak. A második oszlop, a

\underset{̲}{j}

vektor képe pedig az

\underset{̲}{i}

képének a 90 fokos elforgatottja, ami

- sin α \underset{̲}{i} + cos α \underset{̲}{j}

. Tehát a mátrixa

(\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix})

alakú.
Mielőtt továbbmennénk, érdemes megnézni, mi történik, ha az

α

szögű forgatást követően még egy

β

szöggel is forgatunk. A két forgatást egymás után végrehajtva összesen

α + β

szöggel forgattunk, ennek a transzformációnak a mátrixa az előbbiek szerint

(\begin{matrix} cos (α + β) & - sin (α + β) \\ sin (α + β) & cos (α + β) \end{matrix})

. Másrészt az

α

-val történő elforgatás az

(\begin{matrix} x \\ y \end{matrix})

-t a fentiek szerint

\begin{matrix} (\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} cos α \cdot x - sin α \cdot y \\ sin α \cdot x + cos α \cdot y \end{matrix}) -ba \end{matrix}

viszi, ezt pedig a

β

szögű forgatás

\begin{matrix} (\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix}) ((\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix}) (\begin{matrix} x \\ y \end{matrix})) = (\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix}) (\begin{matrix} cos α \cdot x - sin α \cdot y \\ sin α \cdot x + cos α \cdot y \end{matrix}) = \\ = (\begin{matrix} (cos β cos α - sin β sin α) x - (cos β sin α + sin β cos α) y \\ (cos β sin α + sin β cos α) x + (- sin β sin α + cos β cos α) y \end{matrix}) -ba. \end{matrix}

Mivel ez éppen

\begin{matrix} (\begin{matrix} cos (α + β) & - sin (α + β) \\ sin (α + β) & cos (α + β) \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} cos (α + β) x - sin (α + β) y \\ sin (α + β) x + cos (α + β) y \end{matrix}), \end{matrix}

a kapott azonosságból leolvashatók a szinusz- és koszinuszfüggvényre vonatkozó addíciós képletek. Ezen túlmenően az is kiderül, hogyan célszerű értelmezni a

(\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix})

és

(\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix})

mátrixok szorzatát, ha azt akarjuk, hogy azzal megszorozva az

(\begin{matrix} x \\ y \end{matrix})

oszlopot ugyanazt kapjuk, mintha

(\begin{matrix} x \\ y \end{matrix})

-t előbb

(\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix})

-val, majd a kapott oszlopot

(\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix})

-val szoroznánk meg; így a két

2 \times 2

-es mátrix szorzatára kapott definíció:

\begin{matrix} (\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix}) \cdot (\begin{matrix} cos α & - sin α \\ sin α & cos α \end{matrix}) =_{}^{def.} \\ =_{}^{def.} (\begin{matrix} cos β cos α - sin β sin α & cos β sin α + sin β cos α \\ cos β sin α + sin β cos α & - sin β sin α + cos β cos α \end{matrix}), \end{matrix}

illetve általában egy

(\begin{matrix} t_{11} & t_{12} \\ t_{21} & t_{22} \end{matrix})

és egy

(\begin{matrix} s_{11} & s_{12} \\ s_{21} & s_{22} \end{matrix})

mátrix szorzata

\begin{matrix} (\begin{matrix} t_{11} & t_{12} \\ t_{21} & t_{22} \end{matrix}) \cdot (\begin{matrix} s_{11} & s_{12} \\ s_{21} & s_{22} \end{matrix}) = (\begin{matrix} t_{11} s_{11} + t_{12} s_{21} & t_{11} s_{12} + t_{12} s_{22} \\ t_{21} s_{11} + t_{22} s_{21} & t_{21} s_{12} + t_{22} s_{22} \end{matrix}); \end{matrix}

pontosan ezzel érjük el, hogy a megfelelő

T

és

S

transzformációk egymás után alkalmazásának (kompozíciójának) a mátrixa a

T

és

S

transzformációk mátrixának a szorzata legyen. Másszóval a (meglehetősen mesterkéltnek tűnő) mátrixszorzás magyarázatát a megfelelő transzformációk kompozíciója adja.
Haladjunk ezután tovább a nevezetes geometriai transzformációk sorában: jelölje ezúttal

T

az origón átmenő, az

x

tengellyel (pontosabban az

\underset{̲}{i}

egységvektorral)

γ

szöget bezáró egyenesre való tükrözést. Az

\underset{̲}{i}

tükörképe éppen az ő

2 γ

szögű elforgatottja, azaz

cos 2 γ \cdot \underset{̲}{i} + sin 2 γ \cdot \underset{̲}{j}

, a

\underset{̲}{j}

tükörképe pedig az

\underset{̲}{i}

képének a

- 90^{\circ}

-os elforgatottja:

sin 2 γ \cdot \underset{̲}{i} - cos 2 γ \cdot \underset{̲}{j}

; a tükrözés mátrixa tehát

(\begin{matrix} cos 2 γ & sin 2 γ \\ sin 2 γ & - cos 2 γ \end{matrix})

.
Ellenőrzésként érdemes megnézni, mi történik, ha egymás után két egyenesre tükrözünk: az első egyenes az

\underset{̲}{i}

egységvektorral

γ

, a második

δ

szöget zárjon be; a két tükrözés kompozíciójának mátrixa a két tükrözés mátrixának szorzata:

\begin{matrix} (\begin{matrix} cos 2 γ & sin 2 γ \\ sin 2 γ & - cos 2 γ \end{matrix}) \cdot (\begin{matrix} cos 2 δ & sin 2 δ \\ sin 2 δ & - cos 2 δ \end{matrix}) = (\begin{matrix} cos 2 (γ - δ) & - sin 2 (γ - δ) \\ sin 2 (γ - δ) & cos 2 (γ - δ) \end{matrix}) . \end{matrix}

Látható, hogy ez éppen a

γ - δ

szög 2-szeresével való forgatásnak a mátrixa, ahol

γ - δ

a két egyenes által bezárt szög. Ezzel beláttuk, hogy két tengelyes tükrözés kompozíciója az egyenesek által bezárt szög kétszeresével való elforgatás az egyenesek metszéspontja körül.
Szakadjunk el most egy rövidebb időre a ,,nevezetes'' geometriai transzformációktól és gondoljunk arra, hogy a látottak mintájára bármely

2 \times 2

-es mátrix segítségével megadhatunk egy transzformációt: ha

(\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix})

egy ilyen mátrix, akkor az

A

transzformáció vigye a tetszőleges

\vec{O P} = x \underset{̲}{i} + y \underset{̲}{j}

vektort

(a_{11} x + a_{12} y) \underset{̲}{i} + (a_{21} x + a_{22} y) \underset{̲}{j}

-be. Ennek így általában nehéz lenne szemléletes geometriai jelentést tulajdonítani; ha azonban például

a_{12} = a_{21} = 0

, akkor látható, hogy

A (x \underset{̲}{i}) = a_{11} x \underset{̲}{i}

és

A (y \underset{̲}{j}) = a_{22} y \underset{̲}{j}

, tehát a transzformáció ‐ legalábbis két irányban ‐ ,,szépen viselkedik'': az

\underset{̲}{i}

irányában

a_{11}

-szeres, a

\underset{̲}{j}

irányában pedig

a_{22}

-szeres középpontos hasonlóságként. Esetünkben ennek az volt az oka, hogy

A

mátrixa,

(\begin{matrix} a_{11} & 0 \\ 0 & a_{22} \end{matrix})

úgynevezett diagonális mátrix. A jelenség azonban szerencsére ennél szélesebb körben fordul elő. Nézzük példaként a

B = (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix})

mátrixot, ami szemlátomást nem diagonális. Viszont

\begin{matrix} (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) \cdot (\begin{matrix} 1 \\ - 1 \end{matrix}) = (\begin{matrix} 1 \\ - 1 \end{matrix}), és (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) \cdot (\begin{matrix} 2 \\ 3 \end{matrix}) = (\begin{matrix} 12 \\ 18 \end{matrix}); \end{matrix}

tehát a mátrixunknak megfelelő

B

transzformáció a

{\underset{̲}{b}}_{1} = \underset{̲}{i} - \underset{̲}{j}

vektort önmagába képezi, a

{\underset{̲}{b}}_{2} = 2 \underset{̲}{i} + 3 \underset{̲}{j}

vektort pedig

12 \underset{̲}{i} + 18 \underset{̲}{j} = 6 {\underset{̲}{b}}_{2}

-be.
Mi ebből a tanulság? A vektorokat ne

\underset{̲}{i}

és

\underset{̲}{j}

, hanem

{\underset{̲}{b}}_{1}

és

{\underset{̲}{b}}_{2}

segítségével írjuk fel! Ekkor ugyanis egy

u {\underset{̲}{b}}_{1} + v {\underset{̲}{b}}_{2}

alakban felírt vektort a

B

transzformáció egyszerűen

u {\underset{̲}{b}}_{1} + 6 v {\underset{̲}{b}}_{2}

-be képezi. Ahhoz, hogy az eredetileg

x \underset{̲}{i} + y \underset{̲}{j}

alakban fölírt vektort ilyen formában megkapjuk, elegendő az

\underset{̲}{i}

és

\underset{̲}{j}

egységvektorokat felírnunk

{\underset{̲}{b}}_{1}

és

{\underset{̲}{b}}_{2}

segítségével:

\begin{matrix} \underset{̲}{i} = \frac{3}{5} {\underset{̲}{b}}_{1} + \frac{1}{5} {\underset{̲}{b}}_{2}, \underset{̲}{j} = - \frac{2}{5} {\underset{̲}{b}}_{1} + \frac{1}{5} {\underset{̲}{b}}_{2}; \end{matrix}

ekkor

\begin{matrix} x \underset{̲}{i} + y \underset{̲}{j} = x (\frac{3}{5} {\underset{̲}{b}}_{1} + \frac{1}{5} {\underset{̲}{b}}_{2}) + y (- \frac{2}{5} {\underset{̲}{b}}_{1} + \frac{1}{5} {\underset{̲}{b}}_{2}) = (\frac{3}{5} x - \frac{2}{5} y) {\underset{̲}{b}}_{1} + (\frac{1}{5} x + \frac{1}{5} y) {\underset{̲}{b}}_{2}, \end{matrix}

így

\begin{matrix} B (x \underset{̲}{i} + y \underset{̲}{j}) = (\frac{3}{5} x - \frac{2}{5} y) {\underset{̲}{b}}_{1} + 6 (\frac{1}{5} x + \frac{1}{5} y) {\underset{̲}{b}}_{2} . \end{matrix}

A mátrixok nyelvén ez azt jelenti, hogy a vektor képének

{\underset{̲}{b}}_{1}

és

{\underset{̲}{b}}_{2}

szerinti

u'

v'

koordinátái (azaz a

{\underset{̲}{b}}_{1}

és

{\underset{̲}{b}}_{2}

irányú összetevőkkel való felírásában a két együttható) az eredeti (

\underset{̲}{i}

\underset{̲}{j}

szerinti)

(x, y)

koordinátákból az

\begin{matrix} (\begin{matrix} u' \\ v' \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 6 \end{matrix}) \cdot (\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) \cdot (\begin{matrix} x \\ y \end{matrix}) \end{matrix}

szerint kaphatók meg. Az eredmény

\underset{̲}{i}

\underset{̲}{j}

szerinti

x'

y'

koordinátáit ebből már könnyű kiszámítani:

\begin{matrix} u' {\underset{̲}{b}}_{1} + v' {\underset{̲}{b}}_{2} = u' (\underset{̲}{i} - \underset{̲}{j}) + v' (2 \underset{̲}{i} + 3 \underset{̲}{j}) = (u' + 2 v') \underset{̲}{i} + (- u' + 3 v') \underset{̲}{j} \end{matrix}

alapján

\begin{matrix} (\begin{matrix} x' \\ y' \end{matrix}) = (\begin{matrix} 1 & 2 \\ - 1 & 3 \end{matrix}) \cdot (\begin{matrix} u' \\ v' \end{matrix}) = (\begin{matrix} 1 & 2 \\ - 1 & 3 \end{matrix}) \cdot (\begin{matrix} 1 & 0 \\ 0 & 6 \end{matrix}) \cdot (\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) \cdot (\begin{matrix} x \\ y \end{matrix}) . \end{matrix}

Mivel az egyenlőség mindkét oldalán az

\underset{̲}{i}

\underset{̲}{j}

szerinti koordináták szerepelnek, a három mátrix szorzata a

B

transzformáció eredeti mátrixát adja, vagyis

\begin{matrix} B = (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) = (\begin{matrix} 1 & 2 \\ - 1 & 3 \end{matrix}) \cdot (\begin{matrix} 1 & 0 \\ 0 & 6 \end{matrix}) \cdot (\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) . \end{matrix}

A kapott háromtényezős előállítás geometriai jelentése tehát a következő. A

B

transzformáció végrehajtását három fázisra bontjuk: először az

\underset{̲}{i}

\underset{̲}{j}

által meghatározott koordináta-rendszerről áttérünk a

{\underset{̲}{b}}_{1}

{\underset{̲}{b}}_{2}

szerinti koordináta-rendszerre ‐ ennek felel meg a jobb szélső tényező; utána a transzformáció szempontjából kellemes rendszer szerint végrehajtjuk

B

-t ‐ ezt mutatja a középső tényező; végül visszatérünk az eredeti

\underset{̲}{i}

\underset{̲}{j}

koordináta-rendszerre ‐ ezt írja le a bal szélső tényező.
Mivel a két szélső mátrix egymással ellentétes, illetve fordított irányú lépést jelenít meg, nem túlságosan meglepő, hogy szorzatuk,

\begin{matrix} (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) \cdot (\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) \cdot (\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) \end{matrix}

a ,,semleges'' ún. egységmátrix, ami a mátrixok szorzására ugyanúgy viselkedik, mint a közönséges számoknál az 1: a vele való szorzás mindent változatlanul hagy. Ennek alapján azt mondjuk, hogy a két mátrix egymás inverze:

(\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix}) = {(\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix})}^{- 1}

, illetve

(\begin{matrix} 3 & 2 \\ 3 & 4 \end{matrix}) = {(\begin{matrix} \frac{3}{5} & - \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} \end{matrix})}^{- 1}

.
A mátrixok iménti ,,diagonalizált'' háromtényezős felírásának egy alkalmazására mutatunk példát a következő részben.

Hatványozás és lineáris rekurziók

A mátrixoknak ez a meglepően messze vezető alkalmazása a lineáris rekurzióval definiált sorozatokkal kapcsolatos. A módszert ‐ az elméleti és a technikai nehézségek kikerülése végett ‐ egy ,,kisméretű'' és jól ismert példán, a Fibonacci-féle sorozaton mutatjuk be, utána próbáljuk majd a kérdést valamivel általánosabban is áttekinteni.
A Fibonacci-féle sorozatot a következőképpen definiáljuk: legyen

f_{0} = 0

f_{1} = 1

, és minden

n \geq 1

-re

f_{n + 1} = f_{n} + f_{n - 1}

. Hogyan kerülnek ide mátrixok? Legyen (minden

n \geq 1

-re)

{\underset{̲}{v}}_{n} = (\begin{matrix} f_{n} \\ f_{n - 1} \end{matrix})

, ekkor a sorozat megadási módjából következően van olyan

2 \times 2

-es

A

mátrix, amelyre

A {\underset{̲}{v}}_{n} = {\underset{̲}{v}}_{n + 1}

\begin{matrix} (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \cdot (\begin{matrix} f_{n} \\ f_{n - 1} \end{matrix}) = (\begin{matrix} f_{n + 1} \\ f_{n} \end{matrix}) . \end{matrix}

Mivel ez minden

n

-re érvényes, alkalmazzuk rendre

n = 1

-re, 2-re, 3-ra stb.:

{\underset{̲}{v}}_{2} = A {\underset{̲}{v}}_{1}

{\underset{̲}{v}}_{3} = A {\underset{̲}{v}}_{2} = A (A {\underset{̲}{v}}_{1}) = A^{2} {\underset{̲}{v}}_{1}

{\underset{̲}{v}}_{4} = A {\underset{̲}{v}}_{3} = A (A^{2} {\underset{̲}{v}}_{1}) = A^{3} {\underset{̲}{v}}_{1}

; látható, hogy általában

{\underset{̲}{v}}_{n + 1} = A^{n} {\underset{̲}{v}}_{1}

. Ahhoz tehát, hogy a sorozat

n

-edik tagját közvetlenül, az

n

függvényében felírhassuk elegendő, ha ebben az értelemben ismerjük az

A

mátrix hatványait. Túl sokat kísérletezni nem érdemes az

A

első néhány hatványának kiszámításával: az egyetlen szabályszerűség, amit észrevehetünk az, hogy

A

hatványaiban maguk a Fibonacci-számok jelennek meg, a kör tehát ebben az irányban bezárul.
Újabb nekifutásként próbáljuk meg felmérni: vajon minden (

2 \times 2

-es) mátrix hatványozása ilyen nehézséggel jár-e. Nem nehéz rájönni, hogy bizonyos speciális mátrixok esetében ez egyáltalán nem így van. Ha például

B = (\begin{matrix} a & 0 \\ 0 & b \end{matrix})

típusú, azaz diagonális mátrix, akkor ,,elemenként'' hatványozható, azaz

B^{n} = (\begin{matrix} a^{n} & 0 \\ 0 & b^{n} \end{matrix})

. Kérdés, hogy a diagonális mátrixoknak ez a kedvező tulajdonsága átörökíthető-e minden mátrixra, vagy legalábbis a (nem diagonális) mátrixok egy részére.
A részleges megoldást pontosan az előző részben megismert felbontás nyújtja! Legyen

M

invertálható mátrix,

B

pedig ezzel megegyező méretű diagonális. Hatványozzuk az

A = M^{- 1} B M

mátrixot:

\begin{matrix} A^{2} & = M^{- 1} B M \cdot M^{- 1} B M = M^{- 1} B^{2} M, \\ A^{3} & = M^{- 1} B M \cdot M^{- 1} B^{2} M = M^{- 1} B^{3} M stb. \end{matrix}

Könnyen látható, hogy (minden

n

-re)

A^{n} = M^{- 1} B^{n} M

, tehát azokat a mátrixokat valóban könnyen tudjuk hatványozni, amelyek

A

-hoz hasonlóan származtathatók egy diagonális mátrixból. Nézzük meg, hogy a Fibonacci-féle sorozattal kapcsolatba hozott

(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})

mátrix előállítható-e ilyen módon. Ennek eldöntéséhez olyan

M = (\begin{matrix} x_{1} & x_{2} \\ y_{1} & y_{2} \end{matrix})

mátrixot keresünk, amelyre

\begin{matrix} (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) = M^{- 1} (\begin{matrix} c_{1} & 0 \\ 0 & c_{2} \end{matrix}) M \end{matrix}

teljesül, alkalmas

c_{i}

számokkal. Mivel ismeretlen mátrix inverzével nagyon kényelmetlen lenne a számolás, szorozzuk meg az egyenlet mindkét oldalát balról

M

-mel:

\begin{matrix} (\begin{matrix} x_{1} & x_{2} \\ y_{1} & y_{2} \end{matrix}) (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} c_{1} & 0 \\ 0 & c_{2} \end{matrix}) (\begin{matrix} x_{1} & x_{2} \\ y_{1} & y_{2} \end{matrix}), azaz (\begin{matrix} x_{1} + x_{2} & x_{1} \\ y_{1} + y_{2} & y_{1} \end{matrix}) = (\begin{matrix} c_{1} x_{1} & c_{1} x_{2} \\ c_{2} y_{1} & c_{2} y_{2} \end{matrix}) . \end{matrix}

A két mátrix megfelelő elemeinek kell egyenlőnek lennie, vagyis

\begin{matrix} x_{1} + x_{2} & = c_{1} x_{1} & y_{1} + y_{2} & = c_{2} y_{1} \\ x_{1} & = c_{1} x_{2} & y_{1} & = c_{2} y_{2}, \end{matrix}

rendezve:

\begin{matrix} (1 - c_{1}) x_{1} + x_{2} & = 0 & x_{1} - c_{1} x_{2} & = 0 \\ (1 - c_{2}) y_{1} + y_{2} & = 0 & y_{1} - c_{2} y_{2} & = 0. \end{matrix}

Itt az első és második egyenletből álló rendszer független a harmadik és negyedik egyenletből álló rendszertől, viszont a két rendszer azonos szerkezetű:

x

helyébe

y

-t,

c_{1}

helyébe

c_{2}

-t írva kapjuk az utóbbit az előbbiből. Az első két egyenlet rendszerét megoldva:

\begin{matrix} x_{1} = c_{1} x_{2}, ebből ((1 - c_{1}) c_{1} + 1) x_{2} = 0. \end{matrix}

x_{2} = 0

esetén

x_{1} = 0

, és így az

M

mátrixnak nem létezne inverze, mivel első sora csupa nulla; ezért

1 + c_{1} - c_{1}^{2} = 0

, azaz

\begin{matrix} c_{1} = \frac{1 \pm \sqrt[]{5}}{2}, és ehhez teljesen hasonlóan c_{2} = \frac{1 \pm \sqrt[]{5}}{2} . \end{matrix}

c_{1}

és

c_{2}

nem lehet egymással egyenlő, mivel akkor (

x_{1} = c_{1} x_{2}

és

y_{1} = c_{2} y_{2}

miatt) az

M

első oszlopa a második oszlop

c_{1} = c_{2}

-szerese volna, és emiatt

M

-nek nem létezne inverze. Válasszuk ezért

c_{1}

-et

\frac{1 + \sqrt[]{5}}{2}

-nek,

c_{2}

-t pedig

\frac{1 - \sqrt[]{5}}{2}

-nek. Az

x_{2}

és az

y_{2}

értéke tetszőleges nemnulla számnak választható, legyen mind a kettő 1; ekkor

\begin{matrix} M = (\begin{matrix} \frac{3 + \sqrt[]{5}}{2} & \frac{1 + \sqrt[]{5}}{2} \\ \frac{3 - \sqrt[]{5}}{2} & \frac{1 - \sqrt[]{5}}{2} \end{matrix}), M^{- 1} = (\begin{matrix} \frac{- 1 + \sqrt[]{5}}{2 \sqrt[]{5}} & \frac{1 + \sqrt[]{5}}{2 \sqrt[]{5}} \\ \frac{3 - \sqrt[]{5}}{2 \sqrt[]{5}} & \frac{- 3 - \sqrt[]{5}}{2 \sqrt[]{5}} \end{matrix}), \end{matrix}

és ezekkel valóban

\begin{matrix} {(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})}^{n} = (\begin{matrix} \frac{- 1 + \sqrt[]{5}}{2 \sqrt[]{5}} & \frac{1 + \sqrt[]{5}}{2 \sqrt[]{5}} \\ \frac{3 - \sqrt[]{5}}{2 \sqrt[]{5}} & \frac{- 3 - \sqrt[]{5}}{2 \sqrt[]{5}} \end{matrix}) (\begin{matrix} {(\frac{1 + \sqrt[]{5}}{2})}^{n} & 0 \\ 0 & {(\frac{1 - \sqrt[]{5}}{2})}^{n} \end{matrix}) (\begin{matrix} \frac{3 + \sqrt[]{5}}{2} & \frac{1 + \sqrt[]{5}}{2} \\ \frac{3 - \sqrt[]{5}}{2} & \frac{1 - \sqrt[]{5}}{2} \end{matrix}) = \\ = (\begin{matrix} \frac{1}{\sqrt[]{5}} [{(\frac{1 + \sqrt[]{5}}{2})}^{n + 1} - {(\frac{1 - \sqrt[]{5}}{2})}^{n + 1}] & \frac{1}{\sqrt[]{5}} [{(\frac{1 + \sqrt[]{5}}{2})}^{n} - {(\frac{1 - \sqrt[]{5}}{2})}^{n}] \\ \frac{1}{\sqrt[]{5}} [{(\frac{1 + \sqrt[]{5}}{2})}^{n} - {(\frac{1 - \sqrt[]{5}}{2})}^{n}] & \frac{1}{\sqrt[]{5}} [{(\frac{1 + \sqrt[]{5}}{2})}^{n - 1} - {(\frac{1 - \sqrt[]{5}}{2})}^{n - 1}] \end{matrix}), \end{matrix}

ebből pedig az

n

-edik Fibonacci-féle számra

\begin{matrix} f_{n} = \frac{1}{\sqrt[]{5}} [{(\frac{1 + \sqrt[]{5}}{2})}^{n} - {(\frac{1 - \sqrt[]{5}}{2})}^{n}] . \end{matrix}

Célunkat a Fibonacci-féle számok explicit előállítására elértük, és az ennek érdekében végzett számolás nyilván minden olyan konkrét esetben célhoz vezet, amikor a hatványozni kívánt mátrix egyáltalán előállítható a kívánt

M^{- 1} B M

alakban ‐ az ilyen mátrixról azt mondjuk, hogy diagonalizálható. Sajnos nem minden mátrix ilyen, például (a Fibonacci-sorozatnak megfelelő mátrixhoz látszólag nagyon hasonló)

(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})

mátrix nem diagonalizálható. (Vigasszal szolgálhat ugyanakkor, hogy ezt a mátrixot nagyon könnyű hatványozni, az első néhány hatványban észrevett szabályszerűséget indukcióval egyszerűen beláthatja az Olvasó.)

A továbbiakban ‐ a

2 \times 2

-es mátrixok keretein túllépve ‐ összefoglaljuk a mátrixokra értelmezett alapvető műveleteket és azok legfontosabb tulajdonságait. Ezután röviden tárgyaljuk az ezekhez szorosan kapcsolódó lineáris egyenletrendszerekre vonatkozó lényegesebb tudnivalókat. Akik ezt a két részt túlságosan száraznak találják, nyugodtan lapozzák át; az utána következő témák részben így is követhetőek lesznek, legfeljebb egy-egy ismeretlen fogalom, jelölés vagy állítás azonosítása végett lesz majd érdemes ide alkalmanként visszatérni.

Műveletek mátrixokkal

Összeadás. Két,

n

darab sorból és

k

oszlopból álló (röviden

n \times k

-as) mátrix összege az az ugyancsak

n \times k

-as mátrix, amelyet a két mátrix megfelelő helyén álló elemek összeadásával kapunk, azaz

\begin{matrix} (\begin{matrix} a_{11} & a_{12} & ... & a_{1 k} \\ a_{21} & a_{22} & ... & a_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & ... & a_{n k} \end{matrix}) + (\begin{matrix} b_{11} & b_{12} & ... & b_{1 k} \\ b_{21} & b_{22} & ... & b_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ b_{n 1} & b_{n 2} & ... & b_{n k} \end{matrix}) = (\begin{matrix} a_{11} + b_{11} & a_{12} + b_{12} & ... & a_{1 k} + b_{1 k} \\ a_{21} + b_{21} & a_{22} + b_{22} & ... & a_{2 k} + b_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} + b_{n 1} & a_{n 2} + b_{n 2} & ... & a_{n k} + b_{n k} \end{matrix}) \end{matrix}

Hasonlóan egyszerűen, illetve természetesen értelmezett egy mátrix számszorosa: az adott mátrix minden elemét szorozzuk meg az illető számmal, vagyis

\begin{matrix} c \cdot (\begin{matrix} a_{11} & a_{12} & ... & a_{1 k} \\ a_{21} & a_{22} & ... & a_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & ... & a_{n k} \end{matrix}) = (\begin{matrix} c a_{11} & c a_{12} & ... & c a_{1 k} \\ c a_{21} & c a_{22} & ... & c a_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ c a_{n 1} & c a_{n 2} & ... & c a_{n k} \end{matrix}) \end{matrix}

Szorzás. Két mátrix szorzatát viszont a következő, kezdetben roppant furcsának tűnő módon értelmezzük. Legyen

A

egy

n \times k

-as,

B

pedig

k \times ℓ

-es mátrix; ekkor

A

és

B

szorzata az az

n \times ℓ

-es

C

mátrix legyen, amelynek

(i, j)

-edik elemét az

A

mátrix

i

-edik sorának és a

B

mátrix

j

-edik oszlopának megfelelő elemeit összeszorozva, e szorzatok összegeként kapjuk:

c_{i j} = a_{i 1} b_{1 j} + a_{i 2} b_{2 j} + ... + a_{i k} b_{k j}

. Hangsúlyozandó, hogy

A

és

B

szorzata ‐ ebben a sorrendben ‐ csak akkor értelmezett, ha

A

-nak annyi oszlopa van, ahány sora

B

-nek, és ekkor az

A B

szorzatnak annyi sora lesz, mint

A

-nak, és annyi oszlopa, mint

B

-nek. Vegyük továbbá észre, hogy

A B

-nek az

(i, j)

-edik eleme az

A

i

-edik sorának (mint

1 \times k

-as mátrixnak) és a

B

j

-edik oszlopának (mint

k \times 1

-es mátrixnak) a szorzata, legalábbis abban az értelemben, hogy az utóbbi

1 \times 1

-es mátrixot azonosítjuk az ő egyetlen elemével. Ebből következik, hogy

A B

-nek a

j

-edik oszlopa megegyezik

A

-nak és

B

j

-edik oszlopának a szorzatával.
Mit mondhatunk ezen műveletek tulajdonságairól? A legtöbb ‐ a számok körében teljesülő ‐ műveleti tulajdonság, illetve azonosság itt is érvényben marad: az

n \times k

-as mátrixok összeadása kommutatív és asszociatív, a csupa nullából álló

0

nullmátrixra

A + 0 = A

teljesül (minden

A

-ra), bármely

A

-nak létezik ellentettje

(- A = (- 1) \cdot A)

amelyre

A + (- A) = 0

. Mátrixoknak számmal és mátrixszal való szorzása egyaránt disztributív az összeadásra nézve:

c (A + B) = c A + c B

M (A + B) = M A + M B

(A + B) D = A D + B D

minden, megfelelő méretű

A

B

M

D

mátrixra. Belátható továbbá, hogy a mátrixszorzás asszociatív: ha

A

B

és

C

megfelelő méretű mátrixok, akkor

(A B) C = A (B C)

.
Baj van viszont a mátrixszorzás kommutativitásával! Ha

A

egy

n \times k

-as,

B

pedig

t \times r

-es mátrix, akkor

A B

értelmezéséhez

k = t

B A

értelmezéséhez

r = n

szükséges; ekkor

A B

mérete

n \times r

, azaz

n \times n

B A

mérete pedig

t \times k

, vagyis

k \times k

. Ahhoz, hogy egyáltalán értelme legyen megkérdezni, vajon

A B

egyenlő-e

B A

-val mindenképpen szükséges, hogy a két szorzat azonos méretű legyen, tehát

A

és

B

egyaránt

n \times n

-es. A szorzás azonban még ebben a meglehetősen korlátozott körben sem kommutatív; pl.

n = 2

-re

(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) \cdot (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) \neq (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) \cdot (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

.
Ez a szorzás egyúttal arra is figyelmeztető példát ad, hogy két mátrix szorzata lehet úgy is nulla, hogy eközben egyik tényező sem az.
A mátrixszorzás ‐ egyelőre csupán a jelölések szintjén ‐ első és talán legtermészetesebb alkalmazása a lineáris egyenletrendszerek terén adódik. Lineáris egyenletrendszeren általában a következő típusú feladatot értjük. Adottak az

a_{i j}

és a

b_{i}

számok, ahol

1 \leq i \leq n

1 \leq j \leq k

(alkalmas

n

és

k

pozitív egészekkel); keresendők mindazon

x_{1}, x_{2}, ..., x_{k}

számok, amelyek eleget tesznek a következő egyenleteknek:

\begin{matrix}  \end{matrix}

a11x1+a12x2+...+a1kxk=b1a21x1+a22x2+...+a2kxk=b2⋮an1x1+an2x2+...+ankxk=bn

(1)

Legyen ekkor

A = (a_{i j})

az egyenletrendszer együtthatóiból álló

n \times k

-as mátrix,

\underset{̲}{b} = (b_{i})

pedig az egyenletek jobb oldalán álló konstansokból képezett

n \times 1

-es (oszlop)mátrix. Ha az ismeretlenekből álló

k \times 1

-es

\underset{̲}{x} = (x_{j})

(oszlop)mátrixot is bevezetjük, akkor az (1) egyenletrendszer ekvivalens az

\begin{matrix} A \underset{̲}{x} = \underset{̲}{b} \end{matrix}

(2)

mátrixegyenlettel, hiszen az

A \underset{̲}{x}

mátrix

i

-edik sora éppen az (1)

i

-edik egyenletének bal oldala. Ez azt sugallja, hogy a lineáris egyenletrendszer megoldásához ,,osztani'' kell(ene) az

A

együttható-mátrixszal. A számok körében végezhető közönséges osztáshoz hasonlóan az osztás a reciprokkal (a multiplikatív inverzzel) történő szorzást jelenti, a reciprok-képzés pedig az 1 osztását. Ehhez először is meg kell találni az 1 szám megfelelőjét a mátrixok körében. Ez nem más, mint az az

n \times n

-es mátrix (tetszőleges

n

-re) amelyben az első sor első, a második sor második,

...

, az

n

-edik sor

n

-edik eleme 1, az összes többi pedig nulla:

\begin{matrix} I_{n} = (\begin{matrix} 1 & 0 & ... & 0 \\ 0 & 1 & ... & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & ... & 1 \end{matrix}) . \end{matrix}

Könnyen ellenőrizhető, hogy

A I_{n} = A

és

I_{n} B = B

valóban teljesül minden

k \times n

-es

A

és

n \times k

-as

B

mátrixra. Mit értsünk ezután egy

n \times k

-as

M

mátrix inverzén? Mivel a mátrixszorzás nem kommutatív, kétfélét is érthetünk: olyan

B

mátrixot, amelyre

B M = I_{k}

, vagy olyan

C

mátrixot, amelyre

M C = I_{n}

. Ilyenkor azt mondjuk, hogy

B

M

-nek balinverze,

C

pedig jobbinverze. A szorzás értelmezéséből közvetlenül adódik, hogy

B

és

C

csakis

k \times n

-es lehet. Egyébként két különböző dologról van szó, azaz egyik tulajdonságból sem következik a másik. Például az

M = (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 2 \end{matrix})

mátrixnak van jobbinverze (több is!), ilyen pl.

C = (\begin{matrix} 1 & - 2 \\ 1 & 1 \\ - 1 & 1 \end{matrix})

, viszont nincs balinverze: az

M

-nek egyenlő az első és a második oszlopa, ezért akármilyen (

3 \times 2

-es)

B

mátrixszal szorozzuk is balról, a szorzatban is megegyezik az első és a második oszlop, így az nem lehet (a

3 \times 3

-as) egységmátrix. Hasonlóan látható, hogy például a csupa 1-esből álló

3 \times 4

-es mátrixnak nincs sem bal, sem jobb oldali inverze. Egyszerűbb a helyzet, ha

M

négyzetes mátrix, azaz

n = k

. Ekkor

M

-nek vagy nem létezik semmilyen oldali inverze sem, vagy egyetlen bal és egyetlen jobb oldali inverze van, és ezek egymással egyenlők; utóbbi esetben ezt az egyértelmű mátrixot hívjuk az

M

inverzének, és

M^{- 1}

-nel jelöljük.
Térjünk vissza ezután az inverzek kiszámításához. Ha például az

n \times k

-as

A

mátrixhoz keresünk egy

B

jobbinverzet, akkor az

A B = I_{n}

mátrixegyenletet kell megoldanunk. Jelölje az

I_{n}

oszlopait rendre

{\underset{̲}{e}}_{1}, {\underset{̲}{e}}_{2}, ..., {\underset{̲}{e}}_{n}

, a

B

mátrix ismeretlen oszlopait pedig

{\underset{̲}{y}}^{(1)}, {\underset{̲}{y}}^{(2)}, ..., {\underset{̲}{y}}^{(n)}

. Ekkor

A B = I_{n}

pontosan azt jelenti, hogy

A {\underset{̲}{y}}^{(i)} = {\underset{̲}{e}}_{i}

, minden

i \leq n

-re. Ez

n

darab ‐ egyenként

n

egyenletből álló ‐ lineáris egyenletrendszert jelent (amelyeknek közös az együttható-mátrixuk). Ebből is látható, hogy a lineáris egyenletrendszerek megoldásának kérdése nem kerülhető meg.

Lineáris egyenletrendszerek

Lineáris egyenletrendszerekkel a középiskolában elsősorban a koordináta-geometriában találkozhatunk: például két egyenes közös részének meghatározásához az egyenesek egyenleteiből álló lineáris egyenletrendszert kell megoldani: ha mindkét ismeretlenre egyértelmű megoldás adódik, az azt jelenti, hogy az egyenesek egy pontban metszik egymást; ha nincs megoldás, akkor az egyenesek párhuzamosak.
A következőkben röviden ismertetjük a lineáris egyenletrendszerek megoldásának egyik módszerét, amelyet Gauss-féle kiküszöbölésnek (eliminációnak) neveznek. Tekintsük ehhez az (1) egyenletrendszert, és jelöljük az

i

-edik egyenletét

E_{i}

-vel. Az eljárás során az egyenleteket úgy alakítjuk át, hogy egyrészt a rendszer megoldásainak halmaza ne változzon, másrészt az átalakítások sorozata olyan egyenletrendszerre vezessen, amiből a megoldás közvetlenül leolvasható. E kettős célt a következő két lépés megfelelő számú alkalmazásával érjük el:

(a)

E_{i} \to E_{i}' = c E_{i}

, ahol

c \neq 0

(az

i

-edik egyenletet úgy változtatjuk, hogy mindkét oldalát megszorozzuk a nemnulla

c

számmal);

(b)

E_{i} \to E_{i}' = E_{i} + d E_{j}

, ahol

d

tetszőleges szám és

j \neq i

(az

i

-edik egyenletet úgy változtatjuk, hogy hozzádjuk a

j

-edik egyenlet

d

-szeresét; a

j

-edik egyenlet természetesen változatlan marad).

Mind a kétféle lépés olyan, hogy a rendszer egyetlen egyenletét változtatja csak meg. Az (a) esetén világos, hogy az új,

E_{i}'

egyenlet ekvivalens az eredeti

E_{i}

-vel, így a kapott új egyenletrendszernek ugyanazok a megoldásai, mint az eredetinek. A (b) alkalmazása esetén az látszik, hogy a kapott új,

E_{i}'

egyenlet az

E_{i}

és az

E_{j}

egyenletek együttes következménye, ezért az így kapott új egyenletrendszernek az eredeti rendszer minden megoldása továbbra is megoldása marad. Ez azonban fordítva is igaz, mivel az új egyenletrendszerből következményként visszakaphatjuk a régit: csupán a megváltozott

i

-edik egyenletet kell következményként visszaállítani, ami egyszerű:

E_{i} = E_{i}' - d E_{j}

.
Tudva, hogy az (a) és (b) típusú lépésekkel az eredetivel ekvivalens egyenletrendszerekhez jutunk, már csak arra kell törekedni, hogy ezek segítségével egyre ,,szebb'' alakúra formáljuk (1)-et. Tegyük fel ehhez, hogy

a_{11} \neq 0

; ha

a_{11} = 0

, akkor változtassuk meg az ismeretlenek számozását és szükség esetén az egyenletek sorrendjét is úgy, hogy az ekként adódó

a_{11}'

együttható már ne legyen nulla; ha ezt még így sem tudjuk elérni az azt jelenti, hogy mindegyik

x_{i}

ismeretlen együtthatója minden egyenletben nulla, tehát egyenleteink valamennyien

0 = b_{i}

alakúak. Ekkor nincs is több teendőnk: ha valamelyik

b_{i}

értéke nullától különböző, akkor az egyenletrendszernek nincs megoldása (hiszen tartalmaz ,,nulla = nemnulla'' típusú egyenletet), míg abban az esetben, ha minden

b_{i}

értéke nulla, az egyenletrendszernek minden szám

k

-as megoldása.
Tegyük fel tehát, hogy

a_{11} \neq 0

. Az (a) lépést az első egyenletre alkalmazva elérhető, hogy

a_{11} = 1

legyen. Ezután a (b) lépést alkalmazzuk egymás után a második, harmadik,

...

n

-edik egyenletre úgy, hogy rendre kivonjuk belőlük az első egyenlet

a_{21}

-szeresét,

...

a_{n 1}

-szeresét. Így az

x_{1}

együtthatója az első egyenletben 1, a többiben pedig nulla.
Folytassuk az eljárást, ezúttal az első egyenletre koncentrált lépéssorozatot a második egyenletre irányítva: szeretnénk, hogy a második egyenletben

x_{2}

aktuális

a_{22}'

együtthatója ne legyen nulla. Ha az

x_{2}, ..., x_{k}

ismeretlenek átszámozásával és a másodiktól az

n

-edikig terjedő egyenletek sorrendjének megváltoztatásával sem érhető ez el, akkor a korábbiakhoz hasonlóan ezek mind

0 = b_{i}'

alakúak, és az egyenletrendszernek vagy nincs megoldása, vagy (ha

b_{2}', ..., b_{n}'

mindegyike nulla) az

x_{2}, ..., x_{k}

ismeretlenek értéke tetszőleges lehet, az

x_{1}

pedig az első egyenletből ezekkel kifejezhető. Feltéve, hogy

a_{22}' \neq 0

, a második egyenletet

a_{22}'

-vel osztva elérjük, hogy

a_{22}' = 1

; ezután alkalmazzuk a (b) lépést úgy, hogy az első, a harmadik,

...

n

-edik egyenletből rendre kivonjuk a második egyenlet

a_{12}'

-szeresét,

...

a_{n 2}'

-szeresét. Ezzel

x_{2}

együtthatója a második egyenletben 1, a többiben pedig nulla ‐ miközben

x_{1}

,,kellemes'' együtthatói sehol nem változnak.
Az eljárást ezután a harmadik egyenletre és

x_{3}

együtthatóinak kiritkítására összpontosítva folytatjuk stb. Végül (az ismeretlenek esetleges átszámozását és az egyenletek sorrendjének megváltoztatását is megengedve) az egyenletrendszer a következő alakot ölti:

\begin{matrix}  \end{matrix}

x1+c1,r+1xr+1+...+c1,kxk=d1x2+c2,r+1xr+1+...+c2,kxk=d2⋱xr+cr,r+1xr+1+...+cr,kxk=dr0=dr+1⋮0=dn

(3)

d_{r + 1}, ..., d_{n}

valamelyike nullától különböző, akkor nincs megoldás, egyébként az

x_{r + 1}, ..., x_{k}

ismeretlenek értéke tetszőlegesen megválasztható, ezekkel pedig

x_{1}, ..., x_{r}

rendre kifejezhető az első

r

egyenletből

\begin{matrix} x_{i} = d_{i} - (c_{i, r + 1} x_{r + 1} + ... + c_{i, k} x_{k}) \end{matrix}

szerint. Vegyük észre, hogy ha van megoldás, és

n < k

(vagyis több ismeretlen van, mint ahány egyenlet), akkor az egyenletrendszernek biztosan egynél több megoldása van, hiszen ekkor

r \leq n < k

miatt lesznek olyan ismeretlenek, amelyek értéke szabadon megválasztható. E megállapítás roppant fontos speciális esete a következő:

(*)

Tegyük fel, hogy az (1) egyenletrendszerben

b_{1} = ... = b_{n} = 0

‐ az ilyen egyenletrendszert homogénnek nevezzük. Homogén lineáris egyenletrendszernek biztosan van megoldása, nyilván ilyen például

x_{1} = x_{2} = ... = x_{k} = 0

(ezt szokás a rendszer triviális megoldásának nevezni). Ha ilyenkor

n < k

, akkor a fentiek szerint létezik az egyenletrendszernek a triviálistól különböző megoldása is, ahol tehát nem mindegyik

x_{i}

értéke nulla.

Lineáris kombináció, függetlenség, bázis

Ebben a részben a mátrixműveletek közül elsősorban az összeadásra és a számmal való szorzásra lesz szükség.
Legyenek

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{k}

n \times 1

-es oszlopmátrixok és legyenek

x_{1}, x_{2}, ..., x_{k}

tetszőleges számok. Az

\begin{matrix} x_{1} {\underset{̲}{v}}_{1} + x_{2} {\underset{̲}{v}}_{2} + ... + x_{k} {\underset{̲}{v}}_{k} \end{matrix}

kifejezést (ami ugyancsak egy

n \times 1

-es oszlopmátrix) a

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{k}

rendszer elemeinek az

x_{1}, x_{2}, ..., x_{k}

együtthatókkal képezett lineáris kombinációjának hívjuk. Ha az összes

x_{i}

együttható nulla, akkor nyilván a kombináció értéke a csupa nullából álló oszlopmátrix. Ha az együtthatók minden más értéke esetén (vagyis ha nem mindegyikük nulla) a kombináció sosem egyenlő a csupa nullából álló oszlopmátrixszal, akkor a

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{k}

rendszert (lineárisan) függetlennek nevezzük. Azt mondjuk továbbá, hogy a rendszer (lineárisan) összefüggő, ha nem független, azaz létezik olyan nemtriviális lineáris kombinációja, ami a csupa nullából álló

\underset{̲}{0}

oszlopmátrixot adja.
Hogyan dönthető el, hogy egy rendszer független-e? Meg kell vizsgálni, hogy az

x_{i}

számok mely értékére lesz a velük képezett lineáris kombináció

\underset{̲}{0}

, azaz meg kell oldanunk az

x_{1} {\underset{̲}{v}}_{1} + x_{2} {\underset{̲}{v}}_{2} + ... + x_{k} {\underset{̲}{v}}_{k} = \underset{̲}{0}

egyenletet. Ha

{\underset{̲}{v}}_{j} = (\begin{matrix} a_{1 j} \\ a_{2 j} \\ ⋮ \\ a_{n j} \end{matrix})

, akkor

\begin{matrix} (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}) = x_{1} (\begin{matrix} a_{11} \\ a_{21} \\ ⋮ \\ a_{n 1} \end{matrix}) + x_{2} (\begin{matrix} a_{12} \\ a_{22} \\ ⋮ \\ a_{n 2} \end{matrix}) + ... + x_{k} (\begin{matrix} a_{1 k} \\ a_{2 k} \\ ⋮ \\ a_{n k} \end{matrix}) = (\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + ... + a_{1 k} x_{k} \\ a_{21} x_{1} + a_{22} x_{2} + ... + a_{2 k} x_{k} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + ... + a_{n k} x_{k} \end{matrix}), \end{matrix}

azaz ‐ a két szélső oszlopmátrix megfelelő elemeit egyenlővé téve ‐ egy homogén lineáris egyenletrendszert kell megoldanunk (pl. az ismertetett Gauss-féle elimináció módszerével). Ha megoldásként csak a triviális adódik, akkor a rendszer független, egyébként pedig összefüggő.
Könnyen látható, hogy független rendszer bármelyik elemét elhagyva a megmaradó rendszer is független. Az is gyorsan ellenőrizhető, hogy az

I_{n}

egységmátrix oszlopai független rendszert alkotnak. Megállapíthatjuk tehát, hogy az

n \times 1

-es oszlopmátrixok körében létezik egyelemű, kételemű, háromelemű,

...

n

-elemű független rendszer. Vajon létezik-e

n

-nél több elemű is? A válasz nemleges: ha

k > n

, akkor egy

n \times 1

-es oszlopmátrixokból álló

k

-elemű rendszer biztosan összefüggő, hiszen ennek eldöntéséhez egy

n

egyenletből álló,

k

-ismeretlenes homogén lineáris egyenletrendszert kell megoldanunk, amiről viszont

(*)

szerint tudjuk, hogy létezik nemtriviális megoldása.
Mit mondhatunk a maximális, azaz

n

-elemű független rendszerekről? Tegyük fel, hogy

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{n}

egy ilyen rendszer. Ha ehhez még hozzáveszünk egy tetszőleges

n \times 1

-es

\underset{̲}{z}

oszlopmátrixot, akkor az így kapott

n + 1

-elemű rendszer összefüggő, azaz van olyan nemtriviális lineáris kombinációja, ami nulla:

\begin{matrix} x_{1} {\underset{̲}{v}}_{1} + x_{2} {\underset{̲}{v}}_{2} + ... + x_{n} {\underset{̲}{v}}_{n} + y \underset{̲}{z} = \underset{̲}{0} . \end{matrix}

(4)

Megmutatjuk, hogy itt

y \neq 0

. Tegyük föl ugyanis, hogy

y = 0

, ekkor (4)-ből az marad, hogy

x_{1} {\underset{̲}{v}}_{1} + x_{2} {\underset{̲}{v}}_{2} + ... + x_{n} {\underset{̲}{v}}_{n} = \underset{̲}{0}

. A

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{n}

rendszer azonban független, így ez csak a triviális lineáris kombináció lehet, azaz

x_{1} = ... = x_{n} = 0

. Ellentmondásra jutottunk, hiszen a (4)-ben látható kombináció nemtriviális. Tehát

y \neq 0

; ekkor

\underset{̲}{z}

-t könnyen kifejezhetjük (4)-ből:

\underset{̲}{z} = (- \frac{x_{1}}{y}) {\underset{̲}{v}}_{1} + (- \frac{x_{2}}{y}) {\underset{̲}{v}}_{2} + ... + (- \frac{x_{n}}{y}) {\underset{̲}{v}}_{n}

.
Azt kaptuk, hogy

{\underset{̲}{v}}_{1}, {\underset{̲}{v}}_{2}, ..., {\underset{̲}{v}}_{n}

lineáris kombinációjaként minden

n \times 1

-es oszlopmátrix kifejezhető; az ilyen tulajdonságú független rendszert bázisnak nevezzük.

Sajátérték és determináns

Próbáljunk meg a Fibonacci-sorozatnál alkalmazott számolás hátterére is egy pillantást vetni. Tegyük fel ezért, hogy

A

egy olyan

n \times n

-es mátrix, amely előáll

M^{- 1} B M

alakban, alkalmas

B = (\begin{matrix} c_{1} & 0 & ... & 0 \\ 0 & c_{2} & ... & 0 \\ ⋮ & ⋱ \\ 0 & ... & c_{n} \end{matrix})

diagonális mátrixszal. Jelölje ezúttal is

{\underset{̲}{e}}_{i}

n \times n

-es egységmátrix

i

-edik oszlopát. Ne feledjük, hogy egy tetszőleges

n \times n

-es

G

mátrixot az

{\underset{̲}{e}}_{i}

-vel jobbról megszorozva eredményül a

G

i

-edik oszlopát kapjuk. Tekintsük ezután a keresett

M

mátrix inverzének az

i

-edik oszlopát, vagyis az

n_{i} = M^{- 1} {\underset{̲}{e}}_{i}

szorzatot. Erre

\begin{matrix} A \cdot {\underset{̲}{n}}_{i} = M^{- 1} B M \cdot M^{- 1} {\underset{̲}{e}}_{i} = M^{- 1} B {\underset{̲}{e}}_{i} = M^{- 1} (\begin{matrix} 0 \\ ⋮ \\ c_{i} \\ ⋮ \\ 0 \end{matrix}) = M^{- 1} (c_{i} {\underset{̲}{e}}_{i}) = c_{i} M^{- 1} {\underset{̲}{e}}_{i} = c_{i} {\underset{̲}{n}}_{i} . \end{matrix}

Kiderült, hogy

{\underset{̲}{n}}_{i}

olyan (nem

\underset{̲}{0}

) oszlopmátrix, amely az

A

-val balról megszorozva a

c_{i}

-szeresére változik. Azt mondjuk ilyenkor, hogy

{\underset{̲}{n}}_{i}

A

sajátvektora, és

c_{i}

A

mátrix

{\underset{̲}{n}}_{i}

-hez tartozó sajátértéke. Tehát

M^{- 1}

oszlopai valamennyien sajátvektorai

A

-nak. Megmutatjuk, hogy ez már jellemzi is a megfelelő

M^{- 1}

mátrixokat: ha

N : = M^{- 1}

olyan invertálható mátrix, amelynek oszlopai az

A

-nak sajátvektorai, akkor

B : = M A M^{- 1}

diagonális mátrix (főátlójában

A

sajátértékeivel), azaz

A = M^{- 1} B A

diagonalizálható. Jelölje ehhez ismét

{\underset{̲}{n}}_{i}

N : = M^{- 1}

mátrix

i

-edik oszlopát, ekkor feltételezésünk szerint

A M^{- 1} = A N

-nek az

i

-edik oszlopa

A {\underset{̲}{n}}_{i} = c_{i} {\underset{̲}{n}}_{i}

, ezért

M A M^{- 1} = M (A M^{- 1})

-nek az

i

-edik oszlopa

M (c_{i} {\underset{̲}{n}}_{i}) = c_{i} (M {\underset{̲}{n}}_{i}) = c_{i} (M (M^{- 1}

i

-edik oszlopa

)) = c_{i} (M M^{- 1}

i

-edik oszlopa

) = c_{i} (I_{n}

i

-edik oszlopa

) = (\begin{matrix} 0 \\ ⋮ \\ c_{i} \\ ⋮ \\ 0 \end{matrix})

; tehát valóban

\begin{matrix} M A M^{- 1} = (\begin{matrix} c_{1} & 0 & ... & 0 \\ 0 & c_{2} & ... & 0 \\ ⋮ & ⋱ \\ 0 & ... & c_{n} \end{matrix}) \end{matrix}

diagonális.
A kapott eredmények szerint egy

n \times n

-es mátrix pontosan akkor diagonalizálható, ha bizonyos sajátvektoraiból mint oszlopokból összeállítható egy invertálható

n \times n

-es mátrix.
A kapott feltétel nyomán rögtön szemben találjuk magunkat a következő kérdéssel: hogyan határozhatjuk meg a sajátvektorokat?
A válasz kezdetben egyszerűnek tűnik: ha ismerjük az

A

mátrix sajátértékeit, akkor egy adott

c_{i}

sajátértékhez tartozó sajátvektorok meghatározása az

\begin{matrix} A \underset{̲}{x} = c_{i} \underset{̲}{x} \end{matrix}

(5)

homogén lineáris egyenletrendszer nemtriviális megoldásainak a megkeresését jelenti, ez tehát (már) nem probléma. De honnan tudjuk (előre), hogy mik az

A

sajátértékei? Az (5) szerint ezek éppen azok a

c_{i}

számok, amelyekre az

A \underset{̲}{x} - c_{i} \underset{̲}{x} = \underset{̲}{0}

, illetve ‐ némileg átrendezve ‐ az

(A - c_{i} I_{n}) \underset{̲}{x} = \underset{̲}{0}

homogén lineáris egyenletrendszernek létezik a triviálistól különböző megoldása. A korábbiakra visszaemlékezve láthatjuk, hogy ez éppen akkor következik be, amikor az

A - c_{i} I_{n}

mátrix oszlopainak rendszere lineárisan összefüggő. Persze ismerjük az eljárást, amivel adott

c_{i}

esetén ez eldönthető; de

c_{i}

ismeretlen lévén kedvezőbb lenne, ha az összefüggőség kérdését egy képletbe való behelyettesítéssel dönthetnénk el. Ilyen formula valóban létezik, a neve determináns; illusztrációként

2 \times 2

-es mátrixokra készítjük el.
Legyen a kérdéses mátrix

D = (\begin{matrix} d_{11} & d_{12} \\ d_{21} & d_{22} \end{matrix})

. A

\begin{matrix} {\underset{̲}{d}}_{1} = (\begin{matrix} d_{11} \\ d_{21} \end{matrix}), {\underset{̲}{d}}_{2} = (\begin{matrix} d_{12} \\ d_{22} \end{matrix}) \end{matrix}

oszlopok rendszere pontosan akkor összefüggő, ha léteznek olyan

x_{1}

és

x_{2}

számok, amelyek közül legalább az egyik nem nulla, és

x_{1} {\underset{̲}{d}}_{1} + x_{2} {\underset{̲}{d}}_{2} = \underset{̲}{0}

. Ha például

x_{2} \neq 0

, akkor

{\underset{̲}{d}}_{2} = - \frac{x_{1}}{x_{2}} {\underset{̲}{d}}_{1}

, azaz

(\begin{matrix} d_{12} \\ d_{22} \end{matrix}) = - \frac{x_{1}}{x_{2}} (\begin{matrix} d_{11} \\ d_{21} \end{matrix})

. Ez éppen azt jelenti, hogy a

d_{12} : d_{11}

és a

d_{22} : d_{21}

arányok egyenlők (ugyanígy, ha

x_{1} \neq 0

), azaz

d_{12} d_{21} = d_{11} d_{22}

, illetve

d_{11} d_{22} - d_{12} d_{21} = 0

. A

D = (\begin{matrix} d_{11} & d_{12} \\ d_{21} & d_{22} \end{matrix})

determinánsa tehát

det D = d_{11} d_{22} - d_{12} d_{21}

, ami pontosan akkor nulla, ha

D

oszlopai lineárisan összefüggő rendszert alkotnak.
Ellenőrizzük mindezt a Fibonacci-sorozat mátrixára:

\begin{matrix} 0 = det ((\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) - c_{i} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})) = det (\begin{matrix} 1 - c_{i} & 1 \\ 1 & - c_{i} \end{matrix}) = (1 - c_{i}) (- c_{i}) - 1 \cdot 1 = c_{i}^{2} - c_{i} - 1, \end{matrix}

az ismerős másodfokú egyenlet.
Általában egy

n \times n

-es mátrix determinánsa olyan, a mátrix elemeiből képezett szorzatok előjeles összege, ahol ‐ minden lehetséges módon ‐ minden sorból és oszlopból kiválasztunk egy-egy (összesen

n

) elemet, és az értéke pontosan akkor nulla, ha a mátrix oszlopai összefüggő rendszert alkotnak. Elmondható tehát, hogy egy

n \times n

-es mátrix sajátvektorainak és sajátértékeinek meghatározása egy

n

-edfokú egyenlet és

n

darab, egyenként

n

egyenletből álló,

n

-ismeretlenes (homogén) lineáris egyenletrendszer megoldását igényli.

Egy kombinatorikai alkalmazás

Legyen

H

egy

n

-elemű véges halmaz,

A_{1}, A_{2}, ..., A_{k}

pedig különböző részhalmazai

H

-nak. Kérdés: legfeljebb mennyi lehet a

k

, ha az

A_{i}

részhalmazok közül bármely kettőnek (mármint két különbözőnek) pontosan egy közös eleme van?
A kérdésben szereplő ,,legfeljebb'' szó jogosságát az mutatja, hogy

k

-nak (

n

-hez képest) kicsi értékeire ‐ például

k = 1,2,3

-ra ‐ nagyon könnyű ilyen részhalmazokat megadni, viszont

k

növekedtével a metszetfeltétel egyre erősebb korlátozást jelent. Némi gondolkozás után azonban eszünkbe juthat a következő konfiguráció, amivel

k = n

elérhető: Legyen

H = {h_{1}, h_{2}, ..., h_{n}}

, és legyen

A_{1} = {h_{1}}

A_{2} = {h_{1}, h_{2}}

A_{3} = {h_{1}, h_{3}}

...

A_{n} = {h_{1}, h_{n}}

; itt bármely két részhalmaz metszete

{h_{1}}

. Egy másik, ehhez hasonló lehetőség:

A_{1} = {h_{2}, h_{3}, ..., h_{n}}

A_{2} = {h_{1}, h_{2}}

A_{3} = {h_{1}, h_{3}}

...

A_{n} = {h_{1}, h_{n}}

. A kérdés ezután úgy módosítható, hogy lehet-e

k

n

-nél nagyobb. Megmutatjuk, hogy nem lehet. Ehhez mátrixokat használunk majd és azt az eredményt, hogy

n \times 1

-es oszlopmátrixokból álló független rendszernek legfeljebb

n

eleme lehet.
Előbb azonban térjünk vissza az elsőként talált konfigurációhoz. Ennek jellegzetessége, hogy az egyik részhalmaz egyelemű. Ha egy, a probléma feltételét kielégítő konfigurációról tudjuk, hogy az egyik részhalmaz egyelemű, akkor az szükségképpen része a többi részhalmaznak, hiszen a velük alkotott metszet csak úgy állhat egyetlen elemből. Ekkor viszont ez az elem alkotja bármely két részhalmaznak is a közös részét, ezért a többi

k - 1

részhalmaznak ezen elemet nem tartalmazó része páronként diszjunkt halmazrendszert alkot. Mivel ezek egy

n - 1

elemű halmaz nemüres részei, számuk legfeljebb

n - 1

lehet. Tehát

k - 1 \leq n - 1

, azaz

k \leq n

. A továbbiakban ezért elegendő azokkal az esetekkel foglalkoznunk, amikor mindegyik

A_{i}

részhalmaznak legalább két eleme van.
Az

A_{j}

részhalmazokhoz oszlopmátrixokat rendelünk. Legyen

{\underset{̲}{a}}_{j} = (\begin{matrix} a_{1, j} \\ a_{2, j} \\ ⋮ \\ a_{n, j} \end{matrix})

, ahol

\begin{matrix} a_{i, j} = {\begin{matrix} 1, ha h_{i} \in A_{j}, \\ 0, ha h_{i} \notin A_{j} . \end{matrix} \end{matrix}

Tetszőleges

\underset{̲}{c} = (\begin{matrix} c_{1} \\ c_{2} \\ ⋮ \\ c_{n} \end{matrix})

oszlopmátrix transzponáltjának hívjuk a

{\underset{̲}{c}}^{T} = (\begin{matrix} c_{1} & c_{2} & ... & c_{n} \end{matrix})

sormátrixot. A módszer azon az egyszerű észrevételen alapul, hogy

\begin{matrix} {\underset{̲}{a}}_{j}^{T} \cdot {\underset{̲}{a}}_{ℓ} = | A_{j} \cap A_{ℓ} | = {\begin{matrix} | A_{j} | \geq 2, & ha j = ℓ, \\ 1, & ha j \neq ℓ . \end{matrix} \end{matrix}

(6)

Megmutatjuk, hogy az

a_{1}, a_{2}, ..., a_{k}

rendszer lineárisan független; ebből a korábban látottak szerint valóban következik majd, hogy

k \leq n

. Vizsgálnunk kell, hogy milyen lineáris kombinációjuk

\underset{̲}{0}

. Tegyük föl ezért, hogy

\begin{matrix} x_{1} {\underset{̲}{a}}_{1} + x_{2} {\underset{̲}{a}}_{2} + ... + x_{k} {\underset{̲}{a}}_{k} = \underset{̲}{0}, \end{matrix}

ekkor (6) szerint nyilván

\begin{matrix} 0 & = {\underset{̲}{0}}^{T} \cdot \underset{̲}{0} = {(\sum_{j = 1}^{k} x_{j} {\underset{̲}{a}}_{j})}^{T} \cdot (\sum_{t = 1}^{k} x_{t} {\underset{̲}{a}}_{t}) = \sum_{j = 1}^{k} x_{j}^{2} {\underset{̲}{a}}_{j}^{T} \cdot {\underset{̲}{a}}_{j} + \sum_{j \neq t} x_{j} x_{t} {\underset{̲}{a}}_{j}^{T} \cdot {\underset{̲}{a}}_{t} = \\ = \sum_{j = 1}^{k} | A_{j} | x_{j}^{2} + \sum_{j \neq t} x_{j} x_{t} = \sum_{j = 1}^{k} (| A_{j} | - 1) x_{j}^{2} + {(\sum_{j = 1}^{k} x_{j})}^{2} . \end{matrix}

Itt a második összeg négyzete nemnegatív, az elsőben minden összeadandó szorzat nemnegatív, és a szorzatok

| A_{j} | - 1

tényezője pozitív. A teljes összeg ezért csak úgy lehet nulla, ha minden

x_{j} = 0

. Tehát

{\underset{̲}{a}}_{1}, {\underset{̲}{a}}_{2}, ..., {\underset{̲}{a}}_{k}

valóban lineárisan független.

Miután beláttuk, hogy legfeljebb

n

részhalmaz választható ki az előírt módon, felvetődik a kérdés, vajon mit lehet mondani azokról az esetekről, amikor éppen a maximális számú,

n

halmazból áll a rendszer. A kezdetben talált két konfiguráció alapján gondolhatjuk, hogy még sok, esetleg bonyolultabb szerkezetű példa is van, vagy ellenkezőleg: bizonyítékot kereshetünk arra, hogy további példákra nem nagyon számíthatunk, esetleg nincs is más a már találtakon kívül. Szerencsére nem kell előre eldönteni, melyik irányban próbálkozzunk ‐ csupán használnunk kell azokat az oszlopmátrixokat, amelyekbe a részhalmazok adatait kódoltuk. Annyit azért érdemes elöljáróban észrevenni, hogy egy ilyen

n

tagból álló halmazrendszer szükségképpen lefedi a

H

-t: ha ugyanis lenne a

H

-nak olyan

h

eleme, ami egyik

A_{i}

részhalmazban sincs benne, akkor valamennyi

A_{i}

n - 1

elemű

H ∖ {h}

halmaznak lenne része; de ott a bizonyítottak szerint legfeljebb

n - 1

ilyen részhalmazból álló rendszer található.

Tegyük fel tehát, hogy az

A_{1}, A_{2}, ..., A_{n}

páronként különböző részhalmazai az

n

-elemű

H = {h_{1}, h_{2}, ..., h_{n}}

halmaznak, mindegyikük legalább kételemű, és bármely kettőnek egyetlen közös eleme van. Láttuk, hogy ekkor a nekik megfelelő

{\underset{̲}{a}}_{1}, {\underset{̲}{a}}_{2}, ..., {\underset{̲}{a}}_{n}

oszlopmátrixok rendszere lineárisan független. Tudjuk viszont, hogy

n

-elemű független rendszerként bázist is alkotnak! Ez azt jelenti, hogy minden

n \times 1

-es oszlopmátrix előállítható az

{\underset{̲}{a}}_{1}, {\underset{̲}{a}}_{2}, ..., {\underset{̲}{a}}_{n}

lineáris kombinációjaként. Használjuk ezt fel az

I_{n}

egységmátrix

{\underset{̲}{e}}_{1}, {\underset{̲}{e}}_{2}, ..., {\underset{̲}{e}}_{n}

oszlopaira:

\begin{matrix} {\underset{̲}{e}}_{i} = \sum_{j = 1}^{n} y_{i, j} {\underset{̲}{a}}_{j} . \end{matrix}

(7)

Mielőtt továbbmennénk, vezessük be a következő jelölést: legyen

\begin{matrix} δ_{i, A_{j}} = {\begin{matrix} 1, & ha h_{i} \in A_{j}, \\ 0, & ha h_{i} \notin A_{j} . \end{matrix} \end{matrix}

Így (6) és (7) szerint

\begin{matrix} δ_{i, A_{k}} & = {\underset{̲}{a}}_{k}^{T} \cdot {\underset{̲}{e}}_{i} = {\underset{̲}{a}}_{k}^{T} \cdot \sum_{j = 1}^{n} y_{i, j} {\underset{̲}{a}}_{j} . = \sum_{j = 1}^{n} y_{i, j} {\underset{̲}{a}}_{k}^{T} \cdot {\underset{̲}{a}}_{j} = \sum_{j = 1}^{n} y_{i, j} | A_{k} \cap A_{j} | = \\ = y_{i, k} | A_{k} | + \sum_{j : j \neq k} y_{i, j} = y_{i, k} (| A_{k} | - 1) + \sum_{j = 1}^{n} y_{i, j} . \end{matrix}

Legyen

y_{i} = \sum_{j = 1}^{n} y_{i, j}

, ekkor tehát

\begin{matrix} δ_{i, A_{k}} = y_{i, k} (| A_{k} | - 1) + y_{i}, \end{matrix}

innen pedig

\begin{matrix} y_{i, k} = \frac{δ_{i, A_{k}} - y_{i}}{| A_{k} | - 1}, \end{matrix}

(8)

amiből ‐

y_{i}

definíciója alapján ‐

\begin{matrix} y_{i} = \sum_{k = 1}^{n} y_{i, k} = \sum_{j = 1}^{n} \frac{δ_{i, A_{k}} - y_{i}}{| A_{k} | - 1} . \end{matrix}

Ebből kifejezhető

y_{i}

\begin{matrix} y_{i} (1 + \sum_{k = 1}^{n} \frac{1}{| A_{k} | - 1}) = \sum_{k = 1}^{n} \frac{δ_{i, A_{k}}}{| A_{k} | - 1} = \sum_{k : h_{i} \in A_{k}}^{} \frac{1}{| A_{k} | - 1}, \end{matrix}

azaz

\begin{matrix} y_{i} = (\sum_{k : h_{i} \in A_{k}}^{} \frac{1}{| A_{k} | - 1}) / (1 + \sum_{k = 1}^{n} \frac{1}{| A_{k} | - 1}) . \end{matrix}

Itt a számláló és a nevező egyaránt pozitív, és a számláló kisebb a nevezőnél; ezért

\begin{matrix} 0 < y_{i} < 1. \end{matrix}

A (8)-cal összevetve ebből az következik, hogy

h_{i} \in A_{k}

esetén

y_{i, k}

pozitív,

h_{i} \notin A_{k}

esetén pedig negatív.
Legyen most

j \neq i

, de egyébként

i, j \leq n

tetszőleges. Ekkor (6) és (7) alapján

\begin{matrix} 0 = {\underset{̲}{e}}_{j}^{T} \cdot \underset{̲}{e_{i}} = {\underset{̲}{e}}_{j}^{T} \cdot \sum_{k = 1}^{n} y_{i, k} {\underset{̲}{a}}_{k} = \sum_{k = 1}^{n} y_{i, k} {\underset{̲}{e}}_{j}^{T} \cdot {\underset{̲}{a}}_{k} = \sum_{k = 1}^{n} y_{i, k} δ_{j, A_{k}} = \sum_{k : h_{j} \in A_{k}}^{} y_{i, k} . \end{matrix}

Egy nulla értékű (és ‐ mivel a halmazrendszer lefedi

H

-t ‐ nem üres) összeget kaptunk, amelyben egyik tag sem nulla; így lennie kell a tagok között pozitívnak. Ha

y_{i, k}

egy ilyen tag, akkor a következő két dolgot tudjuk róla: 1.

h_{i} \in A_{k}

, hiszen

y_{i, k}

pozitív; 2.

h_{j} \in A_{k}

, mivel a tag a fenti összegből való.
Kiderült tehát, hogy ‐ maximális elemszámának köszönhetően ‐ a halmazrendszer azzal a további tulajdonsággal is rendelkezik, hogy a

H

bármely két eleme egyszerre benne van az

n

darab részhalmaz valamelyikében. Megjegyzendő, hogy a két megadott példánk közül a másodikra ez teljesül. Megmutatható viszont, hogy

n \geq 4

esetén minden ettől különböző konfiguráció nagyon szigorú számossági feltételeknek tesz eleget: mindegyik

A_{i}

részhalmaz ugyanannyi elemből áll (legyen ez a szám

q + 1

), a

H

minden eleme pontosan

q + 1

részhalmazban van benne, és ezekből következően

n = q^{2} + q + 1

. Ezeket a konfigurációkat véges projektív síkoknak nevezzük. Az elnevezés nem véletlen: ha

H

elemeit tekintjük pontoknak, az

A_{i}

részhalmazokat pedig egyeneseknek, akkor valóban teljesülnek a projektív síkgeometria axiómái, miszerint bármely két különböző egyenesnek pontosan egy közös pontja van, és bármely két ponthoz található (előbbi szerint pontosan egy) olyan egyenes, amely mindkét pontot tartalmazza. Ha

q

prímhatvány, akkor egy

n = q^{2} + q + 1

elemű halmazon létezik véges projektív sík (olykor többféle is!). Híres, és mindmáig megoldatlan probléma viszont, hogy létezik-e olyan

k

szám, ami nem prímhatvány, de az

n = k^{2} + k + 1

elemű halmazon mégis megadható projektív sík.
Az egymást egy pontban metsző halmazok rendszeréről szóló ún. Erdős ‐ de Bruijn-tételt tehát a következőképpen fogalmazhatjuk meg: Ha egy

n \geq 4

elemű halmaz

k

darab részhalmaza közül bármelyik kettőnek pontosan egy közös eleme van, akkor

k \leq n

, és ha

k = n

, akkor a rendszer vagy az ismertetett két példa egyike, vagy egy véges projektív sík.

Befejezés

Mátrixok sajátvektorai és sajátértékei a matematika és a fizika számos területén előfordulnak. Befejezésül essék néhány szó ismét a koordináta-geometriáról. Tekintsük például azt a síkgörbét, amelynek (a szokásos derékszögű koordináta-rendszerben) az egyenlete

\begin{matrix} 6 x^{2} + 4 x y + 3 y^{2} + 5 x - 8 y - 10 = 0. \end{matrix}

Mi ez a görbe, mik a főbb geometriai jellemzői? Könnyebb lenne erre választ adni, ha egy másik, az alakzathoz ,,jobban illeszkedő'' koordináta-rendszerben lenne az egyenlet felírva. Csakhogy éppen ez a feladat: az adekvát koordináták megtalálása. Ha a koordináta-rendszert eltoljuk a

\underset{̲}{v} = (a, b)

vektorral, akkor az új

x'

y'

koordinátákkal

x = x' + a

y = y' + b

teljesül; ezeket az eredeti egyenlet változóiba helyettesítve egy kis számolás után megkaphatjuk az alakzatunk egyenletét az új rendszerben. De a részletek kiszámolása nélkül is látható, hogy az új egyenletben ugyanazok maradnak a másodfokú tagok (

x^{2}

x y

y^{2}

) együtthatói. A probléma kemény magja tehát ezekben keresendő ‐ az elsőfokú tagokat és a

- 10

konstanst hagyjuk is egyelőre figyelmen kívül.
A megoldás kulcsa az, hogy a

6 x^{2} + 4 x y + 3 y^{2}

részt mátrixokkal,

\begin{matrix} (\begin{matrix} x & y \end{matrix}) (\begin{matrix} 6 & 4 \\ 0 & 3 \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) \end{matrix}

(9)

alakban írjuk fel. Ha a koordináta-rendszert az origó körül

β

fokkal elforgatjuk, az új

x'

y'

koordinátákra

\begin{matrix} (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix}) (\begin{matrix} x' \\ y' \end{matrix}), illetve (\begin{matrix} x & y \end{matrix}) = (\begin{matrix} cos β & sin β \\ - sin β & cos β \end{matrix}) (\begin{matrix} x' & y' \end{matrix}) . \end{matrix}

Így az elforgatott koordináta-rendszerben az alakzat új egyenletének másodfokú része:

\begin{matrix} (\begin{matrix} x' & y' \end{matrix}) {\underset{︸}{(\begin{matrix} cos β & sin β \\ - sin β & cos β \end{matrix}) (\begin{matrix} 6 & 4 \\ 0 & 3 \end{matrix}) (\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix})}}_{}^{} (\begin{matrix} x' \\ y' \end{matrix}) . \end{matrix}

A megjelölt háromtényezős mátrixszorzat adja az új egyenletben a másodfokú tagok együtthatóit. Jó lenne, ha ott az

x' y'

együtthatója nulla lenne, mert akkor ‐ a koordináta-rendszer alkalmas eltolása után ‐ könnyű lenne észrevenni, hogy pl. ellipszissel, hiperbolával vagy parabolával van-e dolgunk. Ez éppen azt jelentené, hogy az aláhúzott mátrix diagonális. Itt felcsillan a remény: a bal szélen álló mátrix éppen a jobb oldalinak az inverze! Célba érhetünk tehát, ha az eredeti

(\begin{matrix} 6 & 4 \\ 0 & 3 \end{matrix})

mátrix diagonalizálható. Egyszerű és már ismert számolással ellenőrizhető is, hogy ez a mátrix valóban diagonalizálható. Ám ne örüljünk korán: a diagonalizálhatóság önmagában itt nem elegendő, a követelmény az, hogy alkalmas

(\begin{matrix} cos β & - sin β \\ sin β & cos β \end{matrix})

típusú mátrixszal lehessen diagonalizálni ‐ ilyen pedig a mi mátrixunkhoz nem létezik.
Azonban szerencsénk van: lehet más is a kiindulási mátrix! Vegyük észre ugyanis, hogy (9)-ben az

x y

együtthatója a

(\begin{matrix} 6 & 4 \\ 0 & 3 \end{matrix})

mátrix jobb felső és bal alsó elemének összegeként adódik ‐ így ezek egyikét szabadon megválaszthatjuk. Válasszuk őket egyenlőnek, ekkor az

(\begin{matrix} 6 & 2 \\ 2 & 3 \end{matrix})

mátrix a bal felső és a jobb alsó sarok meghatározta egyenesre szimmetrikus. A lineáris algebra egy alapvető tétele ‐ az ún. főtengelytétel ‐ szerint minden szimmetrikus

n \times n

-es mátrix egy alkalmas ortogonális mátrixszal diagonalizálható;

2 \times 2

-es esetben ez éppen a kívánt alakot jelenti.
Esetünkben a megfelelő diagonalizáló mátrix

(\begin{matrix} \frac{1}{\sqrt[]{5}} & \frac{2}{\sqrt[]{5}} \\ - \frac{2}{\sqrt[]{5}} & \frac{1}{\sqrt[]{5}} \end{matrix})

, és az új

x'

y'

koordinátákkal felírt

\begin{matrix} (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} \frac{1}{\sqrt[]{5}} & \frac{2}{\sqrt[]{5}} \\ - \frac{2}{\sqrt[]{5}} & \frac{1}{\sqrt[]{5}} \end{matrix}) (\begin{matrix} x' \\ y' \end{matrix}), \end{matrix}

azaz

x = \frac{1}{\sqrt[]{5}} x' + \frac{2}{\sqrt[]{5}} y'

y = - \frac{2}{\sqrt[]{5}} x' + \frac{1}{\sqrt[]{5}} y'

helyettesítésekkel kapott új egyenlet (az elforgatott koordináta-rendszerben):

\begin{matrix} 2 x'^{2} + 7 y'^{2} + \frac{21}{\sqrt[]{5}} x' + \frac{2}{\sqrt[]{5}} y' - 10 = 0. \end{matrix}

Innen már simább úton haladhatunk tovább; teljes négyzetté kiegészítéssel eltüntethetjük az elsőfokú tagokat:

\begin{matrix} 2 {(x' + \frac{21}{4 \sqrt[]{5}})}^{2} + 7 {(y' + \frac{1}{7 \sqrt[]{5}})}^{2} = 10 + \frac{441}{80} + \frac{1}{245}, \end{matrix}

ennek megfelelően eltolhatjuk a koordináta-rendszert, végül osztunk az újonnan adódó konstans tag abszolút értékével. Az egyenlet fenti alakjából egyébként már leolvasható, hogy ‐ 2 és 7 pozitív lévén ‐ görbénk egy ellipszis. A szokásos

\frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} = 1

alakba való átírással megkaphatjuk az ellipszis tengelyeinek hosszát, a diagonalizáló mátrix révén pedig (ld.

arcsin \frac{2}{\sqrt[]{5}}

és társai) e tengelyeknek az eredeti koordináta-rendszer tengelyeivel bezárt szögét.