Harminchárom miniatúra a lineáris algebra alkalmazásairól

Ajánló Jiří Matoušek Thirty-three miniatures. Mathematical and algorithmic applications of linear algebra című könyvéhez

„A lineáris algebra szó hallatán sokakban unalmas és hatalmas mátrixszorzások (rém)képe merül fel, mások pedig valamilyen iszonyúan elvont és emészthetetlen elméletre gondolnak. A könyvben megpróbáljuk ezeket a tévhiteket eloszlatni azáltal, hogy a konkrétból kiindulva haladunk az általános felé, és már minimális tudással felvértezve is valódi és szórakoztató alkalmazásokat tárgyalunk.” (Freud Róbert: Lineáris algebra [2])

A fenti idézet, amely bizonyára sokaknak ismerősen cseng¹, akár a jelen ajánló tárgyát képező könyv mottója is lehetne. Jiří Matoušek² a lineáris algebra számára legkedvesebb, gyakran meglepő alkalmazásait tárja az olvasó elé harminchárom rövid fejezetből (miniatúrából) álló gyűjteményében, amely az Amerikai Matematikai Társaság Student Mathematical Library című könyvsorozatának 53. köteteként jelent meg 2010-ben [7]. A sorozat elsődleges célja, hogy ablakot nyisson a modern matematika aktív kutatási területeire, bemutassa fejlődésüket, a legfontosabb kérdéseket és eredményeket, mindezt ráadásul úgy, hogy a szükséges előismeretek lehetőleg ne haladják meg az egyetemi matematika tananyag alapozó kurzusainak kereteit.

A Thirty-three miniatures ennek a követelménynek minden tekintetben megfelel. A szerző az olvasóról csupán annyit feltételez, hogy rendelkezik lineáris algebrai alapismeretekkel, barátságos viszonyt ápol polinomokkal, valamint ismeri a gráfelmélet és az euklideszi geometria alapfogalmait.

A fejezetek Matoušek szubjektív megítélése szerinti nehézségi sorrendben követik egymást. Valóban, a Fibonacci-sorozatról szóló részek (1. és 2. miniatúrák) akár egy középiskolai szakkörön is – megfelelő előkészülettel – feldolgozhatók, míg a későbbi fejezetek megértésében sokat segíthet, ha az olvasó már rendelkezik bizonyos fokú matematikai érettséggel.

Fontos hangsúlyozni, hogy az egyes miniatúrák önállóan is olvasható kerek egészt alkotnak.³ Mindegyik fejezet egy konkrét probléma pontos ismertetésével és motivációjával, valamint a szükséges definíciók és jelölések bevezetésével kezdődik. Ezt rendszerint az adott fejezet gerincét képező tétel kimondása és bizonyítása követi, végül pedig bibliográfiai megjegyzések és hivatkozások.

Természetesen a gyűjtemény a szerző érdeklődését tükrözi (kombinatorika, geometria és számítógép-tudomány), de ezen belül rendkívül szerteágazó a témaválasztás. A bemutatott alkalmazások által érintett főbb területek a teljesség igénye nélkül (zárójelben a vonatkozó fejezetek sorszámai): algoritmusok (1, 10), extremális halmazrendszerek (3, 4, 8, 17, 33), hibajavító kódok (5), kombinatorikus geometria (6, 7, 9, 15, 18, 20, 30), véletlen algoritmusok (11, 24, 27), lehetetlenségi bizonyítások (12, 13), spektrális gráfelmélet (14, 31), polinommódszer (16, 25), diszkrepanciaelmélet (19, 20), leszámlálási problémák (21, 22, 23, 26) és információelmélet (28, 29).

Mindezek miatt a Thirty-three miniatures kiválóan használható a lineáris algebra, a diszkrét matematika, vagy a gráfelmélet kurzusainak kiegészítő tankönyveként.⁴ Feldolgozható szemináriumokon, speciálkollégiumokon, de akár önállóan is, és mindazok érdeklődésére számot tart, akik szeretnének bepillantást nyerni a fent említett kutatási területekbe. A további elmélyülést a gazdag irodalomjegyzék segíti. Nagyjából A5-ös méretének köszönhetően a könyv egy kabátzsebben is elfér. Mivel egy miniatúra átlagosan öt (a legrövidebb másfél, a leghosszabb tizenegy) oldal hosszú, ezért már rövidebb utazások során is szórakoztató és érdekfeszítő kihívást kínál.

Ízelítőül íme az eredeti fordításán alapuló 9. miniatúra.

9. miniatúra. Egyenlőszögű egyenesek

