Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Квадратный корень из детерминанта кососимметричной квадратной матрицы
Square root of the determinant of a skew symmetric square matrix
В математике детерминант кососимметричной матрицы размера m×m всегда можно представить как квадрат полинома от элементов матрицы, полинома с целочисленными коэффициентами, зависящего только от m. Если m нечетно, то полином равен нулю. Если m четно, то это ненулевой полином степени m/2, определенный с точностью до умножения на ±1. Соглашение относительно кососимметричных тридиагональных матриц, приведенное ниже в примерах, определяет конкретный полином, называемый полиномом Пфаффа. Значение этого полинома, примененное к элементам кососимметричной матрицы, называется пфаффианом этой матрицы. Термин "пфаффиан" был введен , который косвенно назвал его в честь Иоганна Фридриха Пфаффа. Явно, для кососимметричной матрицы ,
In mathematics, the determinant of an m×m skew symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depends on m. When m is odd, the polynomial is zero. When m is even, it is a nonzero polynomial of degree m/2, and is unique up to multiplication by ±1. The convention on skew symmetric tridiagonal matrices, given below in the examples, then determines one specific polynomial, called the Pfaffian polynomial. The value of this polynomial, when applied to the entries of a skew symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by , who indirectly named them after Johann Friedrich Pfaff. Explicitly, for a skew symmetric matrix ,
что было впервые доказано , который ссылается на Якоби как на автора, введшего эти полиномы в работах по системам дифференциальных уравнений Пфаффа. Кейли получает это соотношение, специализируя более общий результат для матриц, отклоняющихся от кососимметрии только в первой строке и первом столбце. Детерминант такой матрицы равен произведению пфаффианов двух матриц, полученных путем обнуления верхнего левого элемента в исходной матрице и последующего копирования, соответственно, отрицательной транспонированной первой строки в первый столбец и отрицательной транспонированной первого столбца в первую строку. Это доказывается индукцией путем разложения детерминанта по минорам и использования рекуррентной формулы, приведенной ниже.
which was first proved by , who cites Jacobi for introducing these polynomials in work on Pfaffian systems of differential equations. Cayley obtains this relation by specialising a more general result on matrices that deviate from skew symmetry only in the first row and the first column. The determinant of such a matrix is the product of the Pfaffians of the two matrices obtained by first setting in the original matrix the upper left entry to zero and then copying, respectively, the negative transpose of the first row to the first column and the negative transpose of the first column to the first row. This is proved by induction by expanding the determinant on minors and employing the recursion formula below.
Рекурсивное определение
По общепринятому соглашению, пфаффиан матрицы 0×0 равен единице. Пфаффиан кососимметричной матрицы 2n×2n A при n > 0 может быть вычислен рекурсивно как
By convention, the Pfaffian of the 0×0 matrix is equal to one. The Pfaffian of a skew symmetric 2n×2n matrix A with n > 0 can be computed recursively as
где индекс i может быть выбран произвольно, – функция Хевисайда, а обозначает матрицу A, из которой удалены i-я и j-я строки и столбцы. Обратите внимание, что при специальном выборе это выражение упрощается до:
where the index i can be selected arbitrarily, is the Heaviside step function, and denotes the matrix A with both the ith and jth rows and columns removed. Note how for the special choice this reduces to the simpler expression:
Свойства и идентичность
Пфаффианы обладают следующими свойствами, аналогичными свойствам определителей. Умножение строки и соответствующего столбца на константу эквивалентно умножению пфаффиана на ту же константу. Одновременная перестановка двух различных строк и соответствующих столбцов меняет знак пфаффиана. Прибавление к другой строке и соответствующему столбцу кратного одной строки и соответствующего столбца не изменяет значение пфаффиана. Используя эти свойства, пфаффианы можно вычислять быстро, подобно вычислению определителей.
Pfaffians have the following properties, which are similar to those of determinants. Multiplication of a row and a column by a constant is equivalent to multiplication of the Pfaffian by the same constant. Simultaneous interchange of two different rows and corresponding columns changes the sign of the Pfaffian. A multiple of a row and corresponding column added to another row and corresponding column does not change the value of the Pfaffian. Using these properties, Pfaffians can be computed quickly, akin to the computation of determinants.
Приложения
Существуют программы для численного вычисления пфаффиана на различных платформах (Python, Matlab, Mathematica). Пфаффиан является инвариантным полиномом от кососимметричной матрицы при ортогональном преобразовании базиса. В связи с этим он играет важную роль в теории характеристических классов. В частности, его можно использовать для определения класса Эйлера риманова многообразия, который применяется в обобщённой теореме Гаусса — Бонне. Количество полных паросочетаний в планарном графе задаётся пфаффианом, следовательно, вычислимо за полиномиальное время с помощью алгоритма FKT. Это удивительно, учитывая, что для общих графов задача является очень сложной (так называемая #P-полная). Этот результат используется для вычисления числа раскрасок прямоугольника домино, функции распределения моделей Изинга в физике или марковских случайных полей в машинном обучении (; ), где базовый граф является планарным. Он также применяется для разработки эффективных алгоритмов для некоторых задач, которые кажутся неразрешимыми, включая эффективное моделирование определённых типов ограниченных квантовых вычислений. Подробнее см. статью «Голографический алгоритм».
There exist programs for the numerical computation of the Pfaffian on various platforms (Python, Matlab, Mathematica) The Pfaffian is an invariant polynomial of a skew symmetric matrix under a proper orthogonal change of basis. As such, it is important in the theory of characteristic classes. In particular, it can be used to define the Euler class of a Riemannian manifold that is used in the generalized Gauss–Bonnet theorem. The number of perfect matchings in a planar graph is given by a Pfaffian, hence is polynomial time computable via the FKT algorithm. This is surprising given that for general graphs, the problem is very difficult (so called #P complete). This result is used to calculate the number of domino tilings of a rectangle, the partition function of Ising models in physics, or of Markov random fields in machine learning (; ), where the underlying graph is planar. It is also used to derive efficient algorithms for some otherwise seemingly intractable problems, including the efficient simulation of certain types of restricted quantum computation. Read Holographic algorithm for more information.