GENERALIZED SCARPIS AND PRODUCT MATRICES



Scarpis, generalized Scarpis and product matrices

© Nickolay A. Balonin, 1.05.2015


Предыстория произведения Скарпи такова. Итальянский математик Умберто Скарпи сто лет назад вставил матрицу Адамара размера 4 в ее блок, без каймы, размера 3×3. Тогда еще не было представлений о нормальной форме и блок не назывался core. По моему, он даже отсекал не первую строку. Метод работал, но требовал смещения этого самого ядра пропорционально отстоянию замещаемого элемента от левого верхнего угла шпигуемой матрицы. Проверил на вставке матрицы Адамара порядка 8 в основу 7×7, работает. Опубликовал статью 1898 г., появились метод Скарпи и зомбирование сознания, что смещения нужны.



Разновидности метода Скарпи: со смещением и при смене порядка вставки


То, что смещений нет при реверсной вставке Скарпи не заметил или не посчитал нужны считать за метод (селекция матриц по видам их симметрии появилась позднее). Порядок второй матрицы повышен, чтобы сделать различие особенно заметным. У матрицы порядка 12 происходит смещение основы core части блоков. Реверсная вставка, не зависит от вида порядка, прост ли он, степень ли или составной, все равно. Что свойственно кронекерову произведению. Проскочим сочетание 27 на 28, не заметив проблем, получим матрицу 756.

У ортогональных матриц кайма и диагональ – разменная монета. Отрезали кайму, диагональ упала в 0, добавили кайму, диагональ ушла в 1. Возьмем обычное произведение Кронекера и отрежем кайму размером в умножаемый блок. Матрица потеряет ортогональность. Начнем менять на диагонали все отрицательные элементы –1, дошли до 0, поднялись выше, дошли до 1. Что получилось? Готово дело. На диагонали стоят матрицы из одних 1, ведь 1 мы не трогали. Вот и получилось "произведение Скарпи". Это случай, когда мерсеннов блок ушел в –b=1, а у блоков вне диагонали –b ушло в –1.



Снежинка и матрица Мерсенна М11


Смещения не всегда нужны. Можно назвать обобщение метода Скарпи методом снежинки. Смещение есть и его, как бы, нет. Ведь если поворот совпадает с симметрией, снежинки, то после поворота она будет такой же. В методе Скарпи надо антисимметрировать матрицу (нужна кососимметрия) и поменять порядок вставки. Вставлять блоки C=core(H) размеров 3×3, 7×7 в матрицы Адамара H размеров 4, 8, т. п. На диагональ J, как обычно. Смещение вставляемых блоков исчезает.

Терпима и дистанция 3<4 (дистанция 4, это произведение Кронекера). Супер-Скарпи n=(q+1)(q+4), тема разрешимости дистанций раскрыта в витражах.



Матрица Адамара H88 вложением М11 в H8


Версия

