アダマール行列のソースを表示

'''アダマール行列'''（アダマールぎょうれつ、{{lang-en-short|Hadamard matrix}}）とは、要素が {{math|1}} または {{math|&minus;1}} のいずれかであり、かつ各行が互いに[[直交]]である[[正方行列]]である。すなわち、アダマール行列の任意の2つの行は、互いに[[垂直]]な[[空間ベクトル|ベクトル]]を表す。

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

== 性質 ==
定義より、{{mvar|n}}次のアダマール行列 {{mathbf|''H''}} は以下の性質を満たす。
:<math>\boldsymbol{H}^\intercal \boldsymbol{H} = n \boldsymbol{I}_n</math>
ここで {{math|'''I'''{{sub|''n''}}}} は {{mvar|n}}次単位行列である。このことから、<math>\det \boldsymbol{H} =\pm n^{n/2}</math> となる。

行列 {{mvar|M}} を、要素が有界で {{math2|{{abs|'''''M'''{{sub|ij}}''}} ≤ 1 (1 ≤ ''i'', ''j'' ≤ ''n'')}} である {{mvar|n}}次複素行列とする。このときアダマールの不等式より、'''''M'''''の行列式は以下のように有界となる。
:<math>|\operatorname{det}(\boldsymbol{M})| \leq n^{n/2}</math>
実行列 {{mathbf|''M''}} に関して、上記の不等式において等号が成り立つことと、{{mathbf|''M''}} がアダマール行列であることとは同値である。

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

== シルベスターの生成法 ==
アマダール行列の最初の例は、[[ジェームス・ジョセフ・シルベスター]]によって[[1867年]]に作られた。{{mvar|n}}次のアダマール行列 {{mvar|H}} が与えられたとき、行列
:<math>\begin{bmatrix}
H &H \\
H &-H
\end{bmatrix}</math> 
は {{math2|2''n''}}次のアダマール行列となる。この結果は繰り返し適用できるため、以下のような行列の[[列 (数学)|列]]が導かれる（この列は[[ウォルシュ行列]]とも呼ばれる）。
:<math>\begin{align}
\boldsymbol{H}_1 &= \begin{bmatrix}
  1
\end{bmatrix} \\
\boldsymbol{H}_2 &= \begin{bmatrix}
  1 &1  \\
  1 &-1
\end{bmatrix} \\
\boldsymbol{H}_4 &= \begin{bmatrix}
  1 &1  &1  &1  \\
  1 &-1 &1  &-1 \\
  1 &1  &-1 &-1 \\
  1 &-1 &-1 &1
\end{bmatrix} \\
\boldsymbol{H}_{2^k} &= \begin{bmatrix}
  \boldsymbol{H}_{2^{k-1}} &\boldsymbol{H}_{2^{k-1}} \\
  \boldsymbol{H}_{2^{k-1}} &-\boldsymbol{H}_{2^{k-1}}
\end{bmatrix} = \boldsymbol{H}_2 \otimes \boldsymbol{H}_{2^{k-1}} \quad (2 \le k \in \mathbb{N})
\end{align}</math>
ここで <math>\otimes</math> は[[クロネッカー積]]を表す。

この方法で、シルベスターは任意の非負整数 {{mvar|k}} について、{{math|2{{sup|''k''}}}}次のアダマール行列を生成した<ref>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</ref>。

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

