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.
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 skupa\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 skup
\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
\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
2 zaključiti da ne postoji ni jedan latinski kvadrat koji bi istovremeno bio ortogonalan s
M i
N.
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-potencija
. 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ći
:
a_{0}=0,
a_{1}=1,
a_{2},
a_{3},
\ldots,
a_{n-1}. Definirajmo matrice
(1)
A_{k}=\Big(a_{ij}^{(k)}\Big)_{i,j=0,1,\ldots{},n-1} \qquad k=1,2,\ldots{},n-1
na sljedeći način:
(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.
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:
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 (
2) imamo:
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 (
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
\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}}.
Nakon što od (
3) oduzmemo (
4) te iskoristimo komutativnost, asocijativnost i distributivnost u polju, dobijemo
(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 (
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.
\ \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.
Nazovimo to svojstvo
(\ast).
Dokaz. Neka su
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
Desarguesova).
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 vrijedi
:
|
(P1) |
Za svake dvije različite točke postoji jedinstven pravac na kojem obje leže; |
|
(P2) |
Za svaka dva različita pravca postoji jedinstvena točka kojom oba prolaze; |
|
(P3) |
Svakom točkom prolazi točno n+1 pravac; |
|
(P4) |
Na svakom pravcu leži točno n+1 točka. |
Za dva različita pravca koja prolaze istom točkom kažemo da se
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:
Propozicija 9. Projektivna ravnina reda
n sadržava
n^{2}+n+1 točku i isto toliko pravaca.
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
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
(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 teoremu
5 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)):
|
(P1): Za kombinaciju točaka P_{i} i P_{j} (i,j=1,2,\ldots{},n+1, i \neq j) jasno vrijedi – pravac p je jedini koji ih spaja). Također je jasno i za kombinaciju Q_{i} i P_{j} (i=1,2,\ldots{},n^{2}, j=1,2,\ldots{},n+1) – jedino ih spaja pravac p_{kj}, gdje je k broj na mjestu (j,i) matrice A. Za kombinaciju Q_{i} i Q_{j} (i,j=1,2,\ldots{},n^{2}, i \neq j) dovoljno je pokazati da i-ti i j-ti stupac matrice A imaju u točno jednom retku isti broj (reći ćemo da se preklapaju točno jednom). Budući da se svaki broj, u svakom retku matrice A javlja točno n puta, broj svih preklapanja svih stupaca je \binom{n}{2} \cdot n \cdot (n+1). Očito se zbog svojstva (\ast) dva različita stupca mogu preklapati najviše jednom. Ako se neka dva stupca ne preklapaju, tada je
\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}. |
|
(P2): Za pravce p i p_{ij} (i=1,2,\ldots{},n, j=1,2,\ldots{},n+1) očito vrijedi, sijeku se samo u točki P_{j}. Također je jasno da je jedina zajednička točka pravaca p_{i_{1} j} i p_{i_{2} j} (i_{1},i_{2}=1,2,\ldots{},n, i_{1} \neq i_{2}, j=1,2,\ldots{},n+1) upravo P_{j}. Sad promotrimo pravce p_{i_{1} j_{1}} i p_{i_{2} j_{2}} (i_{1},i_{2}=1,2,\ldots{},n, j_{1},j_{2}=1,2,\ldots{},n+1, j_{1} \neq j_{2}). Redci j_{1} i j_{2} matrice A (svojstvo (\ast)) tvorit će sve uređene parove iz skupa \lbrace 1,2,\ldots,n\rbrace, pa među ostalim i par (i_{1},i_{2}), i to točno jednom. Zato promatrani pravci imaju jedinstveno sjecište. |
|
(P3): Za točke P_{i} (i=1,2,\ldots{},n+1) očito vrijedi. Međutim, vrijedi i za Q_{j} (j=1,2,\ldots{},n^{2}), jer se u svakom stupcu matrice A nalazi n+1 brojeva. |
|
(P4): Za pravac p očito vrijedi. Pravac p_{ij} (i=1,2,\ldots{},n, j=1,2,\ldots{},n+1) osim P_{j}, sadržava još točno n različitih točaka, jer se u j-tom retku matrice A broj i pojavljuje točno n puta. |
Dakle, konstruirali smo projektivnu ravninu, koja je očigledno reda
n. Time je teorem potpuno dokazan.
\ \blacksquare
Sada smo se domogli glavnog rezultata ovog odjeljka:
Korolar 11. [Veblen–Bussey] Za svaku prim-potenciju
p^{n} postoji projektivna ravnina reda
p^{n}.
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
11 (je li red svake konačne projektivne ravnine prim-potencija?). To pitanje i dalje nije riješeno, te je preraslo u tzv.
hipotezu o prim-potencijama, koja kaže da je red svake konačne projektivne ravnine prim-potencija. Rezultat koji bi bio najbliži spomenutoj hipotezi dali su još 1949. godine R. H. Bruck i H. J. Ryser, a mi ćemo ga dokazati. Međutim, bit će nam potrebni neki netrivijalni rezultati iz teorije brojeva.
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.
Dokaz. Vidi
[6], str. 43.
\ \blacksquare
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}.
Dokaz. Vidi
[6], str. 44.–45.
\ \blacksquare
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
(5)
L_{i}:=\sum_{\lbrace j \ : \ P_{j} \text{ leži na } l_{i}\rbrace } x_{j}, \qquad i=1,2,\ldots,v.
Vrijede identiteti:
(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}.
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
(8)
\sum_{i=1}^{v}L_{i}^{2} + nx_{v+1}^{2} = n \sum_{i=1}^{v+1}x_{i}^{2} + T^{2},
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
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
15 povlači da
(x,y,z,w)A_{n} reprezentira broj
tn. Zato možemo pisati
(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},
gdje je
(10)
(y_{1},y_{2},y_{3},y_{4})=(x_{1},x_{2},x_{3},x_{4})A_{n}.
Sustav (
10) možemo napisati u obliku
(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 (
9) uvrstimo u (
8) te dobijemo
\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},
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:
|
\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}. |
Nakon te supstitucije, identitet (
11) sada postaje
\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},
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
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
14 povlači da je
n=m^{2}+k^{2} za neke
m,k \in \mathbb{Z}.
\ \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 dio
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
11 nam kaže da postoje projektivne ravnine redova
2,
3,
4,
5,
7,
8,
9,
11,
\ldots{} Korolar
17 nam kaže da ne postoje projektivne ravnine redova
6,
14,
21,
22,
\ldots{} Međutim, već za red
10,
12 ili
15 navedeni rezultati ne mogu nam dati odgovor. Može se lako pokazati da postoji beskonačno mnogo prirodnih brojeva za koje navedeni rezultati ne daju odgovor.
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
[7].
5Poopćenje
U ovom odjeljku iskazat ćemo poopćenje teorema
16, koje su našli H. J. Ryser i S. Chowla 1950. godine. No prije toga potrebno je definirati nešto općenitiju strukturu od konačne projektivne ravnine. Promatrat ćemo konačne projektivne ravnine s aspekta
teorije dizajna.
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)-BIBD
), ako vrijedi:
|
(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. |
Nadalje, kažemo da je
(v,k,\lambda)-BIBD
simetričan ako je
\lambda (v-1)=k^{2}-k.
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}.
Dokaz. Vidi
[2], str. 30.–35.
\ \blacksquare
Zašto je teorem
18 općenitiji slučaj teorema
16? Pretpostavimo da postoji projektivna ravnina reda
n, tj. da postoji simetričan
(n^{2}+n+1,n+1,1)-BIBD, te primijetimo da je
n^{2}+n+1 uvijek neparan broj.
Pretpostavimo prvo da je
n \equiv 0 \text{ ili } 3 \pmod{4}. Tada se jednakost (
13) reducira na jednadžbu
x^{2}=ny^{2}+z^{2}, koja uvijek ima netrivijalno rješenje
x=z=1,
y=0. Dakle, u slučaju
n \equiv 0 \text{ ili } 3 \pmod{4} teorem Bruck–Ryser–Chowla ne daje odgovor o (ne)postojanju projektivne ravnine reda
n.
Pretpostavimo sada da je
n \equiv 1 \text{ ili } 2 \pmod{4}. Tada se jednakost (
13) reducira na
x^{2}+z^{2}=ny^{2}, pa je (po lemi
14)
n=m^{2}+k^{2} za neke
m,k \in \mathbb{Z}, što je upravo tvrdnja teorema
16.
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 |
