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


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

Конструкция Пэли не дает матрицы порядков: 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.

Теория чисел и матрицы Адамара тесны связаны, так как популярный алгоритм построения матриц Адамара опирается на теплицевы матрицы символов Лежандра. Как случай-исключение любопытен n=22-й порядок (и сходные, n=34-й и т.п.): когда значения n–1 вида не представимы суммой двух квадратов. Соответственно, для них не подыскать ни матриц Адамара (n кратно 4), ни их предикатов – матриц Белевича (см. двуциклические – two circulant matrices) [1], [2], [3]. Возникает закономерный вопрос, как эти матрицы обобщить? На этот вопрос дает ответ теория M-матриц: ортогональных по столбцам или строкам матриц Адамара-Мерсенна (Адамара-Эйлера, Адамара-Ферма).



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

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


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

  A  
   A  
  A  
  –A  


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

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

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

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

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


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

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

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


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

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


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


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



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


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


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


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

Матрица пакета MatLab


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


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





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



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


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



Umberto SCARPIS (Padova 1861 – Bologna 1921)



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

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



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.

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





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


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

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] блочно-циркулянтной матрицы Пэли

P=
A
C
B
B
A
C
C
B
A


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



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

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


Симметричная и кососимметричная 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



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


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


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

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

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

Rambler's Top100