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

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

МАТРИЦЫ АДАМАРА-МЕРСЕННА | СИМВОЛ ВЕЛИКОГО ОДИНА

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

На сайте есть тематический форум по матрицам Адамара.

КРАТКОЕ ИЗЛОЖЕНИЕ ТЕОРИИ ЧИСЕЛ И МАТРИЦ АДАМАРА

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

АЛГОРИТМ ЕВКЛИДА

Наша книга опирается на исполняемые алгоритмы, поэтому вполне логично рассмотреть сначала алгоритм Евклида. Считается, что именно с него берет начало сам термин, алгоритм. Изложим его на свой манер, с шагами, и с обязательной теперь уже исполняемой с листа программой.

Античный человек, как и нынешний, измерял свой путь шагами. Это естественно, подсчитать, во сколько целых шагов укладывается пройденный путь. Содержание древнейшего в истории человечества алгоритма состоит в том, что остаток пути оценить в шагах невозможно, но зато сам шаг можно измерить теперь полученным остатком пути. Ведь остаток заведомо меньше его. Величина шага принимается за новый путь, а остаток пути, за новый шаг. Ясно, что эту процедуру можно повторять и повторять, инвертируя, заменяя шаг остатком и уточняя величину пройденного пути. Опираясь, в целом, всего на одну меру измерения - начальный шаг. Не применяя длин стоп, фаланг и прочих инградиентов.

Построим наш первый алгоритм целиком на этой идее, обозначая путь как a, шаг как b, количество вхождений инвертируемого шага как q, остаток a-qb как r.


a=225, b=10, r=b,

while r>0, 

 q=floor(a/b), r=a-q*b, q=?,   

 if r>0, a=b, b=r, end, 

end,

Запустим исполняемый алгоритм для пути a=225 и шага b=10, получим последовательно количества вхождений (фракции) 22, 2. Измените a на 227, результаты изменятся на 22, 1, 2, 3. Результат применения алгоритма Евклида принято записывать в квадратных скобках, особо выделяя первое полученное число шагов в пути по сравнению с прочими количествами выбором особого знака разделения

225:10 = [22; 2], 227:10 = [22; 1, 2, 3].

Это напоминает запятую в десятичной записи числа, однако выделяемые разделителями количества - не цифры, а числа. Символ отношения a:b можно заменять дробной чертой a/b, тут, как и в школьных обозначениях пропорций или дробей, применительно к ситуации, непринципиально.

ЦЕПНАЯ ДРОБЬ

Цепная дробь раскрывает в привычных арифметических терминах то, что бы отношение исходных чисел a и b, оцененное при помощи алгоритма Евклида, значило

a/b = [q0; q1, ... , qn] = q0 + 1/(q1 + ...).

В данном выше примере примере

225/10 = [22; 2] = 22 + 1/2,

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

227/10 = 22 + 1/(1 + 1/(2 + 1/3)) = 22 + 1/(1 + 3/7) = 22 + 7/10.

В приложении к первой главе приводятся классические алгоритмы поиска наибольшего общего делителя и фракций отношения двух целых чисел a/b, фракций вещественного числа и наилучшего приближения его отношением двух целых чисел. Все это входит в классику теории числа, хорошо известно, и едва ли заслуживает ныне более подробных комментариев. Ведь перед нами превосходно написанные книги, дело лишь за соответствующими иллюстрациями. Остановимся подробнее на иных аспектах, связанных со становлением теории чисел.

ТЕОРЕМА ФЕРМА

Советник Ферма прославился тем, что обратил внимание на следующее. Целые числа, удовлетворяющие уравнению из теоремы Пифагора

x2 + y2 = z2

получили название пифагоровых троек (x, y, z). Еще древние научились такие комбинации искать, с точностью до масштабного множителя

x=p2 – q2, y=2pq, z=p2 + q2.

Пифагоровы тройки как точки пересечения окружности с сеткой

