МАТРИЦЫ АДАМАРА


Адамар Жак – французский математик. Родился в Версале. В детстве увлекался языками. Победил на конкурсе знатоков греческого и латинского языков. Среднее образование получил в лицее Людовика Великого. Известны фундаментальные исследования Адамара в различных областях математики. В теории чисел Адамар доказал асимптотический закон распределения простых чисел (высказанный П. Л. Чебышевым). В теории дифференциальных уравнений занимался задачей О. Коши для гиперболических уравнений. В классическом анализе и теории функций известны неравенство Адамара, теорема Адамара о степенных рядах. Адамар сформулировал понятие корректности задачи математической физики. Интересны работы Адамара по вариационному исчислению (вариационная формула, теорема Адамара). Адамар написал учебник по геометрии, этюды по психологии математики.

Конструкция Пэли не дает матрицы порядков: 92, 116, 156, 172, 184, 188, 232, 236, 260, 268, 292, 324, 356, 372, 376, 404, 412, 428, 436, 452, 472, 476, 508, 520, 532, 536, 584, 596, 604, 612, 652, 668, 712, 716, 732, 756, 764, 772, 808, 836, 852, 856, 872, 876, 892, 904, 932, 940, 944, 952, 956, 964, 980, 988, 996... см. [1], [2], [3]. В 1985 г. К. Савад (Sawade) нашел матрицу размера 268 [4]. В 2004 г. Хади Харагани и Бехруз Тайфех-Резайе [5] нашли матрицу Адамара размера 428 (on line пример), и теперь минимальное значение n, для которого она неизвестна, составляет 668.



Пропус 92 и Пропус 116 (симметричные и трехблочные)


Неизвестны матрицы Адамара порядков 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964... Драгомир Джокович (Djoković, 2009) внес поправки в список неразрешенных порядков Colbourn and Dinitz (2007) и нашел 4 прежде неизвестные матрицы порядков 764, 23068, 28324, 32996 [6].

Максимальная сложность. Матрицы отмеченных известных и неизвестных пока еще трудных порядков 4(4t–1)=92, 116, ..., 668, 716, 982, ... сложнее бициклов, но не сложнее трехблочных конструкций Балонина-Себерри (Пропусов) [7, 8].

Порядки, для которых существует только одна матрица Адамара: 1, 2, 4, 8, 12. На 16-м порядке их 5, на 20-м их 3, на 24 их 60, на 28-м их 487. На 32, 36, и 40 счет идет на миллионы. Некоторые из них эквивалентны с точностью до транспонирования.

1. Leonard Baumert, S. W. Golomb and Marshall Hall, Discovery of an Hadamard Matrix of order 92. JR. Communicated by F. Bohnenblust, California Institute of Technology. Bull. Amer. Math. Soc. 68, 1962, pp. 237-238.
2. L. D. Baumert and M. Hall, Jr., A new construction for Hadamard matrices, Bull. Amer. Math. Sot. 71 (1965), 169-170 (PDF).
3. Baumert, L. D. Hadamard matrices of orders 116 and 232. Bull. Amer. Math. Soc. 72 (1966), no. 2 (PDF)
4. K. Sawade, A Hadamard matrix of order 268, Graphs Combin., 1985, 1, 185-187.
5. H. Kharaghani, B. Tayfeh-Rezaie (2005). A Hadamard matrix of order 428. Journal of Combinatorial Designs. 13 (6): 435–440. doi:10.1002/jcd.20043
6. Đoković, Dragomir Ž (2008). "Hadamard matrices of order 764 exist". Combinatorica. 28 (4): 487–489.
7. N. A. Balonin, Jennifer Seberry, Visualizing Hadamard matrices: the propus construction, preprint 15pp (submitted 6 Aug 2014) [arXiv:1512.01732v1]
8. Olivia Di Matteo, Dragomir Z. Djokovic, Ilias S. Kotsireas Symmetric Hadamard matrices of order 116 and 172 exist // Special matrices, 2015. № 3, pp. 227-234.

ОРТОГОНАЛЬНЫЕ БАЗИСЫ



КАТАЛОГ МАТРИЦ АДАМАРА | КОНФЕРЕНЦ-МАТРИЦЫ

