Участник:Бугаков Юрий/Построение матрицы Адамара произвольного размера

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

1.1.1 Общее описание алгоритма

Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков Жаком Адамаром (1865-1963). Их применение в науке и технике посвящены тысячи публикаций. Они предоставляют эффективные возможности для организации хранения, обработки и передачи информации.

Квадратная матрица Н порядка n с элементами ±1 называется матрицей Адамара, если выполняется условие

$H_n\,H_n^T = n\,E_n$

Нетрудно показать, что различные строки матрицы Адамара попарно ортогональны. Также можно увидеть из определения, что n четно и любые две строки совпадают ровно в n/2 позициях и различаются в остальных.

Матрицу Адамара можно определить эквивалентным образом:

$H_{n} = H_1\otimes H_{n-1}$

$\begin{align} H_1 = &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

где $\otimes$ представляет собой тензорное произведение, то есть

$H_{n} = \begin{pmatrix} H_{n-1} & H_{n-1}\\ H_{n-1} & -H_{n-1}\end{pmatrix}$

$\begin{align} H_1 = &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок n матрицы Адамара при n ≥ 3 может быть лишь четным. Более того, при n ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли n, кратного 4, существует матрица Адамара порядка n? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).

Часто размерность матрицы Адамара считают равной степени 2 и нормализируют её. Определение принимает следующий вид:

Матрицей Адамара H_n эта матрица размера 2ⁿ × 2ⁿ, для которой справедливо равенство

$H_n = H_{1} \otimes H_{n-1}$

$\begin{align} H_1 = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

где $\otimes$ представляет собой тензорное произведение.

Также, мы можем вычислить значения каждого элемента матрицы Адамара $H_n$. Для этого представим порядковые номера k и l элемента $h_{kl}$ в виде двоичного разложения

$k = \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0$

и

$l = \sum^{m-1}_{i=0} {l_i 2^i} = l_{m-1} 2^{m-1} + l_{m-2} 2^{m-2} + \cdots + l_1 2 + l_0$

где k_j и l_j коэффициенты двоичного разложения чисел k и l (1 или 0).

Тогда каждый элемент матрицы Адамара $H_n$ имеет вид

$h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}$

Представим некоторые частные примеры матриц Адамара:

$\begin{align} H_0 = &+1\\ H_1 = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

$\begin{align} H_2 = \frac{1}{2} &\begin{pmatrix}\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\end{pmatrix}\\ H_3 = \frac{1}{2^{\frac{3}{2}}} &\begin{pmatrix}\begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1\\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1\\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1\\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1\\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{array}\end{pmatrix}\\ \end{align}$

1.2 Математическое описание алгоритма

Исходные данные: положительно определённая симметрическая матрица $A$ (элементы $a_{ij}$).

Вычисляемые данные: нижняя треугольная матрица $L$ (элементы $l_{ij}$).

Формулы метода:

$\begin{align} l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align}$

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление $\frac{1}{l_{ii}}$ и затем умножение на него всех (видоизменённых) $a_{ji}$ . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.