Максимальный определитель проблема Адамар , названная в честь Жака Адамар , просит наибольший определитель в виде матрицы с элементами , равные 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 равно 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), но которые были доказаны исчерпывающими вычислениями как имеющие максимальный определитель.
Дизайн экспериментов в статистике использует {1, -1} матрицы 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}
Любая из следующих операций, выполняемая с матрицей R {1, −1} , изменяет определитель R только на знак минус:
- Отрицание ряда.
- Отрицание столбика.
- Чередование двух рядов.
- Обмен двух колонн.
Две матрицы {1, -1}, R 1 и R 2 , считаются эквивалентными, если R 1 может быть преобразован в R 2 некоторой последовательностью вышеуказанных операций. Определители эквивалентных матриц равны, за исключением, возможно, смены знака, и часто удобно стандартизировать 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} из строк со 2 по n . (Это не меняет определителя.)
- Извлеките подматрицу ( n −1) × ( n −1), состоящую из строк со 2 по n и столбцов со 2 по n . Эта матрица имеет элементы 0 и −2. (Определитель этой подматрицы такой же, как и у исходной матрицы, что можно увидеть, выполнив расширение кофактора в столбце 1 матрицы, полученной на шаге 1.)
- Разделите подматрицу на −2, чтобы получить матрицу {0, 1}. (Это умножает определитель на (−2) 1− n .)
Пример:
В этом примере исходная матрица имеет определитель −16, а ее изображение имеет определитель 2 = −16 · (−2) −3 .
Поскольку определитель матрицы {0, 1} является целым числом, определитель матрицы n × n {1, −1} является целым числом, кратным 2 n −1 .
Верхние оценки максимального определителя
Матрица Грама
Пусть R быть п по п {1, -1} матрица. Матрица Грама из R определяется как матрица G = RR Т . Из этого определения следует, что G
- целочисленная матрица,
- является симметричным ,
- является положительным полуопределенной ,
- имеет постоянную диагональ, значение которой равно n .
Отрицание строки R или применения перестановки к ним приводит в тех же самых отрицаниях и перестановка применяется как к строкам, а также соответствующим столбцы, из G . Мы также можем определить матрицу G '= R T R . Матрица G является обычной матрицей Грама множества векторов, полученным из множества рядов R , в то время как G 'является матрица Грама , полученная из множества столбцов R . Матрица R, для которой G = G ′, является нормальной матрицей . Каждая известная матрица с максимальным определением эквивалентна нормальной матрице, но неизвестно, всегда ли это так.
Граница Адамара (для всех n )
Оценка Адамара может быть получена, если заметить, что | det R | = (det G ) 1/2 ≤ (det nI ) 1/2 = n n / 2 , что является следствием наблюдения, что nI , где I - единичная матрица n на n , является единственной матрицей максимального определителя среди матрицы, удовлетворяющие свойствам 1–4. То, что det R должно быть целым числом, кратным 2 n -1, можно использовать для другой демонстрации того, что граница Адамара не всегда достижима. При п нечетно, то связанный п п / 2 является либо нецелым или нечетным, и поэтому недостижимы , за исключением когда это п = 1. При п = 2 к с к нечетной, самая высокая степень 2 деления Адамара граница 2 к которой меньше 2 n −1, если не n = 2. Следовательно, оценка Адамара недостижима, если n = 1, 2 или кратное 4.
Барба это связано для п нечетное
Когда n нечетно, свойство 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).
Оценка Элиха – Войтаса для n 2 (mod 4)
Когда n четно, набор строк R можно разделить на два подмножества.
- Строки четного типа содержат четное количество элементов 1 и четное количество элементов −1.
- Строки нечетного типа содержат нечетное количество элементов 1 и нечетное количество элементов -1.
Скалярное произведение двух строк одного и того же типа конгруэнтно n (mod 4); скалярное произведение двух строк противоположного типа конгруэнтно n +2 (mod 4). Когда n ≡ 2 (mod 4), это означает, что, переставляя строки R , мы можем принять стандартную форму ,
где 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 имеют стандартную форму и соответствующим образом нормализованы, то мы можем написать
где W , X , Y и Z представляют собой ( n / 2) × ( n / 2) -матрицы с постоянными суммами по строкам и столбцам w , x , y и z, которые удовлетворяют z = - w , y = x и w 2 + х 2 = 2 п -2. Следовательно, оценка Элиха – Войтаса недостижима, если 2 n −2 не выражается в виде суммы двух квадратов.
Оценка Элиха для n 3 (mod 4)
Когда n нечетно, тогда, используя свободу умножения строк на -1, можно наложить условие, что каждая строка R содержит четное количество элементов 1 и нечетное количество элементов -1. Можно показать, что если допустить эту нормировку, то свойство 1 группы G можно усилить до
- G - матрица с целыми элементами, конгруэнтными n (mod 4).
Когда n 1 (mod 4), оптимальная форма Barba удовлетворяет этому более сильному свойству, но когда n 3 (mod 4), это не так. Это означает, что в последнем случае оценку можно уточнить. Элих [7] показал, что, когда n 3 (mod 4), усиленное свойство 1 означает, что форма с максимальным определением G может быть записана как B - J, где J - матрица всех единиц, а B - блочно-диагональная матрица , диагональные блоки имеют вид ( п -3) Я +4 , J . Более того, он показал, что в оптимальной форме количество блоков s зависит от n, как показано в таблице ниже, и что каждый блок имеет либо размер r, либо размер r + 1, где
п | s |
---|---|
3 | 3 |
7 | 5 |
11 | 5 или 6 |
15–59 | 6 |
≥ 63 | 7 |
За исключением n = 11, где есть две возможности, оптимальная форма уникальна до умножения любого набора строк и соответствующего набора столбцов на -1 и до одновременного применения перестановки к строкам и столбцам. Эта оптимальная форма приводит к оценке
где v = n - rs - количество блоков размера r +1, а u = s - v - количество блоков размера r . Кон [8] проанализировал границу и определил, что, помимо n = 3, это целое число только для n = 112 t 2 ± 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.
п | D ( п ) | Заметки |
---|---|---|
1 | 1 | Матрица Адамара |
2 | 1 | Матрица Адамара |
3 | 1 | Достигает границы Элиха |
4 | 2 | Матрица Адамара |
5 | 3 | Достигает границы Барбы; циркулянтная матрица |
6 | 5 | Достигает границы Элиха – Войтаса |
7 | 9 | 98,20% связанного Ehlich |
8 | 32 | Матрица Адамара |
9 | 56 | 84,89% границы Барбы |
10 | 144 | Достигает границы Элиха – Войтаса |
11 | 320 | 94,49% связанного Ehlich; три неэквивалентные матрицы |
12 | 1458 | Матрица Адамара |
13 | 3645 | Достигает границы Барбы; матрица с максимальным определением - это {1, −1} матрица инцидентности проективной плоскости порядка 3 |
14 | 9477 | Достигает границы Элиха – Войтаса |
15 | 25515 | 97,07% связанного Ehlich |
16 | 131072 | Матрица Адамара; пять неэквивалентных матриц |
17 | 327680 | 87,04% связанного Барба; три неэквивалентные матрицы |
18 | 1114112 | Достигает границы Элиха – Войтаса; три неэквивалентные матрицы |
19 | 3411968 | Достигает 97,50% ограничения Ehlich; три неэквивалентные матрицы |
20 | 19531250 | Матрица Адамара; три неэквивалентные матрицы |
21 год | 56640625 | 90,58% связанного Барба; семь неэквивалентных матриц |
Рекомендации
- ↑ Адамар, Дж. (1893), «Решение вопросов относительно детерминантов», Bulletin des Sciences Mathématiques , 17 : 240–246
- ^ Сильвестр, Дж. Дж. (1867), «Мысли об обратных ортогональных матрицах, одновременной последовательности знаков и мозаичных покрытиях двух или более цветов с приложениями к правилу Ньютона, декоративной плитке и теории чисел», Лондон, Эдинбург, Дублин, Фил. Mag. J. Sci. , 34 : 461–475
- ^ Галил, З .; Кифер, Дж. (1980), " D- оптимальные схемы взвешивания", Ann. Стат. , 8 : 1293-1306, DOI : 10,1214 / AOS / 1176345202
- ^ Барба, Гвидо (1933), "Intorno al teorema di Hadamard suiterminanti a valore massimo", Giorn. Мат. Баттаглини , 71 : 70–86.
- ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Math. З. , 83 : 123-132, DOI : 10.1007 / BF01111249.
- ^ Войтас, М. (1964), "О неравенстве Адамара для определителей порядка, не делимого на 4", Коллок. Математика. , 12 : 73–83.
- ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n 3 mod 4", Math. З. , 84 : 438-447, DOI : 10.1007 / BF01109911.
- ^ Кон, JHE (2000), "Почти D-оптимальные планы", Utilitas Math. , 57 : 121–128.
- ^ Тамура, Хироки (2006), "D-оптимальных конструкций и группа делимые конструкции", журнал комбинаторной Designs , 14 : 451-462, DOI : 10.1002 / jcd.20103.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A003432 (задача о максимальном детерминанте Адамара: наибольший определитель (действительной) {0,1} -матрицы порядка n.)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.