아다마르 행렬

틀:위키데이터 속성 추적 선형대수학에서 아다마르 행렬(또는 하다마드 행렬, Hadamard行列, 틀:Llang)은 모든 성분이 ±1이며, 행벡터들과 열벡터들이 각각 서로 직교하는 정사각 행렬이다.

정의

실수 성분 $n\times n$ 정사각 행렬 $M\in \mathrm{Mat}(n,n;ℝ)$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 $M$을 아다마르 행렬이라고 한다.

• 모든 성분이 $\pm 1$이며, $M/\sqrt{n}$은 직교 행렬이다.
• 모든 성분이 $\pm 1$이며, 모든 행벡터가 서로 직교한다. 즉, 임의의 $i,i^{\prime }\in \{1,\dots ,n\}$에 대하여 ${\sum }_{j=1}^n{M}_{ij}{M}_{i^{\prime }j}=n{\delta }_{ij}$이다. 즉, $M{M}^{\mathrm{\top }}=n{1}_{n\times n}$이다.
• 모든 성분이 $\pm 1$이며, 모든 열벡터가 서로 직교한다. 즉, 임의의 $j,j^{\prime }\in \{1,\dots ,n\}$에 대하여 ${\sum }_{i=1}^n{M}_{ij}{M}_{i{j}^{\prime }}=n{\delta }_{j{j}^{\prime }}$이다. 즉, $M^{\mathrm{\top }}M=n{1}_{n\times n}$이다.
• 모든 성분이 절댓값 1 이하의 실수이며, $\det M=\pm n^{n/2}$이다.

여기서 $\delta$는 크로네커 델타이다.

아다마르 설계

첫째 행과 첫째 열이 모두 +1만으로 구성된 아다마르 행렬을 표준형 아다마르 행렬(標準型Hadamard行列, 틀:Llang)이라고 한다. 모든 아다마르 행렬은 행 및 열의 순열 및 −1을 곱하는 것을 통해 표준형으로 만들 수 있다.

$n\times n$ 표준형 아다마르 행렬 $M_{n\times n}$이 주어졌을 때,

1. 첫째 행과 첫째 열을 제거하고,
2. 성분을 $(+1,-1)\mapsto (+1,0)$으로 치환하자.

그렇다면, 성분이 0 또는 1인 $(n-1)\times (n-1)$ 정사각 행렬을 얻는다.

만약 $n$이 4의 배수일 경우, 이 $(n-1)\times (n-1)$ 행렬은 $(t=2,n/2-1,n-1)$-블록 설계의 결합 행렬을 이루며,

${\lambda }_0=n-1$

${\lambda }_1=n/2-1$

${\lambda }_2=n/4-1$

이다. 즉,

• $n-1$개의 블록이 있으며,
• 모든 점은 $n/2-1$개의 블록에 속하며,
• 서로 다른 임의의 두 점은 $n/4-1$개의 블록에 공통적으로 속한다.

이를 아다마르 설계(Hadamard設計, 틀:Llang)라고 한다.

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

성질

존재

임의의 자연수 $n\in \mathbb{N}$에 대하여, $n\times n$ 아다마르 행렬이 존재할 필요 조건은 다음과 같다.

$n\in \{1,2\}$이거나, 또는 $n$은 4의 배수이다.

이 조건이 필요 충분 조건이라는 추측은 아다마르 추측(Hadamard推測, 틀:Llang)이라고 하며, 아직 증명되거나 반증되지 못했다. 다만, 적어도 $n<668$에 대해서는 위 조건이 필요 충분 조건이다.

$n\times n$ 아다마르 행렬이 존재하기 위한 알려진 충분 조건은 다음이 있다.

• $n$은 다음과 같은 꼴의 양의 정수들의 곱이다.
  • 2
  • $q+1$, $q\equiv 3(\mathrm{mod}4)$, $q$는 소수의 거듭제곱
  • $2(q+1)$, $q\equiv 1(\mathrm{mod}4)$, $q$는 소수의 거듭제곱

행렬식

행렬 공간 ${𝒳}_n=\{M\in \mathrm{Mat}(n,n;ℝ):|M_{ij}|\le 1\mathrm{\forall }i,j\}$을 정의하자. 그렇다면, 아다마르 부등식(틀:Llang)에 따르면,

$\mathrm{\forall }M\in {𝒳}_n:|\det M|\le n^{n/2}$

이다.

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

정칙 아다마르 행렬

$n\times n$ 아다마르 행렬 $H$의 초과량(超過量, 틀:Llang)은 그 모든 성분들의 합이다.

$\mathrm{E}(H)=\sum _{i,j}{H}_{i,j}\in \mathbb{Z}$

이는 다음과 같은 상계를 갖는다.

$|\mathrm{E}(H)|\le n^{3/2}$

$n\times n$ 아다마르 행렬 $H$에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 아다마르 행렬을 정칙 아다마르 행렬(틀:Llang)이라고 한다.

• $\mathrm{E}(H)=n^{3/2}$
• 각 행의 합과 각 열의 합이 각각 일정하다. 즉, 임의의 $i,i^{\prime }\in \{1,2,\dots ,n\}$에 대하여, ${\sum }_{j=1}^n(M_{i,j}-M_{i^{\prime },j})={\sum }_{j=1}^n(M_{j,i}-M_{j,i^{\prime }})=0$이다.

