라틴 방진

3.1. 동위 라틴 방진

임의의 라틴 방진이 주어졌을 때, 다음 연산을 가하여도 여전히 라틴 방진을 얻을 수 있다.

* 행들의 순열
* 열들의 순열
* 각 원소에 대한 순열

만약 같은 알파벳 위의 두 라틴 방진에 위 연산들을 적용하여 서로 같게 만들 수 있다면, 이 두 라틴 방진은 서로 동위(同位, isotopic^영어) 관계라고 한다.

예를 들어, 라틴 방진의 행을 순열하거나, 열을 순열하거나, 기호의 이름을 순열하면, 원래 라틴 방진과 동위 관계에 있는 새로운 라틴 방진을 얻는다. 동위는 동치 관계이므로, 모든 라틴 방진의 집합은 동위류(isotopy classes)로 나눌 수 있다. 같은 동위류에 속하는 두 방진은 동위 관계이며, 다른 동위류에 속하는 방진은 동위 관계가 아니다.

3.2. 켤레 라틴 방진

라틴 방진은 순서쌍 (행, 열, 값)으로 표현할 수 있다. 이때 순서쌍의 세 성분을 치환하여 얻을 수 있는 라틴 방진을 켤레 라틴 방진이라고 한다. 예를 들어 각 순서쌍 (r,c,s)을 (c,r,s)로 바꾸면 원래 방진을 전치하는 것과 같다. 여기서 r, c, s는 각각 행, 열, 심볼을 의미한다. (r,c,s)를 (c,s,r)로 바꾸는 것과 같이 더 복잡한 연산도 가능하다. 이러한 치환은 "아무것도 하지 않음"을 포함하여 총 6가지 경우가 있으며, 이들을 원래 방진의 켤레(conjugate)라고 부른다.

3.3. 직교성

같은 크기의 두 라틴 방진 $M$, $N$이 주어졌을 때, 각 칸에서 두 라틴 방진의 성분이 각각 다른 순서쌍을 이룬다면, 즉 다음 조건을 만족하면,
:$\backslash forall\; i,j,i\text{'},j\text{'}\backslash in\backslash \{1,2,\backslash dotsc,\backslash \}\backslash colon\; (M\_\{ij\},N\_\{ij\})\backslash ne(M\_\{i\text{'}j\text{'}\},N\_\{i\text{'}j\text{'}\})$
$M$과 $N$은 서로 직교(直交, orthogonal^영어)한다고 하며, $M\backslash perp\; N$으로 표기한다.

같은 크기의 라틴 방진 집합 $\backslash mathcal\; M$에 대하여, 임의의 서로 다른 두 라틴 방진 $M,N\backslash in\backslash mathcal\; M$이 항상 $M\backslash perp\; N$를 만족하면, $\backslash mathcal\; M$을 상호 직교 라틴 방진 집합(set of mutually orthogonal Latin squares^영어, 약자 MOLS)이라고 한다. 특히, 크기가 2인 상호 직교 라틴 방진 집합, 즉 직교하는 두 라틴 방진의 순서쌍 $(M,N)$은 직교 라틴 방진 (쌍)(直交Latin方陣順序雙, (pair of) orthogonal Latin square(s)^영어) 또는 그레코라틴 방진(Greco–Latin square^영어)이라고 한다.

3.4. 횡단 (Transversal)

라틴 방진에서 횡단은 n개의 셀을 선택하는 것으로, 다음 조건을 만족한다.

* 각 행에서 하나의 셀을 포함한다.
* 각 열에서 하나의 셀을 포함한다.
* 각 기호를 포함하는 셀이 하나씩 있다.

라틴 방진을 이분 그래프로 표현했을 때, 횡단은 각 모서리가 다른 색상을 갖는 무지개 매칭에 해당한다.

일부 라틴 방진에는 횡단이 없을 수 있다. 예를 들어 n이 짝수일 때, 셀 (i,j)의 값이 (i+j) mod n인 n×n 라틴 방진은 횡단을 갖지 않는다. 다음은 그 예시이다.

:$$$$
\begin{bmatrix}
1 & 2 \\
2 & 1
\end{bmatrix}
\quad
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 3 & 4 & 1 \\
3 & 4 & 1 & 2 \\
4 & 1 & 2 & 3
\end{bmatrix}


다음은 횡단과 관련된 추측들이다.

