Математическая энциклопедия - перманент
Связанные словари
Перманент
(mxn)-матрицы А =|| а ij|| функция
где aij - элементы из коммутативного кольца, суммирование производится по всем взаимно однозначным отображениям s из {1, 2, . . ., т}в {1, 2, . . ., п}. Если m=n, то s всевозможные подстановки, и П. представляет собой частный случай матричной функции Шура
при где характер степени 1 на подгруппе Нсимметрической группы Sn (при H=Sn, , в зависимости от четности s, получается определитель).
П. применяется в линейной алгебре, теории вероятностей и комбинаторике. В комбинаторике П. можно интерпретировать следующим образом: число систем различных представителей для заданного семейства подмножеств конечного множества есть П. матрицы инцидентности для инцидентности системы, связанной с этим семейством.
Наибольший интерес представляют П. матриц из нулей и единиц ((0,1)-матриц), матриц с неотрицательными действительными элементами, в частности дважды стохастических матриц (у к-рых суммы элементов по любой строке и любому столбцу равны 1) и комплексных эрмитовых матриц. Из основных свойств П. следует отметить теорему о разложении (аналог теоремы Лапласа для определителей) и теорему Вине Коши, дающую представление П. произведения двух матриц через сумму произведений П., образованных из сомножителей. Для П. комплексных матриц полезно представление их в виде скалярного произведения на классах симметрии вполне симметричных тензоров (см., напр., [3]). Один из наиболее эффективных способов вычисления П. дает формула Райзера:
где А k совокупность подматриц размера квадратной матрицы А, ri=ri (Х).сумма элементов в i-й строке X, i, k=1, . . ., т. Ввиду сложности вычисления П. важны его оценки. Ниже приведены нек-рые из оценок снизу.
а) Если Аесть (0, 1)-матрица с т, то
при
если t<т и per А>0.
б) Если Аесть (0, 1)-матрица порядка п, то
где суммы элементов в строках А, расположенные в порядке невозрастания, =
в) Если А - положительно полуопределенная эрмитова матрица порядка n, то
где , если Оценки П. сверху:
1) для (0, 1)-матрицы порядка п
2) для вполне неразложимой матрицы порядка п с неотрицательными целыми элементами
3) для комплексной нормальной матрицы с собственными значениями l1,... , ln
Наиболее известной проблемой в теории П. являлась гипотеза Ван дер Вардена: П. дважды етохастич. матрицы порядка пограничен снизу величиной n!/nn, и это значение достигается лишь для матрицы, составленной из дробей 1/n. Положительное решение этой проблемы было получено в 1980 (см. [4]).
Из применений П. следует отметить связь с известными комбинаторными задачами о встречах, об исполнителях, с Фибоначчи числами, с перечислением латинских квадратов и троек Штейнера, с нахождением числа 1-факторов и линейных подграфов в графе;дважды етохастич. матрицы связаны с нек-рыми вероятностными моделями. Интересны физич. применения П., среди к-рых наиболее важна проблема ди-меров, возникающая при изучении адсорбции двухатомных молекул поверхностного слоя: через П. (0, 1) -матрицы простого строения выражается число способов объединения атомов вещества в двухатомные молекулы. Известны также применения П. в статистич. физике, теории кристаллов, физич. химии.
Лит.:[1] Райзер Г. Д ж., Комбинаторная математика, пер. с англ., М., 1966; [2] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [3] Минк X., Перманенты, пер. с англ., М., 1982; [4] Егорычев Г. П., Решение проблемы Ван дер Вардена для перманентов, Красноярск, 1980; [5] Фаликман Д. И., "Матем. заметки", 1981, т. 29, в. 6, с. 931-38. В. Е. Тараканов.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985