Könnyű látni, hogy $\mathbb{R}^3$ -ban legfeljebb három egymást páronként derékszögben metsző egyenes adható meg, de más szögek esetén a helyzet bonyolultabb. Például egy szabályos ikozaéder hat főátója szimmetria-okokból egyenlőszögű családot alkot (1. ábra). A következőkben – lineáris algebra segítségével – megmutatjuk, hogy ez a szám maximális. Legfeljebb hány (origón átmenő) egyenes helyezhető el a háromdimenziós térben úgy, hogy bármely kettő által közbezárt szög ugyanakkora legyen? (Ilyen egyenesek családját egyenlőszögűnek nevezzük.)

1. ábra

Tétel. (Gerzon [6]) Egy egyenlőszögű család $\mathbb{R}^d$ -ben legfeljebb $\binom{d+1}{2}$ egyenesből állhat. Speciálisan $\mathbb{R}^3$ -ban legfeljebb 6 egyenlőszögű egyenes adható meg.

Bizonyítás. Tekintsünk $n$ egyenlőszögű egyenest $\mathbb{R}^d$ -ben, amelyek páronként $\theta \in (0,\frac{\pi}{2}]$ fokos szöget zárnak be. Legyen $\mathbf{v}_i$ az $i$ -edik egyenes 1 hosszúságú irányvektora ( $\mathbf{v}_i$ két lehetséges irányítása közül tetszőlegesen választhatunk). Az egyenlőszögűség feltétele azzal ekvivalens, hogy bármely $i \neq j$ párra

$\displaystyle \vert\langle \mathbf{v}_i, \mathbf{v}_j \rangle\vert = \cos{\theta}.$

Ha $\mathbf{v}_i$ -re $d \times 1$ -es oszlopvektorként tekintünk, akkor egyrészt a skalárszorzat definíciója szerint $\mathbf{v}_i^\top \mathbf{v}_j = \langle \mathbf{v}_i, \mathbf{v}_j \rangle$ , másrészt $\mathbf{v}_i \mathbf{v}_j^\top$ egy $d \times d$ -es mátrix.

Megmutatjuk, hogy a $\mathbf{v}_i \mathbf{v}_i^\top$ ( $i=1,2,\ldots,n$ ) mátrixok lineárisan függetlenek a valós szimmetrikus $d \times d$ -es mátrixok vetorterében, amelynek dimenziója $\binom{d+1}{2}$ . Következésképp $n \leq \binom{d+1}{2}$ , ami épp a bizonyítandó állítás.

Tekintsük tehát az általános

$\displaystyle \sum_{i=1}^n a_i \mathbf{v}_i \mathbf{v}_i^\top = \mathbf{0}$

(1)

lineáris kombinációt. Az egyenletet jobbról és balról rendre a $\mathbf{v}_j$ és $\mathbf{v}_j^\top$ vektorokkal szorozva, a mátrixszorzás asszociativitása alapján

