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





МАТРИЦЫ: АДАМАРА | МЕРСЕННА | ЭЙЛЕРА | БЕЛЕВИЧА | ФЕРМА | ВЕБИНАР
AUTHORS | Andries E. Brouwer | Hadi Kharaghanis | Will Orrick | Коды Форни

МАРЕН МЕРСЕНН [2] | ТЕОРИЯ ЧИСЕЛ [1][2] | МАТРИЦЫ БЕЛЕВИЧА
ЧИСЛА ФЕРМА | ЗАГАДКИ ЧИСЕЛ ФЕРМА | ЭНЦИКЛОПЕДИЯ
Hadamard-type matrices 2014

BY Warwick's de Launey book



Warwick, go

BY Ionin's book













BY Brouwer's book











Хади, Янко, Тончеев



В статьях по комбинаторике транспозиции (парные перестановки элементов с индексами a, b) объединяют в циклы (a,b,c,...)(...) вместо (a,b)(b,c) и т.п.

ПРЕДЫСТОРИЯ


Платоновы тела Теорема Ферма-Эйлера Карацуба А.А. Доклад на конференции, посвященной 300-летию со дня рождения Л. Эйлера (Математический институт им. В. А. Стеклова, 17 мая 2007 г.) СИМВОЛЬНАЯ ДИНАМИКА

Внимание Эйлера к теории чисел привлек Гольдбах (письмо Гольдбаха к Эйлеру от 1 декабря 1729 г.), и первой работой была работа о теореме Ферма, касающаяся представимости простых чисел суммою двух квадратов целых чисел. Несмотря на разницу в возрасте в 17 лет, Гольдбах и Эйлер дружили, вели активную переписку, где ставились и решались проблемы теории чисел, вплоть до кончины Гольдбаха в 1764 г.



Таблица сумм двух квадратов


Сендеров В, Спивак А. Целые числа Гаусса [Don Zagir]

Совсем легко понять, почему 3, 7, 11 и прочие числа, дающие при делении на 4 остаток 3, непредставимы в виде a2+b2: квадрат чётного числа всегда делится на 4, квадрат нечётного числа всегда даёт остаток 1 при делении на 4, сумма двух квадратов при делении на 4 может давать остатки 0, 1 или 2, но никак не 3. Представимость простых чисел вида 4k+1 неочевидна (особенно если заметить, что простота существенна: число 21 хотя и имеет нужный остаток, но суммой двух квадратов не представляется), см. более тут.

Собрание ссылок на обзоры и прочие источники по матрицам Адамара, Белевича (C-матрицам) и сопредельным вопросам (старый блог).

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


МОНИТОРИНГ: Калькулятор | SBIBD
Дженнифер: N.J.A. Sloane new | Библиотека | Дженнифер (циркулянтные)
WIKI | Eric Tressler | П. Камерун | Стинсон | Холл, Комбинаторика, 1970 | Jacobus Hendricus van Lint, Richard Michael Wilson. A course in combinatorics | Муд | Симплексы и кубы [2]
МАТРИЦЫ АДАМАРА-ВИЛЬЯМСОНА: СТАТЬЯ 1965 | СТАТЬЯ 1981 | СТАТЬЯ 2002
КНИЖЕЧКА 2007 г. КАТИ ХОРАДАМ | РИСУНКИ АЛАНА ВЕНТИНКА | LAP-книга | Сачков В.Н. Введение в комбинаторные методы
САЙТ: ПЕТЕР КАМЕРУН | Combinatorial design theory ХАДИ, МАТРИЦА 428 | 1852
МОНИТОРИНГ: Калькулятор | Перечень (N. J. A. Sloane) new | Библиотека | Еще.
Матричная алхимия: мир фракталов | вакуумное условие


С-МАТРИЦЫ:


WIKI | from WOLFRAM | П. Камерун [2] | аннотация | блог | симметричные
МОНИТОРИНГ: Список C-матриц | С-матрицы | Коды
Порядки C26, C66 подозрительны на множественность решения, в таблице НЕТ C66?
Имеем 25=0x0+5x5=3x3+4x4, 65=1x1+8x8=4x4+7x7 и 65=5x13, а неразрешены 4k+3 = 3, 7, 11, ..
conference matrices do not exist for orders n = 22, 34, 58, 70, 78, 94 …
Known
n=4 6 8 10 12 14 16 18 (1 Matrix)
n=20 (2) 24 (9) 26 (4) 28 (41) 30 (6)
n=32 36 38 40 42 44 46 48 50 (1 Matrix)
n=52 (9)
n=54 56 (1 Matrix)
n=60 (2 Matrices)
n=62 64 [66?] 68 72 74 76 80 82 84 [86?] 88 90 92 96 98 100 (1 Matrix)

