Maksimal determinant muammosi - Hadamards maximal determinant problem - Wikipedia

Hadamardning maksimal determinant muammosinomi bilan nomlangan Jak Hadamard, eng kattasini so'raydi aniqlovchi a matritsa 1 yoki -1 ga teng elementlar bilan. Elementlari 0 yoki 1 ga teng bo'lgan matritsalar uchun o'xshash savol teng, chunki quyida ko'rsatilgandek, o'lchamdagi {1, -1} matritsaning maksimal determinanti n 2.ⁿ⁻¹ {0,1} kattalikdagi matritsaning maksimal determinantidan kattaroq n−1. Muammo 1893 yilgi maqolada Hadamard tomonidan qo'yilgan^[1] unda u o'zining mashhurlarini taqdim etdi determinant bog'langan va umumiy o'lchamdagi matritsalar uchun echilmagan bo'lib qoladi. Hadamardning chegarasi shundan iboratki, kattalikdagi matritsalar {1, -1} n ko'pi bilan determinantga ega n^n/2. Hadamard qurilishini ko'rdi Silvestr^[2]qachon chegaraga erishgan matritsalar misollarini keltirib chiqaradi n 2 ning kuchiga ega va 12 va 20 o'lchamdagi o'ziga xos misollarni keltirib chiqardi. Shuningdek, u faqat qachon bog'liqligini ko'rsatdi n 1, 2 yoki ko'paytmaga teng. Qo'shimcha misollar keyinchalik Skarpis va Paley tomonidan va keyinchalik ko'plab boshqa mualliflar tomonidan tuzilgan. Bunday matritsalar endi sifatida tanilgan Hadamard matritsalari. Ular intensiv o'qishdi.

Matritsa o'lchamlari n buning uchun n ≡ 1, 2 yoki 3 (mod 4) kamroq e'tibor oldi. Dastlabki natijalar, Hadamard bilan bog'lanishni kuchaytirgan Barba tufayli n g'alati va uchun eng katta determinantlarni topgan Uilyamson n= 3, 5, 6 va 7. Ba'zi muhim natijalarga quyidagilar kiradi

Barba, Ehlich va Voytas tufayli yanada qattiqroq chegaralar n ≡ 1, 2 yoki 3 (mod 4), ammo har doim ham erishish mumkin emasligi ma'lum,
chegaralarini qo'lga kiritadigan bir nechta cheksiz matritsalar ketma-ketligi n ≡ 1 yoki 2 (mod 4),
aniqlik chegaralariga erishadigan bir qator matritsalar n ≡ 1 yoki 2 (mod 4),
bir qator matritsalar aniq chegaralarga erisha olmaydi n Or 1 yoki 3 (mod 4), ammo bu maksimal aniqlovchiga ega bo'lgan to'liq hisoblash bilan isbotlangan.

