EULER MATRICES



© Nickolay Balonin, 6.09.2014


МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ БИЦИКЛОВ


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

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

Уравнение круга x2+y2=p+λ(v–2p) для элементов x, y параметров SDS r=px=k1, s=py=k2, p=k1+k2–λ, задает достижимое целочисленное решение. Для всех матриц Эйлера x=y=1 круг с квадратом радиуса p+λ(v–2p)=2 разрешим при целых v=n/2=2p–1, λ=p–2.

Условие ортогональности строк (столбцов) бицикла с элементами a, –b при превалировании элементов a=1 имеет вид (n–2(k1+k2)+λ)a2–2(k1+k2–λ)abb2=0. Для матриц Эйлера k1=k2=p–1, p=k1+k2–λ=(n+2)/4. Корни a=(p±sqrt(p2–(n–2p–λ)λ))b/(n–2p–λ) уравнения (n–2p–λ)a2–2pabb2=0. Из a=(p±sqrt(2p))b/p=1 (с учетом λ=p–2, (n–2p–λ)=p, где p=t при n=4t–2) получаем амплитуду отрицательных элементов b=t/(t±sqrt(2t)).

На порядке 38 матрица Эйлера имеет SDS(38;9,9;8), соответственно p=10, x=1, y=1. Уравнение x2+y2=p+λ(v–2p)=2 разрешимо при v=19<2p=20. Ортогонализованная матрица максимума детерминанта имеет SDS(38;6,7;4), у нее превалируют отрицательные элементы, соответственно p=9, x=3, y=2. Уравнение x2+y2=p+λ(v–2p)=13 разрешимо при v=19>2p=18. Похоже, что у проекций матриц абсолютного максимума детерминанта условие ортогональности сводится к требованию v>2p, для матриц Эйлера v<2p, для матриц Адамара v=2p!

EULER MATRIX TABLE




Meander of Hadamard Family Matrices


