A complex Hadamard matrix of order 94

Each language version is independently generated for its own context, not a direct translation.

이 논문은 수학의 한 분야인 '조합론'에서 매우 어려운 퍼즐 하나를 해결한 이야기를 담고 있습니다. 전문 용어인 '복소수 하마르드 행렬 (Complex Hadamard Matrix)'이라는 거대한 건물을 짓기 위해, 연구자가 어떻게 새로운 설계도를 그렸는지 쉽게 설명해 드리겠습니다.

1. 배경: 거대한 퍼즐 조각 찾기

상상해 보세요. 수학자들은 **'하마르드 행렬'**이라는 특별한 정사각형 모양의 퍼즐 조각들을 가지고 있습니다. 이 조각들은 숫자 -1 과 1 로만 이루어져 있고, 서로 다른 줄을 곱하면 0 이 되어야 하는 아주 까다로운 규칙을 따릅니다.

이런 조각들은 통신, 암호, 의료 영상 등 다양한 분야에서 '완벽한 신호'를 만드는 데 쓰입니다. 하지만 문제는 크기입니다.

수학자들은 크기가 94 인 거대한 퍼즐을 만들고 싶어 했습니다.
기존에는 크기가 47 인 작은 조각 4 개를 특별한 방식으로 합쳐서 크기가 94 인 것을 만들 수 있었습니다.
하지만 그 '특수한 방식'을 위해 필요한 47 크기의 조각들 ( Williamson 행렬) 은 실제로 존재하지 않는다는 것이 증명되어 있었습니다. 마치 94 층 건물을 짓기 위해 필요한 47 층짜리 기둥이 세상에 없다는 소리와 같습니다.

2. 해결책: 새로운 설계도 (Theorem 4)

저자 (Ferenc Szöllősi) 는 "기존의 기둥이 없다면, 새로운 설계도를 그려서 다른 재료를 쓰자!"라고 생각했습니다.

기존 방식: 4 개의 대칭적인 기둥을 모두 찾아야 함 (불가능).
새로운 방식: 4 개의 기둥 중 적어도 2 개만 대칭적이면 된다는 새로운 공식을 발견했습니다.
- 마치 건물을 지을 때, 네 기둥이 모두 똑같은 모양일 필요는 없고, 두 개만 대칭이면 나머지 두 개는 조금 다른 모양 (비대칭) 을 가져도 건물이 무너지지 않는다는 것을 증명해낸 것입니다.
- 이 새로운 설계도 (Theorem 4) 를 사용하면, 기존에 없던 47 크기의 조각들을 찾을 수 있는 길이 열렸습니다.

3. 컴퓨터의 도움: 거대한 모래밭에서 바늘 찾기

이제 문제는 "새로운 설계도에 맞는 47 크기의 조각들을 실제로 찾아내는 것"입니다.

가능한 조합의 수는 우주에 있는 별의 수보다 더 많을 정도로 어마어마합니다.
연구자는 컴퓨터를 이용해 이 거대한 모래밭을 샅샅이 뒤졌습니다.
전략:
1. 먼저 규칙을 만족할 가능성이 높은 '후보 조각'들을 선별합니다 (행의 합이 특정 조건을 만족하는지 확인).
2. 컴퓨터가 수백만 번의 시도를 하며, 두 조각을 합쳤을 때 규칙을 만족하는지 빠르게 체크합니다.
3. 마치 **해시 함수 (Hash function)**라는 '지문 인식기'를 만들어, 비슷한 조각들을 같은 폴더에 모아두고, 정반대 성질의 조각을 찾아서 짝을 맞추는 방식을 썼습니다.

4. 결과: 94 층 건물의 완공

약 하루 넘게, 20GB 의 메모리를 사용하며 약 80 억 번의 시도를 한 끝에, 연구자는 마침내 두 가지의 성공적인 조합을 찾아냈습니다 (Example 1 과 Example 2).

이 두 가지 조합을 새로운 설계도 (Theorem 4) 에 대입하자, 드디어 크기가 94 인 복잡한 하마르드 행렬이 완성되었습니다.