The tajribalarni loyihalash yilda statistika {1, -1} matritsalardan foydalanadi X (shart emas kvadrat) buning uchun axborot matritsasi X^TX maksimal determinantga ega. (Belgilanish X^T belgisini bildiradi ko'chirish ning X.) Bunday matritsalar sifatida tanilgan D-optimal dizaynlar.^[3] Agar X a kvadrat matritsa, u to'yingan D-optimal dizayni sifatida tanilgan.

Hadamard matritsalari

Har qanday ikkita qator n×n Hadamard matritsasi ortogonal. {1, -1} matritsasi uchun bu istalgan ikki qator yozuvlarning to'liq yarmida farq qiladi, bu esa imkonsiz n bu toq raqam. Qachon n ≡ 2 (mod 4), ikkala uchinchi qatorga ortogonal bo'lgan ikkita qator bir-biriga ortogonal bo'lolmaydi. Ushbu bayonotlar birgalikda an n×n Hadamard matritsasi faqatgina mavjud bo'lishi mumkin n = 1, 2 yoki ko'paytma 4. Hadamard matritsalari yaxshi o'rganilgan, ammo an yoki yo'qligi ma'lum emas n×n Hadamard matritsasi har birida mavjud n bu musbat ko'paytma 4. Eng kichigi n buning uchun an n×n Hadamard matritsasi mavjud emasligi ma'lum emas 668.

{1, −1} matritsalarining ekvivalenti va normalizatsiyasi

{1, -1} matritsada bajarilganda quyidagi operatsiyalardan biri R, ning determinantini o'zgartiradi R faqat minus belgisi bilan:

Bir qatorni inkor qilish.
Ustunning inkor etilishi.
Ikki qatorni almashtirish.
Ikki ustunni almashtirish.

Ikki {1, −1} matritsalar, R₁ va R₂, hisobga olinadi teng agar R₁ ga aylantirilishi mumkin R₂ yuqoridagi operatsiyalarning ba'zi bir ketma-ketligi bo'yicha. Ekvivalent matritsalarning determinantlari tengdir, ehtimol belgining o'zgarishi bundan mustasno va ko'pincha uni standartlashtirish qulay R qatorlar va ustunlarni inkor qilish va almashtirish orqali. A {1, -1} matritsa quyidagicha normallashtirilgan agar uning birinchi satridagi va ustunidagi barcha elementlar teng bo'lsa 1. Matritsaning kattaligi g'alati bo'lsa, ba'zida har bir satr va ustunda juft elementlar soni 1 va toq sonli elementlar bo'lgan boshqa normallashtirishdan foydalanish foydalidir - 1. Ushbu normallashtirishlarning har ikkalasini ham dastlabki ikkita operatsiya yordamida bajarish mumkin.

{1, −1} va {0, 1} matritsalar uchun maksimal determinant muammolarini ulash

Normallashtirilgan to'plamdan bitta-bitta xarita mavjud n×n {1, -1} matritsalar (n−1)×(n-1) determinantning kattaligi 2 marta kamaytirilgan {0, 1} matritsalar¹⁻ⁿ. Ushbu xarita quyidagi bosqichlardan iborat.

{1, −1} matritsasining 1-qatorini 2-dan 2-gacha bo'lgan qatorlardan olib tashlang n. (Bu determinantni o'zgartirmaydi.)
Chiqarib oling (n−1)×(n−1) 2 dan 2 gacha qatorlardan iborat submatrix n va ustunlar 2 dan n. Ushbu matritsa 0 va −2 elementlarga ega. (Ushbu pastki matritsaning determinanti asl matritsaning o'zi bilan bir xil, a bajarilishi bilan ko'rish mumkin kofaktor kengayishi 1-bosqichda olingan matritsaning 1-ustunida.)
{0, 1} matritsasini olish uchun submatrisani -2 ga bo'ling. (Bu determinantni (-2) ga ko'paytiradi¹⁻ⁿ.)

Misol:

{ displaystyle { begin {bmatrix} 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}}}

Ushbu misolda asl matritsa -16 determinantiga ega va uning tasviri 2 = -16 · (-2) determinantga ega.⁻³.

{0, 1} matritsaning determinanti butun son bo'lgani uchun, anning determinanti n×n {1, −1} matritsa - bu 2 ga teng butun sonⁿ⁻¹.

Maksimal determinantning yuqori chegaralari

Grammatrisa

Ruxsat bering R bo'lish n tomonidan n {1, −1} matritsasi. The Grammatrisa ning R matritsa sifatida belgilangan G = RR^T. Ushbu ta'rifdan kelib chiqadigan narsa G

butun sonli matritsa,
bu nosimmetrik,
bu ijobiy-yarim cheksiz,
qiymati teng bo'lgan doimiy diagonalga ega n.

Qatorlarini inkor qilish R yoki ularga permutatsiyani qo'llash bir qator inkorlarga va permutation-ga satrlarga ham, tegishli ustunlarga ham qo'llanilishiga olib keladi. G. Biz matritsani ham belgilashimiz mumkin G′=R^TR. Matritsa G bu odatiy Grammatrisa qatorlari to'plamidan kelib chiqqan vektorlar to'plamining R, esa G′ - ning ustunlari to'plamidan olingan Gram matritsa R. Matritsa R buning uchun G = GA a normal matritsa. Har bir ma'lum bo'lgan maksimal-determinant matritsasi normal matritsaga teng, ammo bu har doim ham shunday bo'ladimi-yo'qmi noma'lum.

Hadamard bog'langan (hamma uchun n)

