아다마르 행렬

선형대수학에서 아다마르 행렬(또는 하다마드 행렬, Hadamard行列, 영어: Hadamard matrix)은 모든 성분이 ±1이며, 행벡터들과 열벡터들이 각각 서로 직교하는 정사각 행렬이다.^[1][2][3]

정의

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

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

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

아다마르 설계

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

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

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

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

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

${\displaystyle \lambda _{0}=n-1}$

${\displaystyle \lambda _{1}=n/2-1}$

${\displaystyle \lambda _{2}=n/4-1}$

이다. 즉,

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

이를 아다마르 설계(Hadamard設計, 영어: Hadamard design)라고 한다.

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

성질

존재

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

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

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

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

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

행렬식

행렬 공간 ${\displaystyle {\mathcal {X}}_{n}=\{M\in \operatorname {Mat} (n,n;\mathbb {R} )\colon |M_{ij}|\leq 1\;\forall i,j\}}$을 정의하자. 그렇다면, 아다마르 부등식(영어: Hadamard inequality)에 따르면,

${\displaystyle \forall M\in {\mathcal {X}}_{n}\colon |\det M|\leq n^{n/2}}$

이다.

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

정칙 아다마르 행렬

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

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

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

${\displaystyle |\operatorname {E} (H)|\leq n^{3/2}}$

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

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

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

연산

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

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

실베스터 구성

임의의 두 아다마르 행렬

${\displaystyle H_{m\times m}\in \operatorname {Mat} (m,m;\mathbb {R} )}$

${\displaystyle H_{n\times n}\in \operatorname {Mat} (n,n;\mathbb {R} )}$

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

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

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

${\displaystyle H_{2\times 2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

를 사용하여, 크기 ${\displaystyle 2^{k}}$의 아다마르 행렬들을 구성할 수 있다. 이를 실베스터 구성(영어: Sylvester’s construction)이라고 한다.

이에 따라,

${\displaystyle H_{1\times 1}={\begin{pmatrix}1\end{pmatrix}}}$

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

페일리 구성

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

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

${\displaystyle \chi \colon \mathbb {F} _{q}\to \{-1,0,1\}}$

${\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}}}$

를 정의하자. (여기서 ${\displaystyle \mathbb {F} _{q}}$는 유한체이다.)

이제, 임의의 전단사 함수

${\displaystyle \{1,2,\dotsc ,q\}\to \mathbb {F} _{q}}$

${\displaystyle i\mapsto a_{i}}$

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

${\displaystyle Q_{ij}=\chi (a_{i}-a_{j})}$

를 정의할 수 있다. 이를 야콥스탈 행렬(영어: Jacobsthal matrix)이라고 한다. 만약 ${\displaystyle q\equiv 1{\pmod {4}}}$일 경우 ${\displaystyle -1\in \mathbb {F} _{q}}$은 제곱수이며, ${\displaystyle Q}$는 대칭 행렬이다 (${\displaystyle Q_{ij}=Q_{ji}}$). 반면, 만약 ${\displaystyle q\equiv 3{\pmod {4}}}$일 경우 ${\displaystyle -1}$은 제곱수가 아니며, ${\displaystyle Q}$는 반대칭 행렬이다 (${\displaystyle Q_{ij}=-Q_{ji}}$).

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

${\displaystyle M_{(q+1)\times (q+1)}={\begin{pmatrix}0&j_{1\times q}\\-j_{q\times 1}&Q_{q\times q}\end{pmatrix}}}$

을 정의할 수 있다. 여기서

${\displaystyle j_{1\times q}={\begin{pmatrix}1&1&\dotsm &1\end{pmatrix}}}$

${\displaystyle j_{q\times 1}={\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}}$

이다.

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

만약 ${\displaystyle q\equiv 1{\pmod {4}}}$일 경우, ${\displaystyle M}$의 각 성분을

${\displaystyle 0\mapsto {\begin{pmatrix}1&-1\\-1&-1\end{pmatrix}}}$

${\displaystyle \pm 1\mapsto \pm {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

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

예

1×1 행렬

${\displaystyle {\begin{pmatrix}1\end{pmatrix}}}$

및

${\displaystyle {\begin{pmatrix}-1\end{pmatrix}}}$

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

2×2 행렬

${\displaystyle {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

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

역사

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

1933년에 레이먼드 에드워드 앨런 크리스토퍼 페일리(영어: Raymond Edward Alan Christopher Paley, 1907~1933)가 유한체를 사용한 페일리 구성을 발견하였다.^[6]

같이 보기

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