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

Разложение по столбцу (4.18) — частный случай разложения (4.19) при когда

Доказательство. Обозначим сум­му вида для матрицы, образованной столбцами исходной матрицы А; сумму вида для матри­цы, полученной из А вычеркиванием столбцов Распишем ЛО в виде

Вынося за скобки общие слагаемые в одинаково подчеркнутых выражениях, получим

Вынося теперь за скобки общее слагаемоенайдем

Но

Последние два выражения в совокупности дают (4.19).

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

Разложение (4.19) можно рассматривать как принцип оптимальности, по которому максимальная сумма элементов вида в М × Р-матрице

состоит из двух подсумм того же вида, из которых одна относит­ся к подматрице, образованной произвольными r столбцами матрицы А, а вторая — к подматрице, образованной остальными Р—r стобцами.

4.4. Простейшее выражение логического определителя первого рода

Мы видели (§ 4.3), что разложение ЛО по столбцу (по совокупности столбцов) понижает размерность ЛО и уменьшает число элементарных операций в его выражении. Поэтому естественно ожидать, что, продолжив это разложение, в конце концов получим выражение ЛО через его элемен­ты, содержащее минимальное число операций. Воспользуемся разложением ЛО по столбцу (4.18). Разложим в нем логическое дополнение по некоторому r-му (r≠j) столбцу Здесь— ЛО, полученный из исходного ЛО вычеркиванием j-го и r-го столбцов, т. е. логическое дополнение этих столбцов. Далее разложими т. д. В итоге получим искомое выражение ЛО

(4.20)

Согласно выражению (4.20) ЛО равен просто сумме максимальных элементов всех своих стобцов. Сложность (число элементарных опера­ций выражения (4.20)

(4.21)

Она пропорциональна размерам матрицы А и во много раз меньше слож­ности выражения ЛО согласно его определению (4.2). Из срав­нения (4.2) и (4.20) видно, что

(4.22)

т. е. в данном случае операциив некотором смысле коммутативны.

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

Будем рассматривать М ×Р-матрицу (4.1) и все возможные

ее суммы элементов содержащие каждая ровно один элемент из

каждого столбца А.

Однако теперь введем дополнительное ограничение: из произвольной i-й строки в сумму может входить лишь определенное число элементов рi, ограниченное снизу и сверху согласно

(4.23)

Суммы удовлетворяющие дополнительным ограничениям (4.23), обозначим а их число — R.

Определение 4.4. Будем называть ЛО с ограничениями второго рода для матрицы А выражения вида

(4.24) .

(4.25)

т. е. дизъюнкцию (конъюнкцию) БЛ всех сумм элементов А, содержащих каждая ровно один элемент из каждого столбца А и рi элементов из i-й строки где pi ограничены неравенствами (4.23).

По той же причине, что и в случае ограничений первого рода (4.2), ниже из двух типов ЛО изучается только ЛО (4.24). ЛО (4.24), (4.25) сущест­вуют не всегда, так как ограничения (4.23) могут быть такими, что для заданной матрицы нет ни одной суммы вида

Теорема 4.3. Дая существования у М × Р-матрицы ЛО вида

(4.24) или (4.25) необходимо и достаточно, чтобы ограничения (4.23) удовлетворяли условию

(4.26)

Доказательство. Пусть выполнено условие (4.26). Тогда область (4.23) не пуста, т. е. можно выбрать такие значения параметров рi в

(4.23), что и При этом можно образовать по крайней мере одну сумму элементов видадля заданной матрицывзяв из первой строки элементов, расположенных в первыхстолбцах, из второй строки элементов, расположенных в следующих столбцах,..., из М-й строки элементов, расположен­ных в последних столбцах. Следовательно, ЛО (4.24) как максимум (ЛО (4.20) как минимум) всех сумм видасуществует. Допустим теперь, что условие (4.26) не выполнено. Тогда и потому область (4.23) пуста, т. е. нельзя подобрать такие значения параметров рi, чтобы и Значит, для матрицы

нельзя образовать ни одной суммы элементов вида и ЛО (4.24), (4.25) не существуют.

ЛО с ограничениями второго рода обладают свойствами ЛО с ограни­чениями первого рода, содержащимися в леммах 4.2 — 4.8, что доказывает­ся точно так же. Кроме того, они обладают двумя свойствами, уточняю­щими соответствующие свойства ЛО с ограничениями первого рода. Имен­но, свойство, выражаемое леммой 4.1, уточняется так.

Лемма 4.15. Перестановка местами двух строк совместно с их ограни­чениями не меняет величины ЛО (4.24), (4.25):

(4.27)

Доказательство формулы (4.27) совпадает с доказательством форму­лы (4.4). Свойство, выражаемое леммой 4.9, уточняется таким образом.

Лемма 4.16. ЛО (4.24), содержащий в качестве элемента некоторой

i- й строки бесконечность, сам равен бесконечности, если область ограничений для i-й строки не пуста.

Доказательство повторяет ход доказательства леммы 4.9, но учитывает нижеследующее свойство, типичное только для ЛО с ограничениями второ­го рода.

Лемма 4.17. Строка, область ограничений которой пуста, может быть вычеркнута без изменения величины ЛО (4.24), (4.25):

Доказательство следует из того, что по определению (4.24) в выражение левого ЛО (4.28) не входят элементы k-й строки.