ОРТОГОНАЛЬНЫЕ МАТРИЦЫ



Понятие матрицы, прямоугольной таблицы чисел, тесно соседствует с понятием системы векторов, координаты которых составляют либо ее столбцы, либо строки. Для большей простоты ортогональной матрицей называется квадратная матрица, у которой транспонированная и обратная к ней матрицы тождественны, т.е. AA'=I, I – единичная матрица.

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

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

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

Ортогональные матрицы столь же фундаментальны уже потому, что их порядок – число, слагающее теорию чисел. Существует довольно очевидное соответствие между числами n и ортогональными матрицами размерности n, т.е. ортогональными базисами. Или пространствами. Понятия числа и пространства – фундаментальны, не сводимы друг к другу. Но они могут отвечать друг-другу. Это объекты из разных миров, и одно может быть характеристикой другого. Матрицы, при их размерах, смотрятся даже более информативными источниками, чем числа. При всем том, эти соотносящиеся друг с другом объекты неудобны для исследователей чисел или матриц, поскольку оба этих направления достаточно глубоки и требуют в своем обозрении и манипуляциях с ними разных знаний и навыков.

Теория чисел знаменита своими древними, как Сфинкс, загадками-теоремами. Теория матриц начала складываться в отчетливое направление относительно недавно – с выходом в свет монографии Гантмахера в середине прошлого века. До него первичную работу проделал Дж. Сильвестр. Некоторые результаты теории матриц получены уже в эпоху компьютеров, это совсем не длительный период времени. Справочник Гантмахера с момента его выхода дополняли разные более или менее фундаментальные труды, можно указать на несколько книг, в особенности, Джонсона. Но и Галуба, Воеводина, Беллмана, Уилкинсона и Райнша и др.

Тем не менее, некоторые сведения по построению ортогональных матриц до сих пор не попали в справочники по теории матриц, а фигурируют в курсах разрозненных дисциплин, например, в комбинаторике, что вызывает недоумение. В самом деле, а что может быть первичнее, в теории матриц, чем понятие ортогональности? И почему ортогональные матрицы трактуются вне этих справочников? Белевич, дополнивший теорию матриц Адамара, описывал их в статьях по электрическим схемам и трансформаторам. Тематика не выбирает ученых по принципу, в какой области они работают. Но рано или поздно необходимость в подведении итогов назревает. Отчасти это и делали уже в компьютерную эпоху, тоже разные специалисты. Беллман – известен как специалист по теории управления и матрицы для него – побочный материал, тем не менее, он написал заметный прикладной обзор.

Ортогональных матриц не то, чтобы много, они образуют континуальные множества, образуемые непрерывным поворотом ортогонального базиса в n-мерном пространстве. На этих множествах, тем не менее, есть матрицы более или менее интересные в некотором контексте.


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

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

Квазиортогональной (ортогональной матрицей в широком смысле этого слова) можно называть матрицу, построенную на системе ортогональных векторов, она ортогональна в узком смысле после ортонормирования.

МИНИМАКСНЫЕ МАТРИЦЫ


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

М-матрицы, в широком смысле слова, это матрицы с ортогональными вектор-столбцами или строками, являющиеся таковыми после нормирования строк или столбцов. Не теряя общности, в дальнейшем будем рассматривать матрицы с ортогональными вектор-столбцами, одинаково нормированными, т.е матрицы M порядка n, удовлетворяющие следующему равенству

M'M=μ2I,



где I – единичная матрица, μ – норма столбцов (весовой коэффициент).

Важнейшими представителями M-матриц с μ2 равными n и n–1 являются матрицы Адамара и Белевича (С-матрицы, conference-matrices): матрицы с элементами {1, –1} и {1, 0, –1} соответственно, причем нулевые элементы расположены по диагонали. Максимум абсолютного значения элементов m (m-норма) обоих матриц связан с весовым коэффициентом простой зависимостью m=1/μ.

Приведенная норма m=n1/2m, которая для матриц Адамара принимает минимально возможное у М-матриц значение m=1. Приведенная m-норма матриц Белевича больше единицы, но с ростом порядка n стремится к ней, принимая минимально возможное у М-матриц значение на порядках, отличных от порядков, на которых существуют матриц Адамара. Как видно, у этих матриц нет конкурентов, но дело в том, что они не всегда существуют.

