MERSENNE MATRICES



© Nickolay Balonin and Jennifer Seberry, 6.09.2014


THE STARTING MATRICES



Two Mersenne matrices M3

CIRCULANT MATRICES





Mersenne matrices of orders 3, 7, 11, 19

THEOREM: (WHITEMAN, STANTON-SPROTT)


Let p and q=p+2 be twin primes (powers) then there exists a circulant SBIBD(pq,(pq–1)/2, (pq–3)/4). It gives circulant Mersenne matrices orders 15, 35, ets.



Mersenne matrices M15 and M35



Квазиортогональные двухуровневые {1,–b} матрицы порядков 4t–1 с уровнем b=t/(t+sqrt(t)), регламентированным частным множеством их на порядках Мерсенна *). По гипотезе Балонина Н.А. матрицы Мерсенна расширяемы без особенностей на все указанное множество порядков (тесно связана с гипотезой Адамара для матриц Адамара).

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

Простые числа Мерсенна образуют последовательность: 3, 7, 31, 127, 8 191, 131 071, 524 287, 2 147 483 647, 2 305 843 009 213 693 951, 618 970 019 642 690 137 449 562 111, 162 259 276 829 213 363 391 578 010 288 127, 170 141 183 460 469 231 731 687 303 715 884 105 727, … (последовательность A000668 в OEIS)

Показатели k простых чисел Мерсенна образуют последовательность: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433, 1 257 787, 1 398 269, 2 976 221, 3 021 377, 6 972 593, 13 466 917, 20 996 011, 24 036 583, 25 964 951, 30 402 457, 32 582 657, … (последовательность A000043 в OEIS)

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

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


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

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


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

МЕТОД ОРБИТ


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

ГЕНЕРАТОРЫ МАТРИЦ МЕРСЕННА


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



Круги на воде (сложное в стесненном пространстве) и биллиард (встречи в просторном)


Роль пространства состояний, задающих арифметику, играют конечные поля GF(p) и GF(2). Траектории генераторов искусственного хаоса "развертывает" до матрицы сдвиговый регистр развертки – еще одна динамическая система.

Динамические модели размера m, это, в частности, рекурсии: Xk=FXk–1, k=1, 2, 3, ... Вектор Xk от начального состояния X0 стремится к главному собственному вектору S матрицы F, если система устойчива. Когда доходит, процесс замирает на его воспроизведении. Динамическая система исчерпывает свое разнообразие. Возьмем теперь в качестве выхода системы одну компоненту вектора состояния. Этот колебательный процесс мы заводим в сдвиговый регистр. Запускаем, и сдвиговый регистр заполняет сдвигами циклическую матрицу.



Генератор и сдвиговый регистр, две динамические системы


Заметим, попутно, что сдвиговый регистр тоже описывается моделью Yk=FYk–1, где F – фробениусова матрица. Мы малой динамической системой возбуждаем другую, систему побольше и "без трения", образовав выходом первой системы вектор начального состояния Y0 второй. Если матрица, заполненная сдвиговым регистром, ортогональна, она такова же, как и матрица Адамара. Обобщает ее.

Констатируем. Динамическая система порядка m исчерпывает свое разнообразие за v=2m–1 шагов. Ее выход – процесс – с помощью сдвигового регистра (модель волнообразования бассейна, простая, тоже, динамическая) мы заполняем матрицу. Добавляем кайму. И это дает матрицу Адамара.


Уравнения динамических систем в GF(2). Дискретная модель маятника Xk=FXk–1, m=2 – порядок модели, k – целое, описывает все те же колебания маятника от начального состояния, где параметры фробениусовой матрицы соответствующим образом пересчитываются, чтобы сохранить не только качественное, но и количественное подобия моделей. Наращивая размер вдвое, мы переходим к модели, восходящей в первооснове своей к двузвенной конструкции маятника (к модели двойного маятника). В более общем случае перед нами предстает модель колебания нити или тросовой системы, для которой можно брать в рассмотрение четные и нечетные размеры модели динамической системы.

Генераторы последовательностей в GF(2m). Рассмотрим динамическую систему Xk=FXk–1 с элементами и вектором состояния, определенными в поле GF(2), X0=[a0, a1, … , am–1]T – вектор ее начального состояния, ak = CXk, при С=[1, 0, … , 0, 0], – выход.

Модель дает бинарную последовательность a=[a0, a1, … , av–1] элементов со значениями {0, 1}, где первые m членов последовательности равны элементам вектора начального состояния, а остальные vm элементов дополняют значения выхода динамической системы. Последовательности длины n=v+1=2m, состоящие из 1 и продуктов циклического сдвига a, можно рассматривать, в свою очередь, как элементы поля GF(2m).

