Максималды детерминант проблемасы - Hadamards maximal determinant problem - Wikipedia

Хадамардың максималды детерминант мәселесі, атындағы Жак Хадамар, ең үлкенін сұрайды анықтауыш а матрица элементтері 1 немесе −1-ге тең. Элементтері 0 немесе 1-ге тең матрицалар үшін ұқсас сұрақ эквивалентті болады, өйткені төменде көрсетілгендей, өлшемнің {1, -1} матрицасының максималды детерминанты n 2.n−1 {0,1} өлшемді матрицаның максималды детерминанты есе n−1. Мәселе Хадамардың 1893 жылғы мақаласында туындаған[1] онда ол өзінің әйгілі тұсауын кесті детерминантты байланысты және жалпы өлшемдегі матрицалар үшін шешілмеген болып қалады. Хадамардың шегі {1, −1} - өлшем матрицаларын білдіреді n ең көп дегенде анықтауышқа ие nn/2. Хадамардың құрылысын байқады Сильвестр[2]матрицалардың мысалдарын шығарады, олар қашан байланысты болады n ол 2-нің күші болып табылады және оның өлшемдері 12 және 20-ға тең мысалдарды келтірді. Сонымен қатар, байланыс тек сол кезде болатындығын көрсетті n 1-ге, 2-ге немесе 4-ке еселікке тең. Қосымша мысалдарды кейіннен Скарпис пен Пейли, содан кейін көптеген басқа авторлар салған. Мұндай матрицалар қазір белгілі Хадамард матрицалары. Олар қарқынды оқудан өтті.

Матрица өлшемдері n ол үшін n , 1, 2 немесе 3 (мод 4) аз көңіл бөлді. Алғашқы нәтижелер Хадамардың байланысын күшейткен Барбаға байланысты n тақ, және ең үлкен детерминанттарды тапқан Уильямсон n= 3, 5, 6 және 7. Кейбір маңызды нәтижелерге жатады

  • Барба, Эхлич және Войтасқа байланысты қатаң шектеулер n , 1, 2 немесе 3 (мод 4), бірақ олар әрдайым қол жетімді емес екендігі белгілі,
  • шектеріне жететін матрицалардың бірнеше шексіз тізбегі n ≡ 1 немесе 2 (мод 4),
  • шектеулерге жететін бірқатар матрицалар n ≡ 1 немесе 2 (мод 4),
  • шектеулерге қол жеткізбейтін бірқатар матрицалар n Or 1 немесе 3 (мод 4), бірақ мұны максималды детерминанты бар толық есептеу арқылы дәлелдеді.

The эксперименттерді жобалау жылы статистика {1, −1} матрицаларын қолданады X (міндетті түрде квадрат емес), ол үшін ақпараттық матрица XТX максималды детерминанты бар. (Белгілеу XТ дегенді білдіреді транспозициялау туралы X.) Мұндай матрицалар ретінде белгілі D-оңтайлы дизайн.[3] Егер X Бұл квадрат матрица, ол қаныққан D-оңтайлы дизайн ретінде белгілі.

Хадамард матрицалары

Кез келген екі қатар n×n Хадамард матрицасы болып табылады ортогоналды. {1, −1} матрицасы үшін бұл кез-келген екі жол жазбалардың тура жартысында ерекшеленетінін білдіреді, бұл мүмкін емес n болып табылады тақ сан. Қашан n ≡ 2 (mod 4), екеуі де үшінші қатарға ортогональ болатын екі қатар бір-біріне орогональ бола алмайды. Бұл мәлімдемелер бірге ан n×n Хадамард матрицасы тек болған жағдайда болады n = 1, 2 немесе 4-ке еселік. Хадамар матрицалары жақсы зерттелген, бірақ ан екендігі белгісіз n×n Хадамард матрицасы әрқайсысында бар n бұл 4-тің оң еселігі. Ең кішісі n ол үшін n×n Хадамард матрицасының бар екендігі белгісіз - 668.

{1, −1} матрицаларының эквиваленттілігі және қалыпқа келуі

{1, −1} матрицасында орындалған кез-келген операциялардың кез-келгені R, детерминантын өзгертеді R тек минус белгісі бойынша:

  • Жолды теріске шығару
  • Бағанды ​​терістеу
  • Екі қатарды ауыстыру.
  • Екі бағанды ​​ауыстыру.

