하다마드 행렬

수학에서 프랑스 수학자 자크 하다마르의 이름을 딴 하다마드 행렬은 입력이 +1 또는 -1이고 행이 상호 직교하는 사각 행렬이다. 기하학적 용어로, 이것은 Hadamard 행렬의 각 행 쌍이 두 개의 수직 벡터를 나타낸다는 것을 의미하며, 조합적 용어로 각 행 쌍은 열의 정확히 절반에 일치하는 항목을 가지고 있고 나머지 열에는 일치하지 않는 항목을 가지고 있다는 것을 의미한다. 이 정의의 결과로서 해당 속성은 행뿐만 아니라 열에 대해서도 유지된다. n×n Hadamard 행렬의 행에 의해 확장되는 n차원 병렬로토프는 항목이 절대값으로 경계되는 벡터에 의해 확장되는 병렬로토프 중에서 가능한 최대 n차원 볼륨을 가진다. 마찬가지로, Hadamard 행렬은 절대값이 1보다 작거나 같은 행렬 사이에 최대 결정 인자를 가지고 있으며, 따라서 Hadamard의 최대 결정 인자 문제에 대한 극단적 해결책이다.

특정 Hadamard 행렬은 Hadamard 코드(Red-Muller 코드로 일반화됨)를 사용하는 오류 수정 코드로 거의 직접 사용할 수 있으며, 통계학자가 매개변수 추정기의 분산을 추정하기 위해 사용하는 균형 잡힌 반복 복제(BRR)에도 사용된다.

특성.

H를 순서 n의 Hadamard 행렬이 되게 하라. H의 전치는 그 역과 밀접한 관계가 있다. 사실:

${\displaystyle HH^{\textsf{T}=nI_{n}}}$

여기서 나는_n n × n 아이덴티티 매트릭스이고 H는^T H의 전치물이다. 이것이 사실인지 확인하려면, H의 행이 모두 실수의 필드 위에 있는 직교 벡터이며 각각 $길이$가 n$${\$displaystyle${\$sqrt{n}}$임을 알 수 있다$.$ H를 이 길이로 나누면 직교 행렬이 그 역행렬이 된다. 길이를 다시 곱하면 위와 같다. 결과적으로.

${\displaystyle \operatorname {det}(H)=\pm n^{\frac{n}{2}},}$

여기서 det(H)는 H의 결정 요인이다.

M이 n 순서의 복잡한 행렬이며, 각 i, j에 대해 1과 n 사이의 M_ij ≤ 1로 경계가 지정된다고 가정한다. 그 때 하다마드의 결정인자 바운드는 다음과 같이 말하고 있다.

${\displaystyle \operatorname {det}(M) \leq n^{\frac {n}{2}.}$

이 바운드의 동일성은 M이 Hadamard 행렬인 경우에만 실제 행렬 M에 대해 달성된다.

하다마드 행렬의 순서는 1, 2 또는 4의 배수여야 한다.^[1]

실베스터 건축

하다마드 행렬의 예는 실제로 제임스 조셉 실베스터에 의해 1867년에 처음 건설되었다. H를 순서 n의 Hadamard 행렬이 되게 하라. 분할된 행렬

${\displaystyle {\bmatrix}H&H\\H&-H\end{bmatrix}}$

2n 순서의 하다마드 행렬이야 이러한 관찰은 반복적으로 적용될 수 있으며 월시 행렬이라고도 불리는 행렬의 다음 순서로 이어진다.

${\displaystyle {\reasoned}H_{1}&={\begin{bmatrix}1\end{bmatrix}},\\H_{2}&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H_{4}&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},\end{aligned}}}$

그리고