Произведение Скарпи, на самом деле, это H=(HIC+I×J, C=core(H), I адаптируется к размеру блока, – все то же кронекерово произведение, с поправкой цепочки диагональных блоков. Узнать его нелегко потому, что оно более капризное, требует подготовки сомножителей. Компенсация влияния каймы изменением диагонали – общее место теории этих матриц. Это означает, что матрицы кратных порядков не вполне свободны друг от друга, и это естественно. Роль кронекерова произведения, как самого простого, не требующего даже приведения матрицы к нормальной форме, понял еще Пэли. К сожалению, не все порядки составные, простые числа независимы. Перечень трудных порядков 4t по t: 167, 179, 223, (251, найден в 2013-м), 283, 311, 347, 359, 419, 443, 479, 487, 491. Степенные функции в полях Галуа дают опорные матрицы некоторых связанных с простыми числами или степенями простых чисел порядков. Роль матричных умножений (вставок plug into, витражей) – расширить состав таких матриц комбинированием безотносительно к простоте связанного с порядком числа. Это касается кронекерова произведения, и прочих. Даже, когда на первый взгляд, произведение Скарпи зависит от простоты порядка квадрируемой матрицы, речь идет об его частной модификации, и при ином устройстве вычислений алгоритм индифферентен к порядку.

Есть фундаментальные постулаты о симметрии объектов. Типа, все снежинки симметричны. Таковы и матрицы Мерсенна, они сводимы к кососимметричной форме. Метод Скарпи индифферентен к порядку, он увеличивает все матрицы Мерсенна (generalized generalized Scarpis method). Обратим внимание, алгоритм применим к порядку 15, а это даже не степень, а 3×5 (пара), и к порядку 39, хотя 39=3*13! Возьмем матрицу Адамара 36 или 52, выделим Мерсенна 35 или 51, и .. работает. Имеем цепочку утверждений о роли симметрии в жизни этих матриц.

Гипотеза 1: кососимметричные матрицы Мерсенна существуют для всех q=4t–1.
Гипотеза 2: произведение Скарпи дает все матрицы Мерсенна n=q(q+1)–1.
Гипотеза 3: произведение Скарпи дает все матрицы Адамара n=q(q+1).

Роль матриц порядка r=1 (mod 4) выглядит несколько таинственной только если не знать особенностей цепочек квазиортогональных матриц: это не более чем полуфабрикаты для получения матриц Эйлера удвоенного порядков 2r, а за ними матриц Мерсенна порядков 1+2r: r=5 дает M11; блоки размера 5 прекрасно различимы на рисунке выше. Обобщение метода Скарпи (generalized Scarpis method) – это общий метод, как и произведение Кронекера, ориентированное на "квадрирование" матриц Мерсенна. Квадрирование матриц Зейделя не имеет смысла, поскольку матрица Зейделя порядка 5 структурно связана с матрицей Мерсенна порядка 11, но никак не с матрицей Зейделя порядка 29, хотя 5×6=29+1=30 (самостоятельная цепочка). Простые числа 5 и 29 – независимы.

Скарпи в 1898 году нашел вставку одноблочной матрицы в одноблочную, без "клея" в виде J. Необычно в методах без компенсации-шва J то, что вставка сопровождается кручением блоков, как в номерном замке. Ясно, что многоблочные структуры тоже можно раздувать, поблочно. Появляются многочисленные модификации этого древнего метода. Если матрицу для заливки шва на диагонали не добавлять, для сбрасывания напряжения структуры надо отрезать кайму. Как если бы жестяную банку открыли, крышка уже не нужна. Она была "клеем" на ядре, выбросили. Если метод Скарпи, это номерной замок, то тут (inversed Scarpis method, ниже) на один сундук их вешается два.



Кососимметричная матрица порядка 92


Кососимметричные матрицы Адамара, они более первичны: порождения метода Сильвестра и произведения Кронекера теряют ось симметрии, это вторичные матрицы, построенные от матриц заведомо более низкого порядка. Согласно гипотезе Дженнифер, кососимметричные матрицы существуют для любого порядка 4t. Напомним, что через десять лет после нахождения Голомбом, Баумертом и Холлом первой "компьютерной" матрицы порядка 92, Себерри отыскала кососимметричную 92.

Большой вклад в развитие методов plug into внесли работы Дженнифер Себерри и Миеко Ямады (J. Seberry and M. Yamada, знаменитый обзор 90-х). Для широкозахватности метода (не всегда это обязательно) обработки расширению подвергается не любая матрица, а матрица антисимметризованная. Чтобы избежать разрывов, как в обоях, на диагональ примешивают диагональные же матрицы – все из единиц, помимо (возможно) диагонали (d-матрицы). Это клей, d-матрица, она и сама по себе живет. Клей, который без всего, это диагональная квазиортогональная матрица.

Ядра матриц Адамара и Белевича (cores) ортогонализуются изменением отрицательного элемента, обычная подгонка. Но есть еще и вставка ядра с каймой в ядро, при этом уровень отрицательный квазиортогональной матрицы подскакивает до –1, не дожидаясь бесконечности. Получение расширенных матриц Адамара (или взвешенных матриц) вставками матриц с дистанцией порядков 0 (Kroneker product) 1 и 2 – обыденность симметризованных представлений пар матрица и ядро или двух близких целых, с заменой клеток на диагонали на единичный блок J или J–2I.

Антисимметрирование позволяет отказаться от смещений, поскольку оно спотыкается о сложность расчета смещений для кратных порядков. Это, как бы, разные умножения-вставки 27*28 – обычный метод, а 28*27 – иной. Когда в 28 вставляем симметрированную матрицу 27 без смещения, не возникает проблем. Выходит, что обобщение метода Скарпи, приписываемой молвой Палею (хотя сомнительно для 33-го то года, источник толкует об ином обобщении), таки возможно, но сам ход обобщения иной. Меняем вставку на обратную, антисимметрируем матрицу перед этим, и ... готово, 756.


Jennifer Seberry and Mieko Yamada, Hadamard matrices, sequences, and block designs, Contemporary Design Theory: A Collection of Surveys, J. H. Dinitz and D. R. Stinson, eds., John Wiley and Sons, Inc., 1992. pp. 431–560

МАТЕМАТИК УМБЕРТО СКАРПИ



Umberto Scarpis (Padova 1861 – Bologna 1921)


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


SCARPIS-BALONIN PRODUCT
H=C×C (MERSENNE SQUARE) n=q*(q+1)


Первую версию модифицированного алгоритма писал Юра Балонин (2014): основа (core) вставляется в самою себя, с позиционным поворотом Скарпи, расширяемые элементы определяют знак каймы (все просто). Мало известное произведение основы С (core) размера q=3 mod 4, простое, нормализованной матрицы Адамара H (размера n=1+q на нее саму. Произведение Скарпи "×" с расширением (Scarpis product), размера q(q+1), в оригинале статьи описание алгоритма сложнее – моя адаптация в одну формулу, имеет вид:


где T – матрица перестановок (циклического сдвига) в степени, равной произведению индексов (i–1)(j–1) элементов основы, индекс считаем от 0; e – вектор из 1. Конструкция симметричная, сдвигать можно столбцы. Матрица С=–sign(M), M – матрица Мерсенна, произведение Скарпи описывает их "квадрирование", поскольку нужны только элементы основы. Есть превосходная детализация метода Скарпи Драгомиром (метод в виде процедуры ниже).

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.

Балонин Н. А., Балонин Ю. Н., Сергеев М. Б. Вычисление матриц Мерсенна и Адамара методом Скарпи // Вестник информационных технологий, механики и оптики. 2014. № 3. С. 104–112.



Core C7 and Nicks' matrix H56



Core C7 and Dragomirs' matrix H56

DRAGOMIR'S ALGORITHM | CRETAN PROPUS

Вычисления цепочками (матричная экспонента)

GENERALIZED SCARPIS


Scarpis observed version for q is prime, circulant shift modulated by index multiplication makes blocks to be orthogonal pairwise, in common case there are blocks besides of etries inside Jacobsthal structure: it is used in Hadamard and Belevich matrix core multiplication below; different distantions between cores 0, 1, 2, 3 observed in Vitrages.



Skew Mersenne matrix 27 and Hadamard 28 to get matrix 756


Для степеней простых и составных чисел, порождающих матрицы Мерсенна, например, порядка n–1=27, алгоритм получения матрицы Адамара порядка 28*27=4m=756, m=n(4n–1)=189 состоит, как ни парадоксально, в отказе от знаменитого смещения. Ядро кососимметрической матрицы Адамара вставляется в матрицу Адамара, цепочка центральных блоков замещается матрицей из единиц J=ones(M). Таким способом можно построить и матрицу Адамара 56, порядка, обычного для произведения Скарпи матрицы порядка 7. Для M15, M35, M39, M51 метод тоже работает, так что простота порядка тут не при чем.

Так можно расправиться и с ядром порядка 13, получив взвешенную W(14*13=182,169)!

Применительно к массиву Вильямсона метод был опубликован в работе Дженнифер Себерри, см. работу Seberry, 1975. Ввиду большого вклада Дженнифер Себерри (и Миеко Ямады) в расчеты матриц Адамара вставками (plug into) кососимметричный массив Вильямсона называется массивом Себерри-Вильямсона: матрица A – кососиметрическая, B, C, D симметричные обратные циркулянты, каталог кососимметрических матриц): пусть M=core(H); в таком случае имеем произведение Кронекера с поправкой A=A×M+I×(J–M), B=B×M, C=C×M, D=D×M; here × is usual Kroneker product, I=eye(A), J=ones(M).

*) Order 756 is reachable: together with 428 it is specified in list 428, 596, 604, 612, 732, 756 of SAS-package. Possible interpretation: 756 is based on Williamson matrices, size 189.

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


