Матрица 
называется матрицей k – мерного дискретного преобразования Фурье. Эти матрицы естественным образом возникают при умножении многочленов от многих переменных. Согласно свойству 1 (кронекерова произведения) это преобразование легко сводится к последовательному выполнению одномерных дискретных преобразований. Многократным применением свойства 1 кронекерова произведения матриц получим, что трудоемкость умножения на матрицу k-мерного дискретного преобразования Фурье равна 
, где 
- трудоемкость умножения на 
и 
. Хотя этот способ самый простой, но в общем случае не самый лучший.
Пусть рассматривается k – мерное дискретное произведение Фурье порядка 
, 
при i=1,…,k, причем 
, 
, и . Тогда применяя указанный подход, учитывая, что 
, выводим общую оценку трудоёмкости k-мерного преобразования Фурье 
.
Трудоемкость можно понизить, если вначале воспользоваться леммой 1 и представить 
, а затем, используя свойства кронекерова произведения разложить k-мерное преобразование в произведение матриц 
. Трудоемкость умножения на матрицу перестановок 
и на диагональную матрицу 
не более 2n. Общая трудоемкость умножения получается равной 
.