Мы привыкли к проверке орфографии "на лету", сложно представить – было время, когда пишущая машинка не помогала исправлять текст. То же самое будет с вычислениями. В Интернет спрос найдут блоги с автоматической поддержкой online вычислений. Исследование обобщенных матриц Адамара: см. каталог, размещено в математической сети имени Леонарда Эйлера.

ИТЕРАЦИОННАЯ ФОРМУЛА СИЛЬВЕСТРА


Еще Д.Д. Сильвестр (1814-1897) – известный английский математик, основатель Американского математического журнала. Выделил среди матриц с ортогональными столбцами (строками) последовательность

  A  
   A  
  A  
  –A  


порождаемую рекурсией с начальным условием A=1, w=n – порядок матрицы.

Матрица Сильвестра обобщает матрицу спектрального преобразования Фурье на дискретный случай, когда амплитуда сигнала задается всего двумя уровнями. Ее столбцами являются предложенные в начале прошлого века функции Родемахера и Уолша – аналоги косинусных и синусно-косинусных базисов. Базис Уолша недостижим тривиальной амплитудной дискретизацией уровней гармонических функций.

СТАТЬИ О МАТРИЦАХ СЕМЕЙСТВА АДАМАРА


Балонин Н. А., Сергеев М. Б. Матрицы локального максимума детерминанта // Информационно-управляющие системы. 2014. № 1. С. 2–15.
Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 2016. № 1. С. 2–15.
Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара, произведения // Информационно-управляющие системы. 2016. № 5. С. 2–14.
Балонин Н. А., Сергеев М. Б. Расширение гипотезы Райзера на двуциклические структуры и разрешимость матриц Адамара орнаментом в виде бицикла с двойной каймой // Информационно-управляющие системы. 2017. № 1. С. 2–10.

БОЛЬШЕ СТАТЕЙ


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



Keywords: maximal determinant problem, Procrustes matrices, Hadamard matrices


Теорема Адамара состоит в том, что если у квадратной матрицы все элементы по модулю меньше или равны единице, то |det(A)|≤nn/2.

Верхняя граница достигается на матрицах Адамара порядков 1, 2 и n=0 (mod 4). Другими словами, с точки зрения геометрии объем n-мерного тела максимален, когда задающие его векторы взаимно перпендикулярны. Доказательство знаменитого неравенства Адамара опирается на свойство определителей, позволяющее в оценках переходить к произведению A'A, порождающему квадратичные формы от элементов, которые в данном случае просты.

Норма Адамара матрицы: h=mn1/2, m-норма равна максимуму абсолютных значений элементов ортогональной матрицы, получаемой из A нормированием столбцов.

Адамар опубликовал следующие отсутствующие в последовательности Сильвестра матрицы 12-го и 20-го порядков (24-й порядок порождается процедурой Сильвестра из 12-го, и первый отличный порядок-исключение: 28-й)


Гипотеза Адамара состоит в том, что такие матрицы существуют для порядков 1, 2 и n=4k, где k – целое число.

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

МАТРИЦА АДАМАРА H12


Матрица двенадцатого порядка, предложенная Адамаром в его статье, посвященной поиску максимального определителя.


Матрица двадцатого порядка, предложенная Адамаром в его статье, посвященной поиску максимального определителя.


ПЯТЬ НЕЭКВИВАЛЕНТНЫХ МАТРИЦ 16-го ПОРЯДКА





ТРИ НЕЭКВИВАЛЕНТНЫЕ МАТРИЦЫ



СИММЕТРИЧНЫЕ ФОРМЫ


Матрицы пакета Internet-MatLab

МАТРИЦЫ АДАМАРА-СКАРПИ



Umberto SCARPIS (Padova 1861 – Bologna 1921)



Падуя (Padova) – недалеко от Венеции (на веточке к морю, от Милана), место расположения старейшего Университета Европы (1222), где работали Коперник, Галилей (и Скарпи). Ныне (via) есть улочка Умберто Скарпи.





Матрицы Адамара-Скарпи, посчитанные по матрицам Мерсенна, модифицированный алгоритм в реализации Юры Балонина: матрица Мерсенна вставляется в самою себя, с позиционным поворотом Скарпи, расширяемые элементы определяют знак каймы (все просто).