Обычный метод Скарпи вставляет матрицу Мерсенна в расширенную каймой матрицу Мерсенна с циклическим смещением основы (core). Возможен ход наоборот, отрезаем кайму у бициклической матрицы Мерсенна с каймой (базируется, как и все обычные матрицы Мерсенна, на адекватной ей по структуре матрице Якобсталя с нулевой диагональю) ! Не добавляем теперь, а отбрасываем кайму. Получим четную основу, бицикл. Четное ядро режем пополам. Ничего, что у половинки размер не мерсеннов (например, 13, prime), вот что ново. Берем пару половинок, применяем метод Скарпи. Блоки собираем снова в "бицикл", получаем матрицу Адамара ! Инверсный метод Скарпи. Выше добавляется кайма. А тут она выбрасывается! Бициклическое ядро увеличивается. Совершенно новый метод!



Inversed Scarpis-Balonin method NEW, block-sizes 1 or 3 (mod 4)!


где × – операция произведения Скарпи (со смещениями), СTС =(q+1)IJ (произведение ядра от ядра дает блочно-диагональную матрицу с диагональными блоками (q+1)I–2J).

Еще раз, с размерами. В методе используется бициклическая матрица Мерсенна с каймой – затравка размера pm=2q+1, pm – не обязательно простое целое, можно 15. У нее отчикивается кайма, и Скарпи резво ортогонализует с раздуванием два блока, причем, любых размеров, и 3 mod 4 и 1 mod 4. Блоки слагают расширенную матрицу Адамара. Роль каймы – служить для формирования матрицы Мерсенна, роль крышки жестяной банки. Ее выбрасывают.



