선형대수학에서 아다마르 행렬(또는 하다마드 행렬, Hadamard行列, 영어: Hadamard matrix)은 모든 성분이 ±1이며, 행벡터들과 열벡터들이 각각 서로 직교하는 정사각 행렬이다.[1][2][3]
실수 성분
정사각 행렬
에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는
을 아다마르 행렬이라고 한다.
- 모든 성분이
이며,
은 직교 행렬이다.
- 모든 성분이
이며, 모든 행벡터가 서로 직교한다. 즉, 임의의
에 대하여
이다. 즉,
이다.
- 모든 성분이
이며, 모든 열벡터가 서로 직교한다. 즉, 임의의
에 대하여
이다. 즉,
이다.
- 모든 성분이 절댓값 1 이하의 실수이며,
이다.
여기서
는 크로네커 델타이다.
첫째 행과 첫째 열이 모두 +1만으로 구성된 아다마르 행렬을 표준형 아다마르 행렬(標準型Hadamard行列, 영어: standard Hadamard matrix)이라고 한다. 모든 아다마르 행렬은 행 및 열의 순열 및 −1을 곱하는 것을 통해 표준형으로 만들 수 있다.
표준형 아다마르 행렬
이 주어졌을 때,
- 첫째 행과 첫째 열을 제거하고,
- 성분을
으로 치환하자.
그렇다면, 성분이 0 또는 1인
정사각 행렬을 얻는다.
만약
이 4의 배수일 경우, 이
행렬은
-블록 설계의 결합 행렬을 이루며,
![{\displaystyle \lambda _{0}=n-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44f140739e53c21af7d979790e7749397fe6a444)
![{\displaystyle \lambda _{1}=n/2-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce52f5896d053dc3dd0258b97158cb2cfd653f33)
![{\displaystyle \lambda _{2}=n/4-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db85d468705260e971bf6ed37b55fdb51aa7f737)
이다. 즉,
개의 블록이 있으며,
- 모든 점은
개의 블록에 속하며,
- 서로 다른 임의의 두 점은
개의 블록에 공통적으로 속한다.
이를 아다마르 설계(Hadamard設計, 영어: Hadamard design)라고 한다.
반대로,
인
-블록 설계가 주어졌을 때, 위와 같이 표준형 아다마르 행렬을 재구성할 수 있다.
임의의 자연수
에 대하여,
아다마르 행렬이 존재할 필요 조건은 다음과 같다.
이거나, 또는
은 4의 배수이다.
이 조건이 필요 충분 조건이라는 추측은 아다마르 추측(Hadamard推測, 영어: Hadamard conjecture)이라고 하며, 아직 증명되거나 반증되지 못했다. 다만, 적어도
에 대해서는 위 조건이 필요 충분 조건이다.
아다마르 행렬이 존재하기 위한 알려진 충분 조건은 다음이 있다.
은 다음과 같은 꼴의 양의 정수들의 곱이다.
- 2
,
,
는 소수의 거듭제곱
,
,
는 소수의 거듭제곱
행렬 공간
을 정의하자. 그렇다면, 아다마르 부등식(영어: Hadamard inequality)에 따르면,
![{\displaystyle \forall M\in {\mathcal {X}}_{n}\colon |\det M|\leq n^{n/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec13bf522f903640056dee0ff0ad1e49c435d739)
이다.
아다마르 행렬의 행렬식은
이다. 즉, 만약
아다마르 행렬이 존재한다면, 이는
위에서 행렬식 절댓값 함수
를 최대화한다.
아다마르 행렬
의 초과량(超過量, 영어: excess)은 그 모든 성분들의 합이다.
![{\displaystyle \operatorname {E} (H)=\sum _{i,j}H_{i,j}\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd76d7a35ce9577ddb6d6678310738fd11b76185)
이는 다음과 같은 상계를 갖는다.
![{\displaystyle |\operatorname {E} (H)|\leq n^{3/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96dd3a16c76ac066df487945d9855dfc97eb192e)
아다마르 행렬
에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 아다마르 행렬을 정칙 아다마르 행렬(영어: regular Hadamard matrix)이라고 한다.
![{\displaystyle \operatorname {E} (H)=n^{3/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aad024e5955e1f6b3c99fda45985a238260e335a)
- 각 행의 합과 각 열의 합이 각각 일정하다. 즉, 임의의
에 대하여,
이다.
정칙 아다마르 행렬의 크기는 항상 제곱수이다. 즉,
또는
의 꼴이다.
만약
가 아다마르 행렬이라면,
역시 아다마르 행렬이다. 보다 일반적으로, 아다마르 행렬에 다음 연산을 가해도 아다마르 행렬을 이룬다.
- 임의의 한 열에 −1을 곱하기
- 임의의 한 행에 −1을 곱하기
- 열의 순서를 뒤바꾸기
- 행의 순서를 뒤바꾸기
임의의 두 아다마르 행렬
![{\displaystyle H_{m\times m}\in \operatorname {Mat} (m,m;\mathbb {R} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5187eaa6c06a60c7d91f03124a1de5e863df2c0a)
![{\displaystyle H_{n\times n}\in \operatorname {Mat} (n,n;\mathbb {R} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7a5fbcfd7eae7abd4435a758d48551d5bc296e7)
이 주어졌을 때, 그 크로네커 곱
![{\displaystyle H_{m\times m}\otimes H_{n\times n}=H_{mn\times mn}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/710641e09235b94144fc28cca3b3f03d1bc85b7d)
은 역시 아다마르 행렬이다. 특히,
![{\displaystyle H_{2\times 2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d066c80dbd6a69a1aa1cf7b2029145644eb0780)
를 사용하여, 크기
의 아다마르 행렬들을 구성할 수 있다. 이를 실베스터 구성(영어: Sylvester’s construction)이라고 한다.
이에 따라,
![{\displaystyle H_{1\times 1}={\begin{pmatrix}1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5c723cb0d058d88f139696f25628949cac974d6)
로부터 시작하여
크기의 아다마르 행렬들을 구성할 수 있다.
페일리 구성(영어: Paley construction)은 유한체를 사용하여 아다마르 행렬을 구성하는 방법이다.
가 홀수 소수의 거듭제곱이라고 하자. 이제, 함수
![{\displaystyle \chi \colon \mathbb {F} _{q}\to \{-1,0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f21dda99e8e58002c64a5a5dd14046aa8da9c67)
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca80fbfdb920071682092daad34fa1368a4bc92b)
를 정의하자. (여기서
는 유한체이다.)
이제, 임의의 전단사 함수
![{\displaystyle \{1,2,\dotsc ,q\}\to \mathbb {F} _{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37b80b037990fc75ac7d98c0ca0e2e1030b36bd2)
![{\displaystyle i\mapsto a_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5a40952c1eb1b555fb21927867fa5db7957083c)
를 고르자. 그렇다면,
행렬
![{\displaystyle Q_{ij}=\chi (a_{i}-a_{j})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2e1aa0b49b07759ac8afcf13848c392e04218d0)
를 정의할 수 있다. 이를 야콥스탈 행렬(영어: Jacobsthal matrix)이라고 한다. 만약
일 경우
은 제곱수이며,
는 대칭 행렬이다 (
). 반면, 만약
일 경우
은 제곱수가 아니며,
는 반대칭 행렬이다 (
).
이제,
행렬
![{\displaystyle M_{(q+1)\times (q+1)}={\begin{pmatrix}0&j_{1\times q}\\-j_{q\times 1}&Q_{q\times q}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e518ed312238ab1adf061979a5d1d1aafe2f083e)
을 정의할 수 있다. 여기서
![{\displaystyle j_{1\times q}={\begin{pmatrix}1&1&\dotsm &1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67cb8f82303d3372a353ccbfadc02319db80f964)
![{\displaystyle j_{q\times 1}={\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e33a1e51be62e345d34f33fde9248d4d05eec182)
이다.
만약
일 경우,
는
아다마르 행렬이다.
만약
일 경우,
의 각 성분을
![{\displaystyle 0\mapsto {\begin{pmatrix}1&-1\\-1&-1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd487c036e9ec0979d9bf3f6c20b0c7672efe10f)
![{\displaystyle \pm 1\mapsto \pm {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4d5c8cee68d295670fc1bf0cd7d387510b8b91a)
로 치환하면,
아다마르 행렬을 얻는다.
1×1 행렬
![{\displaystyle {\begin{pmatrix}1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca455b18a9a4f49b0c715053ea4d994555261643)
및
![{\displaystyle {\begin{pmatrix}-1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1562c45b8ccffd57e396b07ec8732a356d4d0da5)
은 아다마르 행렬이다. 이는 추가로 정칙 아다마르 행렬이다.
2×2 행렬
![{\displaystyle {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cdff3276fa397abc5fedc5fce99ca395921e172)
은 표준형 아다마르 행렬이지만, 정칙 아다마르 행렬이 아니다.
1867년에 제임스 조지프 실베스터가
크기의 아다마르 행렬을 최초로 구성하였다.[4] 이후 1893년에 자크 아다마르가 행렬의 행렬식의 절댓값의 최댓값의 상계를 발표하였으며,[5] 이 때문에 이를 포화시키는 행렬이 “아다마르 행렬”이라고 불리게 되었다.
1933년에 레이먼드 에드워드 앨런 크리스토퍼 페일리(영어: Raymond Edward Alan Christopher Paley, 1907~1933)가 유한체를 사용한 페일리 구성을 발견하였다.[6]
- ↑ Hedayat, A.; Wallis, W. D. (1978년 11월). “Hadamard matrices and their applications”. 《The Annals of Statistics》 (영어) 6 (6): 1184–1238. ISSN 0090-5364. JSTOR 2958712.
- ↑ Agaian, S. S. (1985). 《Hadamard matrices and their applications》. Lecture Notes in Mathematics (영어) 1168. Springer-Verlag. doi:10.1007/BFb0101073. ISBN 978-3-540-16056-4. ISSN 0075-8434.
- ↑ Seberry, Jennifer; Yamada, Mieko (1992년 6월). 〈Hadamard matrices, sequences, and block designs〉 (PDF). Dinitz, Jeffrey H.; Stinson, Douglas R. 《Contemporary design theory: a collection of surveys》. Wiley-Interscience Series in Discrete Mathematics and Optimization (영어). Wiley. 431–560쪽. ISBN 978-0-471-53141-8.
- ↑ Sylvester, James Joseph (1867). “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.
- ↑ Hadamard, Jacques (1893). “Résolution d’une question relative aux déterminants”. 《Bulletin des Sciences Mathématiques》 (프랑스어) 17: 240–246. JFM 25.0221.02.
- ↑ Paley, Raymond Edward Alan Christopher (1933년 4월). “On orthogonal matrices”. 《Journal of Mathematics and Physics》 (영어) 12 (1–4): 311–320. doi:10.1002/sapm1933121311. JFM 59.0114.04. Zbl 0007.10004.
- “Hadamard matrix”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- “Hadamard theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Hadamard matrix”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Hadamard's maximum determinant problem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Paley construction”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Paley's theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- 이철희. “아다마르 행렬 (Hadamard matrix)”. 《수학노트》.
- 차재복 (2016년 10월 17일). “하다마드 행렬, 아다마르 행렬, Hadamard 행렬”. 《정보통신기술용어해설》.
- Sloane, Neil J. A. “A library of Hadamard matrices” (영어).
- Gupta, V. K.; Parsad, Rajender; Dhandapani, A. “Hadamard Matrix (Beta)” (영어). 2016년 3월 5일에 원본 문서에서 보존된 문서. 2017년 5월 22일에 확인함.