Hamiltonian cycle polynomial

In mathematics, the Hamiltonian cycle polynomial of an n×n-matrix is a polynomial in its entries, defined as

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

where $H_{n}$ is the set of n-permutations having exactly one cycle.

This is an algebraic option useful, in a number of cases, for determining the existence of a Hamiltonian cycle in a directed graph.

It is a generalization of the number of Hamiltonian cycles of a digraph as the sum of the products of its Hamiltonian cycles' arc weights (all of which equal unity) for weighted digraphs with arc weights taken from a given commutative ring. In the meantime, for an undirected weighted graph the sum of the products of the edge weights of its Hamiltonian cycles containing any fixed edge (i,j) can be expressed as the product of the weight of (i,j) and the Hamiltonian cycle polynomial of a matrix received from its weighted adjacency matrix via subjecting its rows and columns to any permutation mapping i to 1 and j to 2 and then removing its 1-st row and 2-nd column.

In (Knezevic & Cohen (2017)) it was shown that

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

where $A_{J}$ is the submatrix of $A$ induced by the rows and columns of $A$ indexed by $J$, and ${\bar {J}}$ is the complement of $J$ in $\{1,\dots ,n\}$, while the determinant of the empty submatrix is defined to be 1.

Due to this and Borchardt's identities, for a non-singular n×n Cauchy matrix $C(x,y)$ $\operatorname {ham} (C(x,y))={\det }(-D_{1}^{2}C^{*2}(x,y)D_{2}^{2}+I_{/1})\operatorname {det} (C(x,y))$ where $D_{1},D_{2}$ are diagonal matrices that make $D_{1}C(x,y)D_{2}$ unitary (in a real field or a field of a finite characteristic, or orthogonal in the field of complex numbers), $C^{*2}(x,y)$ is the Hadamard (entry-wise) square of $C(x,y)$, and $I_{/1}$ is the identity n×n-matrix with the entry of indexes 1,1 replaced by 0.

In a field of characteristic 2 the equality $\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})$ turns into $\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}})$ what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary matrix $U$ (i.e. such that $U^{T}U=I$ where $I$ is the identity n×n-matrix), because in such a field each minor of a unitary matrix coincides with its algebraic complement: $\operatorname {ham} (U)={\det }^{2}(U+I_{/1})$ where $I_{/1}$ is the identity n×n-matrix with the entry of indexes 1,1 replaced by 0. Hence if it's possible to polynomial-time assign weights from a field of characteristic 2 to a digraph's arcs that make its weighted adjacency matrix unitary and having a non-zero Hamiltonian cycle polynomial then the digraph is Hamiltonian. Therefore the Hamiltonian cycle problem is computable on such graphs in polynomial time.

In characteristic 2, the Hamiltonian cycle polynomial of an n×n-matrix is zero if n > 2k where k is its rank or if it's involutory and n > 2.

Besides, in an arbitrary ring $R$ whose characteristic isn't an even natural number, for any skew-symmetric n×n-matrix $A$ there exists a power series in a formal variable $\varepsilon$ $U(\varepsilon )=\sum _{n=0}^{\infty }U_{n}\varepsilon ^{n}$ such that it's a unitary n×n-matrix over $R\left(\varepsilon \right)$ and $U_{0}=I$, $U_{1}=A$, while for any $U(\varepsilon )$ satisfying these conditions $\operatorname {ham} (A)$ equals the coefficient at the $n$-th power of $\varepsilon$ in the power series $\operatorname {ham} (U(\varepsilon ))$. And for any ring $R$ of an even characteristic the same is true when the diagonal of $AA^{T}$ is a multiple of 2. It implies that computing, up to the $n$-th power of $\varepsilon$, the Hamiltonian cycle polynomial of a unitary n×n-matrix over the infinite extension of any ring of characteristic q (not necessarily prime) by the formal variable $\varepsilon$ is a #$_{q}$P-complete problem if $q$ isn't 2 and computing the Hamiltonian cycle polynomial of a $k$-semi-unitary matrix (i.e. an n×n-matrix $V$ such that $\operatorname {rank} (V^{T}V-I\,)=k$) over such an extension of any ring of characteristic 2 is a #$_{2}$P-complete problem for any $k$ > 0 (because any $k$-semi-unitary matrix can be received from a unitary matrix via removing $k$ rows and $k$ columns). For $k=1$ the latter statement can be re-formulated as the #$_{2}$P-completeness of computing, for a given unitary n×n-matrix $U$ over a field of characteristic 2, the n×n-matrix $H(U)$ whose i,j-th entry is the Hamiltonian cycle polynomial of a matrix received from $U$ via subjecting its rows and columns to any permutation mapping j to 1 and i to 2 and then removing its 1-st row and 2-nd column (i.e. the sum of the products of the arc weights of the corresponding weighted digraph's Hamiltonian paths from vertex i to vertex j) for i ≠ j and zero for i = j. This matrix satisfies the matrix equation $U(H(U))^{T}=H(U)U^{T}$, while $\operatorname {ham} \left({\begin{matrix}U&{Ua}\\a^{T}&1\end{matrix}}\right)=(a_{1}^{2}+...+a_{n}^{2})\operatorname {ham} (U)$ where $a$ is an arbitrary n-vector (what can be interpreted as the polynomial-time computability of the Hamiltonian cycle polynomial of any 1-semi-unitary m×m-matrix $A$ such that $AA^{T}=I+bb^{T}$ where $b$ is the $m$-th column of $A$ with its $m$-th entry replaced by 0 and $I$ is the identity m×m-matrix).