БОЛЬШЕ ПРО МЕТОД СКАРПИ

В оригинале кайма отделена от матриц Мерсенна, что усложняет алгоритм



HADAMARD-SCARPIS MATRICES H380, H552


Оригинальный алгоритм

1. Составляется блочно-составная матрица из (n+1)x(n+1) матриц Мерсенна Mn с соблюдением знаковой политики (черезстолбцовые минусы у матриц и блоков).
2. Прозводится "обеднение" окаймляющих блоков замещением их одним столбцом или одной строкой, соответственно их положению: стартовый блок и первая строка "выбеливаются" в 1.
3. Производится поворот, как в номерном замке (или барабане кольта), строк блочных матриц, соответственно произведению индексов их размещения.

Литература

1. Scarpis U. Primi Elementi Della Teoria Dei Numeri, 1897 (Hardback)

2. Scarpis U. Sui determinanti di valore massimo, Rendiconti della R. Istituto Lombardo di Scienze e Lettere 31 (1898) 1441–1446.

МАТРИЧНОЕ КВАДРАТИЧНОЕ УРАВНЕНИЕ


Матричное квадратичное уравнение

A'A = wI,


выделяет класс матриц с ортогональными вектор-столбцами, здесь I – единичная матрица, w – весовой коэффициент. Среди целочисленных решений этого уравнения выделяют матрицы Адамара и Белевича (C-матрицы).

МАТРИЦЫ С КОМПЛЕКСНЫМИ КОЭФФИЦИЕНТАМИ


Комплексная матрица Адамара

aik=e2пj(i–1)(k–1)/n


отличается от матрицы Фурье масштабным коэффициентом sqrt(n). Матрицы, определенные над полем комплексных чисел с единичным модулем, относят к категории обобщенных адамаровых матриц, однако свобода выбора фазы несоизмеримо больше свободы выбора знака при модуле: особых проблем этот случай не вызывает.

Рассмотрим нормализованную структуру комплексной матрицы

A=
1
1
1
1
a
b
1
c
d


она ортогональна, если b=c=–1–a, d=a, a – кубический корень из 1 для a2+a+1=0.

Выделяют комплексные адамаровы матрицы битсоновского типа с произвольным показателем корня, с элементами ±1, ±j (корень четвертой степени из 1), и случаи с показателем корня равным порядку матрицы n.

МАТРИЦЫ АДАМАРА И БЕЛЕВИЧА


Пропуски между порядками 1, 2, 4, 8, 16, 32, ... сильвестровой последовательности матриц существенно возрастают. В начале прошлого века Ж. Адамар построил аналогичные матрицы 12-го (а значит, и 24) и 20-го порядков и высказал гипотезу, что решения с элементами ±1 существуют для всех степеней, кратных 4. С тех пор такие матрицы называют адамаровыми.

Определение 1. Адамаровой матрицей А называется nxn матрица с элементами ±1, обладающая свойством

A'A=nI.


Следующий шаг сделал В. Белевич – русский математик, работавший в Америке, выходец из среды петербургских эмигрантов, покинувших Россию в годы революции. Он расширил множество рассматриваемых матриц до форм с нулевой диагональю и элементами ±1 вне ее.

Определение 2. Матрицей Белевича C называется nxn матрица с нулевой диагональю и остальными элементами ±1, обладающая свойством

С'С=(n–1)I.


Матрицы Белевича (конференц-матрицы или C-матрицы) связаны с теоремой теории чисел Эйлера: необходимое условие их существования заключается в том, чтобы n–1 было разложимо на сумму двух квадратов. Они заполняют четные пустующие порядки 6, 10, 14, 18, ... сильвестровой последовательности матриц, исключениями являются, например, 22, 34, 58.

Условие ортогональности – это квадратическое уравнение, дающее на случай первого порядка

a2=1,


корни +1, –1. Таковы и матрица Адамара

A'A=nI,


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

ТЕОРЕМА СУЩЕСТВОВАНИЯ


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

Q=
A
B
C
D