Порядки 46, 66, 86 для графов ПРОБЛЕМНЫЕ, Белевич 46 нашел Рудольф МАТОН, есть статья по обобщению Себерри и Вайтмана.

66 – минимальный порядок, для которого неизвестно, существует ли матрица Белевича. Прежде всего, она не может быть построена на базе пары циклических матриц (Handbook of Combinatorial Designs, Charles J. Colbourn, Jeffrey H. Dinitz).

WEIGHING MATRICES:



C. Koukouvinos found many Weighing matrices


W(n,m) WIKI | Jennifer 1976 (Tiryn seq) | классификация | Марчел Голей
R. Craigen, Weighing matrices and conference matrices | оптимальные | Kotsireas | W(58,53)

НЕПЛОХОЙ ЛИСТ ССЫЛОК

van Lint and Seidel (1966): van Lint, J.H., and Seidel, J.J. (1966), Equilateral point sets in elliptic geometry. Indagationes Mathematicae, vol. 28, pp. 335-348.

Вот еще одна (!): n–1 всегда будет суммой квадратов целых чисел, если n–2 является степенью простого числа.

Первые несколько возможных порядков симметричных конференс-матриц n = 2, 6, 10, 14, 18, (не 22, так как 21 не является суммой двух квадратов), 26, 30, (не 34, так как 33 не является суммой двух квадратов), 38, 42, 46 [? проблемна по Зейделю, для Пэли и графов], 50, 54, (не 58), 62 (последовательность A000952 в OEIS); для всех приведённых значений известно, что симметричные конференс-матрицы существуют. Для n = 66 вопрос остаётся открытым.

В виде суммы трех квадратов представимы все числа, кроме 4^k(8n+7) (k,n – целые неотрицательные, Карацуба А.А., стр. 22). В виде суммы четырех квадратов – количество делителей, не кратных 4. (В зависимости от того, считать ли перестановки слагаемых за разные представления, появляются множители).

ДОКЛАД КАМЕРОНА

MAX DET


Sloane Neil: Ehlich and Yang have given such matrices for
n = 2, 6, 10, 14, 18, 26, 30, 38, 42, 46, 50, 54, 62, 66. C matrices and two circulant Largest Determinant matrices, they both appear to exist for the same values of n Янг, [2] | 86 | R by Kouk

ОБЗОР [2] | INDIANA | УОРИК [2] [3] [4] | CRC | WIKI | W | Achim Flammenkamp


