Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

하다마드 행렬에 대해서 (part 1)

2003.10.06 09:07

송홍엽 조회 수:10488 추천:190

혹시 하다마드 행렬에 대해서 공부해본 적이 있나요?
놀랍게도 내 전공분야중 중요한 한 분야가 바로 하다마드 행렬에 관한 것이랍니다.
하다마드 행렬이 우선 무엇인지를 먼저 말하고 왜 이것을 전공하게 되었는지 설명하겠습니다.

정의1: Hadamard matrix of order n은 오직 +1과 -1로 구성된 크기가 n x n 인 정방행렬로서, 어떤 서로다른 두 행벡터의 내적값도 0이다.

여기서 두 행벡터의 내적이라 함은 component-wise 곱셈의 결과를 모두 더한 값입니다. 서로 직교한다는 뜻입니다.
이러한 성질을 가지기 때문에 디지털 통신시스템에서 signaling에 무척이나 중요하게 사용됩니다. 문제는 이러한 하다마드 행렬을 찾는 일이고 쉽게 만들어내는 것입니다. 우선 있어야 만들어낼수있지요.

예를 우습게 든다면, 무언가를 만들고자할때 다이아몬드보다 2배정도 강한 재료가 필요하다고 합시다. 그 순간 우리는 그 물건을 만들수없을을 깨닫게 됩니다. 그런 강도를 가진 재료는 없기때문입니다. (요즘엔 혹시 있을지도....^^) 마찬가지로, 어떤 통신시스템을 구성하고자할때, 주어진 길이를 가지며 서로직교하는 n개의 벡터가 필요하다고 합시다. 만일, 그러한 조건을 만족하는 집합이 존재하지 않는다는것을 알면 그 순간 그러한 시스템을 구성할수없다고 결론내리고 이를 우회할 방법을 찾아야겠지요...

길이가 n이고 서로직교하는 n개의 벡터가 존재한다면 하다마드 행렬을 구성할수있습니다. 반대로, 하다마드 행렬을 찾으면, 그러한 조건을 만족하는 벡터의 집합을 구성할수있지요... 이 집합이 바로 디지털 통신시스템의 signaling방식에 사용되는 것입니다.

자, 혹시 3차 하다마드 행렬을 본적 있나요 ? 8차는요? 12차는요?
혹시, 2차, 4차, 8차, 16차, 32차, 64차로 증가하는 하다마드 행렬을 본적 있나요?

일반적으로 홀수차 하다마드 행렬을 존재하지 않습니다. 이를 증명해봅시다.

정리1. 1차를 제외한 홀수차 하다마드 행렬은 존재하지 않는다.
증명:
n차의 임의의 하다마드 행렬M이 주어졌다고 합시다. 우리는 바로 이 크기 n이 짝수임을 결론내리고자 합니다.
이를 위해서 다음을 생각합시다. 이 행렬의 맨 위의 행을 쳐다봅시다. 이 행에는 +1도 있고 -1도 있을수있습니다.
혹시 -1이 있다면, 그 자리를 포함하는 열벡터의 모든 원소에 -1을 곱합시다.

그 결과는 다음의 이유때문에 역시
n차 하다마드 행열입니다. -1을 모두 곱하기 전을 M이라 하고 곱하고 난 후를 N이라 한다면, 동일한 위치의 서로다른
두개의 행벡터를 생각합시다. M에서 만일 그 자리가 +1,+1이거나 -1,-1이면 N에서는 그 반대로 -1,-1이거나 +1,+1이되어
그 두행의 내적을 계산할때 그 자리의 component-wise곱셈의 결과는 +1로 변함이 없습니다.
만일 M에서 그 자리가 +1,-1이거나 -1,+1이면, N에서는 반대로 -1,+1이거나 +1,-1이되어 역시
그 두행의 내적을 계산할때 그 자리의 component-wise곱셈의 결과는 -1로 변함이 없습니다.

