Задача Адамара о максимальном определителе

Математическая задача

Задача Адамара о максимальном определителе , названная в честь Жака Адамара , требует найти наибольший определитель матрицы с элементами, равными 1 или −1. Аналогичный вопрос для матриц с элементами, равными 0 или 1, эквивалентен, поскольку, как будет показано ниже, максимальный определитель матрицы {1,−1} размера n равен 2 ^{n −1} , умноженному на максимальный определитель матрицы {0,1} размера n −1. Задача была поставлена ​​Адамаром в статье 1893 года ^[1] , в которой он представил свою знаменитую границу определителя , и остается нерешенной для матриц общего размера. Граница Адамара подразумевает, что {1, −1}-матрицы размера n имеют определитель не более n ^{n /2} . Адамар заметил, что конструкция Сильвестра ^[2] дает примеры матриц, которые достигают границы, когда n является степенью 2, и привел собственные примеры размеров 12 и 20. Он также показал, что граница достижима только тогда, когда n равно 1, 2 или кратно 4. Дополнительные примеры были позже построены Скарписом и Пейли, а затем и многими другими авторами. Такие матрицы теперь известны как матрицы Адамара . Они подверглись интенсивному изучению.

Размеры матриц n, для которых n  ≡ 1, 2 или 3 (mod 4), получили меньше внимания. Самые ранние результаты принадлежат Барбе, который ужесточил границу Адамара для нечетных n , и Уильямсону, который нашел наибольшие определители для n = 3, 5, 6 и 7. Некоторые важные результаты включают

• более строгие границы, полученные Барбой, Элихом и Войтасом для n  ≡ 1, 2 или 3 (mod 4), которые, однако, как известно, не всегда достижимы,
• несколько бесконечных последовательностей матриц, достигающих границ при n  ≡ 1 или 2 (mod 4),
• число матриц, достигающих границ для конкретных n  ≡ 1 или 2 (mod 4),
• ряд матриц, не достигающих границ для конкретных n  ≡ 1 или 3 (mod 4), но для которых с помощью исчерпывающих вычислений доказано, что они имеют максимальный определитель.

Планирование экспериментов в статистике использует матрицы X (не обязательно квадратные) {1, −1}, для которых информационная матрица X ^T X имеет максимальный определитель. (Обозначение X ^T обозначает транспонирование 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}

Любая из следующих операций, выполняемая над матрицей R типа {1, −1} , изменяет определитель R только на знак минус:

• Отрицание ряда.
• Отрицание столбца.
• Перестановка двух рядов.
• Перестановка двух колонок.

Две матрицы {1,−1}, R ₁ и R ₂ , считаются эквивалентными , если R ₁ можно преобразовать в R ₂ некоторой последовательностью вышеприведенных операций. Определители эквивалентных матриц равны, за исключением, возможно, смены знака, и часто удобно стандартизировать R с помощью отрицаний и перестановок строк и столбцов. Матрица {1,−1} нормализована, если все элементы в ее первой строке и столбце равны 1. Когда размер матрицы нечетный, иногда полезно использовать другую нормализацию, в которой каждая строка и столбец содержат четное число элементов 1 и нечетное число элементов −1. Любая из этих нормализаций может быть выполнена с помощью первых двух операций.

Связь задач максимального определителя для матриц {1, −1} и {0, 1}

Существует однозначное отображение из набора нормализованных матриц n × n {1, −1} в набор матриц ( n −1) × ( n -1) {0, 1}, при котором величина определителя уменьшается в 2 раза ^{1− n} . Это отображение состоит из следующих шагов.

1. Вычтите строку 1 матрицы {1, −1} из строк со 2 по n . (Это не изменит определитель.)
2. Извлечь подматрицу ( n −1)×( n −1), состоящую из строк со 2 по n и столбцов со 2 по n . Эта матрица имеет элементы 0 и −2. (Определитель этой подматрицы такой же, как и у исходной матрицы, как можно увидеть, выполнив разложение кофакторов в столбце 1 матрицы, полученной на шаге 1.)
3. Разделим подматрицу на −2, чтобы получить матрицу {0, 1}. (Это умножает определитель на (−2) ^{1− n} .)

Пример:

${\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}}}$

В этом примере исходная матрица имеет определитель −16, а ее образ имеет определитель 2 = −16·(−2) ⁻³ .

Поскольку определитель матрицы {0, 1} является целым числом, определитель матрицы n × n {1, −1} является целым числом, кратным 2 ^{n −1} .

