JACOBSTHAL MATRICES



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 1.05.2015

Матрица Якобсталя Q удовлетворяют уравнению Q'Q = nI – J, где Q – искомая целочисленная матрица, I,J – единичная матрица и матрица, состоящая полностью из 1 (тех же порядков, что и Q): QJ = JQ = 0, с элементами ±1 вне нулевой диагонали. Закрытые порядки (не существуют): 21, 33, 57, 69, 77, 93, n<100.

Матрицу Q ввел в рассмотрение немецкий математик Эрнст Якобсталь, ученик Фробениуса и Шура, работавший в начале прошлого века над диссертацией по квадратичным вычетам.

Уравнение напоминает условие ортогональности, решение: циклическая матрица символов Лежандра Qij = ((ij)/n), i<>j заведомо существует, если n – простое число. Циклическая форма симметрическая или кососимметрическая – в зависимости от того, принадлежит ли разность –1 квадратичным вычетам, т.е. n=1 (mod 4) или n=3 (mod 4), соответственно.

МАТРИЦЫ УДВОЕННОГО ПОРЯДКА, ПЛЮС 1

0
 eT 
 –eT 
 –e 
Q
 I+Q 
e
 (–I–Q)T 
 QT 
    
0
 eT 
 –eT 
 –e 
A
B
e
 –BT 
 AT 
    
0
 –eT 
 eT 
 –e 
A
B
e
 BT 
 –AT 


Регулярную матрицу Якобсталя порядка m = 3 (mod 4) – простое число, можно удвоить по итерационной формуле. Для m = 1 (mod 4) симметричный блок запихиваем в бок, центральный блок – ищется дополняющая его кососимметричекая матрица. Впрочем, можно искать оба блока A, B, в частности, для четных порядков симметричной матрицы Якобсталя (см. Shadow matrices).



Jacobsthal matrix Q11 and border two-circulant Q11


LIBRARY OF JACOBSTHAL MATRICES

ОСОБЫЕ ПОРЯДКИ

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

СИММЕТРИЧНОЕ ЯДРО С-МАТРИЦЫ


Симметричную матрицу Якобсталя можно найти как ядро (core) С-матрицы, которая, как известно, симметрична. В первооснове это половинки H-матриц.



С-матрица порядка 26, с 2 и 6 блоками


КВАДРИРОВАНИЕ, ТРОИРОВАНИЕ


Core of square: Q ⊗ Q + I ⊗ J – J ⊗ I, cube: Q ⊗ Q ⊗ Q + Q ⊗ I ⊗ J + I ⊗ J ⊗ Q + J ⊗ Q ⊗ I, .. orders give by chain of Kronecker products the next matrices: сore of C3 leads by 3x3x3 to core of C28, core of C8 leads by 7x7 to core of C50, and so on. The Jacobsthal matrices arose out of work by Goldberg in about 1967. In fact the Q ⊗ Q ⊗ Q + I ⊗ J ⊗ Q + J ⊗ Q ⊗ I + Q ⊗ I ⊗ J given there with Q the core of a conference matrix or a skew-Hadamard matrix allows the core of the matrix of order p3 + 1 to be found.

In mathematics, the Paley construction (WIKI) is a method for constructing Hadamard matrices using finite fields. The construction was described in 1933 by the English mathematician Raymond Paley. The Paley construction uses quadratic residues in a finite field GF(q) where q is a power of an odd prime number. There are two versions of the construction depending on whether q is congruent to 1 or 3 (mod 4).

The quadratic character χ(a) indicates whether the given finite field element a is a perfect square. Specifically, χ(0) = 0, χ(a) = 1 if a = b2 for some non-zero finite field element b, and χ(a) = −1 if a is not the square of any finite field element. For example, in GF(7) the non-zero squares are 1 = 12 = 62, 2 = 32 = 42, and 4 = 22 = 52. Hence χ(0) = 0, χ(1) = χ(2) = χ(4) = 1, and χ(3) = χ(5) = χ(6) = −1. The Jacobsthal matrix is circulant matrix Legendre symbols based.

COMMON PRODUCTS

ВЕЛИКОЛЕПНАЯ ПЯТЕРКА 5*9


The Seberry construction of CORE C3646=circul(A,B,C,C',B') calculated through the A,B,C-iterations for orders n=45*92k+1 by the following formulaes

