  In the context of the graph matching problem we propose a novel method for
projecting a matrix $Q$, which may be a doubly stochastic matrix, to a
permutation matrix $P.$ We observe that there is an intuitve mapping, depending
on a given $Q,$ from the set of $n$-dimensional permutation matrices to sets of
points in $\mathbb{R}^n$. The mapping has a number of geometrical properties
that allow us to succesively sample points in $\mathbb{R}^n$ in a manner
similar to simulated annealing, where our objective is to minimise the graph
matching norm found using the permutation matrix corresponding to each of the
points. Our sampling strategy is applied to the QAPLIB benchmark library and
outperforms the PATH algorithm in two-thirds of cases. Instead of using linear
assignment, the incorporation of our sampling strategy as a projection step
into algorithms such as PATH itself has the potential to achieve even better
results.