Матрицам Адамара и Белевича присуще два качества: минимальная m-норма и малое количество уровней – значений их элементов.

Второе качество, оно также экстремально низкое у матриц Адамара. Поэтому, вводя обобщающее понятие, будем относить к M-матрицам также варианты, оптимальные по m-норме при заданном количестве уровней, т.е. матрицы, оптимальные на желаемой структуре. Как правило, это матрицы, локально-оптимальные по критерию минимума m-нормы, т.е. можно руководствоваться в классификации только этим селективным критерием.

Гипотеза Адамара о кратности порядков выделенных им минимаксных ортогональных матриц числу 4, закладывает основы теории соответствия чисел и ортогональных базисов. Напомним, что последовательности чисел 4k+1 и 4k+3 (4k–1) ввели в научный обиход Ферма и Эйлер. Ферма утверждал, что всякое простое число вида 4k+1 может быть представлено в виде суммы двух квадратов, причем единственным образом (простые числа вида 4k+3 исключены). Критерий Эйлера о разложимости n–1 на сумму двух квадратов входит в проверку необходимых условий существования матриц Белевича порядков n=4k+2.

Минимаксные ортогональные матрицы с минимальным числом уровней дают, в зависимости от остатка r деления порядка n на 4, четыре случая:

♦ r = 0 – матрицы Адамара (H), включая матрицы последовательности Сильвестра;
♦ r = 1 – матрицы Ферма (F), включая матрицы порядков, равных числам Ферма;
♦ r = 2 – матрицы Эйлера (E) и Белевича (С) с исключениями на основе критерия Эйлера;
♦ r = 3 – матрицы Мерсенна (M), включая матрицы порядков, равных числам Мерсенна.

В M-матрицы входят множества H, F, E (С) и M, в которых, как будет показано, последовательности Сильвестра и Мерсенна являются системообразующими. Оценки плотности охвата порядками матриц числовой оси питаются, соответственно, сходными гипотезами: гипотеза Адамара (перенос свойств матриц порядков последовательности Сильвестра на H), гипотеза Балонина (перенос свойств матриц порядков последовательности Мерсенна на М). Получается общая, для числовой оси, теория минимаксных ортогональных базисов.

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

S2n=
  Sn  
  Sn  
 Sn 
 –Sn 


где S1=1.

Подводя итог. Важными представителями М-матриц являются матрицы Адамара и Белевича. В самом общем случае мы заинтересованы получать решения для любого порядка n, четного или нечетного, все равно. Уровни M-матриц не обязательно равны ±1 или 0, и они не всегда целочисленны: еще Кумер предложил рассматривать обобщенные целые, устроенные наподобие комплексных, но с целыми или иррациональными образующими, взятыми вместо корня из –1, вида a+bsqrt(2).

Множество M-матриц состоит, в общем, из подмножеств матриц, из которых двухуровневые адамаровы H-матрицы и трехуровневые C-матрицы изучены хорошо, а оставшиеся матрицы нечетных и некоторых пропущенных среди C-матриц четных порядков изучены недостаточно полно. Учитывая связь C-матриц с теорией чисел, это косвенное исследование области, в которой получение новых результатов традиционно сложно. Вакантные пропуски среди матриц Белевича отвечают некоторым нетривиальным объектам теории чисел, поэтому их замещения в области матриц интересны.

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

ПРАВИЛЬНЫЕ МАТРИЦЫ


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

D=(n–1)/2.


Договоримся называть структуры, повторяющие логику построения латинских квадратов на усеченном числом уровней множестве элементов, правильными.

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

Дальнейшее увеличение коэффициента n вызывает к жизни эффект, известный в теории нелинейных систем: если возрастание числа уровней рассматривать, как бифуркацию, существует критическая точка, когда состояние системы оценивается как хаотическое. Уровневая структура разрушается у матрицы уже 13-го порядка.

ДИАГРАММА МИРОНОВСКОГО


Диаграмма Мироновского показывает зависимость приведенных умножением на sqrt(n) m-норм от порядка n. У матриц Адамара m-норма оценивается как 1/sqrt(n), приведенная норма минимально возможная, она равна 1. Это нижняя оценка нормы.

У матриц Белевича m-норма оценивается как 1/sqrt(n-1), приведенная норма заведомо больше минимально возможной, адамаровой, но стремится к 1 с ростом порядка. Довольно очевидно, что чем меньше дисперсность абсолютных величин элементов М-матриц, тем меньше приведенная m-норма.



