МАКСИМАЛЬНЫЙ ОПРЕДЕЛИТЕЛЬ



© Nickolay A. Balonin 22.04.2015
Keywords: maximal determinant problem, Hadamard matrices


Матрицы максимума детерминанта – квадратные вещественные матрицы порядка n с ограниченными 1-ей по амплитуде элементами и экстремальным (самым большим по абсолютному значению) детерминантом среди детерминантов матриц того же размера. Это матрицы сходные с ортогональными по столбцам и строкам матрицами Адамара – матрицами максимума детерминанта на порядках 1, 2 и n=4t, t – целое число, в том, что их элементами могут быть только числа 1 и –1.

Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 2016. № 1. С. 2–15.

Матрицы максимума детерминанта четных порядков устроены относительно несложно, сказывается парный размер, они тяготеют к бициклической структуре, известно довольно много таких матриц.

Матрицы максимума детерминанта нечетных порядков, напротив, изучены недостаточно полно, среди них мало матриц простой структуры.

Матрицы нечетных порядков распадаются на семейства. Принцип бесконечного их разнообразия, который мы сформулируем более точно и проиллюстрируем ниже, приводит к тому, что семейства сходных между собой матриц, они небольшие. Семейство циклических матриц, например, состоит (никто ранее не высказывал этого предположения, выскажем его) из трех представителей: 3, 5, 13, см. рис. 1. Элементы 1 отображены клетками белого цвета.



Циклические матрицы максимума детерминанта порядков 3, 5, 13



Некоторые общие мотивы обустройства циклических (и бициклических) матриц максимума детерминанта и матриц Адамара просматриваются. Отметим, что согласно гипотезе Ризера порядок циклических матриц Адамара не превышает 4. Гипотеза до сих пор не доказана. Таким образом, нечетные матрицы подымают эту планку до характерного критического порядка 13. Корреляция отмеченных порядков 4, 5, 13 с длинами пар 2, 10, 26 последовательностей Голея, порождающих бициклические конструкции матриц Адамара, очевидна.

Помимо семейства циклических матриц максимума детерминанта есть моноциклы с каймой из 1 порядков первых двух простых чисел Мерсенна 3, 7 (они же – бициклы без инверсии знака вида [A B; B A] с каймой), см. рис. 2.



Циклические с каймой матрицы максимума детерминанта порядков 3, 7



Моноциклы Мерсенна, так их будем называть, заканчиваются на первом составном порядке 15, который соответствующую матрицу данной конструкции не порождает, на порядке 31 и последующих простых порядках матрицы данного семейства также не обнаруживаются. Семейство матриц порядков Ферма, соответственно, должно базироваться на первых пяти простых числах Ферма, раскроем это положение несколько полнее.

Семейству моноциклов Мерсенна вторит семейство бициклических матриц (тоже, с каймой) Ферма вида порядков 3, 5, 17, 257, 65537, повторяющих первые простые числа Ферма, здесь e – вектор из 1. Экстремальные свойства первых трех матриц малых порядков не вызывают сомнения, см. рис. 3.



Бициклические матрицы Ферма порядков 3, 5, 17



Для того, чтобы наш обзор матриц максимума детерминанта нечетных порядков был полон, мы приведем еще несколько начальных матричных портретов, в которых несложно выловить закономерность, которая препятствует их нахождению на высоких порядках. А именно, сложность структуры матрицы нарастает вместе с порядком. Возьмем для примера пропущенные в семействах матрицы порядков 9, 11, 15, рис. 4.



Сложные матрицы максимума детерминанта порядков 9, 11, 15



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

Блочная кайма изобилует неповторяющимися у всех трех матриц деталями – для их поиска пришлось применить переборную программу под красноречивым названием “калейдоскоп”. Она синтезирует матрицы максимума детерминанта, заполняя содержимое части циклических блоков прямоугольными вложениями. Даже на низких порядках времени на поиск оптимальной структуры уходит порядком.

