アダマールの最大行列式問題

ジャック・アダマールにちなんで名付けられたアダマールの最大行列式問題は、要素が 1 または −1 である行列の最大の行列式を求める問題です。要素が 0 または 1 である行列に対する類似の問題は、以下に示すように、サイズnの {1,−1} 行列の最大行列式は、サイズn −1の {0,1} 行列の最大行列式の2 ^{n −1}倍であるため、同等です。この問題は、アダマールが 1893 年の論文^[1]で提起したもので、彼は有名な行列式境界を提示しましたが、一般的なサイズの行列については未解決のままです。アダマールの境界は、サイズnの {1, −1} 行列の行列式が最大でn ^{n /2}であることを意味します。アダマールは、シルベスター^[2]の構成により、nが2の累乗のときに 境界に達する行列の例が生成されることに注目し、サイズが12と20の独自の例を作成しました。また、境界はnが1、2、または4の倍数の場合にのみ達成可能であることも示しました。その後、スカルピスとペイリーによって追加の例が構築され、その後多くの他の著者によっても構築されました。このような行列は現在、アダマール行列として知られています。これらは集中的に研究されています。

n  ≡ 1、2、または 3 (mod 4)の行列サイズn はあまり注目されていません。最も初期の結果は、 n が奇数の場合のアダマールの境界を強化した Barba と、 n =3、5、6、および 7 の場合の最大行列式を発見した Williamsonによるものです。重要な結果には以下が含まれます。

• バルバ、エーリッヒ、ヴォイタスによる、n  ≡ 1、2、または 3 (mod 4) に対するより厳しい境界が、しかしながら、常に達成できるわけではないことが知られている。
• n  ≡ 1 または 2 (mod 4)の境界に達する行列の無限列がいくつかある。
• 特定のn≡1 または2（mod 4）の境界を満たす行列の数、
• 特定のn  ≡ 1 または 3 (mod 4) の境界には達しないが、徹底的な計算によって最大の行列式を持つことが証明された行列の数。

統計学における実験計画法では、情報行列X ^T Xが最大の行列式を持つ{1, −1}行列X（必ずしも正方行列ではない）を使用する。（表記法X ^TはXの転置を表す。）このような行列はD最適計画と呼ばれる。^[3] Xが正方行列の 場合、飽和D最適計画と呼ばれる。

n × nアダマール行列の任意の 2 行は直交します。{1, −1} 行列の場合、任意の 2 行の要素がちょうど半分だけ異なることを意味しますが、これはnが奇数のときは不可能です。n ≡ 2 (mod 4)のとき 、3 番目の行に直交する 2 つの行は、互いに直交することはできません。これらのステートメントを合わせると、n × nアダマール行列は、 n  = 1、2、または 4 の倍数の場合にのみ存在できます。アダマール行列は十分に研究されていますが、4 の正の倍数であるすべてのnに対してn × nアダマール行列が存在するかどうかはわかっていません。n × nアダマール行列が存在しないことが知られている最小のnは668 です。

以下のいずれかの演算を{1, −1}行列Rに対して実行すると、 Rの行列式はマイナス符号だけ変化します。

• 行の否定。
• 列の否定。
• 2 行の交換。
• 2 つの列の交換。

2 つの {1,−1} 行列R ₁とR ₂は、上記の操作をいくつか実行することでR _{1 を}R ₂に変換できる場合、同等であると見なされます。同等の行列の行列式は、符号の変更を除いて等しく、行と列の反転と順列置換によってR を標準化すると便利な場合がよくあります。{1, −1} 行列は、最初の行と列のすべての要素が 1 に等しい場合に正規化されます。行列のサイズが奇数の場合、すべての行と列に偶数個の要素 1 と奇数個の要素 -1 が含まれる別の正規化を使用すると便利な場合があります。これらの正規化はどちらも、最初の 2 つの操作を使用して実行できます。

正規化されたn × n {1, −1}行列の集合から( n −1)×( n -1){0, 1}行列の集合への1対1の写像があり、その場合、行列式の大きさは21 ^{− n}倍に減少する。この写像は次の手順で構成される。