Верхние границы максимального определителя

Матрица Грама

Пусть R — матрица n на n {1, −1}. Матрица Грама для R определяется как матрица G  =  RR ^T . Из этого определения следует, что G

1. — целочисленная матрица,
2. симметричен ,​
3. является положительно-полуопределенным ,
4. имеет постоянную диагональ, значение которой равно n .

Отрицание строк R или применение к ним перестановки приводит к тому, что те же отрицания и перестановки применяются как к строкам, так и к соответствующим столбцам G . Мы также можем определить матрицу G ′= R ^T R . Матрица G является обычной матрицей Грама набора векторов, полученной из набора строк R , в то время как G ′ является матрицей Грама, полученной из набора столбцов R . Матрица R , для которой G  =  G ′, является нормальной матрицей . Каждая известная максимально-детерминантная матрица эквивалентна нормальной матрице, но неизвестно, всегда ли это так.

Граница Адамара (для всех)н)

Граница Адамара может быть получена, если заметить, что |det  R | = (det  G ) ^1/2  ≤ (det  nI ) ^1/2  =  n ^{n /2} , что является следствием наблюдения, что nI , где I — единичная матрица размера n на n , является единственной матрицей максимального определителя среди матриц, удовлетворяющих свойствам 1–4. То, что det  R должен быть целым числом, кратным 2 ^{n −1,} можно использовать для еще одной демонстрации того, что граница Адамара не всегда достижима. Если n нечетно, то граница n ^{n /2} либо нецелая, либо нечетная, и поэтому недостижима, за исключением случая, когда n  = 1. Если n  = 2 k , где k нечетно, то наивысшая степень числа 2, делящая границу Адамара, равна 2 ^k , что меньше 2 ^{n −1,} если только n  = 2. Следовательно, граница Адамара недостижима, если только n  = 1, 2 или кратно 4.

Барба направляется внстранный

Когда n нечетно, свойство 1 для матриц Грама можно усилить до

1. G — нечетно-целая матрица.

Это позволяет вывести  более точную верхнюю границу ^{[4] : ​​|det} R | = (det  G ) ^1/2  ≤ (det ( n -1) I + J ) ^1/2  = (2 n −1) ^1/2 ( n −1) ^{( n −1)/2} , где J — матрица, состоящая из всех единиц. Здесь ( n -1) I + J — матрица с максимальным детерминантом, удовлетворяющая модифицированному свойству 1 и свойствам 2–4. Она единственна с точностью до умножения любого набора строк и соответствующего набора столбцов на −1. Граница недостижима, если только 2 n −1 не является полным квадратом, и, следовательно, никогда не достижима, когда n  ≡ 3 (mod 4).

Элих-Войтас направляется вн ≡ 2 (мод 4)

Если n четное, множество строк R можно разбить на два подмножества.

• Строки четного типа содержат четное число элементов 1 и четное число элементов −1.
• Строки нечетного типа содержат нечетное количество элементов 1 и нечетное количество элементов −1.

Скалярное произведение двух строк одного типа сравнимо с n (mod 4); скалярное произведение двух строк противоположного типа сравнимо с n +2 (mod 4). Когда n  ≡ 2 (mod 4), это означает, что, переставляя строки R , мы можем принять стандартную форму ,

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

где A и D — симметричные целочисленные матрицы, элементы которых сравнимы с 2 (mod 4), а B — матрица, элементы которой сравнимы с 0 (mod 4). В 1964 году Элих ^[5] и Войтас ^[6] независимо показали, что в максимальной детерминантной матрице этой формы A и D имеют размер n /2 и равны ( n −2) I +2 J , в то время как B — нулевая матрица. Эта оптимальная форма единственна с точностью до умножения любого набора строк и соответствующего набора столбцов на −1 и одновременного применения перестановки к строкам и столбцам. Это подразумевает границу det  R  ≤ (2 n −2)( n −2) ^{( n −2)/2} . Элих показал, что если R достигает границы и если строки и столбцы R переставлены так, что и G  =  RR ^T, и G ′ =  R ^T R имеют стандартную форму и соответствующим образом нормализованы, то мы можем записать

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

где W , X , Y и Z — матрицы ( n /2)×( n /2) с постоянными суммами строк и столбцов w , x , y и z, удовлетворяющие соотношениям z  = − w , y  =  x и w ² + x ²  = 2 n −2. Следовательно, граница Элиха–Войтаса недостижима, если 2 n −2 не выражается как сумма двух квадратов.