이는 수학계에서 오랫동안 풀리지 않던 미해결 문제 중 하나를 해결한 것입니다.
마치 94 층짜리 건물을 짓기 위해 필요한 기둥을 처음-ever 발견한 것과 같습니다.

5. 의미와 미래

이 연구는 단순히 하나의 숫자 (94) 를 해결한 것을 넘어, **"기존의 틀을 깨고 새로운 조합 방식을 찾으면 불가능해 보였던 것도 가능해진다"**는 것을 보여줍니다.

유추: 만약 기존에 47 크기의 기둥을 찾는 것이 '금강석으로 만든 열쇠'를 찾는 것이었다면, 연구자는 '금강석 대신 강철을 쓸 수 있는 새로운 자물쇠'를 발명해낸 셈입니다.
미래: 이 방법을 통해 크기가 118 인 더 큰 행렬 (p=59) 도 언젠가 찾아낼 수 있을 것으로 기대됩니다. 슈퍼컴퓨터와 더 똑똑한 알고리즘을 결합하면, 수학의 미지의 영역을 더 넓혀갈 수 있을 것입니다.

한 줄 요약:

"기존의 방법으로는 불가능하다고 생각했던 94 크기의 수학 퍼즐을, **새로운 설계도 (2 개의 대칭 조각만 필요함)**와 컴퓨터의 끈질긴 탐색을 통해 처음으로 완성해낸 이야기입니다."

Each language version is independently generated for its own context, not a direct translation.

1. 연구 배경 및 문제 정의 (Problem)

해더마드 행렬의 정의: $n$ 차 실수 해더마드 행렬 $H$ 는 원소가 $\{-1, 1\}$ 인 정방행렬이며, $HH^T = nI_n$ 을 만족합니다.
복소수 해더마드 행렬: 원소가 $\{-1, -i, 1, i\}$ 인 행렬로, 행들이 복소수 공간에서 서로 직교합니다.
기존 연구의 한계:
- 윌리엄슨 (Williamson) 의 방법은 4 개의 대칭 순환 (symmetric circulant) $\{-1, 1\}$ -행렬을 사용하여 $4p $차 실수 해더마드 행렬을 구성합니다. 그러나$ p=47$과 같은 특정 차수에서는 이러한 윌리엄슨 행렬이 존재하지 않는 것이 알려져 있습니다.
- 카라가니와 세버리 (Kharaghani and Seberry) 는 윌리엄슨 행렬을 사용하여 $2p $차 복소수 해더마드 행렬을 구성하는 방법을 제시했습니다. 하지만 이 방법 역시$ p=47$의 경우, 필요한 대칭 순환 행렬들이 존재하지 않아 적용할 수 없었습니다.
핵심 문제: $p=47$ (즉, $2p=94$) 인 경우, 윌리엄슨 행렬이 존재하지 않음에도 불구하고 94 차수의 복소수 해더마드 행렬을 구성할 수 있는가?

2. 방법론 (Methodology)

저자는 기존 구성법을 수정하고 컴퓨터 탐색을 결합하여 문제를 해결했습니다.

가. 수학적 구성법의 수정 (Theoretical Modification)

기존 구성 (Theorem 3): 카라가니와 세버리의 방법은 4 개의 행렬이 모두 서로 호환적 (amicable) 이어야 하며, 보통 4 개 모두 대칭이어야 했습니다.
새로운 구성 (Theorem 4): 저자는 Goethels-Seidel 배열의 아이디어를 차용하여 구성법을 수정했습니다.
- 핵심 아이디어: 4 개의 순환 행렬 $A, B, C, D$ 중 **최소 2 개만 대칭 (symmetric)**이면 되며, 나머지 2 개는 대칭이 아니어도 됩니다.
- 구체적 방법: 행렬 $R$ (back-diagonal matrix) 을 도입하여 $C$ 와 $D$ 를 변형 ( $C+DR$ , $C-DR$ 등) 하고, 이를 복소수 행렬 $X, Y$ 로 조합하여 $2p$차 복소수 해더마드 행렬을 생성합니다.
- 조건: $A, B, C, D$ 는 순환 행렬이며, $AAT + BBT + CCT + DDT = 4pI_p$ 를 만족해야 합니다.