Первая матрица существенно отличается от второй стартовым блоком каймы. Третья матрица отличается от обоих инверсией знаков на диагонали блока Мерсенна с образованием четырех симметрично расположенных моноблоков из одинаковых элементов. Иными словами, данные матрицы не образуют семейство, поскольку их орнамент индивидуален, он не предсказуем и не повторяется.

Можно предположить, что нарастание сложности структуры вне пределов семейств матриц связано с составным характером чисел 9, 15. Приведем в противовес этому предположению следующий сэт матриц порядков 19, 21, 23, рис. 5.



Сложные матрицы максимума детерминанта порядков 19, 21, 23


Матрицы простых порядков 11, 19, 23 имеют между собой немало общего, мы видим в их составе все те же блоки малого порядка. Но на порядке 19 каждая четверть матрицы – блочная матрица с каймой, причем первая четверть отличается от трех остальных похожих на нее тем, что в ней с шагом 3 по строкам и по столбцам идут неожиданные вкрапления в виде инверсии знаков элементов. Этот необычный индивидуальный орнаментальный узор, а по Сильвестру матрицы максимума детерминанта – орнаменты, не встречается среди матриц ниже и выше ее по порядку, независимо от того, простой это порядок или составной.

Матрица 21 собрана на основе блоков не 3, а 4-го порядка, про матрицу 23-го порядка, напротив, невозможно высказать суждение, блоками какого размера она заполнена. На каждом порядке мы видим оригинальный орнамент, они не повторяются.

Наше предположение (гипотеза) состоит в том, что особенности орнаментов матриц максимума детерминанта неисчерпаемы. Поэтому с ростом порядка находить их становится все более сложно. Первая сомнительная матрица, детерминант которой не подтвержден на оптимум, встречается уже на порядке 22. Наиболее вероятное решение для размеров 22, 34, и сходных с ними в том, что n–1 не разложимо на сумму двух квадратов (помимо порядка 58), – это бициклы с парной каймой, см. рис. 6.



Матрицы максимума детерминанта порядков 22, 34



Индивидуальность матрицы 22 проявляется в том, что это единственный двоякосимметричный бицикл с каймой, с обоими симметричными блоками A, B. Аналогичная граница симметрии бициклов без каймы на порядках матриц Адамара, обнаружена на критическом порядке 32.

Часть детерминантов матриц четных порядков удовлетворяют граничному значению известного неравенства Адамара (оценка детерминантов сверху), экстремальные матрицы – матрицы Адамара. Сходное неравенство, но для детерминантов матриц нечетных порядков, предложил Гвидо Барба.

Граница Барбы. Матрицы A порядков n с элементами, не превосходящими 1-цы, удовлетворяют неравенству: |det(A)|2≤(det(n–1)I+J)=(n–1)n–1(2n–1), где I – единичная матрица, J – матрица из единиц. Максимум достигается на порядках, для которых 2n–1 – полный квадрат. Это необходимое условие, позволяющее выделить экстремальные решения, выведено из требования целочисленности экстремальной матрицы с элементами 1 и –1.

Граница Барбы достижима на последовательности порядков, описываемой как суммы квадратов близких чисел n=a2+b2, b=a+1. Матрицы Барбы порядков 5, 13, 25 (Raghavarao), 41 (Bridges, Hall and Hayden), 61 (Brower), 85? (Solomon, Orrick), 113 (Brower) и т.п., сложность орнамента чередуется через порядок (порядки 41, 85, и т.п. сложнее), 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п., сходны с адамаровыми в том, что их детерминант достигает своей границы.

Это витражи – матрицы, построенные вставками блоков в матрицы Адамара, впервые описанные Рагхаварао и Андре Бровером. Принцип нарастания сложности орнамента справедлив и для них, алгоритм построения матриц Барбы встречается и описан лишь в общих чертах, позволяющих найти отдельные матрицы, см. рис. 7.