Ферма заметил, что среди пифагоровых троек нет квадратов целых чисел. Иными словами, аналогичное уравнение четвертой степени неразрешимо в целых числах, и ему показалось, что он понял - почему это происходит для всех степеней, выше второй. В том случае, когда решение найти нетрудно, ценится противоположное умение указать те случаи именно, когда таковое определенно не существует.

Дальнейшая история теоремы Ферма известна и изложена во многих источниках. Ферма, за дифицитом бумаги в его время, царапал свои записи на широких свободных полях учебника Диофанта. Сын издал записи отца. Теорема Ферма спасла от смерти фабриканта, который снял с полки экземпляр, заинтересовался ходом мысли, и забыл про пистолет. Денежный приз за доказательство, назначенный им в газетах, всколыхнул широкие слои общества. На эту тему состоялись дебаты во французской академии наук, собравшей вереницу корифеев после того, как Наполеон поощрил Вольта серьезным денежным призом за изобретенную им электрическую батарейку. То есть, сделал математику профессией. В петровской академии наук, у нас, в Петербурге, задолго до разворачивания столь долгого эха, утверждением Ферма занялся Эйлер.

Для тех, кто ценит искусство, на страницах современной книги можно предложить насладиться созданным в СССР кинорежиссером С.Л. Райтбуртом научно-популярным фильмом на тему теоремы Ферма.

ГИПОТЕЗА ЭЙЛЕРА

Тут мы притормозим взмахи исторического маятника, и остановимся на расширительных толкованиях теоремы Ферма, возникших на почве ее долгой недоказуемости. Эйлер доказал утверждение Ферма на случай третьих степеней. Он же предложил выход из тупика, напрашивающийся ввиду того, что четверка чисел 3, 4, 5, 6 связана сходным выражением

33 + 43 + 53 = 63.

Почему бы степенному уравнению не набирать (для его разрешимости) вместе с показателем степени равное ему количество обязательных слагаемых? В начале прошлого века, казалось бы, нашлось подтверждение (Нори, 1911 год)

304+1204+2724+3154 = 3534.

Спустя полвека свое веское слово сказали, наконец, компьютеры. Контрпример К. Дж. Леидера и Т. Р. Паркина (L. J. Lander, T. R. Parkin, 1966 года) одним росчерком цифрового кода развалил эту красивую гипотезу

275 + 845 + 1105 + 1335 = 1445.

В 1988 году Наум Элькис из Гарвардского университета нашел еще и следующее решение:

26824404 + 153656394 + 1879604 = 206156734

Так компьютерные эксперименты поставили точку на попытке поиска решения, закрываемого теоремой Ферма.

РАЗЛОЖЕНИЕ НА СУММУ КВАДРАТОВ

Еще Жирар и, позднее, Ферма заметили, что любое натуральное число представляется суммой (не более, чем) четырех квадратов целых чисел. Эйлер подробно рассмотрел вопрос о двух слагаемых, тут сквозит нечто близкое пифагоровым тройкам

x2 + y2 = z.

Этим уравнением плотно занимались уже не античные мифические греки, а наши современники. В 1749 году, после семи лет работы и почти через сто лет после смерти Ферма, Эйлеру удалось доказать теорему о простых числах, согласно которой разложение на сумму квадратов всегда возможно для чисел 4k+1. Ни одно число вида 4k+3 не представимо в виде суммы двух квадратов. Число, содержащее в своем разложении лишь четные степени 4k+3, может быть представлено в виде суммы двух квадратов. Если отбросить заведомо не представимые суммой двух квадратов числа, то это 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, ... Числа типа 4k+1 представимы всегда.

Известны сложные схемы решения, принадлежащие Лежандру, Гауссу, Серру и Якобсталю. Основная теорема арифметики гласит, что любое число может быть представлено, причем, единственным образом (с точностью до перестановок) произведением простых чисел. Определение простого числа оперирует произведением, сложение - сторонняя операция для него. Путь к суммам тернист и пролегает через решение проблемы Гольдбаха.

ПРОБЛЕМА ГОЛЬДБАХА

