03.11.2017 admin

1.4. Матрицы Адамара-Мерсенна


Существуют два способа определения интересующих нас далее малоуровневых ортогональных матриц нечетных порядков, равных числам Мерсенна n = 2k–1.

Первый, алгоритмический, восходит к итерационному алгоритму Сильвестра, который надо, очевидно, модифицировать для того, чтобы работать с нечетными порядками. Он даст матрицы, которые назовем по праву их авторов, матрицами Адамара-Мерсенна.

Повторяя путь, пройденный Адамаром, опираясь на инварианты матриц Адамара-Мерсенна, можно дать общее не алгоритмическое их определение и расширить множество ортогональных матриц нечетных порядков, идущих через четверку. Такие более общие матрицы будем называть, для большей простоты, матрицами Мерсенна.

Базовых элементов здесь два, соответственно, итерационный алгоритм стартует на с 1, как у матриц Адамара основной ветви, а с нормированной D-матрицы третьего порядка с элементами {1, –1/2}, отрицательные элементы сосредоточены на диагонали.

Ориентируясь на желаемый вид матриц (структурный инвариант), переставим два первых столбца стартовой матрицы местами, см. на рис. 1., – строение нижнего правого угла отражает структуру матриц Адамара.



Рисунок 1. Диагональная D-матрица и матрица Адамара-Мерсенна


Пусть M – двухуровневая, как и матрица Адамара, матрица c элементами {a, –b}, a=1, 0<b<a.

Определение 1. Сопряженная по знаку матрица M* – матрица, элементы которой взаимно изменены по значениям уровней: элемент a заменен на –b, –b – на a.

Определение 2. Модифицированный алгоритм Сильвестра удвоения порядка дает [M,M;M,M*].

Очевидно, что в случае равенства a=b модифицированный алгоритм сводится к обычному алгоритму Сильвестра. Так как порядок получаемой при этом матрицы четен, нарастим его на единицу, не меняя, разумеется, состава элементов дополнительной каймы.

У нормализованных матриц Адамара кайма состоит из однородных по знаку элементов a или –a.

Это структурный инвариант, который для каймы матриц Адамара-Мерсенна, судя по матрице стартового порядка, выглядит иначе, как условие равенства количеств отрицательных –b и следующих за ними положительных a элементов, сосредоточенных вне элемента диагонали a. Найденный инвариант полностью детерминирует вид следующих матриц.

Положение 1. Матрица Адамара-Мерсенна M порядка n = 2k–1 порождается модификацией алгоритма Сильвестра с добавлением нормализованной каймы, условию ортогональности столбцов отвечает значение b=(q–(4q)1/2)a/(q–4), где q=n+1 (порядок матрицы Адамара).

Портреты двух последовательно вычисленных матриц Адамара-Мерсенна представлены на рис. 2. Для них можно построить построить инвариант в виде своей специфически приведенной m–нормы, позволяющий отличать их от остальных матриц. Игрою вездесущего случая в начале этих матриц можно рассмотреть стилизованную букву М.



Рисунок 2. Портреты матрица Адамара-Мерсенна 7-го и 15-го порядков


Дополнительный корень квадратичного уравнения, следующего из условия ортогональности столбцов, дает матрицу с большей величиной m-нормы, таким решением для b мы пренебрегаем.

Оба отмеченных выше варианта стартовых матриц, разумеется, эквивалентны. D-матрица третьего порядка относится к ненормализованным матрицам Адамара-Мерсенна, что не мешает строить с ее помощью нормализованные варианты более высокого порядка. Следующее наблюдение состоит в том, что перестановками не получить иных существенно различающихся между собой структур.

К принципиально важным бинарностям такого толка относятся, например, треугольники золотого сечения, из которых построены узоры Пенроуза. Две матрицы Адамара-Мерсенна третьего порядка образуют бинарный структурный базис, теперь уже, матричных элементов. Из них могут складываться неприводимые к одноэлементному базису составные объекты, получаемые замещением чисел {a, –b} матрицами.

Различие их со столь же малоуровневыми D-матрицами состоит в том, что с ростом порядка m–норма D-матриц растет почти также стремительно, как и у единичных матриц.

Этот показатель, m–норма, – инвариант классического алгоритма Сильвестра, ее он не изменяет, поэтому итерируемая им D-матрица третьего порядка не увеличивает своей нормы. Но у матриц Адамара-Мерсенна ввиду наращиваемой каймы этот показатель еще и падает, с ростом порядка уровень –b стремится к –1, а приведенная m–норма стремится к абсолютному показателю матриц Адамара, к 1.

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

Перед нами довольно сильное продолжение теории ортогональных матриц, но не единственное в своем роде, поскольку кратность порядков матриц Адамара четырем оставляет еще две вакансии. К ним мы и переходим.

Hide

Rambler's Top100