MAXIMUM DETERMINANT MATRICES
(ODD ORDERS)




© Nickolay A. Balonin, Dragomir Z. Djokovic, 22.04.2015

Hadamard-type matrix catalogue and on-line algorithms


D. RAGHAVARAO | A.E. BROUWER | TABLE | SLOANE | CONVERTER


ЗАКОН СИММЕТРИИ (ИДУТ ЧЕРЕЗ 8?)



Новый порог симметрии 58=50+8 и 66=58+8?!




Tamura n=59 det()=1.096e+52 и 86 за 3 суток w=100000 попытка 999


Табличка Матрица 59 заметно уступает рекорду Тамуры (0.86 против 0.96, не бицикл)

ПОДБОРКА СТАТЕЙ О МАТРИЦАХ СЕМЕЙСТВА АДАМАРА

Балонин Н. А., Сергеев М. Б. Расширение гипотезы Райзера на двуциклические структуры и разрешимость матриц Адамара орнаментом в виде бицикла с двойной каймой // Информационно-управляющие системы. 2017. № 1. С. 2–10.
Балонин Н. А., Сергеев М. Б. Матрицы локального максимума детерминанта // Информационно-управляющие системы. 2014. № 1. С. 2–15.

ОБЗОР МАТРИЦ МАКСИМУМА ДЕТЕРМИНАНТА НЕЧЕТНЫХ ПОРЯДКОВ


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



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



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



Матрицы порядков 3×5=15, 3×13=39 с детерминантом около 0.7 Barba bound


Помимо семейства циклических матриц максимума детерминанта есть моноциклы с каймой из 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-го порядка, напротив, невозможно высказать суждение, блоками какого размера она заполнена. На каждом порядке мы видим оригинальный орнамент, они не повторяются.

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

KALEIDOSCOPE OPTIMIZATION

Поражаюсь неистощимости симметрий матриц нечетных порядков. На каждом новом порядке калейдоскоп приходится менять. Узор обязательно содержит подскок новый. Матрица 19, скажем, содержит бордюр и вполне обыденные 4 субблока, но один, верхний, "расстрелян" инверсией каждой четвертой клетки. А у предыдущих матриц такого крапа нет. И матрица 21, иная, у нее блоки "вертятся". Похожи, друг на друга, но с поворотом и инверсией знака. Это красивая веточка, я ее не сразу оценил, глубокая. Порядки 3, 5, 13 и 7, 17 имеют циклические формы. Остальное – крошево льда в русле реки, точная картина. Для них годится что то вроде калейдоскопа, – игрушка из детского сада (три зеркала, отражают некий орнамент, конечность просматривается). Построил программу. Порядки до 22-го (и 34-й интересен) она одолела. Программа откровенно дрянненькая еще, надо бы получше, но иногда с нею бывают удачные находки. Плюс конвертер.

Среди матриц (глобального) максимума детерминанта нечетных порядков очень мало матриц простой структуры, причем сосредоточены они на невысоких порядках. Матрицы распадаются на семейства. Семейство циклических матриц, похоже, конечно и состоит всего из трех представителей: 3, 5, 13, корреляция с порядками пар последовательностей Голея размеров 10, 26 очевидна. Им вторит семейство бициклических матриц с каймой: 3, 5, 17, повторяющих первые числа Ферма. Помимо пары семейств циклических и бициклических матриц есть моноцикл с каймой порядка 7 (он же бицикл без инверсии знака [A B; B A]). Порядок 17 может быть последним порядком матриц простой структуры, надо проверить 257-й, торчит незабитым гвоздем во всей этой симфонии *).

*) В 1796 году Карлу Фридриху Гауссу удалось доказать, что если число сторон правильного многоугольника равно простому числу Ферма, то его можно построить при помощи циркуля и линейки. На сегодняшний день известны следующие простые числа Ферма: 3, 5, 17, 257, 65537 (Числа Ферма, Семен Гидинкин).


У простого числа 2k+1 показатель обязан быть степенью двойки, поэтому простые числа Ферма агрегируют в себе все простые числа этой последовательности. Серпинский исследовал масштабированные числа m2k+1 на предмет быть составными., детальнее: гонки по вертикали.

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

