MAXIMUM DETERMINANT MATRICES
(EVEN ORDERS)




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


D. RAGHAVARAO | A.E. BROUWER | TABLE | ORBIT | X102 | CONVERTER


MAXIMUM DETERMINANT MATRIX TABLE



Порядки семейств: четные два Барбы и нечетные Барбы и Ферма F (оранж)


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

Семейства и простота. Часто встречаемые бициклы, большие порядков Барбы на единицу nB=k2+(k+1)2, 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.



Матрицы максимума детерминанта порядков 226 и 314


Бициклов много, D-оптимальные матрицы существуют с размером блока: 3; 5; 7; 9; 13; 15; 19; 21 ... 27; 31; 33; 37; 41; 43; 45; 49; 51; 55 ... 63; 69; 73; 75; 77; 79; 85; 87; 91; 93; 97; 103; 113; 121; 131; 133; 145; 157; 181; 183. Бицикл размера 46 есть (матрица Белевича сложнее) ! Циклические блоки размеров 11, 17, 29 отсутствуют: на порядках, где нет матриц Белевича, но есть W(n,n–2) (22, 34, не 58, 70, и т. п.) бицикл требует себе двойную кайму. Этим эта область и примечательна, но именно это редко где отмечают. Вопрос описания симметрий – исключительно важен для эффективного поиска последовательностей. Описание симметрии в лоб, что если есть элемент слева в позиции 2, то он есть и справа, в позиции 2, оно упускает из вида, что при циклическом смещении кода позиции смещаются. Факторизации типа a=[1,2]⊗a индифферентны к смещению. Код сокращается вдвое, это сорт "симметрии" тоже. Псевдоорбита [1,v–1] отвечает симметричным решениям, поэтому для матриц X46, X54 ее нет! Частный случай метода симметрий – метод орбит, который приносит успех на особых порядках.



Матрицы максимума детерминанта n=58 and 98


Порядки 22, 34, 70, 78, 94, n<100 и т.п., на которых n–1 – не сумма двух квадратов (но не 58), аппроксимируются бициклами с двойной каймой, из них только порядок 22 двоякосимметричен. Негациклические моноциклы встречаются, похоже, только на порядках 6 и 10. Интриги в этой области поменьше, поскольку здесь нет следа от порядков Ферма, фокус с удвоением матриц Ферма не проходит. Хотя можно предположить, что оптимум достигается экономией структуры, у не Ферма 34 клеток вдвое меньше. Эта интересная семья Ферма за пределами двух "официально признанных" семей интересна предположением, что на 2×257=514 тоже нечто подобное происходит (и что она основная семья!). Хольцман и Хади нашли матрицы 66, 150 цепочки витражей типа 1*7*2=14, 3*11*2=66, 5*15*2=150, 7*19*2=266, 9*23*2=414, ... (с помощью кронекерова произведения).



Матрицы F234 (Det/Max=0.758), X34 (Det/Max=0.969697)


ORBIT METHOD: ALGORITHM ON LINE


Орбиты. Циклические подгруппы xk позволяют изучить состав и характер множеств элементов входящих в мультипликативную группу кольца Z*v. Действие подгруппы H на кольцо Z*v дает все ее частные орбиты (строго говоря, орбитой группы именуются совокупность частных орбит), проще говоря, это итог масштабирования подгруппы элементами кольца. Умножение на g=0 дает частную орбиту {0}, умножение на g=1 дает саму подгруппу, на g=2 – следующую орбиту и т.п. Орбиты описывают симметрии генерируемых последовательностей. На вырожденных порядках 46, 50, 54, 90 и везде, где размер подгруппы минимален 1, решение дают укороченные орбиты и даже две разные орбиты для плеч бицикла.

С ВЫВОДОМ МАСШТАБОВ ОРБИТ


Выбор основания x. В первую очередь надо проверять простые числа 2, 3, 5, 7, .. и их степени, разумеется. Версия x1=2 годится для многих стартовых матриц невысокого порядка. Трюк с x1=2, 2*15=30, 31*2=62 проходит. Матрицы порядков 114 и 146 сидят на простых числах x1=7 (7*8=56, 57*2=114) и x1=2 (2*36=72, 73*2=146), матрица порядка 170 выловлена на квадрате x1=72=49 ((49–7)*2=84, 85*2=170), матрица 82 сидит на квадрате квадрата x1=24=16 ((16+4)*2=40, 41*2=82). Заметим, что верна 4 для порядка 86: (4–2)*21=42, 43*2=86. Для матрицы 226 x1=24=16 дает (16–2)*8=112, 113*2=226. Для матрицы 314 x1=39 (39*4=156, 157*2=314).