Элих направляется вн ≡ 3 (мод 4)

Когда n нечетно, то, используя свободу умножения строк на −1, можно наложить условие, что каждая строка R содержит четное число элементов 1 и нечетное число элементов −1. Можно показать, что если предположить эту нормализацию, то свойство 1 G может быть усилено до

1. G — матрица с целыми элементами, сравнимыми с n (mod 4).

Когда n  ≡ 1 (mod 4), оптимальная форма Барбы удовлетворяет этому более сильному свойству, но когда n  ≡ 3 (mod 4), она этого не делает. Это означает, что в последнем случае границу можно усилить. Элих ^[7] показал, что когда n  ≡ 3 (mod 4), усиленное свойство 1 подразумевает, что максимально-детерминантная форма G может быть записана как B − J , где J — матрица из всех единиц, а B — блочно-диагональная матрица , диагональные блоки которой имеют вид ( n -3) I +4 J . Более того, он показал, что в оптимальной форме количество блоков s зависит от n , как показано в таблице ниже, и что каждый блок имеет либо размер r , либо размер r+1, где ${\displaystyle r=\lfloor n/s\rfloor .}$

За исключением n = 11, где есть две возможности, оптимальная форма единственна с точностью до умножения любого набора строк и соответствующего набора столбцов на −1 и одновременного применения перестановки к строкам и столбцам. Эта оптимальная форма приводит к границе

${\displaystyle \det R\leq (n-3)^{(n-s)/2}(n-3+4r)^{u/2}(n+1+4r)^{v/2}\left[1-{\frac {ur}{n-3+4r}}-{\frac {v(r+1)}{n+1+4r}}\right]^{1/2},}$

где v  =  n − rs — число блоков размера r +1, а u  = s − v — число блоков размера r . Кон ^[8] проанализировал границу и определил, что, помимо n  = 3, она является целым числом только для n  = 112 t ² ±28 t +7 для некоторого положительного целого числа t . Тамура ^[9] вывел дополнительные ограничения на достижимость границы, используя теорему Хассе–Минковского о рациональной эквивалентности квадратичных форм, и показал, что наименьшее n  > 3, для которого граница Элиха предположительно достижима, равно 511.

Максимальные детерминанты до размера 21

Максимальные определители матриц {1, −1} до размера n  = 21 приведены в следующей таблице. ^[10] Размер 22 — наименьший открытый случай. В таблице D ( n ) представляет максимальный определитель, деленный на 2 ^{n −1} . Эквивалентно, D ( n ) представляет максимальный определитель матрицы {0, 1} размера n −1.

Ссылки

1. Адамар, Ж. (1893), «Решение вопроса относительно детерминантов», Bulletin des Sciences Mathématiques , 17 : 240–246
2. Сильвестр, Дж. Дж. (1867), «Мысли об обратных ортогональных матрицах, одновременных последовательностях знаков и мозаичных покрытиях двух или более цветов с приложениями к правилу Ньютона, орнаментальной плитке и теории чисел», Лондон Эдинбург Дублин Фил. Маг. J. Sci. , 34 (232): 461–475, doi :10.1080/14786446708639914
3. Галил, З.; Кифер, Дж. (1980), « D -оптимальные конструкции взвешивания», Ann. Стат. , 8 (6): 1293–1306, doi : 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", Math. З. , 83 : 123–132, номер документа : 10.1007/BF01111249, S2CID  120916607.
6. Войтас, М. (1964), «О неравенстве Адамара для определителей порядка, не делящегося на 4», Colloq. Math. , 12 : 73–83, doi : 10.4064/cm-12-1-73-83.
7. Элих, Хартмут (1964), "Determinantenabschätzungen für binäre Matrizen mit n  ≡ 3 mod 4", Math. З. , 84 : 438–447, номер документа : 10.1007/BF01109911, S2CID  116683967.
8. Кон, Дж. Х. Э. (2000), «Почти D-оптимальные конструкции», Utilitas Math. , 57 : 121–128.
9. Тамура, Хироки (2006), «D-оптимальные планы и групповые делимые планы», Журнал комбинаторных планов , 14 (6): 451–462, doi :10.1002/jcd.20103.
10. Слоан, Н. Дж. А. (ред.). "Последовательность A003432 (задача максимального определителя Адамара: наибольший определитель (действительной) {0,1}-матрицы порядка n.)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.