라틴 방진

3. 성질

주어진 크기의 라틴 방진의 정확한 개수는 알려져 있지 않지만, 상한과 하한은 알려져 있다. 크기가 $n$인 라틴 방진의 수를 $L\_n$이라고 하면, 다음이 성립한다.^[6]

:$\backslash frac\{(n!)^\{2n\}\}\{n^\{n^2\}\}\backslash le\; L\_n\backslash le\; \backslash prod\_\{i=1\}^n(i!)^\{n/i\}\backslash qquad\backslash forall\; n\backslash in\backslash mathbb\; N$

(단, $n=0$일 경우, 좌변에서 $0^0=1$로 놓으며, 우변에서 0개의 항의 곱은 1이다.)

또한, $L\_n$에 대한 공식은 다음과 같다.^[27]

:$L\_n=n!\backslash sum\_\{M\backslash in\backslash operatorname\{Mat\}(n,n;\backslash \{0,1\backslash \})\}(-)^$

\binom{\operatorname{perm}M}n

여기서

• $\backslash operatorname\{Mat\}(n,n;\backslash \{0,1\backslash \})$은 $\backslash \{0,1\backslash \}$ 성분을 갖는, $n\backslash times\; n$ 정사각 행렬들의 집합이다.
• $|\backslash \{(i,j)\backslash in\backslash \{1,2,\backslash dotsc,n\backslash \}^2\backslash colon\; M\_\{ij\}=0\backslash \}|$은 행렬 $M$의 성분 가운데, 값이 0인 것의 수이다.
• $\backslash operatorname\{perm\}M\backslash in\backslash mathbb\; N$은 행렬 $M$의 퍼머넌트이다.
• $\backslash textstyle\backslash binom\{-\}\{-\}$은 이항 계수이다.

크기가 2와 6인 경우를 제외하고, 모든 크기에 대해 서로 직교하는 라틴 방진 쌍이 존재한다.

일반적으로, $n\backslash ge2$일 때, 크기 $n\backslash times\; n$의 상호 직교 라틴 방진(MOLS) 집합의 크기는 항상 $n-1$ 이하이다. 만약 $n$이 소수의 거듭제곱일 때 (즉, 크기 $n$의 유한체가 존재할 때) 이 상계는 최댓값을 갖는다. 구체적으로, 크기 $n-1$의 $n\backslash times\; n$ 상호 직교 라틴 방진 집합은 크기 $n$의 유한 사영 평면의 존재와 동치이다.

3. 1. 동위 라틴 방진

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

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

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

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

3. 2. 켤레 라틴 방진

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

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''개의 셀을 선택하는 것으로, 다음 조건을 만족한다.

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

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

일부 라틴 방진에는 횡단이 없을 수 있다. 예를 들어 ''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'' 라틴 방진에는 횡단이 있다고 추측했다.^[9]
• 1975년 S. K. Stein과 Brualdi는 ''n''이 짝수일 때 모든 ''n''×''n'' 라틴 방진에는 크기가 ''n''−1인 부분 횡단이 있다고 추측했다.^[10]
• Stein은 더 나아가 라틴 방진뿐만 아니라 각 기호가 정확히 ''n''번 나타나는 ''n''×''n'' 배열에도 크기가 ''n''−1인 횡단이 존재한다고 추측했다.^[9]

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

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

4. 연산

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

• 행들의 순열
• 열들의 순열
• 각 성분에 대한 순열

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

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

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

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

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

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

5. 역사

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

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

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

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

6. 응용

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

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

6. 1. 실험 계획

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

6. 2. 오류 정정 부호

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

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

{| class="wikitable"

|-

|

A

B

C

D

|

|

|

|

|

|}

열두 문자의 인코딩은 서로 직교하는 세 개의 라틴 방진으로 구성된다. 이제 전체 전송 중에 채널 1과 2에 잡음이 추가되었다고 상상해 보자. 그러면 문자 A는 다음과 같이 수신될 것이다.

