Product of Parikh matrices and commutativity (Q2909192)

The Parikh matrix of a word \(w\) over an ordered alphabet \(\Sigma_{n}=\left\{ a_{1}<\cdots<a_{n}\right\} \) is an upper triangular \(\left( n+1\right) \times\left( n+1\right) \) matrix with unit main diagonal and the entry at position \(i,j\), \(i<j\), being equal to the number of occurrences of the scattered subword \(a_{i}a_{i+1}\cdots a_{j-1}\) in \(w\). The mapping assigning to \(w\) its Parikh matrix is a monoid morphism. One of the questions widely studied in the literature is the ambiguity of the Parikh matrix mapping. The present paper investigates a closely related problem of pairs of words \(u,v\), such that \(uv\) and \(vu\) yield the same Parikh matrix. Though such pairs of commuting words are rather easily characterized in the case of a binary alphabet, the authors did not succeed to provide a characterization for the case of larger alphabets. They only describe some constructs leading to such pairs of words. The section dealing with commutators of words and languages -- sets of words commuting in the above sense with a given word or with some word in a given language -- does not bring truly non-trivial results.