Диаграмма Мироновского – зависимость приведенной m-нормы от порядка


Показатель, отражающий стремление M-матрицы походить на адамарову, – инвариант преобразования (удвоения порядка) Сильвестра. Все матрицы, связанные преобразованием Сильвестра, имеют одну и ту же m-норму.

Таким образом, соответствующий алгоритм удвоения порядка отражает перенос m-норм вправо (это важно), а сходное преобразование C-матриц в адамаровы – вправо и вниз, до 1.

ГИПОТЕЗА БАЛОНИНА


На экспериментально построенной диаграмме Мироновского хорошо видно, что помимо полочки снизу просматривается ограничение падения амплитуд графика m-норм. Предположение о том, что приведенная норма высокоуровневых M-матриц не падает до 1, высказана Балониным Н.А.

Гипотеза Адамара. Согласно этой гипотезе для всех порядков n=4*k ( кратных 4: 4, 8, 12, 16, 20, ..), существуют адамаровы матрицы.

Гипотеза Балонина. Согласно этой гипотезе для всех порядков n=3+4*k (3, 7, 11, 15, 19, ..), существуют матрицы типа Мерсенна (М-матрицы с уровнями 1, –b).

Иными словами, для матриц порядков n=3+4*k аналогом последовательности Сильвестра является последовательность Мерсенна (модифицируется правило построения матриц высокого порядка из матриц низкого порядка), положения (гипотезы) и в том и в другом случаях расширяют множество ортогональным матриц, относительно величин уровней которых 1, -1 и 1, –b можно высказаться определенно, и не более того.

Гипотеза Балонина о приведенной норме. Приведенные m-нормы структурированных (уровневых) M-матриц типа Адамара, Белевича, Мерсенна с ростом n стремятся к 1, предположение (гипотеза) состоит в том, что для остальных минимаксных матриц это не так, есть иной предел b=9/8 (оптимистичная оценка, полочка).

У отдельных представителей матриц m может приближаться к 1, но с ростом порядка всегда найдутся "особо плохие", в этом смысле, матрицы. Не все матрицы приближаются к адамаровым, всегда будут отклонения, и первой такой неструктурируемой матрицей является M13.

Всего существует 4 типа M-матриц: A,B,C,D, где A – адамаровы, C – матрицы Белевича, B (и можно добавить D, учитывая отличие порядков по модулю 4, но тогда опускаются пропуски среди матриц Белевича) – остальные матрицы, деление пока весьма условное. Положение, высказанное Мироновским, подтвердилось – между матрицами порядков 3 (mod 4) и 1 (mod 4) существует такая же разница, как между матрицами Адамара и Белевича (C-матрицами).

Казалось бы естественно предположить обратное, что приведенная m-норма M-матриц с ростом порядка убывает. Так оно и есть, но это касается лишь регулярных структур с относительно небольшим числом уровней. Если матрицы "хаотические", то показатель дисперсности их элементов не убывает, он стабилизируется на некотором уровне, назовем его b-полочка.

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

Косвенное доказательство связано с известными в теории пропусками C-матриц. В самом деле, рассмотрим M-матрицу вдвое меньшего (нечетного) порядка, чем четный порядок C-матрицы. Для порядков, кратных четырем, то есть, для матриц Адамара, эту роль играют сами C-матрицы.

Преобразование Сильвестра работает на перенос приведенной нормы вправо. Так как этот показатель – инвариант преобразования Сильвестра, при гарантированном уменьшении m-нормы и стремлении этого показателя к 1, с увеличением n можно было бы найти матрицу, лучшую, чем C-матрица. А это невозможно, поскольку С-матрицы существуют не всегда, и это известно определенно.

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

ОЦЕНКА КРИТИЧЕСКОГО УРОВНЯ НОРМЫ


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

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

Все последующие матрицы, хотя и индивидуальны, подвержены этому правилу. Оценивание критического значения приведенных норм важно для построения итерационных алгоритмов поиска M-матриц. Если приведенная норма достигла своего минимально возможного значения, искать более оптимальную матрицу бесполезно.

АЛГОРИТМ ПОИСКА M-МАТРИЦ


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



Итерационный алгоритм поиска структуры и параметров M-матриц