Матрицы максимума детерминанта порядков 25, 41



Теперь мы подходим к основному тезису нашей статьи, рассматривающей матрицы Ферма. В последовательность чисел n=4t+1 вложены как числа Барбы, отмеченные выше, так и числа Ферма (кроме первого).

Простые числа Ферма – классические объекты теории чисел, известно всего пять таких чисел Fk = 3, 5, 17, 257, 65537.

В 1796 году Карл Фридрих Гаусс обнаружил неожиданную связь между ними и геометрическими фигурами, вписав в круг правильный семнадцатиугольник и доказав более общее положение, что если число сторон правильного многоугольника равно простому числу Ферма, то его можно построить при помощи циркуля и линейки.

Эта междисциплинарная связь глубока и может находить иные оригинальные проявления. Сэт матриц порядков чисел Мерсенна относительно большой, просто устроенных матриц максимума детерминанта среди них мало, так что он обречен быть сложно устроенным. А вот с матрицами Ферма все намного интереснее.

Похоже, они образуют серьезную альтернативу матрицам Барбы. Алгоритмы построения матрицы Ферма обнаружены еще при отыскании форм, которые экстремальны на ортогональных подмножествах матриц. Вместо привычных 1 и –1 в них присутствуют элементы 1 и –b, b – иррациональное число, кайма также отличается своим значением bd ≤ 1. Иррациональные матрицы Ферма сводятся к указанным выше бициклическим формам элементарным округлением.

Таким образом, ортогональные и не ортогональные матрицы Ферма – одни и те же матрицы, отличающиеся параметрической настройкой. Это качество оригинальное и присуще также просто устроенным бициклам, которые образуют основной сэт матриц максимума детерминанта четных порядков. Иными словами, матрицы максимума детерминанта Ферма F – почти ортогональные по строкам и столбцам матрицы, близкие к квазиортогональным матрицам Адамара.

Выделенная близостью к ортогональным структурам цепочка матриц отличается от прочих матриц максимума детерминанта тем, что оптимистическая оценка Барбы для них может быть заменена прагматической точной оценкой.

Для матриц, у которых 2n–1 не составляет полный квадрат, верхняя граница Барбы B завышена. Она иррациональна и, соответственно, не достижима на экстремальных матрицах с целыми элементами 1 и –1, т.е. нуждается в коррекции в сторону уменьшения умножением ее на иррациональный множитель, меньший 1

Для матриц Ферма такой множитель составляет величину Fk–1/(2Fk–1)1/2.

Гипотеза. Матрицы Ферма порядков простых чисел n=Fk=3, 5, 17, 257, 65537, .. – матрицы абсолютного (или локального) максимума детерминанта Fk–1/(2Fk–1)1/2×B, B=(n–1)n–1(2n–1) – оценка Барбы.

В самом деле, одна из конструкций матриц Ферма затрагивает матрицы Адамара с максимальным эксцессом (сумой элементов матрицы). Будучи регулярными, имея равные по значениям суммы строк и столбцов, такие блоки легко ортогонализируются даже в том случае, когда к ним добавлена кайма из равных между собой элементов. Они порождают ортогональные по строками и столбцам матрицы, которые параметрически сводимы (округлением) к экстремальным матрицам Ферма F с элементами 1, –1, изображенным ранее на рис. 3.

Эксцесс, модуль суммы элементов регулярной матрицы Адамара H, равен |eTHe|, где e – вектор с единичными элементами, причем det(F)=(1+eTH–1e)det(H), это позволяет оценить детерминант ((n–1)1/2+1)/(2n–1)1/2, n=4u2+1, u – целое число. Знаки элементов блока H важны, наращивание 1 прибавлением eTH–1e гарантирует избыток отрицательных элементов. Поделив выражение для детерминанта на B, можно получить отмеченную выше относительную границу Fk–1/(2Fk–1)1/2.