В математике все исторически долгим путем устанавливаемые факты тесно переплетены, и особое положение порядков Ферма вполне может быть соотносимо с их ролью в теореме Гаусса о многоугольниках. Эти матрицы максимумов, ортогональная и неортогональная, они уходят друг от друга, не только параметрами, но и структурой. Сэт матриц Мерсенна – он большой, а просто устроенных матриц абсолютных махимумов мало, так что он обречен. А вот с матрицами Ферма все интереснее, они структурно (при ортогонализации и наоборот) не меняются, только параметрически. Так как Гаусс показал избранность чисел Ферма, простых, многоугольниками, то абсолютные махимумы как раз на них и сидят, они точно сидят на 3, 5, 17. Рыщут их с фонарями, но мимо порядка 257 прошли.. (при том, что роль матриц с большим эксцессом известна).

В самом деле, для n=5 имеем точное целое значение 1. Для порядков больших 5-ти, n=Fk=17, 2Fk–1=33 не полный квадрат, относительный детерминант стремится к 5/sqrt(33)=0.8704..., и это именно так. Вслед матрице порядка Барбы 255 идет 257-я: имеем заранее предсказуемое 17/sqrt(2*257–1)=17/sqrt(9*57)=0.7505.. Мы можем, следовательно, предсказать значение детерминанта для такого чудовищного порядка, как 65537 (0.7099). Ниже 0.7 детерминант матриц обозримых порядков не падает.

Для нечетных порядков оценку верхней границы уточнил Гвидо Барба |det(A)|2≤(det(n–1)I+J)=(n–1)n–1(2n–1), максимум достигается на порядках, для которых 2n–1 – полный квадрат (необходимое условие, иначе нарушается целочисленность). Эквивалентное условие (гипотеза): n=k2+(k+1)2 [*]. Оптимум достижим на матрицах Рагхаварао и Андрэ Брауэра. На четных порядках 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) – сумма двух квадратов.



Матрица X7 как моноцикл с каймой и Ферма 257


Порядки Барбы. В n=4t+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, и т.п. сложнее). Матрицы порядков 5, 13, 25, [41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п.] сходны с адамаровыми в том, что достигают по значению детерминанта отмеченной границы.

Порядки Ферма. У целочисленной матрицы детерминант должен быть целочисленным. Для порядков n=Fk, число Ферма, удалось получить красивую формулу отстояния от иррациональной границы Барбы. Интригующее начало здесь есть – порядки Барбы дают оптимистичную (радужную) оценку детерминанта (для всех матриц), а на порядках простых чисел Ферма существует прагматическая оценка детерминанта.

Целочисленный (sqrt(n–1)+1)det(H), det(H)=(n–1)(n–1), n–1=4u2 детерминант округленных матриц Ферма отличается от иррациональной границы Барбы иррациональным же (компенсационным) масштабным множителем Fk–1/(2Fk–1)1/2 для порядков, равных числам Ферма.

Эксцесс, модуль суммы элементов матрицы, равен |e'He|, e – вектор с единичными элементами, причем det(F)=(1+e'H–1e)det(H), это позволяет оценить детерминант (sqrt(n–1)+1)/sqrt(2(n–1)+1), n=4u2+1. Для получения матрицы максимума детерминанта знак элементов H принципиален, избыток отрицательных элементов гарантирует прибавление модуля e'H–1e к 1, а не вычитание.

Для матрицы порядка 17 иррациональный коэффициент падения детерминанта 0.85.. к иррациональной же границе Барбы отвечает проверенному экстремуму, для порядка 37 (сходной матрицы, но не число Ферма) коэффициент падения детерминанта 0.82 (для надстроенной регулярной матрицы) слишком пессимистичен, есть 0.94; на порядке 65 наблюдается сближение 0.79 и 0.81 (но это не число Ферма!), на 101 близки 0.78 и 0.8; на порядке Барбы 145 сильное расхождение 0.76 и 1 (!), на 197 есть 0.75 и ?, на 257 (есть Барба, но 255-й) 0.75 и ? – отсутствуют матрицы для сравнения. Вслед 1-м идет падение относительного детерминанта. Это касается чисел 5(1) и 9(0.85), 13(1) и 17(0.87) уже в начале оси порядков. Следующий за 113 (где достижима 1) через 4 порядок 117 балует лишь значением 0.72 !


