Матрицы Адамара

Размещено на http://www.allbest.ru/

Матрицы Адамара

Сергеев Александр Эдуардович

В 1893 году французский математик Ж.Адамар поставил вопрос: пусть дана матрица фиксированного порядка с коэффициентами не превосходящего по модулю данного значения, тогда какое наибольшее по модулю значение может принимать детерминант этой матрицы? Адамар полностью решил этот вопрос в случае, когда коэффициенты матрицы- комплексные числа и выдвинул соответствующую гипотезу в случае, когда коэффициенты матрицы- вещественные числа, по модулю равные единице. Такие матрицы, удовлетворяющие гипотезе Адамара, стали называть матрицами Адамара, их порядок равен четырём и неизвестно, является ли это условие достаточным для их существования. В статье рассматривается естественное обобщение матриц Адамара над полем вещественных чисел, они существуют для любого порядка. В работе предлагается алгоритм построения обобщённых матриц Адамара, и он иллюстрируется на числовых примерах. Также вводится понятие константы для данного натурального числа, вычисляются значения этой константы для некоторых натуральных чисел и показываются некоторые приложения константы Адамара для оценок сверху и снизу модуля определителя данного порядка с произвольными вещественными коэффициентами и эти оценки в некоторых случаях лучше известных оценок Адамара. Результаты статьи связываются с результатами Кона по величине детерминантов матриц с вещественными коэффициентами, не превосходящими по модулю единицы

Ключевые слова: МАТРИЦА АДАМАРА, НЕРАВЕНСТВО АДАМАРА, КОНСТАНТА АДАМАРА, ОБОБЩЕННАЯ МАТРИЦА АДАМАРА, ГИПОТЕЗА АДАМАРА

Матрицы Адамара и некоторые их обобщения

В 1893 году французский математик Адамар поставил такой вопрос: пусть А будет nxn матрица с коэффициентами не превосходящими по модулю число M>0. Какое наибольшее по модулю значение может принимать детерминант detA матрицы А?

Адамар полностью решил этот вопрос в случае, когда коэффициенты матрицы А комплексные числа и выдвинул известную гипотезу в случае вещественных коэффициентов матрицы А.

Обозначим символом ||д|| Евклидову норму вектора д=() т.е.

||д|| =

Тогда справедлива теорема Адамара [1].

Теорема 1. Пусть А - комплексная nxn матрица с линейно независимыми колонками . Тогда

(1)

где - транспонированная матрица сопряжённой , и равенство в (1) достигается только если матрица диагональная.

Следствие 1. Пусть А=() есть комплексная матрица с ||1, тогда |det(A)| и равенство достигается только если ||=1 для всех индексов 1 i, j n и = - единичная матрица.

Следствие 2. Пусть А=() есть комплексная nxn матрица с ||М, |det(A)| и равенство достигается, если ||=М для всех индексов 1 i, j n и выполняется равенство =.

Определение 1. Комплексная nxn матрица А=() называется матрицей Адамара порядка n, если =1 и = .

Теорема 2 (Адамар) Для любого натурального существует комплексная матрица Адамара А порядка .

Легко проверить, что матрицей Адамара порядка является следующая матрица А:

A=

где , 0 k n-1, - комплексные корни n-ой степени из единицы, тогда = .

Определение 2. Вещественная nxn матрица А=() называется матрицей Адамара порядка n, если и = .

Возникает вопрос о существовании вещественных матриц Адамара любого порядка . Для такой матрицей Адамара является матрица

Матрица 4х4 вида как легко можно проверить также является матрицей Адамара

И вообще, как заметил Сильвестр, если - матрица Адамара порядка есть также матрица Адамара. Однако вещественных матриц Адамара порядка 3, 5, 6, 7, 9, 10, 11… не существует, так как справедлива следующая теорема Адамара:Ю

Теорема 3. Пусть А=() - вещественная матрица Адамара порядка > 2. Тогда делится на 4.

Учитывая этот результат, Адамар сформулировал свою знаменитую гипотезу:

Гипотеза Адамара (1893): Для каждого натурального , делящегося на 4, существует вещественная матрица Адамара порядка .

Существуют различные методы построения вещественных матриц Адамара порядка для некоторых бесконечных серий натуральных чисел делящихся на 4 [2], однако они не позволяют доказать гипотезу Адамара. Наименьшим порядком, кратным 4, для которого матрица Адамара неизвестна является (?)

Если любую строку или любой столбец матрицы Адамара умножить на -1, то получим другую матрицу Адамара того же порядка. Умножая строки и столбцы матрицы Адамара на -1 мы можем получить нормализованную матрицу Адамара, первая строка и первый столбец которой состоит только из положительных единиц.

Если переставить строчки или столбцы матрицы Адамара, то получим опять матрицу Адамара.

Матрицы Адамара, получаемые друг из друга многократным применением перестановок строк или столбцов и умножением строк или столбцов на -1 называются эквивалентными.

Пусть А=() - матрица размера mxm и В=() - матрица размера nxn. Тогда Кронекеровским прямым произведением АВ матрицу А и В называется матрица размера х следующего вида:

АВ=

Справедливо утверждение: Кронекерово произведение двух матриц Адамара является матрицей Адамара. Действительно, используя свойства Кронекерова произведения матриц, получаем для матриц А и В порядков соответственно равенство:

(АВ) = (АВ) = () (B) = =

что и доказывает утверждение.

Отсюда следует, что если существует матрицы Адамара порядков , то существует матрица Адамара порядка .

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

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

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

Прямое вычисление показывает, что

матрица адамар слагаемое

и значит = = 4. Отсюда вытекает, что , в чем можно убедиться, если мы будем расщеплять определитель 1 матрицы 4-го порядка по какой-нибудь строке и равенство достигается для матрицы Адамара