Moreover, it would be worth noting that in characteristic 2 the Hamiltonian cycle polynomial possesses its invariant matrix compressions (partly analogical to the Gaussian modification that is invariant for the determinant), taking into account the fact that $\operatorname {ham} (X)=0$ for any t×t-matrix $X$ having three equal rows or, if $t$ > 2, a pair of indexes i,j such that its i-th and j-th rows are identical and its i-th and j-th columns are identical too.

Hence if a matrix has two equal rows with indexes i and j then adding one of them to any third one doesn't change this polynomial in characteristic 2 what allows to Gaussian-style eliminate all the entries of its i-th column except the i,i-th and j,i-th ones (in case if they aren't zero) and remove its i-th column and j-th row (in the manner described above) – then the Hamiltonian cycle polynomial of the initial matrix equals this polynomial of the new one multiplied by the initial j,i-th entry.

Also in characteristic 2 and for matrices with more than two rows the Hamiltonian cycle polynomial isn't changed by adding the i-th column to the j-th one in a matrix where the i-th and j-th rows are identical what, particularly, yields the identity

$\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)$

for an n×n-matrix $U$, m×m-matrices $V$ and diagonal $D$, m×n-matrix $A$ and n×m-matrix $B$.

This identity's restriction to the case when $U$ is unitary, $VD+DV^{T}+AA^{T}=I+D^{2}$ and $BD=UA^{T}$, where $I$ is the identity m×m-matrix, makes the (2m+n)×(2m+n)-matrix in the equality's right side unitary and its Hamiltonian cycle polynomial computable, hence, in polynomial time what therefore generalizes the above-given formula for the Hamiltonian cycle polynomial of a unitary matrix. Besides, in characteristic 2 for square matrices X, Y $\operatorname {ham} \left({\begin{matrix}X&Y\\Y&X\end{matrix}}\right)$ is the square of the sum, over all the pairs of non-equal indexes i,j, of the i,j-th entry of Y multiplied by the Hamiltonian cycle polynomial of the matrix received from X+Y via removing its i-th row and j-th column (in the manner described above). Hence, upon putting in the above equality A = B and U = V, we receive another extension of the class of unitary matrices where the Hamiltonian cycle polynomial is computable in polynomial time.

Apart from the above-mentioned compression transformations, in characteristic 2 the following relation is also valid for the Hamiltonian cycle polynomials of a matrix and its partial inverse (for $A_{11}$ and $A_{22}$ being square, $A_{11}$ being invertible):

$\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)$

and, due to the fact that the Hamiltonian cycle polynomial doesn't depend on the matrix's diagonal entries, adding an arbitrary diagonal matrix doesn't change this polynomial too. These two types of transformation don't compress the matrix, but keep its size unchanged. However, in a number of cases their application allows to reduce the matrix's size by some of the above-mentioned compression operators.

Hence there is a variety of matrix compression operators performed in polynomial time and preserving the Hamiltonian cycle polynomial in characteristic 2 whose sequential application, together with the transpose transformation (utilized each time the operators leave the matrix intact), has, for each matrix, a certain limit that can be defined as the compression-closure operator. When applied to classes of matrices, that operator thus maps one class to another. As it was proven in (Knezevic & Cohen (2017)), if the compression-closure of the class of unitary matrices contains a subset where computing this polynomial is #$_{2}$P-complete then the Hamiltonian cycle polynomial is computable in polynomial time over any field of this characteristic -- what would imply the equality RP = NP.

References

• Knezevic, Anna; Cohen, Greg (2017), Some facts on Permanents in Finite Characteristics, arXiv:1710.01783, Bibcode:2017arXiv171001783K.

• Kogan, Grigoriy (1996). "Computing permanents over fields of characteristic 3: Where and why it becomes difficult". Proceedings of 37th Conference on Foundations of Computer Science. pp. 108–114. doi:10.1109/SFCS.1996.548469. ISBN 0-8186-7594-2. S2CID 39024286.{{cite book}}: CS1 maint: date and year (link)

• Cohen, Greg (2010), A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set, arXiv:1005.2281, Bibcode:2010arXiv1005.2281C