이렇게 M의 맨 위의 행을 쳐다보고 혹시 -1이 있다면 그자리를 포함하는 열벡터의 모든 원소에 -1을 곱합니다.
이를 필요한 만큼 반복하여 첫행을 모두 +1로 바꿉시다. 그래도 역시 결과는 n차 하다마드행렬입니다.
이제 그 결과를 N이라 합시다. 행렬N에서
임의의 서로다른 두 행벡터의 내적은 0이어야하므로, 첫행과 나머지 어떤 행과의 내적도 0입니다.
그런데 첫행이 모두 +1 이므로, 나머ㄷ지 어떤 행에도 +1 숫자만큼 -1의 숫자가 정확히 같은 수만큼 있어야 합니다.
이는 결국 행의 길이가 짝수임을 뜻합니다. (증명끝)

좀더 정확히는 다음과 같은 사실을 증명할수있습니다.

정리2: 1차와 2차를 제외하면 n차 하다마드 행렬이 존재하는 필요조건은 n이 4의 배수입니다.
즉, n차 하다마드 행렬이 존재한다면, n은 반드시 1, 2, 또는 4의 배수입니다.

(증명: 추후에....)

정리 2가 사실이라면 3차 하다마드 행렬은 존재하지 않습니다. 마찬가지로 9차나 10차 하다마드 행렬도 없고요...

정리2의 역은 사실일까요 ? 즉, 모든 4의 배수 n에 대하여 n차 하다마드 행렬이 존재할까요?
놀랍게도 이는 아직 open problem입니다.

Conjecture 1: 모든 4의 배수 n에 대하여 n차 하다마드 행렬이 존재한다.

위의 가설은 아직 완전히 증명되지 못하였습니다. 그렇다고 반례가 찾아진것도 아닙니다.
하다마드 행렬에 대한 수학적 연구가 100여년이 되었지만, 인간의 무지는 하염없기만 합니다.
예를 들어 428차가 그렇습니다. 428차 하다마드 행렬을 찾아낸 사람이 이세상에 아직까지 없었습니다.
그렇다고, 428차 하다마드 행렬이 존해할수없다는 증명을 완성한 사람도 이세상에 아직까지 없었습니다.
무엇이 사실일까요? 존재할까요 아니면 존재하지 않을까요?

존재한다고 믿는 사람들은 그 예를 하나 찾으려고 무단히 애를 씁니다.
하나의 예를 찾으면 그만이니까요.
존재하지 않는다고 믿는 사람들은 428차 하다마드 행렬의 존재를 가정한 후에
이로부터 유추할수있는 우스꽝스런 결론을 찾으려고 무단히 애를 씁니다.
만일 이러한 작업이 성공한다면 흔히 "proof by contradiction" 이라는 기법으로
존재하지 않음을 증명하는 셈이 됩니다... 그 어느편도 성공한적이 아직은 없었습니다.
혹시 여러분중에 도전하고픈 생각 없나요 ? 그 어느편으로 결론이 내려진다해도 이는 놀라운 결론이며
바로 세계적으로 유명해질수있는 기회가 됩니다...
여러분중에 이를 해결한다면 내가 석사학위를 예약해두겠습니다....-- 장난이 아닙니다..........

더 많은 이야기를 추후 시간내서 올리도록 하겠습니다....오늘은 여기까지만요..









165.132.59.119 송홍엽: 놀랍게도 428차 이전까지의 작은 4의 배수인 차수에 대해서는 모두다 하다마드행렬이 찾아졌습니다. 428부터는 무한히 많은 4의 배수의 차수에 대해서 알려져있지만 동시에 무한히 많은 4의 배수의 차수에 대해 open입니다... -[10/06-00:13]-

165.132.59.119 송홍엽: 놀랍게도 428차 이전까지의 작은 4의 배수인 차수에 대해서는 모두다 하다마드행렬이 찾아졌습니다. 428부터는 무한히 많은 4의 배수의 차수에 대해서 알려져있지만 동시에 무한히 많은 4의 배수의 차수에 대해 open입니다... -[10/06-00:13]-

165.132.59.119 송홍엽: 이 내용을 아무래도 수업시간에 다루어야할 판입니다.... -[10/12-20:36]-

61.98.8.61 진석용: 428차 하다마드 행렬이 2004년에 발견되었지요... -[11/24-02:25]-