Порядок 5 (центральный холм, пятый элемент) общий для простых и сложных построений, очевидно, системообразующий. От него идут русла в n=4t+1. Первые из n=4t–1 числа Мерсенна 3, 7 менее заметны и исчерпываются раньше (порядки, кратные 7, сложные). Сложность остальных матриц нарастает с ростом порядка, это касается обоих ветвей n=4t+1 и n=4t–1, наверняка есть матрицы, ассоциируемые с n=4t–3 (сосуществующие с n=4t+1, но "иные").

Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 2016. № 1. С. 2–15.
Balonin N. A., Sergeev M. B. Regular Hadamard matrix of order 196 and similar matrices // Informatsionno-upravliaiushchie sistemy, 2015, № 1 (73), pp. 2–3.
Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Ферма // Информационно-управляющие системы. 2012. № 6. С. 90–93.
Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.

DYNAMIC SYSTEM GENERATOR FOR 3, 5, 13



Maximum determinat matrices X3 and X5



Maximum determinat matrices X13

GALOIS FIELD PROCEDURE

ПОИСК БИЦИРКУЛЯНТОВ С КАЙМОЙ 3, 5, 17



Maximum determinat matrices X5 and X17


ОСОБЫЙ ПОРЯДОК 7



Матрица X7 = [A,B;B,A] (нет "–" при втором A) !



Матрицы максимума детеримнанта и Мерсенна


Матрицы Мерсенна – моноцикл или бицикл [A B; B –A] с каймой, аналогия с округлением возможна с натяжкой, при инверсии отрицательных элементов каймы знак диагонального блока остается инверсным. В отличие от матриц Ферма, матрицы Мерсенна проявляют себя лишь на порядке 3 (но на нем все себя проявляют).

Простые числа Мерсенна названы в честь Марена Мерсенна, который еще в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, его формула дает простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным. Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами – числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Еще Евклид доказал, что если простое число p имеет вид числа Мерсенна, то число p(p+1)/2: 6=1+2+3, 28=1+2+4+7+14, ... является совершенным. Леонард Эйлер доказал, что все четные совершенные числа имеют вид, указанный Евклидом.

ОКРУГЛЕННЫЕ МАТРИЦЫ ФЕРМА



Регулярные матрицы Адамара порядков 36 и 64


Судя по таблице Уорика, в единую систему, опирающуюся на представление о связи структуры матрицы с семейством числа, матрицы не сведены. Отсутствует представление о матрицах локального максимума детерминанта с общей для всех матриц семейства n=4t+1 простой структурой. Алгоритмы построения регулярных матриц Адамара, служащих основой (core) матрицам Ферма, рассмотрены в статье ниже.



Первую матрицу H144 с эксцессом 1728 надо инвертировать по знаку


Напомним, что простые числа Ферма 3, 5, 17, 257 и т.п., – порядки правильных многоугольников, построение циркулем и линейкой, с 17-м порядком отличился еще Гаусс. На 17-м порядке конструкция матрицы Ферма (регулярная матрица Адамара с каймой) по детерминанту конкурента не имеет и представляет собой оптимальную матрицу. Причем на классе квазиортогональных матриц эта структура только локальна оптимальна. Относительный максимум детерминанта округленных матриц Ферма монотонно понижается с порядком 4, 16, 36, 64, 100, 144, 196, 256, и т.п., с каймой), это матрицы сугубо оптимальные только до порядка 17 включительно (порядок 257 с нашей оценкой близости к границе 0.75 *) негде проверить)!



RAGHAVARAO ORDER X25





Bridges, Hall and Hayden (my sorting) X41 and Solomon, Orrik X85 ??



A. Brower constructions X61 and X113




Ориентировочная матрица X27

COMPLICATED STRUCTURES


The sense to study ornamental structures of maxumum determinant matrices: we can meet them inside some classical problem matrices, such as conference matrices order 45 (orders 66, 86 unknown). In difference to Hadamard matrices, special conference matrices have strip-blocks besides of circulant and backcirculant structures. The maximum determinant matrices consist of such elements, as "spots": local unit sign inversion as a common symmetry destroy (look order 19). The concept of maximum determinant matrices of odd orders – in "absence of types" – every new order brings a new unknown feature.