Hadamardning bog'langanligini | detR| = (detG)^1/2 ≤ (det.)nI)^1/2 = n^n/2, bu kuzatuv natijasidir nI, qayerda Men bo'ladi n tomonidan n identifikatsiya matritsasi, 1-4 xususiyatlarini qondiradigan matritsalar orasida maksimal determinantning noyob matritsasi. Bu detR butun sonning 2 ga ko'paytmasi bo'lishi kerakⁿ⁻¹ Hadamardning chegarasi har doim ham mavjud emasligini yana bir namoyish qilish uchun foydalanish mumkin. Qachon n toq, chegaralangan n^n/2 tamsayısiz yoki g'alati bo'lib, shuning uchun holatlardan tashqari unga erishib bo'lmaydi n = 1. Qachon n = 2k bilan k g'alati, Hadamardning chegarasini ajratuvchi 2 ning eng yuqori kuchi 2 ga teng^k bu 2 dan kamⁿ⁻¹ agar bo'lmasa n = 2. Demak, Hadamardning bog'lanishiga erishib bo'lmaydi, agar n = 1, 2 yoki 4 ga ko'paytma.

Barba majburiy n g'alati

Qachon n toq, Gram matritsalari uchun 1-xususiyat kuchaytirilishi mumkin

G toq sonli matritsa.

Bu yuqori chegarani keskinlashtirishga imkon beradi^[4] olinishi kerak: | detR| = (detG)^1/2 ≤ (det (n-1)Men+J)^1/2 = (2n−1)^1/2(n−1)^(n−1)/2, qayerda J bu yagona matritsa. Bu yerda (n-1)Men+J o'zgartirilgan xususiyat 1 va 2-4 xususiyatlarini qondiradigan maksimal-determinant matritsa. Har qanday qatorlar to'plamini va tegishli ustunlar to'plamini -1 ga ko'paytirishgacha noyobdir. Chegaraga erishish mumkin emas, agar 2n$ -1 $ - bu mukammal kvadrat, shuning uchun qachon bo'lmasin n ≡ 3 (mod 4).

Ehlich-Voytas tomon yo'l oldi n ≡ 2 (mod 4)

Qachon n teng qatorlar qatori R ikkita pastki qismga bo'linishi mumkin.

Qatorlari hatto yozing elementlarning juft sonini 1 va even1 elementlarning juft sonini o'z ichiga oladi.
Qatorlari toq turi elementlarning toq soni 1 va toq soni −1 elementlardan iborat.

Xuddi shu turdagi ikkita qatorning nuqta mahsuloti mos keladi n (mod 4); qarama-qarshi turdagi ikki qatorli nuqta hosilasi mos keladi n+2 (mod 4). Qachon n ≡ 2 (mod 4), bu shuni anglatadiki, qatorlarni almashtirish orqali R, deb taxmin qilishimiz mumkin standart shakl,

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

qayerda A va D. nosimmetrik butun matritsalar bo'lib, ularning elementlari 2 (mod 4) va ga mos keladi B elementlari 0 ga mos keladigan matritsa (mod 4). 1964 yilda Ehlich^[5] va Vojtas^[6] mustaqil ravishda ushbu shaklning maksimal determinant matritsasida, A va D. ikkalasi ham o'lchamga ega n/ 2 va (ga teng)n−2)Men+2J esa B nol matritsa. Ushbu maqbul shakl har qanday qatorlar to'plamini va tegishli ustunlar to'plamini -1 ga ko'paytirishgacha va bir vaqtning o'zida qatorlar va ustunlarga almashtirishni qo'llash uchun noyobdir. Bu bog'langan detni nazarda tutadiR ≤ (2n−2)(n−2)^(n−2)/2. Ehlich buni ko'rsatdi R ning chegaralari va qatorlari va ustunlari bo'lsa R ikkalasi ham shunday joylashtirilgan G = RR^T va G′ = R^TR standart shaklga ega va mos ravishda normallashtirilgan, keyin biz yozishimiz mumkin

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

qayerda V, X, Yva Z bor (n/2)×(n/ 2) doimiy qator va ustunlar yig'indisi bo'lgan matritsalar w, x, yva z bu qondiradi z = −w, y = xva w²+x² = 2n−2. Shuning uchun Ehlich-Voytas bog'lanishiga erishilmasa, 2n−2 ikkita kvadratning yig'indisi sifatida ifodalanadi.

Ehlich bog'langan n ≡ 3 (mod 4)

Qachon n g'alati, keyin satrlarni -1 ga ko'paytirish erkinligidan foydalanib, har bir satrning sharti qo'yilishi mumkin R elementlarning juft sonini 1 va toq sonini −1 elementlarini o'z ichiga oladi. Ko'rinib turibdiki, agar bu normalizatsiya qabul qilingan bo'lsa, unda 1 ning xususiyati G ga kuchaytirilishi mumkin