Смещенные орбиты. С ними связаны случаи, когда v–1 имеет несколько простых множителей. Орбита, заметная своей ограниченной длиной и угадываемая по резкому падению квадратичной невязки, отвечает множителю или смещенному произведению множителей: 186 (v–1=92=23*4, но x1=25), 206 (v–1=102=51*2=3*17*2, но x1=46), 226 (v–1=112=56*2=3*19*2, x1=16), 242 (v–1=120=60*2=3*5*8, x1=3!), 262 (v–1=130=65*2=5*13*2, но x1=53), 482 (v–1=240=3*5*16, x1=3*5=15!). Когда множители не уравновесить, балланс достигается на тривиальной орите.

Тривиальные орбиты. С ними связаны случаи (не всегда), когда n–1 или размер плеча – не простое число. Драгомир обращает внимание на порядок 126: n–1=125 и длина плеча 63, подгруппа тривиальна. Также n=91*2=182 и (9–3)*5*2=90 недосягаемо. Для n=111*2=222 имеем 11*10=110 или 121–11=110, тоже ничего не получается. Эти матрицы не простые: 91=7*13, 111=3*37. Для порядков 362 (n–1=192=361, v–1=180=90*2=5*9*4), 422 (n–1=421 и v–1=210=3*5*7*2) длины плеч – простые числа 181 и 211, но v–1 имеют в своих разложениях много множителей и выделить одну на всех орбиту (помимо тривиальной) проблематично.

Псевдоорбиты. Порядки, на которых n–1 – не простое число, сложны для взаимосвязанных между собой конференц-матриц и матриц максимума детерминанта. Например, матрица порядка 46 имеет размер плеча 23 (простое число), тем не менее показательная функция от 11=22/2 длиннее потребностей бицикла (составляет всю группу). Симметрии бицикла описываются бисетами: [1, x], x<22; нет орбиты [1,22]. Триплеты [1, x, y] содержат все возможные (x, y). Повидимому, все триплеты таковы, при случайном поиске часто выпадает [1,13,20]. С ними можно поступать также, как с частными орбитами, поэтому назовем их псевдоорбитами. Матрицы размеров 50, 54 и 90 с составными плечами отмечены тем же свойством. Порядок 50 сидит на бисетах [1,2], [1,3], ... и орбитах [1,5], [1,10], ... (второе число пропорционально 5), есть триплеты. Симметричная версия ловится на паре (5,7) для плеч [1,5] [1,7], но охотнее на (15,7). Порядке 54 сидит на бисетах [1,2], ... за исключением орбит (второе число пропорционально 9).

Ложка в стакане воды, преломление, это и есть метод орбит. Ложка, она одна. Часть ложки видна над стаканом, а часть, с изломом, видна в воде. Матрица максимума детерминанта сидит на экстремальной показательной функции, представленной фрагментарно орбитами. Индексы –1 в каждой строке бицикла совпадают с значениями элементов орбит. Другими словами, для SDS(n=2v=62;k1=15,k2=10;λ=10) например, это факторизация строк индексов элементов на общую подгруппу x=[1,2,4,8,16] длины 5 и множители o1=[4,24,28] длины 3=k1/5, o2=[6,20] длины 2=k2/5 в контексте кронекерова произведения a=x⊗o1, b=x⊗o2. Нетривиальная факторизация учитывает совпадение произведений элементов, дающих одни и те же адреса. Если подгруппы, потенциальные кандидаты на факторизацию, они видны воочию, то множители представляют собой искомую часть. Чем длиннее орбиты, тем короче поиск.