MATRIX X3


MATRIX X5


MATRIX X7


MATRIX X9


MATRIX X11


MATRIX X13


MATRIX X15


MATRIX X17


MATRIX X19


MATRIX X21


MATRIX X23


MATRIX X25


MATRIX X27


MATRIX X41


МАТРИЦЫ ПОРЯДКА 31



Матрицы с Det/Barba=0.727791056595955 and 0.7060421984906806



Субоптимальные матрицы Det/Barba=0.184 и 0.372


Напомним, что 3, 15, 31, 63, – это все мерсенновы числа. Опираясь на строго циклические и симметричные клетки порядков 3 (бордюр) и 4 компьютер оптимизировал детерминант до 0.706 границы Барбы (первое предложение), синее, при рекорде 0.727 у Hiroki Tamura, красное.

Мы знаем, что любопытная природа МАХ ДЕТ требует в одном месте, но испортить общую благостность упорядоченности. Надо же какое странное свойство! В альтернативе порядок базовых клеток 8, упорядоченность (сильно) нарушена, перехлест в другую сторону Вот теперь задача препарирована. Вопрос может быть правильно поставлен так: КАК подпортить синюю картинку, чтобы она превзошла красную по детерминанту?

У X15 хватило порчи (увода от цикличности) первого маленького квадрата, там "вишенка" ! Один обратный циклический блок на всю матрицу и "дрова" в виде каймы. Заметим X15 в целом симметрична, X22 – симметрична, X34 – нет, то есть X31 – пограничный порядок. Второй более тонкий вопрос, следовательно, состоит в том, симметрична ли X31 в целом – есть ли симметричная форма?

*) Barba bound established for n=1 (mod 4), for n=3 (mod 4) need more complicated estimation.

QUASI-ORTHOGONAL MATRICES



Big determinat matrices X15 and Q15



Quasi-orthogonal matrix Q15 and its levels



Big determinat matrices X19 and Q19



Quasi-orthogonal matrix Q19 and its levels