Константы, расчет которых проще проверки ортогональности пары бицикла, составляют основу ее поиска проверкой симметрии (есть еще перспектива PSD-теста (2).

АЛГОРИТМ ПРЯМОГО ПОИСКА


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

Симметрично-кососимметричные матрицы Эйлера пропорциональны порядку первой стартовой матрицы q×6, q – простое нечетное число, это 6, 18, 30, 42, не 54, 66, 78, не 90, 102 и т.п. Поэтому просто случайные последовательности для генерации матриц Эйлера, это не интересно. Их надо генерировать правильно на основе столбца единиц и пар инвертированных по порядку столбцов блоков с равными и противоположными знаками.



Симметрично-кососимметричная E66


На такой почве хорошо находятся также двоякосимметричные и двоякокососимметричные матрицы. Порядки 50=2×25, 54=2×27, 98=2×49, на которых симметрия нарушается, связаны с длинами последовательностей, равных квадратам, кубам и т.п. простых чисел. Так как поле Галуа для таких размеров блоков можно построить, вопрос их поиска сводится к построению соответствующей процедуры (возможно, через негациклические матрицы). Отдельно стоит порядок 2×45=90, для которого нужны либо более изощренные подходы, либо решение проблемы в лоб, тяжелым поиском.

АЛГОРИТМ ОПТИМИЗАЦИИ ДЕТЕРМИНАНТА


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

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

РАСЧЕТ СИМВОЛАМИ ЛЕЖАНДРА


Матрица Эйлера как ядро бициклической матрицы Адамара с двойной каймой, порядок клетки бицикла v=(n–2)/2 – простое число (матрицы сопровождают список простых чисел). Это путь конструирования матрицы из матрицы Мерсенна или Зейделя вдвое меньших размеров.

ПОКАЗАТЕЛЬНЫЕ ФУНКЦИИ В ПОЛЕ ГАЛУА


Это восходящий к идее Секейреша путь конструирования бицикла размера n из пар комплементарных последовательностей, процедура использует точки пересечения орбиты xk с ее же значениями, смещенными на ±1 в поле GF(q): q=n+1=pm.

Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 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 (негациклические бициклы)

МЕТОД ОРБИТ


Орбиты, это масштабированная множителями показательная функция xk в конечном поле Галуа или мультипликативном кольце Zv. Метод орбит использует факторизацию строк индексов элементов на общую подгруппу xk и множители o1, o2 в контексте кронекеровых произведений

a=x⊗o1, b=x⊗o2.



Euler matrices E6 and E10



Euler matrices E14* and E18



Euler matrices E22 and E26



Euler matrices E30 and E34



Euler matrices E38 and E42



Euler matrices E46 and E50*



Euler matrices E54* and E58



Euler matrices E62 and E66



Euler matrices E70 and E74



Euler matrices E78 and E82



Euler matrices E86 and E90*



Euler matrices E94 and E98*

EULER MATRIX SDS


EULER MATRICES

Euler matrices, E, order n=2m=4t+2, constructed with two square blocks A, B with levels a=1, –b; a=1, b=t/(t+sqrt(2t)), t=(n+2)/4.

Euler matrices, E, order n=2m=4t+2, constructed with two square blocks A, B with levels a=1, –b; a=1, b=t/(t+sqrt(2t)), t=(n+2)/4.

Three level Belevitch matrices of even orders n=4t–2 can be exist if n–1 is the sum of two squares. For omit orders (Belevitch matrices are absent) there are four level quasi-orthogonal matrices: Euler matrices. Function of level can be written as b=t/(t+(2t)1/2). Formulae (t–(2t)1/2)/(t–2) has special case: b=1/2, t=2. Every second Euler matrix can be constructed by A=B – Mersenne matrix of order 4k–1; the other way is based on chains idea, see [5], [8], [11] in Russian.

E=
 A 
 B 
 BT 
 –AT 



The historic aspect. Two number families of odd prime numbers 4k+1 and 4k–1 were researched by Fermat and Euler. Euler had no interest to number theory – his friend, non mathematician, Goldbax (1742) taken his attention, that every even number is a sum of two primes: n = 2m = p + q: 6 = 3 + 3, 8 = 5 + 3, 10 = 3 + 7, etc. Goldbax's conjecture is non resolved today. Euler observed the case n = a2 + b2. 1749 year he has found the resonable solution (WIKI).

EULER MATRICES CATALOGUE | | MERSENNE MATRICES CATALOGUE

TWO CIRCULANT MATRICES



Euler matrix E6



Mersenne matrix M7 and Hadamard H8



Euler matrices E10 and E14



Mersenne matrices M11 and M15



Hadamard matrices H12 and H16

MORE MATRICES FROM CATALOGUE


The Euler matrices exist as extremum: they can be determinet independently as a solution of optimisation (non combinatoric) varying task for maximum determinant search, indifferently to their orders.

Balonin's conjecture says ([8, 13, 19], in Russian, below or PDF): Euler matrices of orders n=4t–2, t is an integer, exist (the ways to prove observed here [10], [13]): there is modified Sylvester algorithm [5, PDF] to build fractal construction for all orders n=2m, m = 2k–1.

Let us note, we know and can calculate its level for any order n=4t–2: it exists also as varying matrix with free choosen moduli level b, taken from equations of orthogonality. This function is monotonous and has no singular points showing the matrix does not exist.

The family 4k+1 has so called Fermat numbers. If there is Fermat number, there is Fermat matrix. The family 4k–1 consists Mersenne numbers. If there is Mersenne number, there is Mersenne matrix. Look also: Mersenne matrices and Fermat matrices.

EULER MATRIX LEVEL b


GALOIS FIELDS PROCEDURE


The existence of Hadamard matrices H, it follows from existence of Euler matrices: they exists for all orders n=4k–2, if meander is true, the Hadamard conjecture* is theorem. Transitions between E-, M-, H-matrices illustrated by on line algorithm are placed below.

*) See the conjecture 1 Kotsireas, Koukouvinos, Seberry, 2005 also, it commented by big set of samples calculated by generalised Legendre pairs: Fletcher, Gysin, Seberry, 2001.


DESCRIPTION (IN RUSSIAN)


Матрицы Эйлера. Модульно-двуровневые матрицы с ортогональными столбцами и элементами {±a, ±b}, b<a, порядков, равных числам n=2k, k – нечетное число, следующего вида

E2k=
 Ak 
 Bk 
 BTk 
 –ATk 


где Ak, Bk – матрицы нечетного порядка, уровень b=a/2 при n=6, b=(q–(8q)1/2)a/(q–8), q=n+2 (порядок матриц Адамара) при n>6. Матрицы Эйлера сосуществуют с матрицами Белевича и дополняют их, если последние не существуют.

Оба основания Ak, Bk равны симметричной матрице Адамара-Мерсенна в случае значений k, равных числам Мерсенна. Последовательность вычисляемых отсюда матриц Адамара-Эйлера обобщает последовательность Сильвестра и порождает модифицированные функции Родемахера и Уолша (аналоги косинусных и синусно-косинусных базисов) с амплитудами, отличными от единичного значения.

Матрицы Мерсенна M и Эйлера E в связках образуют замечательные структуры, названные меандрами, в силу сходства их со знаменитым орнаментом. Эта структура описывает происхождение всех матриц Адамара H. Матрицы Зейделя S при этом играют роль предиктивных матриц отличных от центрального меандров, связанных с матрицами Белевича C.



Меандры связи матриц семейства Адамара


