アダマール行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』

アダマール行列（アダマールぎょうれつ）とは、要素が1または-1のいずれかであり、かつ各行が互いに直交であるような正方行列である。すなわち、アダマール行列の任意の2つの行は、互いに垂直なベクトルを表す。

この行列は、アダマール符号（あるいはその拡張としてのリード・マラー符号）による前方誤り訂正や、統計学における分散推定のための均衡反復複製(BRR)法などで直接的に用いられる。行列の名前は、フランスの数学者ジャック・アダマールにちなんでいる。

[編集] 性質

定義より、n次のアダマール行列Hは以下の性質を満たす。

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

ここでI_nはn × nの単位行列である。このことから、 $\det H =\pm n^{n/2}$ となる。

行列Mを、要素が有界で|M_ij| ≤1 (1 ≤ i, j ≤ n)であるようなn次複素行列とする。このときアダマールの不等式より、Mの行列式は以下のように有界となる。

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

実行列Mに関して、上記の不等式において等号が成り立つことと、Mがアダマール行列であることとは同値である。

アダマール行列の次数は必ず1か2、もしくは4の倍数である。

[編集] シルベスターの生成法

アマダール行列の最初の例は、ジェームス・ジョセフ・シルベスターによって1867年に作られた。n次のアダマール行列Hが与えられたとき、行列

$\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_{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 \le k \in N)$

ここで $\otimes$ はクロネッカー積を表す。

この方法で、シルベスターは任意の非負整数kについて、2^k次のアダマール行列を生成した。^[1]

シルベスターの行列は、多くの特別な性質を盛っている。これらはいずれも対称行列であり、またトレースは0である。第1列および第1行の要素はすべて正である。その他の全ての行および列において、正の要素数と負の要素数は等しい。シルベスターの行列は、ウォルシュ関数と密接に関係している。

[編集] 他の生成法

群の準同型 $\{1,-1,\times\}\mapsto \{0,1,\oplus\}$ によるアダマール行列の要素に対する写像を用いると、シルベスターによるアダマール行列を別の方法で生成することができる。まず、nビットの整数を列であるとみなし、これを昇順に並べた $n\times 2^n$ 行列 $F n$ を考える。このとき、 $F n$ は次のように再帰的に定義できる。

$F_1=\begin{bmatrix} 0 & 1\end{bmatrix}$

$F_n=\begin{bmatrix} 0_{1\times 2^{n-1}} & 1_{1\times 2^{n-1}} \\ F_{n-1} & F_{n-1} \end{bmatrix}$

帰納法により、上記の準同型写像によるアダマール行列の像は以下のようになる。

$H_{2^n}=F_n^TF_n.$

この生成法からわかることとして、アダマール行列 $H_{2^n}$ の各行が行列 $F n$ によって生成される長さ2ⁿ、ランクn、最小距離 $2 n - 1$ の線形誤り訂正符号となっている。この符号は、ウォルシュ符号とも呼ばれる。なお、アダマール符号もアダマール行列から生成されるが、若干異なる手順であるためウォルシュ符号とは異なる点に注意が必要である。

[編集] アダマールの予想

アダマール行列の理論に関する最も重要な未解決問題は、その存在性についてである。アダマール予想とは、任意の正整数kに対して4k次のアダマール行列が存在するというものである。

1867年のシルベスターによる生成法では、2^k次のアダマール行列が得られた。12次と20次のアダマール行列は、アダマールによって1893年に求められた。^[2]

その後、1933年にレイモンド・ペイリーが、4を法として3と合同であるような任意の素数冪qについて、q+1次のアダマール行列を生成する方法を示した。^[3]彼はまた、4を法として1と合同であるような素数冪qについて、2(q+1)次のアダマール行列を生成した。彼の生成法は有限体を用いたものである。アダマール予想はペイリーの業績から生じたものと考えるべきかも知れない。シルベスターとペイリーの手法を組み合わせても4k次のアダマール行列が生成できない最小の次数は92(k=13)である。92次のアダマール行列は、バウメルト、ゴロム、ホールが計算機を用いて1962年に生成した。彼らはジョン・ウイリアムソンの手法を用いて計算を行い、これはさらに多くの次数の行列を生成することにも成功した。現在では、アダマール行列を生成する多くの手法が知られている。

2004年6月21日、Hadi KharaghaniとBehruz Tayfeh-Rezaieは428次のアダマール行列を生成したと発表した。この結果、まだ生成されていないアダマール行列の最低次数は668となった。

[編集] 等価性

あるアダマール行列について行あるいは列ごとに符号を反転させる、行あるいは列を入れ替えることで別のアダマール行列が得られるとき、2つのアダマール行列は等価であるという。等価性という点では、1次、2次、4次、8次および12次のアダマール行列は一意である。16次では5種類の互いに等価でないアダマール行列が存在する。20次では3種類、24次では60種類、28次では487種類ある。32次、36次、40次では、100万を超える等価でないアダマール行列が存在する。

[編集] 歪アダマール行列

$H^T + H= 2I \$ であるようなアダマール行列Hを、歪アダマール行列と呼ぶ。

リードとブラウンは1972年に、n+1次の歪アダマール行列が存在するとき、n次の二重正則トーナメントグラフが存在することを示した。

[編集] 一般化と特殊例

数学の文献では、アダマール行列の一般化や特殊例が数多く研究されている。基本的な一般化のひとつとして、weighing matrixが挙げられる。これは要素として0を許し、一方で全ての行および列における0以外の要素が行列内で共通の定数であることを要求するものである。

他の一般化として、複素アダマール行列がある。これは各要素が絶対値1の複素数であり、かつH H^*= n I_n（H^*はHの随伴行列）を満たすような行列である。複素アダマール行列は作用素環論や量子計算理論の研究から生まれたものである。この特殊例であるバトソン型複素アダマール行列は、要素が1のq乗根である複素アダマール行列である。複素アダマール行列という用語は、いくつかの文献ではq=4の場合に限って用いられることがある。

実アダマール行列の特殊例としては、循環アダマール行列が挙げられる。これは最初の行のみ定義し、残りの行は直前の行を1つ循環シフトして得られるものである。1次と4次の循環アダマール行列は知られており、それ以外の次数では循環アダマール行列は存在しないという予想が示されている。

正則アダマール行列は、行和と列和がそれぞれ等しい実アダマール行列のことである。

[編集] 参考文献

^ J.J. Sylvester. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34:461-475, 1867
^ J. Hadamard. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246, 1893
^ R. E. A. C. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12:311–320, 1933.

H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, 2004.

S. Georgiou, C. Koukouvinos, J. Seberry, Hadamard matrices, orthogonal designs and construction algorithms, pp. 133-205 in DESIGNS 2002: Further computational and constructive design theory, Kluwer 2003.

K.B. Reid & E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combinatorial Theory A 12 (1972) 332-338.

[1] 100次までの歪アダマール行列（28次までは全ての種類を網羅）

N.J.A. Sloane's Library of Hadamard Matrices

[2] （668、716、876、892次を除く）1000次までのアダマール行列を計算するオンラインツール

R. K. Yarlagadda and J. E. Hershey, "Hadamard Matrix Analysis and Synthesis, (1996)

カテゴリ: 数学のオープンプロブレム

See also ebooksgratis.com: no banners, no cookies, totally FREE.