с пересчетом Q=D–C(A–W)–1B параметров матрицы D, имеющим цель сохранить правую часть Q'Q=wI при итерационном понижения порядка n–4 вплоть до n=2.

Размерность 4 взята из теоремы Лагранжа о гарантированном разложении натурального числа на сумму четырех квадратов w=n–1=w12+w22+w32+w42, в которой используется конструкция Вильямсона с тем же весом W'W=wI вида

W=
 w1 
 w2 
 w3 
 w4 
 –w2 
 w1 
 –w4 
 w3 
 –w3 
 w4 
 w1 
 –w2 
 –w4 
 –w3 
 w2 
 w1 



Элементарное следствие алгоритма понижения порядка состоит в том, w=n–1, n=2 (mod 4) – представимо парой квадратов рациональных, в общем, а значит, и парой целых чисел, т.к. объект разложения – целое число. Это обстоятельство отмечал еще Белевич, указав на то, что в ряду исследуемых им матриц нет матриц с n=22, 34 и т.п..

МАТРИЦА ЯКОБСТАЛЯ


В теории построения матриц Адамара и Белевича используются теплицевы или блочно-теплицевы матрицы Якобсталя и Пэли, последние появляются вместе со сложными порядками. Кроме того, матрицы Адамара и Белевича связаны между собой преобразованием, сходным с сильвестровым.

Для решения основной проблемы выделяют вспомогательное уравнение Якобсталя

J'J = (n – 1)I − E,



где J – искомая целочисленная матрица, I,E – единичная матрица и матрица, состоящая полностью из 1 (тех же порядков, что и J).

Это уравнение ввел немецкий математик Эрнст Якобсталь, ученик Фробениуса и Шура, работавший в начале прошлого века над диссертацией по квадратичным вычетам. Оно напоминает условие ортогональности, несколько сложнее его, но зато решение устроено исключительно просто: это теплицева матрица символов Лагранжа

Jij = ((i–j)/n), i<>j,


удовлетворяющая условию JE = EJ = 0, с элементами ±1 вне нулевой диагонали.

Матрица Якобсталя J заведомо существует, если n – простое число. Она циклическая и симметрическая или кососимметрическая – в зависимости от того, принадлежит ли разность –1 квадратичным вычетам, т.е. n=1 (mod 4) или n=3 (mod 4), соответственно.

МАТРИЦА ПЭЛИ


Первый встреченный сложный порядок n=9 (не является простым числом) удовлетворяет условию основной теоремы Эйлера о разложимости на сумму двух квадратов – содержит 3 в четной степени 2. В тридцатых годах прошлого века Раймонд Пэли рассмотрел квадратичные вычеты последовательности девяти чисел

0, 1, −1, a, a+1, a−1, −a, −a+1, −a−1


определенной над иррациональным корнем a неприводимого к простым множителям многочлена: x2 + x − 1 = 0. Ей отвечают символы Лежандра, разделенные на три составляющие

a=[0, 1, 1], b=[–1, –1, 1], c=[–1, 1, –1],


и соответствующие им циклические блоки A, B, C, удовлетворяющие, как видно, условию симметрии a[2]=a[1], c[0]=b[0], c[1]=b[2], c[2]=b[1] блочно-циклической матрицы Пэли

J=
A
C
B
B
A
C
C
B
A


которая является решением матричного уравнения Якобсталя.



Условие, при котором получается симметричная матрица, зажимает C=B' и верхнюю половину элементов A. Задачу ее построения можно решить также перебором, существует, например, решение при a=[0 -1 1], b=[1 -1 1].

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


Матрицы Якобсталя порядка n=4k–3, n – простое число, в теории графов интерпретируются как матрицы смежности Зейделя: симметричная матрица с нулями на диагонали и прочими элементами {1, –1}, описывающими отсутствие или наличие связи между узлами с номерами, отвечающими индексам строки и столбца.


Понятие выделено Зейделем и Линтом в 1966 году в связи с изучением типов симметрий собственных значений этих матриц. Строго регулярные графы отличаются, помимо порядка, еще парой характеристик: количеством общих соседей двух смежных и двух несмежных узлов. Для порядков, не равных простым числам, графам отвечают блочно-составные матрицы Якобсталя, они же – нормализованные матрицы Белевича без каймы в виде первых строки и столбца. Проблемные в теории графов порядки, например, 45, освоены только в 1978 году, после публикаций блочно-составных матриц Рудольфа Матона.