CONFERENCE MATRIX C(46) HAS COMMON FEATURES
WITH MAX DET MATRICES X21, X25 (MATHONS' CROSS-SHIFTED BLOCKS)




POOR CELLS of {1,1,0}-TYPES (CIRCULANT AND CROSS-SHIFTED)

BALONIN-SEBERRY CONSTRUCTION



RICH CELLS of {1,2,0}-TYPES (CIRCULANT, BACK-CIRCULANT AND CROSS-SHIFTED)

COMPILATION TO C-MATRIX WITH INVARIANT 5



OLD AND NEW STRUCTURES (5 IS QUANTITY OF CELL-and-BLOCK TYPES)

N. A. Balonin, Jennifer Seberry A Review and New Symmetric Conference Matrices //Informatsionno-upravliaiushchie sistemy, 2014, № 4 (71), pp. 2–7.

GALOIS FIELD PROCEDURES

ИЗУЧАЕМ АЛЬТЕРНАНСЫ !


Помимо выжимания максимума, есть задачка, мы не исследовали. Вот на 70 максимум достигается на одной и той же H'H, и долго. А максимумы на соседних средних и малых порядках достигаются на нескольких H'H. С каким законом это связано? Это даже интереснее дожидания трамвая 70, когдаааа он "приедет". В среднем он ходит, возможно, раз в неделю. Это мы уже почти изучили все и знаем. Смотрите как интересно! Альтернансов много, но оптимальный на 42 равномерно распределен, как и на порядке 70. Близнецы и братья.



Оптимальный альтернанс на 42 и 130 !


А какие еще порядки таковы? И в чем логика альтернансов? Предварительная оценка: порядки 6, 10 (0 альтернансов), 18, 30=18+4×3 (2 альтернанса, n делится на 2+1=3), 42=30+4×3, 70=42+4×7, попробуем угадать: 98=70+4×7 ! (6 альтернансов, n делится на 6+1=7) "равнорастопыренные". Равномерный Альтернанс на 98 угадан, его нашли, например, Великанец Н.В., Власенко А.А, студенты. То есть тут все как при пилке дров.. нужно согласование бревна n и полешка N+1 (альтернанс N). Попробуем угадать еще: 130, 130+4×13=182? (12 альтернансов, n делится на 12+1=13). Остальные 2 альтернанса, например, до порядка 38 включительно, наоборот, равнодушны к порядку следования полосок (любой)!

Предвычислитель детерминанта непрямой метод, но быстрый. Подтверждает устойчивые альтернансы! Обнаруживает прокол у Томаса на 106, 110, 114, 118.

Алгоритм поиска альтернансов Нажимаем кнопку стоп алгоритма ниже, и натаскиваем в свою таблицу версий решений для своего порядка n=... 6, 10, ..., 34, 38, 42, 46, 50, .. ! Подстраиваем DetFin=0.87; под желаемое, чтобы останавливаться на нужном детерминанте...

Таблица альтернансов для 42.

Табличка сравним Tomas det(|H|)



а остальные порядки как? уточнить [102, 106, 110, 114, 118], поискать 122, 126, 130?

ТРИ СЕМЕЙСТВА БИЦИКЛОВ SDS(n=2v,k1,k2,λ)


В отличие от циклических матриц, для описания которых годится SBIBD(n,k,λ), бициклы описываются SDS(n=2v;k1,k2;λ) – парным дифференциальным набором. За основу параметров SDS берутся расчеты количеств тех элементов (1 или –1), которых меньше.

Параметры SDS связаны соотношением λ(v–1)=k1(k1–1)+k2(k2–1), где k1, k2 – число элементов одного знака пары бинарных векторов размера v, задающих бицикл, а λ – общее число попарно совпадающих (пересекающихся) элементов первой и второй строк бицикла. Выбором переменных, оно сводится к уравнению круга, разрешимого в целых числах, и сказывается на уравнении для уровней, разрешимого в вещественных и иррациональных числах. Классификация бициклов с каймой отсутствует в литературе, эксперименты рисуют следующую картину.

МАТРИЦЫ ФЕРМА 3, 5, 17, 257, 65537, ...




Гаусс заметил связь правильных фигур с простыми числами Ферма 3, 5, 17, 257, 65537, .. и построил правильный семнадцатиугольник


Гаусс заметил связь правильных многоугольников с простыми числами Ферма 3, 5, 17, 257, 65537, .. и построил правильный семнадцатиугольник. Ришело на 80 страницах указал построение 257 угольника. В гёттингенской библиотеке в чемоданах больших размеров хранится способ построения правильного 65537-угольника, выполненное неким Гермесом. По этому поводу Джеймс Литлвуд пошутил: "Один навязчивый аспирант достал своего руководителя, и тот сказал ему: "Идите и разработайте способ построения правильного 65537-угольника!" Аспирант ушел и вернулся только через 20 лет". Выходит, эта связь проецируема также на экстремальные бициклы Томаса, которые мы исследуем также для порядков за пределами чисел Ферма. Вот этот опус собрал сведения про число 17, но что это также и экстремальный бицикл с каймой, этого составители не знают. :)

Семейство Ферма. Основная череда порядков, эта простые числа Ферма [1]: 3, 5, 17, 257, 65537, ... На них параметры k1, k2 оптимальных бициклов не зависят от наличия каймы. Они связаны с главным результатом Гаусса, его семнадцатиугольником, вписанным в круг (вроде бы, нарисован на могильном камне Гаусса). Например, "бициклы Томаса" с каймой 3, 5, 17 – превосходят все остальные орнаменты по детерминанту. Назовем их матрицами Ферма. Если предположение верно, то же самое касается порядка 257: бицикл 256 для него строится удвоениями Голея, они имеют более общие порядки 2k=2, 4, 8, 16, 32, ...



Матрицы Ферма 17 (симметричная!) и F257


Семейства Барбы. Существуют нечетные числа Гвидо Барбы nB=k2+(k+1)2 (сумма квадратов "чет" и "нечет"). Четные порядки бициклов равны nB+1 или 2nB, матрицы Томаса отличает кайма с 1, поэтому число –1 внутри ядра (core) больше, чем у обычных бициклов, матрица "вспучена" по k1, k2. Это нарушает баланс уравнения, появляется добавка λ(v–1)=k1(k1–1)+k2(k2–1)–ξ.