The largest possible determinants (Hadamard's maximum determinant problem) for n=1, 2, ... are

1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, ... (Sloane's A003432)... {1,0}-matrix
1, 2, 4, 16, 48, 160, ... (Sloane's A003433; Ehlich and Zeller 1962, Ehlich 1964).. {-1,1}-matrix

The numbers of distinct binary matrices having the largest possible determinant {1,0} are 1, 3, 3, 60, 3600, 529200, 75600, 195955200, 13716864000, ... (Sloane's A051752). The numbers of distinct {1,-1}-matrices having the largest possible determinant are 1, 4, 96, 384, 30720, ... (Sloane's A188895) Wolframs

Матрица R'R=(n–1)I+O Д. Раджавара (Бомбей), 2n–1=квадрат n=5, 13, 25, 41, 61 (!)
D. Raghavarao, Some optimum weighing designs, Ann. Math. Statist. 30 (1959) 295-303.

Норму матриц и свойства описал Гвидо Барба, см. также циркулянтные матрицы

Barba, Guido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Giorn. Mat. Battaglini 71: 70–86.

И был такой мужичок Баркер. Код Баркера, это попытка сгенерить Белый шум, но в очень ограниченном векторе из 1 и -1. Баркер наткнулся на ограничение 13 (Storer J.E., Turyn R.).

Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.

Barker R.H. Group synchronization of binary digital systems, in Jackson. W. (ed.) // Communication Theory. — Academic Press, London, 1953, pp. 273-287.

Storer J.E., Turyn R. Optimum finite code groups // roceedings IRE (Correspondence), 1958, V. 46, pp. 1649.

ОБЗОР



Для n = 2 (mod 4), Ehlich показал, что квадрат детерминанта ограничен значением 4(n–2)n–2(n–1)2, причем для порядков n<=38 они существуют определенно для p=n–1 увязанных с Hubert's symbols, проблемны n = 22, 34, 58, 70, 78, 94, 106, 130, 134, 142, 162, 166, 178, and 190 (как у Белевичей): M=[A B, -B' -A'], MM'=[P 0;0 P], P=diag(n,2), 2 за пределами диагонали.
H. Ehlich, "Determinantenabschätzungen für binäre Matrizen," Math. Z., v. 83, 1964, pp. 123-132

The most general upper bound on the maximal determinant, due to Barba, can only be achieved when the order is the sum of two consecutive squares. It is conjectured that the bound is always attained in such cases. Apart from these, only in orders 3, 7, 9, 11, 17 and 21 has the maximal value been established.

Блочная, порядок 7





Umberto SCARPIS (Padova 1861- Bologna 1921)




Умберто связал числа Мерсенна с матрицами Адамара, нашел H12, H56


Scarpis’s paper followed Hadamard’s by five years. Hadamard in turn had been preceded by Sylvester. Scarpis may have been motivated by an examination of the structure of Hadamard’s H12. As in Sylvester’s construction, Scarpis constructs a larger Hadamard matrix from a smaller Hadamard matrix.

Specifically, if an Hadamard matrix Hn can be found, where n–1 is prime, then an Hadamard matrix Hn(n–1) can be constructed. Paley later proved that for any n≡0 (mod 4) with n–1 a prime (or more generally, a prime power (простая степень, в связи с Сильвестром)) an Hadamard matrix Hn can indeed be found.

In Paley’s famous paper on the construction of Hadamard matrices using quadratic residues in finite fields, he remarks (see Lemma 5) that an 1892-by-1892 Hadamard matrix can be constructed by applying Scarpis’s construction to the 44-by-44 Hadamard matrix obtained using Paley’s first construction, and that size 1892 (which is 44×43) cannot be obtained using the methods of Sylvester and Paley alone.


Порядки "Paley construction" n=p+1, p+1 if p is prime and p+1 is a multiple of 4. This is then expanded to order (p+1)*2k using the Sylvester construction (программуля).

Порядки: Сильвестер 2k, Пэли pk+1 и 2pk+2, p – простое. По Пэли недостижим порядок 1892 (достижим по Скарпи через матрицу H44) Порядки n=2k: см. спр. у Вольфрама


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


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



1. Начальный квадратный блок размера n образован матрицей с единичными элементами a=1. От него вправо идут блоки, образованные дублированием n раз каждой из колонок матрицы Мерсенна, верхняя строчка которых замещается элементами a=1.



От начального блока вниз идут блоки, образованные дублированием n раз каждой из строк матрицы Мерсенна, с инверсией знака их элементов. Правее размещается колонка блоков из M.

2. Вправо от блока из первой строки идут матрицы M, –М, M, (и т.п....) так что



3. Вправо от блока из второй (i=2) строки идет матрица M. Далее блок –М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки i=2. Далее блок М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки 2(i-1)+1=3. Далее у матриц более большой размерности идет блок –М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки 3(i-1)+1=4, и т.п.



4. Вправо от блока из третьей (i=3) строки идет матрица M. Далее блок –М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки i=3. Далее блок М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки 1+{2(i-1)+1 mod n}=3. Далее у матриц более большой размерности идет блок –М с циклически сдвинутыми наверх строками так, чтобы он начинается со строки 1+{3(i-1)+1 mod n}, и т.п.



В итоге имеем






Will Orrick Blog | I.J. Schoenberg




Ray Edwin GILMAN (1887-1975)


Теорема Гилмана, 1930. Пусть n делится на 4, при n–1 простом, тогда матрица Адамара существует.


Теорема Пэли, 1933. Пусть n делится на 4, при n–1 или n/2–1 "une puissance de nombre premier" (a prime power), тогда матрица Адамара существует..





Вложение M7 в M3 НЕОРТОГОНАЛЬНО




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


n=12:

n=20:

1. Sylvester, J.J. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34: 1867, P. 461–475.
J. J. Sylvester, “Thoughts on Orthogonal Matrices, Simultaneous Sign-Successions, and Tessellated Pavements in Two or More Colours, with Applications to Newton’s Rule, Ornamental Tile-Work, and the Theory of Numbers.” Phil. Mag. 34, pp. 461-475, 1867.
2. Hadamard, J. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques 17: 1893, P. 240–246.


Порядки n=12, 20: (Shalom Eliahou, La conjecture de Hadamard (I) (II)) | слайды


Сайт?: Shalom Eliahou, La conjecture de Hadamard (I) — Images des Mathématiques, CNRS, 2012.

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

4. Paley, R.E.A.C. (1933). "On orthogonal matrices". Journal of Mathematics and Physics 12: 311–320.
Raymond E.A.C. Paley, "On Orthogonal Matrices." Journal of Mathematics and Physics, vol. 12, pp. 311-320, 1933.
5. J. Williamson, “Hadamard’s Determinant Theorem and the Sum of Four Squares.” Duke Math. J., vol. 11, pp. 65-81, 1944.
6. Belevitch, V. Theorem of 2n-terminal networks with application to conference telephony. Electr. Commun., vol. 26 1950. pp. 231–244.

7. L. D. Baumert, S. W. Golomb, M. Hall Jr., “Discovery of an Hadamard Matrix of Order 92.” Bull. Amer. Math. Soc., vol. 68, pp. 237-238, 1962.
L. D. Baumert; S. W. Golomb, M. Hall Jr (1962). "Discovery of an Hadamard matrix of order 92". Bull. Amer. Math. Soc. 68 (3): 237–238. doi:10.1090/S0002-9904-1962-10761-7.
Опубликованы у Эрика Тесслера
8. L. D. Baumert, "Hadamard Matrices of Orders 116 and 232." Bull. Amer. Math. Soc., vol. 72, pp. 237, 1966.
9. K. Sawade, A Hadamard matrix of order 268, Graphs Combin. 1 (1985), no. 2, 185–187.
10. H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs 13 (2005), 435–440.
11. F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 47, 56. ISBN 0-444-85193-3.
12. Neil Sloane, A library of Hadamard matrices old | new
13. WIKI

* * *

1. M. Hall, Jr., Note on the Mathieu group M12, Arch. Math. 13 (1962), 334–340.
2. J. Seberry and M. Yamada, Hadamard matrices, sequences and block designs, pp. 431–560 in Contemporary Design Theory: A Collection of Surveys (ed. J. H. Dinitz and D. R. Stinson), Wiley, New York, 1992.
3. Institute for Studies in Theoretical Physics and Mathematics, IPM, Iran;
http://math.ipm.ac.ir.


ОБА ВИДА МАТРИЦ: Себерри | обзор | новация


КОМПЛЕКСНЫЕ: Классификация | Каталог | Ли (комплексные C-матрицы)


ОРТОГОНАЛЬНОСТЬ: Мохан, ортогональность у матриц | ДКП 8x8 [техника]hl=ru | Симплексы и кубы [2]

Числа Мерсенна n=2^k–1: Числа Мерсенна | 2 | 3 | Числа Прота


A theorem of van Lint and Seidel (1966) asserts that, if a symmetric conference matrix of order n exists, then n-1 is the sum of two squares. Thus there is no such matrix of order 22 or 34. They exist for all other orders up to 42 which are congruent to 2 (mod 4), and a complete classification of these is known up to order 30.

Между тем, в самой книге указывается Иной автор D. Raghavarao (статьи 59, 60 годов), для случая n=2 mod 4 требование выглядит как ограничение на символ (n–1,–1)p=1 для всех простых p, Линту и Сейделю не принадлежит даже переформулировка условия, поскольку относительно нее они ссылаются на Белевича (1950) (!), который, в свою очередь, следует неким авторам. Кроме того, теоремой 5.2. отмечается, что это касается не столько матриц Белевича, сколько квазиортогональных рациональных матриц (к которым они принадлежат) Q'Q=mI, берется m – заведомо разложимое в сумму 4-х квадратов (ссылка на Лагранжа), составляется матрица Лагранжа (она же, Пропуса!) из элементов разложения m. Отмечается, что собственные значения C-матриц по модулю равны sqrt(n–1) !

Raghavarao, D. (1959). "Some optimum weighing designs". Annals of Mathematical Statistics 30 (2): 295–303.

---

Теорема. Необходимое условие существования квадратной рациональной матрицы Q порядка n=2 (mod 4), удовлетворяющей условию Q'Q=wI, где w – целое число, состоит в том, что w – сумма квадратов двух целых чисел.

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

Q=
A
B
C
D


По теореме Лагранжа любое целое число представимо суммой четырех квадратов w=w12+w22+w32+w42. Введем в рассмотрение матрицу W такую, что W'W=wI

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


причем det(A–W)<>0 (разность ортогональных матриц). Докажем, что для Q*=D–C(A–W)–1B (порядка n–4) справедливо то же самое равенство Q*'Q*=wI.

Обозначив множители в (–B'(A'–W')–1 I) Q'Q (–(A–W)–1B; I) как X, Y, Z, U и приняв во внимание две версии равенств

X(YZ)U=B'(A'–W')–1w(A–W)–1B+wI
(XY)(ZU)=B'(A'–W')–1W'W(A–W)–1B+Q*'Q*

приходим к выводу, что итерациями понижения порядка на 4 можно спуститься до матрицы второго порядка. Но тогда w представимо суммой двух целых чисел (а не четырех).

Отметим, что приложение теоремы к Q=[0 e'; e J] приводит к теореме Брюса-Ризера (Bruck-Ryser) о существовании J'J+O=(n–1)I, J – матрица Якобсталя (Bruck, R.H. and H.J. Ryser, The existance of certain finite projective planes, Canad. J. Math. 1, 88-93 (1949))

МАТРИЦЫ БЕЛЕВИЧА-СКАРПИ (M3)




Матрицы квадратичного и "кубического"? золотого сечения

первая дает сдвинутое на 1 "золотое сечение" (sqrt(5)+1)/2 в собственном значении, Арнольд.

Зейдель (Seidel) ввел матрицу Зейделя S, получаемую удалением каймы C-матрицы (зейделева матрица смежности некоторого графа). Это граф с n-1 вершиной, соответствующим строкам и столбцам матрицы S, две вершины являются смежными, если соответствующие элементы матрицы S отрицательны. Полученный граф является строго регулярным и относится к типу конференс-графов (названы так именно из-за конференс-матрицы).

Существование конференс-матриц порядка n, разрешаемое вышеуказнными ограничениями известно только для некоторых значений n. Например, если n = q + 1 где q является простой степенью сравнимой с 1 (mod 4), то существуют конференц-графы (q=5, 9, 13, 17, 25, 29) и графы Пэли, они дают примеры симметричных матриц порядка n: в качестве S берётся зейделева матрица смежности графа.

Матрица графа с q узлами k ребрами описывает связь узлов с ребрами (бинарно), кроме того, парой чисел характеризуется количество общих соседей у двух связанных и двух несвязанных узлов: первая матрица из таблицы приведена ниже (на диагонали 0): 25(узлов),12(ребер),5,6.




ТЕОРИЯ БАРКЕРА-ТЮРИНА


1. Barker R.H. Group synchronization of binary digital systems, in Jackson. W. (ed.)// Communication Theory. — Academic Press, London, 1953, pp.273-287.

2. Storer J.E., Turyn R. Optimum finite code groups// roceedings IRE (Correspondence), 1958, V. 46, pp.1649.

Теорема. Не cуществует последовательностей Баркера нечетной длины превосходящей 13. Бинарные коды Баркера существуют только для длин 13.

3. Turyn R.J., Storer J. On binary sequences// Proc. Amer. Math. Soc., 12, 1961, pp. 394–399.

Гипотеза. Не cуществует последовательностей Баркера четной длины превосходящей 13. Импульсная автокорреляционная функция имеет свойство С(τ)–C(τ–N)=0 для 0&<τlt;N.

4. Turyn R. On Barker codes of even length// Proceedings of the IEEE, September 1963, V. 51, № 9, pp. 1256.

Проверена гипотеза для четных длин от 14 до 121000.

5. Eliahou S., Kervaire M., Saffari, B. A new restriction on the lengths of Golay complementary sequences// J. Combin. Theory (A), 55, 1990, pp. 49–59.

6. Eliahou S., Kervaire M. Barker sequences and difference sets// L’Enseignement Mathematique, 1992, V.38, pp.345-382.

7. Schmidt B. Cyclotomic integers and finite geometry // J. Am. Math. Soc., Vol. 12, 1999, pp.929-952.

8. Schmidt B. Characters and cyclotomic fields in finite geometry // Lecture Notes in Mathematics, Vol. 1797, Springer, Berlin, 2002.

9. Leung K.H., Schmidt B. The field descent method// Designs, codes and cryptography, Vol. 26, 2005, pp.171-188.

10. Mossinghoff M.J. Wieferich pairs and Barker sequences // Designs, Codes and Cryptography, 53, No. 3, 2009, pp.149-163.

ССЫЛКА


ПОДБОРКА: ОБОБЩЕННЫЕ МАТРИЦЫ АДАМАРА


Балонин Н.А., Мироновский Л.А. Матрицы Адамара нечетного порядка // Информационно-управляющие системы. 2006, № 3. C. 46-50.


Useful Literature by MAX DET


G. Barba, Intorno al teorema di Hadamard sui determinanti a valore massimo, Giorn. Mat. Battaglini 71 (1933) 70-86.

L. D. Baumert, Hadamard matrices of orders 116 and 232, Bull. Amer. Math. Soc. 72 (1966) 237.

L. D. Baumert, S. W. Golomb, M. Hall Jr.,Discovery of an Hadamard matrix of order 92, Bull. Amer. Math. Soc. 68 (1962) 237-238.

Rambler's Top100