나. 컴퓨터 지원 탐색 알고리즘 (Computer-Aided Search)

목표: $p=47$ 인 경우, 위 조건을 만족하면서 **2 개가 대칭인 순환 행렬 (대칭 유형: ssxx)**을 찾습니다.
알고리즘 단계:
1. 행의 합 (Row Sums) 제한: Lemma 4 에 따라 행의 합 $\sigma_A, \sigma_B, \sigma_C, \sigma_D$ 가 $4p$를 만족하도록 제한합니다.
2. 스펙트럼 제한 (Lemma 5): 해더마드 행렬 블록으로서의 고유값 제약을 이용해 후보 행렬을 필터링합니다.
3. 해시 기반 탐색:
  - 대칭 행렬 $A, B$ 의 주기적 자기상관 (autocorrelation) 벡터 $I(a), I(b)$ 를 계산하고 합 $\Sigma = I(a) + I(b)$ 를 구합니다.
  - 이 합을 해시 함수 $h(\Sigma)$ 를 통해 인덱싱하여 저장합니다.
  - 비대칭 행렬 $C, D$ 의 자기상관 벡터 $I(c), I(d)$ 를 무작위로 생성하여 $-\Delta = I(c) + I(d)$ 가 저장된 해시 테이블에 존재하는지 확인합니다.
4. 자원: 약 80 억 번 ($8 \cdot 10^9$) 의 시도를 수행하며, 약 20GB 메모리와 1 일 이상 소요되었습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

가. 94 차수 복소수 해더마드 행렬의 존재 증명 (Theorem 1)

주요 결과: $p=47$ 인 경우, 2 개가 대칭이고 2 개가 비대칭인 순환 행렬들을 성공적으로 발견했습니다.
구체적 예시:
- Example 1: 행의 합이 $\sigma_A=3, \sigma_B=7, \sigma_C=7, \sigma_D=9$ 인 경우.
- Example 2: 행의 합이 $\sigma_A=-1, \sigma_B=-5, \sigma_C=9, \sigma_D=9$ 인 경우.
- 이 두 예시 중 하나를 수정된 구성법 (Theorem 4) 에 적용하여 94 차수 복소수 해더마드 행렬을 최초로 구성했습니다.

나. 새로운 구성법 제시 (Theorem 4)

기존에는 4 개의 행렬이 모두 대칭이어야만 복소수 해더마드 행렬을 구성할 수 있다는 인식이 있었으나, 저자는 2 개의 대칭 행렬만으로도 충분함을 보였습니다. 이는 Williamson-type 행렬이 존재하지 않는 경우에도 복소수 해더마드 행렬을 찾을 수 있는 새로운 경로를 열었습니다.

4. 의의 및 향후 전망 (Significance & Future Work)

수학적 의의:
- $p=47$ 은 Williamson 행렬이 존재하지 않는 대표적인 사례였으며, 이로 인해 $2p=94$차 복소수 해더마드 행렬의 존재가 오랫동안 미해결 문제로 남아있었습니다. 이 논문은 이를 해결함으로써 해더마드 행렬 이론의 중요한 공백을 메웠습니다.
- $p=35$ (70 차) 이후의 다음 주요 미해결 차수인 $p=59$ (118 차) 로의 확장을 위한 기초를 마련했습니다.
방법론적 의의:
- 대칭성 요구 사항을 완화하고 컴퓨터 탐색을 결합한 하이브리드 접근법의 유효성을 입증했습니다.
- 향후 슈퍼컴퓨팅 자원과 더 정교한 탐색 알고리즘을 통해 $p=47$ 보다 큰 차수 (예: $p=59$ ) 로의 확장이 가능할 것으로 기대됩니다.

요약

이 논문은 **수학적 구성법의 개선 (2 개의 대칭 행렬만 요구)**과 대규모 컴퓨터 탐색을 결합하여, 기존에 구성 불가능하다고 여겨졌던 94 차수 복소수 해더마드 행렬을 최초로 발견하고 구성했습니다. 이는 조합론 및 행렬 이론 분야에서 중요한 이정표가 되는 연구입니다.