БПФ и кронекерово произведение.

Для примера рассмотрим случай, когда n=2m. Переставим строки матрицы дискретного преобразования Фурье с четными номерами на верх. Данное преобразование эквивалентно умножению слева матрицы дискретного преобразования Фурье на матрицу перестановок вида . Полученную матрицу разобьём на блоки размером . В левом верхнем блоке на пересечении i-ой строки и j-го столбца будет расположен элемент равный . Таким образом, левый верхний блок матрицы равен . Рассмотрим теперь правый верхний блок матрицы . Так как на пересечении i-ой строки и j-го столбца располагается элемент равный , то этот блок равен . Строение нижних блоков несколько сложнее. Элемент левого нижнего блока, расположенный на пересечении i-ой строки и j-го столбца равен , и отличается от элемента матрицы множителем, зависящим от номера столбцы. Обозначим через диагональную матрицу . Левый нижний блок матрицы равен . . Элемент правого нижнего блока, расположенный на пересечении i-ой строки и j-го столбца равен , и, следовательно, правый нижний блок равен . Тем самым показано равенство . Непосредственной проверкой нетрудно убедиться в справедливости следующего равенства , где - единичная матрица k – го порядка. Заметим, что . Следовательно, матрица дискретного преобразования Фурье представляется в виде .

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

Если n является степенью двойки , то применяя данную формулу k раз получим, что трудоемкость вычисления образа дискретного преобразования равна . Обобщение указанной схемы на произвольный случай будет приведено ниже в лемме 1.