* 1967년 H. J. Ryser는 n이 홀수일 때 모든 n×n 라틴 방진에는 횡단이 있다고 추측했다.
* 1975년 S. K. Stein과 Brualdi는 n이 짝수일 때 모든 n×n 라틴 방진에는 크기가 n−1인 부분 횡단이 있다고 추측했다.
* Stein은 더 나아가 라틴 방진뿐만 아니라 각 기호가 정확히 n번 나타나는 n×n 배열에도 크기가 n−1인 횡단이 존재한다고 추측했다.

이러한 추측들의 일부 약한 버전은 증명되었다.

* 모든 n×n 라틴 방진에는 크기가 2n/3인 부분 횡단이 있다.
* 모든 n×n 라틴 방진에는 크기가 n − sqrt(n)인 부분 횡단이 있다.
* 모든 n×n 라틴 방진에는 크기가 n − 11 log(n)인 부분 횡단이 있다.
* 모든 n×n 라틴 방진에는 크기가 n − O(log n/loglog n)인 부분 횡단이 있다.
* 모든 충분히 큰 n×n 라틴 방진에는 크기가 n −1인 부분 횡단이 있다. (사전 출판)

4. 연산

임의의 라틴 방진이 주어졌을 때, 다음 연산을 가하여도 여전히 라틴 방진을 이룬다.
* 행들의 순열
* 열들의 순열
* 각 성분에 대한 순열

같은 알파벳 위의 두 라틴 방진에 위와 같은 연산들을 가하여 같게 만들 수 있다면, 이 두 라틴 방진은 서로 동위(同位, isotopic^영어)라고 한다.

알파벳이 전순서 집합일 때, 임의의 라틴 방진에 순열을 가해 첫 행과 첫 열이 둘 다 순서대로 배열되게 놓을 수 있다. 이를 표준형 라틴 방진(標準型Latin方陣, normal-form/standard-form/reduced Latin square^영어)이라고 한다.

라틴 방진의 순서쌍 표현에서, 크기 3의 집합 위의 순열을 취하여도 역시 라틴 방진을 이룬다. 이 경우 원래 라틴 방진과 순열을 취한 라틴 방진은 서로 켤레(conjugate^영어)라고 한다. 예를 들어 행렬 표현에서 정사각 행렬의 전치 행렬을 취하는 것은 켤레를 취하는 연산에 해당한다.

라틴 방진은 행, 열, 기호를 교환하여 동치인 다른 라틴 방진을 생성할 수 있으며, 이러한 동치 관계를 이소토피(isotopy)라고 한다. 모든 라틴 방진은 이소토피를 통해 동치류(이소토피류, isotopy classes)로 나눌 수 있다.

또한, 직교 배열 표현을 사용하여 각 3-튜플의 문자 순서를 체계적으로 바꾸는 연산을 통해 새로운 라틴 방진을 만들 수 있다. 이러한 연산으로 얻을 수 있는 라틴 방진을 원래 방진에 대해 공액(conjugate 또는 parastrophe)이라고 한다.

두 라틴 방진 중 하나가 다른 하나의 공액에 대해 이소토픽일 때, 이들을 파라토픽(paratopic 또는 main class isotopic)이라고 한다. 이것 역시 동치 관계이며, 이 동치류는 main classes, species, paratopy classes 등으로 부른다. 각 main class는 최대 6개의 이소토피류를 포함한다.

5. 역사

최석정(1646~1715)은 1710년~1715년 경 출판된 것으로 여겨지는 수학서 《구수략》에서 세계 최초로 9×9 직교 라틴 방진 쌍을 제시하였다. 최석정은 이 9×9 직교 라틴 방진을 구구모수변궁양도(九九母數變宮陽圖)라고 명명하였다.

프랑스의 수학자 자크 오자낭(Jacques Ozanam^프랑스어, 1640~1718)은 1694년에 각종 수학 퍼즐이 수록된 책을 출판하였다. 이후 오자낭 사후 1778년에 장에티엔 몽튀클라(Jean-Étienne Montucla^프랑스어, 1725~1799)가 이를 편집하고 새 퍼즐들을 추가하여 재출판하였으며, 이 개정판에는 4×4 직교 라틴 방진에 해당하는 퍼즐이 수록되어 있다. 이 퍼즐은 플레잉카드의 4개의 슈트(◆, ♥, ♠, ♣)에 속하는 킹(K), 퀸(Q), 잭(J), 에이스(A) 카드를 사용하여 직교 라틴 방진을 구성하는 것이었다.

