§ 15. Перманент матрицы

Обозначим через матрицу с элементами

Перманентом матрицы назовем сумму

где суммирование производится по всем размещениям из элементов по

Предварительно рассмотрим перманенты нескольких матриц

(см. скан)

Основные свойства перманентов. 1) Перманент матрицы инвариантен относительно любой перестановки строк и столбцов.

2) При умножении какой-либо строки (или столбца) на скаляр перманент умножается на .

3) Если квадратная матрица, то

где - матрица, транспонированная к

б) если получается из вычеркиванием строки и столбца, то

Эти свойства легко проверяются. Приведем пример применения (15.11). Например, для матрицы из (15.6)

Следующая теорема облегчает вычисление перманента матрицы.

Теорема. Пусть матрица размера — матрица, полученная из заменой столбцов столбцами из нулей, сумма элементов строки матрицы а

суммирование в распространено на все сочетания без повторения из по Тогда

Прежде чем перейти к доказательству, рассмотрим пример. Пример. Пусть

(см. скан)

(см. скан)

Доказательство. Воспользуемся обобщенной формулой включения и исключения (12.24).

Пусть множество всех сочетаний без повторения из элементов по

Припишем элементам веса

Пусть свойство заключается в том, что (15.22) не содержит номера Если матрица, полученная из заменой столбцов нулевыми, то

и

Отсюда следует, что равен сумме весов элементов из удовлетворяющих в точности свойствам . В силу (12.24)

Подставляя (15.25) в (15.26) и замечая, что имеем

Для квадратной матрицы формула (15.13) упрощается:

Случай булевых матриц. Рассмотрим матрицы, элементы которых — нули и единицы. Такие матрицы называют булевыми, например,

Найдем перманенты некоторых булевых матриц.

Обозначим через единичную матрицу порядка

Очевидно,

Рассмотрим перестановочную матрицу определяемую условиями

Например,

Для любого

Определим матрицу условием

Например,

Очевидно,

Так как для имеем

то ввиду (15.28)

Сравнивая (15.37) и (15.35), получаем

Определим матрицу с элементами

где

Например,

Докажем теперь, что

Обозначим через матрицу с элементами

Например, для

По (15.11), учитывая инвариантность перманента при перестановках строк и столбцов, имеем

Подставим (15.46) в (15.45):

Заменим в на

Тогда (15.47) запишется так:

если заметить, что

Пример. Пусть

В силу (15.11) последний член справа в (15.50) запишется так:

Подставляя (15.51) в (15.50), получаем формулу, совпадающую при с (15.47):

В силу (15.49)

что опять приводит к (15.47) для :

если заметить, что

Перепишем (14.25):

и заменим на

Отсюда

и

если заметить, что

Сравнивая (15.49) и (15.60), видим, что последовательности совпадают. Тем самым (15.42) доказано.

Разлагая согласно (15.28):

получаем новую формулу для числа беспорядков:

Применение перманентов булевых матриц. Формулы (15.35) и (15.42) можно получить непосредственно следующим образом.

Подсчитаем число перестановок из элементов, в которых не допускаются некоторые расположения элементов. Построим прямоугольную булеву матрицу, в которой на запрещенных местах стоят нули (на рис. II эти клетки заштрихованы), а на остальных местах — единицы.

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

Рис. 11.

С помощью таких рассмотрений можно непосредственно доказать (15.38) и (15.42). В случае (15.38) ограничений нет и мы получаем все перестановок. Если все ограничения сводятся к наличию нулей на главной диагонали, то получаем (15.42), так как любой беспорядок есть перестановка, в которой запрещенные позиции изображаются нулями на главной диагонали в соответствующей булевой матрице.

Отметим, что перманент можно рассматривать как энумератор, хотя этот способ неудобен, когда число строк или столбцов в матрице велико. Более эффективный способ излагается в §§ 42—45 главы IV.

Мы вновь вернемся к перманенту в § 20.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)