Вместе с единичным элементом, они образуют матрицу A с одной каймой и циклическим основанием, которая переходит в матрицу Адамара при замене 0 на –1 при подходящем выборе вектора начального состояния в пространстве состояний.



Матрицы Адамара порядков n=2m: 16 и 32


Порядки матриц n=2m известны как сильвестровы, сильвестрова конструкция образуется вложением матрицы Адамара в самою себя, но при вложении не получается циклическая структура, порождаемая динамическими моделями осцилляций. Тем не менее, это матрицы эквивалентные, см. линк ниже. Отметим, что матрицу порядка 16 не найти через символы Лежандра, поскольку 15 – не простое число. Удаление каймы ведет к матрице Мерсенна.

MERSENNE AND HADAMARD MATRICES



Mersenne matrix M11 and Hadamard matrix H12

MERSENNE MATRICES CATALOGUE | | EULER MATRICES CATALOGUE


Mersenne matrix *). A quasi-orthogonal matrix, named Mersenne matrix M [3, 8], is a two-level quasi-orthogonal matrix of order n with level functions a=1, –b; where b=t/(t+sqrt(t)), t=(n+1)/4. Function of definition can be written b=(tt1/2)/(t–1) for matrices of order n=4t–1, t is an integer. Special case: b=1/2, for t=1, n=3. The family orders covers Mersenne numbers n = 2k–1 = 3, 7, 15, 31, 63, 127, .. (OEIS-sequence A000225), they may be prime but also non prime numbers.

Balonin's conjecture says ([6], in Russian, below or PDF): Mersenne matrices of orders n=4k–1, k – integer number, exist (the ways to prove observed here [8], [11]): there is modified Sylvester algorithm [3, PDF] to build fractal construction for all orders n = 2k–1. We give also one circulant, two-circulant constructions below.

Taniyama's conjecture concerns the co-existence of elliptic curves and modular forms. Elliptic curves and modular forms are so different from each other, that we could not say, that elliptic curves could be made to give modular forms. Similarly many named sequences from number theory co-exist with families of quasi-orthogonal matrices. If there is Mersenne number, there is Mersenne matrix. Look also: Fermat matrices and Euler matrices.

SYLVESTER SEQUENCE (IN RUSSIAN)


Последовательность матриц Адамара-Мерсенна обобщает последовательность матриц Сильвестра на нечетные значения порядков матриц n=2k–1, порождает модифицированные функции Родемахера и Уолша – аналоги косинусных и синусно-косинусных базисов.



Матрицы Сильвестра-Мерсенна 7 и 15 порядков


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

M2k+1=
 a 
 –bT 
 eT 
 –b 
  Mk 
 Mk 
 e 
  Mk 
 Mk* 



где Mk* – коммутативно-сопряженная матрица c взаимно-переставленными элементами уровней, субвекторы e и b содержат элементы a=1 и b; b=a/2 при n=3, b=(q–2q1/2)a/(q–4), q=n+1 (порядок матриц Адамара) при n>3, структура первой матрицы – диагональная или (нормальная форма матрицы) трилистник

M3=
 –b 
 a 
 a 
 a 
 –b 
 a 
 a 
 a 
 –b 
M3=
 a 
 –b 
 a 
 –b 
 a 
 a 
 a 
 a 
 –b 


МАТРИЦЫ МЕРСЕННА ОБЩЕГО ВИДА


Матрицы Мерсенна. Двухуровневые квазиортогональные матрицы порядков n=4k–1 с элементами {a=1, –b}, в столбце (строке) количество элементов b<a на единицу меньше, чем a. Значения b=a/2 при n=3, b=(q–2q1/2)a/(q–4), q=n+1 (порядок матриц Адамара) при n>3.



Отличающиеся от Сильвестровых матрицы M11, M19



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

Гипотеза Балонина. Матрицы Мерсенна для всех значений нечетных порядков n=4k–1 существуют. Аналогична гипотезе Адамара о существовании матриц Адамара четных порядков, равных 1, 2 и 4k, базирующейся на опубликовании Адамаром матриц 12 и 20 порядков. Ниже приведены соответствующие им матрицы Мерсенна 11 и 19 порядков.

Отличаются от нормальной формы матриц Адамара-Мерсенна, в общем, автономией их внедиагональных блоков

Mn=
 a 
 –bT 
 eT 
 –b 
  A(n–1)/2 
 B(n–1)/2 
 e 
  BT(n–1)/2 
 A(n–1)/2* 



где Ak* – коммутативно-сопряженная матрица c взаимно-переставленными элементами уровней, субвекторы каймы b, e содержат b и a=1.

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