Yazarlar: Elif Seçkin, Figen Şenses, Bülent Ünal
Özel bir matris türü olan Latin kareler, kombinasyon tasarımlarında ve istatistikte yapılan deneylerde geniş uygulama alanına sahiptir. Konuya Latin kareyi tanımlamakla başlayalım. \(n\) elemanlı bir küme üzerinde tanımlanan \(n×n\) boyutunda bir kare matrisinin her satır ve sütununda kümenin elemanları birer kez kullanılıyorsa bu matrise Latin kare denir. Böyle bir matrise Latin kare denmesinin nedeni bu yapının ilk ortaya çıktığında kümenin elemanlarının Latin harfleri olarak alınmasındandır. Ancak, tanımlarda ve hesaplarda sağlayacağı kolaylık açısından genellikle \({1, 2, \dots, n}\) veya \({0, 1, \dots, n-1}\) kümesi tercih edilir.
\(2×2\) boyutunda \({1, 2}\) kümesi üzerinde tanımlı sadece 2 tane Latin kare vardır:
\( \begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix} \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \)
Aşağıda da \({1, 2, \dots, 5}\) kümesi üzerinde tanımlı \(5×5\) boyutunda bir Latin kare yer almaktadır.
\(L\) = \(\begin{matrix} 4 & 2 & 3 & 5 & 1 \\ 1 & 3 & 5 & 4 & 2 \\ 3 & 4 & 2 & 1 & 5 \\ 2 & 5 & 1 & 3 & 4 \\ 5 & 1 & 4 & 2 & 3 \\ \end{matrix}\)
Birinci satırı \( (1 2 3 \dots n)\) olan \(n × n\) boyutunda Latin kareye standart formda denir. Her Latin kareden standart formda Latin kareler elde edilebilir. Orneğin, yukarıdaki \(5×5 L \) Latin karesinden standart formda bir latin kare elde edelim. Eğer her 4 yerine 1, her 5 yerine 4, her 1 yerine de 5 yazarsak standart formdaki \(L_{1}\) karesini buluruz.
\(L_1\) = \(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 1 & 2 \\ 3 & 1 & 2 & 5 & 4 \\ 2 & 4 & 5 & 3 & 1 \\ 4 & 5 & 1 & 2 & 3 \\ \end{matrix}\)
\(L\) ‘nin sütunlarını değiştirerek de standart formda bir Latin kare bulunabilir: 1. sütunu 4. sütun, 5. sütunu 1. sütun ve 4. sütunu 5. sütun olarak yazarsak \(L_2\) standart karesi elde edilir:
\(L_2\) = \(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \\ 5 & 4 & 2 & 3 & 1 \\ 4 & 5 & 1 & 2 & 3 \\ 3 & 1 & 4 & 5 & 2 \\ \end{matrix}\)
Daha önceki örneğimizde \(2×2\) boyutunda sadece 2 tane Latin karesi olduğunu görmüştük. Şimdi de \(3×3\) Latin karelerine bakalım. Birinci satır ve sütunu doldurulmuş olan Latin karesini sadece bir şekilde tamamlayabiliriz. İlk satır ve ilk sütunu 1 2 3 şeklinde alınırsa
\( \begin{matrix} 1 & 2 & 3\\ 2 & · & · \\ 3 & · & · \end{matrix}\)
ikinci satırın ikinci ve üçüncü elemanı 3 veya 1 olabilir. Fakat bu satırın 3. sütununa 3 yazamayız, çünkü 3. sütunda 3 var. Böylece ikinci satırı \(2 3 1 \) şeklinde doldururuz, ve son satıra da tek seçenek olarak \( 3 1 2 \)kalır
\( \begin{matrix} 1 & 2 & 3\\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{matrix}\)
Sütunları \(3! = 6\) değişik şekilde yazabiliriz. Bu permütasyonların herbirinin satırlarını, ilk satırı sabit tutarak, 2 şekilde sıralayabiliriz. Böylece 12 farklı \(3×3\) Latin karesi elde ederiz.
\( \begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{matrix} \begin{matrix} 1 & 3 & 2 \\ 2 & 1 & 3 \\ 3 & 2 & 1 \end{matrix} \begin{matrix} 2 & 3 & 1 \\ 3 & 1 & 2 \\ 1 & 2 & 3 \end{matrix} \)
\( \begin{matrix} 2 & 1 & 3 \\ 3 & 2 & 1 \\ 1 & 3 & 2 \end{matrix} \begin{matrix} 3 & 1 & 2 \\ 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix} \begin{matrix} 3 & 2 & 1 \\ 1 & 3 & 2 \\ 2 & 1 & 3 \end{matrix} \)
\( \begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2\\ 2 & 3 & 1 \end{matrix} \begin{matrix} 1 & 3 & 2 \\ 3 & 2 & 1 \\ 2 & 1 & 3 \end{matrix} \begin{matrix} 2 & 3 & 1 \\ 1 & 2 & 3\\ 3 & 1 & 2 \end{matrix} \)
\( \begin{matrix} 2 & 1 & 3 \\ 1 & 3 & 2\\ 3 & 2 & 1 \end{matrix} \begin{matrix} 3 & 1 & 2 \\ 2 & 3 & 1\\ 1 & 2 & 3 \end{matrix} \begin{matrix} 3 & 2 & 1 \\ 2 & 1 & 3\\ 1 & 3 & 2 \end{matrix} \)
Birinci satır ve sütunu (\(1 2 3 4\)) olan \(4×4\) boyutunda 4 tane Latin karesi vardır. Bu karelerin her birinden, önce 4 tane sütununun 24 permütasyonunu sonra da kalan 3 satırın 6 permütasyonunu göz önüne alarak \(24·6=144\) Latin kare elde ederiz. Böylece birbirinden farklı \(4·144=576\) olarak bulunur.
\(5×5\) Latin karelerinin sayısına bakalım. İlk satır ve sütunu (\(1 2 3 4 5\)) olan \(5×5\) Latin karelerinin sayısı 56’dır. 5 sütunun ve ilk satır dışındaki 4 satırın permütasyonları ile bu 56 Latin karenin herbirinden \(5!·4!=2880\) farklı Latin kare elde ederiz. Bu nedenle \(56·2880=161.280\) tane \(5×5\) latin kare vardır.
\(L_1=(a_{ij})\) ve \(L_2=(b_{ij})\) \(n×n\) boyutunda iki Latin kare olsun. Eğer tüm \(i,j=1,\dots,n\) için (\(a_{ij},b_{ij}\)) sıralı ikilileri farklı oluyorsa \(L_1\) ve \(L_2\) birbilerine dik Latin karelerdir denir.
Daha önceki örneğimizde \(2×2\) boyutunda sadece 2 tane Latin kare olduğunu görmüştük, bunlar birbirine dik olmadığından \(2×2\) boyutunda dik Latin kareler yoktur. \(3×3\) boyutunda birbirine dik sadece bir Latin kare çifti vardır, ve bunlar şu karelerdir:
\( \begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{matrix} \) ve \( \begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2\\ 2 & 3 & 1 \end{matrix} \)
Dik Latin kareleri tek bir kare ile gösterebiliriz. Örneğin yukarıdaki \(3×3\) dik Latin kareler
\( \begin{matrix} 11 & 22 & 33 \\ 23 & 31 & 12\\ 32 & 13 & 21 \end{matrix} \)
şeklinde de gösterilebilir.
İlk ortaya çıktıklarında Latin karelerin Latin harfleri ile inşa edildiklerini söylemiştik. Dik Latin karelerin gösteriminde ise, karelerin birincisi için Latin harfleri; ikincisi için Yunan harfleri kullanılırdı. Bu nedenle dik Latin karelere Greko-Latin Kareler adı da verilir. Bu gösterimle, yukarıdaki 3 x 3 dik Latin kareler ve ortaya çıkan Greko-Latin kare şöyle yazılabilir:
\( \begin{matrix} A & B & C \\ B & C & A \\ C & A & B \end{matrix} \begin{matrix} α & β & γ \\ γ & α & β \\ β & γ & α \end{matrix} \begin{matrix} Aα & Bβ & Cγ \\ Bγ & Cα & Aβ \\ Cβ & Aγ & Bα \end{matrix} \)
\(n×n\) boyutlarında dik Latin kare çiftlerinin elde edilmesi ilgi çekici bir problemdir. $n$ tek olduğunda böyle bir çift her zaman vardır ve bunları yazmak için birçok algoritma da verilmiştir. Örneğin, \(n\) tek doğal sayı olmak üzere, \(L_1=(a_{ij})\), \(a_{ij}=i+j mod(n)\) ve \(L_2=(b_{ij})\), \(b_{ij}=i+2j \)mod(\(n\)) şeklinde oluşturulan \(L_1\) ve \(L_2\) matrisleri \({0,1,2,\dots,n-1}\) kümesi üzerinde dik Latin karelerdir. \(n=5\) için uygulanırsa,
\(L_1\) = \( \begin{matrix} 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ \end{matrix} \) ve \( L_2\) = \( \begin{matrix} 3 & 0 & 2 & 4 & 1 \\ 4 & 1 & 3 & 0 & 2 \\ 0 & 2 & 4 & 1 & 3 \\ 1 & 3 & 0 & 2 & 4 \\ 2 & 4 & 1 & 3 & 0 \\ \end{matrix} \)
elde edilir. \(n\) çift ise, \(n=2\) halinde olduğu gibi, dik Latin kare çiftleri bulunmayabilir. Çeşitli boyutlarda dik Latin kare çiftlerinin olup olmadığını ilk araştıran Leonhard Euler (1707-1783) olmuştur. Euler, 1782’de ‘k negatif olmayan bir tamsayı olmak üzere \(4k+2\) boyutunda birbirlerine dik Latin kare çifti yoktur’ şeklinde bir konjektür ortaya atmıştır. \(2×2\) ( \(k=0\) ) için konjektürün doğru olduğu zaten aşikardı. Uzun yıllar konjektür ortada kaldıktan sonra, G. Tarry 1900 yılında \(6×6\) ( \(k=1\) ) halinde birbirlerine dik Latin kare çifti olmadığını doğrulamıştır. Ancak, 1960 yılında R.C. Bose, S.S. Shrikhande ve E.T. Parker, Euler’in konjektürünün \(k≥2\) için yanlışlığını göstermişlerdir, yani \(k ∈ Z^+\) , \(k≥2\) olmak üzere \(4k+2\) boyutunda en azından bir tane birbirlerine dik Latin kare çifti olduğunu ispatlamışlardır.
Aşağıda verilen üç Latin karenin herhangi ikisinin birbirilerine dik olduğu görülmektektedir…
\( \begin{matrix} 3 & 4 & 5 & 1 & 2 \\ 5 & 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 5 & 1 \\ 4 & 5 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 & 5 \\ \end{matrix} \begin{matrix} 4 & 5 & 1 & 2 & 3\\ 2 & 3 & 4 & 5 & 1 \\ 5 & 1 & 2 & 3 & 4 \\ 3 & 4 & 5 & 1 & 2 \\ 1 & 2 & 3 & 4 & 5 \\ \end{matrix} \begin{matrix} 5 & 1 & 2 & 3 & 4 \\ 4 & 5 & 1 & 2 & 3\\ 3 & 4 & 5 & 1 & 2 \\ 2 & 3 & 4 & 5 & 1 \\ 1 & 2 & 3 & 4 & 5 \\ \end{matrix} \)
Şimdi şunu iddia ediyoruz: \(n\), 2’den büyük bir doğal sayı olmak üzere, \(n×n\) boyutunda birbirlerine dik Latin karelerinin maksimum sayısı \(n-1\) ‘dir. İddiamızın doğruluğunu göstermek için \(L_1,L_2,\dots,L_k\) \((0,1,2,\dots,k)\) kümesi üzerinde tanımlı, her biri diğerleri ile dik olan \(n×n\) boyutunda Latin kareleri göz önüne alalım ve \(L_m (1≤m≤k)\) karesini \((i,j)\) elemanını da \(a_{ij}^{(m)}\) ile gösterelim. \(a_{11}^{(1)}=a\) ve \(a_{11}^{(2)}=b\) olsun. \((0≤a,b≤n-1)\). \(a\) sayısı \(L_1\)’in ikinci satırında \(j\) numaralı sütununda bulunuyorsa yani \(a_{2j}^{(1)}=a\) \((j\neq1)\) ise \(L_1\) ve \(L_2\) dik olduklarından \(a_{2j}^{(2)}=b\) olamaz. O halde, \(a_{2j}^{(2)}\) için kullanılabilecek en fazla \(n-1\) sayı var. Bu argümana devamla sonuca gidebiliriz.
Herhangi bir \(n\) için birbirlerine dik en fazla \(n-1\) Latin kare yazılabileceğini gösterdik. Peki ne zaman tam \(n-1\) tane böyle Latin kare yazabiliriz? Bu sorunun cevabı da şöyle verilebilir: Eğer \(p\) asal bir sayı ve \(n=p^t (t,n ∈Z^+,n>1)\) ise \(n×n\) boyutunda \(n-1\) tane \(L_1,L_2,\dots,L_{n-1}\) dik Latin kareleri vardır ve \(L_m=(a_{ij}^{(m)})\) olmak üzere bu kareler \((a_{ij}^{(m)})=i+mj\) mod\((n) \)\((0≤i,j≤n-1; m=1,2,\dots,n-1)\) şeklinde tanımlanabilir. Bu iddianın ispatına her \(k\in {1,2,\dots,n-1}\) için \(L_k\)’nin bir Latin kare olduğunu göstermekle başlayalım… Farz edelim ki, \(L_k\) bir Latin kare değildir. O halde \(L_k\)’nin belli bir satırında veya sütununda tekrarlanan sayı olacaktır. Eğer \(t.\) sütunda sayı tekrarı varsa \(r≠s\) olmak üzere öyle \(r,s ∈\){\(1,2,\dots,n\)} bulunabilir ki \(a_{rt}^{(k)}=a_{st}^{(k)}\) olur. Tanım gereği \(r+kt=s+kt\) mod\((n) \)\(⇒r=s\) bulunur ki bu \(r≠s\) ile çelişir. Bu çelişkiden \(L_k\)’nin hiçibir sütununda tekrar olmadığı anlaşılır. Tekrarlama \(t.\) satırda ise \(r≠s\) olmak üzere öyle \(r,s ∈\){\(1,2,\dots,n\)} vardır ki \(a_{tr}^{(k)}=a_{ts}^{(k)}\)’dir. Buradan \(t+rk=t+sk\) mod\((n) \) yani \(rk=sk\) mod\((n) \) elde edilir. \(k≠0 r,s∈\){\(1,2,\dots,n\)} ve \(n=p^t\) olduğundan \(r=s\) olur ki bu da çelişkidir, yani \(L_k\)`nın hiçbir satırında da tekrar yoktur. \(L_k\) “Latin kare değildir kabulü” çelişkili netice doğurduğundan doğru bir kabul değildir,yani “\(L_k\) Latin kare değilidir” olamaz, o halde her \(k=1,2,\dots,n-1 \) için yukarıdaki gibi tanımlanmış \(L_k\) bir Latin karedir. Şimdi de bu karelerin dikliğini gösterelim… Farz edelim ki \(L_k\) ve \(L_m (1≤k≠m≤n-1)\) dik değildir. Bir başka deyişle, \(1≤i,j,r,s≤n\) ve \((i,j)≠(r,s)\) için \(a_{ij}^{(k)}=a_{ij}^{(k)}=a_{rs}^{(k)}\) ve \(a_{ij}^{(m)}=a_{rs}^{(m)}\) olduğunu farz edelim. Tanımlardan \(i+kj=r+ks\) mod\((n) \) ve \(i+mj=r+ms\) mod\((n) \) elde edilir. İki eşitliğin taraf tarafa farkları alınarak \((k-m)j=(k-m)s\) mod\((n) \) yazılır. \(k≠m\) alındığında \(k-m≠0\) olur ve \(n\) de \(p^t (p\) -asal\()\) tipinde olduğu için \(j=s\) olduğu görülür. Bu eşitlik \(i+kj=r+ks\) mod\((n) \)’de yerine konularak \(i=r\) bulunur. Yani, \((i,j)=(r,s)\) sonucu elde edilir ki bu da çelişkidir. O halde \(L_k\) ve \(L_m\) birbirlerine dik karelerdir.
Şimdi, bu metodu kullanarak \(5×5\) boyutunda 4 tane dik Latin kare yazalım: \(L_1\) karesi \(a_{ij}^{(1)}=i+j \) mod\((5) \) ile tanımlı, o halde
\( a_{11}^{(1)}=1+1=2 ; a_{12}^{(1)}=1+2=3\)
\( a_{13}^{(1)}=1+3=4 ; a_{14}^{(1)}=1+4=5=0\)
\( a_{15}^{(1)}=1+0=1 ; a_{21}^{(1)}=2+1=3\)
\( · ·\)
\( · ·\)
\( · ·\)
ve sonuçta
\(L_1\) = \( \begin{matrix} 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ \end{matrix}\)
bulunur. \(L_2\) ise \(a_{ij}^{(2)}=i+2j\) mod\((5) \) ile tanımlı olduğundan
\( a_{11}^{(2)}=1+2·1=3 ; a_{12}^{(2)}=1+2·2=0\)
\( a_{13}^{(2)}=1+2·3=2 ; a_{14}^{(2)}=1+2·4=4\)
\( a_{15}^{(2)}=1+2·5=1 ; a_{21}^{(2)}=2+2·1=4\)
\( · ·\)
\( · ·\)
\( · ·\)
\(L_2\) = \( \begin{matrix} 3 & 0 & 2 & 4 & 1 \\ 4 & 1 & 3 & 0 & 2 \\ 0 & 2 & 4 & 1 & 3 \\ 1 & 3 & 0 & 2 & 4 \\ 2 & 4 & 1 & 3 & 0 \\ \end{matrix} \)
elde edilir. \(L_3\) için \(a_{ij}^{(3)}=i+3j\) mod\((5) \) ve \(L_4\) için de \(a_{ij}^{(4)}=i+4j\) mod\((5) \) \(L_1,L_2,L_3\) ve\(L_4\) dik kareleri aşağıdaki gibi yazılır.
\( \begin{matrix} 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ \end{matrix} \begin{matrix} 3 & 0 & 2 & 4 & 1 \\ 4 & 1 & 3 & 0 & 2 \\ 0 & 2 & 4 & 1 & 3 \\ 1 & 3 & 0 & 2 & 4 \\ 2 & 4 & 1 & 3 & 0 \\ \end{matrix} \)
\( \begin{matrix} 4 & 2 & 0 & 3 & 1 \\ 0 & 3 & 1 & 4 & 2 \\ 1 & 4 & 2 & 0 & 3 \\ 2 & 0 & 3 & 1 & 4 \\ 3 & 1 & 4 & 2 & 0 \\ \end{matrix} \begin{matrix} 0 & 4 & 3 & 2 & 1 \\ 1 & 0 & 4 & 3 & 2 \\ 2 & 1 & 0 & 4 & 3 \\ 3 & 2 & 1 & 0 & 4 \\ 4 & 3 & 2 & 1 & 0 \\ \end{matrix} \)
Not: Bu yazı Matematik Dünyası Dergisi arşivinden siteye eklenmiştir. Yazı ilk olarak derginin 1991 yılı 4. sayısında yer almıştır. Matematik Dünyası arşivi titiz bir çalışma ile çevrim içi platformlarda yeni okuyucularıyla buluşuyor. Bu yazıyı burada okunabilir hale getiren arşiv ekibi üyesi Erkay Aktaş‘a ve tüm gönüllü arşiv ekibimize teşekkür ediyoruz. Yazıyı PDF olarak okumak için PDF arşivine buradan ulaşabilirsiniz.