Последовательности бицикла a, b можно собирать буквально "на живую нитку" с учетом желаемого типа симметрии. В ортогональных задачах для описания матрицы хватает одной или пары пересекающихся орбит. Если ортогональность не подразумевается, последовательность нарезается на фрагменты-орбиты. Прием напоминает прижимание к потолку провисшей веревки для белья и относится к точным методам, он ищет целочисленный "резонанс" сообразно размеру задачи. Экстремальную показательную функцию масштабируют случайными числами и из полученных чисел составляют две последовательности длинами k1 и k2. Если подгруппа тривиальная, состоит из 1, имеем лишь масштабные коэффициенты, т.е. это обычный перебор. У сложных бициклов X46, X50, X54 плечи в ход идут и укороченные наборы вместо орбит.

Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 2016. № 1. С. 2–15.
Balonin N. A., Djocovich D. Z. Negaperiodic Golay pairs and Hadamard matrices. // Informatsionno-upravliaiushchie sistemy [Information and Control Systems], 2015, no. 5, pp. 2–17. doi:10.15217/issn1684-8853.2015.5.2 (негациклические бициклы)

EXTREMAL MATRIX CONJECTURES



Extremal by determinant orthogonal C-matrix W(46,45) and non orthogonal X46


Conjecture 1: if W(2v,2v–1) exists (indifferent to its form) then two circulant maximum determinant matrix with Ratio 1 (to Ehlich/Wojtas bound ) exists.
Conjecture 2: if such two circulant maximum determinant matrix exists then W(2v,2v–1) exists too (big doubts due orders 66, 86).



Extremal by determinant X66 and X86 (symmetric) matrices


As a matter of fact, number system has some strong logic: both these type of matrices have maximum determinant on own classes (orthogonal {0,1,–1} for W(2v,2v–1) and not orthogonal {1,–1} matrices). Let us taken in consideration the Mathon or BS-construction W(46,45). W(46,45) has no two circulant form, but it is important only the fact of existence. We have to have (indifferent to W(46,45)-form) from 1: two circulant X46 exists! And computer found X46 in this short form. Let us take in consideration, we have also X66, X86. If conjecture 2 is true, from existence of X66 and X86 (symmetric one) follows existence W(66,65) and W(86,85). This conjecture follows big doubts due weighing matrices are not binary matrices.



Extremal by determinant W(22,20) and X22 matrices



Extremal by determinant W(34,32) and X34 matrices


Conjecture 3: Let W(n=2v,n–2) weighing matrix exists, then two-border-two-circulant D-optimal desing exists and 86 is the last symmetric matrix order.
Conjecture 4: Order 22, v=11, is the last D-optimal desing with symmetric two-border-two-circulant matrix.



Extremal by determinant W(58,53) and X58 matrices


A'=A, B'=B for X22. Bound 32 for symmetric HM was wide proven, so i think, X22 is the last two-symmetric matrix, 34>32. Matrix X22 is different with X34 by type of symmetry. Order 58 is good for a system of classification due W(58,56) is absent. Orders 22, 34 where we met W(22,20), W(34,32) they have extremum on two border two circulant form. Order 22 has two symmetric A, B: the last signs of symmetry for these border-matrices. Order 86 can be the last symmetric among two-circulan matrices. We have only 7 such "symmetric" orders 6, 10, 14, 26, 50, 62, 86. A logic says: if 22 is the last for two-border construction, it could be the last two-circulant form 86 .

Ишмухаметов вынес слово "факторизация" в название книги, оно определяет тему, потому что остальные слова – общего характера. Заметим, что при построении бициклов мы ищем орбиты или псевдоорбиты, это факторизация последовательностей. Видимо, слово это емкое, оно передает суть. Книжка Ишмухаметова замечательная. Интересно, что порядок 90 у Мах Дет, похоже, особый, у него нет факторизации, это "целое число". Два дня компьютер висит на поиск факторизации 90 типа x=[1,t], а факторизация 98 ведь найдена ! Возможно такое, что матрицы Белевича того же порядка НЕ ПОДЧИНЯЮТСЯ правилу соответствия чисел и матриц, потому что n–1=65 разложимо на сумму квадратов, причем MAX DET n=66 есть, а Белевича 66 может не быть. Бицикл МАХ ДЕТ классический, у него уровня ДВА 1 и –1. Бицикл Белевича с нарушением, у него ТРИ уровня, он с 0, 1, –1. А правило должно касаться БИНАРНЫХ бициклов, это разрушает гипотезы вокруг Белевичей, они "волюнтаристы", у них выдран один зуб, на диагонали. То есть, у них нет ни факторизаций на случаи 66, 86, ни самих решений в виде бициклов.

