5 GLOBAL MAXIMUMS

MAXIMUM DETERMINANT QUASI-ORTHOGONAL MATRICES




Hadamard matrix family catalogue of odd orders

© Nickolay A. Balonin, 20.10.2015


SQUARE MATRICES OF ODD ORDERS




Развертка детерминанта ортогональной матрицы третьего порядка


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



Multi-level maximum detherminant quasi-orthogonal matrix A11


Conjecture (Balonin [12]). There are only 5 maximum determinat matrices (det(A)→max; |aij|≤1; A'A=ω(n)I) with quantity of levels estimated as (n+1)/2±m, m≤1, integer. Search method uses pendulum models and an original algorithm of detherminant optimization.

Орбита, это показательная функция xk mod v. Числа от 0 до v разбиваются орбитами на классы эквивалентности. На сообщества. Если число принадлежит одной орбите, оно не принадлежит другой. Неортогональный бицикл максимума детерминанта сидит на экстремальной орбите. Индексы ее –1 в строках бицикла совпадают со значениями элементов орбиты или с масштабированными значениями элементов орбиты. При длинной орбите масштабных коэффициентов мало, быстро находим матрицу. Ложка в стакане воды, преломление, это и есть метод орбит. Ложка, она одна. Часть ложки видна над стаканом, а часть, с изломом, видна в воде. Что касается ортогональных матриц, здесь построения сложнее.

На порядке 13 (чертова дюжина) наблюдается коллапс уровневой структуры [12]. Нечто вроде константы Фейгенбаума – точка отделения бифуркаций уровней от "хаоса". Матрица-артефакт 13 "хаотична" по уровням. После 13 встречаются матрицы 15 и 19, похожие на "нормальные", но они не адамаровы. То есть, у них не самый большой детерминант. Матрицы, как бы, говорят, смотрите. Каждое нечетное число уникально. Мы им соответствуем, но мы такие разные. Матрица выступает как характеристика числа.

INTHERNET DATABASE


LEVEL HISTOGRAMS



Maximum determinant matrix A3



Maximum determinant matrix A5



Maximum determinant matrix A7



Maximum determinant zipper-matrix A7



Maximum determinant matrix A9



Maximum determinant matrix A11



Suboptimal matrix A11



A13 m=0.3098375495474202 h=1.117135171957338 det(A)=4123418 !



Suboptimal M13, a=1, b=0.936187, c=0.465886;
c*c+b*c+b*b-a*c+a*b–2*a*a=0; 2*b*c–2*a*b+a*a=0



Suboptimal M13, multi-level matrix



A15: m=0.2887947513169841 h=1.118497262322792 det(A)=12335608



Suboptimal M15 with m=0.290406>0.2886 (minimum)



A17: m=0.27439064282819675 h=1.1313416030617842 det(A)=3529571214



A19: m=0.252372696277 h=1.100067079181 det(A)=229717994042



Suboptimal M19 with m=0.252372>0.2521 (minimum)



Suboptimal M19 with m=0.252415>0.2521 (minimum)



Suboptimal M21 with m=0.245610 h=1.125527



A21: m=0.2426246113667 h=1.111845647047 det(A)=8248369206998



A23: m=0.2331447018837 h=1.11812271078 det(A)=350438919758585



A25: m=0.223378748338 h=1.11689374169 det(A)=18791163529769436



Suboptimal M25 with m=0.222031>0.2185 (minimum)



Raghavarao M25 with m=0.221279>0.2185 (minimum)



A27: m=0.210726701244 h=1.0949680592 det(A)=1817906931627483000



Suboptimal M27 with one border one circulant form



Suboptimal M27 with one border two circulant form



Suboptimal M29 with m=0.208580 h=1.123239



A29: m=0.2079108175 h=1.1196340176 det(A)=60473416111103525000



Suboptimal M49, two versions

OLD ALGORITHMES


PROCRUSTUS BED | OPTIMAL OCTAHEDRON | MANY HANDS GOD | BARKER CODES

MAXIMUM DETERMINANT MATRICES



Maximum determinant matrices A3 and A5



Maximum determinant matrices A7 and A9



Maximum determinant matrices A11 and A13


1. Balonin N. A., Jennifer Seberry. A Review and New Symmetric Conference Matrices // Informatsionno-upravliaiushchie sistemy, 2014, № 4 (71), pp. 2–7.
2. Балонин Н. А., Мироновский Л. А. Матрицы Адамара нечетного порядка // Информационно-управляющие системы. 2006, № 3. C. 46–50.
3. Балонин Н. А., Сергеев М. Б. М-матрицы // Информационно-управляющие системы. 2011. № 1. С. 14–21.
4. Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.
5. Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Ферма // Информационно-управляющие системы. 2012. № 6. С. 90–93.
6. Балонин Н. А., Сергеев М.Б. О двух способах построения матриц Адамара-Эйлера // Информационно-управляющие системы. 2013. № 1. С. 7–10.
7. Балонин Н. А. О существовании матриц Мерсенна 11-го и 19-го порядков // Информационно-управляющие системы. 2013. № 2. С. 90–91.
8. Балонин Н. А., Сергеев М. Б. М-матрицы и кристаллические структуры // Вестник Магнитогорского государственного технического университета им. Г.И. Носова. 2013. № 3. С. 58–62.
9. Балонин Н. А., Сергеев М. Б. К вопросу существования матриц Адамара и Мерсенна // Информационно-управляющие системы. 2013. № 5. С. 2–8.
10. Балонин Н. А., Сергеев М. Б. Взвешенная конференц-матрица, обобщающая матрицу Белевича на 22-м порядке // Информационно-управляющие системы. 2013. № 5. С. 97–98.
11. Балонин Н. А., Сергеев М. Б. Матрица золотого сечения G10 // Информационно-управляющие системы. 2013. № 6. С. 2–5.
12. Балонин Н. А., Сергеев М. Б. Матрицы локального максимума детерминанта // Информационно-управляющие системы. 2014. № 1. С. 2–15.
13. Балонин Н. А., Сергеев М. Б. Двуциклическая М-матрица 22-го порядка // Информационно-управляющие системы. 2014. № 2. С. 109–111.
14. Балонин Н. А., Сергеев М. Б. Нормы обобщенных матриц Адамара // Вестник СПбГУ. Сер. 10. 2014. Вып. 2. С. 5–11.
15. Балонин Н. А., Сергеев М. Б. О расширении ортогонального базиса в задачах сжатия видеоизображений // Вестник компьютерных и информационных технологий (ВКИТ) 2014. № 2. С. 11–15.
16. Балонин Н. А., Балонин Ю. Н., Сергеев М. Б. Вычисление матриц Мерсенна и Адамара методом Скарпи // Вестник информационных технологий, механики и оптики. 2014. № 3. С. 104–112.
17. Балонин Н. А., Балонин Ю. Н., Востриков А. А., Сергеев М. Б. Вычисление матриц Мерсенна-Уолша // Вестник компьютерных и информационных технологий (ВКИТ) 2014. № X. С. XXX–XXX. (в печати).
18. Сергеев А. М. Обобщенные матрицы Мерсенна и гипотеза Балонина // Автоматика и вычислительная техника. 2014. № 4. С. 35–43.



DISCUSSION


Многоуровневые М-матрицы, оптимальные в строгом смысле этого слова, стоят первыми в нашем списке артефактов благодаря критическому решению, обрывающему их ряд на 13-м порядке, тоже входящем в состав порядков особых матриц.

Задача Прокруста, матрицы Прокруста. Строго оптимальные по минимуму m-нормы квазиортогональные матрицы (максимума детерминанта) будем матрицами Прокруста. Их поиск представляет собой задачу, достаточно легко разрешимую на низких порядках итерационными методами. Качественно решение описывает следующая гипотеза.

Гипотеза. Малоуровневыми матрицами Прокруста нечетного порядка являются только первые пять матриц: A3, A5, A7, A9, A11 [2,3,12].

Легко заметить, что с ростом порядка n число нижних уровней оптимальных регулярных матриц подчиняется формуле

K=(n–1)/2


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

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

В семействе отмеченных матриц нечетного порядка есть три регулярные A3, A5, A11 и две нерегулярные A7, A9 матрицы. Субоптимальные регулярные матрицы R7, R9 по m-норме прилегают очень близко к оптимальным структурам.

MAX DET MATRICES COMPARISION


Cимметричная матрица третьего порядка X=O–2I, O состоит из 1, имеет детерминант 4, это превосходит определитель матрицы Мерсенна |det(M3)|=27/8=3.375. Они связаны сингулярным разложением, а попросту – имеют одинаковые собственные векторы. Матрица Мерсенна имеет еще и одинаковые по модулю собственные числа, вот и вся разница. Матрица с максимальным детерминантом пересчитывается в матрицу Мерсенна алгоритмом Прокруста.



Матрицы X3 с элементами {1, –1} и Мерсенна A3=M3 с элементами {1, –1/2}


X3=VDV', M3=VSV',


где S – матрица сигнатур {1, –1} для собственных значений D.

Оптимальная матрица 5-го порядка с определителем 48 относится к матрицам Рагхаварао, у нее есть общность с матрицей Ферма F5 (а не с матрицей Якобсталя), но проекцией Прокруста F5 не является (определитель проекции падает в 1000 раз).



Оптимальная матрица X5 и матрица Ферма F5


Итерационный алгоритм оптимизации подымает определитель трехуровневой теперь уже ортогональной матрицы до ее максимального значения – около 20.7.



Оптимальная матрица Прокруста A5


Оптимальная матрица 6-го порядка разделяет черты матриц Эйлера E6 и Белевича C6, последние можно получить заменой значений диагональных элементов с выборочной политикой знаков.



Оптимальная матрица X6 и матрица Белевича C6


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



Эквивалентные версии оптимальной матрицы X7




Матрица Мерсенна M7 и матрица Прокруста A7




Версия матрицы X7 и матрицы Прокруста A7


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



Оптимальные матрицы X7 и X9



Оптимальная матрица X9 и матрица A9



Оптимальная матрица X11 и матрица Прокруста A11




Матрица Прокруста A13 c m=0.309837, det=1/m13=4 123 513



Сопоставление матрицы Прокруста A13 и матрицы Рагхаварао R13


Число ее уровней несоотносимо с числом уровней матрицы A11 – ей предшествует последняя в ряду матриц Адамара, имеющая единственное представительство среди эквивалентных матриц. Определитель округленной матрицы 10 223 616 в полтора раза уступает максимальному для неортогональных матриц значению определителя матрицы Рагхаварао R13: 14 929 920.


CONFERENCE MATRICES AS MAXIMUM DETERMINANT MATRICS


Conference matrices – quasi-orthogonal maximum detherminant matrices of even orders, they are W(2n,2n–1) weighing matrices [1], due structuaral bounds they have some unknown orders: 66, 86 for first 2n≤100.

1) We take wholly random initial matrix, size 2n, n is odd.
2) It has No any structure (No any blocks), circulant block is a bound as we see by n=33 case
3) It has a minimal structure: 0 on diagonal and symmetry accordingly diagonal

Conjecture: maximum detherminant Cretan matrix, order 2n, n is odd (and sum of two squares, naturally), gives W(2n,2n–1).

For n=9, matrix has 2n2n=162–9=153 wholly unknown entries – a big number of variables. 153 leads to 153! combinations. It is big area of undefinity. Algorithm has No any information about future solution, matrix has no blocks. It is something like Mandelbrot fractal: it has 1 axe of symmetry and looks like random one. Demonstration procedure below resolves cases to order 26 easy.



Examples of wholly random W(18,17) and W(26,25)


1. Christos Koukouvinos and Jennifer Seberry, New weighing matrices constructed using two sequences with zero autocorrelation function – a review, J. Stat. Planning and Inf., 81 (1999), 153-182. ISSN 0378-3758/99.

Rambler's Top100