Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

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

2003.10.06 09:07

송홍엽 조회 수:10698 추천: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]-
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 9404
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6367
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8420
89 [퍼온글] 우리전공의 학부생이 공부하면 좋을 수학과목 ?? 송홍엽 2003.03.23 6510
88 지금 내 전공분야는 공부한던 시절엔 나에게 가장 힘든 분야였답니다... 송홍엽 2003.06.03 5026
87 벡터공간이란 무엇일까.. 송홍엽 2003.10.06 14169
86 유클리디안 n차원 벡터공간 (and Online-HW1) 송홍엽 2003.10.06 7634
85 basis란.. (and Online-HW2) 송홍엽 2003.10.06 82575
84 디지털 이야기... 송홍엽 2003.10.06 3404
» 하다마드 행렬에 대해서 (part 1) [1] 송홍엽 2003.10.06 10698
82 [일반인을 위한 교양강좌] CDMA 통신기술 (2001.7) 송홍엽 2003.10.13 3649
81 채널코딩에 관한 첫번째 이야기 송홍엽 2003.10.13 4910
80 쉬었다가는 페이지 file 송홍엽 2003.10.20 3815
79 채널코딩 둘째이야기... 송홍엽 2003.11.12 18141
78 채널코딩 세째 이야기 송홍엽 2003.11.13 5118
77 Dr. Shannon 송홍엽 2003.12.07 26753
76 [공지] 게시판을 열면서 송홍엽 2004.03.30 3894
75 funny story 송홍엽 2004.04.01 14060
74 [퍼온글] 달력의 유래 송홍엽 2004.04.01 5313
73 유명한 퍼즐1 송홍엽 2004.04.01 3572
72 Golomb-Puzzle 2003.12 file 송홍엽 2004.04.02 3712
71 DMS와 정보량 송홍엽 2004.04.04 3569
70 수집합이란... 송홍엽 2004.04.13 3729