ペイリー構造

数学において、ペイリー構成は有限体を使用してアダマール行列を構成する方法であり、1933 年にイギリスの数学者レイモンド・ペイリーによって記述されました。

Paley 構成は、有限体 GF( q )の平方剰余を使用します。ここで、 q は奇数の素数の累乗です。q が4 を法として 1 と合同か 3 と合同かによって、構成には 2 つのバージョンがあります。

q を奇数素数のべき乗とする。有限体 GF( q ) において、二次関数の文字χ( a ) は、元aがゼロか、ゼロでない平方数か、平方数でない数かを示す。

${\displaystyle \chi (a)={\begin{cases}0&{\text{if }}a=0\\1&{\text{if }}a=b^{2}{\text{ \mathrm {GF} (q)\\-1 内の 0 でない }}b\ に対して&{\text{if }}a{\text{ が }}\mathrm {GF} (q) 内のどの要素の平方でもない場合。\end{cases}}}$

たとえば、GF(7) では、非ゼロ平方は 1 = 1 ² = 6 ²、4 = 2 ² = 5 ²、および 2 = 3 ² = 4 ²です。したがって、χ(0) = 0、χ(1) = χ(2) = χ(4) = 1、χ(3) = χ(5) = χ(6) = −1 となります。

GF( q )のヤコブスター行列Qは、行と列がGF( q )の要素でインデックス付けされ、行aと列bの要素がχ( a  −  b )であるq  ×  q行列です。たとえば、GF(7)では、ヤコブスター行列の行と列が体要素0、1、2、3、4、5、6でインデックス付けされている場合、

${\displaystyle Q={\begin{bmatrix}0&-1&-1&1&-1&1&1\\1&0&-1&-1&1&-1&1\\1&1&0&-1&-1&1&-1\\-1&1&1&0&-1&-1&1\\1&-1&1&1&0&-1&-1\\-1&1&-1&1&1&0&-1\\-1&-1&1&-1&1&1&0\end{bmatrix}}.}$

ヤコブスタール行列は、 QQ ^T = qI  −  JおよびQJ = JQ = 0という特性を持ちます。ここで、 Iはq  ×  q 単位行列、Jはq  ×  q すべて 1 の行列です。qが1 mod 4 に合同である場合、−1 は GF( q )の正方行列であり、 Qは対称行列であることを意味します。q が 3 mod 4 に合同である場合、 −1 は正方行列ではなく、Q は歪対称行列です。qが素数で、行と列が通常の 0、1、2、… の順序で体元によってインデックス付けされている場合、 Q は巡回行列です。つまり、各行は巡回置換によって上の行から取得されます。

qが3 mod 4に一致する 場合

${\displaystyle H=I+{\begin{bmatrix}0&j^{T}\\-j&Q\end{bmatrix}}}$

は、サイズq  + 1のアダマール行列です。ここで、 j は長さqのすべての 1 の列ベクトルであり、I は( q +1)×( q +1) 単位行列です。行列Hは歪んだアダマール行列であり、H + H ^T  = 2 Iを満たします。

qが1 mod 4に一致する場合、行列の0の要素をすべて置き換えて得られる行列は、

${\displaystyle {\begin{bmatrix}0&j^{T}\\j&Q\end{bmatrix}}}$

マトリックスと

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

そして、行列のすべてのエントリは±1である

${\displaystyle \pm {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$

はサイズ2( q +1)のアダマール行列です 。これは対称アダマール行列です。

GF(7)のヤコブスター行列にパリー構成Iを適用すると、8×8のアダマール行列が得られる。

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

q が素数ではなく素数べきである場合の Paley II 構成の例として、GF(9) を考えてみましょう。これは、既約な二次方程式の根を付加することによって得られる GF(3) の拡大体です。異なる既約な二次方程式は、同等の体を生成します。x ² + x −1 を選択し、a をこの多項式 の根とすると、GF ( 9) の 9 つの要素は、0、1、−1、a、a + 1、 a −1、− a、− a +1、− a −1 と表記できます。非ゼロの平方は、1 = (±1) ²、− a +1 = (± a ) ²、a −1 = (±( a +1)) ²、および −1 = (±( a −1)) ²です。ヤコブスター行列は、

${\displaystyle Q={\begin{bmatrix}0&1&1&-1&-1&1&-1&1&-1\\1&0&1&1&-1&-1&-1&-1&1\\1&1&0&-1&1&-1&1&-1&-1\\-1&1&-1&0&1&1&-1&-1&1\\-1&-1&1&1&0&1&1&-1&-1\\1&-1&-1&1&1&0&-1&1&-1\\-1&-1&1&-1&1&-1&0&1&1\\1&-1&-1&-1&-1&1&1&0&1\\-1&1&-1&1&-1&-1&1&1&0\end{bmatrix}}.}$

これは9つの3×3循環ブロックからなる対称行列である。ペイリー構成IIは対称20×20アダマール行列を生成する。

1- 111111 111111 111111
-- 1-1-1- 1-1-1- 1-1-1-

11 1-1111 ----11 --11--
1- --1-1- -1-11- -11--1
11 111-11 11---- ----11
1- 1---1- 1--1-1 -1-11-
11 11111- --11-- 11----
1- 1-1--- -11--1 1--1-1

11 --11-- 1-1111 ----11
1- -11--1 --1-1- -1-11-
11 ----11 111-11 11----
1- -1-11- 1---1- 1--1-1
11 11---- 11111- --11--
1- 1--1-1 1-1--- -11--1

11 ----11 --11-- 1-1111
1- -1-11- -11--1 --1-1-
11 11---- ----11 111-11
1- 1--1-1 -1-11- 1---1-
11 --11-- 11---- 11111-
1- -11--1 1--1-1 1-1---。

アダマール行列のサイズは1、2、または4の倍数でなければならない。サイズmとnの2つのアダマール行列のクロネッカー積は、サイズmnのアダマール行列である。ペイリー構成と2×2行列から行列のクロネッカー積を形成することにより、

${\displaystyle H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},}$

92 を除く 100 までのすべての許容サイズのアダマール行列が生成されます。1933 年の論文で、ペイリーは「mが 4 で割り切れる場合は常に、±1 で構成されるm次直交行列を構築できる可能性があるが、一般定理は明らかに困難である」と述べています。これは、アダマール予想の最初の公表された声明のようです。サイズ 92 の行列は、最終的に、ウィリアムソンによる構築とコンピューター検索を組み合わせて、ボーマート、ゴロム、ホールによって構築されました。現在、 m < 668のすべての場合にアダマール行列が存在することが示されています 。 ${\displaystyle m\,\equiv \,0\mod 4}$

• ペイリー複葉機
• ペイリーグラフ

• Paley, REAC (1933). 「直交行列について」.数学物理学ジャーナル. 12 : 311–320. doi :10.1002/sapm1933121311. Zbl  0007.10004.
• LD Baumert; SW Golomb ; M. Hall Jr (1962). 「92次のアダマール行列の発見」Bull. Amer. Math. Soc . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 .
• FJ MacWilliams ; NJA Sloane (1977)。誤り訂正符号の理論。ノースホランド。pp. 47, 56。ISBN 0-444-85193-3。