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

Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.

Сюда тоже запилим
Последовательный алгоритм
Последовательная сложность	$O(n^3)$
Объём входных данных	$\frac{n (n + 1)}{2}$
Объём выходных данных	$\frac{n (n + 1)}{2}$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(n)$
Ширина ярусно-параллельной формы	$O(n^2)$

Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (разделы 2.4, 2.5)

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

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

Матрица Адамара $H$ порядка $n$ представляет собой матрицу размера n×n из элементов $+1$ и $-1$, такую, что: $H \cdot H^T = n \cdot E_n,$ где $E_n$ — это единичная матрица размера n×n.

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях: 1) умножение строчки или столбца на −1; 2) перестановка строчек или столбцов местами.

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

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