1. {1, −1} 行列の行 1 を行 2 から行nまでから減算します。(これによって行列式は変化しません。)
2. 行 2 からn、列 2 からnで構成される( n −1)×( n −1) サブ行列を抽出します。この行列には、要素 0 と -2 があります。(このサブ行列の行列式は、手順 1 で取得した行列の列 1 に対してコファクター展開を実行するとわかるように、元の行列の行列式と同じです。)
3. 部分行列を−2で割って{0, 1}行列を得る。（これにより行列式に（−2）^{1− n}が掛けられる。）

例：

${\displaystyle {\begin{bmatrix}1&1&1&1\\1&-1&-1&1\\1&1&-1&-1\\1&-1&-1\\1&-1&-1\end{bmatrix}}\rightarrow \left[{\begin{array}{c|ccc}1&1&1&1\\\hline 0&-2&-2&0\\0&0&-2&-2\\0&-2&0&-2\end{array}}\right]\rightarrow {\begin{bmatrix}-2&-2&0\\0&-2&-2\\-2&0&-2\end{bmatrix}}\rightarrow {\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix}}}$

この例では、元の行列の行列式は−16で、その像の行列式は2 = −16·(−2) ⁻³です。

{0, 1}行列の行列式は整数なので、n × n {1, −1}行列の行列式は2 ^{n −1}の整数倍になります。

Rをn行n列{1, −1}の行列とする。Rのグラム行列は行列G  =  RR ^Tと定義される。この定義から、Gは

1. は整数行列であり、
2. 対称的である、
3. は半正定値であり、
4. 値がnに等しい定数対角線を持ちます。

Rの行を反転するか、それらに置換を適用すると、同じ反転と置換がGの行と対応する列の両方に適用されます。行列G ′= R ^T Rを定義することもできます。行列Gは、 Rの行の集合から派生したベクトルの集合の通常のグラム行列であり、G ′ は、 Rの列の集合から派生したグラム行列です。 G  =  G ′となる行列Rは、正規行列です。既知の最大行列式行列はすべて正規行列と同等ですが、常にそうであるかどうかはわかっていません。

アダマールの境界は、|det  R | = (det  G ) ^1/2  ≤ (det  nI ) ^1/2  =  n ^{n /2}であることに注目することで導くことができます。これは、 nI （ここでIはnバイn 単位行列）が、特性 1 ～ 4 を満たす行列の中で最大の行列式の唯一の行列であるという観察の結果です。 det  R は2 ^{n −1}の整数倍でなければならないということは、アダマールの境界が常に達成できるわけではないことを別の方法で証明するために使用できます。nが奇数のとき、境界n ^{n /2}は非整数または奇数であり、したがってn = 1 のときを除いて達成できません。 n  = 2 kでkが奇数の とき、アダマールの境界を割り切る 2 の最大のべき乗は 2 ^kであり、 n = 2でない限り2 ^{n −1}より小さくなります。したがって、アダマールの境界はn  = 1、2、または 4 の倍数で  ない限り達成できません。

nが奇数のとき、グラム行列の特性1は次のように強化される。

1. G は奇数整数行列です。

これにより、より明確な上限^[4]を導くことができます: |det  R | = (det  G ) ^1/2  ≤ (det ( n -1) I + J ) ^1/2  = (2 n −1) ^1/2 ( n −1) ^{( n −1)/2}、ここでJ はすべて 1 の行列です。ここで ( n -1) I + Jは、修正された特性 1 と特性 2 ～ 4 を満たす最大行列式行列です。これは、任意の行セットとそれに対応する列セットに -1 を乗じるまで一意です。この上限は、2 n −1 が完全な平方数でない限り達成できず、したがってn  ≡ 3 (mod 4) のときは決して達成できません。

nが偶数の場合、 Rの行の集合は2 つのサブセットに分割できます。

• 偶数型の行には、偶数個の要素 1 と偶数個の要素 -1 が含まれます。
• 奇数型の行には、奇数の要素 1 と奇数の要素 -1 が含まれます。

