Перманент

(mxn)-матрицы А =|| а ij|| — функция где aij — элементы из коммутативного кольца, суммирование производится по всем взаимно однозначным отображениям s из в . Если 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. В. Е. Тараканов.