A=A⊗A⊗A+A⊗I⊗J+I⊗J⊗A+J⊗A⊗I
B=B⊗Bs⊗Bs+C⊗Bd⊗Bs–B⊗Cd⊗Bd+C⊗Cs⊗Bd
C=B⊗Bs⊗Cd+C⊗Bd⊗Cd+B⊗Cd⊗Cs–C⊗Cs⊗Cs


where I – identity matrix, J – matrix with 1, Bs=(B+B')/2, Bd=(B–B')/2, Cs=(C+C')/2, Cd=(C–C')/2, it is started at matrices of rich cell-structure: A – a circulant matrix of circulant cells (1-type), B – a circulant matrix of back-circulant cells (2-type), C – a cross-matrix (0-type): it gives Balonin-Seberry construction (below).

MATRIX C3646 (5×9×9×9+1) | МАТРИХ C442 (7×7×9+1)


ПРИМЕРЫ НАХОЖДЕНИЯ МАТРИЦ СТЕПЕНЕЙ ПОРЯДКА


Собственно, есть формула возведения порядка матрицы в квадрат, использующая кронекерово произведение: QxQ+IxJ–JxI, где I, J – единичная матрица и матрица из единиц.

Такие матрицы можно вычислить иначе – замещением элементов {0, 1, –1} матрицы Якобсталя тремя циклическими блоками:

Такого сорта формулы мотивируют и нахождение матриц Адамара на основе близких пар

Для куба степени (формула Белевича): Q ⊗ Q ⊗ Q + Q ⊗ I ⊗ J + I ⊗ J ⊗ Q + J ⊗ Q ⊗ I.

There is an other opinion, that Jacobsthal matrices arose out of work by Goldberg in about 1967. In fact the Q ⊗ Q ⊗ Q + I ⊗ J ⊗ Q + J ⊗ Q ⊗ I + Q ⊗ I ⊗ J, Q is the core of a conference matrix or a skew-Hadamard matrix, leads to the core of matrix of order q3 + 1.

ВЫЧЕТЫ НАБОРА ИРРАЦИОНАЛЬНЫХ ЧИСЕЛ


В тридцатых годах прошлого века Раймонд Пэли рассмотрел квадратичные вычеты последовательности девяти чисел

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

Q=
A
C
B
B
A
C
C
B
A


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



Условие, при котором получается симметричная матрица, зажимает C=B' и верхнюю половину элементов A (например, решение при a=[0 –1 1], b=[1 –1 1]). Наиболее простая симметричная конструкция строится на паре векторов a=[0 –1 –1], b=[1 –1 –1]):

КВАДРАТИЧНЫЕ ВЫЧЕТЫ СЛОЖНЫХ ПОЛЕЙ ГАЛУА


Квадратичные вычеты. Операция "умножения" не выводит целые числа поля Галуа GF(p) за пределы этого поля, по определению. Она связана с "возвращением" квадратов чисел в пределы выбранного числового диапазона.


Те места, куда квадраты чисел "возвращаются", называются квадратичные вычеты (quadratic residues). Прочие числа числового поля называются квадратичные невычеты.

Квадратичные вычеты полей Галуа GF(p2) позволяют идентифицировать элементы полей значениями символов Лежандра на принадлежащие квадратичным вычетам 1 и невычетам –1. Цепочки символов разбиваются на фрагменты длиной p, позволяющие строить циклические блоки блочных циклических матриц Якобсталя.



Матрицы Якобсталя, построенные на блоках Лежандра для GF(9), GF(25)


МАТРИЦА ЯКОБСТАЛЯ КОНСТРУКЦИИ БАЛОНИНА-СЕБЕРРИ


Случай n=k2(k+2), где k,k+2 – порядки матриц Якобсталя, на случай k=3: вытесняем 0, 1, –1 матрицы Якобсталя порядка 5 блоками A, B, C, полученными ортогональными преобразованиями матрицы Якобсталя порядка 9=3x3; 3, 5 – пара близких простых.

или

Более регулярный путь расчета матрицы Якобсталя n=45=325

аналогичен расчету матрицы Якобсталя, n=1573=11213.

МАТРИЦА КОНСТРУКЦИИ РУДОЛЬФА МАТОНА

В прежней редакции

BY NEGACYCLIC MATRICES

HIDDEN CIRCULANTS | C442 | C3646 | R. MATHON | J. СЕБЕРРИ

Rambler's Top100