Latinska kvadrater och ändliga geometrier

En latinsk kvadrat är en kvadratisk matris där varje symbol förekommer en gång per rad och kolumn, och ändliga geometrier är högstrukturerade incidenssystem på ändligt många punkter och linjer.

Definition

En latinsk kvadrat av ordning n är en n-gånger-n-matris fylld med n symboler så att varje symbol förekommer exakt en gång i varje rad och varje kolumn; ett ändligt projektivt plan är en incidensstruktur av punkter och linjer där varje par av punkter ligger på en unik linje och varje par av linjer möts i en unik punkt.

Scope

Detta ämne behandlar latinska kvadrater och parvis ortogonala latinska kvadrater, deras ekvivalens med nät och transversala designer, samt ändliga projektiva och affina plan konstruerade från ändliga kroppar. Det inkluderar Eulers klassiska förmodan om ortogonala kvadrater och det djupa sambandet mellan parvis ortogonala latinska kvadrater och ändliga projektiva plan.

Core questions

• Hur många parvis ortogonala latinska kvadrater av en given ordning kan existera?
• För vilka ordningar existerar kompletta uppsättningar av ortogonala kvadrater, och därmed projektiva plan?
• Hur konstruerar ändliga kroppar plan och ortogonala kvadrater?
• Vilka incidensaxiom definierar affina och projektiva geometrier över ändliga mängder?

Key concepts

• Latinsk kvadrat
• Parvis ortogonala latinska kvadrater
• Transversala designer och nät
• Ändligt projektivt plan
• Affint plan
• Galois (ändliga) kroppar

Key theories

MOLS och projektiva plan

En komplett uppsättning av n-1 parvis ortogonala latinska kvadrater (MOLS) av ordning n existerar om och endast om ett ändligt projektivt plan av ordning n existerar, vilket kopplar latinsk-kvadrat-kombinatorik till ändlig geometri.

Vederläggning av Eulers förmodan

Euler förmodade att inga par av ortogonala latinska kvadrater existerar för ordningar kongruenta med 2 modulo 4; Bose, Shrikhande och Parker motbevisade detta 1960 för alla sådana ordningar utom 2 och 6.

Clinical relevance

Latinska kvadrater tillhandahåller rad-kolumn-experimentdesigner som kontrollerar två källor till variation samtidigt, ortogonala matriser stöder faktorielle experiment och mjukvarutestning, och ändliga geometrier genererar koder och designer.

History

Euler studerade ortogonala latinska kvadrater 1782 genom sitt problem med trettiosex officerare; hans förmodan stod sig fram till motbevisningen 1960 av Bose, Shrikhande och Parker, de så kallade Euler-förstörarna.

Key figures

• Leonhard Euler
• R. C. Bose
• E. T. Parker

Seminal works

• colbourn2007

Frequently asked questions

Vad innebär det att två latinska kvadrater är ortogonala?

När de två kvadraterna läggs över varandra förekommer varje ordnat par av symboler exakt en gång, så kvadraterna särskiljer gemensamt varje cell i rutnätet.

Är ett Sudoku-rutnät en latinsk kvadrat?

Ett färdigt Sudoku är en latinsk kvadrat av ordning nio med det extra villkoret att varje tre-gånger-tre-ruta också innehåller varje symbol en gång.