アダマール行列

数学において、アダマール行列は、フランスの数学者ジャック・アダマールにちなんで名付けられた正方行列で、要素が +1 または -1 で、行が互いに直交している。幾何学的には、アダマール行列の各行のペアが 2 つの直交 ベクトルを表すことを意味し、組合せ論的には、各行のペアがちょうど半分の列に一致する要素を持ち、残りの列には不一致の要素を持つことを意味する。この定義の結果として、対応する特性は行だけでなく列にも当てはまる。

n  ×  nアダマール行列の行によって張られるn次元平行体は、その要素の絶対値が 1 に制限されるベクトルによって張られる平行体の中で、最大の n 次元体積を持ちます。同様に、アダマール行列は、絶対値が 1 以下の要素を持つ行列の中で最大の行列式を持ち、したがって、アダマールの最大行列式問題の極値解となります。

特定のアダマール行列は、アダマール符号（リード・ミュラー符号で一般化）を使用した誤り訂正符号としてほぼ直接使用することができ、統計学者がパラメータ推定値の分散を推定するために使用する平衡反復複製（BRR）でも使用されます。

H をn 次アダマール行列とします。Hの転置行列はその逆行列と密接な関係があります。実際、 次のようになります。

${\displaystyle HH^{\textsf {T}}=nI_{n}}$

ここで、I _nはn  ×  n 単位行列、H ^{T は}Hの転置行列です。これが正しいことを確認するには、Hの行がすべて実数体上の直交ベクトルであり、それぞれの長さが であることに注目してください。 H をこの長さで割ると、転置が逆行列である直交行列が得られます。 長さを再度掛けると、上記の等式が得られます。その結果、 ${\displaystyle {\sqrt {n}}\,.}$

${\displaystyle \operatorname {det} (H)=\pm \,n^{n/2},}$

ここでdet( H )はHの行列式です。

M がn次複素行列で、 各i , j が1 からnまでの範囲で、その要素が | M _ij | ≤ 1で制限されるとする。このとき、アダマールの行列式境界は次のように表される。

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

この境界における等式は、 M がアダマール行列である 場合にのみ、実行列Mに対して達成されます。

アダマール行列の次数は1、2、または4の倍数でなければならない。^[1]

アダマール行列の例は、実は1867年にジェームズ・ジョセフ・シルベスターによって初めて構築されました。Hをn次のアダマール行列とします。すると、分割された行列

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

は 2 n次のアダマール行列です。この観察は繰り返し適用でき、ウォルシュ行列とも呼ばれる次の行列のシーケンスにつながります。

${\displaystyle {\begin{aligned}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}},\end{aligned}}}$

そして

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

において、 はクロネッカー積を表します。 ${\displaystyle 2\leq k\in N}$${\displaystyle \otimes }$

このようにして、シルベスターはすべての非負整数kに対して^2k次のアダマール行列を構築した。^[2]

シルベスター行列には、いくつかの特殊な性質があります。対称行列であり、k  ≥ 1 (2 ^k  > 1)のときトレースゼロを持ちます。 最初の列と最初の行の要素はすべて正です。 他のすべての行と列の要素は、正と負の間で均等に分割されます。 シルベスター行列は、ウォルシュ関数と密接に関係しています。

アダマール行列の要素を群準同型 を使って写像すると、シルベスターのアダマール行列の別の構成を記述することができます。まず、すべてのnビットの数値が昇順に並べられた列で構成される行列を考えます。次のように再帰的に 定義できます。${\displaystyle (\{1,-1\},\times )\mapsto (\{0,1\}),\oplus \}}$${\displaystyle F_{n}}$${\displaystyle n\times 2^{n}}$${\displaystyle F_{n}}$

${\displaystyle {\begin{aligned}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}}.\end{aligned}}}$

帰納法によって、上記の準同型によるアダマール行列の像は次のように 表される。

${\displaystyle H_{2^{n}}=F_{n}^{\textsf {T}}F_{n}.}$

この構成は、アダマール行列の行がランクnの長さの線形誤り訂正符号とみなすことができ、生成行列との最小距離が${\displaystyle H_{2^{n}}}$${\displaystyle 2^{n}}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle F_{n}.}$

このコードはウォルシュ コードとも呼ばれます。対照的に、アダマール コードは、わずかに異なる手順で アダマール行列から構築されます。${\displaystyle H_{2^{n}}}$

アダマール行列の理論における最も重要な未解決問題は存在の問題である。具体的には、アダマール予想は、すべての正の整数kに対して 4 kの位数のアダマール行列が存在することを提案している。アダマール予想はペイリーの業績とされているが、ペイリーの研究以前にも暗黙のうちに他の人によって考えられていた。^[3]

シルベスターの構成の一般化により、と がそれぞれn 次とm 次のアダマール行列である場合、 はnm次アダマール行列であることが証明されます。この結果は、より小さい次数のアダマール行列がわかれば、より高次のアダマール行列を生成するために使用されます。 ${\displaystyle H_{n}}$${\displaystyle H_{m}}$${\displaystyle H_{n}\otimes H_{m}}$

