Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

7. Intermezzó: vissza a 17. századba – koordinátageometria

7. Intermezzó: vissza a 17. századba – koordinátageometria

Középiskolában azt tanultuk, hogy az y = m 1 x + b 1 és az y = m 2 x + b 2 egyenletekkel megadott e 1 , ill. e 2 egyenesek akkor és csak akkor merőlegesek, ha m 1 = - 1 / m 2 . Ha a koordinátatengelyekkel párhuzamos egyenesekre is gondolunk, akkor egy kissé pontosabban kell fogalmaznunk: egy egyenes egyenlete a x + b y + c = 0 , ahol a és b nem lehet egyszerre zérus. (Az egyik lehet: a = 0 esetén a vízszintes, b = 0 esetén a függőleges egyenesek egyenletére jutunk.) Legyen most az e 1 , e 2 egyenesek egyenlete rendre a 1 x + b 1 y + c 1 = 0 , ill. a 2 x + b 2 y + c 2 = 0 . Ha a két egyenes merőleges egymásra, akkor a 1 a 2 + b 1 b 2 = 0 , és megfordítva, ebből a feltételből következik is a merőlegesség, ha tényleg két egyenesről van szó, vagyis ha az a 1 , b 1 és az a 2 , b 2 párok egyike sem két zérusból áll.

Általában is merőlegesnek (vagy latin szóval ortogonálisnak) nevezzük az akárhány dimenziós v 1 = ( x 1 , y 1 , ) és a v 2 = ( x 2 , y 2 , ) vektorokat), ha

x 1 x 2 + y 1 y 2 + = 0

teljesül. A síkban beszélhetünk két merőleges egyenesről, vagy a 3-dimenziós térben egy S síkról és egy rá merőleges e egyenesről (mely ekvivalens azzal, hogy az e egyenes az S sík összes egyenesére merőleges). Általában legyen most egy k -dimenziós és egy l -dimenziós „rész-terünk” egy kellően nagy (legalább k + l -dimenziós) térben. Ezeket ortogonálisnak nevezzük, ha előbbi bármely vektora merőleges utóbbi bármely vektorára. Ha egy épp k + l -dimenziós térben vagyunk, akkor szokás ezt a két rész-teret (szokásosabb nevén alteret) egymás ortogonális komplementerének nevezni.

Azt állítjuk, hogy tulajdonképpen ez is „olyan, mint a dualitás”. A 10. ábrán látható hálózat feszültségeire az u 2 + u 3 - u 1 = 0 , u 4 + u 5 - u 3 = 0 , u 2 + u 4 + u 5 - u 1 = 0 egyenleteket írtuk fel; ezek felfoghatóak úgy is, mint a

( - 1 , 1 , 1 , 0 , 0 ) , ( 0 , 0 , - 1 , 1 , 1 ) , ( - 1 , 1 , 0 , 1 , 1 )

vektoroknak az ( u 1 , u 2 , u 3 , u 4 , u 5 ) vektorral való ortogonalitása, illetve általában a Kirchhoff-féle feszültségtörvények megfogalmazhatóak úgy is, hogy az ( u 1 , u 2 , ) feszültségvektor ortogonális minden olyan 0 , ± 1 vektorra, mely egy-egy kört ír le. Hasonlóképp az ábrán látható hálózat áramaira az i 1 + i 2 = 0 , i 2 - i 3 - i 4 = 0 , i 4 - i 5 = 0 egyenleteket írtuk fel; ehelyett mondhattuk volna azt, hogy az

( 1 , 1 , 0 , 0 , 0 ) , ( 0 , 1 , - 1 , - 1 , 0 ) , ( 0 , 0 , 0 , 1 , - 1 )

vektorok merőlegesek az ( i 1 , i 2 , i 3 , i 4 , i 5 ) vektorra, illetve általában a Kirchhoff-féle áramtörvények azt fejezik ki, hogy az ( i 1 , i 2 , ) áramvektor ortogonális minden olyan 0 , ± 1 vektorra, mely egy-egy vágást ír le.

Mármost vegyük észre, hogy a köröket és a vágásokat leíró vektorhalmazok ortogonális altereket határoznak meg, vagyis a első csoport bármelyik vektora merőleges a második csoport bármelyik vektorára. (Ha ezt valaki nem gépies összeszorzással ellenőrzi, hanem követi is a gráfon, hogy épp melyik élnél tartunk, akkor hamar rájöhet arra, hogy tulajdonképpen egy ismert anekdotában olvasható népi bölcsességről van szó: amikor valaki dicsekszik, hogy reggelente edzésképp ötször átússza a folyót, a többiek csendben megjegyzik, hogy ők ugyan csak négyszer ússzák át, de utána legalább visszajuthatnak a ruhájukhoz…)

Általánosabban, ha egy gráf összes körét vagy vágását leíró vektorokat egymás alá írjuk, akkor a gráf kör-, ill. vágásmátrixához jutunk, ld. a 3. szakasz táblázatának 7-8. sorait. Belátható, hogy ezek nemcsak ortogonális altereket határoznak meg, hanem ezek az alterek egymás ortogonális komplementerei is.

Általában is, ha van két M 1 , M 2 mátrixunk, melyek mindketten k + l oszlopból állnak, továbbá M 1 sorai egy k -, míg M 2 sorai egy l -dimenziós alteret határoznak meg, továbbá a két altér egymás ortogonális komplementere, akkor a két mátrixot (vagyis inkább az általuk meghatározott altereket) is tekinthetjük egymás duálisának.

Ezt a gondolatot felhasználva vezette be 1935-ben Whitney a mátrixok és a gráfok közös általánosításaképp a matroidok fogalmát. Azóta a matroidelmélet a diszkrét matematika egyik legfontosabb ágává fejlődött – és talán nem meglepő, hogy épp a villamos hálózatok és a rúdszerkezetek vizsgálata során bizonyult különösen jól alkalmazhatónak.