В 1742 году немецкий математик Христиан Гольдбах в письме к своему другу и коллеге Леонарду Эйлеру (переписка опубликована) высказал одно очень простое утверждение. "Всякое целое число, большее или равное шести, может быть представлено в виде суммы трех простых чисел", - написал Гольдбах. Эйлер заметил в ответном письме, что проблема сводится к доказательству того, что каждое четное число есть сумма двух простых. Эта проблема, решения

x + y = z,

получила название "Проблемы Гольдбаха", и ее доказательство до сих пор не найдено.

А ведь правда: какое бы четное число мы не брали, его можно выразить суммой двух простых. Например:

6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7, ...

Можно взять сколь угодно большое число, и гипотеза окажется верна.

Следующий график количества вариантов разложения взят из обзора Тима Скоренко.

Проблема состоит именно в том, чтобы найти общее математическое доказательство утверждения Гольдбаха. Характерно то, что Гольдбах не был светилом математической науки своего времени. Он родился в 1690-м году и закончил юридический факультет Кенигсбергского университета: математика была всего лишь его хобби. В 1725-м году Гольдбах приехал в Россию, где получил звание академика Петербургской академии наук, а с 1742 года работал в Коллегии иностранных дел.

С Эйлером он вел дружескую переписку в течение 35 лет, вплоть до своей смерти в 1764 году в Москве. В 1843-м году 177 писем этой переписки были опубликованы. Он довольно много путешествовал и дружил с многими известными математиками, в том числе с семьей Бернулли. За свою жизнь он опубликовал менее десятка некрупных математических работ, хотя две из них – о бесконечных рядах – сделали его достаточно известным в научных кругах. Впрочем, в широких кругах Христиан Гольдбах стал известен благодаря нескольким фразам в одном-единственном письме к своему другу. Такие вот игры судьбы.

КОНЕЧНЫЙ НАБОР ЧИСЕЛ

Числа - абстрагированное свойство предметов иметь количественное выражение. Ряд чисел бесконечен, это абстракция. Количество обозначаемых ими реальных предметов может быть конечным. Лишние числа можно использовать по разному.

Галуа, игаясь с числом, лишние числа отбросил, обозначил конечные числа буквами и составил из них две таблицы: сложения и умножения. После чего показал, что для конечного набора чисел законы арифметики, с которыми мы знакомимся в школе, тоже выполняются. Иллюстрируя, что числа не существуют сами по себе, они - продукт изобретения ума человеческого.

Можно не отбрасывать лишние числа, а договориться, что часть из них обозначает одно и то же, как тут (предметы дает нижний ряд)

0 1 2 3 4 5 6 7 8 9 ..
0 1 2 0 1 2 0 1 2 0 ..

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

4 ≡ 1 (mod 3)

В общем,

a ≡ b (mod m)

означает просто, что a – b делится нацело на m. Поскольку числа, равные или большие по значению m, всего лишь обозначения, вычисления с ними с некоторыми оговорками можно заменить вычислениями с числами 0, 1, ... , m-1.

ЕЩЕ ОДНА ТЕОРЕМА ФЕРМА

Разместим в нижнем ряду значения квадратов чисел по модулю m=3

0 1 2 3 4 5 6 7 8 9 ..
0 1 1 0 1 1 0 1 1 0 ..

Такие наблюдения привели Ферма к обобщению, что если модуль m простой, то степень m – 1 любого a (не сравнимого с нулем) тождественна 1

am – 1 ≡ 1 (mod m)

Заметим, что для простого m число φ(m) = m – 1 означает количество чисел, меньших m и взаимно простых с m.

Свойство помечать единицей степени заинтересовало Эйлера, и он выяснил, что для любого m показатель (функция Эйлера) сохраняет отмеченное качество. Так m = 20 взаимно просто с 1, 3, 7, 9, 11, 13, 17, 19, т.е. φ(20) = 8. Обобщение Эйлером теоремы такое

aφ(m) ≡ 1 (mod m).

