FERMAT MATRICES



© Nickolay Balonin and Jennifer Seberry, 6.09.2014


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

xp–1+xp–2 + …+ x + 1 = 0


при простом p должна определяться выражением p=1+22k (теорема Гаусса). Точку в деле построения правильных многоугольников поставило нахождение построений 17-, 257- и 65537-угольника. Первое было найдено Йоханнесом Эрхингером в 1825 году, второе – Фридрихом Юлиусом Ришело в 1832 году, а последнее – Густавом Гермесом в 1894 году.

Более общий ряд достижимых порядков определяется произведениями степеней двойки на произведения чисел Ферма (3, 4, 5, 6, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 51, 60, 64, 68, 80, 85, 96, ... ), см. wiki. Правильные 3-, 4-, 5-, 6-, 8-, 10-, 12-, 15- и 16-ки были построены еще древними геометрами.

Матрицы Ферма. Ортогональные матрицы порядков n=4t+1 с каймой и двухуровневым (a, b) ядром (core), отвечающем структуре регулярной матрицы Адамара порядков 4u2. Для порядков, включающим числа Ферма: 3, 5, 17, не 33, [65], не 129, 257, не 513, [1025], не 2049, [4097], не 8193, [16385], не 32769, 65537 (!), .. есть рекуррентный алгоритм построения.

Трехуровневые матрицы Ферма, F, {a=1, –b, s}, b<a, bs<a, выборочных значений порядков n=4t+1=4u2+1, u – целое. Пусть q=n–1=4u2, p=q+sqrt(q)=2(2u+1)u, для n=3 имеем 2a=b=s=1, для n>3, a=1, b=(2np)/p=1–(2u–1)/((2u+1)u), s=sqrt(nq–2sqrt(q))/p=sqrt((4u2+1)u2u)/((2u+1)u).

Также b=(2np)/p=(1+2tt1/2)/(2t+t1/2), s=sqrt(nq–2sqrt(q))/p=sqrt((4t+1)tt1/2)/(2t+t1/2).



The Fermat numbers have the form n = 22k+1 = 3, 5, 17, 257, 65537, 4294967297, .. [1]. Fermat made his famous mistake with this sequence suggesting they were all prime. Numbers of the form n = 22k+1, k is integer, and n=2k+1, k=1 or an even number, are similar in this sense. They belong to the 4t+1 family, or, more specifically to n=2k+1, k=1 or an even number, subset (the 4t+1 family has and other less wide subsets).

Fermat matrices are three level, F, {a=1, –b, s}, b<a, bs<a, of orders n=4t+1, will be called Fermat matrices. Let be q=n–1, p=q+sqrt(q). For n=3 we have special case 2a=b=s=1, for n>3,

a=1, b=(2np)/p=(1+2tt1/2)/(2t+t1/2), s=sqrt(nq–2sqrt(q))/p=sqrt((4t+1)tt1/2)/(2t+t1/2).


The structural invariants: every column (besides the border with "s") has v=(2qp)/2=(q–sqrt(q))/2 entries a=1. So F'F=FF'=ω(n)I, where the weight ω(n)=va2+(qv)b2+s2=(q–sqrt(q))/2+(q+sqrt(q))b2/2+s2. For n=5, v=(4–2)/2=1 entries a=1, for n=17, v=(16–4)/2=6 entries a=1, for n=65, v=(64–8)/2=28 entries a=1.

A Fermat matrix of order n has the following entries: a, –b, s (s is "side"). The letter sb is used for the side value. The level moduli of Cretan Matrices CM are parameterised by as a=1, b, c, d.. with a≥b≥c≥d≥...

The Fermat matrix core described is a regular double Propus A=–D, B=C. Kharaghani [2] conjectured that Bush-type regular Hadamard matrices of order 4m2 exist for all m, but these matrices, for m is odd, are hard to construct. Examples are known for m=3, 5, 9. The case m=3 is observed by Jennifer Seberry ([3] or SITE) leads to a regular Propus H36 and hence F37.

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 Fermat number, there is Fermat matrix. Look also: Mersenne matrices.

