아다마르 행렬 문서 원본 보기

{{위키데이터 속성 추적}}
[[선형대수학]]에서 '''아다마르 행렬'''(또는 하다마드 행렬, Hadamard行列, {{llang|en|Hadamard matrix}})은 모든 성분이 ±1이며, 행벡터들과 열벡터들이 각각 서로 [[직교]]하는 [[정사각 행렬]]이다.<ref>{{저널 인용|제목=Hadamard matrices and their applications|이름=A.|성=Hedayat|이름2=W. D.|성2=Wallis|url=https://projecteuclid.org/euclid.aos/1176344370|jstor=2958712|저널=The Annals of Statistics|권=6|호=6|날짜=1978-11|쪽=1184–1238|issn=0090-5364|언어=en}}</ref><ref>{{서적 인용|제목=Hadamard matrices and their applications|이름=S. S.|성=Agaian|날짜=1985|doi=10.1007/BFb0101073|총서=Lecture Notes in Mathematics|권=1168|issn=0075-8434|isbn=978-3-540-16056-4|출판사=Springer-Verlag|언어=en}}</ref><ref>{{서적 인용|장url=http://mathscinet.ru/files/YamadaSeberry1992.pdf|장=Hadamard matrices, sequences, and block designs|이름=Jennifer|성=Seberry|이름2=Mieko|성2=Yamada|쪽=431–560|제목=Contemporary design theory: a collection of surveys|출판사=Wiley|날짜=1992-06|isbn=978-0-471-53141-8|url=http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471531413.html|editor1-first=Jeffrey H.|editor1-last=Dinitz |editor2-first=Douglas R. |editor2-last=Stinson |총서=Wiley-Interscience Series in Discrete Mathematics and Optimization |언어=en}}</ref>

== 정의 ==
실수 성분 <math>n\times n</math> [[정사각 행렬]] <math>M\in\operatorname{Mat}(n,n;\mathbb R)</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이를 만족시키는 <math>M</math>을 '''아다마르 행렬'''이라고 한다.
* 모든 성분이 <math>\pm1</math>이며, <math>M/\sqrt n</math>은 [[직교 행렬]]이다.
* 모든 성분이 <math>\pm1</math>이며, 모든 행벡터가 서로 직교한다. 즉, 임의의 <math>i,i'\in\{1,\dotsc,n\}</math>에 대하여 <math>\textstyle\sum_{j=1}^nM_{ij}M_{i'j}=n\delta_{ij}</math>이다. 즉, <math>MM^\top=n1_{n\times n}</math>이다.
* 모든 성분이 <math>\pm1</math>이며, 모든 열벡터가 서로 직교한다. 즉, 임의의 <math>j,j'\in\{1,\dotsc,n\}</math>에 대하여 <math>\textstyle\sum_{i=1}^nM_{ij}M_{ij'}=n\delta_{jj'}</math>이다. 즉, <math>M^\top M=n1_{n\times n}</math>이다.
* 모든 성분이 절댓값 1 이하의 [[실수]]이며, <math>\det M=\pm n^{n/2}</math>이다.
여기서 <math>\delta</math>는 [[크로네커 델타]]이다.

=== 아다마르 설계 ===
첫째 행과 첫째 열이 모두 +1만으로 구성된 아다마르 행렬을 '''표준형 아다마르 행렬'''(標準型Hadamard行列, {{llang|en|standard Hadamard matrix}})이라고 한다. 모든 아다마르 행렬은 행 및 열의 [[순열]] 및 &minus;1을 곱하는 것을 통해 표준형으로 만들 수 있다.

<math>n\times n</math> 표준형 아다마르 행렬 <math>M_{n\times n}</math>이 주어졌을 때,
# 첫째 행과 첫째 열을 제거하고,
# 성분을 <math>(+1,-1)\mapsto (+1,0)</math>으로 치환하자.
그렇다면, 성분이 0 또는 1인 <math>(n-1)\times(n-1)</math> [[정사각 행렬]]을 얻는다.

만약 <math>n</math>이 4의 배수일 경우, 이 <math>(n-1)\times(n-1)</math> 행렬은 <math>(t=2,n/2-1,n-1)</math>-[[블록 설계]]의 결합 행렬을 이루며,
:<math>\lambda_0=n-1</math>
:<math>\lambda_1=n/2-1</math>
:<math>\lambda_2=n/4-1</math>
이다. 즉,
* <math>n-1</math>개의 블록이 있으며,
* 모든 점은 <math>n/2-1</math>개의 블록에 속하며,
* 서로 다른 임의의 두 점은 <math>n/4-1</math>개의 블록에 공통적으로 속한다.
이를 '''아다마르 설계'''(Hadamard設計, {{llang|en|Hadamard design}})라고 한다.

반대로, <math>\lambda_0=n-1</math>인 <math>(2,n/2,n-1)</math>-[[블록 설계]]가 주어졌을 때, 위와 같이 표준형 아다마르 행렬을 재구성할 수 있다.

== 성질 ==
=== 존재 ===
임의의 자연수 <math>n\in\mathbb N</math>에 대하여, <math>n\times n</math> 아다마르 행렬이 존재할 [[필요 조건]]은 다음과 같다.
:<math>n\in\{1,2\}</math>이거나, 또는 <math>n</math>은 4의 배수이다.
이 조건이 [[필요 충분 조건]]이라는 추측은 '''아다마르 추측'''(Hadamard推測, {{llang|en|Hadamard conjecture}})이라고 하며, 아직 증명되거나 반증되지 못했다. 다만, 적어도 <math>n<668</math>에 대해서는 위 조건이 [[필요 충분 조건]]이다.

<math>n\times n</math> 아다마르 행렬이 존재하기 위한 알려진 [[충분 조건]]은 다음이 있다.
* <math>n</math>은 다음과 같은 꼴의 양의 정수들의 곱이다.
** 2
** <math>q+1</math>, <math>q\equiv 3\pmod 4</math>, <math>q</math>는 [[소수 (수론)|소수]]의 거듭제곱
** <math>2(q+1)</math>, <math>q\equiv 1\pmod 4</math>, <math>q</math>는 [[소수 (수론)|소수]]의 거듭제곱

=== 행렬식 ===
행렬 공간 <math>\mathcal X_n=\{M\in\operatorname{Mat}(n,n;\mathbb R)\colon |M_{ij}|\le1\;\forall i,j\}</math>을 정의하자. 그렇다면, '''아다마르 부등식'''({{llang|en|Hadamard inequality}})에 따르면,
:<math>\forall M\in\mathcal X_n\colon |\det M|\le n^{n/2}</math>
이다.

<math>n\times n</math> 아다마르 행렬의 [[행렬식]]은 <Math>\pm n^{n/2}</math>이다. 즉, 만약 <math>n\times n</math> 아다마르 행렬이 존재한다면, 이는 <math>\mathcal X_n</math> 위에서 [[행렬식]] 절댓값 함수 <math>M\mapsto |\det M|</math>를 최대화한다.

=== 정칙 아다마르 행렬 ===
<math>n\times n</math> 아다마르 행렬 <math>H</math>의 '''초과량'''(超過量, {{llang|en|excess}})은 그 모든 성분들의 합이다.
:<math>\operatorname E(H)=\sum_{i,j}H_{i,j}\in\mathbb Z</math>
이는 다음과 같은 [[상계 (수학)|상계]]를 갖는다.
:<math>|\operatorname E(H)|\le n^{3/2}</math>

<math>n\times n</math> 아다마르 행렬 <math>H</math>에 대하여 다음 두 조건이 서로 [[동치]]이며, 이를 만족시키는 아다마르 행렬을 '''정칙 아다마르 행렬'''({{llang|en|regular Hadamard matrix}})이라고 한다.
* <math>\operatorname E(H)= n^{3/2}</math>
* 각 행의 합과 각 열의 합이 각각 일정하다. 즉, 임의의 <math>i,i'\in\{1,2,\dotsc,n\}</math>에 대하여, <math>\textstyle\sum_{j=1}^n(M_{i,j}-M_{i',j})=\sum_{j=1}^n(M_{j,i}-M_{j,i'})=0</math>이다.

정칙 아다마르 행렬의 크기는 항상 [[제곱수]]이다. 즉, <math>1\times1</math> 또는 <math>4m^2\times 4m^2</math>의 꼴이다.

== 연산 ==
만약 <math>H</math>가 아다마르 행렬이라면, <math>-H</math> 역시 아다마르 행렬이다. 보다 일반적으로, 아다마르 행렬에 다음 연산을 가해도 아다마르 행렬을 이룬다.
* 임의의 한 열에 &minus;1을 곱하기
* 임의의 한 행에 &minus;1을 곱하기
* 열의 순서를 뒤바꾸기
* 행의 순서를 뒤바꾸기

=== 실베스터 구성 ===
임의의 두 아다마르 행렬
:<math>H_{m\times m}\in\operatorname{Mat}(m,m;\mathbb R)</math>
:<math>H_{n\times n}\in\operatorname{Mat}(n,n;\mathbb R)</math>
이 주어졌을 때, 그 [[크로네커 곱]]
:<math>H_{m\times m}\otimes H_{n\times n}=H_{mn\times mn}</math>
은 역시 아다마르 행렬이다. 특히,
:<math>H_{2\times2}=\begin{pmatrix}1&1\\1&-1\end{pmatrix}</math>
를 사용하여, 크기 <Math>2^k</math>의 아다마르 행렬들을 구성할 수 있다. 이를 '''실베스터 구성'''({{llang|en|Sylvester’s construction}})이라고 한다.

이에 따라,
:<math>H_{1\times 1}=\begin{pmatrix}1\end{pmatrix}</math>
로부터 시작하여 <math>2^k\times 2^k</math> 크기의 아다마르 행렬들을 구성할 수 있다.

=== 페일리 구성 ===
'''페일리 구성'''({{llang|en|Paley construction}})은 [[유한체]]를 사용하여 아다마르 행렬을 구성하는 방법이다.

<math>q</math>가 홀수 [[소수 (수론)|소수]]의 거듭제곱이라고 하자. 이제, [[함수]]
:<math>\chi\colon\mathbb F_q\to \{-1,0,1\}</math>
:<math>\chi\colon a\mapsto\begin{cases}
0&a=0\\
1&a\in\{a^2\colon a\in \mathbb F_q^\times\}\\
-1&a\not\in\{a^2\colon a\in \mathbb F_q\}
\end{cases}
</math>
를 정의하자. (여기서 <math>\mathbb F_q</math>는 [[유한체]]이다.)

이제, 임의의 [[전단사 함수]]
:<math>\{1,2,\dotsc,q\}\to\mathbb F_q</math>
:<math>i\mapsto a_i</math>
를 고르자. 그렇다면, <math>q\times q</math> 행렬
:<math>Q_{ij}=\chi(a_i-a_j)</math>
를 정의할 수 있다. 이를 '''야콥스탈 행렬'''({{llang|en|Jacobsthal matrix}})이라고 한다. 만약 <math>q\equiv1\pmod4</math>일 경우 <math>-1\in\mathbb F_q</math>은 제곱수이며, <math>Q</math>는 [[대칭 행렬]]이다 (<Math>Q_{ij}=Q_{ji}</math>). 반면, 만약 <math>q\equiv3\pmod4</math>일 경우 <math>-1</math>은 제곱수가 아니며, <math>Q</math>는 [[반대칭 행렬]]이다 (<math>Q_{ij}=-Q_{ji}</math>).

이제, <math>(q+1)\times(q+1)</math> 행렬
:<math>M_{(q+1)\times(q+1)}=\begin{pmatrix}
0&j_{1\times q}\\
-j_{q\times1}&Q_{q\times q}
\end{pmatrix}</math>
을 정의할 수 있다. 여기서
:<math>j_{1\times q}=\begin{pmatrix}1&1&\dotsm&1\end{pmatrix}</math>
:<math>j_{q\times1}=\begin{pmatrix}1\\1\\\vdots\\1\end{pmatrix}</math>
이다.

만약 <math>q\equiv3\pmod4</math>일 경우,
<math>H_{(q+1)\times(q+1)}=1_{(q+1)\times(q+1)}+M_{(q+1)\times(q+1)}</math>
는 <math>(q+1)\times(q+1)</math> 아다마르 행렬이다.

만약 <math>q\equiv1\pmod4</math>일 경우, <math>M</math>의 각 성분을
:<math>0\mapsto \begin{pmatrix}1&-1\\-1&-1\end{pmatrix}</math>
:<math>\pm1\mapsto \pm\begin{pmatrix}1&1\\1&-1\end{pmatrix}</math>
로 치환하면, <math>2(q+1)\times2(q+1)</math> 아다마르 행렬을 얻는다.

== 예 ==
1×1 행렬
:<math>\begin{pmatrix}1\end{pmatrix}</math>
및
:<math>\begin{pmatrix}-1\end{pmatrix}</math>
은 아다마르 행렬이다. 이는 추가로 정칙 아다마르 행렬이다.

2×2 행렬
:<math>\begin{pmatrix}1&1\\1&-1\end{pmatrix}</math>
은 표준형 아다마르 행렬이지만, 정칙 아다마르 행렬이 아니다.

== 역사 ==
1867년에 [[제임스 조지프 실베스터]]가 <math>2^k\times2^k</math> 크기의 아다마르 행렬을 최초로 구성하였다.<ref>{{저널 인용|이름=James Joseph|성= Sylvester|저자링크=제임스 조지프 실베스터|제목=Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers|저널=Philosophical Magazine|권=34|쪽=461–475|날짜=1867|언어=en}}</ref> 이후 1893년에 [[자크 아다마르]]가 행렬의 [[행렬식]]의 [[절댓값]]의 최댓값의 상계를 발표하였으며,<ref>{{저널 인용|이름=Jacques|성=Hadamard|저자링크=자크 아다마르|제목=Résolution d’une question relative aux déterminants|저널=Bulletin des Sciences Mathématiques |권= 17 |날짜=1893|쪽=240–246|jfm= 25.0221.02|언어=fr}}</ref> 이 때문에 이를 포화시키는 행렬이 “아다마르 행렬”이라고 불리게 되었다.

1933년에 레이먼드 에드워드 앨런 크리스토퍼 페일리({{llang|en|Raymond Edward Alan Christopher Paley}}, 1907~1933)가 [[유한체]]를 사용한 페일리 구성을 발견하였다.<ref>{{저널 인용|성=Paley|이름=Raymond Edward Alan Christopher|날짜=1933-04|제목=On orthogonal matrices|저널=Journal of Mathematics and Physics|권=12|호=1–4|쪽=311–320|doi=10.1002/sapm1933121311|zbl= 0007.10004|jfm=59.0114.04|언어=en}}</ref>

== 같이 보기 ==
* [[윌리엄슨 형식]]
* [[심플렉틱 행렬]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Hadamard matrix}}
* {{eom|title=Hadamard theorem}}
* {{매스월드|id=HadamardMatrix|title=Hadamard matrix}}
* {{매스월드|id=HadamardsMaximumDeterminantProblem|title=Hadamard's maximum determinant problem}}
* {{매스월드|id=PaleyConstruction|title=Paley construction}}
* {{매스월드|id=PaleysTheorem|title=Paley's theorem}}
* {{수학노트|title=아다마르 행렬 (Hadamard matrix)}}
* {{웹 인용|url=http://www.ktword.co.kr/abbr_view.php?m_temp1=4392|제목=하다마드 행렬, 아다마르 행렬, Hadamard 행렬|웹사이트=정보통신기술용어해설|저자=차재복|날짜=2016-10-17|언어=ko}}
* {{웹 인용|url=http://neilsloane.com/hadamard/|제목= A library of Hadamard matrices|이름=Neil J. A.|성=Sloane |언어=en}}
* {{웹 인용|url=http://www.iasri.res.in/design/WebHadamard/|제목=Hadamard Matrix (Beta)|이름=V. K.|성=Gupta|이름2=Rajender|성2=Parsad|이름3=A.|성3=Dhandapani|언어=en|확인날짜=2017-05-22|보존url=https://web.archive.org/web/20160305145506/http://www.iasri.res.in/design/WebHadamard/|보존날짜=2016-03-05|url-status=dead}}

[[분류:수학의 미해결 문제]]
[[분류:조합론]]
[[분류:행렬]]