Екі {1, −1} матрица, R1 және R2, қарастырылады балама егер R1 түрлендіруге болады R2 жоғарыда аталған операциялардың бірізділігі бойынша. Эквивалентті матрицалардың детерминанты, тек таңбаның өзгеруін қоспағанда, тең болады, және оны көбіне стандарттау ыңғайлы R жолдар мен бағандарды терістеу және ауыстыру арқылы. {1, −1} матрицасы мынаған тең қалыпқа келтірілген егер оның бірінші жолындағы және бағанындағы барлық элементтер тең болса 1. Матрицаның өлшемі тақ болғанда, кейде әр жолда және бағанда жұп элементтер саны 1 мен элементтердің тақ саны болатын әртүрлі қалыптауды қолдану пайдалы болады - 1. Осы нормаландырудың кез-келгенін алғашқы екі амалды қолдану арқылы жүзеге асыруға болады.

{1, −1} және {0, 1} матрицалары үшін максималды детерминант есептерін қосу

Нормаланған жиынтықтан бір-бірден карта бар n×n {1, −1} матрицалар (n−1)×(n-1) детерминанттың шамасы 2 есе азайтылатын {0, 1} матрицалар1−n. Бұл карта келесі қадамдардан тұрады.

  1. {1, −1} матрицасының 1-ші жолын 2-ден 2-ге дейінгі жолдардан алып тастаңыз n. (Бұл анықтауышты өзгертпейді.)
  2. Шығарып алыңыз (n−1)×(n−1) 2-ші қатардан тұратын субматрица n және бағандар 2-ден n. Бұл матрицада 0 және −2 элементтері бар. (Бұл субматриканың детерминанты бастапқы матрицамен бірдей, оны а орындау арқылы көруге болады кофактордың кеңеюі 1-қадамда алынған матрицаның 1-бағанында.)
  3. {0, 1} матрицасын алу үшін субматриканы −2-ге бөліңіз. (Бұл детерминантты (-(2) көбейтеді1−n.)

Мысал:

Бұл мысалда бастапқы матрицаның determ16 детерминанты бар, ал оның кескінінің детерминанты 2 = −16 · (−2)−3.

{0, 1} матрицасының детерминанты бүтін сан болғандықтан, ан детерминанты n×n {1, −1} матрицасы - 2-ге бүтін санn−1.

Максималды детерминанттың жоғарғы шектері

Грамматрица

Келіңіздер R болуы n арқылы n {1, −1} матрица. The Грамматрица туралы R матрица ретінде анықталған G = RRТ. Бұл анықтамадан мыналар шығады G

  1. бүтін матрица,
  2. болып табылады симметриялы,
  3. болып табылады позитивті-жартылай шексіз,
  4. мәні тең болатын тұрақты диагоналы бар n.

Теріс жолдар R немесе оларға ауыстыруды қолдану бірдей терістеулер мен ауыстыруларды жолдарға да, сәйкес бағандарға да қолдануға әкеледі G. Біз матрицаны да анықтай аламыз G′=RТR. Матрица G әдеттегідей Грамматрица қатарынан алынған векторлар жиынтығының R, ал G′ - бағаналар жиынынан алынған Грамматрица R. Матрица R ол үшін G = G' Бұл қалыпты матрица. Кез-келген белгілі максималды-детерминантты матрица қалыпты матрицаға эквивалентті, бірақ бұл әрдайым бола ма, жоқ па белгісіз.

Хадамар байланған (барлығы үшін) n)

Хадамардың байланысы | det ескерту арқылы шығарылуы мүмкінR| = (детG)1/2 ≤ (дет.)nI)1/2 = nn/2, бұл байқаудың салдары болып табылады nI, қайда Мен болып табылады n арқылы n сәйкестік матрицасы, 1-4 қасиеттерін қанағаттандыратын матрицалар арасындағы максималды детерминанттың ерекше матрицасы. Бұл детR бүтін 2-ге еселік болуы керекn−1 Хадамардың байланысы әрдайым қол жетімді еместігін тағы бір демонстрациялау үшін пайдалануға болады. Қашан n тақ, шектеулі nn/2 не бүтін емес, не тақ, сондықтан қол жетімді емес жағдайларды қоспағанда n = 1. Қашан n = 2к бірге к тақ, Хадамардың шекарасын бөлетін 2-нің ең жоғарғы қуаты 2-ге теңк бұл 2-ден азn−1 егер болмаса n = 2. Демек, Хадамардың байланысы мүмкін емес, егер n = 1, 2 немесе 4-ке еселік.

Барба міндетті n тақ

Қашан n тақ болса, Грам матрицалары үшін 1 қасиетін күшейтуге болады

  1. G тақ-бүтін матрица.

