Полином гамильтонова цикла - Hamiltonian cycle polynomial

В математике Полином гамильтонова цикла из п×п-матрица - это многочлен от элементов матрицы, определяемый как

${\displaystyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$

куда ${\displaystyle H_{n}}$ это набор п-перестановки имея ровно один цикл.

Это алгебраический вариант, полезный в ряде случаев для определения существования Гамильтонов цикл в ориентированный граф.

Это обобщение числа гамильтоновых циклов орграфа как суммы произведений весов дуг его гамильтоновых циклов (все из которых равны единице) для взвешенных орграфов с весами дуг, взятыми из данного коммутативного кольца. Между тем, для неориентированного взвешенного графа сумма произведений весов ребер его гамильтоновых циклов, содержащих любое фиксированное ребро (я,j) может быть выражено как произведение веса (я,j) и полином гамильтонова цикла матрицы, полученной из ее взвешенной матрицы смежности путем перестановки ее строк и столбцов любым перестановочным отображением я к 1 и j к 2 а затем удалив его 1-й ряд и 2-й столбец.

В (Кнежевич и Коэн (2017) ) было показано, что

${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})}$

куда ${\displaystyle A_{J}}$ является подматрицей ${\displaystyle A}$ индуцированные строками и столбцами ${\displaystyle A}$ проиндексировано ${\displaystyle J}$, и ${\displaystyle {\bar {J}}}$ является дополнением ${\displaystyle J}$ в ${\displaystyle \{1,\dots ,n\}}$, а определитель пустой подматрицы определен равным 1.

В силу этого и тождеств Борчардта для неособого п×п Матрица Коши ${\displaystyle C(x,y)}$ ${\displaystyle \operatorname {ham} (C(x,y))={\det }(-D_{1}^{2}C^{*2}(x,y)D_{2}^{2}+I_{/1})\operatorname {det} (C(x,y))}$ куда ${\displaystyle D_{1},D_{2}}$ диагональные матрицы, которые делают ${\displaystyle D_{1}C(x,y)D_{2}}$ унитарный (в вещественном поле или поле конечной характеристики, или ортогональный в поле комплексных чисел), ${\displaystyle C^{*2}(x,y)}$ - квадрат Адамара (по входам) ${\displaystyle C(x,y)}$, и ${\displaystyle I_{/1}}$ это личность п×п-матрица с индексами 1,1 замененными на 0.

В поле характеристики 2 равенство ${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})}$ превращается в ${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}})}$ что, таким образом, дает возможность полиномиально вычислить полином гамильтонова цикла любой унитарной матрицы ${\displaystyle U}$ (т.е. такие, что ${\displaystyle U^{T}U=I}$ куда ${\displaystyle I}$ это личность п×п-матрица), поскольку в таком поле каждый минор унитарной матрицы совпадает со своим алгебраическим дополнением: ${\displaystyle \operatorname {ham} (U)={\det }^{2}(U+I_{/1})}$ куда ${\displaystyle I_{/1}}$ это личность п×п-матрица с индексами 1,1, замененными на 0. Следовательно, если возможно полиномиальное время присвоить веса из поля характеристики 2 дугам орграфа, которые сделают его взвешенную матрицу смежности унитарной и имеющей ненулевой многочлен гамильтонова цикла то орграф гамильтонов. Следовательно, проблема гамильтонова цикла вычислима на таких графах за полиномиальное время.

В характеристике 2 полином гамильтонова цикла п×п-матрица равна нулю, если п > 2k, где k - его ранг или если он инволютивен и п > 1.

Кроме того, в произвольном кольце ${\displaystyle R}$ характеристика которого не является четным натуральным числом для любого кососимметричного п×п-матрица ${\displaystyle A}$ существует степенной ряд от формальной переменной ${\displaystyle \varepsilon }$ ${\displaystyle U(\varepsilon )=\sum _{n=0}^{\infty }U_{n}\varepsilon ^{n}}$ так что это унитарный п×п-матрица над ${\displaystyle R\left(\varepsilon \right)}$ и ${\displaystyle U_{0}=I}$, ${\displaystyle U_{1}=A}$, а для любого ${\displaystyle U(\varepsilon )}$ удовлетворяющий этим условиям ${\displaystyle \operatorname {ham} (A)}$ равен коэффициенту при ${\displaystyle n}$-я степень ${\displaystyle \varepsilon }$ в силовом ряду ${\displaystyle \operatorname {ham} (U(\varepsilon ))}$. И для любого кольца ${\displaystyle R}$ четной характеристики то же самое верно, когда диагональ ${\displaystyle A^{2}}$ кратно 2. Это означает, что вычисления с точностью до ${\displaystyle n}$-я степень ${\displaystyle \varepsilon }$, многочлен гамильтонова цикла унитарной п×п-матрица над бесконечным расширением любого кольца характеристики q (не обязательно простого) формальной переменной ${\displaystyle \varepsilon }$ это #${\displaystyle _{q}}$P-полный проблема если ${\displaystyle q}$ не 2 и вычисление полинома гамильтонова цикла ${\displaystyle k}$-полунитарная матрица (т.е. п×п-матрица ${\displaystyle V}$ такой, что ${\displaystyle \operatorname {rank} (V^{T}V-I\,)=k}$) над таким расширением любого кольца характеристики 2 является #${\displaystyle _{2}}$P-полный проблема для любого ${\displaystyle k}$ > 0 (потому что любое ${\displaystyle k}$-полунитарную матрицу можно получить из унитарной матрицы, удалив ${\displaystyle k}$ ряды и ${\displaystyle k}$ столбцы). За ${\displaystyle k=1}$ последнее утверждение можно переформулировать как #${\displaystyle _{2}}$P-полнота вычислений для данной унитарной п×п-матрица ${\displaystyle U}$ над полем характеристики 2 п×п-матрица ${\displaystyle H(U)}$ чей я,j-й элемент - это полином гамильтонова цикла матрицы, полученной из ${\displaystyle U}$ путем перестановки его строк и столбцов любым отображением перестановок я к 1 и j к 2 а затем удалив его 1-й ряд и 2-й столбец (т.е. сумма произведений весов дуг гамильтоновых путей соответствующего взвешенного орграфа из j к я) за я ≠ j и ноль для я = j. Эта матрица удовлетворяет матричному уравнению ${\displaystyle U(H(U))^{T}=H(U)U^{T}}$, пока ${\displaystyle \operatorname {ham} \left({\begin{matrix}U&{Ua}\\a^{T}&0\end{matrix}}\right)=(a_{1}^{2}+...+a_{n}^{2})\operatorname {ham} (U)}$ куда ${\displaystyle a}$ - произвольный n-вектор.