Минимальный показатель степени уравнения называется порядком числа a. Например, a=5 и m=11 взаимно просты, m - простое. Порядок числа 5 равен φ(m) = m – 1 = 10, т.е. 510 ≡ 1 (mod 11).

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

Теорема Ферма

am – 1 ≡ 1 (mod m)

вводит, по сути, понятие корня из 1 по модулю m. Свойство степенного уравнения иметь корни зависит от значения правой части, варьируемой (в общем) в диапазоне от 1 до m–1. Важные для теории сравнения значения, дающие разрешимые уравнения, называются вычетами (остальные невычетами).

Рассмотрим, например, квадраты последовательности натуральных чисел по модулю m=13

1 4 9 3 12 10 10 12 3 9 4 1

Квадратичные уравнения с правыми частями 1, 3, 4, 9, 10, 12 разрешими в целых числах, это вычеты. Остальные числа 5, 6, 7, 8, 11 - квадратичные невычеты. Множество 1, 2, ..., m–1, на котором ищутся квадратичные вычеты, избыточно, оно симметрично относительно середины интервала, ибо

(m – a)2 ≡ a2 (mod m).

Избыточность учитывается при построении алгоритмов, сокращая необходимые для вычисления вычетов операции.

СИМВОЛЫ ЛЕЖАНДРА

Свойство числа a быть или не быть вычетом по модулю m напоминает булеву функцию со значениями ±1. Сохранилось идущее от Лежандра дробное обозначение ее (a/m), поскольку она обладает мультипликативным свойством

(ab/m) = (a/m)(b/m).

Напишем алгоритм, вычисляющий вектор символов Лежандра по квадратичным вычетам модуля m, в точке 0 элемент вектора приравнивается 0.


m=13, c=legendre(m), c=?, 
n=line(c), g=[n c], plotL(g),

function: legendre(m), 
var c s m2, m2=floor(m/2), 
c=one(m), c={-1*c}, c[0]=0,   
for var i=1:m2, s=i*i, 
c[s-floor(s/m)*m]=1, end,
return c,
end,

КРИТЕРИЙ ЭЙЛЕРА

Вернемся к теореме Ферма, переписав ее как

aM ≡ ±1 (mod m)

где M = (m – 1)/2 (половина степени), т.е. аппроксимациям

m=4k+1: 1 5 9 13 17 21 ... m=4k+3: 3 7 11 15 19 23 ...

отвечают четные и нечетные числа M соответственно.

В терминах символов Лежандра теорема Ферма записывается в форме критерия, предложенного Эйлера

(a/m) = aM (mod m)

Из критерия следует, в частности, что число a = –1 есть квадратичный вычет для четных M, и квадратичный невычет для нечетных.

Тот факт, что сравнение a2 + 1 ≡ 0 (mod m) разрешимо для простых вида 4k+1 и неразрешимо для простых вида 4k+3, отмечал еще Ферма.

ЗАКОН ВЗАИМНОСТИ

Квадратичный закон взаимности, сформулированный Лежандром для двух простых чисел a и m, имеет вид

(a/m)(m/a) = (–1)MA,

где M = (m – 1)/2, A = (a – 1)/2. Он позволяет упрощать выкладки, сменой модуля.

Лейбниц, формируя курсы дифференциального и интегрального исчисления, отводил важное значение формализации математики, то есть, формулирования простых (но трудно доказуемых) правил, обращаясь к которым можно формальным образом решать задачи, не входя во всю сложность их проблематики. Закон взаимности как раз из числа таких правил, его полезно знать, для упрощений.

МАТРИЧНЫЕ ДИОФАНТОВЫЕ УРАВНЕНИЯ

Скалярное произведение играет особую роль в математике, с его помощью вводится понятие ортогональности векторов и матриц. В матричном случае это условие имеет вид

A'A = nI,

где I - единичная матрица, n - порядок матрицы.

Среди целочисленных решений этого уравнения наиболее известны матрицы последовательности Сильвестра

S =
A A
A –A

рекуррентной подстановкой в качестве A самих себя, начиная с S=1.

