ריבוע לטיני

בקומבינטוריקה, ריבוע לטיני הוא ריבוע של n שורות ו-n עמודות, שבכל שורה ובכל עמודה שלו כתובים אותם n סמלים שונים, בלי חזרות.

לדוגמה:

{\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}\quad \quad {\begin{bmatrix}1&3&0&2\\3&2&1&0\\2&0&3&1\\0&1&2&3\end{bmatrix}}

הדוגמה הקלה ביותר היא ריבוע שבשורה ה- i ובעמודה ה-j שלו כתוב i+j-1 או i+j-1-n (בוחרים בכל מקרה את המספר שנמצא בין 1 ל- n). באופן כללי יותר, לוח הכפל של כל חבורה הוא ריבוע לטיני. בסטטיסטיקה ריבועים לטיניים משמשים בתכנון ניסויים של שני משתנים. מקורו של המונח 'ריבוע לטיני' הוא בכך שלאונרד אוילר שחקר אותם השתמש באותיות לטיניות כסמלים.

פעולות על ריבועים לטיניים[עריכת קוד מקור | עריכה]

ריבועים שקולים[עריכת קוד מקור | עריכה]

אם מסדרים מחדש את השורות או את העמודות של ריבוע לטיני, או מחליפים את הסימנים זה בזה, מתקבל ריבוע לטיני חדש. זוהי דוגמה לפעולה של החבורה $\ S_{n}\times S_{n}\times S_{n}$ (כאשר $\ S_{n}$ היא החבורה הסימטרית) על קבוצת הריבועים הלטיניים. לריבועים המתקבלים מריבוע נתון על ידי פעולות אלה קוראים ריבועים שקולים (Isotopic squares). מכיוון שריבועים שקולים שייכים לאותו מסלול תחת הפעולה של $\ S_{n}\times S_{n}\times S_{n}$ , השקילות היא אכן יחס שקילות. כשסופרים ריבועים לטיניים מגודל מסוים, נוח לספור את מחלקות השקילות במקום את הריבועים הבודדים.

ריבועים צמודים[עריכת קוד מקור | עריכה]

נסמן ב- $\ A_{ij}$ את הערך המופיע בשורה ה-i והעמודה ה-j של הריבוע A. את התנאי על הופעת כל ערך פעם אחת בכל שורה ובכל עמודה אפשר לנסח מחדש כך: ב- $\ n^{2}$ השלשות $\ \{(i,j,A_{ij})\}$ , כל שני רכיבים עוברים על כל $\ n^{2}$ האפשרויות. מכאן רואים שהתפקידים של "שורה", "עמודה" ו"ערך" בתיאור של ריבוע לטיני הם סימטריים. אפשר להחליף אותם, ולקבל ריבוע חדש. זוהי למעשה פעולה נוספת, של החבורה $\ S_{3}$ . ששת הריבועים המתקבלים באופן זה מריבוע נתון הם צמודים (conjugate) זה לזה.

ריבועים דומים[עריכת קוד מקור | עריכה]

כשמשלבים את השקילות והצמידות, כלומר את פעולת הערבוב של שורות, עמודות או סמלים עם פעולת ההחלפה בין שורות, עמודות וסמלים, צריך להבחין שהפעולות אינן מתחלפות: החלפת שתי שורות שלאחריה מחליפים בין תפקידי השורות והעמודות אינה זהה להחלפת התפקידים שאחריה מחליפים שתי שורות. במילים אחרות, החבורה של פעולות על ריבועים לטיניים הנוצרת מן הפעולות של $\ S_{n}^{3}$ ושל $\ S_{3}$ שהוזכרו קודם לכן, אינה המכפלה הישרה של שתי החבורות; זוהי דוגמה נאה למכפלת זר (wreath product), שהיא סוג מיוחד של מכפלה ישרה למחצה.

אם אפשר לעבור מריבוע אחד לריבוע אחר על ידי פעולת השקילות ואחריה פעולת הדמיון (או להפך, הסדר אינו חשוב), אז שני הריבועים הם ריבועים דומים. גם יחס זה הוא יחס שקילות, והמחלקות קרויות 'מינים'. כל מין של ריבועים לטיניים כולל לכל היותר שש מחלקות-שקילות.

מספרם של הריבועים הלטיניים[עריכת קוד מקור | עריכה]

לא ידועה נוסחה הקובעת את מספרם של הריבועים הלטיניים בגודל n; גם נוסחאות למספרן של מחלקות השקילות או של המינים, אינן ידועות. להלן מספר הריבועים בגודל n שהם 'ממוינים', כלומר שהשורה הראשונה והעמודה הראשונה ממוינות בסדר עולה (כדי לקבל את מספר הריבועים הלטיניים הכולל, יש להכפיל ב- $\ (n-1)!n!$ ).