:12 12 123 124

다시 말해, 첫 번째 슬롯에서는 주파수 1과 주파수 2에서 신호를 모두 수신한다. 세 번째 슬롯에는 주파수 1, 2 및 3의 신호가 있다. 잡음 때문에 처음 두 개의 슬롯이 1,1인지, 1,2인지, 2,1인지, 2,2인지 더 이상 알 수 없다. 하지만 1,2의 경우만이 위의 표의 문자, 즉 문자 A와 일치하는 시퀀스를 생성한다.

마찬가지로 세 번째 슬롯의 모든 주파수에 정전기가 발생한다고 상상할 수 있다.

:1 2 1234 4

다시, 인코딩 테이블에서 전송된 문자가 A였음이 추론될 수 있다. 이 코드가 감지할 수 있는 오류 수는 시간 슬롯 수보다 1 적다. 또한 주파수 수가 소수 또는 소수의 거듭제곱인 경우 직교 라틴 방진은 가능한 한 효율적인 오류 감지 코드를 생성한다는 것이 입증되었다.

6. 3. 퍼즐

6. 4. 농업 연구

7. 일반화

• 라틴 사각형은 열과 가능한 값은 ''n''개이지만 행의 수는 ''n''보다 작을 수 있는, 라틴 방진의 일반화된 형태이다. 각 값은 각 행과 열에 최대 한 번 나타난다.
• 그레코-라틴 방진은 두 개의 라틴 방진 쌍으로, 하나를 다른 것 위에 겹쳐 놓았을 때 각 순서쌍의 기호가 정확히 한 번씩 나타난다.
• 라틴 하이퍼큐브는 라틴 방진을 2차원에서 다차원으로 일반화한 것이다.

참조

_[1] 웹사이트 Cambridge college to remove window commemorating eugenicist http://www.theguardi[...] 2020-06-28
_[2] 간행물 Introduction to Combinatorics https://books.google[...] CRC Press
_[3] 서적 Handbook of Combinatorial Designs https://books.google[...] CRC Press 2017-03-28
_[4] harvnb
_[5] harvnb
_[6] harvnb
_[7] 논문 A formula for the number of Latin squares
_[8] arXiv Rainbow matchings and partial transversals of Latin squares
_[9] 논문 On a conjecture of Stein 2017-01-04
_[10] 논문 Transversals of Latin squares and their generalizations 1975-08-01
_[11] 논문 A lower bound for the order of a partial transversal in a latin square 1969-07-01
_[12] 논문 An n × n Latin square has a transversal with at least n−n distinct symbols 1978-03-01
_[13] 논문 A lower bound for the length of a partial transversal in a Latin square 2008-10-01
_[14] 논문 New bounds for Ryser's conjecture and related problems https://www.ams.org/[...] 2022-04-15
_[15] arXiv A proof of the Ryser-Brualdi-Stein conjecture for large even ''n 2023
_[16] 논문 Generating uniformly distributed random latin squares
_[17] 간행물 Design of Comparative Experiments Cambridge University Press
_[18] 간행물 Theory of Optimal Designs Springer-Verlag
_[19] 논문 Permutation arrays for powerline communication
_[20] 뉴스 Euler's revolution New Scientist 2007-03-24
_[21] 논문 Powerline communication and the 36 officers problem
_[22] 논문 The complexity of completing partial latin squares
_[23] 웹사이트 The application of Latin square in agronomic research http://joas.agrif.bg[...]
_[24] 웹사이트 Letters Patent Confering the SSC Arms http://www.ssc.ca/ar[...]
_[25] 웹사이트 The International Biometric Society http://www.tibs.org 2005-05-07
_[26] 서적
_[27] 저널
_[28] 서적
_[29] 저널 http://coding.yonsei[...] 2017-06-08
_[30] 서적
_[31] 서적
_[32] 저널 http://www.biodivers[...] 2017-06-09
_[33] 저널 http://gallica.bnf.f[...]
_[34] 저널
_[35] 저널