В последовательности матриц порядов 1, 2, 4, 8, 16, и т.п. встречаются все большие и большие пропуски. Еще в начале прошлого века Адамар высказал гипотезу, что решения с элементами ±1 существуют для всех степеней, кратных 4, и нашел матрицы 12-го и 20-го порядков. С тех пор отыскание адамаровых матриц стало чем-то вроде спорта. Теплицевы матрицы символов Лежандра являются строительными блоками при построении последних.

АССОЦИАТИВНЫЕ МАТРИЦЫ

Помимо обычной принятой в матричной алгебре операции умножения, существуют альтернативные варианты, которые переходят в обычную посредством перевода одного из векторов в матричную форму. Например, скалярное произведение двух векторов записывается при помощи символа транспонирования, превращающего вектор в "матрицу-строку"

(a,b) = a⋅b = a'b

Векторное произведение векторов - это произведение кососимметрической матрицы на вектор

a⊗x = Ax,

где

A =
0 -a3 a2
a3 0 -a1
–a2 a1 0
.

Операция ⊗ имеет тесное родство с операцией транспонирования тем, что она влияет на вектор перед нею, переводя его в отмеченную матричную форму. Тем самым, смешанное произведение векторов представляет собой хорошо известную в матричной алгебре билинейную форму

y⋅(a⊗x) = y'Ax.

С точки зрения векторно-матричного исчисления символ Лежандра (a/m), это вектор размерности m – 1 или m (если доопределить начальную точку, как 0)

c = [ 0, (1/m), ... , (m – 1)/m) ].

Легко видеть, что алгебре символов Лежандра отвечает перевод вектора в диагональную форму, поскольку результат - тоже вектор

(ab/m) = Ab,

где A - диагональная матрица символов Лежандра. В теории матриц существуют диагональная, фробениусова, теплицева, ганкелева и другие формы, производные от векторов. Каждая из них порождает соответствующую матрицу символов Лежандра.

МАТРИЦА ЯКОБСТАЛЯ

Матрица, элемены которой зависят от разницы символов, называется теплицевой. Теплицева матрица, построенная на основе вектора символов Лежандра для

Tij = c(i-j/m), i≠j,

называется матрицей Якобсталя (на диагонали нули). Эта матрица симметрическая или кососимметрическая в зависимости от того, принадлежит ли разность –1 квадратичным вычетам, т.е. m=1 (mod 4) или m=3 (mod 4) соответственно. Если m - простое число, то эта матрица циркулянтная.

Теплицева циркулянтная матрица Якобсталя отличается от ортогональной матрицы тем, что

T'T = (m – 1)I − O, и TO = OT = 0,

где I - единичная матрица, O - матрица, состоящая полностью из 1.


m=13, T=jacobsthal(m), mesh(T),

