Дискретно-непрерывная математика (стр. 104 )

4.6. Разложения логаческих определителей второго рода

Разложения ЛО с ограничениями второго рода на меньшие ЛО получа­ются аналогично соответствующим у ЛО с ограничениями первого рода.

Определение 4.5. Пусть - произвольный М × Р- ЛО (4.24). ЛО, полу­ченный из вычеркиванием k-гo столбца и сдвигом области значений параметра рr в (4.23) на единицу влево, называется логическим дополне­нием элемента в и обозначается Таким образом,

(4.29)

Здесьозначает усеченную разность, т. е.

используемую вместо обычной разности для того, чтобы область значе­ний рr не стала отрицательной.

Теорема 4.4. ЛО вида (4.24) можно разложить по любому j-му столбцу, представив его как дизъюнкцию БЛ сумм всех возможных элементов этого столбца и их логических дополнений

(4.30)

Доказательство. Распишем ЛО в виде

Вынесем за знаки не зависящие от q слагаемые

Сравнив вторые слагаемые скобок с выражением (4.29), получим (4.30).

Разложение ЛО по столбцу (4.30) можно обобщить. Пусть - про­извольный М × Р-ЛО (4.24) для матрицы (4.1). Рассмотрим под­матрицы Вr и матрицы А, образованные множеством из r произвольных столбцов А и дополнительным множеством из Р—r остальных столбцов. Определение (4.24) ЛО матрицы A вклю­чает ограничения (4.23) на числа элементов из различных строк А. Отсюда - ограничения на числа элементов из различных строк подматриц Вr и Пусть- число элементов i-й строки Вr, включаемых в выражение ЛО (4.24), а - аналогичное число дляЯсно, что

(4.31)

где pi, i = 1,.. . ,M, - число элементов i-й строки всей матрицы А, вклю­чаемых в выражение ЛО (4.24). При задании ЛО вектор ограни-ничений по матрице А фиксируется согласно (4.23).

Поэтому, выбрав некоторую допустимую область для вектора ограничений по подматрице Вr, тем самым в силу (4.31) устанавливаем соответствующую допустимую область Vk для вектора ограничений по дополнительной подматрице

Определение 4.6. Пусть- произвольный М × Р- ЛО (4.24). Тогда ЛО, образованный множеством столбцов ЛО при ограничениях на числа элементов из различных строк Вr в виде k= 1,. .., Q, т. е. выражение

(4.32)

называется минором r-го порядка, соответствующим множеству столбцов Вr исходного ЛО и ограничению Тогда также ЛО, полученный из вычеркиванием множества столбцов Вr и заданием ограниче­ний на числа элементов из различных строк оставшейся подматрицы в видет. е. выражение

(4.33)

называется логическим дополнением минора в

Теорема 4.5. Произвольный ЛО (4.24) можно разложить по любой совокупности столбцов представив его в виде дизъюнкции БЛ сумм всех возможных для данного Вr миноров и их логических дополнений

(4.34)

Доказательство. Используя введенные обозначения, распишем ЛО в виде

Вынося за знаки не зависящие от s слагаемые, получим

Теперь вынесем за знакислагаемые, не зависящие от q:

Полученное выражение с учетом обозначений (4.32), (4.33) совпадает с (4.34). Разложение по столбцу (4.30) - частный случай разложения (4.34) при

Разложения ЛО по столбцу (4.30) и по совокупности столбцов (4.34) можно, аналогично § 4.4, рассматривать как некоторые принципы опти­мальности. Так как эти разложения понижают размерность ЛО и умень­шают сложность (число элементарных операций БЛ) его выражения, их целесообразно применять повторно, вплоть до получения выражения, со­держащего достаточно простые ЛО, например ЛО-столбцы, определяемые по очевидной формуле

(4.35)

В процессе последовательного разложения ЛО ужесточаются ограничения на строки ЛО, что часто приводит к появлению фиктивных (несуществую­щих) ЛО. Их (и содержащие их суммы) следует исключать из разложения. Это ведет к дополнительному уменьшению сложности выражения ЛО.

Оценим сложность представления М × Р-ЛО, получаемого последователь­ным разложением по столбцу. Считаем, что в процессе разложения фиктив­ные ЛО не появляются. Такое допущение завышает оцениваемую слож­ность. Учитывая это, из (4.30) получаем следующее уравнение для числа N(P) элементарных операций , + в представлении ЛО:

(4.36)

Отсюда, учитывая следующее из (4.35) начальное условие последовательно найдем N(2), N(3).....и, наконец, при или

(4.37)

Реально сложность получаемого представления ЛО обычно существенно меньше верхней оценки (4.37). Разложение по совокупности столбцов еще уменьшает эту сложность (см. ниже § 4.8,4.10).

Сложность представления ЛО, полученного в результате разложения, во много раз меньше сложности прямого выражения ЛО согласно его определению (4.24).

4.7. Логические определители третьего рода и их свойства

Рассмотрим снова М × Р-матрицу (4.1) при М = Р и все возможные суммы ее элементовсодержащие каждая один элемент из каждого столбца А. Введем дополнительное ограничение: из любой строки А в сумму должен входить тоже один элемент. Суммы удовлетворяющие этому дополнительному ограничению, обозначим Число таких сумм равно M!