同じタイプの2つの行のドット積はn（mod 4）に合同です。反対のタイプの2つの行のドット積はn +2（mod 4）に合同です。n ≡ 2（mod 4）のとき、 これは、Rの行を並べ替えることで、標準形式を想定できることを意味します。

${\displaystyle G={\begin{bmatrix}A&B\\B^{\mathrm {T} }&D\end{bmatrix}},}$

ここで、AとD は対称整数行列で、その要素は 2 (mod 4) に合同であり、Bは 0 (mod 4) に合同である。1964 年に、Ehlich ^[5]と Wojtas ^[6]は独立に、この形式の最大行列式行列において、AとD は両方ともサイズn /2 で ( n −2) I +2 Jに等しく、 B はゼロ行列であることを示した。この最適形式は、任意の行セットと対応する列セットを −1 で乗算し、行と列に同時に置換を適用するまで一意である。これは、境界 det  R  ≤ (2 n −2)( n −2) ^{( n −2)/2}を意味する。Ehlich は、R が境界に達し、 Rの行と列が置換されてG  =  RR ^TとG ′ =  R ^T Rの両方が標準形式を持ち、適切に正規化されている場合、次のように書けることを 示した。

${\displaystyle R={\begin{bmatrix}W&X\\Y&Z\end{bmatrix}}}$

ここで、W、X、Y、Zは、z  = − w、y  =  x 、およびw 2 + ^{x 2}  = 2 n −2を満たす、行と列の合計w、x、y、zが定数である( n / 2)×( n / 2) 行列です。したがって、 2 n −2 が 2 つの平方の和として表されない 限り、エーリッヒ–ヴォイタスの境界は達成できません。

nが奇数のとき、行を−1倍する自由度を利用して、Rの各行に偶数個の要素1と奇数個の要素−1が含まれるという条件を課すことができる。この正規化を仮定すると、 Gの特性1は次のように強化されること がわかる。

1. G はn (mod 4)に合同な整数要素を持つ行列です。

n ≡ 1 (mod 4)のとき 、Barba の最適形式はこのより強い性質を満たすが、n  ≡ 3 (mod 4) のときは満たさない。これは、後者の場合、境界を鋭くすることができることを意味する。Ehlich ^{[7] は、} n ≡ 3 (mod 4)のとき 、強化された性質 1 は、Gの最大行列式形式がB − Jと書けることを示している。ここで、Jはオールワン行列であり、Bは対角ブロックが( n -3) I +4 J の形式であるブロック対角行列である。さらに、彼は、最適形式では、ブロックの数sが下の表に示すようにnに依存し、各ブロックのサイズはrまたはr+1のいずれかであることを示した。${\displaystyle r=\lfloor n/s\rfloor .}$

n =11の場合には2つの可能性があるが、任意の行の集合とそれに対応する列の集合を-1倍し、行と列に同時に順列を適用するまで、最適形式は一意である。この最適形式から、次の境界が得られる。

${\displaystyle \det R\leq (n-3)^{(ns)/2}(n-3+4r)^{u/2}(n+1+4r)^{v/2}\left[1-{\frac {ur}{n-3+4r}}-{\frac {v(r+1)}{n+1+4r}}\right]^{1/2},}$

ここで、v  =  n − rsはサイズr +1のブロックの数、 u  = s − v はサイズrのブロックの数です。Cohn ^{[8] は、この境界を分析し、} n  = 3を除けば、正の整数tに対してn  = 112 t ² ±28 t +7 の場合にのみ整数になることを決定しました。Tamura ^{[9] は、二次形式の有理同値性に関する}ハッセ-ミンコフスキーの定理を使用して、境界の達成可能性に関する追加の制限を導出し、エーリッヒの境界が達成可能であると考えられる最小のn  > 3 は 511 であることを示しました。

サイズn = 21までの{1, −1}行列の最大行列式を 次の表に示す。^[10] サイズ22は最小のオープンケースである。表では、D ( n )は最大行列式を^{2n −1}で割ったものを表す。同様に、D ( n )はサイズn −1の{0, 1}行列の最大行列式を表す。