阿达马矩阵

维基百科,自由的百科全书
跳转至: 导航搜索

数学中,阿达马矩阵是一个方阵,每个元素都是 +1 或 −1,每行都是互相正交的。阿达马矩阵常用于纠错码,如Reed-Muller码。阿达马矩阵的命名来自于法国数学家雅克·阿达马

性质[编辑]

n 阶的阿达马矩阵 H 满足下面的式子

 H H^{\mathrm{T}}= n I_n

这里 Inn × n单位矩阵

假设 M 是一个 n 阶的实矩阵,它的每个元素都是有界的

|Mij| ≤1.

则存在阿达马不等式

 |\operatorname{det}(M)| \leq n^{n/2}.

当且仅当M是阿达马矩阵式上式取等号。

阿达马矩阵的阶数必须是1,2,或者是4的倍数。

西尔维斯特构造法[编辑]

阿达马矩阵最初的构造的例子是由詹姆斯·约瑟夫·西尔维斯特给出的。假设H是一个n阶的阿达马矩阵,则下面的矩阵

\begin{bmatrix} H & H\\ H & -H\end{bmatrix}

给出一个2n阶的阿达马矩阵。连续使用这个方法,我们可以给出下面的一系列矩阵:

 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}
 \vdots

利用这种方法,西尔维斯特成功的构造了任何2k 阶阿达马矩阵,其中k为非负整数。

西尔维斯特给出的矩阵有些特殊的性质。他们都是对称矩阵,并且这些矩阵的都是0。第一行和第一列的元素都是+1,其他各行各列的元素都是一半+1,一半-1。这些矩阵和Walsh函数有密切的关系。

阿达马猜想[编辑]

在阿达马矩阵理论最重要的开放性问题(即尚且无法判断对错的问题)是存在性的问题。

阿达马猜想: 对于每个4的倍数 n = 4kk 为自然数,都存在 n 阶的阿达马矩阵。

西尔维斯特构造法给出了阶数为1, 2, 4, 8, 16, 32 等等的阿达马矩阵,之后阿达马本人给出了阶数为12和20的阿达马矩阵。Raymond Paley 随后给出了任何q+1 阶的阿达马矩阵的方法,其中q 是任何模4为3的质数任意次幂。他也给出了形式为2(q+1)的阿达马矩阵的方法,其中q 是任何模4为1的质数任意次幂。他使用了有限域的办法得出了这些结论。阿达马猜想很可能就是Paley提出的。现在有了更多的构造阿达马矩阵的办法。

Hadi Kharaghani 和 Behruz Tayfeh-Rezaie 2004年6月21日宣布他们构造出了428阶的阿达马矩阵。现在最小的尚未被构造出来的4k阶阿达马矩阵是668阶。

参考[编辑]