SYMMETRIC TWO CIRCULANT MATRICES BOUND (86)



Матрицы максимума детерминанта n=50, 86


Получается стройная картина из 4 гипотез. Никто не знает, есть ли на свете С-матрицы 66, 86. Загадка XX века. Но С-матрицы и X-матрицы – это строгие максимумы на ортогональном и не ортогональном множествах матриц с элементами ≤1. Предположим, что, независимо от сложности структуры С-матрицы, сам факт ее существования тесно связан с существованием более простой по форме не ортогональной X-матрицы. Последняя же не стиснута ортогональностью. Нет давления связи. И в самом деле, для сложной по структуре из клеток матрицы C46 (конструкция Матона или BS) есть простая по форме X46. Что же мы можем извлечь из этого знания? А вот что. Загадка века имеет таки решение. Ведь X-матрицы 66, 86 находит метод орбит. В числовой системе дырок не бывает. Если простой X46 отвечает сложная C46, теперь и ребенок сделает вывод, что существование С66, С86 получило солидное подкрепление в виде довода: X66 и X86 есть и мы умеем их находить. Довольно важное размышление о числовой системе. Это ведь касается ВСЕХ сомнительных С-матриц, появляется методика проверки их существования. Про С66, С86 ранее ничего не было известно. Кстати, редко кто знает, что С-матрицы оптимальны по детерминанту. На стадии их оформления их давали как ортогональные {0,1,–1} матрицы с 0 на диагонали, и все.

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


МЕТОД ПРОЕКЦИЙ С ЛОКАЛЬНЫХ МАКСИМУМОВ X=sign(Cretan(2v))



Sireni Day matrices 62, 66 were calculated: Chagoda matrices X=sign(Cretan(62 or 66))


Для нахождения экстремальных не ортогональных матриц используем проекции ортогональных многоуровневых критских матриц X=sign(Cretan(2v)). Cреди матриц с каймой двоякосимметрична только матрица порядка 22.

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

TWO FAMILIES 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, задающих бицикл, а λ – общее число попарно совпадающих (пересекающихся) элементов первой и второй строк бицикла. Выбором переменных, оно сводится к уравнению круга, разрешимого в целых числах, и сказывается на уравнении для уровней, разрешимого в вещественных и иррациональных числах.

Уравнение окружности x2+y2=p+λ(v–2p) для элементов x, y параметров SDS r=px=k1, s=py=k2, p=k1+k2–λ, задает достижимое целочисленное решение. На порядке 38 ортогонализованная матрица максимума детерминанта имеет SDS(38;6,7;4), соответственно p=9, x=3, y=2. Уравнение x2+y2=p+λ(v–2p)=13 разрешимо при v=19>2p=18. Окружность радиуса q2 всегда проходит через целую точку (x=q, y=0).

Family 1 (big family). Порядки n=2(q2+q+1)=6, 14, 26, 42, 62, 86, 114, ... разрешимы на k1=q(q+1)/2, k2=q(q–1)/2, где q=k1k2 – радиус окружности x2+y2=k1+k2=q2, p=k1=(n–2)/4, λ=k2=pq, q2=k1+k2=k, в таком случае n–2p–λ=n–2k1k2: b=(k2±sqrt(k22–(n–2k1k2)k1))/(n–2k1k2). Для порядков 114 включительно x=q. Матрица 6 (x=2) двоякосимметрична, у симметричных матриц симметрия плеч чередуется 14 (x=2), 26 (x=4), [не симметрична 42], 62 (x=2), причем 62 и 86 (x=4) имеют одинаковый тип симметрии.

Family 2 (little family). Порядки n=2(2q2+2q+1)=10, 26!, 50, 82, 122, ... разрешимы на k1=k2=q2, где sqrt(2)q – радиус окружности x2+y2=2q2, x=y=q, λ=q2+q, p=q2q=(n–2)/4, q2=(k1+k2)/2=k/2. Для порядков 50 включительно x=2q+1. Матрица 10 (x=2) двоякосимметрична, [не симметрична 42], симметрична 50 (x=3 или 6). На порядке 50 плечи симметричного бицикла быстрее находятся при привлечении для них двух разных орбит.