Как видно, для порядков в виде чисел Ферма n=Fk удалось получить красивую формулу отличия целочисленного детерминанта от иррациональной для большинства порядков границы Барбы. У целочисленной матрицы детерминант должен быть целочисленным, поэтому масштабный коэффициент поправки иррационален.

Проверим границу Ферма конкретными вычислениями для чисел Fk = 3, 5, 17, 257, 65537.. Первое число 3 стартовое. Для порядка n=5 имеем целое значение поправки детерминанта Fk–1/(2Fk–1)1/2=3/91/2=1. Детерминант достигает здесь целочисленной в данной точке границы Барбы, эта матрица существует, оптимальна, и изображена на рис. 3 второй. Для порядка n=Fk=17 имеем 2Fk–1=33 – не полный квадрат, относительный детерминант равен здесь 5/331/2=0.8704... Это иррациональное число – масштабный множитель, который выступает поправкой к недостижимой иррациональной оценке границы Гвидо Барбы. Их произведение дает целое число 5/331/2×B – детерминант матрицы Ферма порядка 17. Эта матрица существует, оптимальна, и изображена на рис. 3 третьей.

Оптимальность остальных матриц порядков больше 17 не доказать переборными процедурами. Множество матриц с целыми элементами 1, –1 конечно, однако орнаменты экстремальных матриц возрастают в своей сложности.

Вслед матрице порядка Барбы порядка 255 идет матрица Ферма 257-я: имеем заранее предсказуемое относительное значение 17/sqrt(2*257–1)=17/sqrt(9*57)=0.7505.. Ее можно получить модифицированным алгоритмом Сильвестра, см. рис 8.



Матрица Ферма 257


КЛАСС НЕОРТОГОНАЛЬНЫХ МАТРИЦ


Оптимальные по значению детерминанта матрицы ищутся на классе {1,–1}-матриц, расширение {0,1,–1}-матрицами не добавляет к нему ничего нового, в смысле возможности улучшения значения детерминанта, оно эффективно только на подклассе ортогональных матриц. Ограничение на значения детерминантов для матриц порядков 1, 2, ... сверху, использующие оценки Адамара (адамарова граница), равны 1, 2, 3⋅31/2, 16, 25⋅51/2, 216, ..., квадраты равны 1, 4, 27, 256, 3125, ...

Для нечетных порядков оценку верхней границы уточнил Гвидо Барба |det(A)|2≤(n–1)n–1(2n–1), максимум достигается на порядках, для которых 2n–1 – полный квадрат (необходимое условие, иначе нарушается целочисленность). Эквивалентное условие (гипотеза): n=k2+(k+1)2 [*].

Оптимальные матрицы удовлетворяют условию A'A=(n–1)I+J, J – матрица из единиц, они существуют только на порядках n=1 (mod 4). Пару таких матриц (15 и 25 порядков) нашел и опубликовал Raghavarao. Матрицы Рагхаварао порядков 5, 13, 25, [41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п.] сходны с адамаровыми в том, что достигают по значению детерминанта отмеченной границы.



Циклическая матрица Рагхаварао R13


Остальные матрицы могут быть оптимальными, но границы не достигают. Матрица типа Рагхаварао и округленная до целых значений матрица Ферма пятого порядка имеют одинаковый определитель, на 17-м порядке конструкция Ферма конкурента не имеет и представляет собой оптимальную матрицу. На классе квазиортогональных матриц она только локальна оптимальна. Предположение о том, что подобного сорта матрицы всегда лучшие по определителю опроверг в 2003 году эксперимент с матрицей 65-го порядка Уорика и Соломона.

МАТРИЦЫ АДАМАРА-ГОЛЕЯ И ЯНГА



Спаренные циклические матрицы X6, X10


Если существуют циклические матрицы A, B нечетного порядка 1<n<31, исключая порядки 11, 17, 29 и т.п., с элементами {1,–1}, удовлетворяющие критерию

A2+B2=2(n–1)I+2J,


где J – матрица единиц, то существует матрица максимального детерминанта X=X(2n)

