# Using adjacency matrix to calculate the number of hamiltonian paths

I heard that adjacency matrix can be used to calculate the number of k-length paths in a graph. Can't this be used as a way to calculate the number of hamiltonian paths?

-
More specifically, the adjacency matrix can be used to calculate the number of ways of reaching vertex $i$ from $j$ in $k$ steps. This of course does not guarantee non-repeating vertices. – EuYu Aug 23 '12 at 1:07

The adjacency matrix does not calculate the number of $k$-length paths in a graph. It calculates the number of $k$-length walks from one vertex to another. (More specifically, the entries of the $n$th power of the adjacency matrix encodes the number of walks). To see the difference between paths and walks, consider any two adjacent vertices not part of a cycle. Then there is exact one path between the two vertices i.e. the edge between them, but there exists an infinite number of walks between them. For example $v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2$ is a walk from $v_1$ to $v_2$ of length $3$. Specifically, paths do not allow repetition of vertices while walks do, therefore this does not in general aid in the computation of Hamiltonian paths or indeed, paths of arbitrary lengths.