While determining the existence of Euler cycle (going once through each edge) for given graph is trivial, for Hamilton path (going once through each vertex) it is NP-complete problem (e.g. worth a million dollar).

Denoting adjacency matrix of this graph by and its number of vertices by , diagonal elements of count also eventual Hamilton cycles – the problem is that they also count other length n cycles – going more than once through some vertex.

The question is if we could somehow "subtract" those going multiple times through some vertex ...

Grassman variables (anticommuting), used in physics to work on fermions, seem to be perfect for this purpose. Assume we have Grassman variables: what also implies . So multiplication of of such variables is nonzero iff it contains all indexes (vertices).

Denote as diagonal matrix made of these variables. It is now easy to see that:

Graph contains Hamilton cycle iff.

Grassman variables can be realized by matrices – so we could see this formula in terms of block matrices ... unfortunately known realizations require e.g. size matrices, what is not helpful - we get only an implication:

If P != NP, then there is no polynomial size matrix realization of Grassman variables.

So probably these realizations just require exponentially large matrices, what seems reasonable.

We could easily find , so maybe there is a way to quickly find , what should be sufficient?

Any thoughts?