Criteria for the matrix equivalence of words

This paper investigates the criteria for deciding whether two words are matrix equivalent. Certain upper diagonal matrices, generally referred to as the Parikh matrices, have been widely investigated because of their usefulness in computing the numbers of subword occurrences and thereby characterizing words by numbers. However, apart from the binary alphabet, not much is known about the properties of the matrix equivalent words, that is, words possessing the same matrix. The paper investigates both the general criteria, as well as the criteria valid in natural special cases. An exhaustive solution is obtained for ternary alphabets.