A={T'*T}, A=?, O=ones(T), A={T*O}, A=?, 

function: jacobsthal(m), 
var c ij s r m1 T, m1=m-1,
c=legendre(m), T=zeros(m),   
r=m-floor(m/4)*4,
for var i=0:m1, 
for var j=0:i-1, 
k=i-j, s=c[i-j],
T[i][j]=s, if r=3, s=-s, end,
T[j][i]=s, 
end, end, 
return T,  
end,

function: legendre(m), 
var c s m2, m2=floor(m/2), 
c=one(m), c={-1*c}, c[0]=0,   
for var i=1:m2, s=i*i, 
c[s-floor(s/m)*m]=1, end,
return c,
end,

МАТРИЦА ПЭЛИ

Случай m=9 выбивается из теории тем, что 9 - не простое число (квадрат 3). Раймонд Пэли поставил ему в соответствие неприводимое (неразложимое на простые множители) уравнение вида

x2 + x − 1 = 0,

имеющее корни 0.618.., –1.618... Обозначим его корень a и рассмотрим последовательность из 9 чисел, порождаемую отстоянием корня a от 1

0, 1, −1, a, a+1, a−1, −a, −a+1, −a−1

Возьмем квадраты: (±1)2=1, (±a)2=−a+1, (±(a+1))2=a−1, и (±(a−1))2=–1. Как видно, a и a+1, –a и –a–1 не являются квадратами. Этой последовательности отвечает вектор обобщенных символов Лежанда

0, 1, 1, –1, –1, 1, –1, 1, –1

Вектор разделяется на три равные части, которые позволяют построить циркулянтные блоки третьего порядка A, B, C. Получив три блока, достраиваем на их основе блочно-циркулянтную матрицу

P =
A C B
B A C
C B A

состоящую в итоге из девяти 3×3 циркулянтных блоков. Симметричная матрица Пэли обладает теми же самыми свойствами, что и матрица Якобсталя.


m=9, P=paley(), mesh(P), 

A={P'*P}, A=?, O=ones(P), B={P*O}, B=?, 

function: paley(),
var a b c A B C,
a=[0 1 1], b=[-1 -1 1], c=[-1 1 -1], 
A=circul(a), B=circul(b), C=circul(c),
a={[A B]}, a={[a C]}, tr(a),
b={[C A]}, b={[b B]}, tr(b), a={[a b]},
c={[B C]}, c={[c A]}, tr(c), A={[a c]},  
return A,
end,

function: circul(c),
% get circulant matrix,
var n k a A, 
n=size(c), A=zeros(n+1), 
for var i=0:n, for var j=i:n, 
k=j-i, A[j][i]=c[k], 
if i<>j, A[i][j]=c[n-k+1], end, 
end, end, 
return A,
end,

Сведения по Фибоначчи последовательности

Числа Фибоначчи (Fibonacci):

Fn = Fn–1 + Fn–2,

где n>1, F0=0, F1=1, первые десять 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и 55. Порождение суммы трех членов называют иногда последовательностью Трибоначчи (Tribonacci).

Числа Лукаса: 2, 1, 3, 4, 7, 11.. получены обобщением предыдущего с иными начальными условиями 2 и 1.

Золотое сечение: Fn+1/Fn стремится к (1+√5)/2

Fn+1/Fn = (Fn+Fn–1)/Fn = 1 + 1/Fn/Fn–1

где x=Fn+1/Fn, при большом n Fn+1/Fn = Fn/Fn–1, отсюда

x2 – x – 1 = 0, корни a=(1+√5)/2=1.618.., b=(1–√5)/2=–0.618..,

положителен первый корень, к нему стремится отношение. В то же время отношение членов последовательности Лукаса стремится к золотому сечению 0.618.., для этой последовательности x2 + x – 1 = 0, знаки корней инверсны.

Формула Бине: В 1843 Binet выражает числа Фибоначчи и Лукаса формулами через золотое сечение

Fn = (an – bn)/(a – b), Ln=an + bn

Фибоначчи полиномы: В 1883 два математика (Catalan and Jacobsthal) ввели в рассмотрение не числа, а полиномы

fn(x) = xfn–1(x) + fn–2(x),

где n>1, f0(x)=0, f1(x)=1, тогда fn(1)=Fn. Причем отношение полиномов последовательности fn+1(x)/Fn(x) стремится к a(x)=(x+√(x2+4))/2. Есть аналог формулы Бине, где b(x) сопряжено с a(x).

При x=2icosh(z) имеем a(z)=iez, b(z)=ie–z, тогда

fn=in–1 sinh(nz)/sinh(z).

Полиномы Якобсталя (Джекобса) (Jacobsthal):

fn(x)=fn–1(x) + xfn–2(x),

где n>1, fn(1)=Fn, fn(2)=Jn (числа последовательности Якобсталя). Немецкий математик Эрнст Якобсталь - ученик Фробениуса и Шура (формы Шура), диссертация по вычетам.

Матрица Якобсталя вошла в перечень стандартных матриц IT++ библиотеки C++ для научных расчетов, наравне с C-матрицами и матрицами Адамара.

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

Кососимметрические теплицевы матрицы Якобсталя наиболее легко достраиваются до ортогональных

A =
1 e'
–e I + T

где I - единичная матрица. Следующий алгоритм дает решение для порядков 12 и 20.


A=hadamardc(12), 

A=?, X={A'*A}, mesh(X),

function: hadamardc(n),
var m e I T, m=n-1, T=jacobsthal(m), 
I=eye(T), T={I+T}, A=one(m), A={-1*A}, 
A={[A T]}, tr(A), e=one(m+1), 
A={[e A]}, tr(A), 
return A, 
end,

function: jacobsthal(m), 
var c ij s r m1 T, m1=m-1,
c=legendre(m), T=zeros(m),   
r=m-floor(m/4)*4,
for var i=0:m1, 
for var j=0:i-1, 
k=i-j, s=c[i-j],
T[i][j]=s, if r=3, s=-s, end,
T[j][i]=s, 
end, end, 
return T,  
end,

function: legendre(m), 
var c s m2, m2=floor(m/2), 
c=one(m), c={-1*c}, c[0]=0,   
for var i=1:m2, s=i*i, 
c[s-floor(s/m)*m]=1, end,
return c,
end,

Перестановкой столбцов данную структуру легко симметризовать, в таком случае нижний блок будет составлять ганкелева матрица символов Лежандра.

Симметричный случай теплицевой матрицы Якобсталя тоже несложен, на ее основе выписывается матрица Белевича

C =
0 e'
e T

она ортогональна лишь тогда, когда m – 1 представима в виде суммы двух квадратов, например, для m = 6. К 4k+1 относится 21, но это число - не простое. Поэтому матрица Белевича 22-го порядка не ортогональна.

Модифицированное правило Сильвестра

A =
I + С I – С
I – С – I – С

позволяет избавиться от 0 и перевести матрицу в класс с ±1.

Следующий алгоритм дает симметрическое решение для порядков 12 и 20.


C=belevitсh(6),  C=?, X={C'*C}, mesh(X),
A=hadamards(12), A=?, X={A'*A}, mesh(X), 

function: hadamards(n),
var m e I A B C, m=n/2, 
C=belevitсh(m), I=eye(C), 
A={I+C}, B={I-C}, 
A={[A B]}, tr(A), C={{-1*I-C}}, 
B={[B C]}, tr(B), 
A={[A B]}, tr(A), 
return A, 
end,

function: belevitсh(n),
var m e C T, m=n-1, 
if m=9, 
T=paley(), else, 
T=jacobsthal(m), 
end, C=one(m),  
C={[C T]}, tr(C), e=one(m+1), 
C={[e C]}, tr(C), C[0][0]=0,
return C, 
end,

function: jacobsthal(m), 
var c ij s r m1 T, m1=m-1,
c=legendre(m), T=zeros(m),   
r=m-floor(m/4)*4,
for var i=0:m1, 
for var j=0:i-1, 
k=i-j, s=c[i-j],
T[i][j]=s, if r=3, s=-s, end,
T[j][i]=s, 
end, end, 
return T,  
end,

function: legendre(m), 
var c s m2, m2=floor(m/2), 
c=one(m), c={-1*c}, c[0]=0,   
for var i=1:m2, s=i*i, 
c[s-floor(s/m)*m]=1, end,
return c,
end, 

function: paley(),
var a b c A B C,
a=[0 1 1], b=[-1 -1 1], c=[-1 1 -1], 
A=circul(a), B=circul(b), C=circul(c),
a={[A B]}, a={[a C]}, tr(a),
b={[C A]}, b={[b B]}, tr(b), a={[a b]},
c={[B C]}, c={[c A]}, tr(c), A={[a c]},  
return A,
end,

function: circul(c),
% get circulant matrix,
var n k a A, 
n=size(c), A=zeros(n+1), 
for var i=0:n, for var j=i:n, 
k=j-i, A[j][i]=c[k], 
if i<>j, A[i][j]=c[n-k+1], end, 
end, end, 
return A,
end,



Rambler's Top100