G butun elementlari bilan mos keladigan matritsa n (mod 4).

Qachon n ≡ 1 (mod 4), Barbaning optimal shakli bu kuchli xususiyatni qondiradi, ammo qachon n ≡ 3 (mod 4), unday emas. Bu shuni anglatadiki, ikkinchi holatda chegarani keskinlashtirish mumkin. Ehlich^[7] buni qachon ko'rsatdi n ≡ 3 (mod 4), kuchaytirilgan xossasi 1 ning maksimal-determinant shakli ekanligini anglatadi G sifatida yozilishi mumkin B−J qayerda J bu bitta matritsa va B a blok-diagonali matritsa uning diagonal bloklari (n-3)Men+4J. Bundan tashqari, u optimal shaklda bloklar sonini, s, bog'liq n quyidagi jadvalda ko'rsatilgandek va har bir blok o'lchamiga ega r yoki o'lcham r + 1 qayerda ${ displaystyle r = lfloor n / s rfloor.}$

n	s
3	3
7	5
11	5 yoki 6
15 − 59	6
≥ 63	7

Dan tashqari n= 11, agar ikkita imkoniyat mavjud bo'lsa, optimal shakl har qanday qatorlar to'plamini va tegishli ustunlar to'plamini -1 ga ko'paytirishgacha va bir vaqtning o'zida qatorlar va ustunlarga almashtirishni qo'llash uchun noyobdir. Ushbu maqbul shakl cheklanishga olib keladi

