Математическая энциклопедия

"

0

C

F

G

H

K

L

N

P

S

T

W

Z

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Э

Ю

Я

ПЕРМАНЕНТ

(mxn)-матрицы А =|| а _ij|| - функция

где a_ij - элементы из коммутативного кольца, суммирование производится по всем взаимно однозначным отображениям s из {1, 2, . . ., т}в {1, 2, . . ., п}. Если m=n, то s - всевозможные подстановки, и П. представляет собой частный случай матричной функции Шура

при где - характер степени 1 на подгруппе Нсимметрической группы S_n (при H=S_n, , в зависимости от четности s, получается определитель).

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

Наибольший интерес представляют П. матриц из нулей и единиц ((0,1)-матриц), матриц с неотрицательными действительными элементами, в частности дважды стохастических матриц (у к-рых суммы элементов по любой строке и любому столбцу равны 1) и комплексных эрмитовых матриц. Из основных свойств П. следует отметить теорему о разложении (аналог теоремы Лапласа для определителей) и теорему Вине - Коши, дающую представление П. произведения двух матриц через сумму произведений П., образованных из сомножителей. Для П. комплексных матриц полезно представление их в виде скалярного произведения на классах симметрии вполне симметричных тензоров (см., напр., [3]). Один из наиболее эффективных способов вычисления П. дает формула Райзера:

где А _k - совокупность подматриц размера квадратной матрицы А, r_i=r_i (Х).- сумма элементов в i-й строке X, i, k=1, . . ., т. Ввиду сложности вычисления П. важны его оценки. Ниже приведены нек-рые из оценок снизу.

а) Если Аесть (0, 1)-матрица с т, то

при

если t<т и per А>0.

б) Если Аесть (0, 1)-матрица порядка п, то

где - суммы элементов в строках А, расположенные в порядке невозрастания, =

в) Если А - положительно полуопределенная эрмитова матрица порядка n, то

где , если Оценки П. сверху:

1) для (0, 1)-матрицы порядка п

2) для вполне неразложимой матрицы порядка п с неотрицательными целыми элементами

3) для комплексной нормальной матрицы с собственными значениями l₁,... , l_n

Наиболее известной проблемой в теории П. являлась гипотеза Ван дер Вардена: П. дважды етохастич. матрицы порядка пограничен снизу величиной n!/nⁿ, и это значение достигается лишь для матрицы, составленной из дробей 1/n. Положительное решение этой проблемы было получено в 1980 (см. [4]).

Из применений П. следует отметить связь с известными комбинаторными задачами о встречах, об исполнителях, с Фибоначчи числами, с перечислением латинских квадратов и троек Штейнера, с нахождением числа 1-факторов и линейных подграфов в графе;дважды етохастич. матрицы связаны с нек-рыми вероятностными моделями. Интересны физич. применения П., среди к-рых наиболее важна проблема ди-меров, возникающая при изучении адсорбции двухатомных молекул поверхностного слоя: через П. (0, 1) -матрицы простого строения выражается число способов объединения атомов вещества в двухатомные молекулы. Известны также применения П. в статистич. физике, теории кристаллов, физич. химии.

Лит.:[1] Райзер Г. Д ж., Комбинаторная математика, пер. с англ., М., 1966; [2] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [3] Минк X., Перманенты, пер. с англ., М., 1982; [4] Егорычев Г. П., Решение проблемы Ван дер Вардена для перманентов, Красноярск, 1980; [5] Фаликман Д. И., "Матем. заметки", 1981, т. 29, в. 6, с. 931-38. В. Е. Тараканов.