아다마르 행렬

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

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

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

n\times n 표준형 아다마르 행렬 M_{n\times n}이 주어졌을 때,
# 첫째 행과 첫째 열을 제거하고,
# 성분을 (+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設計, )라고 한다.

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

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

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

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

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

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

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

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

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

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

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

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

q가 홀수 소수의 거듭제곱이라고 하자. 이제, 함수
:\chi\colon\mathbb F_q\to \{-1,0,1\}
:\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}

를 정의하자. (여기서 \mathbb F_q는 유한체이다.)

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

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

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

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

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

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

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

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

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

## 각주

## 외부 링크
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

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