Кронекерово произведение. Его свойства.

Трудоемкость умножения произвольной матрицы A размерами на вектор равна . Эта оценка вряд ли может быть улучшена , так как она совпадает с числом элементов матрицы. Ситуация изменится, если умножение проводится на матрицу специального вида. К примеру, трудоемкость умножения диагональной матрицы на вектор равна . Бывает, что трудоемкость умножения зависит от размера дополнительной выделенной памяти. Например, трудоемкость умножения на матрицу перестановок равна при условии выделения дополнительно n ячеек памяти и если память не выделяется.

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

Пусть и - прямоугольные матрицы соответственно размеров и . Кронекеровым произведением называется матрица размеров следующего блочного строения . Приведем основные свойства кронекерова произведения матриц.

Свойство 1. Пусть и - прямоугольные матрицы соответственно размеров и , и существуют алгоритмы умножения векторов на эти матрицы с трудоемкостью равной соответственно и . Тогда, трудоемкость умножения вектора на матрицу не превосходит .

Доказательство. Вычислим трудоемкость умножения матрицы на вектор x, состоящий из nr компонент. Разобьем вектор x на n кусков, каждый длины r. По правилу блочного произведения матриц, для вычисления результата надо каждый из данных кусков умножить на матрицу B, а затем полученные векторы длины p складывать между собой с коэффициентами из матрицы A. Таким образом, для вычисления ответа потребуется n умножений на матрицу B и p умножений на матрицу A. Сложность операции умножения получается равной .

В общем случае, трудоемкость умножения матрицы на вектор пропорциональна размерам матрицы. В частности, если матрицы A и B произвольные, то и . Тогда сложность умножения матрицы на вектор, не больше , что может быть существенно меньше чем .

Свойство 2. Пусть и , тогда .

Доказательство следует из правила блочного произведения матриц.

Свойство 3. Пусть существуют и , тогда .

Доказательство. По свойству 1 имеем . Из полученного равенства вытекает требуемое утверждение.

Свойство 4. .

Доказательство следует из определения операций кронекерова произведения и транспонирования матриц.