Отметим, что q=6 SDS(86;15,21;15) есть в каталоге, хотя q – не простое число и не степень его, вопреки более жесткому требованию (справедливому для бицикла с k1=k2, тут недоразумение, см. для q=6, n=86 [1]). При высокой статистике повторения в поиске одной строки бицикла, ее можно замораживать, и тогда поиск второй строки резко ускоряется.

Условие ортогональности строк (столбцов) бицикла с элементами a, –b при превалировании элементов –b имеет вид λa2–2(k1+k2–λ)ab+(n–2(k1+k2)+λ)b2=0, k1, k2 < p, p=k1+k2–λ=(n–2)/4. При a=1 квадратное уравнение для модуля уровня b матрицы (n–2p–λ)b2–2paba2=0 дает корни b=(p±sqrt(p2–(n–2p–λ)λ))/(n–2p–λ). Отметим, SDS(22;4,4;2), эта матрица есть в каталоге, но она не оптимальная, ортогонализации не подлежит, так как p–(n–2p–λ)λ=–2.

Для ускорения поиска парных бинарных последовательностей ортогональных бициклов их проверяют на комплементарность, тестируя взаимные инварианты, например спектральную плотность (power spectral density, PSD-тест). Вместо пар комплементарных последовательностей можно искать пары комплементарных друг другу сумм элементов, извлекая из сумм потом зависимые от них последовательности O={0}O2O3...Om. Таблицы найденных последовательностей порядков первой сотни (и более: таблица) не учитывают симметрию. Из ранних публикаций указывают [1] (и Янга 60-х, конечно).

[1] T. Chadjipantelis, S. Kounias, Supplementary difference sets and D-optimal designs for n ≡ 2 (mod 4) Discrete Math., 57 (1985), pp. 211–216

ОЦЕНКА ДЕТЕРМИНАНТА СВЕРХУ


Ehlich и Wojtas: |det(A)|2≤4(n–2)n–2(n–1)2, максимум достигается на матрицах X, порождающих блочно диагональную форму X'X, блок (v–2)I+2J, n=2v, 2(v–1) – сумма двух квадратов. Округленные матрицы Эйлера отличаются знаками блоков (n+2)I–2J. Начальные матрицы бициклы – продукт пересечения пар экспонент со случайным подбором показателей в поле GF(2m), где 2m выбирается близко к размеру матрицы n. Поиск в поле GF(p) связывают с расчетом линейных комбинаций нескольких экспонент. Первые таблицы составлял Янг, позднее Драгомир и Кукувинос с Илиасом. Среди бициклов существуют матрицы порядков n=2(q2+q+1), q – степень простого числа (и оптимальные матрицы на 1 меньших прядков), конкретно найдены: 6, 10, 14, 18, (not 22), 26, 30, 38, 42, 46, 50, 54, (not 58), 62, 66, (not 70), 74, (not 78), 82, 86, 90, 98, 102, 110, 114, 118, 122, 126. Наименьший неизвестный порядок 198 ! Also мало известны 146 (nick here), 158, 170 (nick here), 182, 186, 194, 206, 226 (nick here), 242, 262, 266, 290, 314, 362, 366, 482 (by Dragomir 2012).

Для нечетных порядков оценку верхней границы уточнил Гвидо Барба |det(A)|2≤(n–1)n–1(2n–1), максимум достигается на порядках, для которых 2n–1 – полный квадрат (необходимое условие, иначе нарушается целочисленность). Эквивалентное условие (гипотеза): n=k2+(k+1)2 [*]. Оптимум достижим на матрицах Рагхаварао и Андрэ Брауэра. Матрицы порядков 5, 13, 25, [41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п.] сходны с адамаровыми в том, что достигают по значению детерминанта отмеченной границы. На четных порядках 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) – сумма двух квадратов.

Блочные матрицы также встречаются, например, порядок 66 описал Хади, дав пример блочно составной матрицы с каймой, продукта умножения блоков размеров 6×11, постро

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


       THIS SITE INSTUMENT
   ALPHA WIKI-MANUAL       INTERNET MATLAB ON LINE


© Nickolay Balonin


ТАБЛИЦА



Rambler's Top100