Принимая во внимание неравенства Адамара, оценивающие величину модуля detA через длины строк (столбцов) матрицы А=() порядка :

(2)

(3)

Получаем из (2) и (3) следующие оценки для констант Адамара:

Анализируя ±1 матрицы 5-го порядка получаем следующую обобщенную матрицу Адамара :

Следовательно =|det|=48. С помощью упорядоченных компьютерных вычислений были найдены следующие обобщенные матрицы Адамара порядка 6, 7, 9, 10:

Используя полученные матрицы, получаем константы Адамара

Значение константы имеем из ранее приведённой формулы для матрицы Адамара Мы видим, что значение констант… Адамара быстро растут с увеличением…

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

Пусть , , тогда рассмотрим матрицу

Имеем det=(-1)[()()-2()]. Ясно, что для максимальной detнадо взять значения (можно взять и ), получим в итоге две обобщенные матрицы Адамара 3-его порядка:

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

Взяв , получим матрицу Адамара 4-го порядка, так как det=16.

Возьмем полученную матрицу и построим с помощью соответствующего окаймления обобщенную матрицу Адамара 5-го порядка:

Взяв , получим обобщенную матрицу Адамара 5-го порядка, так как det= 48.

Возьмем полученную матрицу и построим с помощью окаймления обобщенную матрицу Адамара порядка 6:

;

,, получим обобщенную матрицу Адамара , так как в этом случае det=160.

Окаймляя полученную матрицу строкой

и колонкой , получаем обобщенную матрицу Адамара , так как det=576:

Неизвестно всегда ли указанный алгоритм дает обобщенную матрицу Адамара.

Константа Адамара позволяет вычислить наибольшее возможное число положительных слагаемых при раскрытии определителя -го порядка по его определению в виде алгебраической суммы ! слагаемых, если элементы определителя вещественные числа справедлива формула:

Используя, полученные ранее результаты, получаем:

Отсюда имеем не строго убывающую последовательность чисел:

Возникает вопрос существует ли предел дроби и чему он равен?

= ?

Пусть А - nxn матрица с вещественными коэффициентами и - наибольшее положительное слагаемое среди алгебраических слагаемых в detA, а - наименьшее отрицательное слагаемое, тогда выполняется неравенство:

|detA| (4)

Неравенство (4) для некоторых матриц дает более точную оценку, чем неравенства Адамара (2) и (3). Например, для матрицы по формулам Адамара , а по соотношению (4) имеем:

и так как , то это точная оценка!

Пусть А=() - вещественная матрица порядка , введем следующие функции, зависящие от порядка матрицы А:

Е. Коном [3] доказано, что выполняются соотношения

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

Кроме того, Адамар доказал [4], что справедливо неравенство:

(5)

причем равенство в (5) выполняется для данного натурального только если существует матрица Адамара порядка .

Теорема 4. Пусть Н - матрица Адамара порядка , имеют подматрицу Адамара М порядка . Тогда .

В то же время приведенные выше (ранее) примеры показывают, что обобщенная матрица Адамара порядка может содержать в качестве подматрицы матрицу Адамара порядка .

С помощью компьютерных вычислений, разными авторами вычислены для небольших значения функции

Из приведенных примеров можно заметить индексное свойство обобщенных матриц Адамара: они обладают свойством нормальности . Однако неизвестно будет ли каждая обобщенная матрица Адамара обладать этим свойством, т.е. быть нормальной матрицей.

В [7] дана хорошая нижняя граница для детерминанта обобщенной матрицы Адамара А порядка:

(6)

В этой статье обобщенная матрица Адамара называется максимальной детерминантной матрицей.

Пусть А - обобщенная матрица Адамара порядка 5, приведенная нами ранее в примерах, тогда |det(A)|=48, а из неравенства (6) получаем

т. е. это хорошая нижняя оценка.

В заключении отметим, что задача построения матриц Адамара и обобщенных матриц Адамара любого порядка вещественных чисел, требуется составить из них матрицу А , имеющую максимальный |det(A)|.

Например, если

то матрица А= имеет максимальный detA=412 и найти такую матрицу не сложно. Если же взять 16 чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, то найти 4х4 матрицу из этих чисел с максимальным детерминантом гораздо сложнее:

А=

Никакого алгоритма для решения этой задачи, исключая матрицы Адамара, пока не найдены. Другие обобщения матриц Адамара для нечетных порядков содержатся в [10] и [9].

Литература

1. J. Hadamard, Resolution d'une question relative discriminants, Bull des Sci. Math. 17(1893), 240-246.

2. Ю. В. Таранников, Комбинаторные свойства дискретных структур и приложения к криптологии, М. МУНМО, 2011.

3. J.H.E. Cohn, On the value of determinants, Proc, Amer, Math. Soc, 14 (1963), 581-588.

4. S.S. Again, Hadamare matrices and their Application, Aecture Notes in Mathematics, 1168, springer-Verlag, 1985.

5. J.H.E. Cohn, Hadamar matrices and some generalizations, Amer. Math. Monthly 72 (1965), 515-518.

6. K.J. Haradan, Hadamar Matrices and their Applications, Princeton University Press, 2007.

7. R.R. Brent, J.H. Osborn, General lower bounds of maximal determinants of binary matrices. Preprint, 2012.

8. В.М. Сидельников, Теория кодирования, М. Физматлит, 2008.

9. Н.А. Болонин, Л.А. Мироновский, Матрицы Адамара нечётного порядка// Информационные управляющие системы, 2008, N3, C.46-50.

10. Н.А. Болонин, М.Б. Сергеев, Л.А. Мироновский, Вычисление матриц Адамара-Мерсенна// Информационные управляющие системы, 2012, N5, C. 92-94.

Размещено на Allbest.ru