레온하르트 오일러는 1779년에 집필되고 1782년에 출판된 논문에서 라틴 방진과 그레코라틴 방진을 연구하였다. 오일러는 이 논문에서 "라틴 방진"이라는 용어를 처음 사용하였는데, 이는 조합론적 구조를 다룰 때 그리스 문자 대신 라틴 문자를 사용한 것에서 유래하였다. 마찬가지로, "그레코라틴 방진"이라는 용어는 두 라틴 방진의 원소를 각각 라틴 문자와 그리스 문자로 표기한 것에서 유래하였다. 오일러는 이 논문에서 36인의 장교 문제를 언급하며, 6개의 서로 다른 계급과 6개의 서로 다른 연대에 속하는 장교들을 정사각형 모양으로 배열할 때, 각 행과 열에 서로 다른 계급과 연대에 속하는 장교들이 오도록 배열하는 문제의 불가능성을 언급하였다. 오일러는 $n\backslash not\backslash equiv\; 2\backslash pmod4$일 경우 서로 직교하는 $n\backslash times\; n$ 라틴 방진 쌍이 존재함을 증명하고, 이것이 직교 라틴 방진 쌍이 존재하기 위한 필요충분조건일 것이라고 추측하였다.

1901년에 프랑스의 수학자 가스통 타리(Gaston Tarry^프랑스어, 1843~1913)는 서로 직교하는 두 6×6 라틴 방진이 존재할 수 없음을 증명하여 오일러의 추측 중 일부를 확인하였다. 그러나 1959년에 라지 찬드라 보스와 샤라드찬드라 샨카르 슈리칸데(शरदचंद्र शंकर श्रीखंडे^힌디어, Sharadchandra Shankar Shrikhande^영어)는 서로 직교하는 22×22 라틴 방진을 증명하였다. 곧 보스와 슈리칸데와 어니스트 틸던 파커(Ernest Tilden Parker^영어, 1926~1991)는 1960년에 10 이상의 모든 수에 대하여 오일러의 추측이 거짓임을 증명하였다. 즉, 크기가 2와 6인 경우를 제외한 모든 경우에 직교 라틴 방진 쌍이 존재한다.

6. 응용

라틴 방진은 실험 계획, 오류 정정 부호, 암호학, 조합론 등 다양한 분야에 응용된다.

* 실험 계획: 통계학에서 라틴 방진은 실험 설계에 사용되며, 특히 농업 연구에서 실험 오차를 최소화하는 데 활용된다. 두 개의 블로킹 요인에 대한 '행-열 설계'의 특수한 경우이다.
* 오류 정정 부호: 서로 직교하는 라틴 방진 집합은 오류 정정 부호로 응용된다. 전력선을 통해 광대역 인터넷을 전송하는 경우처럼, 단순한 백색 잡음보다 복잡한 잡음 환경에서 통신 품질을 향상시키는 데 사용된다.
* 퍼즐: 스도쿠는 라틴 방진의 특수한 경우이며, 켄켄, 스트림코 퍼즐도 라틴 방진을 활용한다. 또한, 라틴 방진은 카미사도와 같은 추상 전략 보드 게임의 기반이 되기도 한다.

6.1. 실험 계획

통계학에서, 라틴 방진은 실험 설계에 사용된다. 실험 설계에서 라틴 방진은 두 개의 블로킹 요인에 대한 '행-열 설계'의 특수한 경우이다.

6.2. 오류 정정 부호

서로 직교하는 라틴 방진 집합은 오류 정정 부호로 응용되어, 단순한 백색 잡음보다 더 많은 유형의 잡음에 의해 통신이 방해받는 상황, 예를 들어 전력선을 통해 광대역 인터넷을 전송하려는 시도에 사용된다.

우선, 메시지는 여러 주파수 또는 채널을 사용하여 전송된다. 이는 특정 주파수에서 발생하는 잡음에 신호가 덜 취약하도록 하는 일반적인 방법이다. 전송할 메시지의 문자는 서로 다른 주파수에서 연속적인 시간 간격으로 일련의 신호를 전송하여 인코딩된다. 아래 예에서 A부터 L까지의 문자는 네 개의 서로 다른 주파수에서 신호를 전송하고 네 개의 시간 슬롯으로 인코딩된다. 예를 들어 문자 C는 먼저 주파수 3, 다음 4, 1 및 2로 전송하여 인코딩된다.