Paley qurilishi - Paley construction

Yilda matematika, Paley qurilishi qurish uchun usuldir Hadamard matritsalari foydalanish cheklangan maydonlar. Qurilish 1933 yilda tasvirlangan Ingliz tili matematik Raymond Paley.

Paley qurilishidan foydalaniladi kvadratik qoldiqlar cheklangan maydonda GF(q) qayerda q toq kuch asosiy raqam. Qurilishga bog'liq ravishda ikkita versiya mavjud q 1 yoki 3 ga mos keladi (mod 4).

Kvadratik belgilar va Yakobsthal matritsasi

Kvadratik belgi χ (a) berilgan cheklangan maydon elementi yoki yo'qligini bildiradi a mukammal kvadrat. Xususan, χ (0) = 0, χ (a) = 1 agar a = b² nolga teng bo'lmagan cheklangan maydon elementi uchun bva χ (a) Agar = -1 bo'lsa a har qanday cheklangan maydon elementining kvadrati emas. Masalan, ichida GF(7) nolga teng bo'lmagan kvadratlar 1 = 1 ga teng² = 6², 4 = 2² = 5²va 2 = 3² = 4². Demak χ (0) = 0, χ (1) = χ (2) = χ (4) = 1 va χ (3) = χ (5) = χ (6) = -1.

The Jeykobsthal matritsa Q uchun GF(q) bo'ladi q×q satr va ustunlar bilan matritsa, qatorga kirish kabi cheklangan maydon elementlari tomonidan indekslangan a va ustun b bu χ (a − b). Masalan, ichida GF(7), agar Jacobsfal matritsasining satrlari va ustunlari maydon elementlari 0, 1, 2, 3, 4, 5, 6 tomonidan indekslangan bo'lsa, unda

{ 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}}.}

Jakobstal matritsasi xususiyatlarga ega QQ^T = qI − J va QJ = JQ = 0 qaerda Men bo'ladi q×q identifikatsiya matritsasi va J bo'ladi q×q barchasi 1 matritsa. Agar q $ 1 (mod 4) $ ga to'g'ri keladi, keyin $ -1 $ kvadrat GF(q) shuni anglatadiki Q a nosimmetrik matritsa. Agar q $ 3 (mod 4) $ ga to'g'ri keladi, $ -1 $ kvadrat emas va Q anosimmetrik matritsa. Qachon q asosiy son, Q a sirkulant matritsa. Ya'ni, har bir satr yuqoridagi qatordan tsiklik almashtirish orqali olinadi.

Paley qurilishi I

Agar q keyin 3 (mod 4) ga mos keladi

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

bu Hadamard matritsasi q + 1. Mana j uzunlikning barcha-1 ustunli vektori q va Men bo'ladi (q+1)×(q+1) identifikatsiya matritsasi. Matritsa H a Hadamard matritsasini burish, bu uni qondirishini anglatadi H+H^T = 2Men.

Paley qurilishi II

Agar q 1 (mod 4) ga mos keladi, keyin barcha 0 yozuvlarini almashtirish natijasida olingan matritsa

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

matritsa bilan

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

va matritsa bilan barcha yozuvlar ± 1

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

2 o'lchamdagi Hadamard matritsasi (q + 1). Bu nosimmetrik Hadamard matritsasi.

Misollar

Paley Construction I-ni Jacobsthal matritsasiga qo'llash GF(7), biri 8 × 8 Hadamard matritsasini ishlab chiqaradi,

11111111-1--1-11-11--1-1-111--1---111--1-1-111----1-111----1-111.

Paley II qurilishiga misol uchun qachon q asosiy raqam emas, balki asosiy kuchdir, o'ylab ko'ring GF(9). Bu kengaytma maydoni ning GF(3) an ildizi bilan tutashgan holda olinadi qisqartirilmaydigan kvadratik. Turli qisqartirilmaydigan kvadratikalar teng maydonlarni hosil qiladi. Tanlash x²+x-1 va ruxsat berish a ning to`qqiz elementi bo`lgan ushbu polinomning ildizi bo`ling GF(9) 0, 1, -1, a, a+1, a−1, −a, −a+1, −a−1. Nolga teng bo'lmagan kvadratlar 1 = (± 1)², −a+1 = (±a)², a−1 = (±(a+1))²va -1 = (± (a−1))². Jeykobsthal matritsasi

{ displaystyle Q = { begin {bmatrix} 0 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & -1 1 & 0 & 1 & 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 & 0 & 1 - 1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & 1 & 0 end {bmatrix}}.}

Bu to'qqizta 3 × 3 sirkulyant bloklardan tashkil topgan nosimmetrik matritsa. Paley Construction II nosimmetrik 20 × 20 Hadamard matritsasini ishlab chiqaradi,

1- 111111 111111 111111-- 1-1-1- 1-1-1- 1-1-1-11 1-1111 ----11 --11--1- --1-1- -1-11- -11--111 111-11 11---- ----111- 1---1- 1--1-1 -1-11-11 11111- --11-- 11----1- 1-1--- -11--1 1--1-111 --11-- 1-1111 ----111- -11--1 --1-1- -1-11-11 ----11 111-11 11----1- -1-11- 1---1- 1--1-111 11---- 11111- --11--1- 1--1-1 1-1--- -11--111 ----11 --11-- 1-11111- -1-11- -11--1 --1-1-11 11---- ----11 111-111- 1--1-1 -1-11- 1---1-11 --11-- 11---- 11111-1- -11--1 1--1-1 1-1---.

Hadamard gumoni

Hadamard matritsasining kattaligi 1, 2 yoki ko'paytma 4 ga teng bo'lishi kerak Kronecker mahsuloti o'lchamdagi ikkita Hadamard matritsasi m va n bu Hadamard matritsasi mn. Paley konstruktsiyasidan va 2 × 2 matritsadan Kronecker matritsalarini hosil qilib,

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

92 dan tashqari har bir ruxsat etilgan o'lchamdagi 100 gacha bo'lgan Hadamard matritsalari ishlab chiqariladi. Peyli o'zining 1933 yilgi maqolasida: «Bu, ehtimol, har doimgidek ko'rinadi m 4 ga bo’linsa, an hosil qilish mumkin ortogonal matritsa tartib m ± 1 dan tashkil topgan, ammo umumiy teorema har qanday qiyofaga ega. " Bu e'lon qilingan birinchi bayonotga o'xshaydi Hadamard gumoni. Oxir-oqibat 92 o'lchovli matritsa Baumert tomonidan qurilgan, Golomb va Zal, Uilyamson tufayli konstruktsiyadan foydalangan holda kompyuterni qidirish. Hozirgi vaqtda Hadamard matritsalari hamma uchun mavjudligini ko'rsatdi ${ displaystyle scriptstyle m , equiv , 0 mod 4}$ uchun m < 668.

Shuningdek qarang

Adabiyotlar

Paley, R.E.A.C. (1933). "Ortogonal matritsalarda". Matematika va fizika jurnali. 12: 311–320.
L. D. Baumert; S. V. Golomb; M. Hall kichik (1962). "92-darajali Hadamard matritsasini kashf etish". Buqa. Amer. Matematika. Soc. 68 (3): 237–238. doi:10.1090 / S0002-9904-1962-10761-7.
F.J.MakVilliams; N.J.A. Sloan (1977). Xatolarni tuzatish kodlari nazariyasi. Shimoliy-Gollandiya. pp.47, 56. ISBN 0-444-85193-3.