Ortogonalni latinski kvadrati i konačne projektivne ravnine
Sažetak
U ovom članku uvodi se pojam latinskog kvadrata, njegove ortogonalnosti, te konačne projektivne ravnine (s kombinatornog aspekta). Navode se i dokazuju neka njihova osnovna svojstva i veze. Dokazuje se dovoljan uvjet egzistencije konačne projektivne ravnine zadanog reda. Najjači rezultat koji se dokazuje jest Bruck-Ryserov teorem, koji daje neke nužne uvjete na red konačne projektivne ravnine. Na kraju, kratko i informativno daje se uvid u generalizaciju.
Sadržaj
1Ortogonalni latinski kvadrati
Tijekom povijesti latinski su kvadrati bili dio zabavne matematike. Međutim, u jednom su trenu matematičari uvidjeli netrivijalnost kombinatornih problema koji proizilaze iz razmatranja o latinskim kvadratima, kao i primjenu u drugim granama matematike. Mi ćemo razviti teoriju latinskih kvadrata u mjeri koja nam je potrebna da uspostavimo vezu s konačnim projektivnim ravninama.
Definicija. Kažemo da je kvadratna matrica A reda n \in \mathbb{N} latinski kvadrat ako vrijedi:
| \bullet | Elementi matrice A su elementi nekog n-članog skupa1\lbrace a_{1},a_{2},\ldots,a_{n}\rbrace; |
| \bullet | U svakom retku matrice A, svaki a_{i}, i=1,2,\ldots{},n nalazi se na točno jednom mjestu; |
| \bullet | U svakom stupcu matrice A, svaki a_{i}, i=1,2,\ldots{},n nalazi se na točno jednom mjestu. |
Primjer 1. Vrlo je lako provjeriti da su matrice
M := \left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array} \right) \quad \text{i} \quad N := \left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{array} \right)
latinski kvadrati reda 3.Općeniti latinski kvadrati neće nam biti posebno zanimljivi, ali hoće familije latinskih kvadrata istog reda koje imaju sljedeće svojstvo:
Definicija. Za latinske kvadrate A_{1}=\Big(a_{ij}^{(1)}\Big)_{ij} i A_{2}=\Big(a_{ij}^{(2)}\Big)_{ij} reda n kažemo da su ortogonalni ako skup2
\Big\lbrace \Big(a_{ij}^{(1)},a_{ij}^{(2)}\Big) \ : \ i,j=1,2,\ldots{},n \Big\rbrace
sadržava n^{2} različitih uređenih parova. Očito je ekvivalentno zahtijevati da je
\Big(a_{i_{1}j_{1}}^{(1)},a_{i_{1}j_{1}}^{(2)}\Big) \neq \Big(a_{i_{2}j_{2}}^{(1)},a_{i_{2}j_{2}}^{(2)}\Big), \text{ čim je } i_{1} \neq i_{2} \text{ ili } j_{1} \neq j_{2}.
Kažemo da je skup \lbrace A_{1},A_{2},\ldots,A_{t}\rbrace latinskih kvadrata istog reda ortogonalan ako su svaka dva različita elementa tog skupa ortogonalna.
Napomena. Uz ortogonalne latinske kvadrate veže se jedna poznata Eulerova hipoteza: Ako je n \equiv 2 \pmod{4}, tada ne postoje ortogonalni latinski kvadrati reda n. Pokazalo se poslije da je hipoteza pogrešna, točnije, da postoje ortogonalni latinski kvadrati reda n za n \in \mathbb{N} \setminus \lbrace 2,6\rbrace. Više o tome vidi u [2] , str. 151.–152.
Propozicija 2. Neka je S=\lbrace A_{1},A_{2},\ldots,A_{t}\rbrace ortogonalan skup latinskih kvadrata, reda n \geq 3. Tada je t \leq n-1.
Dokaz. Budući da nam je bitan samo raspored elemenata u latinskom kvadratu, a ne svojstva samih elemenata, možemo bez smanjenja općenitosti svakom posebno preimenovati elemente; time nećemo pokvariti ni definicijska svojstva latinskog kvadrata, niti ortogonalnost s drugim latinskim kvadratima, naravno, uz uvjet da različitim elementima pridružimo različito ime. Svakom latinskom kvadratu A_{i} \in S preimenujmo prvi redak u (1 \ 2 \ \ldots \ n). Budući da se u prvom retku od A_{i} nalazi svaki element (točno jednom), time su jedinstveno određena imena elemenata u svim preostalim retcima od A_{i}. Dakle, možemo smatrati da su
A_{1}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right), \quad A_{2}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right), \quad \ldots
\ldots, \quad A_{t}= \left(\begin{array}{cccc}1 & 2 & \ldots & n \\ \vdots & \vdots & \vdots & \vdots \end{array}\right).
Promotrimo koji brojevi mogu biti na mjestu (2,1) u tim matricama. Tu ne može biti 1, jer su te matrice latinski kvadrati. Također, zbog međusobne ortogonalnosti, ti brojevi očito moraju biti različiti za različite matrice, kojih ima t. Brojevi su iz skupa \lbrace 2,3,\ldots,n\rbrace, pa slijedi t \leq n-1, tj. tvrdnja teorema.
\ \blacksquare
Napomena. Gornji dokaz možemo provesti i u slučaju n=2, te zaključiti da ne postoje dva različita ortogonalna latinska kvadrata reda 2.
Primjer 3. Latinski kvadrati M i N iz primjera 1 su ortogonalni, jer njihovom superpozicijom dobivamo skup
2 zaključiti da ne postoji ni jedan latinski kvadrat koji bi istovremeno bio ortogonalan s M i N.
\left\lbrace \begin{array}{ccc} (1,1) & (2,2) & (3,3) \\ (2,3) & (3,1) & (1,2) \\ (3,2) & (1,3) & (2,1) \end{array} \right\rbrace
u kojem se nalaze svi mogući uređeni parovi elemenata iz skupa \lbrace 1,2,3\rbrace. Možemo po propoziciji Sada kada znamo da postoje ortogonalni latinski kvadrati, te kada imamo gornju među za njihov broj, postavlja se pitanje koliko ih zapravo može biti za zadani red. Odgovor na to općenito nije poznat. Međutim, u nekim posebnim slučajevima ipak možemo primjetiti da se ta gornja međa postiže. To je sadržaj sljedećeg teorema.
Definicija. Ako ortogonalan skup latinskih kvadrata reda n ima n-1 element, kažemo da je taj skup potpun (ili zasićen).
Teorem 4. Neka je n prim-potencija3. Tada postoji potpun skup ortogonalnih latinskih kvadrata reda n.
Dokaz. Za brojeve oblika n=p^{m} postoji konačno (Galoisovo) polje reda n, u oznaci (GF(n),+,\cdot) – vidi [1] , str. 280. Neka su svi (međusobno različiti) elementi tog polja sljedeći4: a_{0}=0, a_{1}=1, a_{2}, a_{3}, \ldots, a_{n-1}. Definirajmo matrice
na sljedeći način:
Dokažimo da je svaka matrica iz (1 ) latinski kvadrat. Budući da u našem polju ima n elemenata, kao i mjesta u svakom retku (stupcu) matrice A_{k}, dovoljno je dokazati da se u svakom retku (stupcu) pojavljuju samo različiti elementi. Pretpostavimo da matrica A_{k} u istom retku ima dva ista elementa, tj. neka je a_{ij_{1}}^{(k)}=a_{ij_{2}}^{(k)}. Zbog (2 ) vrijedi:
2 ) imamo:
1 ) su latinski kvadrati (reda n). Dokažimo još da su svaka dva međusobno ortogonalna. Neka su k,k' \in \lbrace 1,2,\ldots,n-1\rbrace međusobno različiti. Uočimo da je tada i a_{k} \neq a_{k'}, tj. a_{k} - a_{k'} \neq 0. Pretpostavimo da za neke i_{1},i_{2},j_{1},j_{2} \in \lbrace 0,1,\ldots,n-1\rbrace vrijedi
Nakon što od (3 ) oduzmemo (4 ) te iskoristimo komutativnost, asocijativnost i distributivnost u polju, dobijemo
3 ), trivijalno slijedi i j_{1}=j_{2}, pa su latinski kvadrati A_{k} i A_{k'} ortogonalni (uočimo da to povlači i da su međusobno različiti). Stoga je skup \lbrace A_{1},A_{2},\ldots, A_{n-1}\rbrace ortogonalan te sadržava n-1 različitih elemenata, pa je potpun.
(1)
A_{k}=\Big(a_{ij}^{(k)}\Big)_{i,j=0,1,\ldots{},n-1} \qquad k=1,2,\ldots{},n-1
(2)
a_{ij}^{(k)}:=a_{k} a_{i} + a_{j} \qquad i,j=0,1,\ldots{},n-1 \quad k=1,2,\ldots{},n-1.
a_{k} a_{i}+a_{j_{1}}=a_{k} a_{i} + a_{j_{2}} \quad \Rightarrow \quad a_{j_{1}}=a_{j_{2}} \quad \Rightarrow \quad j_{1}=j_{2},
pa vidimo da ti elementi moraju biti i u istom stupcu. Slično za stupce, pretpostavimo da matrica A_{k} u istom stupcu ima dva ista elementa, tj. a_{i_{1} j}^{(k)}=a_{i_{2} j}^{(k)}. Opet zbog (
a_{k} a_{i_{1}}+a_{j}=a_{k} a_{i_{2}} + a_{j} \quad \Rightarrow \quad a_{k} a_{i_{1}}=a_{k} a_{i_{2}} \quad \Rightarrow \quad a_{k} (a_{i_{1}}-a_{i_{2}})=0.
Sad iskoristimo činjenicu da u polju nema djelitelja nule, te a_{k} \neq 0 (jer je k\gt 0), pa imamo
a_{i_{1}}-a_{i_{2}}=0 \quad \Rightarrow \quad a_{i_{1}}=a_{i_{2}} \quad \Rightarrow \quad i_{1}=i_{2}.
Dakle, matrice (
\Big(a_{i_{1} j_{1}}^{(k)},a_{i_{1} j_{1}}^{(k')}\Big)=\Big(a_{i_{2} j_{2}}^{(k)},a_{i_{2} j_{2}}^{(k')}\Big).
To povlači a_{i_{1} j_{1}}^{(k)}=a_{i_{2} j_{2}}^{(k)} i a_{i_{1} j_{1}}^{(k')}=a_{i_{2} j_{2}}^{(k')}, iz čega slijede izrazi
(3)
a_{k} a_{i_{1}}+a_{j_{1}}=a_{k} a_{i_{2}}+a_{j_{2}},
(4)
a_{k'} a_{i_{1}}+a_{j_{1}}=a_{k'} a_{i_{2}}+a_{j_{2}}.
(a_{k} - a_{k'})a_{i_{1}}=(a_{k} - a_{k'})a_{i_{2}} \quad \Rightarrow \quad (a_{k} - a_{k'})(a_{i_{1}}-a_{i_{2}})=0
\Rightarrow \quad a_{i_{1}}-a_{i_{2}}=0 \quad \Rightarrow \quad a_{i_{1}}=a_{i_{2}} \quad \Rightarrow \quad i_{1}=i_{2}.
Nakon što izraz i_{1}=i_{2} stavimo u (
\ \blacksquare
Sljedeći teorem nama je više tehničkog karaktera, iako je značajan i sam za sebe (npr. u teoriji kodiranja).
Teorem 5. Neka su n \geq 3, t \geq 2 prirodni brojevi. Postoji ortogonalan skup od t latinskih kvadrata reda n ako i samo ako postoji matrica tipa (t+2,n^{2}) s elementima iz skupa \lbrace 1,2,\ldots,n\rbrace, koja ima svojstvo da stupci svake podmatrice tipa (2,n^{2}) tvore n^{2} različitih uređenih parova iz skupa \lbrace 1,2,\ldots,n\rbrace, ili ekvivalentno tomu, da se pojavljuju svi mogući uređeni parovi elemenata iz tog skupa.5 Nazovimo to svojstvo (\ast).
Dokaz. Neka su
Obrnuto, neka je A' matrica tipa (t+2,n^{2}), s elementima iz \lbrace 1,2,\ldots,n\rbrace, koja ima svojstvo (\ast). Primijetimo očitu činjenicu da se svaki broj u svakom retku pojavljuje točno n puta. Naime, ako bi se neki broj k pojavljivao više od n puta u i-tom retku, tada bi tvorio više od n uređenih parova oblika (k,\text{nešto}), u nekoj podmatrici u kojoj se nalazi i-ti redak, pa bi neka dva para morala biti jednaka. Ako bi se pak k pojavljivao manje od n puta, tada bi se neki drugi broj k' morao pojaviti više od n puta, pa provedemo analogno razmatranje za k'. Također primijetimo da se svojstvo (\ast) neće pokvariti pri permutiranju stupaca A', pa možemo pretpostaviti da A' ima prvi redak kao matrica A. Promotrimo početni komad duljine n drugog retka matrice A'. Iznad tog komada nalaze se samo jedinice, pa prvih n stupaca možemo permutirati da nam taj početni komad bude (1 \quad 2 \quad \ldots \quad n), a da se ne promijeni prvi redak. To ponovimo i za sljedeći blok duljine n (ispod dvojki), te analogno sve do kraja drugog retka. Dobili smo da prva dva retka matrice A' izgledaju kao prva dva retka matrice A, te je ostalo sačuvano svojstvo (\ast). Dakle, bez smanjenja općenitosti, neka je A'=A. Sad očito možemo reverzibilnim postupkom (dobivanja matrice A iz skupa \lbrace A_{1},A_{2},\ldots,A_{t}\rbrace) iz matrice A dobiti skup S:=\lbrace A_{1},A_{2},\ldots,A_{t}\rbrace. Lako se vidi kako svojstvo (\ast) i prva dva retka matrice A garantiraju da su matrice A_{1},A_{2},\ldots,A_{t} latinski kvadrati. Jednako je lako vidjeti da svojstvo (\ast) povlači i međusobnu ortogonalnost od A_{i} i A_{j}, za međusobno različite i,j = 1,2,\ldots{},t. Stoga je S ortogonalan skup od t latinskih kvadrata reda n.
A_{1}=\Big(a_{ij}^{(1)}\Big)_{ij}, \quad A_{2}=\Big(a_{ij}^{(2)}\Big)_{ij}, \quad \ldots , \quad A_{t}=\Big(a_{ij}^{(t)}\Big)_{ij}
t latinskih kvadrata reda n, takvih da su svaka dva različita međusobno ortogonalna. Neka su, bez smanjenja općenitosti, elementi svih tih latinskih kvadrata iz skupa \lbrace 1,2,\ldots,n\rbrace. Posložimo elemente tih matrica u matricu tipa (t+2,n^{2}) na sljedeći način:
\left(\begin{array}{ccccccccccccc} 1 & 1 & \ldots & 1 & 2 & 2 & \ldots & 2 & \ldots & n & n & \ldots & n \\ 1 & 2 & \ldots & n & 1 & 2 & \ldots & n & \ldots & 1 & 2 & \ldots & n \\ a_{11}^{(1)} & a_{12}^{(1)} & \ldots & a_{1n}^{(1)} & a_{21}^{(1)} & a_{22}^{(1)} & \ldots & a_{2n}^{(1)} & \ldots & a_{n1}^{(1)} & a_{n2}^{(1)} & \ldots & a_{nn}^{(1)} \\ a_{11}^{(2)} & a_{12}^{(2)} & \ldots & a_{1n}^{(2)} & a_{21}^{(2)} & a_{22}^{(2)} & \ldots & a_{2n}^{(2)} & \ldots & a_{n1}^{(2)} & a_{n2}^{(2)} & \ldots & a_{nn}^{(2)} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{11}^{(t)} & a_{12}^{(t)} & \ldots & a_{1n}^{(t)} & a_{21}^{(t)} & a_{22}^{(t)} & \ldots & a_{2n}^{(t)} & \ldots & a_{n1}^{(t)} & a_{n2}^{(t)} & \ldots & a_{nn}^{(t)} \end{array} \right).
Nazovimo tu matricu A. Ako primijetimo da je svaka podmatrica tipa (2,n^{2}) matrice A zapravo kombinacija 2 različita retka matrice A, lako se vidi da joj stupci tvore sve različite uređene parove (njih n^{2}). Naime, za prva dva retka poprilično je jasno. Ako bi i-ti redak (2\lt i \leq t+2) s prvim ili drugim retkom tvorio dva jednaka uređena para, to bi bilo u kontradikciji s činjenicom da je A_{i-2} latinski kvadrat. Ako bi i-ti i j-ti redak (2\lt i\lt j \leq t+2) tvorili dva jednaka uređena para, to bi bilo u kontradikciji s ortogonalnošću latinskih kvadrata A_{i-2} i A_{j-2}. Dakle, matrica A ima i svojstvo (\ast).Obrnuto, neka je A' matrica tipa (t+2,n^{2}), s elementima iz \lbrace 1,2,\ldots,n\rbrace, koja ima svojstvo (\ast). Primijetimo očitu činjenicu da se svaki broj u svakom retku pojavljuje točno n puta. Naime, ako bi se neki broj k pojavljivao više od n puta u i-tom retku, tada bi tvorio više od n uređenih parova oblika (k,\text{nešto}), u nekoj podmatrici u kojoj se nalazi i-ti redak, pa bi neka dva para morala biti jednaka. Ako bi se pak k pojavljivao manje od n puta, tada bi se neki drugi broj k' morao pojaviti više od n puta, pa provedemo analogno razmatranje za k'. Također primijetimo da se svojstvo (\ast) neće pokvariti pri permutiranju stupaca A', pa možemo pretpostaviti da A' ima prvi redak kao matrica A. Promotrimo početni komad duljine n drugog retka matrice A'. Iznad tog komada nalaze se samo jedinice, pa prvih n stupaca možemo permutirati da nam taj početni komad bude (1 \quad 2 \quad \ldots \quad n), a da se ne promijeni prvi redak. To ponovimo i za sljedeći blok duljine n (ispod dvojki), te analogno sve do kraja drugog retka. Dobili smo da prva dva retka matrice A' izgledaju kao prva dva retka matrice A, te je ostalo sačuvano svojstvo (\ast). Dakle, bez smanjenja općenitosti, neka je A'=A. Sad očito možemo reverzibilnim postupkom (dobivanja matrice A iz skupa \lbrace A_{1},A_{2},\ldots,A_{t}\rbrace) iz matrice A dobiti skup S:=\lbrace A_{1},A_{2},\ldots,A_{t}\rbrace. Lako se vidi kako svojstvo (\ast) i prva dva retka matrice A garantiraju da su matrice A_{1},A_{2},\ldots,A_{t} latinski kvadrati. Jednako je lako vidjeti da svojstvo (\ast) povlači i međusobnu ortogonalnost od A_{i} i A_{j}, za međusobno različite i,j = 1,2,\ldots{},t. Stoga je S ortogonalan skup od t latinskih kvadrata reda n.
\ \blacksquare
Primjer 6. Ortogonalna shema latinskih kvadrata M i N primjera 1 je
\left(\begin{array}{ccccccccc} 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 \\ 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\ 1 & 2 & 3 & 2 & 3 & 1 & 3 & 1 & 2 \\ 1 & 2 & 3 & 3 & 1 & 2 & 2 & 3 & 1 \end{array} \right).
Primjer 7. Dva ortogonalna latinska kvadrata reda 10 (prvi se dobije uzimajući u obzir samo znamenke jedinica brojeva u matrici, a drugi gledajući samo znamenke desetica):
\left(\begin{array}{cccccccccc} 00 & 67 & 58 & 49 & 91 & 83 & 75 & 12 & 24 & 36 \\ 76 & 11 & 07 & 68 & 59 & 92 & 84 & 23 & 35 & 40 \\ 85 & 70 & 22 & 17 & 08 & 69 & 93 & 34 & 46 & 51 \\ 94 & 86 & 71 & 33 & 27 & 18 & 09 & 45 & 50 & 62 \\ 19 & 95 & 80 & 72 & 44 & 37 & 28 & 56 & 61 & 03 \\ 38 & 29 & 96 & 81 & 73 & 55 & 47 & 60 & 02 & 14 \\ 57 & 48 & 39 & 90 & 82 & 74 & 66 & 01 & 13 & 25 \\ 21 & 32 & 43 & 54 & 65 & 06 & 10 & 77 & 88 & 99 \\ 42 & 53 & 64 & 05 & 16 & 20 & 31 & 89 & 97 & 78 \\ 63 & 04 & 15 & 26 & 30 & 41 & 52 & 98 & 79 & 87 \end{array} \right).
Za kraj odjeljka spomenimo da ne postoji „elegantna” matematička teorija uz pomoć koje bi se tražile familije ortogonalnih latinskih kvadrata. Uglavnom se za proučavanje ortogonalnih latinskih kvadrata koriste računalne metode za nalaženje, te asimptotske formule za broj takvih.
2Konačne projektivne ravnine
U ovom odjeljku želimo istaknuti samo kombinatorna svojstva projektivnih ravnina, dok geometrijska svojstva zanemarujemo (npr. ne zanima nas je li neka projektivna ravnina Desarguesova6).
Definicija. (Konačna) projektivna ravnina \Pi (reda n \in \mathbb{N}\setminus \lbrace 1\rbrace) je uređena trojka (\mathcal{T},\mathcal{P},\textbf{I}) nepraznih skupova; elemente skupa \mathcal{T} zovemo točke, skupa \mathcal{P} pravci, a \textbf{I} \subseteq \mathcal{T} \times \mathcal{P} je binarna relacija koju zovemo relacija incidencije (ako je (T,p) \in \textbf{I}, kažemo da točka T leži na pravcu p, ili pak da pravac p prolazi točkom T), te vrijedi7:
sijeku u toj točki, te je ona sjecište danih pravaca. Za pravac koji prolazi kroz dvije različite točke kažemo da je spojnica tih dviju točaka, tj. da spaja te dvije točke.
Napomena. Primijetimo da je definicija projektivne ravnine simetrična s obzirom na pojmove točka i pravac. Stoga koju god tvrdnju dokažemo, vrijedit će i njoj dualna tvrdnja dobivena zamjenom pojmova točka\leftrightarrowpravac i svih izvedenih pojmova.
Primjer 8. Ako stavimo \mathcal{T}:=\lbrace 1,2,\ldots,7\rbrace i
\mathcal{P}:=\Big\lbrace \lbrace 1,2,3\rbrace ,\lbrace 3,4,5\rbrace ,\lbrace 1,5,6\rbrace ,\lbrace 1,4,7\rbrace ,\lbrace 2,5,7\rbrace ,\lbrace 3,6,7\rbrace ,\lbrace 2,4,6\rbrace \Big\rbrace ,
tada se lako provjeri da je (\mathcal{T},\mathcal{P},\in) projektivna ravnina reda 2, koju zovemo Fanova ravnina. Možemo je predočiti slikom:
Dokaz. Neka je P bilo koja točka spomenute projektivne ravnine. Kroz nju (po (P3) ) prolazi n+1 različitih pravaca, pri čemu na svakom leži n različitih točaka koje nisu P (po (P4) ). Ti se pravci sijeku u P pa nemaju drugih zajedničih točaka (po (P2) ). Dakle, imamo 1 + (n+1) \cdot n = n^{2}+n +1 različitih točaka. Ostaje provjeriti ima li preostalih. Ako je Q neka točka različita od P, onda (po (P1) ) postoji pravac koji ih spaja. Taj pravac jedan je od onih n+1, pa smo točku Q već uračunali. Dakle, točaka ima n^{2}+n +1, a po prethodnoj napomeni isto toliko ima i pravaca.
\ \blacksquare
Sljedećim teoremom potpuno razotkrivamo vezu između projektivne ravnine reda n i potpunog skupa ortogonalnih latinskih kvadrata reda n. Izlazi da je ta veza 1–1 korespondencija. Štoviše, u dokazu dajemo efektivan način konstrukcije jedne strukture iz druge. To će, u kombinaciji s rezultatima iz prethodnog odjeljka osigurati neke dovoljne uvjete za egzistenciju projektivnih ravnina.
Teorem 10. Neka je n \geq 3 prirodan broj. Postoji projektivna ravnina reda n ako i samo ako postoji potpun skup ortogonalnih latinskih kvadrata reda n.
Dokaz. Neka je dana projektivna ravnina reda n, te fiksirajmo neki pravac p. Neka su sve (međusobno različite) točke koje leže na pravcu p sljedeće: P_{1},P_{2},\ldots,P_{n+1}. Preostalo je n^{2}+n+1-(n+1)=n^{2} različitih točaka koje ne leže na pravcu p. Neka su sve takve Q_{1},Q_{2},\ldots,Q_{n^{2}}. Kroz svaku točku P_{i} prolazi još n različitih pravaca koji nisu p, pa tim n injektivno pridružimo oznake iz skupa \lbrace 1,2,\ldots,n\rbrace, za i=1\ldots{}n+1 (dakle, dva pravca s istom oznakom ne moraju biti jednaka, dok dva pravca s istom oznakom koja oba prolaze točkom P_{i}, za neki i \in \lbrace 1,2,\ldots,n+1\rbrace moraju biti isti pravac). Definirajmo a_{ij} kao pravac koji je jedinstveno određen točkama P_{i} i Q_{j}, te promotrimo matricu
(P1) ). To povlači da Q_{j_{1}} leži na p, što je očita kontradikcija. Dakle, matrica A tipa (n+1,n^{2}), s elementima iz skupa \lbrace 1,2,\ldots,n\rbrace, ima svojstvo (\ast). Prema teoremu 5 , postoji (n-1)-člani ortogonalan skup latinskih kvadrata reda n, a to je upravo potpuni skup ortogonalnih latinskih kvadrata reda n.
Obrnuto, ako postoji potpuni ortogonalni skup latinskih kvadrata reda n, tada po teoremu5 postoji matrica A tipa (n+1,n^{2}), s elementima iz \lbrace 1,2,\ldots,n\rbrace, koja ima svojsto (\ast). Stupce matrice A proglasimo točkama Q_{1},Q_{2},\ldots,Q_{n^{2}} (zbog svojstva (\ast) svaka dva stupca su različita), te uvedimo i dodatne točke P_{1},P_{2},\ldots,P_{n+1}. Neka pravac p sadržava točke P_{1},P_{2},\ldots,P_{n+1} i samo te. Uzmimo da pravac p_{ij}, i=1,2,\ldots{},n, j=1,2,\ldots{},n+1 prolazi točkom P_{j}, te onima i samo onima Q_{k} (k=1,2,\ldots{},n^{2}) kojima se u j-tom retku nalazi broj i. Provjerimo da je konstrukcija dobra, tj. da smo zaista dobili projektivnu ravninu (potrebno je provjeriti aksiome (P1) –(P4) ):
Dakle, konstruirali smo projektivnu ravninu, koja je očigledno reda n. Time je teorem potpuno dokazan.
A := \big( \text{oznaka od } a_{ij}\big)_{i=1,2,\ldots{},n+1,j=1,2,\ldots{},n^{2}}
tipa (n+1,n^{2}). Elementi te matrice očito su iz skupa \lbrace 1,2,\ldots,n\rbrace. Dokažimo da A ima svojstvo (\ast). Ako pretpostavimo da nije tako, tada postoje međusobno različiti i_{1}, i_{2} \in \lbrace 1,2,\ldots,n+1\rbrace i međusobno različiti j_{1}, j_{2} \in \lbrace 1,2,\ldots,n^{2}\rbrace takvi da vrijedi
(\text{oznaka od } a_{i_{1} j_{1}},\ \text{oznaka od } a_{i_{2} j_{1}})=(\text{oznaka od } a_{i_{1} j_{2}}, \ \text{oznaka od } a_{i_{2} j_{2}}).
Izjednačavanjem prvih komponenti uređenih parova dobijemo da je oznaka od a_{i_{1} j_{1}} ista kao i oznaka od a_{i_{1} j_{2}}, za pravce a_{i_{1} j_{1}} i a_{i_{1} j_{2}} koja oba prolaze točkom P_{i_{1}}. Stoga mora biti a_{i_{1} j_{1}} = a_{i_{1} j_{2}}. Potpuno analogno je i a_{i_{2} j_{1}} = a_{i_{2} j_{2}}. Neka je q pravac određen točkama Q_{j_{1}} i Q_{j_{2}}. Vrijedi:
Q_{j_{1}} \ \text{leži na} \ a_{i_{1} j_{1}} = a_{i_{1} j_{2}}, \ Q_{j_{2}} \ \text{leži na} \ a_{i_{1} j_{2}} \ \stackrel{\href{#P1}{(P1)}}{\Rightarrow} \ q=a_{i_{1} j_{2}} \ \Rightarrow \ P_{i_{1}} \ \text{leži na} \ q .
Potpuno analogno vidi se da i P_{i_{2}} leži na q, pa je p=q (po Obrnuto, ako postoji potpuni ortogonalni skup latinskih kvadrata reda n, tada po teoremu
|
\binom{n^{2}}{2} \gt \binom{n}{2} \cdot n \cdot (n+1) \quad \Rightarrow \quad \frac{n^{2}(n^{2}-1)}{2}\gt \frac{n^{2}(n-1)(n+1)}{2},
što je nemoguće. Dakle, svaka dva stupca preklapaju se točno jednom. Neka se broj k nalazi u stupcima i i j matrice A, u istom retku r. Sada je jasno da je p_{kr} jedini pravac koji spaja točke Q_{i} i Q_{j}. |
|
|
|
|
|
|
\ \blacksquare
Sada smo se domogli glavnog rezultata ovog odjeljka:
Dokaz. Za p^{n}=2 imamo Fanovu ravninu. Za ostale prim-potencije egzistencija slijedi direktno iz teorema 4 i teorema 10 .
\ \blacksquare
Prirodno se postavlja pitanje vrijedi li obrat korolara
3Rezultati iz teorije brojeva
Dokazi sljedećih dvaju teorema nisu trivijalni te nemaju direktne veze s našom temom. Stoga ćemo navesti samo iskaze teorema, uz naznaku gdje se ti dokazi mogu pronaći.
Teorem 12. Broj n \in \mathbb{N} može se zapisati u obliku n=k^{2}+m^{2} za neke k,m \in \mathbb{Z} ako i samo ako se u rastavu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom.
Teorem 13. [Lagrange] Za svaki n \in \mathbb{N} postoje x,y,z,w \in \mathbb{Z} takvi da je
n = x^{2}+y^{2}+z^{2}+w^{2}.
Lema 14. Neka je n \in \mathbb{N} takav da je n=p^{2}+q^{2} za neke p,q \in \mathbb{Q}. Tada postoje m,k \in \mathbb{Z} takvi da je n=m^{2}+k^{2}.
Dokaz. Neka je n=\big(\frac{p_{1}}{q_{1}}\big)^{2}+\big(\frac{p_{2}}{q_{2}}\big)^{2}, gdje su p_{1},p_{2} \in \mathbb{Z}, q_{1},q_{2} \in \mathbb{N}. Slijedi \displaystyle (q_{1}q_{2})^{2} n=p_{1}^{2}+p_{2}^{2}. Po teoremu 12 slijedi da se u prikazu broja (q_{1}q_{2})^{2} n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom. U prikazu broja (q_{1}q_{2})^{2} na proste faktore očito se svaki prosti faktor javlja s parnom potencijom. Dakle, u prikazu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja se s parnom potencijom. Po teoremu 12 slijedi da je n=k^{2}+m^{2} za neke k,m \in \mathbb{Z}.
\ \blacksquare
Lema 15. Za brojeve a,b,c,d,x,y,w,z \in \mathbb{R} vrijedi identitet
\begin{align*} (a^{2}+b^{2}+c^{2}+d^{2}) & (x^{2}+y^{2}+z^{2}+w^{2})=\\ = & \ (ax-by-cz-dw)^{2}+(bx+ay-dz+cw)^{2}+\\ & +(cx+dy+az-bw)^{2}+(dx-cy+bz+aw)^{2}. \end{align*}
Dokaz. Trivijalan je posao izmnožiti obje strane i provjeriti jednakost.
\ \blacksquare
Za potrebe sljedećeg dokaza bit će nam zgodna i sljedeća definicija.
Definicija. Reći ćemo da uređena četvorka (x,y,z,w) \in \mathbb{Z}^{4} reprezentira broj t \in \mathbb{Z} ako je t=x^{2}+y^{2}+z^{2}+w^{2}.
4Bruck–Ryserov teorem
Teorem 16. [Bruck–Ryser] Neka je \Pi projektivna ravnina reda n te neka je n \equiv 1 \text{ ili } 2 \pmod{4}. Tada je n=k^{2}+m^{2} za neke k,m \in \mathbb{Z}.
Dokaz. Neka je \Pi projektivna ravnina reda n te neka je n \equiv 1 \text{ ili } 2 \pmod{4}. Po propoziciji 9 , ravnina \Pi sadržava n^{2}+n+1=:v točku, i jednako toliko pravaca. Lako je vidjeti da je v+1 \equiv 0 \pmod{4}. Neka su P_{1},P_{2},\ldots,P_{v} točke, a l_{1},l_{2},\ldots,l_{v} pravci ravnine \Pi. Neka su x_{1},x_{2},\ldots,x_{v} varijable s vrijednostima u \mathbb{R}, te označimo
Vrijede identiteti:
Identitet (6 ) dobijemo tako da nakon kvadriranja identiteta (5 ) i sumiranja po i=1,2,\ldots,v iskoristimo aksiome (P1) i (P3) . Identitet (7 ) je malo zgodnije zapisan identitet (6 ). Uvedimo još jednu varijablu x_{v+1} s vrijednošću u \mathbb{R} te pribrojimo nx_{v+1}^{2} u (7 ). Dobijemo
gdje je T:=\sum_{i=1}^{v}x_{i}. Po teoremu 13 postoje nenegativni brojevi a,b,c,d \in \mathbb{Z} takvi da je n=a^{2}+b^{2}+c^{2}+d^{2}. Neka je matrica A_{n} \in M_{4}(\mathbb{R}) dana s
15 povlači da (x,y,z,w)A_{n} reprezentira broj tn. Zato možemo pisati
gdje je
Sustav (10 ) možemo napisati u obliku
9 ) uvrstimo u (8 ) te dobijemo
gdje su L_{1},L_{2},\ldots,L_{v},x_{v+1},T linearne kombinacije varijabli y_{1},y_{2},\ldots,y_{v+1}. Izraz (11 ) je valjan za svaku valuaciju varijabli y_{1},y_{2},\ldots,y_{v+1}. Želimo uzeti takav y_{1} da bude y_{1}^{2}=L_{1}^{2}. Kako bismo se uvjerili da je to moguće, promotrimo sljedeća dva slučaja:
Nakon te supstitucije, identitet (11 ) sada postaje
gdje su x_{v+1},T linearne kombinacije varijable y_{v+1}. Tada je x_{v+1}=\alpha{}y_{v+1}, T=\beta{}y_{v+1} za neke \alpha, \beta \in \mathbb{Q} (primijetimo da su koeficijenti svih linearnih kombinacija tijekom cijelog dokaza racionalni brojevi – ni jedan korak u dokazu nije za posljedicu imao gubitak racinalnosti koeficijenata). Izaberimo sada y_{v+1}:=1. Sada (12 ) povlači
14 povlači da je n=m^{2}+k^{2} za neke m,k \in \mathbb{Z}.
(5)
L_{i}:=\sum_{\lbrace j \ : \ P_{j} \text{ leži na } l_{i}\rbrace } x_{j}, \qquad i=1,2,\ldots,v.
(6)
\sum_{i=1}^{v}L_{i}^{2} = 2 \sum_{i=1}^{v}\sum_{j=i+1}^{v}x_{i}x_{j} + (n+1) \sum_{i=1}^{v}x_{i}^{2},
(7)
\sum_{i=1}^{v}L_{i}^{2} = n \sum_{i=1}^{v}x_{i}^{2} + \Big(\sum_{i=1}^{v}x_{i}\Big)^{2}.
(8)
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = n \sum_{i=1}^{v+1}x_{i}^{2} + T^{2},
A_{n}:=\left(\begin{array}{rrrr} a & b & c & d \\ -b & a & d & -c \\ -c & -d & a & b \\ -d & c & -b & a \end{array}\right).
Nije teško vidjeti da je \det{}A_{n}=(a^{2}+b^{2}+c^{2}+d^{2})^{2}=n^{2} \neq 0, pa je A_{n} regularna matrica. Ako (x,y,z,w) reprezentira broj t, tada lema
(9)
n(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2},
(10)
(y_{1},y_{2},y_{3},y_{4})=(x_{1},x_{2},x_{3},x_{4})A_{n}.
(x_{1},x_{2},x_{3},x_{4})=(y_{1},y_{2},y_{3},y_{4})A_{n}^{-1}.
Primijetimo da su elementi matrice A_{n}^{-1} iz \mathbb{Q}. Dakle, svaki x_{1},x_{2},x_{3},x_{4} je linearna kombinacija varijabli y_{1},y_{2},y_{3},y_{4} s racionalnim koeficijentima. Te linearne kombinacije zajedno s (
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2} + n \sum_{i=5}^{v+1}x_{i}^{2} + T^{2},
gdje su L_{1},L_{2},\ldots,L_{v},T linearne kombinacije (s racionalnim koeficijentima) varijabli y_{1},y_{2},y_{3},y_{4},x_{5},x_{6},\ldots,x_{v+1}. Isti postupak napravimo i za sljedeću uređenu četvorku (x_{5},x_{6},x_{7},x_{8}), i tako dalje, sve do (x_{v-2},x_{v-1},x_{v},x_{v+1}) jer je v+1 \equiv 0 \pmod{4}. Dobijemo identitet
(11)
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = \sum_{i=1}^{v+1}y_{i}^{2} + T^{2},
| \bullet | Ako u linearnoj kombinaciji L_{1}, y_{1} dolazi s koeficijentom 1, tada jednadžbu y_{1}=-L_{1} očito možemo riješiti po y_{1}, tj. možemo za y_{1} uzeti neku linearnu kombinaciju varijabli y_{2},y_{3},\ldots,y_{v+1} takvu da je y_{1}^{2}=L_{1}^{2}. |
| \bullet | Ako u linearnoj kombinaciji L_{1}, y_{1} dolazi s koeficijentom različitim od 1, tada možemo analogno izvesti isti zaključak kao u prošlom slučaju, proučavajući jednadžbu y_{1}=L_{1}. |
\sum_{i=2}^{v}L_{i}^{2} + nx_{v+1}^{2} = \sum_{i=2}^{v+1}y_{i}^{2} + T^{2},
gdje su L_{2},L_{3},\ldots,L_{v},x_{v+1},T linearne kombinacije varijabli y_{2},\ldots,y_{v+1}. Ponavljajući taj postupak (za y_{2},y_{3},\ldots,y_{n} redom), dobijemo identitet
(12)
nx_{v+1}^{2} = y_{v+1}^{2} + T^{2},
n \alpha^{2}=1+\beta^{2} \quad \stackrel{\alpha \neq 0}{\Rightarrow} \quad n=\Big(\frac{1}{\alpha}\Big)^{2}+\Big(\frac{\beta}{\alpha}\Big)^{2}, \quad \frac{1}{\alpha}, \frac{\beta}{\alpha} \in \mathbb{Q}.
Lema
\ \blacksquare
Korolar 17. [Bruck–Ryser, alternativna formulacija] Ako je n prirodan broj za koji vrijedi n \equiv 1 \text{ ili } 2 \pmod{4} i ako nekvadratni dio9 broja n u rastavu na proste faktore sadržava barem jedan prosti faktor p takav da je p \equiv 3 \pmod{4}, tada ne postoji projektivna ravnina reda n.
Dokaz. Pretpostavimo da postoji projektivna ravnina reda n te neka vrijedi n \equiv 1 \text{ ili } 2 \pmod{4}. Tada je po teoremu 16 n=m^{2}+k^{2} za neke m,k \in \mathbb{Z}. Teorem 12 povlači da se u rastavu broja n na proste faktore svaki prosti faktor p za koji je p \equiv 3 \pmod{4} javlja s parnom potencijom. Očito tada nekvadratni dio broja n ne sadržava ni jedan prosti faktor p za koji je p \equiv 3 \pmod{4}. Obratom po kontrapoziciji dobivamo tvrdnju korolara.
\ \blacksquare
Korolar
Krajem prošlog stoljeća uz pomoć računala je dokazano da ne postoji projektivna ravnina reda 10, dok je pitanje o postojanju projektivne ravnine reda 12 i dalje otvoren problem. Vidi
5Poopćenje
U ovom odjeljku iskazat ćemo poopćenje teorema
Definicija. Neka su v,k,\lambda \in \mathbb{N} takvi da je v \geq k \geq 2. Uređen par (X,\mathcal{A}), gdje je \mathcal{A} \subseteq \mathcal{P}(X), zovemo (v,k,\lambda)-balansiran nepotpun blok dizajn (kraće ćemo pisati (v,k,\lambda)-BIBD10), ako vrijedi:
Nadalje, kažemo da je (v,k,\lambda)-BIBD simetričan ako je \lambda (v-1)=k^{2}-k.
| (B1) | \text{card}(X)=v; |
| (B2) | Svaki blok (tj. element od \mathcal{A}) sadržava točno k elemenata; |
| (B3) | Svaki neuređeni par različitih elemenata iz X nalazi se u točno \lambda blokova. |
Sada nije teško vidjeti da je projektivna ravnina reda n zapravo (n^{2}+n+1,n+1,1)-BIBD, uz identifikaciju: pravac \leftrightarrow blok (tj. pravac smatramo skupom točaka koje na njemu leže). Štoviše, projektivna ravnina reda n simetričan je (n^{2}+n+1,n+1,1)-BIBD. Sada smo u mogućnosti iskazati najavljeni teorem:
Teorem 18. [Bruck–Ryser–Chowla] Uzmimo da postoji simetričan (v,k,\lambda)-BIBD. Ako je v paran broj, tada je k- \lambda=w^{2} za neki w \in \mathbb{Z}. Ako je v neparan broj, tada postoje x,y,z \in \mathbb{Z} koji nisu svi nula, tako da vrijedi:
(13)
x^{2}=(k- \lambda)y^{2}+(-1)^{\frac{v-1}{2}} \lambda z^{2}.
Zašto je teorem
Pretpostavimo prvo da je n \equiv 0 \text{ ili } 3 \pmod{4}. Tada se jednakost (
Pretpostavimo sada da je n \equiv 1 \text{ ili } 2 \pmod{4}. Tada se jednakost (
Bibliografija
| [1] | T. W. Hungerford, Algebra, Springer, 2003 |
| [2] | D. R. Stinson, Combinatorial desings, construction and analysis, Springer, 2004 |
| [3] | S. Radas, Ortogonalni latinski kvadrati, magistarski rad, PMF–Matematički odjel, Sveučilište u Zagrebu, 1988 |
| [4] | D. R. Huges, F. C. Piper, Projective planes, Springer, 1973 |
| [5] | D. Palman, Projektivna geometrija, Školska knjiga, 1984 |
| [6] | A. Dujella, Uvod u teoriju brojeva, skripta, PMF–Matematički odjel, Sveučilište u Zagrebu, http://web.math.hr/~duje/utb/utblink.pdf |
| [7] | C. W. H. Lam, The Search for a Finite Projective Plane of Order 10, The American Mathematical Monthly Volume 98, Issue 4 (str. 305–318), 1991 |
5Takvu matricu zovemo ortogonalna shema redan, jakosti 2 i indeksa 1}. Za detalje vidi [3] , str. 25. ili [2] str. 140. odnosno str. 225.
6Vidi npr. [5] , str. 26.
7Projektivna ravnina najčešće se definira uz pomoć tri aksioma: (P1) , (P2) i (P5): postoje 4 točke od kojih tri ne leže na istom pravcu. Ako je neki od skupova \mathcal{T} ili \mathcal{P} konačan, tada se pokazuje da vrijede (P3) i (P4) za neki n \in \mathbb{N}, koji tada zovemo red dane projektivne ravnine. Za datalje vidi npr. [4] , str. 79. ili [5] , str. 55.
