КВАДРАТИЧНЫЕ ВЫЧЕТЫ



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 1.05.2014


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


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

Пример 1. Рассмотрим GF(7) с элементами {0, 1, 2, 3, 4, 5, 6}. Квадраты чисел 12=1, 22=4, 32=9=2 (mod 7), 42=16=2 (mod 7), 52=25=4 (mod 7), 62=36=1 (mod 7). Взятие квадратов по модулю простого числа 7 "вернуло" числовые значения (вычеты) 1, 2, 4.

Определение 2. Функция Лагранжа – бинарная функция аргумента из GF(p), равна 0 для 0, равна 1, если число – квадратичный вычет. И равна –1, в противоположном случае.

Определение 3. Циклическая матрица, построенная на векторе значений функции Лагранжа, называется матрицей Якобсталя Y, для p равных простым числам она почти ортогональна

YTY = p IJ


где I, J – единичная матрица и квадратная матрица единичных элементов порядков p, причем произведения J Y = Y J = 0.

Циклической матрице Y отвечает дизайн SBIBD(4t–1;2t;t), с матрицей связности A, получаемой заменой –1 на 0. Из двух возможных комплиментарных SBIBD(7,4,2) и SBIBD(7,3,1)



Complementary pair SBIBD(7,4,2) and SBIBD(7,3,1)


последний назван адамаров, поскольку от нормализованной матрицы Адамара его отделяет только кайма из 1. Еще один способ получения этого дизайна состоит в замене нулевых диагональных элементов матрицы Якобсталя на –1.

Для большей определенности из пары комплементарных дизайнов в качестве основного принято выбирать тот, у которого ν > 2k. Например, при определении адамарового дизайна.

Определение 4. Адамаров дизайн SBIBD(4t–1;2t–1;t–1) назван так постольку, поскольку после замены в матрице связности A элемента 0 на элемент –1, и добавления каймы из 1, мы получим нормализованную матрицу Адамара H, HHT = n I.


Отметим. Значения функции Лежандра {0,1,1,1} для поля GF(4) дают циклическую матрицу, отличную от матрицы Якобсталя тем, что

YTY = I + 2J

,

которое можно представить также композицией пар {0,1} {1,1}, порождающих блоки блочной циклической матрицы, по аналогии со случаем GF(9).


ВЛИЯНИЕ ТЕОРИИ ГРУПП


Операцию "возвращения" (идея Зингера [1]) можно построить на основе "честных" вычетов. Теория групп рассматривает алгебраические операции умножения (возведения в квадрат), сложения весьма условно.

Пример 2. Пусть D = {1, 3, 4, 5, 9} – подмножество целых {0, 1, 2, ... , 10}. Рассмотрим все ненулевые разности Δ по модулю 11: 1 – 3 = –2 = 9 ; 1 – 4 = –3 = 8; 1 – 5 = –4 = 7; 1 – 9 = –8 = 3; 3 – 1 = 2; 3 – 4 = –1 = 10; 3 – 5 = –2 = 9; 3 – 9 = –6 = 5; 4 – 1 = 3; 4 – 3 =1; 4 – 5 = –1 = 10; 4 – 9 = –5 = 6; 5 – 1 = 4; 5 – 3 = 2; 5 – 4 = 1; 9 – 1 = 8; 9 – 3 = 6 = 5; 9 – 4 = 5; 9 – 5 = 4. Отметим, что одинаковые разности встречаются ровно дважды, причем матрица связности A дизайна SBIBD(11;5;2) имеет вид circ(0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0).


Разностные наборы объяснили существование циклических матриц с адамаровым дизайном для не простых значений p, равных произведениям двух близких простых чисел или их степеней p=3×5=15, 5×7=35, 7×9=63 и т.п. [2, 3].



Marshall Hall (1955) gave SBIBDs of M15 and M35



Marshall Hall (1955) gave SBIBD of M63


ВЛИЯНИЕ ТЕОРИИ ФИНИТНЫХ ПОЛЕЙ ГАЛУА GF(p)


Если наборы целых чисел не годны, для образования поля, часть поля строится с помощью корней полиномов (включая иррациональные числа). Полиномиальное уравнение дает средство построения возвратной операции путем выражения старшей степени m корня степенями меньшего порядка. Пэли использовал это для построения расширенных полей GF(pm).

Пример 3. Следующая набор из девяти чисел

0, 1, –1, a, a+1, a–1, –a, –a+1, –a–1


определенный с помощью иррационального корня a неприводимого к простым множителям многочлена x2 + x – 1 = 0, образует расширенное поле Галуа GF(p=32). Ему отвечает набор символов Лежандра, разделенный на три составляющие a=[0, 1, 1], b=[–1, –1, 1], c=[–1, 1, –1], порождающие циклические блоки A, B, C блочной циклической матрицы Якобсталя

Y=
A
C
B
B
A
C
C
B
A


Наиболее простая симметричная конструкция циклических блоков, удовлетворяющая условию симметрии элементов a[2]=a[1], c[0]=b[0], c[1]=b[2], c[2]=b[1] блочной циклической матрицы строится на паре векторов a=[0, –1, –1], b=[1, –1, –1]), c=b.

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


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

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

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

Четвертая степень

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


Порядки, не равные простым числам, приводят к блочным матрицам. Например, для построения матрицы Якобсталя порядка n=k2(k+2), где k,k+2 – порядки матриц Якобсталя, на случай k=3 воспользуемся конструкцией со скрытой циклической симметрией.

1. Singer, J. A theorem in finite projectiνe geometry and some applications to number theory, Trans. Amer. Math. Soc. 43, 1938, pp. 377–385.
2. Hall, Jr , M. A survey of difference sets, Proc Amer. Math. Soc. 7, 1956, pp. 975–986.
3. Stanton, R. G. and Sprott, D. A. A family of difference sets, Canad. J. Math., 10, 1953, pp 73–77.



Rambler's Top100