Бұл жоғарғы шекараны анықтауға мүмкіндік береді[4] алынуы керек: | detR| = (детG)1/2 ≤ (дет (n-1)Мен+Дж)1/2 = (2n−1)1/2(n−1)(n−1)/2, қайда Дж бұл бәріне арналған матрица. Мұнда (n-1)Мен+Дж өзгертілген 1 қасиеті мен 2-4 қасиеттерін қанағаттандыратын максималды-детерминант матрица. Бұл кез-келген жолдар жиынтығын және сәйкес бағандар жиынтығын −1 көбейтуге дейін ерекше. Шектеуге жету мүмкін емес, егер 2n−1 - бұл керемет квадрат, сондықтан ешқашан қол жетімді емес n ≡ 3 (мод 4).

Эхлич-Войтас бағытталды n ≡ 2 (мод 4)

Қашан n жолдарының жиынтығы R екі жиынға бөлуге болады.

  • Қатарлары тіпті теріңіз элементтердің жұп саны 1 және an1 элементтерінің жұп саны бар.
  • Қатарлары тақ түрі элементтердің тақ саны 1 және тақ элементтер саны −1 болуы керек.

Бір типтегі екі қатардың нүктелік көбейтіндісі сәйкес келеді n (мод 4); қарама-қарсы типтегі екі қатардың нүктелік көбейтіндісі сәйкес келеді n+2 (мод 4). Қашан n ≡ 2 (mod 4), бұл дегеніміз, жолдарын ауыстыру арқылы R, деп болжауға болады стандартты форма,

қайда A және Д. элементтері 2 (mod 4) мен сәйкес келетін симметриялық бүтін матрицалар B - бұл элементтері 0-ге сәйкес келетін матрица (mod 4). 1964 жылы Эхлич[5] және Войтас[6] дербес көрсеткендей, осы форманың максималды детерминант матрицасында, A және Д. екеуі де мөлшерде n/ 2 және тең (n−2)Мен+2Дж уақыт B нөлдік матрица. Бұл оңтайлы форма кез-келген жолдар жиынтығын және бағандардың сәйкес жиынтығын −1-ге көбейтуге және жолдар мен бағандарға бір мезгілде орын ауыстыруды қолдануға дейін ерекше. Бұл байланысты детаны білдіредіR ≤ (2n−2)(n−2)(n−2)/2. Эхлич егер ол көрсетсе R шекарасына жетеді, ал егер жолдары мен бағандары болса R екеуіне де рұқсат етілген G = RRТ және G′ = RТR стандартты формасы бар және сәйкесінше қалыпқа келтірілген, содан кейін біз жаза аламыз

қайда W, X, Y, және З болып табылады (n/2)×(n/ 2) тұрақты және жолды қосындылары бар матрицалар w, х, ж, және з бұл қанағаттандырады з = −w, ж = х, және w2+х2 = 2n−2. Демек, Эхлич-Войтас байланысы 2-ге дейін орындалмайдыn−2 екі квадраттың қосындысы ретінде көрінеді.

Эхлич байланысты n ≡ 3 (мод 4)

Қашан n тақ болса, онда жолдарды −1-ге көбейту еркіндігін пайдаланып, әрбір жолдың шартты қойылуы мүмкін R элементтердің жұп саны 1 және тақ элементтер саны −1 болады. Көрсетуге болады, егер бұл нормалану қабылданса, онда 1-дің қасиеті G күшейтілуі мүмкін

  1. G - бүтін элементтері сәйкес келетін матрица n (мод 4).

Қашан n ≡ 1 (mod 4), оңтайлы Барба формасы осы күшті қасиетті қанағаттандырады, бірақ қашан n ≡ 3 (мод 4), олай емес. Бұл дегеніміз, соңғы жағдайда шекараны анықтауға болады. Эхлич[7] қашан екенін көрсетті n ≡ 3 (mod 4), күшейтілген қасиет 1-нің максималды-детерминантты түрін білдіреді G деп жазуға болады BДж қайда Дж бұл барлығына арналған матрица және B Бұл блок-диагональды матрица оның диагональды блоктары формада (n-3)Мен+4Дж. Оның үстіне, ол оңтайлы түрде блоктар санын, с, байланысты n төмендегі кестеде көрсетілгендей және әрбір блоктың өлшемдері бар р немесе өлшем r + 1 қайда

nс
33
75
115 немесе 6
15 − 596
≥ 637

Қоспағанда n= 11, егер екі мүмкіндік болса, оңтайлы форма кез-келген жолдар жиынтығын және сәйкес бағандар жиынтығын −1-ге көбейтуге және жолдар мен бағандарға бір уақытта ауыстыруды қолдану үшін ерекше болады. Бұл оңтайлы форма шектеуге әкеледі