Порядки Ферма с двумя ветвями порядков Барбы мы видим, как бы, точками нащупанный подводный хребет этого океана матриц в виде трех усов. "Линия Эверестов", это порядки Ферма. Барба – два отрога. Трехлистник, любимая игра природы. Взять хотя бы сочленение головы с плечами. Природа очень любит дитохомию. Деление на два. Обожает. Основа симметрии всего и вся. Но без трехлистника не сочленить тело. Матрицы, любопытные модели, где всплывает трехусовость.

Четные порядки семейств больше порядков Барбы на единицу n=nB+1 = 6, 14, 26, 42, 62, 86, 114, 146, 182, 222, 266, 314, 366, 422, 482, 546, 614, 686, 762, ... большая семья (big family). Красным цветом помечены симметричные матрицы максимума детерминанта без каймы, зеленым – кососимметричные (с точностью до диагонали). Серия порядков простых (длина последовательности – простое число) матриц 6, 14, 26, не 42, 62, 86 прерывается относительно более сложными матрицами порядков 42, 114, далее идет простая матрица 146, потом сложная 182 (скорее всего, орбита 1), а матрицу порядка 222 никто не нашел до сих пор. Для них k1=(q2+q)/2; k2=λ=(q2q)/2.

Удвоенные порядки Барбы дают бициклы с n=2nB=10, 26, 50, 82, 170, 226, 290, 362, 441, 530, 626, 730, 842, 962, ... малая семья (little family). К простым относятся порядки 10, 26, 82, 170, 226, ... порядки 50, 290 и т.п. сложнее. Для них k1=k2=q2, λ=q2q.





Two symmetric bicycles with border 51, 59!


Мысль совершенно правильная оказалась – семейство с матрицей 86 не сохраняет качество при добавлении каймы. А второе менее уязвимое, но тогда, раз Барба 50 симметричный существует (его же и вылавливал полгода назад – симметрия объект поисков, скажем Оливия с соавторами нашли редкий симметричный четырецикл 116), то должен быть и Барба 51. К тому же, матрица с таким детерминантом лидирует среди всех прочих орнаментов, согласно таблице Уорика, 51. Рекорды Томаса: для сравнения (не симметричное решение). Это несомненно новый научный результат! Гипотеза про порядок 35 не выдержала проверки, эти примеры ее опровергают.

Подусие. Есть еще такая штука, как бифуркации (удвоения). Проверка порядков под усами, отстоящими ниже по порядкам на 1. Под одним из усов Барбы (первое семейство) сидит подусие n=nB = 5, 13, 25, 41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685, 761, .... Четвертый прижатый лепесток порядков. Если расставить все по полочкам, порядки лепестков полезно выделять.

*) Возникает естественный вопрос о матрицах составных 65, 1025, и т. п. порядков. Ответ с их размещением прост: они дают условный экстремум на бициркулянтах с каймой. Есть еще Ферма 37 и т.п. Сидят на регулярных N-циркулянтах с каймой. Регулярные матрицы, это витражи. Вот на витражах они и дают эктремум. Бицикл с каймой 37 уступит по детерминанту витражу типа Пропус. А вот бицикл 17 не проиграет четырехциклу 17. Они одинаковы по экстремуму. Порядки Ферма – системообразующие, роль локальных экстремумов класса ортогональных матриц играют здесь условные экстремумы на стуктурах.


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



Two symmetric Fermat matrix X17 and Fermat X257 (det=3.0560783×10309)



Two circulant matrix 37, det()=0.63, and Fermat 37, det()=0.819 !



The symmetric extremum X35 and asymmetric X37 !


Условно оптимальные моноциклы, это матрицы порядков Мерсенна 3×p=3, 15, не 21, 39, ... (p – простое), тогда как 5×p=5, 25, не 35 (число Мерсенна!) .. одинаково экстремальны на циклической или бициклической основах. Что касается 13×p=13, 65, .. то ответ мы знаем, циклическая и бициклическая основы лидируют попеременно.