ЗЕЙДЕЛЬ И ЛИНТ 1966


АЛГОРИТМ НАХОЖДЕНИЯ МАТРИЦ БЕЛЕВИЧА


Симметричная и кососимметричная C-матрицы (матрицы Белевича) строятся дополнением матриц Якобсталя

C=
0
 e' 
e
J
,
C=
0
 e' 
 –e 
J
,



согласно двум основным случаям: n–1=1 (mod 4) или n–1=3 (mod 4), здесь e – вектор из единиц. Компенсационные добавки устраняют добавочный член с матрицей E в вспомогательном уравнении. Симметричная блочно-циклическая матрица Пэли используется в первой формуле J=P.

АЛГОРИТМ НАХОЖДЕНИЯ МАТРИЦ АДАМАРА


Матрицы Адамара строятся на основе кососимметрических C-матриц устранением нулевой диагонали

A=I+С,


именно таковы первые два случая-исключения порядков 12 и 20, рассмотренные еще Адамаром.

Симметричный вариант опирается на преобразование Сильвестра с аналогичными компенсационными единичными матрицами–добавками

A=
  I+С  
    I–С  
  I–C  
  –I–C  


это, в частности, случай более высокого порядка n=28, не рассмотренный Адамаром.

Гипотеза Адамара не доказана до сих пор, эффективность любого алгоритма зависит от порядка. Известны примеры построения некоторых видов стартовых матриц сильвестровой последовательности.

ЦИКЛИЧЕСКАЯ МАТРИЦА


Адамарова матрица

A=
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 


циклическая, это характерно для n=1, n=4 (Circulant Hadamard Matrices R. Stanley), порядки 2 и кратные 8 исключены.

МАТРИЦА ВИЛЬЯМСОНА


Вильямсон ввел в рассмотрение кососимметрическую ортогональную матрицу

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A


блочные (как у матрицы Пэли) элементы которой представлены циклическими попарно-коммутативными симметрическими подматрицами нечетного порядка m с элементами ±1, удовлетворяющими условию

A2+B2+C2+D2=4mI.


Поиск элементов таких блоков обеспечивается переборным алгоритмом, что дает еще один тип адамаровых матриц, замещающих пропуски в последовательности Сильвестра. Этим способом строится матрица 92 порядка: первая матрица порядка n<100, недостижимая в рамках конструкции Пэли. В простейшем случае A=1, B=1, C=1, D=1 дает адамарову матрицу четвертого порядка.

Алан Вентинк рассмотрел в так называемом "чайном-пакетике" для матриц Адамара 16-го порядка цветок.


ПОСЛЕДОВАТЕЛЬНОСТЬ СИЛЬВЕСТРА






МАТРИЦЫ 16-го ПОРЯДКА





МАТРИЦЫ 20-го ПОРЯДКА




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


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


Матрица Серпинского продуцирует матрицу Адамара сильвестровой последовательности возведением –1 в степень, равную значениям элементов этой матрицы:

H=–1S



Если выбелить ненулевые элементы матрицы Серпинского, получатся узнаваемые контуры треугольника Серпинского



ЦИКЛИЧЕСКИЕ И БИЦИКЛИЧЕСКИЕ МАТРИЦЫ АДАМАРА



Пример циклической матрицы Адамара

A=
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 