${\displaystyle H_{2^{k}={\begin{bmatrix}H_{2^{k-1}&H_{2^{k-1}\\H_{2^{k-1}&-H_{2^{k-1}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1},}$

$2{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle kn}$ N ${\displaystyle 2\leq$ k$\in N}$의 경우$,$ 여기서 $\otimes {\displaystyle }$ ${\displaystyle \otimes }$은 Kronecker 제품을 의미한다.

이런 방식으로 실베스터는 음이 아닌 정수 k마다 순서 2의^k 하다마드 행렬을 구성했다.^[2]

실베스터의 매트릭스에는 여러 가지 특별한 성질이 있다. 그것들은 대칭이며, k ≥ 1 (2^k > 1)일 때 추적 0을 가진다. 첫 번째 열과 첫 번째 행의 원소들은 모두 양이다. 다른 모든 행과 열의 원소는 양과 음으로 균등하게 나누어져 있다. 실베스터 행렬은 월시 함수와 밀접하게 연결되어 있다.

대체건설

만약 우리가 그룹${\displaystyle }$동형성${\displaystyle \{1}$, -${\displaystyle }$1, × }${\displaystyle \mapsto \{0,}$ ${\displaystyle 1}$,${\displaystyle \}}$ }$$} {\$displaystyle \{1$,-1,\time \}\$mapsto \{0,1$,\oplus$$\}}}}}를 사용하여 Hadamard 행렬의 요소들을 매핑한다면, 우리는 실베스터의 대체 구조를 설명할 수 있다. 먼저 행렬 $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$열이 오름차순으로 배열된 모든 n비트 번호로 구성된 $행렬{\displaystyle }$ F ${\displaystyle \times }$ ${\displaystyle {2n}^{}}$ ${\$ 2$^{n}$을 고려하십시오. 다음에 따라 F ${\displaystyle n_{}}$ ${\$를 재귀적으로$$ 정의할 수 있다.

${\displaystyle {\reasoned}F_{1}&={\begin{bmatrix}0&1\end{bmatrix}}\\\F_{n}&={\begin{bmatrix}0_{1\times 2^{n-1}_{1\times 2^{n-1}}{n-1}\\\\\F_{n-1}&F_{n-1}\end{bmatrix}.\end{정렬}}}$

위와 같은 동형성 하의 하다마드 행렬의 이미지는 다음과 같이 유도를 통해 알 수 있다.

${\displaystyle H_{2^{n}=F_{n}^{\textsf{T}F_{n}.}$

이 구조는 Hadamard 행렬 $H{\displaystyle {}_{}}$ ${\displaystyle {{2n}^{}}_{}}$ ${\$의 행을 길이 ${\displaystyle {2n}^{}}$ ${\$의 선형 오류$$ 수정 코드로 볼 수$$ 있으며, 행렬 ${\displaystyle F_{}}$ ${\displaystyle F_{n}}$를 생성하는 최소$$ 거리 ${\displaystyle {2n}^{}}$- ${n-{$n-1}로 볼 수 있음을 입증한다.$}$

이 코드를 월시 코드라고도 한다. 이와는 대조적으로 Hadamard 코드는 약간 다른 절차에 의해$$ Hadamard $매트릭스{\displaystyle {}_{}}$ H ${\displaystyle {{2n}^{}}_{}}$ ${\$에서 생성된다.

하다마드 추측

Hadamard 행렬 이론에서 가장 중요한 공개 문제는 존재의 그것이다. 하다마드 추측은 모든 양의 정수 k에 대해 순서 4k의 하다마드 행렬이 존재함을 제안한다. 하다마드 추측도 파니의 작품 이전에 다른 사람들에 의해 암묵적으로 고려되기는 했지만, 파일리의 추측에 기인해 왔다.^[3]

실베스터 공사의 일반화를 통해 ${\displaystyle {Hn}_{}}$ ${\$와 ${\displaystyle {Hm}_{}}$ ${\$이 각각$$ 주문 n과 m의 Hadamard 행렬이라면 $Hn{\displaystyle {}_{}{n}_{}}$ ${\displaystyle H_{}}$ ${\displaystyle {}_{}}$ ${\$}\$otimes H_{$m}}은 주문의 Hadamard 행렬이라는 것을 증명한다. 이 결과는 일단 더 작은 주문의 행렬이 알려지면 더 높은 순서의 Hadamard 행렬을 생산하는 데 사용된다.

실베스터의 1867년 건축 수율은 1, 2, 4, 8, 16, 32 등 주문서 1, 2, 4, 8, 32이다. 12번과 20번 주문의 Hadamard 행렬은 이후 Hadamard에 의해 건설되었다(1893년).^[4] 1933년 레이먼드 페일리는 q가 3모듈로 4에 합치되는 어떤 원전원일 때 q+1의 하다마드 행렬을 생산하고, q가 1모듈로 4에 합치되는 원전원일 때 q+1) 순서 q+1의 하다마드 행렬을 생산하는 팰리 건축물을 발견했다.^[5] 그의 방법은 한정된 분야를 사용한다.

실베스터의 방법과 페일리의 방법의 조합으로 구성할 수 없는 가장 작은 순서는 92이다. 1962년 JPL에서 바우머트, 골롬, 홀이 컴퓨터를 이용해 이 주문의 하다마드 매트릭스를 발견했다.^[6] 그들은 윌리엄슨 때문에 많은 추가 수주를 한 건설사를 이용했다.^[7] Hadamard 매트릭스를 건설하는 다른 많은 방법들이 현재 알려져 있다.

2005년, 하디 카라가니와 베루즈 타이페-레자이는 주문서 428의 하다마드 매트릭스 건축을 출판했다.^[8] 결과적으로, 현재 알려진 하다마드 행렬이 없는 가장 작은 순서는 668이다.

2014년^[update] 현재, 그 순서의 어떠한 Hadamard 행렬도 알려져 있지 않은 2000년도보다 작거나 같은 4의 12개의 배수가 있다.^[9] 그것들은: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964이다.

등가성 및 고유성

행이나 열을 부정하거나 행이나 열을 상호 교환하여 다른 행으로부터 하나를 얻을 수 있다면 두 개의 Hadamard 행렬은 동등한 것으로 간주된다. 등가성까지, 1, 2, 4, 8, 12 순서의 독특한 하다마드 행렬이 있다. 순서 16의 불평등 행렬 5개, 순서 20의 3개, 순서 24의 60개, 순서 28의 487개가 있다. 수백만 개의 불평등 행렬은 32, 36, 40개의 명령으로 알려져 있다. 또한 전이가 가능한 등가성의 더 강력한 개념을 사용하여, 순서 16의 4가지 불평등 행렬, 순서 20의 3가지, 순서 24의 36 그리고 순서 28의 294가 있다.^[10]

Hadamard 매트릭스도 다음과 같은 점에서 고유하게 복구할 수 있다. 순서 $n{\displaystyle }$ ${\displaystyle n}$의 H ${\displaystyle H}$에 $O{\displaystyle ({n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$/ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n^{2}/\log n)$ 항목이$$ 무작위로 삭제된 경우$$, 압도적 가능성이 있는 경우, 손상된 항목에서$$ 원래의 행렬 $H{\displaystyle }$ ${\displaystystyle H}$을 완벽하게 복구할 수 있다. 복구 알고리즘은 매트릭스 역전과 동일한 계산 비용을 갖는다.^[11]

특례

하다마드 행렬의 많은 특별한 사례들이 수학 문헌에서 조사되었다.

스큐 하다마드 행렬

$A{\displaystyle {}^{}}$ Hadamard ${\displaystyle \mathrm{매트릭스}}$H는${\displaystyle {}^{}{H}^{}}$ ${\displaystyle T}$+ ${\displaystyle \mathrm{H}}$ = 2$$I. ${\displaystyle$ H$^{\textsf{T}+H$=2I일 경우 스큐이다$.$$}$ 스큐 Hadamard 행렬은$$ 모든 행과 해당 열을 -1만큼 곱한 후에도 스큐 Hadamard 행렬로 남아 있다. 이를 통해 예를 들어 첫 번째 행의 모든 원소가 1이 되도록 스큐 Hadamard 행렬을 정규화할 수 있다.

1972년 레이드와 브라운은 순서 n + 1의 스큐 하다마드 매트릭스가 존재하는 경우에만 두 배로 정기적인 순서 토너먼트가 존재한다는 것을 보여주었다. n순위의 수학 토너먼트에서는 n명의 선수가 각각 다른 선수와 한 경기를 치르게 되는데, 각 경기는 한 선수의 승리와 다른 선수의 패배를 초래한다. 각 선수가 같은 수의 경기를 이기면 토너먼트가 규칙적이다. 두 명의 다른 선수에게 패한 상대들의 수가 모든 다른 선수 쌍에 대해 같다면 정규 토너먼트는 두 배로 규칙적이다. n(n-1)/2경기는 각각 1명의 선수에게 승리한 결과를 가져왔기 때문에 각 선수가 승리(n-1)/2경기(동일번 패)한다. 주어진 선수에게 패한 (n-1)/2명의 각 선수도 (n-3)/2명의 선수에게 패하기 때문에, j가 i와 주어진 선수에게 모두 패하는 선수 쌍(i, j)의 수는 (n-1) (n-3) / 4. 주어진 선수와 (n-1)의 페어가 다르게 계산되는 경우에도 같은 결과를 얻어야 한다: 주어진 선수와 (n-1) 다른 선수들 중 한 명이 함께 배변한다.같은 수의 공통 상대 그러므로 패배한 상대들의 공통적인 수는 (n-3) / 4. 스큐 하다마드 매트릭스는 원래 플레이어를 모두 물리치는 추가 플레이어를 도입한 다음 i행, j열은 i = j 또는 i를 이기면 1을 포함하고 j를 이기면 -1을 포함하는 규칙에 따라 플레이어가 라벨을 붙인 행과 열로 매트릭스를 형성함으로써 얻는다.. 이 역방향 서신은 스큐 하다마드 매트릭스에서 2배 정규 토너먼트를 생성하는데, 스큐 하다마드 매트릭스가 정규화 되어 첫 번째 행의 모든 요소가 1이 된다고 가정한다.^[12]

일반 하다마드 행렬

일반 Hadamard 행렬은 행과 열의 합계가 모두 같은 실제 Hadamard 행렬이다. 규칙적인 n×n 하다마드 행렬의 존재에 필요한 조건은 n이 완벽한 사각형이 되는 것이다. 순환 행렬은 분명히 규칙적이며, 따라서 순환 행렬은 정사각형이어야 한다. 더욱이, n×n 순환제 Hadamard 매트릭스가 n > 1로 존재한다면 n은 반드시 u 홀수가 있는 4u² 형식이어야 할 것이다.^[13][14]

서큘런트 하다마드 행렬

그러나 순환성 하다마드 행렬 추측은 알려진 1×1 및 4×4 예시 외에 그러한 행렬은 존재하지 않는다고 주장한다. 이는 10 미만의⁴ u 26개 값을 제외한 모든 값에 대해 검증되었다.^[15]

일반화

한 가지 기본적인 일반화는 무게 매트릭스다. 체중계 행렬은 항목도 0일 수 있고 W ${\displaystyle {}^{}}$ ${\displaystyle T^{}}$= w ${\displaystyle I}$ ${\displaystyle WW^{\textsf{T}=wI}$를 만족하는$$ 정사각형 행렬이다. 중량과 순서가 같은 무게 행렬은 하다마드 행렬이다.^[16]

또 다른 일반화에서는 복합 Hadamard^* 매트릭스를 단위 계수의 복잡한 숫자로, H H = n I를_n 만족시키는 매트릭스로 정의한다. 여기서 H는^* 연산자 알헤브라의 연구와 양자 계산 이론에서 발생하는 복합 Hadamard 매트릭스의 결합 전이다. Butson형 Hadamard 행렬은 복잡한 Hadamard 행렬로, 입력된 항목이 q^th 루트로 통합된다. 콤플렉스 하다마드 매트릭스라는 용어는 일부 저자들이 사례 q = 4를 구체적으로 언급하기 위해 사용해 왔다.

실용적 응용

• 올리비아 MFSK – 단파 대역에서 어려운 조건(신호 대 잡음 비 + 다중 경로 전파)에서 작동하도록 설계된 아마추어 무선 디지털 프로토콜
• 균형 잡힌 반복 복제(BRR) – 통계학자가 통계 추정기의 분산을 추정하기 위해 사용하는 기법.
• 코드화된 개구부 분광 분석 – 빛의 스펙트럼을 측정하기 위한 기구. 코드화된 개구부 분광기에 사용되는 마스크 요소는 종종 Hadamard 행렬의 변형이다.
• 피드백 지연 네트워크 – Hadamard 행렬을 사용하여 샘플 값을 혼합하는 디지털 반향 장치
• Plackett-Burman 실험 설계 - 다수의 독립 변수에 대한 일부 측정 수량의 의존성을 조사하기 위한 실험.
• 반응에 미치는 소음 인자 영향을 조사하기 위한 강력한 매개변수 설계
• 신호 처리 및 결정되지 않은 선형 시스템을 위한 압축 감지(역대 문제)
• 양자 컴퓨팅을 위한 Quantum Hadamard 게이트와 양자 알고리즘을 위한 Hadamard 변환.

참고 항목

• 조합 설계
• 하다마드 변형
• Quincunx 행렬
• 월시 행렬
• 양자 논리 게이트

메모들

추가 읽기

• Baumert, L. D.; Hall, Marshall (1965). "Hadamard matrices of the Williamson type". Math. Comp. 19 (91): 442–447. doi:10.1090/S0025-5718-1965-0179093-2. MR 0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Hadamard matrices, orthogonal designs and construction algorithms". Designs 2002: Further computational and constructive design theory. Boston: Kluwer. pp. 133–205. ISBN 978-1-4020-7599-5.
• Goethals, J. M.; Seidel, J. J. (1970). "A skew Hadamard matrix of order 36". J. Austral. Math. Soc. 11 (3): 343–344. doi:10.1017/S144678870000673X.
• Kimura, Hiroshi (1989). "New Hadamard matrix of order 24". Graphs and Combinatorics. 5 (1): 235–242. doi:10.1007/BF01788676. S2CID 39169723.
• Mood, Alexander M. (1964). "On Hotelling's Weighing Problem". Annals of Mathematical Statistics. 17 (4): 432–446. doi:10.1214/aoms/1177730883.
• Reid, K. B.; Brown, E. (1972). "Doubly regular tournaments are equivalent to skew Hadamard matrices". J. Combin. Theory Ser. A. 12 (3): 332–338. doi:10.1016/0097-3165(72)90098-2.
• Seberry Wallis, Jennifer (1976). "On the existence of Hadamard matrices". J. Comb. Theory A. 21 (2): 188–195. doi:10.1016/0097-3165(76)90062-5.
• Seberry, Jennifer (1980). "A construction for generalized hadamard matrices". J. Statist. Plann. Infer. 4 (4): 365–368. doi:10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005). "On some applications of Hadamard matrices". Metrika. 62 (2–3): 221–239. doi:10.1007/s00184-005-0415-y. S2CID 40646.
• Spence, Edward (1995). "Classification of hadamard matrices of order 24 and 28". Discrete Math. 140 (1–3): 185–242. doi:10.1016/0012-365X(93)E0169-5.
• Yarlagadda, R. K.; Hershey, J. E. (1997). Hadamard Matrix Analysis and Synthesis. Boston: Kluwer. ISBN 978-0-7923-9826-4.

외부 링크

• 스큐 하드마드 매트릭스(최대 28개 주문 유형 포함) 100개 주문까지 포함.
• "Hadamard Matrix". OEIS에서
• N. J. A. Sloane. "Library of Hadamard Matrices".
• 668, 716, 876 & 892를 제외한 모든 주문을 1000까지 획득하는 온라인 유틸리티.
• JPL: 1961년, NASA의 제트 추진 연구소와 칼텍의 수학자들이 함께 92개의 행과 기둥을 포함하는 해다마드 매트릭스를 건설했다.