$\displaystyle 0 = \sum_{i=1}^n a_i \mathbf{v}_j^\top(\mathbf{v}_i \mathbf{v}_i^... ...mathbf{v}_i, \mathbf{v}_j \rangle^2 = a_j + \sum_{i \neq j} a_i \cos^2{\theta}$

bármely $j = 1,2,\ldots,n$ esetén. Ez az $M \mathbf{a} = \mathbf{0}$ mátrixegyenlettel ekvivalens, ahol $\mathbf{a} = (a_1,a_2,\ldots,a_n)^\top$ és $M = (1- \cos^2\theta)I_n + (\cos^2\theta)J_n$ . Itt $I_n$ az $n \times n$ -es egységmátrixot, $J_n$ pedig a csupa 1-esből álló $n \times n$ -es mátrixot jelöli. Könnyen megmutatható, hogy a $M$ mátrix nemelfajuló, tehát létezik inverze (ugyanis $M$ pozitív definit, lásd alább), amiből következik, hogy $\mathbf{a} = \mathbf{0}$ . De ez pont azt jelenti, hogy az (1) lineáris kombináció triviális, vagyis a $\mathbf{v}_i \mathbf{v}_i^\top$ ( $i=1,2,\ldots,n$ ) mátrixok valóban lineárisan függetlenek. $\qedsymbol$

Feladat. Mutassuk meg, hogy $\theta \in (0,\frac{\pi}{2}]$ esetén az $M = (1- \cos^2\theta)I_n + (\cos^2\theta)J_n$ mátrix pozitív definit. $I_n$ az $n \times n$ -es egységmátrixot, $J_n$ pedig a csupa 1-esből álló $n \times n$ -es mátrixot jelöli.

Megoldás.

Megjegyzések.

Bár a $\binom{d+1}{2}$ felső korlát $d=3$ esetén éles (amint azt az ikozaéder példája mutatja), $d$ bizonyos értékeire a becslés tovább élesíthető.

Továbbra is nyitott kérdés, hogy általános $d$ esetén legfeljebb mekkora lehet egy egyenlőszögű család, $2 \leq d \leq 13$ esetén azonban ez a szám pontosan ismert. $d = 14$ -re annyit tudunk, hogy egy maximális egyenlőszögű család 28 vagy 29 egyenesből áll. Részletek és további eredmények Greaves, Koolen, Munemasa és Szöllősi 2016-os cikkében találhatók [3].

Legyen most $\theta \in (0,\frac{\pi}{2}]$ értéke rögzített, és jelölje $N_\theta(d)$ egy olyan egyenlőszögű család maximális méretét $\mathbb{R}^d$ -ben, amelyben bármely két egyenes $\theta$ szögben metszi egymást. Balla, Dräxler, Keevash és Sudakov nemrég belátták [1], hogy ekkor $N_\theta(d) \leq 2d - 2$ és egyenlőség csakis akkor áll fenn, ha $\theta = \arccos(\frac{1}{3})$ . Lásd még a Quanta Magazine kapcsolódó riportját [4].

A könyv megrendelhető az AMS honlapjáról: https://bookstore.ams.org/stml-53.

Végül megjegyezzük, hogy a Thirty-three miniatures kiadás előtti változata a hibajegyzékkel együtt elérhető a szerző honlapján: https://kam.mff.cuni.cz/~matousek/la-ams.html.

Irodalomjegyzék

[1] Igor Balla–Felix Dräxler–Peter Keevash–Benny Sudakov: Equiangular lines and spherical codes in Euclidean space, Invent. Math., 211. évf. (2018) 1. sz., 179–212. p. https://doi.org/10.1007/s00222-017-0746-0

[2] Róbert Freud: Lineáris algebra. 1996, ELTE Eötvös Kiadó, Budapest, 518. p.

[3] Gary Greaves–Jacobus H. Koolen–Akihiro Munemasa–Ferenc Szöllősi: Equiangular lines in Euclidean spaces, J. Combin. Theory Ser. A, 138. évf. (2016), 208–235. p. https://doi.org/10.1016/j.jcta.2015.09.008

[4] Kevin Hartnett: A new path to equal-angle lines, https://www.quantamagazine.org/a-new-path-to-equal-angle-lines-20170411. Letöltés dátuma: 2018. február 23.

[5] Jan Kratochvíl–Martin Loebl–Jaroslav Nešetřil–Pavel Valtr: Remembering Jiří Matoušek, https://kam.mff.cuni.cz/Matousek-obituary.html. Letöltés dátuma: 2018. február 23.

[6] P. W. H. Lemmens–J. J. Seidel: Equiangular lines, J. Algebra, 24. évf. (1973), 494–512. p. https://doi.org/10.1016/0021-8693(73)90123-3.

[7] Jiří Matoušek: Thirty-three miniatures. Mathematical and algorithmic applications of linear algebra, Student Mathematical Library sorozat, 53., 2010, American Mathematical Society, Providence, RI, x+182. p. ISBN 978-0-8218-4977-4. https://doi.org/10.1090/stml/053.

Huszár Kristóf

Huszár Kristóf 2013-ban végzett az ELTE Matematika BSc szakán, matematikus szakirányon. Jelenleg az Institute of Science and Technology Austria PhD hallgatója Uli Wagner kutatócsoportjában. Főbb érdeklődési területe a kombinatorikus topológia.

¹ Freud Róbert tankönyve 1996-os megjelenése óta egyetemi hallgatók generációi számara nyújtott bevezetést a lineáris algebrába, amely nemcsak fizikusok és matematikusok és mérnökök mindennapi kenyere, de minden olyan szakterület nélkülözhetetlen eszköztára, ahol felmerül a természetben lejátszódó folyamatok modellezésének, illetve nagymennyiségű (számszerű) adat szisztematikus elemzésének igénye.

² Jiří Matoušek (1963–2015) a prágai Károly Egyetem és a zürichi ETH professzora, generációjának kiemelkedő matematikusa, a kombinatorikus geometria és topológia, illetve a diszkrét matematika nemzetközi hírű kutatója volt. Közel kétszáz tudományos közlemény szerzője vagy társszerzője. Kutatási tevékenysége mellett kivételes tanáregyéniség, nagy hatású pedagógus: az általa írt monográfiák és tankönyvek az adott tudományterületeken alapműnek számítanak [5].

³ Kivétel ez alól a 18., illetve a 29. miniatúra, amelyek rendre támaszkodnak a 17., illetve 28. fejezetek eredményeire.

⁴ Jelen sorok írója ezt saját oktatási tapasztalatai alapján is megerősíti.