■いろいろの漸化式と母関数(その17)

【1】アダマール行列

 アダマール行列Hnは+1か−1の要素をもつn×n行列で,その行と列は互いに直交している.各行または列のノルム(各要素の2乗和)はnであるから,  HnHn’=Hn’Hn=nIn

が成り立つ.

  det|nIn|=n^n

より

  det|Hn|=n^n/2

 最も簡単なアダマール行列は

  H2 =[1, 1]

     [1,−1]

である.すべての他のアダマール行列はn=4kであることが必要である.

 とくに興味深いのは「直積」

  H4=H2×H2,H8=H2×H2×H2,・・・

によって,H2から得られるn=2^mのシルベスタ型のアダマール行列で,

     [1, 1, 1, 1]

  H4 =[1,−1, 1,−1]

     [1, 1,−1,−1]

     [],−1,−1, 1]

     [1, 1, 1, 1, 1, 1, 1, 1]

     [1,−1, 1,−1, 1,−1, 1,−1]

     [1, 1,−1,−1, 1, 1,−1,−1]

  H8 =[1,−1,−1, 1, 1,−1,−1, 1]

     [1, 1, 1, 1,−1,−1,−1,−1]

     [1,−1, 1,−1,−1, 1,−1, 1]

     [1, 1,−1,−1,−1,−1, 1, 1]

     [1,−1,−1, 1,−1, 1, 1,−1]

 アダマール行列は,FFT(高速フーリエ変換)の基本原理とも関係している.

===================================

【2】アダマールの定理

>

 もっと一般に,各成分が1か−1のn×n行列の行列式はn^n/2以下である.

 アダマールの定理の証明は,行列式の幾何学的意味を理解すれば簡単である.行列式の絶対値は,n個のそれぞれの長さ√nの行ベクトルが作るn次元平行六面体の体積だから,その値は(√n)^n=n^n/2以下である.等号はベクトル同士が全部直交するときに限る.

===================================

【3】もうひとつのアダマール行列

 0,+1を成分とする行列で,2つの異なる行または列を取ってくると,成分の半分は一致し,残り半分が違っている行列もアダマール行列とよばれる.

 アダマールはこのような行列が存在するのはnが2または4の倍数の場合だけであることを証明した.1933年,ベイリーはnが4の倍数で,かつ,pを奇素数として,n=2^a(p^b+1)であれば,アダマール行列は必ず存在することを証明した.

 ベイリーの定理から外れる4の倍数は,92,116,156,172,184,188,232,236,260,268などである.

 アダマール行列予想とは,nが4の倍数であればアダマール行列は必ず存在するというものである.現在発見されていない最小のアダマール行列はn=668である.

===================================