Very recently, Matiyasevich showed that the question whether an equation over a trace monoid has a solution or not is decidable. In his proof this question is reduced to the solvability of word equations with constraints, by induction on the size of the commutation relation. In the present paper we give another proof of this result using lexicographical normal forms. Our method is a direct reduction of a trace equation system to a word equation system with regular constraints. We use for this a new result on lexicographical normal forms.