== 他の生成法 ==
[[群 (数学)#群の準同型・同型|群の準同型]] <math>\{1,-1,\times\} \mapsto \{0,1,\oplus\}</math> によるアダマール行列の要素に対する写像を用いると、シルベスターによるアダマール行列を別の方法で生成することができる。まず、''n''ビットの整数を列であるとみなし、これを昇順に並べた <math>n\times 2^n</math>行列<math>\boldsymbol{F}_n</math> を考える。このとき、<math>\boldsymbol{F}_n</math> は次のように再帰的に定義できる。
:<math>\boldsymbol{F}_1 = \begin{bmatrix}
0 &1
\end{bmatrix}</math>
:<math>\boldsymbol{F}_n = \begin{bmatrix}
0_{1\times 2^{n-1}}  &1_{1\times 2^{n-1}} \\
\boldsymbol{F}_{n-1} &\boldsymbol{F}_{n-1}
\end{bmatrix}</math>
帰納法により、上記の準同型写像によるアダマール行列の像は以下のようになる。
:<math>\boldsymbol{H}_{2^n} = \boldsymbol{F}_n^\intercal \boldsymbol{F}_n.</math>
この生成法から分かることとして、アダマール行列 <math>\boldsymbol{H}_{2^n}</math> の各行が行列<math>\boldsymbol{F}_n</math> によって生成される長さ 2{{sup|''n''}}、ランク''n''、最小距離 <math>2^{n-1}</math> の[[線形符号|線形誤り訂正符号]]となっている。この符号は、[[ウォルシュ符号]]とも呼ばれる。なお、アダマール符号もアダマール行列から生成されるが、若干異なる手順であるためウォルシュ符号とは異なる点に注意が必要である。

[[MATLAB]]ではhadamard(n)で<math>n \times n</math>のアダマール行列を生成できる

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

1867年のシルベスターによる生成法では、{{math|2{{sup|''k''}}}}次のアダマール行列が得られた。12次と20次のアダマール行列は、アダマールによって1893年に求められた。<ref>J. Hadamard. ''Résolution d'une question relative aux déterminants.'' Bulletin des Sciences Mathématiques, 17:240-246, 1893</ref>

その後、1933年にレイモンド・ペイリーが、4を法として3と[[合同式|合同]]であるような任意の[[素数]][[冪乗|冪]] {{mvar|q}} について、{{math|''q'' + 1}}次のアダマール行列を生成する方法を示した<ref>R. E. A. C. Paley. ''On orthogonal matrices.'' Journal of Mathematics and Physics, 12:311–320, 1933.</ref>。彼はまた、4を法として1と合同である素数冪 {{mvar|q}} について、{{math2|2(''q'' + 1)}}次のアダマール行列を生成した。彼の生成法は[[有限体]]を用いたものである。アダマール予想はペイリーの業績から生じたものと考えるべきかも知れない。シルベスターとペイリーの手法を組み合わせても {{math|4''k''}}次のアダマール行列が生成できない最小の次数は {{math2|92 (''k'' {{=}} 23)}} である。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万を超える等価でないアダマール行列が存在する。

== 歪アダマール行列 ==
<math>\boldsymbol{H}^\intercal + \boldsymbol{H} = 2\boldsymbol{I}</math> であるアダマール行列'''''H'''''を、歪アダマール行列と呼ぶ。

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

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

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

実アダマール行列の特殊例としては、循環アダマール行列が挙げられる。これは最初の行のみ定義し、残りの行は直前の行を1つ[[ビット演算#(キャリーなし)ローテート|循環シフト]]して得られるものである。1次と4次の循環アダマール行列は知られており、それ以外の次数では循環アダマール行列は存在しないという[[予想 (数学)|予想]]が示されている。

正則アダマール行列は、行和と列和がそれぞれ等しい実アダマール行列のことである。<!--
 
== Practical applications ==
* [[Olivia MFSK]] - an amateur-radio digital protocol designed to work in difficult (low signal-to-noise ratio plus multipath propagation) conditions on shortwave bands.
* Balanced Repeated Replication (BRR) - a technique used by statisticians to estimate the [[variance]] of a [[statistical estimator]]. 
:The BRR variance estimate is found in the following way. First, the estimate is computed using the entire sample. Call this the "full-sample" estimate. Next, many subsamples are taken, each one chosen in a special way. Each of these subsamples will represent about half of the full-sample, so are called "half-samples." Since these half-samples are sampled multiple times, they are also commonly called "replicates."
:The collection of half-samples is not chosen haphazardly, but rather are designed so that they form a "balanced" set of half-samples. Hadamard matrices are used to find the balance. The ideal situation is to have a sample design where there is one-stage of selection, the sampling frame is broken into a collection of sampling strata, and within each stratum, only two primary sampling units (PSUs) are selected. In this circumstance, a half-sample is formed by selecting one PSU from each stratum. Within each stratum, label the PSUs 1 and 2. To gain balance, we use a (square) Hadamard matrix with <I>at least</I> one column per stratum. The rows will represent replicates. If the entry in row <I>r</I> and column <I>h</I> is 1, then we pick PSU 1. If the entry is -1, we pick PSU 2. 
:Because Hadamard matrices are pairwise orthogonal (vector [[dot product]]s are zero), the net result is this: for any two pairs of strata, the number of half-samples where the ''same'' PSU number is chosen for both strata, will be equal to the number of half-samples where ''different'' PSU numbers are chosen between the two strata. Such a collection of half-samples is called "balanced." A stronger situation is when the collection is "fully balanced." This occurs whenever all column sums of the matrix are zero, which means that for any stratum, the number of half-samples where PSU 1 is chosen equals the number of those where PSU 2 is chosen. Full-balance is not necessary, nor always possible, but if it exists, it "enhances" the balance.
:The above situation described the ideal case (full sample = two units sampled per sampling stratum). In reality, often many units are sampled per sampling stratum. In these situations, within each stratum we must define two objects called "variance PSUs" (labeled 1 and 2), where each will contain about half the sampled units in the stratum. This is done randomly, or semi-randomly. If a systematic sample was used, the assignment of units to variance PSUs is usually done by first sorting the sample, similar to how the frame was sorted before it was sampled. Then, the first unit is randomly assigned to PSU 1 or 2. The rest are then assigned, in an alternating fashion, as one moves through the sorted list. In some situations, the number of strata is so large that this affects the efficiency of BRR, in such cases one solution is to collapse the sampling strata together to form new objects, called "variance strata." Another complication occurs if there are several stages of sampling. Unfortunately, BRR will not capture the variance from these other sampling stages, and only captures the variance from the first stage (the between-PSU variance). One final twist is when the multi-stage sample design has "certainty PSUs" (these are in ''all'' first-stage samples, that is, they are sampled with "certainty"). In these situations, for the certainty PSUs ''only'', we usually drop down to the stage-two sample, and for BRR we now let variance strata equal stage-two sampling strata, and variance PSUs be made up of stage-two sampling units (secondary sampling units or SSUs). If there are (conditional) stage two certainties, we subdivide further (to TSUs), and so on. Often, to increase efficiency, the strata at these lower levels are collapsed, often to the PSU, and the PSU is now the the variance stratum.
:For each replicate, a new estimate must be computed, called the "half-sample estimate" or sometimes the "replicate estimate." In BRR's most generic form (called Fay's method of BRR), the units in the full-sample yet not in the half-sample will have their weights deflated, and the units in the half-sample will have their weights inflated. The deflation is accomplished by multiplying the weight by factor <I>k</I> (called the Fay factor) and inflation by a factor (2-<I>k</I>), where 0 <= <I>k</I> < 1. The most common form of BRR is to let <I>k</I> = 0.
:The BRR variance estimate is found in two steps. First, we find the average, over all replicates, of the squared difference of the replicate estimate from the full-sample estimate. Second, we divide this value by the square of (1-<I>k</I>).-->

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* H. Kharaghani and B. Tayfeh-Rezaie, [http://math.ipm.ac.ir/tayfeh-r/papersandpreprints/h428.pdf ''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.
*[http://rangevoting.org/SkewHad.html] 100次までの歪アダマール行列（28次までは全ての種類を網羅）
*[http://neilsloane.com/hadamard/ N.J.A. Sloane's Library of Hadamard Matrices]
*[http://www.iasri.res.in/webhadamard] （668、716、876、892次を除く）1000次までのアダマール行列を計算するオンラインツール
*R. K. Yarlagadda and J. E. Hershey, ''"Hadamard Matrix Analysis and Synthesis'', (1996)  

== 外部リンク ==
* {{高校数学の美しい物語|1382|アダマール行列の定義と性質}}

{{DEFAULTSORT:あたまあるきようれつ}}
[[Category:予想]]
[[Category:行列]]
[[Category:ジャック・アダマール]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]