Кроме того, стоит отметить, что в характеристике 2 многочлен гамильтонова цикла обладает своими инвариантными матричными сжатиями (частично аналогичными гауссовской модификации, инвариантной для определителя), с учетом того, что ${\displaystyle \operatorname {ham} (X)=0}$ для любого т×т-матрица ${\displaystyle X}$ имеющий три равные строки или, если ${\displaystyle t}$ > 2, пара индексов i, j, у которых i-я и j-я строки идентичны, а i-й и j-й столбцы идентичны.

Следовательно, если матрица имеет две равные строки с индексами я и j то добавление одного из них к любому третьему не изменяет этот многочлен в характеристике 2, что позволяет гауссовскому стилю исключить все элементы его я-й столбец, кроме я,я-й и j,я-ые (если они не равны нулю) и удалите его я-й столбец и j-я строка (описанным выше способом) - тогда полином гамильтонова цикла исходной матрицы равен этому полиному новой, умноженному на исходную j,я-я запись.

Также в характеристике 2 и для матриц с более чем двумя строками полином гамильтонова цикла не изменяется добавлением я-й столбец в j-й в матрице, где я-й и j-я строки идентичны, что, в частности, дает идентичность

${\displaystyle \det(D+D^{-1})\operatorname {ham} \left({\begin{matrix}V&A\\B&U\end{matrix}}\right)=\operatorname {ham} \left({\begin{matrix}V&V+D&A\\V+D^{-1}&V+D^{-1}+D&A\\B&B&U\end{matrix}}\right)}$

для п×п-матрица ${\displaystyle U}$, м×м-матрицы ${\displaystyle V}$ и диагональ ${\displaystyle D}$, м×п-матрица ${\displaystyle A}$ и п×м-матрица ${\displaystyle B}$.

Ограничение этой личности на случай, когда ${\displaystyle U}$ унитарен, ${\displaystyle VD+DV^{T}+AA^{T}=I+D^{2}}$ и ${\displaystyle BD=UA^{T}}$, куда ${\displaystyle I}$ это личность м×м-матрица, составляет (2м+п)×(2м+п) -матрица в унитарной правой части равенства и ее полиномиальный гамильтонов цикл вычислим, следовательно, за полиномиальное время, что, таким образом, обобщает приведенную выше формулу для полинома гамильтонова цикла унитарной матрицы. Кроме того, в характеристике 2 для квадратных матриц X, Y ${\displaystyle \operatorname {ham} \left({\begin{matrix}X&Y\\Y&X\end{matrix}}\right)}$ - квадрат суммы по всем парам неравных индексов i, j i, j-го элемента Y, умноженный на многочлен гамильтонова цикла матрицы, полученной от X + Y путем удаления его я-й ряд и j-й столбец (как описано выше). Следовательно, если подставить указанное выше равенство A = B и U = V, мы получим другое расширение класса унитарных матриц, в которых многочлен гамильтонова цикла вычислим за полиномиальное время.

Помимо упомянутых выше преобразований сжатия, в характеристике 2 для многочленов гамильтонова цикла матрицы и ее частичного обратного (для ${\displaystyle A_{11}}$ и ${\displaystyle A_{22}}$ будучи квадратным, ${\displaystyle A_{11}}$ существование обратимый ):

${\displaystyle \operatorname {ham} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)={\det }^{2}\left(A_{11}\right)\operatorname {ham} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}+A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)}$

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

Следовательно, существует множество операторов сжатия матриц, выполняемых за полиномиальное время и сохраняющих полином гамильтонова цикла в характеристике 2, последовательное применение которых вместе с преобразованием транспонирования (используемым каждый раз, когда операторы оставляют матрицу нетронутой) имеет для каждой матрицы определенный предел, который можно определить как оператор сжатия-замыкания. Таким образом, применительно к классам матриц этот оператор отображает один класс в другой. Как было доказано в (Кнежевич и Коэн (2017) ), если оператор сжатия-замыкания отображает класс унитарных матриц на все множество квадратных матриц над бесконечным полем характеристики 2, то многочлен гамильтонова цикла вычислим за полиномиальное время над любым полем этой характеристики, что влечет за собой равенствоRP = НП.

Рекомендации

• Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о перманентах в конечных характеристиках, arXiv:1710.01783, Bibcode:2017arXiv171001783K.

• Коган, Григорий (1996), "Вычисление перманентов над полями характеристики 3: где и почему становится сложно", 37-й ежегодный симпозиум по основам компьютерных наук (FOCS '96): 108–114, Дои:10.1109 / SFCS.1996.548469, ISBN  0-8186-7594-2

• Коэн, Грег (2010), Новая алгебраическая техника для полиномиального вычисления числа гамильтоновых разложений по модулю 2 и аналогичных разбиений множества ребер графа, arXiv:1005.2281, Bibcode:2010arXiv1005.2281C