Структура меандра, как таблица Менделеева, позволяет предсказать существование на порядках матриц Адамара младшего аналога матриц Эйлера, e-матриц (младших матриц Эйлера).

Разрешимость известной проблемы Адамара следует из связи матриц Эйлера с матрицами Мерсенна на единицу большего их порядка и далее с матрицами Адамара с двойной каймой. Доказано, что матрицы Мерсенна и взаимно-связанные с ними матрицы Эйлера на единицу меньшего их порядка, существуют.

ОБЗОР МАТРИЦPDF | ТЕОРЕМЫ О СУЩЕСТВОВАНИИPDF




Связь матриц Мерсенна M7 и Эйлера E14



Связь матриц Эйлера E14 и Мерсенна M15



Матрицы Мерсенна M15 и Адамара H16


Форма матриц Адамара с двойной каймой и двуциклическим ядром с точностью до знака элементов совпадает с формой
Флетчера-Гисина-Себерри (2001), а следствие из существования матриц Эйлера совпадает с предположением 1 Котсиреаса-Кукувиноса-Себерри (2005).

Матрицы Эйлера были предложены для замещения матриц Белевича на порядках n=4k–2, когда матрицы Белевича не существует (с формулировками существования связан критерий Эйлера, отсюда название).



Связь матриц Эйлера и Белевича (диагональ адаптирована) порядка 6


Существовать им проще, поскольку число уровней для матриц Эйлера расширено с 3 (у Белевича) до 4, кроме того, не запрещены иррациональные значения уровней. Вместе с тем, из доказательства существования матриц Эйлера для всех порядков вида n=4k–2 следует доказательство гипотезы Адамара.

ДВУЦИКЛИЧЕСКИЕ МАТРИЦА ЭЙЛЕРА


Матрицы Эйлера, в простейшем случае порядка n=2k, k – простое число, связаны с порождающими их циклическими матрицами Мерсенна или Зейделя. Вместе с тем, матрицы Эйлера определены достаточно широко как матрицы с двумя A, B основаниями, равными, в частности, матрицам Мерсенна при условии A=B=M.

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

Двуциклические матрицы Эйлера существуют на критических для циклических матриц Мерсенна или Зейделя, в частности, и для матриц Белевича, в общем, порядках: 18 (нет циклической матрицы Зейделя S9), 22, 34, 58, 66, 70, 86, ... (нет матриц Белевича порядков 22, 34, 58, 70, .., а вопрос их существования (и структуры) для порядков 66, 86, ... открыт), 30 (нет циклической матрицы Мерсенна M15), и т.п.

Пары порождающих циклические основания A, B последовательностей дают представление о парных символах Лежандра.



Связь матриц Зейделя S5 и Эйлера E10



Связь матриц Мерсенна M7 и Эйлера E14



Матрицы Эйлера E18 и E22



Матрицы Эйлера E26 и E30



Матрицы Эйлера E34 и E38



Матрицы Эйлера E42 и E46


ПОСТРОЕНИЕ НА ОСНОВЕ МАТРИЦ ЗЕЙДЕЛЯ


Построение матрицы Эйлера возможно на основе матриц Зейделя

E2k=
 Sk 
 S*k 
 S*k 
 –Sk 



где S* – матрица, с переставленными элементами a, –b (знаковое сопряжение, обобщенное инвертирование), диагональный элемент матрицы Зейделя выводится в 1.

Составные матрицы: S9 = M3 ⊗ M3!



Матрицы Зейделя S9 и Эйлера E18


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




Матрицы Эйлера последовательности Сильвестра порядков 6 и 14


МАТРИЦЫ ЭЙЛЕРА ПОРЯДКА 2, 6, 10, 14





ГИСТОГРАММЫ УРОВНЕЙ






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


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



Расчет матрицы Эйлера по матрице Мерсенна


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

СИММЕТРИРОВАНИЕ МАТРИЦЫ ЭЙЛЕРА


Модульно-двухуровневые матрицы с ортогональными столбцами и элементами {±a, ±b}, b<a порядков n=4k–2 отличаются от матриц Адамара-Эйлера, в общем, отличием внедиагональных блоков, у симметричных форм

En=
 An/2 
 Bn/2 
 BTn/2 
 –An/2 



причем b=a/2 при n=6, b=(q–(8q)1/2)a/(q–8), q=n+2 (порядок матриц Адамара) при n>6...



Матрица Эйлера до и после симметрирования


СБАЛАНСИРОВАННАЯ ФОРМА


Существует сбалансированная по количеству положительных и отрицательных элементов матрица Эйлера, она строятся коммутативным-сопряжением внедиагональных клеток (с взаимно-переставленными элементами уровней):

En=
 An/2 
 Bn/2* 
 BTn/2* 
 –An/2 



