Перманент

(mxn)-матрицы А =|| а ij|| - функция [img: http://localhost:8080/file/041710-26.jpg] где aij - элементы из коммутативного кольца, суммирование производится по всем взаимно однозначным отображениям s из {1, 2,..., т}в {1, 2,..., п}. Если m=n, то s - всевозможные подстановки, и П. представляет собой частный случай матричной функции Шура [img: http://localhost:8080/file/041710-27.jpg] при [img: http://localhost:8080/file/041710-28.jpg] где [img: http://localhost:8080/file/041710-29.jpg] - характер степени 1 на подгруппе Нсимметрической группы Sn (при H=Sn, [img: http://localhost:8080/file/041710-30.jpg], в зависимости от четности s, получается определитель). П. применяется в линейной алгебре, теории вероятностей и комбинаторике. В комбинаторике П. можно интерпретировать следующим образом: число систем различных представителей для заданного семейства подмножеств конечного множества есть П. матрицы инцидентности для инцидентности системы, связанной с этим семейством. Наибольший интерес представляют П. матриц из нулей и единиц ((0,1)-матриц), матриц с неотрицательными действительными элементами, в частности дважды стохастических матриц (у к-рых суммы элементов по любой строке и любому столбцу равны 1) и комплексных эрмитовых матриц. Из основных свойств П. следует отметить теорему о разложении (аналог теоремы Лапласа для определителей) и теорему Вине - Коши, дающую представление П. произведения двух матриц через сумму произведений П., образованных из сомножителей. Для П. комплексных матриц полезно представление их в виде скалярного произведения на классах симметрии вполне симметричных тензоров (см., напр., [3]). Один из наиболее эффективных способов вычисления П. дает формула Райзера: [img: http://localhost:8080/file/041710-31.jpg] где А k - совокупность подматриц размера [img: http://localhost:8080/file/041710-32.jpg] квадратной матрицы А, ri=ri (Х).- сумма элементов в i-й строке X, i, k=1,..., т. Ввиду сложности вычисления П. важны его оценки. Ниже приведены нек-рые из оценок снизу. а) Если Аесть (0, 1)-матрица с [img: http://localhost:8080/file/041710-33.jpg] т, то [img: http://localhost:8080/file/041710-34.jpg] при [img: http://localhost:8080/file/041710-35.jpg] [img: http://localhost:8080/file/041710-36.jpg] если t<т и per А>0. б) Если Аесть (0, 1)-матрица порядка п, то [img: http://localhost:8080/file/041710-37.jpg] где [img: http://localhost:8080/file/041710-38.jpg] - суммы элементов в строках А, расположенные в порядке невозрастания, [img: http://localhost:8080/file/041710-39.jpg] = [img: http://localhost:8080/file/041710-40.jpg] в) Если А - положительно полуопределенная эрмитова матрица порядка n, то [img: http://localhost:8080/file/041710-41.jpg] где [img: http://localhost:8080/file/041710-42.jpg], если [img: http://localhost:8080/file/041710-43.jpg] Оценки П. сверху: 1) для (0, 1)-матрицы порядка п [img: http://localhost:8080/file/041710-44.jpg] 2) для вполне неразложимой матрицы порядка п с неотрицательными целыми элементами [img: http://localhost:8080/file/041710-45.jpg] 3) для комплексной нормальной матрицы с собственными значениями l1,..., ln [img: http://localhost:8080/file/041710-46.jpg] Наиболее известной проблемой в теории П. являлась гипотеза Ван дер Вардена: П. дважды етохастич. матрицы порядка пограничен снизу величиной n!/nn, и это значение достигается лишь для матрицы, составленной из дробей 1/n. Положительное решение этой проблемы было получено в 1980 (см. [4]). Из применений П. следует отметить связь с известными комбинаторными задачами о встречах, об исполнителях, с Фибоначчи числами, с перечислением латинских квадратов и троек Штейнера, с нахождением числа 1-факторов и линейных подграфов в графе;дважды етохастич. матрицы связаны с нек-рыми вероятностными моделями. Интересны физич. применения П., среди к-рых наиболее важна проблема ди-меров, возникающая при изучении адсорбции двухатомных молекул поверхностного слоя: через П. (0, 1) -матрицы простого строения выражается число способов объединения атомов вещества в двухатомные молекулы. Известны также применения П. в статистич. физике, теории кристаллов, физич. химии.