Two skew bicirculant cores: M7 and M27


Для q=(pm–1)/2 нечетного простого целого, pm – порядок бициклической матрицы Мерсенна с каймой, существует матрица Адамара размера n=2q(q+1) ! Это касается как q=3, так и q=5 ! и т.п. Алгоритм Скарпи работает тут иначе.

Бициклическое ядро матрицы Мерсенна является ортогонализуемым, и это мало известно. Для 7=3+3+1 можно найти матрицы Адамара порядков 3×4=12, 24, 48 (и 56 по Скарпи); 15=7+7+1 дает порядки 7×8=56 (!), 112, 224 (не 240). При 3×3×3+1=28=13+1+13+1, 2*13×14=364 (!), *2=728 (не 756, мы слишком рано получаем ортогональное субядро). Отметим: 2x(x±1)=364 дает оба перемножаемых порядка 13 и 14, корнями.

Пусть n=2q(q+1), размер n/4=q(q+1)/2 – фигурирует в некоторых теоремах существования матриц Вильямсона. Парный метод дает порядок 56, так что и 756 возможен, у матриц Вильямсона, скорее всего, в четверной модификации метода (четырехядерный Скарпи).

Бицикл расширяется легко до ортогональной матрицы промежуточных размеров: 7=3+3+1 дает две матрицы 12, и одну 24, с ядром 23, 23×24=552. Довольно много вариантов всяких матриц.