причем b=((n+2)–(8n)1/2)/(n–2). На десятом порядке это ведет к матрице с уровнем 1–g (матрица с дефицитом g=0.618.. высоты уровня), на пятом порядке ей соответствует матрица Зейделя с аналогичным уровнем и диагональю на уровне половины золотого сечения g.



СОПОСТАВЛЕНИЕ С МАТРИЦАМИ БОЛЕЕ ВЫСОКОГО ДЕТЕРМИНАНТА




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


Матрицы максимального детерминанта (неортогональные) не утрачивают на десятом порядке циклической природы, этим они отличаются от ортогональных матриц Эйлера. В структуре ортогональной матрицы Белевича порядка 10 отчетливо проступают кайма и составляющие ее циклические блоки третьего порядка (поскольку 9=3x3).



Ортогональная матрица Белевича C10


IN ENGLISH

1. 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.
2. Balonin N. A., Vostricov A.A., Sergeev M.B. Two-circulant golden ratio matrices // Informatsionno-upravliaiushchie sistemy, 2014, № 5 (71), pp. 5–11.
3. N. A. Balonin, Jennifer Seberry. A Review and New Symmetric Conference Matrices // Informatsionno-upravliaiushchie sistemy, 2014, № 4 (71), pp. 2–7.
4. Balonin N. A. , Seberry, Jennifer. Visualizing Hadamard Matrices: the Propus Construction // Australasian Journal of Combinatorics (submitted 6 Aug 2014).
5. Сергеев А. М. Обобщенные матрицы Мерсенна и гипотеза Балонина // Автоматика и вычислительная техника. 2014. № 4. С. 35–43. (in English | Springer)

IN RUSSIAN

1. Балонин Н. А., Мироновский Л. А. Матрицы Адамара нечетного порядка // Информационно-управляющие системы. 2006, № 3. C. 46–50.
2. Балонин Н. А., Сергеев М. Б. М-матрицы // Информационно-управляющие системы. 2011. № 1. С. 14–21.
3. Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Мерсенна // Информационно-управляющие системы. 2012. № 5. С. 92–94.
4. Балонин Н. А., Сергеев М. Б., Мироновский Л. А. Вычисление матриц Адамара-Ферма // Информационно-управляющие системы. 2012. № 6. С. 90–93.
5. Балонин Н. А., Сергеев М.Б. О двух способах построения матриц Адамара-Эйлера // Информационно-управляющие системы. 2013. № 1. С. 7–10.
6. Балонин Н. А. О существовании матриц Мерсенна 11-го и 19-го порядков // Информационно-управляющие системы. 2013. № 2. С. 90–91.
7. Балонин Н. А., Сергеев М. Б. М-матрицы и кристаллические структуры // Вестник Магнитогорского государственного технического университета им. Г.И. Носова. 2013. № 3. С. 58–62.
8. Балонин Н. А., Сергеев М. Б. К вопросу существования матриц Адамара и Мерсенна // Информационно-управляющие системы. 2013. № 5. С. 2–8.
9. Балонин Н. А., Сергеев М. Б. Взвешенная конференц-матрица, обобщающая матрицу Белевича на 22-м порядке // Информационно-управляющие системы. 2013. № 5. С. 97–98.
10. Балонин Н. А., Сергеев М. Б. Матрица золотого сечения G10 // Информационно-управляющие системы. 2013. № 6. С. 2–5.
11. Балонин Н. А., Сергеев М. Б. Матрицы локального максимума детерминанта // Информационно-управляющие системы. 2014. № 1. С. 2–15.
12. Балонин Н. А., Сергеев М. Б. Двуциклическая М-матрица 22-го порядка // Информационно-управляющие системы. 2014. № 2. С. 109–111.
13. Балонин Н. А., Сергеев М. Б. Нормы обобщенных матриц Адамара // Вестник СПбГУ. Сер. 10. 2014. Вып. 2. С. 5–11.
14. Балонин Н. А., Сергеев М. Б. О расширении ортогонального базиса в задачах сжатия видеоизображений // Вестник компьютерных и информационных технологий (ВКИТ) 2014. № 2. С. 11–15.
15. Балонин Н. А., Балонин Ю. Н., Сергеев М. Б. Вычисление матриц Мерсенна и Адамара методом Скарпи // Вестник информационных технологий, механики и оптики. 2014. № 3. С. 104–112.
16. Балонин Н. А., Балонин Ю. Н., Востриков А. А., Сергеев М. Б. Вычисление матриц Мерсенна-Уолша // Вестник компьютерных и информационных технологий (ВКИТ) 2014. № X. С. 51–55.
17. Балонин Н. А., Сергеев М. Б. Вычисление матриц Мерсенна методом Пэли. Известия высших учебных заведений. Приборостроение. 2014. № 10. С. 38–41.

Rambler's Top100