Janko-Hadi and Propus form of big determinant matrix order 37


Витраж Ферма 37 дает условный экстремум, абсолютный эктремум для порядка 37 получен, но не систематизирован (получен существенным нарощением каймы с разрушением структуры циклических блоков). У матрицы 37 в 4 блока детерминант вычерпан на симметричной структуре Пропус.



Экстремумы витражи 37 (0.936) и 41 (1), витраж 85 неизвестен


Порядки Барбы n=4t+1=a2+b2, b=a+1, 5, 13, 25, 41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п., разложимых в сумму квадратов близких четного и нечетного числа, выделены тем, что абсолютный максимум детерминанта достигается на них на витражах, половину через раз идущих случаев которых составляют витражи, построенные на матрицах Адамара (четного порядка). С порядками 1, 13, 41, 85 справились кое как (под сомнением 85), но не нашли объединяющего эту черезполосицу общего правила построения витражей. Витраж 41=(6+2)×5+1 построен на блочной матрице 6×6 с двойной каймой, 5 – простое число Ферма, дает базовую последовательность символов Лежандра. Витраж 85=(10+2)×7+1 возможен на блочной матрице 10×10 с двойной каймой, 7 – простое число Мерсенна.

COMPLICATED AND SIMPLE FORMS



Two forms of suboptimal matrices with det()=0.9653 and 0.8607, order 59


There are specific orders. The one border circulant constined extremum X13 (absolute extremum also), X25 have the same determinant as one border two circulant form (Raghavarao orders). Hadamard matrices and Golay sequences is a good foundation for large determinant marices, but for order n=53 Golay sequences give a weak solution. Absolute maximum determinant matrix complexity grows with order (order 59, example, Ehlich bound is used instead universal Barba bound), so there is a sense to observe constrined optimums on the circulant or one border two circulant matrix classes. Tomas Rokicki found some such suboptimal solutions (let us take –1/1-matrix, one can make its top row all ones, and then add it to the other rows and divide them by 2: determinant of 0/1-matrix without border be less in 2n–1 times: the argument can be reversed to build a –1/1 matrix of size n out of any 0/1-matrix of size n–1, so this should be the biggest determinant possible), placed at Will Orrick table. To order n=67 (including) secuences calculated and proven by direct projections X=sign(Creatan(n)), bigger orders is typical sphere of two circulant Hadamard matrix calculation methods.

Balonin N. A., Seberry, Jennifer. Remarks on extremal and maximum determinant matrices with moduli of real entries ≤ 1 // Informatsionno-upravliaiushchie sistemy, 2014, № 5 (71), pp. 2–4.



DIRECT-SEARCH



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


Проблема в том, что оптимальная по детерминанту матрица порядка 53 имеет в качестве ядра не матрицу Адамара 52 (на эту роль годятся лишь ядра матриц Ферма порядков 5, 17, 37 (но у нее 4 блока), 65 и т.п., на порядках простых чисел Ферма они еще и лидируют), с ее идеальной диагональной матрицей квадратичной невязки, а другую матрицу, невязка которой AAT+BBT показана справа.

При поиске бициклов порядка n последовательности a, b длины v=n/2 вычисляются впрок, также, как и произведения их на циклические матрицы Aa, Bb, где A=circ(a), B=circ(b). Для вычисления произведений вычислять циклические матрицы в явном виде не обязательно, причем проверка годности Aa+Bb=[x,-2,-2,....]' востребует только часть z=(v+1)/2 компонент Aa, Bb. Количество отрицательных элементов строк k1, k2 задается заранее. Массивы A, B ниже содержат массивы потенциальных строк, в примере строки задаются случайными. Если известен тип симметрии строк решения, генератор getAB() можно настроить на нужные строки.

Рекорды Томаса: для сравнения.