정칙 아다마르 행렬의 크기는 항상 제곱수이다. 즉, $1\times 1$ 또는 $4m^2\times 4m^2$의 꼴이다.

연산

만약 $H$가 아다마르 행렬이라면, $-H$ 역시 아다마르 행렬이다. 보다 일반적으로, 아다마르 행렬에 다음 연산을 가해도 아다마르 행렬을 이룬다.

• 임의의 한 열에 −1을 곱하기
• 임의의 한 행에 −1을 곱하기
• 열의 순서를 뒤바꾸기
• 행의 순서를 뒤바꾸기

실베스터 구성

임의의 두 아다마르 행렬

$H_{m\times m}\in \mathrm{Mat}(m,m;ℝ)$

$H_{n\times n}\in \mathrm{Mat}(n,n;ℝ)$

이 주어졌을 때, 그 크로네커 곱

$H_{m\times m}\otimes H_{n\times n}=H_{mn\times mn}$

은 역시 아다마르 행렬이다. 특히,

$H_{2\times 2}=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

를 사용하여, 크기 $2^k$의 아다마르 행렬들을 구성할 수 있다. 이를 실베스터 구성(틀:Llang)이라고 한다.

이에 따라,

$H_{1\times 1}=\left(\begin{array}{c}1\end{array}\right)$

로부터 시작하여 $2^k\times 2^k$ 크기의 아다마르 행렬들을 구성할 수 있다.

페일리 구성

페일리 구성(틀:Llang)은 유한체를 사용하여 아다마르 행렬을 구성하는 방법이다.

$q$가 홀수 소수의 거듭제곱이라고 하자. 이제, 함수

$\chi :{𝔽}_q\to \{-1,0,1\}$

$\chi :a\mapsto \{\begin{array}{cc}0& a=0\\ 1& a\in \{a^2:a\in {𝔽}_q^{\times }\}\\ -1& a\in ̸\{a^2:a\in {𝔽}_q\}\end{array}$

를 정의하자. (여기서 ${𝔽}_q$는 유한체이다.)

이제, 임의의 전단사 함수

$\{1,2,\dots ,q\}\to {𝔽}_q$

$i\mapsto a_i$

를 고르자. 그렇다면, $q\times q$ 행렬

$Q_{ij}=\chi (a_i-a_j)$

를 정의할 수 있다. 이를 야콥스탈 행렬(틀:Llang)이라고 한다. 만약 $q\equiv 1(\mathrm{mod}4)$일 경우 $-1\in {𝔽}_q$은 제곱수이며, $Q$는 대칭 행렬이다 ($Q_{ij}=Q_{ji}$). 반면, 만약 $q\equiv 3(\mathrm{mod}4)$일 경우 $-1$은 제곱수가 아니며, $Q$는 반대칭 행렬이다 ($Q_{ij}=-Q_{ji}$).

이제, $(q+1)\times (q+1)$ 행렬

$M_{(q+1)\times (q+1)}=\left(\begin{array}{cc}0& j_{1\times q}\\ -j_{q\times 1}& Q_{q\times q}\end{array}\right)$

을 정의할 수 있다. 여기서

$j_{1\times q}=\left(\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right)$

$j_{q\times 1}=\left(\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right)$

이다.

만약 $q\equiv 3(\mathrm{mod}4)$일 경우, $H_{(q+1)\times (q+1)}=1_{(q+1)\times (q+1)}+M_{(q+1)\times (q+1)}$ 는 $(q+1)\times (q+1)$ 아다마르 행렬이다.

만약 $q\equiv 1(\mathrm{mod}4)$일 경우, $M$의 각 성분을

$0\mapsto \left(\begin{array}{cc}1& -1\\ -1& -1\end{array}\right)$

$\pm 1\mapsto \pm \left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

로 치환하면, $2(q+1)\times 2(q+1)$ 아다마르 행렬을 얻는다.

예

1×1 행렬

$\left(\begin{array}{c}1\end{array}\right)$

및

$\left(\begin{array}{c}-1\end{array}\right)$

은 아다마르 행렬이다. 이는 추가로 정칙 아다마르 행렬이다.

2×2 행렬

$\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

은 표준형 아다마르 행렬이지만, 정칙 아다마르 행렬이 아니다.

역사

1867년에 제임스 조지프 실베스터가 $2^k\times 2^k$ 크기의 아다마르 행렬을 최초로 구성하였다. 이후 1893년에 자크 아다마르가 행렬의 행렬식의 절댓값의 최댓값의 상계를 발표하였으며, 이 때문에 이를 포화시키는 행렬이 “아다마르 행렬”이라고 불리게 되었다.

1933년에 레이먼드 에드워드 앨런 크리스토퍼 페일리(틀:Llang, 1907~1933)가 유한체를 사용한 페일리 구성을 발견하였다.

같이 보기

• 윌리엄슨 형식
• 심플렉틱 행렬

외부 링크

• 틀:Eom
• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:수학노트
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용