We can calculate "middle"-order matrices: for 7=3+3+1 we can get Hadamard matrices orders 3×4=12, 24, 48 (and 56 finally); the same reasons non prime 15=7+7+1 gives orders 7×8=56 (!), 112, 224 (not 240, to get this matrix it is finished by orthogonal sub-core too early).


СОВЕРШЕННЫЕ ЧИСЛА


Бог создал Землю за шесть дней. Это число совершенно. Сумма его делителей равна числу. Следующее такое число 28. Мерсенн 27, неберучка 3×3×3. Блочные матрицы, это матрицы аддитивные, их порядок нарастает аддитивно. Возможно, в этом кроется ключ к построению матрицы 756. 4u2u=756=784–28, 784 – регулярная матрица, продукт пары (27, 29); 4u2u=189 при u=7 и (u=–27/4).

Еще Евклид доказал, что если простое число q имеет вид числа Мерсенна*), то число q(q+1)/2: 6=1+2+3, 28=1+2+4+7+14, 496=16*31, 8 128=64*127, 33 550 336,... является совершенным. Леонард Эйлер доказал, что все четные совершенные числа имеют вид, указанный Евклидом. Значения q=2k–1, k=1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

*) Простые числа Мерсенна 2k–1 названы в честь Марена Мерсенна, который еще в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, его формула дает простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным. Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами – числами, равными сумме всех своих делителей, отличных, конечно, от самого числа.

PAIR PRIMES



PRODUCT RHM=[M⊗S] or H=[S⊗M]
SEIDEL ⊗ MERSENNE: PAIR OF MATRICES OF ODD ORDERS n=(s–1)(s+1)+1


Менее комментируемый раздел содержит немало не опубликованных еще произведений различных основ (матриц Адамара и Белевича) друг на друга. Порядки основ отвечают порядкам округленных до целых значений матриц Мерсенна и Зейделя. Любое произведение такого типа подымает модульный уровень элементов, в данном случае, до 1. Помимо этой приятности находится еще одна привлекательная черта взаимных произведений основ: они продуцируют регулярные матрицы Адамара (матрицы с максимальным эксцессом, матрицы с равными значениями сумм и столбцов).



Seidel matrix S5 and Hadamard matrix H36=[S5⊗M7]


Pair primes (3, 5) and 6k±1: (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349), (419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619), (641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859), (881, 883)

Balonin N. A., Sergeev M. B. Regular Hadamard matrix of order 196 and similar matrices // Informatsionno-upravliaiushchie sistemy, 2015, № 1 (73), pp. 2–3.

OTHER PAIR NUMBERS



THE STRUCTURE OF MATRICES



H-HADAMARD M-MERSENNE, S-SEIDEL, R-REGULAR, F-FERMAT


Any normalized HM, order 4m, gives RHM, order n=16m2 (m,4m,n): (1,4,16), (2,8,64), (3,12,144), (4,16,256), (5,20,400), (6,24,576), (7,28,784), (8,32,1024), (9,36,1296), (10,40,1600), (11,44,1936), .. so squares n=400, 1024, etc. are closed (H. Kharagani), orders 484, 1156, etc. are unknown. Во всех этих экспериментах ортогональность обретают матрицы, ортогональные сами по себе или ортогональные с каймой, вставляемые в почти соразмерные себе клетки. Это общее правило. Иначе их рисунок надо глубоко адаптировать, а иногда это и невозможно. Порядок 400=20×20 менее проблематичен, чем 484=22×22=121×4, так как 22–1=21 (проблемен). От пары (или основания квадрата) требуется разложимость.

HADAMARD ⊗ MERSENNE: PROPUS P=[H4⊗M] n=4m



Mersenne matrix M7 Propus matrix H28

SCARPIS | BUSH-TYPE RHM | VITRAGES | JACOBSTHAL MATRICES | NUMBERS

Rambler's Top100