シルベスターの1867年の構築では、1、2、4、8、16、32次のアダマール行列が生成されます。12次と20次のアダマール行列は、その後アダマールによって構築されました（1893年）。^[4] 1933年、レイモンド・ペイリーはペイリー構築を発見しました。これは、 qが4を法として3に合同な任意の素数累乗のときにq + 1次のアダマール行列を生成し、 qが4を法として1に合同な素数累乗のときに2( q + 1)次のアダマール行列を生成します。 ^[5]彼の方法は有限体を使用します。

シルベスター法とペイリー法を組み合わせても構築できない最小の次数は92である。この次数のアダマール行列は、 1962年にJPLでバウマート、ゴロム、ホールがコンピュータを使用して発見した。^[6]彼らはウィリアムソンによる構築法^[7]を使用し、これにより多くの追加の次数が得られた。アダマール行列を構築するための他の多くの方法が現在知られている。

2005年、ハディ・カラガニとベフルズ・タイフェ・レザイエは、428次のアダマール行列の構築を発表しました。^[8]その結果、現在知られているアダマール行列の最小次数は668となりました。

2014年までに、2000未満の4の倍数で、その位数のアダマール行列が知られていないものが12個ありました。^[9]これらは、668、716、892、1132、1244、1388、1436、1676、1772、1916、1948、1964です。

2 つのアダマール行列は、行または列を反転するか、行または列を交換することで一方が他方から得られる場合、同等であるとみなされます。同等性まで、次数 1、2、4、8、および 12 のアダマール行列は 1 つしかありません。次数 16 の非同等行列は 5 つ、次数 20 の非同等行列は 3 つ、次数 24 の非同等行列は 60 つ、次数 28 の非同等行列は 487 つあります。次数 32、36、および 40 の非同等行列は数百万個知られています。転置も許可するより粗い同等性の概念を使用すると、次数 16 の非同等行列は 4 つ、次数 20 の非同等行列は 3 つ、次数 24 の非同等行列は 36 つ、次数 28 の非同等行列は 294 個あります。^[10]

アダマール行列は、次の意味で一意に復元可能です。 次数のアダマール行列 からランダムに削除された要素がある場合、圧倒的な確率で、破損した行列から元の行列を完全に復元できます。復元アルゴリズムの計算コストは​​、行列の逆変換と同じです。^[11]${\displaystyle H}$${\displaystyle n}$${\displaystyle O(n^{2}/\log n)}$${\displaystyle H}$

アダマール行列の多くの特殊なケースが数学文献で研究されてきました。

アダマール行列Hが歪んでいるとは、 歪んだアダマール行列が、任意の行とそれに対応する列に -1 を掛けた後も歪んだアダマール行列のままである場合です。これにより、たとえば、歪んだアダマール行列を正規化して、最初の行のすべての要素が 1 になるようにすることができます。 ${\displaystyle H^{\textsf {T}}+H=2I.}$

1972 年に Reid と Brown は、次数nの二重正則トーナメントが存在するのは、次数n + 1の歪んだアダマール行列が存在する場合のみであることを示しました。次数n の数学的トーナメントでは、n 人のプレーヤーのそれぞれが他のプレーヤーのそれぞれと 1 試合ずつプレイし、各試合でプレーヤーの 1 人が勝ち、もう 1 人が負けます。各プレーヤーが同じ数の試合に勝つ場合、トーナメントは正則です。正則トーナメントは、2 つの異なるプレーヤーの両方が負けた対戦相手の数が、すべての異なるプレーヤーのペアで同じである場合、二重正則です。プレイされたn ( n − 1)/2 試合のそれぞれでプレーヤーの 1 人が勝つため、各プレーヤーは ( n − 1)/2 試合に勝ちます (そして同じ数の試合に負けます)。特定のプレイヤーに負けた( n − 1)/2 人のプレイヤーはそれぞれ、他の ( n − 3)/2 人のプレイヤーにも負けるので、 j がiと特定のプレイヤーの両方に負けるプレイヤーのペア ( i、j  )の数は ( n − 1)( n − 3)/4 です。ペアの数え方が異なっていても、同じ結果が得られます。つまり、特定のプレイヤーと他のn − 1 人のプレイヤーのいずれかが、一緒に同じ数の共通の対戦相手を倒します。したがって、この共通の敗北した対戦相手の数は ( n − 3)/4 でなければなりません。歪んだアダマール行列は、元のプレイヤー全員を倒した追加のプレイヤーを導入し、 i = j または i が j に勝った場合は行i、列jに 1 が含まれ、jがiに勝った場合は -1 が含まれるという規則に従って、プレイヤー名が行と列にラベル付けされた行列を形成することによって 得 られます。この対応を逆にすると、歪んだアダマール行列が正規化されて最初の行のすべての要素が1になっていると仮定すると、歪んだアダマール行列から二重正則トーナメントが生成されます。^[12]

