WikiDer > Задача о максимальной детерминанте Адамара - Википедия

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

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

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

В дизайн экспериментов в статистика использует {1, −1} матриц Икс (не обязательно квадрат), для которого информационная матрица Икс^ТИкс имеет максимальный определитель. (Обозначение Икс^Т обозначает транспонировать из Икс.) Такие матрицы известны как D-оптимальные конструкции.^[3] Если Икс это квадратная матрица, он известен как насыщенный D-оптимальный дизайн.

Матрицы Адамара

Любые два ряда п×п Матрицы Адамара являются ортогональный. Для матрицы {1, −1} это означает, что любые две строки отличаются ровно половиной элементов, что невозможно, когда п является нечетное число. Когда п 2 (mod 4), две строки, которые обе ортогональны третьей строке, не могут быть ортогональны друг другу. Вместе эти утверждения означают, что п×п Матрица Адамара может существовать, только если п = 1, 2 или кратное 4. Матрицы Адамара хорошо изучены, но неизвестно, является ли п×п Матрица Адамара существует для каждого п это положительное число, кратное 4. Наименьшее п для чего п×п Матрица Адамара неизвестна - 668.

Эквивалентность и нормализация матриц {1, −1}

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

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

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

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

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

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

Пример:

${ 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} является целым числом, определитель матрицы п×п Матрица {1, −1} является целым числом, кратным 2^п−1.

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

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

Позволять р быть п к п {1, −1} матрица. В Матрица Грама из р определяется как матрица грамм = RR^Т. Из этого определения следует, что грамм

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

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

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

Границу Адамара можно получить, отметив, что | detр| = (detграмм)^1/2 ≤ (detnI)^1/2 = п^п/2, что является следствием наблюдения, что nI, куда я это п к п единичная матрица, - единственная матрица максимального определителя среди матриц, удовлетворяющих свойствам 1–4. Это детр должно быть целым числом, кратным 2^п−1 может использоваться, чтобы еще раз продемонстрировать, что ограничение Адамара не всегда достижимо. Когда п нечетно, оценка п^п/2 либо нецелое, либо нечетное, и поэтому недостижимо, кроме случаев, когда п = 1. Когда п = 2k с k нечетно, наибольшая степень двойки, делящей границу Адамара, равна 2^k что меньше 2^п−1 пока не п = 2. Следовательно, оценка Адамара недостижима, если п = 1, 2 или кратное 4.

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

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

1. грамм является нечетно-целочисленной матрицей.

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

Граница Элиха – Войтаса для п ≡ 2 (мод 4)

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

• Ряды даже тип содержат четное количество элементов 1 и четное количество элементов −1.
• Ряды странный тип содержат нечетное количество элементов 1 и нечетное количество элементов -1.

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

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

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

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

куда W, Икс, Y, и Z находятся (п/2)×(п/ 2) матрицы с постоянными суммами по строкам и столбцам ш, Икс, у, и z это удовлетворяет z = −ш, у = Икс, и ш²+Икс² = 2п−2. Следовательно, оценка Элиха – Войтаса недостижима, если 2п−2 выражается как сумма двух квадратов.

Элих готовится к п ≡ 3 (мод 4)

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

1. грамм - матрица с целыми элементами, конгруэнтными п (мод 4).

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

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

${ displaystyle det R Leq (n-3) ^ {(ns) / 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 = п−RS количество блоков размера р+1 и ты =s−v количество блоков размера р. Кон^[8] проанализировал границу и определил, что, помимо п = 3, это целое число только для п = 112т²±28т+7 для некоторого положительного целого числа т. Тамура^[9] выведены дополнительные ограничения на достижимость оценки с помощью Теорема Хассе-Минковского о рациональной эквивалентности квадратичных форм и показал, что наименьшее п > 3, для которых оценка Элиха предположительно достижима, равно 511.

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

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

Рекомендации