это характерно для n=1, n=4 (Circulant Hadamard Matrices R. Stanley), порядки 2 и кратные 8 исключены. Предположение о не существовании иных решений есть в учебнике Ризера (Ryser's conjecture) [1].

There is Ryser's conjecture (see [1], page 134): is the inexistence of matrices of order n > 4 that are circulant and Hadamard matrices simultaneously.

1. H. J. Ryser, Combinatorial mathematics. The Carus Mathematical Monographs, No. 14, Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York 1963.



Two two-circulant Ryser's matrices H8

TWO BASE CONFIGURATIONS OF WEIGHING MATRIX



Weighing matrix W12 (2 cells) and asymmetrical H24



Weighing matrix W12 (4 cells) and symmetrical H12

THE SYLVESTER ORDER



Two two-circulant matrices H16

THE WEIGHING MATRIX AGAIN



Weighing matrix W20 and asymmetrical H40



Weighing matrix W20 (4 cells) and symmetrical H20



Two-circulant asymmetrical Hadamard matrices H20 !

THE WEIGHING FOUR CIRCULANT MATRIX



Multi-circulant matrices W24 and H24



Multi-circulant matrices W24 and H24



Two-circulant multi-level matrix M24

THE WEIGHING MATRIX AGAIN



Weighing matrix W28 and asymmetrical H56



Weighing matrix W28 (4 cells) and symmetrical H28

THE SYLVESTER ORDER



Two-circulant matrices H32

THE WEIGHING MATRIX AGAIN



Weighing matrix W36 and asymmetrical H72

THE ASYMMETRICAL HADAMARD H40



Two-circulant asymmetrical Hadamard matrix H40 !

THE WEIGHING MATRIX AGAIN



Weighing matrix W52 and asymmetrical H104

СТРАНИЦА ПОИСКА БИЦИКЛИЧЕСКИХ МАТРИЦ (БАЛОНИН-СЕБЕРРИ)


МАТРИЦА ВИЛЬЯМСОНА


Вильямсон расширил практику блочного представления матриц Адамара, характерную для конструкций Пэли, увеличив число блоков по горизонтали и по вертикали еще вдвое, и назвав это массивом

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A


блоки которой (собственно, матрицы Вильямсона) представлены попарно-коммутативными симметрическими подматрицами порядка w с элементами ±1, удовлетворяющими условию ортогональности матрицы в целом

A2+B2+C2+D2=4wI.


ТАБЛИЦА 2007: WILLAMSON MATRICES UP TO ORDER 59


Доказано существование матриц порядков 4w для всех w<60 (2007 г.), w=9s и w=(q+1)/2, q – простое целое из чисел, равных –l (mod 4).

Если n/2–1 = 1 mod 4, то существует решение: A и B отличаются только основной диагональю и C=D. В простейшем случае A=1, B=1, C=1, D=1 дает адамарову матрицу четвертого порядка.

Поиск элементов таких блоков обеспечивается переборным алгоритмом, который облегчается, если предположить, что они циклические. Таким способом строится матрица 92 порядка (Baumert, Golomb и Hall, 1962): матрица первой сотни n<100, недостижимая в рамках конструкции Пэли.

1961 ГОД




The pleasure to find new matrix: Hadamard 92 moment 1961


From left to right, Solomon Golomb (Assistant Chief of the Communications Systems Research Section), Leonard Baumert (a postdoc student at Caltech), and Marshall Hall, Jr. (Caltech mathematics professor) hold a framed representation of the matrix.

Опорные векторы матриц 23-го порядка следующие (представление единственное):

A1 = (1, 1, -1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, -1, -1, -1, 1)
B1 = (1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, -1)
C1 = (1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1)
D1 = (1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1)


Позднее Baumert нашел этим методом матрицу 116-го порядка.

Неизвестны матрицы Адамара порядков 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964...

КОСОСИММЕТРИЧЕСКИЕ МАТРИЦЫ АДАМАРА


Definition. The Hadamard matrix H is nxn ±1-matrix H'H=nI. The skew-Hadamard matrix H can be calculated by Williamson-type A, B, C, D matrices, AAT+BBT+CCT+DDT=4mI, A is skew-circulant and B, C, D are back-circulant matrices, symmetry accordingly second diagonal:

H=
A
B
C
D
 –B 
A
D
 –C 
 –C 
 –D 
A
B
 –D 
C
 –B 
A


ИЛЛЮСТРАЦИИ БАЛОНИНА-СЕБЕРРИ


1971 ГОД


There is a skew-Hadamard matrix of order 92 (Jennifer Seberry, 1971). Previously the smallest order for which a skew-Hadamard matrix was not known was 92. The existence of any Hadamard matrix of order 92 was unknown until 1962 (see photo below).

Jennifer Seberry Wallis, A skew-Hadamard matrix of order 92, Bulletin of the Australian Mathematical Society, 5, (1971), 203-204.

Следующая программа для поиска кососимметрических матриц Адамара на базе четырех циклических матриц использует идею сочетания циклической кососимметрической матрицы A, с тремя ациклическими симметричными формами B, C, D.



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

















БИЦИКЛИЧЕСКИЕ МАТРИЦЫ АДАМАРА FGS-CONSTRUCTION


МАТРИЦЫ ЭЙЛЕРА


Бициклические матрицы Адамара с двойной каймой связаны с квазиортогональной матрицей Эйлера

E=
A
B
 BT 
 –AT 


Уравнение для округленной матрицы Эйлера со значениями элементов {1, –1}, несущее информацию только об ее структуре

E'E = (n+2)I – 2X,



где X – блочно-диагональная матрица с блоками единичных элементов порядков n/2. Первое преобразование ее к форме матрицы Адамара заключается в добавлении каймы и парной-перестановки элементов {b,–a} на {a,–b} нижнего правого циклического блока, затем добавляется вторая кайма и элементы округляются до {1,–1}.

ИНТЕРПРЕТАЦИЯ СТРОК В ВИДЕ БАЗИСОВ УОЛША-РАДЕМАХЕРА


Систему ортогональных меандров предложил Ганс Радемахер в 1822 году: Rk(t)=sign(sin(2kπt)), где t – безразмерное время. Ниже дан график до округления.



Система функций Радемахера ортонормирована на интервале [0,1], но неполна (синусы без косинусов). Дополнить ее с помощью косинусов тех же частот получается порядка до восьмого, а в общем условие ортогональности противоречит такой периодичности выборки. В 1923 году американский ученый Уолш получил полную систему ортонормированных функций, дополняя систему функций Радемахера: W0=R0, W1=R1, W2=R2, W3=R1R2, и т.п. На практике их находят, систематизируя строки матриц Адамара последовательности Сильвестра: ниже матрица до и после систематизации.


ФУНКЦИИ РАДЕМАХЕРА | ВИКИ




КЛАСС НЕОРТОГОНАЛЬНЫХ МАТРИЦ


Оптимальные по значению детерминанта матрицы ищутся на классе {1,–1}-матриц, расширение {0,1,–1}-матрицами не добавляет к нему ничего нового, в смысле возможности улучшения значения детерминанта, оно эффективно только на подклассе ортогональных матриц. Ограничение на значения детерминантов для матриц порядков 1, 2, ... сверху, использующие оценки Адамара (адамарова граница), равны 1, 2, 3⋅31/2, 16, 25⋅51/2, 216, ..., квадраты равны 1, 4, 27, 256, 3125, ...

Для нечетных порядков оценку верхней границы уточнил Гвидо Барба |det(A)|2≤(n–1)n–1(2n–1), максимум достигается на порядках, для которых 2n–1 – полный квадрат (необходимое условие, иначе нарушается целочисленность). Эквивалентное условие (гипотеза): n=k2+(k+1)2 [*].

Оптимальные матрицы удовлетворяют условию A'A=(n–1)I+J, J – матрица из единиц, они существуют только на порядках n=1 (mod 4). Пару таких матриц (15 и 25 порядков) нашел и опубликовал Raghavarao. Матрицы Рагхаварао порядков 5, 13, 25, [41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п.] сходны с адамаровыми в том, что достигают по значению детерминанта отмеченной границы.



Циклическая матрица Рагхаварао R13


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

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

На порядках n=3 (mod 4) работает то же ограничение, что и для n=1 (mod 4), оно касается матриц нечетных порядков в целом, но условие 2n–1 – полный квадрат недостижимо тут никогда, поэтому Ehlich отнес случай к труднейшим, для n≥63 им была получена точная оценка для матриц, кратных 7, максимум достигается на матрицах, порождающих блочно диагональную форму A'A, диагональный блок (n–3)I+4J, внедиагональный –J. Отметим, что округленные до целых матрицы Мерсенна дают A'A=(n+1)I–J, вторым корнем этого уравнения идет "черный Мерсенн".

На порядках n=2 (mod 4) Ehlich и Wojtas: |det(A)|2≤4(n–2)n–2(n–1)2, максимум достигается на матрицах, порождающих блочно диагональную форму A'A, блок (n–2)I+2J, 2(n–1) – сумма двух квадратов. Округленные матрицы Эйлера отличаются знаками блоков (n+2)I–2J. Иными словами, проблемны все те же порядки 22, 34, 58 и т.п., что и у матриц Белевича.

Первый проблемный порядок, для которого неясно оптимальное решение – порядок 22, существует оценка определителя 409.6×1012 (численное решение, в A'A присутствует ±2), у ортогональных матриц проблемы начинаются раньше (на 13-м порядке, 4 123 300 против максимально возможного 14 929 920).



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


Если существуют циклические матрицы A, B нечетного порядка 1<n<31, исключая порядки 11, 17 и 29, с элементами {1,–1}, удовлетворяющие критерию

A2+B2=2(n–1)I+2J,


где J – матрица единиц, то существует матрица максимального детерминанта X=X(2n)

X=
A
B
 –BT 
 AT 


где R – обратная единичная матрица (флип).

НЕРАВЕНСТВА ДЛЯ МАТРИЦ МАКСИМАЛЬНОГО ДЕТЕРМИНАНТА | ОБЗОР


КЛАСС ОРТОГОНАЛЬНЫХ МАТРИЦ



Задача о максимальном определителе на классе квазиортогональных матриц имеет решение на матрицах Прокруста, к которым принадлежат, в частности, матрицы Адамара на порядках 1, 2 и далее кратных 4, и матрицы Белевича на порядках n=4k+2 (если таковые существуют). На нечетных значениях порядка (и при четных порядках, не кратных четырем) ортогональность – помеха оптимизировать этот параметр.

В теории оптимизации локальным оптимумам придается значение не меньшее, чем абсолютным экстремумам, в этом смысле можно говорить отдельно об мерсенновских определителях и прочих не менее важных ветвях задачи Прокруста: определителях субоптимальных матриц Эйлера, Ферма и т.п. Оптимальные матрицы содержат в себе столь заметные мерсенновские блоки, что можно говорить о тождестве структурных инвариантов матриц Адамара, Белевича, Мерсенна и т.п. Матрицы Мерсенна, в некотором смысле, – альтернатива матрицам Адамара на нечетных значениях порядка, и что для обоих матриц первичнее: такой же неразрешимый вопрос, как вопрос о курице и яйце. Общего у них – порядочно много, включая гипотезу о существовании, и все же матрицы Мерсенна несут на себе печать нечетных чисел. Пример с "хаотическим" аттрактором: ввиду малости ямки локального оптимума итерации упираются в порог адамаровой нормы уровневых матриц h=m13131/2.



WIKI | ОБЗОР [2] | ПРОКРУСТ | ПРОКРУСТОВ АНАЛИЗ | ТАБЛИЦА | [1] [2]


ИНТЕРНЕТ-ЛИТЕРАТУРА


Матрицы Адамара, каталог: обзор линков в Интернет. См. обзоры по комплексным матрицам (лежит, кстати, на сайте с ключевым корнем chaos) и матрицам Фурье, [см. также Тыртышников Е. Е.].

По теории чисел существуют прекрасно написанные учебники. В шестидесятых годах на русском языке опубликована книга президента Лондонского математического общества Гарольда Дэвенпорта. Примерно тогда же изданы книги Вацлава Серпинского и Александра Осиповича Гельфонда. Много любопытного у известного математика Роджера Пенроуза. Полезно заглянуть в википедию, и узнать, кто такой Морделл Луис Джоел. Теореме Ферма посвящен бестселлер Саймона Сингха. 2004 год, Джон Стилвел использует LaTeX, но разве этого достаточно, в наше время? Теории чисел посвящена книга Сергея Викторовича Сизого.

МАТРИЦЫ | СТАТЬЯ ПО ФРАКТАЛАМ | ТРЕУГОЛЬНИК ПАСКАЛЯ


РАСЧЕТ МАТРИЦ АДАМАРА ИСПОЛНЯЕМЫМИ АЛГОРИТМАМИ

КАТАЛОГ ОБОБЩЕННЫХ МАТРИЦ АДАМАРА | МАТРИЦЫ

Rambler's Top100