В качестве стартового приближения полезно брать теплицевы структуры с конечным числом уровней. Таковой является, например, матрица Гильбера с элементами Aij=m/(i-j) и единицами на диагонали.

Эффективность итераций зависит от сортировки столбцов по признаку первенства наиболее изменяемых – это подталкивает вращение ортов. Коэффициент сжатия элементов полезно последовательно ослаблять, итерационно увеличивая порог функции насыщения

pk=apk–1+(1–a),


где a<1 – параметр инерции процесса, pk – порог ограничения амплитуды элементов матрицы относительно максимального коэффициента (текущего значения m-нормы).

Алгоритм находит отмеченные ранее матрицы 3 и 5 порядков, матрицы Адамара 12 и 20 порядков (с чего началась тема), C-матрицы Белевича, претенденты на пропуски в их последовательности – при подходящем выборе начальных условий.

M-матрица в этом ее определении становится продуктом итерационного процесса, и для ее анализа можно привлекать термины теории динамических систем, в том числе, понятия бифуркации, аттрактора и хаотического аттрактора.

В процессе последовательных бифуркаций скалярная динамическая система удваивает количество уровней. Матрица – это не скаляр, а вектор состояния системы варьируемой размерности. Соответственно, ее элементы занимают не один (как скаляр), а несколько фиксированных уровней.

Теория динамических систем предсказывает последовательный рост числа уровней аттрактора и фрактальную картину распределения. Периодические сокращения числа уровней для матриц Адамара и Белевича аналогичны окнам после критической точки на диаграмме Фейгенбаума.

МЯГКАЯ ФУНКЦИЯ НАСЫЩЕНИЯ


Недостаток и, одновременно, достоинство итерационного алгоритма состоит в том, что ее продуктом может являться локальный оптимум, который интересен сам по себе – именно так обнаруживаются побочные субоптимальные регулярные структуры.

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


Функция коррекции элементов матрицы при разном сжатии p=0.5..1.



АНАЛИТИЧЕСКОЕ ПОСТРОЕНИЕ M-МАТРИЦ


Алгоритм поиска целочисленных ортогональных матриц сводится к рассмотрению возможных значений знаков циклических по абсолютным значениям величин элементов структур, насчитывающих (n–1)/2 потенциальных диагоналей. Для матриц третьего порядка это всего одна (как у C-матриц) диагональ ±a, значение a не равно 0.

M=
a
b
b
b
 ±a 
 ±b 
b
 ±b 
 ±a 


Первая строка и первый столбец матрицы знаконормированы. По абсолютным значениям перед нами неправильный латинский и магический квадрат, рассматриваемый на усеченном множестве из (n+1)/2 элементов, чьи суммы по строкам и строкам равны между собой.

Условие ортогональности первых двух столбцов: ab±ab±bb=0 или 2a–b=0 (при a возьмем везде плюс, при b – минус), откуда b=2a или a=1, b=2. Элементарными преобразованиями итоговая матрица приводима к циклической

M=
 –1 
2
2
2
 –1 
2
2
2
 –1 


Суммы элементов строк и столбцов у этой матрицы постоянны и равны 3.

С матрицей 5-го порядка все тоже очень интересно, циклическая по абсолютным значениям элементов матрица имеет вид

M=
a
c
c
c
b
b
 ±a 
 ±c 
 ±c 
 ±c 
c
 ±b 
 ±a 
 ±c 
 ±c 
c
 ±c 
 ±b 
 ±a 
 ±c 
c
 ±c 
 ±c 
 ±b 
 ±a 


Условие ортогональности первых двух столбцов приводит к уравнению

ba±ac±cc±cc±cb=0,


пусть ±cc±cc уйдет в 0 (как самое большое), cb компенсируется суммой cb=ba+ac, так как a – самое малый уровень. Из ортогональности первого и третьего столбцов имеем второе уравнение

ca±bc±ac±cc±cb=0,


достаточное для нахождения отношений всех уровней: предположим, что ca±ac=0, отсюда сразу получаем с=2b и, с учетом первого уравнения, b=3a/2.

Циклическая целочисленная матрица имеет уровни a=2, b=3, c=6 и принимает вид

M=
2
6
6
 –6 
3
3
2
6
6
 –6 
 –6 
3
2
6
6
6
 –6 
3
2
6
6
6
 –6 
3
2


Суммы элементов строк и столбцов у этой матрицы постоянны и равны 11.






Rambler's Top100