OBZORNIK ZA MATEMATIKO IN FIZIKO IZDAJA DRUŠTVO MATEMATIKOV, FIZIKOV IN ASTRONOMOV SLOVENIJE ISSN 0473-7466 OBZORNIK MAT. FIZ. LJUBLJANA LETNIK 59 ŠT. 4 STR. 121–160 JULIJ 2012 C KM Y 2012 Letnik 59 4 i i “kolofon” — 2012/10/25 — 14:49 — page 1 — #1 i i i i i i OBZORNIK ZA MATEMATIKO IN FIZIKO Glasilo Društva matematikov, fizikov in astronomov Slovenije Ljubljana, JULIJ 2012, letnik 59, številka 4, strani 121–160 Naslov uredništva: DMFA–založništvo, Jadranska ulica 19, p. p. 2964, 1001 Ljubljana Telefon: (01) 4766 553, 4232 460 Telefaks: (01) 4232 460, 2517 281 Elektronska pošta: zaloznistvo@dmfa.si Internet: http://www.obzornik.si/ Transakcijski račun: 03100–1000018787 Mednarodna nakazila: SKB banka d.d., Ajdovščina 4, 1513 Ljubljana SWIFT (BIC): SKBASI2X IBAN: SI56 0310 0100 0018 787 Uredniški odbor: Peter Legiša (glavni urednik), Sašo Strle (urednik za matematiko in odgovorni urednik), Aleš Mohorič (urednik za fiziko), Mirko Dobovišek, Irena Drevenšek Olenik, Damjan Kobal, Petar Pavešić, Marko Petkovšek, Marko Razpet, Nada Razpet, Peter Šemrl, Matjaž Zaveršnik (tehnični urednik). Jezikovno pregledal Janez Juvan. Računalniško stavila in oblikovala Tadeja Šekoranja. Natisnila tiskarna COLLEGIUM GRAPHICUM v nakladi 1250 izvodov. Člani društva prejemajo Obzornik brezplačno. Celoletna članarina znaša 21 EUR, za druge družinske člane in študente pa 10,50 EUR. Naročnina za ustanove je 35 EUR, za tujino 40 EUR. Posamezna številka za člane stane 3,19 EUR, stare številke 1,99 EUR. DMFA je včlanjeno v Evropsko matematično društvo (EMS), v Mednarodno matematično unijo (IMU), v Evropsko fizikalno društvo (EPS) in v Mednarodno združenje za čisto in uporabno fiziko (IUPAP). DMFA ima pogodbo o recipročnosti z Ameriškim matematič- nim društvom (AMS). Revija izhaja praviloma vsak drugi mesec. Sofinancira jo Javna agencija za knjigo Repu- blike Slovenije. c© 2012 DMFA Slovenije – 1883 Poštnina plačana pri pošti 1102 Ljubljana NAVODILA SODELAVCEM OBZORNIKA ZA ODDAJO PRISPEVKOV Revija Obzornik za matematiko in fiziko objavlja izvirne znanstvene in strokovne članke iz mate- matike, fizike in astronomije, včasih tudi kak prevod. Poleg člankov objavlja prikaze novih knjig s teh področij, poročila o dejavnosti Društva matematikov, fizikov in astronomov Slovenije ter vesti o drugih pomembnih dogodkih v okviru omenjenih znanstvenih ved. Prispevki naj bodo zanimivi in razumljivi širšemu krogu bralcev, diplomantov iz omenjenih strok. Članek naj vsebuje naslov, ime avtorja (oz. avtorjev), sedež institucije, kjer avtor(ji) dela(jo), izvle- ček v slovenskem jeziku, naslov in izvleček v angleškem jeziku, klasifikacijo (MSC oziroma PACS) in citirano literaturo. Slike in tabele, ki naj bodo oštevilčene, morajo imeti dovolj izčrpen opis, da jih lahko večinoma razumemo tudi ločeno od besedila. Avtorji člankov, ki želijo objaviti slike iz drugih virov, si morajo za to sami priskrbeti dovoljenje (copyright). Prispevki so lahko oddani v računalni- ški datoteki PDF ali pa natisnjeni enostransko na belem papirju formata A4. Zaželena velikost črk je 12 pt, razmik med vrsticami pa vsaj 18 pt. Prispevke pošljite odgovornemu uredniku ali uredniku za matematiko oziroma fiziko na zgoraj na- pisani naslov uredništva. Vsak članek se praviloma pošlje dvema anonimnima recenzentoma, ki morata predvsem natančno oceniti, kako je obravnavana tema predstavljena, manj pomembna pa je originalnost (in pri matematičnih člankih splošnost) rezultatov. Če je prispevek sprejet v objavo, potem urednik prosi avtorja še za izvorne računalniške datoteke. Le-te naj bodo praviloma napisane v eni od standardnih različic urejevalnikov TEX oziroma LATEX, kar bo olajšalo uredniški postopek. Avtor se z oddajo članka strinja tudi z njegovo kasnejšo objavo v elektronski obliki na internetu. i i “Kramar” — 2012/10/24 — 10:40 — page 121 — #1 i i i i i i NEKAJ NESTANDARDNIH METOD ZA RAČUNANJE DETERMINANT EDVARD KRAMAR Fakulteta za matematiko in fiziko Univerza v Ljubljani Math. Subj. Class. (2010): 15A15, 1501, 1503 V članku prikažemo nekaj enostavnih nestandardnih postopkov računanja determi- nant. Pri tem uporabljamo dvovrstne poddeterminante, izrezovanje stolpca in vrstice ali odštevanje števila od vseh elementov matrike. SOME NONSTANDARD METHODS FOR EVALUATION OF DETERMINANTS In this article we present some simple nonstandard algorithms for evaluation of de- terminants. We are using subdeterminants of order two, removing some row and column or subtracting some number from all elements of the matrix. Uvod Računanje determinante kvadratne matrike večjih redov je zamudno delo. Algoritmi računanja z računalnikom običajno uporabljajo razcep matrike na produkt spodnje in zgornje trikotne matrike (glej na primer [1]). Ta postopek je v tesni zvezi s tako imenovanimi elementarnimi operacijami na vrsticah in stolpcih matrike. Kadar računamo determinante ” ročno“, torej brez uporabe računalnika, običajno prav z omenjenimi operacijami skušamo priti do čim bolj enostavne oblike. Namen prispevka je prikazati nekaj manj znanih metod računanja determinant, ki so lahko same po sebi zanimive. 1. Računanje determinante s pomočjo dvovrstnih poddeterminant Vzemimo matriko A reda n×n in v njej izberimo poljuben neničelni element aik, ki ga na kratko označimo z α. A =  a11 · · · a1,k−1 a1k a1,k+1 · · · a1n a21 · · · a2,k−1 a2k a2,k+1 · · · a2n ... . . . ... ... ... . . . ... ai−1,1 · · · ai−1,k−1 ai−1,k ai−1,k+1 · · · ai−1,n ai1 · · · ai,k−1 α ai,k+1 · · · ain ai+1,1 · · · ai+1,k−1 ai+1,k ai+1,k+1 · · · ai+1,n ... . . . ... ... ... . . . ... an1 · · · an,k−1 ank an,k+1 · · · ann  . (1) Obzornik mat. fiz. 59 (2012) 4 121 i i “Kramar” — 2012/10/24 — 10:40 — page 122 — #2 i i i i i i Edvard Kramar Na stolpcih sj , kjer je j 6= k, naredimo naslednje elementarne operacije: sj → α · sj − aij · sk. Tako dobimo matriko αa11 − a1kai1 · · · αa1,k−1 − a1kai,k−1 a1k αa1,k+1 − a1kai,k+1 · · · αa1n − a1kain αa21 − a2kai1 · · · αa2,k−1 − a2kai,k−1 a2k αa2,k+1 − a2kai,k+1 · · · αa2n − a2kain ... . . . ... ... ... . . . ... 0 · · · 0 α 0 · · · 0 ... . . . ... ... ... . . . ... αan1 − ankai1 · · · αan,k−1 − ankai,k−1 ank αan,k+1 − ankai,k+1 · · · αann − ankain . Determinanto te matrike razvijmo po i-ti vrstici. Pri tem faktor (−1)i+k upoštevamo tako, da pred tem v zgornji matriki pomnožimo zadnje n − i vrstice in zadnje n − k stolpce s številom −1. Rezultat moramo še deliti s faktorjem αn−1 in ugotovimo, da je determinanta naše matrike A enaka 1 αn−2 -kratniku determinante naslednje matrike αa11−a1kai1 · · · αa1,k−1−a1kai,k−1 a1kai,k+1−αa1,k+1 · · · a1kain−αa1n . . . . . . . . . . . . . . . . . . αai−1,1−ai−1,kai1 · · · αai−1,k−1−ai−1,kai,k−1 ai−1,kai,k+1−αai−1,k+1 · · · ai−1,kain−αai−1,n ai+1,kai1−αai+1,1 · · · ai+1,kai,k−1−αai+1,k−1 αai+1,k+1−ai+1,kai,k+1 · · · αai+1,n−ai+1,kain . . . . . . . . . . . . . . . . . . ankai1−αan1 · · · ankai,k−1−αan,k−1 αan,k+1−ankai,k+1 · · · αann−ankain , (2) ki jo označimo z B. Hitro se lahko prepričamo, da elemente te matrike lahko pǐsemo kot dvovrstne determinante B =  ∣∣∣∣a11 a1kai1 α ∣∣∣∣ · · · ∣∣∣∣a1,k−1 a1kai,k−1 α ∣∣∣∣ ∣∣∣∣a1k a1,k+1α ai,k+1 ∣∣∣∣ · · · ∣∣∣∣a1k a1nα ain ∣∣∣∣ ... . . . ... ... . . . ...∣∣∣∣ai−1,1 ai−1,kai1 α ∣∣∣∣ · · · ∣∣∣∣ai−1,k−1 ai−1,kai,k−1 α ∣∣∣∣ ∣∣∣∣ai−1,k ai−1,k+1α ai,k+1 ∣∣∣∣ · · · ∣∣∣∣ai−1,k ai−1,nα ain ∣∣∣∣∣∣∣∣ ai1 αai+1,1 ai+1,k ∣∣∣∣ · · · ∣∣∣∣ ai,k−1 αai+1,k−1 ai+1,k ∣∣∣∣ ∣∣∣∣ α ai,k+1ai+1,k ai+1,k+1 ∣∣∣∣ · · · ∣∣∣∣ α ainai+1,k ai+1,n ∣∣∣∣ ... . . . ... ... . . . ...∣∣∣∣ai1 αan1 ank ∣∣∣∣ · · · ∣∣∣∣ai,k−1 αan,k−1 ank ∣∣∣∣ ∣∣∣∣ α ai,k+1ank an,k+1 ∣∣∣∣ · · · ∣∣∣∣ α ainank ann ∣∣∣∣  . Med determinantama obeh matrik velja torej zveza det(A) = 1 αn−2 det(B). (3) Metoda sestavljanja matrike B je enostavna. Najprej izberemo v matriki A neničelni element α, na primer v i-ti vrstici in k-tem stolpcu. Nato se 122 Obzornik mat. fiz. 59 (2012) 4 i i “Kramar” — 2012/10/24 — 10:40 — page 123 — #3 i i i i i i Nekaj nestandardnih metod za računanje determinant postavimo na to mesto in sestavljamo dvovrstne determinante tako, da ele- ment α vsakokrat dopolnimo s tekočim elementom ars (kjer r 6= i in s 6= k) matrike in dvema elementoma, ki sta na križǐsču ustrezne vrstice in stolpca z i-to vrstico in k-tim stolpcem. Pri tem ohranimo pozicijo elementov, kot so v prvotni matriki, in nam tudi ni treba misliti na predznake. Pri ročnem računanju je seveda pametno, da izberemo za α element 1 ali −1, če tak ob- staja. Naj opomnimo, da v primeru izbire α = a11, če je to število neničelno, dobimo tako imenovano Chiòvo formulo (glej na primer [4]). Računanje de- terminante reda n smo prevedli na računanje determinante reda n − 1. S ponavljanjem postopka pridemo nazadnje do ene same determinante reda 2. Naredimo zgled:∣∣∣∣∣∣∣∣ 5 3 0 4 2 3 0 4 0 7 1 0 2 0 3 7 2 1 3 4 5 1 2 2 3 ∣∣∣∣∣∣∣∣ = ∣∣∣∣∣∣∣ −10 6 2 7 3 −4 0 −7 1 −2 0 −3 −3 3 1 2 ∣∣∣∣∣∣∣ = ∣∣∣∣∣−4 0 −33 −4 71 −2 3 ∣∣∣∣∣ = ∣∣∣∣ 8 −9−2 2 ∣∣∣∣ = −2. Krepko smo označili števila, ki smo jih izbrali za naslednji korak. Oglejmo si še primer iz [6] Dn = ∣∣∣∣∣∣∣∣∣∣∣ a1b1 a1b2 a1b3 · · · a1bn−1 a1bn a1b2 a2b2 a2b3 · · · a2bn−1 a2bn a1b3 a2b3 a3b3 · · · a3bn−1 a3bn ... ... ... . . . ... ... a1bn a2bn a3bn · · · an−1bn anbn ∣∣∣∣∣∣∣∣∣∣∣ , kjer avtor predlaga, da najprej poǐsčemo zvezo med Dn in Dn−1. Vzemimo najprej, da je a1bn 6= 0. Če uporabimo zvezo (3) na desnem zgornjem vogalnem elementu, hitro ugotovimo, da dobimo determinanto, ki ima vse elemente nad glavno diagonalo enake 0, diagonalni elementi pa so po vrsti: a1bn(a2b1−a1b2), a1bn(a3b2−a2b3), . . ., a1bn(anbn−1−an−1bn). Tako dobimo po kraǰsanju z (a1bn) n−2 za vrednost determinante rezultat: Dn = a1bn n−1∏ k=1 (ak+1bk − akbk+1). Če je a1bn = 0, ta zveza trivialno velja. Zvezo (3) lahko najprej posplošimo tako, da izberemo dva neničelna elementa neke vrstice. Če na primer izberemo elementa α = aik 6= 0 in β = air 6= 0, kjer je 1 ≤ k < r < n, podobno kot zgoraj z elementarnimi operacijami na stolpcih sj → α · sj − aij · sk, j = 1, 2, . . . , r, j 6= k, sj → β · sj − aij · sr, j = r + 1, . . . , n 121–133 123 i i “Kramar” — 2012/10/24 — 10:40 — page 124 — #4 i i i i i i Edvard Kramar izpeljemo zvezo det(A) = 1 αr−2βn−r det(B), (4) kjer je matrika B sestavljena iz poddeterminant drugega reda, tvorjenih tako kot zgoraj, pri čemer prvi parameter α uporabimo za prvih r − 1 stolpcev, za naslednje stolpce pa uporabimo parameter β. Zgoraj smo vzeli r 6= n, v nasprotnem dobimo zvezo z enim samim parametrom. Kot primer vzemimo matriko A reda 5 × 5, v kateri izberimo elementa α = a32 in β = a34 A =  a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 α a33 β a35 a41 a42 a43 a44 a45 a51 a52 a53 a54 a55 . Za determinanto te matrike velja zveza det(A) = 1 α4−2β5−4 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ ∣∣∣∣ a11 a12a31 α ∣∣∣∣ ∣∣∣∣ a12 a13α a33 ∣∣∣∣ ∣∣∣∣ a12 a14α β ∣∣∣∣ ∣∣∣∣ a14 a15β a35 ∣∣∣∣ ∣∣∣∣ a21 a22a31 α ∣∣∣∣ ∣∣∣∣ a22 a23α a33 ∣∣∣∣ ∣∣∣∣ a22 a24α β ∣∣∣∣ ∣∣∣∣ a24 a25β a35 ∣∣∣∣ ∣∣∣∣ a31 αa41 a42 ∣∣∣∣ ∣∣∣∣ α a33a42 a43 ∣∣∣∣ ∣∣∣∣ α βa42 a44 ∣∣∣∣ ∣∣∣∣ β a35a44 a45 ∣∣∣∣ ∣∣∣∣ a31 αa51 a52 ∣∣∣∣ ∣∣∣∣ α a33a52 a53 ∣∣∣∣ ∣∣∣∣ α βa52 a54 ∣∣∣∣ ∣∣∣∣ β a35a54 a55 ∣∣∣∣ ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ . Zgornjo zvezo lahko posplošimo še na več izbranih elementov. Tako velja: če v i-ti vrstici matrike (1) izberemo neničelne elemente ai,k1 , ai,k2 , . . . , ai,kr (največ n − 2), kjer je 1 ≤ k1 < k2 < . . . < kr < n, potem velja naslednja zveza: det(A) = 1 ak2−2i,k1 a k3−k2 i,k2 · · · an−kri,kr det(B), (5) kjer je matrika B iz dvovrstnih poddeterminant, tvorjenih na zgoraj opisani način. Pri tem preskočimo pri vsakem izbranem stolpcu na naslednji para- meter. Zanimivo je, da v zvezah (4) in (5) pozicija prvega parametra nima vpliva na faktor pred novo determinanto. V posebnem lahko izberemo n−2 124 Obzornik mat. fiz. 59 (2012) 4 i i “Kramar” — 2012/10/24 — 10:40 — page 125 — #5 i i i i i i Nekaj nestandardnih metod za računanje determinant neničelnih elementov neke vrstice, na primer vse razen prvega in zadnjega. Če smo to naredili v i-ti vrstici, dobimo zvezo det(A) = 1 ai2ai3 · · · ai,n−1 det(B), (6) kjer je matrika B iz determinant reda 2, tvorjenih na zgornji način, pri čemer na vsakem koraku preskočimo na sosednji parameter. Podobne formule, kot so (4), (5) in (6), veljajo, če parametre izbiramo v nekem stolpcu. Za zgled s pomočjo zveze (6) izračunajmo naslednjo determinanto reda n: D(a1, a2, . . . , an; b1, b2, . . . , bn) = ∣∣∣∣∣∣∣∣ an−11 a n−2 1 b1 · · · a1b n−2 1 b n−1 1 an−12 a n−2 2 b2 · · · a2b n−2 2 b n−1 2 ... ... . . . ... ... an−1n a n−2 n bn · · · anbn−2n bn−1n ∣∣∣∣∣∣∣∣. (7) Najprej predpostavimo, da so vsa števila neničelna. Uporabimo zvezo (6) na prvi vrstici in v dobljeni determinanti iz vseh stolpcev izpostavimo potence števil a1 in b1 ter skupne faktorje v vrsticah. Po okraǰsanju dobimo zvezo: D(a1, a2, . . . , an; b1, b2, . . . , bn) = = (a1b2 − a2b1) · · · (a1bn − anb1) ·D(a2, a3, . . . , an; b2, b3, . . . , bn). (8) Zveza velja tudi, če je kakšno od števil enako nič. Vzemimo npr., da je a1 = 0. Razvijmo za ta primer determinanto (7) po prvi vrstici in dobimo: D(0, a2, . . . , an; b1, b2, . . . , bn) = = (−1)n+1bn−11 a2a3 · · · anD(a2, a3, . . . , an; b2, b3, . . . , bn). Isto pa dobimo, če v zvezi (8) postavimo a1 = 0. Zvezo (8) rekurzivno upo- rabimo na vse manǰsih determinantah, dokler ne pridemo do determinante drugega reda, ki je enaka D(an−1, an; bn−1, bn) = an−1bn − anbn−1. Tako pridemo do identitete D(a1, a2, . . . , an; b1, b2, . . . , bn) = ∏ 1≤i