Алгоритм для n>50: бросает выборку, обнаружив претендентную матрицу ! Поиск с фиксированными k1, k2 (можно шевелить по //), с объемом выборки w=1000. Проверим на n=42, подстроив желаемый порог DetFin<0.87 (рестарт). Догоним Томаса за минуту.

Ускорение поиска: компьютер с несколькими процессорами вытягивает до 4 одновременно запущенных на ночь задач.

Алгоритм для n≤50: версия алгоритма не спеша помечает все "одинаково-хорошие" варианты в массиве MX и проверяет их все потом скопом. Не спешить не выгодно, если хорошая матрица всего одна (проще, найдя хорошую матрицу сразу ее проверять, как выше).

Алгоритм, экономный по памяти: версия алгоритма первого типа, без буфера памяти, ныне несколько устарела.

PROJECTION METHOD


Замечательный метод, не нуждается в дополнительной информации о структуре матрицы, более того, он сам по себе может рассматриваться как источник первичной информации для метода орбит, добываемой им опытным путем. Индифферентен к тому, решается ли точная задача или приближенная, поэтому может использоваться для альтернативной проверки таблиц приближенных экстремальных решений. Он базируется на проекциях X=sign(Creatan(n)) с ортогональных критских матриц локальных экстремумов на область матриц с целочисленными элементами {1,–1} или {0,1,–1}.

Пропус 52 с каймой почти достигает границы возможного детерминанта, 0.78 вместо 0.788, это матрица порядка, который создает проблемы при поиске.

Балонин Н. А., Сергеев М. Б. О значении матриц начального приближения в алгоритме поиска обобщенных взвешенных матриц глобального и локального максимума детерминанта. // Информационно-управляющие системы. 2015. № 6. С. 2–9.

ORBIT METHOD


Метод находит орбиты для порядков 5, 5×3=15, 13, 13×3=39, бицикл с каймой 17, но пасует на порядке 51 (который не проблема для метода проекций). Он нуждается в указании параметров SDS(n=2v,k1,k2,λ) и эффективно находит львиную долю точных экстремумов четных порядков, с ними он комментируется подробнее. Бициклы с каймой нечетных порядков из каталога Томаса – приближенного максимума детерминанта (рекорды), такие задачи орбиты решают плохо.

Орбиты, это масштабированная множителями показательная функция xk (целочисленные экспоненты) в конечном поле Галуа или мультипликативном кольце Zv с арифметикой по модулю v (размер генерируемой последовательности). Обобщение метода орбит – это факторизация, например, для случая n=17 и v=8, строк индексов элементов на усеченную подгруппу x=[1,3] длины 2 и множители o1=[2,7] длины 2=k1/2, o2=[3] длины 1=k2/2 в контексте кронекерова произведения a=x⊗o1=[2,5,6,7], b=x⊗o2=[1,3].

Масштабированная несколькими множителями экстремальная показательная функция дают избыточные параметры. Нетривиальная факторизация учитывает совпадение произведений элементов, дающих одни и те же адреса. Если подгруппы или их части, потенциальные кандидаты на факторизацию, они видны воочию (находимы заранее), то множители представляют собой искомую часть. Чем длиннее орбиты, тем короче поиск.

В ортогональных задачах для описания всей последовательности матрицы хватает одной или пары пересекающихся орбит. Если ортогональность не подразумевается, последовательность нарезается на фрагменты-орбиты. Подход напоминает прижимание к потолку провисшей веревки для белья и относится к точным методам, он ищет целочисленный "резонанс" сообразно размеру задачи. Сама по себе идея факторизации шире ее исполнения с орбитами.

Альтернатива орбитам – парные адреса –1-ц в строке. Берем адреса и умножаем их по модулю размера строки адрес на некое число x. Получаем новые адреса –1-ц, которые добавляем к старым. Это скрытая симметрия, раз у нас парами все адреса встречаются. Задав половину адресов и число x – рефлектор (отражатель), ищем похожую на симметричную строку, но симметрия эта не видна на глаз. Орбиты, это более развитая идея симметрии, многогранная симметрия. На плохих порядках симметрия убывает, "ажурные орбиты" перестают работать. Орбиты – сильное, но слишком уязвимое оружие, они дают не все. Вплоть до порядка 59 субоптимальные последовательности довольно быстро ищет метод проекций.

CONVERT YOUR {0,+,–}-MATRIX BY RUN


       THIS SITE INSTUMENT
   ALPHA WIKI-MANUAL       INTERNET MATLAB ON LINE


© Nickolay Balonin

Rambler's Top100