қайда v = nrs - бұл блоктардың саны р+1 және сен =сv - бұл блоктардың саны р. Кон[8] байланысты байланыстырып талдады және одан бөлек екенін анықтады n = 3, бұл тек үшін бүтін сан n = 112т2±28тОң сан үшін +7 т. Тамура[9] көмегімен байланыстырудың қол жетімділігіне қосымша шектеулер алынды Хассе-Минковский теоремасы квадраттық формалардың рационалды эквиваленттілігі туралы және ең кіші екенін көрсетті n > 3 үшін Эхличтің байланысы 511 құрайды.

21 өлшеміне дейінгі максималды детерминанттар

{1, −1} матрицаларының өлшемдеріне дейінгі максималды детерминанттары n = 21 келесі кестеде келтірілген.[10] 22 өлшемі - бұл ең кішкентай ашық қорап. Кестеде, Д.(n) 2-ге бөлінген максималды анықтаушыны білдіредіn−1. Эквивалентті, Д.(n) өлшемнің {0, 1} матрицасының максималды детерминантын білдіреді n−1.

nД.(n)Ескертулер
11Хадамард матрицасы
21Хадамард матрицасы
31Ehlich жетеді
42Хадамард матрицасы
53Барбаға жетеді; циркуляциялық матрица
65Ehlich – Wojtas жетеді
79Эхличтің 98,20% байланысты
832Хадамард матрицасы
956Барбаның 84,89% байланысты
10144Ehlich – Wojtas жетеді
11320Эхличтің 94,49%; үш эквивалентті емес матрица
121458Хадамард матрицасы
133645Барбаға жетеді; максималды-детерминантты матрица - {1, −1} -тің түсу матрицасы проективті жазықтық 3 бұйрық
149477Ehlich – Wojtas жетеді
1525515Эхличтің 97,07% -ы байланысты
16131072Хадамард матрицасы; бес эквивалентті емес матрица
17327680Барбадан 87,04%; үш эквивалентті емес матрица
181114112Ehlich – Wojtas жетеді; үш эквивалентті емес матрица
193411968Эхличтің 97,50% жетеді; үш эквивалентті емес матрица
2019531250Хадамард матрицасы; үш эквивалентті емес матрица
2156640625Барбадан 90,58%; жеті эквивалентті емес матрица

Әдебиеттер тізімі

  1. ^ Хадамард, Дж. (1893), «Résolution d'une question салыстырмалы aux déterminants», Математика бюллетені, 17: 240–246
  2. ^ Сильвестр, Дж. Дж. (1867), «Ньютон ережесіне, декоративті плиткалар мен сандар теориясына қосымшалары бар, кері ортогональ матрицалар, бір мезгілде белгі сабақтастықтары және екі немесе одан да көп түстердегі жасушалы тротуарлар туралы ойлар», Лондон Эдинбург Дублин Фил. Маг. Дж., 34: 461–475
  3. ^ Галил, З .; Кифер, Дж. (1980), «Д.- өлшеудің оңтайлы құрылымдары », Энн. Стат., 8: 1293–1306, дои:10.1214 / aos / 1176345202
  4. ^ Барба, Гвидо (1933), «Intorno al teorema di Hadamard sui determinanti a valore massimo», Джорн. Мат Баттаглини, 71: 70–86.
  5. ^ Эхлич, Хартмут (1964), «Determinantenabschätzungen für binäre Matrizen», Математика. З., 83: 123–132, дои:10.1007 / BF01111249.
  6. ^ Войтас, М. (1964), «4-ке бөлінбейтін тәртіптің детерминанттары үшін Хадамардың теңсіздігі туралы», Коллок. Математика., 12: 73–83.
  7. ^ Эхлич, Хартмут (1964), «Determinantenabschätzungen für binäre Matrizen mit n Mod 3 модуль 4 «, Математика. З., 84: 438–447, дои:10.1007 / BF01109911.
  8. ^ Cohn, J. H. E. (2000), «D-оңтайлы жобалар», Utilitas математикасы., 57: 121–128.
  9. ^ Тамура, Хироки (2006), «D-оңтайлы дизайн және топқа бөлінетін дизайн», Комбинаторлық дизайн журналы, 14: 451–462, дои:10.1002 / jcd.20103.
  10. ^ Слоан, Н. (ред.). «A003432 реттілігі (Хадамардтың максималды детерминанты есебі: а (нақты) ең үлкен детерминанты {0,1} - матрицасы n.)» «. The Он-лайн тізбегінің энциклопедиясы. OEIS қоры.