The notion of isomorphism on stable AF-C^{\ast}-algebras is considered in this paper in the case when the corresponding Bratteli diagram is stationary, i.e. is associated with a single square primitive incidence matrix. A C^{\ast}-isomorphism induces an equivalence relation on these matrices, called C^{\ast}-equivalence. We show that the associated isomorphism equivalence problem is decidable, i.e. there is an algorithm that can be used to check in a finite number of steps whether two given primitive matrices are C^{\ast}-equivalent or not. Special cases of this problem will be considered in a forthcoming paper.