X=
A
B
 BT 
 –AT 
X=
A
 BR 
 –BR 
 –A 


где R – обратная единичная матрица (флип).

Матрицы A, B на порядках Адамара могут быть построены на базе пары комплементарных последовательностей Голея (Golay seq). Необходимое условие существования: размер парных последовательностей должен быть суммой двух квадратов (где один квадрат может быть 0): 1, 2, 4, 8, 10, 16, 20, 26, 32, 40, 52, 64, 80 (n<100). Исходные примитивы имеют порядки 2, 10, и 26 (остальные строятся на их основе).

Идея комплементарных последовательностей (сходных, но для нечетной длины кода) работает и для некоторых порядков, на которых вычисляются матрицы Белевича.

На порядках n=2 (mod 4) Ehlich и Wojtas: |det(A)|2≤4(n–2)n–2(n–1)2, максимум достигается на матрицах, порождающих блочно диагональную форму A'A, блок (m–2)I+2J, n=2m, 2(m–1) – сумма двух квадратов. Округленные матрицы Эйлера отличаются знаками блоков (n+2)I–2J. Иными словами, проблемны все те же порядки 22, 34, 58 и т.п., что и у матриц Белевича.

Первый проблемный порядок, для которого неясно оптимальное решение – порядок 22, существует оценка определителя 409.6×1012 (численное решение, в A'A присутствует ±2), у ортогональных матриц проблемы начинаются раньше (на 13-м порядке, 4 123 300 против максимально возможного 14 929 920).

На порядках n=3 (mod 4) работает то же ограничение, что и для n=1 (mod 4), оно касается матриц нечетных порядков в целом, но условие 2n–1 – полный квадрат недостижимо тут никогда, поэтому Ehlich отнес случай к труднейшим, для n≥63 им была получена точная оценка для матриц, кратных 7, максимум достигается на матрицах, порождающих блочно диагональную форму A'A, диагональный блок (n–3)I+4J, внедиагональный –J. Отметим, что округленные до целых матрицы Мерсенна дают A'A=(n+1)I–J, вторым корнем этого уравнения идет "черный Мерсенн".

ОБЗОР ЯНГА (C. H. Yang) | НЕРАВЕНСТВА | ОБЗОР


КЛАСС ОРТОГОНАЛЬНЫХ МАТРИЦ



Задача о максимальном определителе на классе квазиортогональных матриц имеет решение на матрицах Прокруста, к которым принадлежат, в частности, матрицы Адамара на порядках 1, 2 и далее кратных 4, и матрицы Белевича на порядках n=4k+2 (если таковые существуют). На нечетных значениях порядка (и при четных порядках, не кратных четырем) ортогональность – помеха оптимизировать этот параметр.

В теории оптимизации локальным оптимумам придается значение не меньшее, чем абсолютным экстремумам, в этом смысле можно говорить отдельно об мерсенновских определителях и прочих не менее важных ветвях задачи Прокруста: определителях субоптимальных матриц Эйлера, Ферма и т.п. Оптимальные матрицы содержат в себе столь заметные мерсенновские блоки, что можно говорить о тождестве структурных инвариантов матриц Адамара, Белевича, Мерсенна и т.п. Матрицы Мерсенна, в некотором смысле, – альтернатива матрицам Адамара на нечетных значениях порядка, и что для обоих матриц первичнее: такой же неразрешимый вопрос, как вопрос о курице и яйце. Общего у них – порядочно много, включая гипотезу о существовании, и все же матрицы Мерсенна несут на себе печать нечетных чисел. Пример с "хаотическим" аттрактором: ввиду малости ямки локального оптимума итерации упираются в порог адамаровой нормы уровневых матриц h=m13131/2.



WIKI | ОБЗОР [2] | ПРОКРУСТ | ПРОКРУСТОВ АНАЛИЗ | ТАБЛИЦА | [1] [2]


Rambler's Top100