{ displaystyle det R leq (n-3) ^ {(ns) / 2} (n-3 + 4r) ^ {u / 2} (n + 1 + 4r) ^ {v / 2} chap [ 1 - { frac {ur} {n-3 + 4r}} - { frac {v (r + 1)} {n + 1 + 4r}} o'ng] ^ {1/2},}

qayerda v = n−rs o'lchamdagi bloklar soni r+1 va siz =s−v o'lchamdagi bloklar soni r. Kon^[8] bog'liqligini tahlil qildi va bundan tashqari ekanligini aniqladi n = 3, bu faqat uchun butun son n = 112t²±28t+7 ijobiy son uchun t. Tamura^[9] yordamida bog'lanishning erishilishiga qo'shimcha cheklovlarni keltirib chiqardi Xasse-Minkovskiy teoremasi kvadrat shakllarning oqilona ekvivalenti to'g'risida va eng kichik ekanligini ko'rsatdi n > 3 uchun Ehlichning bog'lanishiga erishish mumkin - 511.

21 o'lchamgacha bo'lgan maksimal determinantlar

{1, -1} matritsalarning kattalikka qadar maksimal determinantlari n = 21 quyidagi jadvalda keltirilgan.^[10] 22 o'lchov - bu eng kichik ochiq quti. Jadvalda, D.(n) 2 ga bo'lingan maksimal aniqlovchini ifodalaydiⁿ⁻¹. Teng ravishda, D.(n) o'lchamdagi {0, 1} matritsaning maksimal determinantini ifodalaydi n−1.

n	D.(n)	Izohlar
1	1	Hadamard matritsasi
2	1	Hadamard matritsasi
3	1	Ehlich bog'langan
4	2	Hadamard matritsasi
5	3	Barbaga bog'langan; sirkulant matritsa
6	5	Ehlich-Voytas bog'iga etib boradi
7	9	Ehlichning 98,20% ulangan
8	32	Hadamard matritsasi
9	56	Barba bilan bog'langanlarning 84,89%
10	144	Ehlich-Voytas bog'iga etib boradi
11	320	Ehlichning 94,49%; uchta ekvivalent bo'lmagan matritsalar
12	1458	Hadamard matritsasi
13	3645	Barbaga bog'langan; maksimal-determinant matritsasi - {1, -1} ning tushish matritsasi proektsion tekislik buyurtma 3
14	9477	Ehlich-Voytas bog'iga etib boradi
15	25515	Ehlichning 97,07% ulangan
16	131072	Hadamard matritsasi; beshta teng bo'lmagan matritsalar
17	327680	87,04% Barba bilan bog'langan; uchta ekvivalent bo'lmagan matritsalar
18	1114112	Ehlich-Voytas bog'langan; uchta ekvivalent bo'lmagan matritsalar
19	3411968	Ehlichning 97,50% ga erishadi; uchta ekvivalent bo'lmagan matritsalar
20	19531250	Hadamard matritsasi; uchta ekvivalent bo'lmagan matritsalar
21	56640625	90,58% Barba bilan bog'langan; etti teng bo'lmagan matritsalar

Adabiyotlar

^ Hadamard, J. (1893), "Résolution d'une question nisbatan aux déterminants", Bulletin des Sciences Mathématiques, 17: 240–246
^ Silvester, J. J. (1867), "teskari ortogonal matritsalar haqidagi fikrlar, bir vaqtning o'zida ishora merosxo'rlari va tessellated yulka ikki yoki undan ortiq rangda, Nyuton qoidalariga tatbiq etilgan, dekorativ plitka ishi va raqamlar nazariyasi", London Edinburg Dublin Fil. Mag. J. Sci., 34: 461–475
^ Galil, Z .; Kiefer, J. (1980), "D.- eng yaxshi tortish dizaynlari ", Ann. Stat., 8: 1293–1306, doi:10.1214 / aos / 1176345202
^ Barba, Gvido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Jorn. Mat Battaglini, 71: 70–86.
^ Ehlich, Xartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Matematika. Z., 83: 123–132, doi:10.1007 / BF01111249.
^ Vojtas, M. (1964), "4 ga bo'linmaydigan tartibning determinantlari uchun Hadamardning tengsizligi to'g'risida", Kolloq. Matematika., 12: 73–83.
^ Ehlich, Xartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n ≡ 3 mod 4 ", Matematika. Z., 84: 438–447, doi:10.1007 / BF01109911.
^ Kon, J. H. E. (2000), "Deyarli D-optimal dizaynlar", Utilitas matematikasi., 57: 121–128.
^ Tamura, Xiroki (2006), "D-optimal dizaynlar va guruhga bo'linadigan dizaynlar", Kombinatorial dizaynlar jurnali, 14: 451–462, doi:10.1002 / jcd.20103.
^ Sloan, N. J. A. (tahrir). "A003432 ketma-ketligi (Hadamardning maksimal determinant muammosi: a (haqiqiy) ning eng katta determinanti {0,1} - n tartibli matritsa)". The Butun sonlar ketma-ketligining on-layn ensiklopediyasi. OEIS Foundation.

[1] Hadamard, J. (1893), "Résolution d'une question nisbatan aux déterminants", Bulletin des Sciences Mathématiques, 17: 240–246

[2] Silvester, J. J. (1867), "teskari ortogonal matritsalar haqidagi fikrlar, bir vaqtning o'zida ishora merosxo'rlari va tessellated yulka ikki yoki undan ortiq rangda, Nyuton qoidalariga tatbiq etilgan, dekorativ plitka ishi va raqamlar nazariyasi", London Edinburg Dublin Fil. Mag. J. Sci., 34: 461–475

[3] Galil, Z .; Kiefer, J. (1980), "D.- eng yaxshi tortish dizaynlari ", Ann. Stat., 8: 1293–1306, doi:10.1214 / aos / 1176345202

[4] Barba, Gvido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Jorn. Mat Battaglini, 71: 70–86.

[5] Ehlich, Xartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Matematika. Z., 83: 123–132, doi:10.1007 / BF01111249.

[6] Vojtas, M. (1964), "4 ga bo'linmaydigan tartibning determinantlari uchun Hadamardning tengsizligi to'g'risida", Kolloq. Matematika., 12: 73–83.

[7] Ehlich, Xartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n ≡ 3 mod 4 ", Matematika. Z., 84: 438–447, doi:10.1007 / BF01109911.

[8] Kon, J. H. E. (2000), "Deyarli D-optimal dizaynlar", Utilitas matematikasi., 57: 121–128.

[9] Tamura, Xiroki (2006), "D-optimal dizaynlar va guruhga bo'linadigan dizaynlar", Kombinatorial dizaynlar jurnali, 14: 451–462, doi:10.1002 / jcd.20103.

[10] Sloan, N. J. A. (tahrir). "A003432 ketma-ketligi (Hadamardning maksimal determinant muammosi: a (haqiqiy) ning eng katta determinanti {0,1} - n tartibli matritsa)". The Butun sonlar ketma-ketligining on-layn ensiklopediyasi. OEIS Foundation.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]