In mathematics, the Hamiltonian cycle polynomial of an "n"×"n"-matrix is a polynomial in its entries, defined as
 formula_1
where formula_2 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 () it was shown that
 formula_3 
where formula_4 is the submatrix of formula_5 induced by the rows and columns of formula_5 indexed by formula_7, and formula_8 is the complement of formula_7 in formula_10, 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 formula_11 formula_12 where formula_13 are diagonal matrices that make formula_14 unitary (in a real field or a field of a finite characteristic, or orthogonal in the field of complex numbers), formula_15 is the Hadamard (entry-wise) square of formula_11, and formula_17 is the identity "n"×"n"-matrix with the entry of indexes 1,1 replaced by 0.
In a field of characteristic 2 the equality formula_3 turns into formula_19 what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary matrix formula_20 (i.e. such that formula_21 where formula_22 is the identity "n"×"n"-matrix), because in such a field each minor of a unitary matrix coincides with its algebraic complement: formula_23 where formula_17 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 formula_25 whose characteristic isn't an even natural number, for any skew-symmetric "n"×"n"-matrix formula_5 there exists a power series in a formal variable formula_27 formula_28 such that it's a unitary "n"×"n"-matrix over formula_29 and formula_30, formula_31, while for any formula_32 satisfying these conditions formula_33 equals the coefficient at the formula_34-th power of formula_27 in the power series formula_36. And for any ring formula_25 of an even characteristic the same is true when the diagonal of formula_38 is a multiple of 2. It implies that computing, up to the formula_34-th power of formula_27, 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 formula_27 is a #formula_42P-complete problem if formula_43 isn't 2 and computing the Hamiltonian cycle polynomial of a formula_44-semi-unitary matrix (i.e. an "n"×"n"-matrix formula_45 such that formula_46) over such an extension of any ring of characteristic 2 is a #formula_47P-complete problem for any formula_44 ; 0 (because any formula_44-semi-unitary matrix can be received from a unitary matrix via removing formula_44 rows and formula_44 columns). For formula_52 the latter statement can be re-formulated as the #formula_47P-completeness of computing, for a given unitary "n"×"n"-matrix formula_20 over a field of characteristic 2, the "n"×"n"-matrix formula_55 whose "i","j"-th entry is the Hamiltonian cycle polynomial of a matrix received from formula_20 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 formula_57, while formula_58 where formula_59 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 formula_5 such that formula_61 where formula_62 is the formula_63-th column of formula_5 with its formula_63-th entry replaced by 0 and formula_22 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 formula_67 for any "t"×"t"-matrix formula_68 having three equal rows or, if formula_69 ; 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
 formula_70
for an "n"×"n"-matrix formula_20, "m"×"m"-matrices formula_45 and diagonal formula_73, "m"×"n"-matrix formula_5 and "n"×"m"-matrix formula_75. 
This identity's restriction to the case when formula_20 is unitary, formula_77 and formula_78, where formula_22 is the identity "m"×"m"-matrix, makes the (2"m"+"n")×(2"m"+"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 formula_80 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 formula_81 and formula_82 being square, formula_81 being invertible):
 formula_84
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 (), if the compression-closure of the class of unitary matrices contains a subset where computing this polynomial is #formula_47P-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.
 ;templatestyles src="Reflist/styles.css" / ;