正則アダマール行列は、行と列の合計がすべて等しい実アダマール行列です。正則n  ×  nアダマール行列が存在するための必要条件は、 n が平方数であることです。巡回行列は明らかに正則であるため、巡回アダマール行列は平方数である必要があります。さらに、n  ×  n巡回アダマール行列がn > 1で存在する場合、 n は必然的に 4 u ²の形式でuが奇数である必要があります。^{[13] [14]}

しかし、巡回アダマール行列予想は、既知の1×1と4×4の例を除いて、そのような行列は存在しないと主張している。これは、uが¹⁰⁴未満の26の値を除くすべての値で検証された。^[15]

基本的な一般化の一つは重み付け行列である。重み付け行列は、要素がゼロになることもあり、あるwに対して重みを満たす正方行列である。重みがその次数に等しい重み付け行列はアダマール行列である。^[16]${\displaystyle WW^{\textsf {T}}=wI}$

別の一般化では、複素アダマール行列は、要素が単位係数の複素数であり、HH ^* = n I _nを満たす行列であると定義されます。ここで、H ^*はHの共役転置です。複素アダマール行列は、作用素代数の研究や量子計算の理論で登場します。 バトソン型アダマール行列は、要素が^1のq乗根である複素アダマール行列です。複素アダマール行列という用語は、q = 4の場合を特に指して使用する著者もいます。

• Olivia MFSK – 短波帯の困難な状況 (信号対雑音比が低く、マルチパス伝播がある) で動作するように設計されたアマチュア無線のデジタル プロトコル。
• 平衡反復複製(BRR) – 統計学者が統計推定値の分散を推定するために使用する手法。
• 符号化開口分光計 –光のスペクトルを測定するための機器。符号化開口分光計で使用されるマスク要素は、多くの場合、アダマール行列の変形です。
• フィードバック遅延ネットワーク – アダマール行列を使用してサンプル値をブレンドするデジタル残響装置
• 測定された量がいくつかの独立変数にどのように依存しているかを調査するためのプラケット・バーマン実験計画法。
• ノイズ要因が応答に与える影響を調査するための堅牢なパラメータ設計
• 信号処理と劣決定線形システム（逆問題）のための圧縮センシング
• 量子コンピューティングのための量子アダマール ゲートと量子アルゴリズムのためのアダマール変換。

• 組み合わせ設計
• アダマール変換
• 五点形マトリックス
• ウォルシュ行列
• 計量マトリックス
• 量子論理ゲート

• Baumert, LD; Hall, Marshall (1965). 「ウィリアムソン型のアダマール行列」. Math. Comp . 19 (91): 442–447. doi : 10.1090/S0025-5718-1965-0179093-2 . MR  0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). 「アダマール行列、直交設計、構築アルゴリズム」。Designs 2002: さらなる計算および構築設計理論。ボストン: Kluwer。pp. 133–205。ISBN 978-1-4020-7599-5。
• Goethals, JM; Seidel, JJ (1970). 「36 次歪アダマール行列」. J. Austral. Math. Soc . 11 (3): 343–344. doi :10.1017/S144678870000673X. S2CID  14193297.
• 木村 宏 (1989). 「24次の新しいアダマール行列」.グラフと組合せ論. 5 (1): 235–242. doi :10.1007/BF01788676. S2CID  39169723.
• ムード、アレクサンダー M. (1964)。「ホテリングの計量問題について」。数理統計年報。17 ( 4): 432–446。doi : 10.1214/aoms/1177730883。
• Reid, KB; Brown, E. (1972). 「二重正則トーナメントは歪んだアダマール行列と同等である」J. Combin. Theory Ser. A . 12 (3): 332–338. doi : 10.1016/0097-3165(72)90098-2 .
• Seberry Wallis, Jennifer (1976). 「アダマール行列の存在について」J. Comb. Theory A . 21 (2): 188–195. doi : 10.1016/0097-3165(76)90062-5 .
• Seberry, Jennifer (1980). 「一般化アダマール行列の構築」J. Statist. Plann. Infer . 4 (4): 365–368. doi :10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005). 「アダマール行列のいくつかの応用について」Metrika . 62 (2–3): 221–239. doi :10.1007/s00184-005-0415-y. S2CID  40646.
• スペンス、エドワード(1995)。「次数24および28のアダマール行列の分類」。離散数学。140 (1–3): 185–242。doi : 10.1016/0012-365X(93)E0169-5。
• Yarlagadda, RK; Hershey, JE (1997).アダマール行列の解析と合成. ボストン: Kluwer. ISBN 978-0-7923-9826-4。

• 28 までのすべてのタイプを含む、100 までのすべての次数の歪んだアダマール行列。
• 「アダマール行列」。OEISで
• NJAスローン。 「アダマール行列のライブラリ」。
• 668、716、876、892 を除く 1000 までのすべての注文を取得するためのオンライン ユーティリティ。
• R を使用してアダマール行列を生成する R パッケージ
• JPL: 1961年、NASAのジェット推進研究所とカリフォルニア工科大学の数学者が協力して、92行9列のアダマール行列を構築しました。