**מספר הריבועים הלטיניים בגודל נתון**
n	מספר הריבועים הממוינים
1	1
2	1
3	1
4	4
5	56
6	9408
7	16942080
8	535281401856
9	377597570964258816
10	7580721483160132811489280
11	5363937773277371298119673540771840

להלן מספרן של מחלקות השקילות ושל המינים. מספר הריבועים במחלקת שקילות מחלק את $\ (n!)^{3}$ , ומספר מחלקות השקילות בכל מין מחלק את 6.

**מחלקות שקילות ומינים של ריבועים לטיניים**
n	מינים	מחלקות שקילות
1	1	1
2	1	1
3	1	1
4	2	2
5	2	2
6	12	22
7	147	564
8	283657	1676267
9	19270853541	115618721533
10	34817397894749939	208904371354363006

השלמה לריבוע לטיני[עריכת קוד מקור | עריכה]

אחת הבעיות המעניינות הקשורות לריבועים לטיניים היא זו של השלמת מידע חלקי: נתונים חלק מהערכים בריבוע בגודל n-על-n, ומעוניינים להשלים את כל האחרים כך שיתקבל ריבוע לטיני. הדבר בלתי אפשרי אם הערכים הנתונים כבר כוללים חזרות (בשורות או בעמודות), אך גם אם אין בנתונים חזרות, זה עדיין לא מבטיח שההשלמה אפשרית.

לעומת זאת, אם נתונות רק מספר שורות שלמות (ללא חזרות בשורות או בעמודות), אז תמיד אפשר להשלים אותן לריבוע לטיני - זוהי תוצאה ממשפט החתונה של Hall.

טיפוסים והכללות[עריכת קוד מקור | עריכה]

ריבועים סימטריים[עריכת קוד מקור | עריכה]

יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים סימטריים ( $\ L_{ij}=L_{ji}$ ) שהאלכסון שלהם קבוע, לבין פירוקים של הגרף השלם על n קודקודים ל-איחוד של n-1 התאמות מלאות (פירוק כזה נקרא 1-factorization).

יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים עם סימטריה מלאה (סימטריים כנ"ל, וכן $\ L_{ij}=k$ אם ורק אם $\ L_{ik}=j$ ), שהאלכסון שלהם הוא הזהות ( $\ L_{ii}=i$ ), לבין מערכות שטיינר משולשות.

ריבועים מאונכים[עריכת קוד מקור | עריכה]

שני ריבועים לטיניים A ו- B הם ריבועים מאונכים (או אורתוגונליים) אם כאשר כותבים אותם יחד באותו ריבוע, $\ n^{2}$ הזוגות $\ (A_{ij},B_{ij})$ שונים זה מזה. במילים אחרות, בכל זוג רכיבים ברביעיות $\ \{(i,j,A_{ij},B_{ij})\}$ מופיעות כל $\ n^{2}$ האפשרויות.

בסביבות 1780 מצא לאונרד אוילר דרך לבנות זוגות של ריבועים לטיניים בכל גודל שאינו מהצורה 4m+2. מאחר שאין זוג של ריבועים לטיניים מאונכים בגודל 2, שיער אוילר שלא קיימים ריבועים מאונכים בגדלים 6, 10, 14 וכו'. ההשערה קיבלה חיזוק כאשר ב-1901 הוכיח האיטלקי גסטון טרי (Gaston Tarry) באמצעות כוח גס שלא קיים זוג ריבועים מאונכים בגודל 6. ואולם, בשנת 1959 מצאו פארקר, בוסה ושריקאנדה (E. T. Parker‏, Raj Chandra Bose‏, Sharadchandra Shankar Shrikhande) זוג ריבועים מאונכים בגודל 10, והראו שקיים זוג כזה בכל גודל (פרט ל-2 ול-6).

בעיה שעדיין נותרה פתוחה, היא מציאת המספר המקסימלי של ריבועים לטיניים בגודל n, המאונכים בזוגות. ידוע כי מספר זה לא יכול לעלות על $\ n-1$ , וכי הוא שווה בדיוק למספר זה, כאשר n מספר ראשוני או חזקה של מספר ראשוני. שאלה זו קשורה גם לגאומטריה פרויקטיבית סופית: קיים מישור פרויקטיבי סופי מסדר n, אם ורק אם קיימים $\ n-1$ ריבועים לטיניים בגודל n המאונכים בזוגות.