The family orders start with the first Fermat numbers and continues on. Fermat numbers may be prime but also non prime numbers. The search for them and pseudoprime [wiki] numbers is an ongoing special research theme for number theory.

Balonin's theorem says ([4, 8, 11], in Russian, below or PDF): Fermat matrices of orders n=2k+1, k=1 or even number, exist: there is a modified Sylvester algorithm to build fractal construction. Thus we give one circulant, two-circulant and Propus constructions below.

1. OEIS-sequence A000215
2. H. Kharaghani, On the twin designs with the Ionin-type parameters, Electronic J. Combin. 7 (2000), R1. MR1736717 (2000m:05027).
3. W. D. Wallis, Anne Penfold Street, and Jennifer Seberry Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices, Springer-Verlag, Berlin 1972.
The review of Mikhail Muzychuk and Qing Xiang (PDF) is also useful.

STARTING CIRCULANT AND TWO-CIRCULANT MATRICES



One- and two-circulant Fermat matrices F5, F17

THE DOUBLE-PROPUS A=–D, B=C FERMAT MATRICES



Regular Double Propus-type F17 and F[65]

THE PROPUS-TYPE B=C FERMAT MATRIX



Regular Propus H36 (constructed by library of Jennifer Seberry) and F37

PROPUS-HADAMARD MATRICES

THE BUSH-TYPE FERMAT MATRIX



The Bush-type matrix H36 (Zvonimir Janko) and F37



The Bush-type matrix H100 and F101


Maximal matrix size 100 first reported by Paley. The matrix above is a regular, symmetric Hadamard matrix, constructed using Theorem 5.15 (p. 344) of [3]. This theorem, due to Wallis and Whiteman, generalizes a construction of Goethals and Seidel. Case m=5, n=4m2 is observed also by Zvonimir Janko, Hadi Kharaghani, and V. D. Tonchev, 2001. See: MAX-DET 101 (non orthogonal).

THE NICK'S FRACTAL FERMAT MATRICES



Fermat matrices F3 and F5



Fermat matrices F17 and F[65] (we see greek F on diagonal!)



Fermat matrices F257 and F[1025]

FRACTAL FERMAT MATRICES (IN RUSSIAN)


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

F4k+1=
 a 
 sT 
 sT 
 sT 
 sT 
 s 
 Fk* 
 Fk 
  Fk 
 Fk 
 s 
 Fk 
 Fk* 
 Fk 
 Fk 
 s 
 Fk 
 Fk 
 Fk* 
 Fk 
 s 
 Fk 
 Fk 
 Fk 
 Fk* 



где Fk* – коммутативно-сопряженная матрица c взаимно-переставленными элементами уровней, при n=3 имеем b=s=2a (спецслучай), далее b=(2np)/p, субвектор каймы s содержат s=(nq–(4q)1/2)a/p, где p=q+q1/2, q=n–1 (порядок матрицы Адамара), стартовая матрица имеет вид

F5=
 a 
 s 
 s 
 s 
 s 
 s 
 a 
 –b 
 –b 
 –b 
 s 
 –b 
 a 
 –b 
 –b 
 s 
 –b 
 –b 
 a 
 –b 
 s 
 –b 
 –b 
 –b 
 a 


Описывает ветвь малоуровневых квази-ортогональных матриц нечетных порядков, содержащих значения чисел Ферма n = 22k+1.

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

Соответственно, эти числа дают лишь название направлению. Выделим из него матрицы порядков n = 2k+1, прореженных лишь требованием четности показателя k. Числа Ферма, начиная с 5, относятся к ним, образуя подмножество, и первые члены этого ряда с ними совпадают, различие начинается только на порядке n=1025.

THE QUASI-FERMAT FAMILY



Fermat matrix F3 and special F9



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