Parikh matrices for powers of words

Abstract

Certain upper triangular matrices, termed as Parikh matrices, are often used in the combinatorial study of words. Given a word, the Parikh matrix of that word elegantly computes the number of occurrences of certain predefined subwords in that word. In this paper, we compute the Parikh matrix of any word raised to an arbitrary power. Furthermore, we propose canonical decompositions of both Parikh matrices and words into normal forms. Finally, given a Parikh matrix, the relation between its normal form and the normal forms of words in the corresponding M-equivalence class is established.

1 Introduction

The problem of finding the optimal number of subwords of a word needed to completely determine that word still remains open [11]. In the spirit of solving this problem, Mateescu et al. introduced Parikh matrices in [12] by generalizing the classical Parikh vectors [14]. In general, the Parikh matrix of a word is an upper triangular matrix which contains the number of occurrences of certain predefined subwords of that word. Despite storing more information about a word, not every Parikh matrix uniquely determines a word. Nevertheless, Parikh matrices and their variants [3, 7,8,9, 20] have opened up the door to various new investigations in the combinatorial study of words (for example, see [1, 2, 4,5,6, 10, 13, 15, 16, 18, 19, 21,22,23,24,25,26,27]).

Repetition in words has been intensively studied in the literature and it dates back to the works of Thue in the early 1900s. Often in the literature, a word is expressed as the power of another word; for instance the word murmur can be written as $(mur)^2$. In this paper, we deal with such powers of words in relative to Parikh matrices. Our main contributions would be as follows:

• (1) A general formula to obtain the Parikh matrix of any power of a given word;

• (2) A normal form of an arbitrary Parikh matrix (respectively word) obtained by decomposing that matrix (respectively word) in terms of powers of other Parikh matrices (respectively words).

The remainder of this paper is structured as follows. Section 2 provides the basic terminology and preliminaries. Section 3 deals with Parikh matrices of powers of words. Apart from presenting a general formula to obtain such Parikh matrices, the properties of these matrices are studied as well. In the next section, we propose a normal form of Parikh matrices sustained by a canonical decomposition. An algorithm to obtain this normal form is presented for Parikh matrices over the binary alphabet. Section 5 proposes a normal form of words, analogous to the one for Parikh matrices. The relation between the normal form of an arbitrary Parikh matrix and the normal forms of the words represented by that matrix is then established. Our conclusions follow after that.

2 Preliminaries

The set of all positive integers is denoted by ${\mathbb {N}}$.

Suppose $\Sigma$ is a finite and nonempty alphabet. The set of all words over $\Sigma$ is denoted by $\Sigma ^*$ and $\lambda$ is the unique empty word. Let $\Sigma ^+$ denote the set $\Sigma ^*\backslash \{\lambda \}$. If $v,w\in \Sigma ^*$, the concatenation of v and w is denoted by vw. An ordered alphabet is an alphabet $\Sigma =\{a_1,a_2,\ldots ,a_s\}$ with an ordering on it. For example, if $a_1<a_2<\cdots <a_s$, then we may write $\Sigma =\{a_1<a_2<\cdots <a_s\}$. For convenience, we shall frequently abuse notation and use $\Sigma$ to denote both the ordered alphabet and its underlying alphabet.

A word v is a scattered subword (or simply subword) of $w\in \Sigma ^*$ if and only if there exist $x_1,x_2,\ldots , x_n$, $y_0, y_1, \ldots ,y_n\in \Sigma ^*$ (possibly empty) such that $v=x_1x_2\cdots x_n \text { and } w=y_0x_1y_1\cdots y_{n-1}x_ny_n$. If the letters in v occur contiguously in w (that is $y_1=y_2=\cdots =y_{n-1}=\lambda$), then v is a factor of w. The number of occurrences of a word v as a subword of w is denoted by $\vert w\vert _v$. Two occurrences of v are considered different if and only if they differ by at least one position of some letter. For example, $\vert abab\vert _{ab}=3$ and $\vert abcabc\vert _{abc}=4$. By convention, $\vert w\vert _{\lambda }=1$ for all $w\in \Sigma ^*$. The reader is referred to [17] for language theoretic notions not detailed here.

For any integer $n\ge 2$, let $\mathcal {M}_n$ denote the multiplicative monoid of $n\times n$ upper triangular matrices with nonnegative integral entries and unit diagonal. For a matrix X, we denote its (i, j)-entry by $X_{i,j}$.

Definition 2.1

Suppose $\Sigma =\{a_1<a_2< \cdots <a_s\}$ is an ordered alphabet, where $s\ge 2$. The Parikh matrix mapping with respect to $\Sigma$, denoted by $\Psi _{\Sigma }$, is the morphism

$$\begin{aligned} \Psi _{\Sigma }: \Sigma ^*\rightarrow \mathcal {M}_{s+1} \end{aligned}$$

defined as follows: $\Psi _{\Sigma }(\lambda )=I_{s+1}$; if $\Psi _{\Sigma }(a_q)=M$, then $M_{i,i}=1$ for each $1\le i\le s+1$, $M_{q,q+1}=1$ and all other entries of the matrix $\Psi _{\Sigma }(a_q)$ are zero. Matrices of the form $\Psi _{\Sigma }(w)$ for $w\in \Sigma ^*$ are called Parikh matrices. We denote by $\mathcal {P}_{\Sigma }$ the set of all Parikh matrices with respect to $\Sigma$ and let $\mathcal {P}_{\Sigma }^+=\mathcal {P}_{\Sigma }\backslash \{I_{s+1}\}$.

Theorem 2.2

[12] Suppose $\Sigma =\{a_1<a_2< \cdots <a_s\}$ is an ordered alphabet and $w\in \Sigma ^*$. The matrix $\Psi _{\Sigma }(w)=M$ has the following properties:

• $M_{i,i}=1$ for each $1\le i \le s+1$;

• $M_{i,j}=0$ for each $1\le j<i\le s+1$;

• $M_{i,j+1}=\vert w \vert _{a_ia_{i+1}\cdots a_j}$ for each $1\le i\le j \le s$.

Remark 2.3

Suppose $\Sigma =\{a_1<a_2< \cdots <a_s\}$. The Parikh vector $\Psi (w)=(|w|_{a_1},|w|_{a_2},\ldots ,|w|_{a_s})$ of a word $w\in \Sigma ^*$ is contained in the second diagonal of the Parikh matrix $\Psi _\Sigma (w)$.

Example 2.4

Suppose $\Sigma =\{a<b<c\}$ and $w=ababcc$. Then

$$\begin{aligned} \Psi _{\Sigma }(w)&=\Psi _{\Sigma }(a)\Psi _{\Sigma }(b)\Psi _{\Sigma }(a)\Psi _{\Sigma }(b)\Psi _{\Sigma }(c)\Psi _{\Sigma }(c)\\&= \begin{pmatrix} 1 &{}\quad 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{pmatrix} \begin{pmatrix} 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{pmatrix} \cdots \begin{pmatrix} 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 1\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}\\&= \begin{pmatrix} 1 &{}\quad 2 &{}\quad 3 &{}\quad 6 \\ 0 &{}\quad 1 &{}\quad 2 &{}\quad 4\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 2\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{pmatrix} =\begin{pmatrix} 1 &{}\quad \vert w\vert _a &{}\quad \vert w\vert _{ab} &{}\quad \vert w\vert _{abc} \\ 0 &{}\quad 1 &{}\quad \vert w\vert _b &{}\quad \vert w\vert _{bc}\\ 0 &{}\quad 0 &{}\quad 1 &{}\quad \vert w\vert _c\\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}. \end{aligned}$$

The following is a basic property used to decide whether a matrix in $\mathcal {M}_3$ is a Parikh matrix.

Theorem 2.5

(see [13]) Suppose $M\in \mathcal {M}_3$. The matrix M is a Parikh matrix if and only if $M_{1,3}\le M_{1,2}\cdot M_{2,3}$.

Definition 2.6

Suppose $\Sigma$ is an ordered alphabet. Two words $w,w'\in \Sigma ^*$ are M-equivalent, denoted by $w\equiv _Mw'$, iff $\Psi _{\Sigma }(w)=\Psi _{\Sigma }(w')$. A word $w\in \Sigma ^*$ is M-ambiguous iff it is M-equivalent to another distinct word. Otherwise, w is M-unambiguous. We denote the M-equivalence class of a word $w\in \Sigma ^*$ by $C_w$.

3 Powers of Parikh matrices

The following result can be used to compute any power of a given matrix in $\mathcal {M}_n$ where integer $n\ge 2$. In particular, since every Parikh matrix is a matrix in $\mathcal {M}_n$ for some integer $n\ge 2$, this result can be applied to it as well.

Theorem 3.1

For every integer $m\ge 1$, $n\ge 2$, and $X \in \mathcal {M}_n$,

$$\begin{aligned} \displaystyle (X^m)_{i,j}= {\left\{ \begin{array}{ll} \sum \nolimits _{t=1}^{j-i} \left( {\begin{array}{c}m\\ t\end{array}}\right) \underbrace{\sum \limits _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j} }_{\text {understood to be } X_{i,j} \text { when } t=1} &{}\quad \text { if }\ 1\le i<j\le n,\\ 1 &{}\quad \text { if }\ 1\le i=j \le n,\\ 0 &{}\quad \text { if }\ 1\le j<i\le n. \end{array}\right. } \end{aligned}$$

Proof

We prove by induction on the power m. The base step is obvious. For the induction step, we only consider the case $i<j$ as the other two cases trivially hold. We have

$$\begin{aligned} (X^{m+1})_{i,j}&=\sum _{l=1}^{n} (X^m)_{i,l} X_{l,j} \nonumber \\&= \sum _{l=i}^{j} (X^m)_{i,l} X_{l,j} \nonumber \\&=X_{i,j} + \sum _{l=i+1}^{j-1} (X^m)_{i,l} X_{l,j}+ (X^{m})_{i,j }. \end{aligned}$$

(*)

Now,

$$\begin{aligned} \sum _{l=i+1}^{j-1} (X^m)_{i,l} X_{l,j}&=\sum _{l=i+1}^{j-1} \left[ \sum \limits _{t=1}^{l-i} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<l} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},l}\right] X_{l,j}\\&=\sum _{l=i+1}^{j-1} \sum \limits _{t=1}^{l-i} \left[ \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<l} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},l} X_{l,j}\right] \\&=\sum _{t=1}^{j-i-1} \sum _{l=i+t}^{j-1} \left[ \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<l} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},l} X_{l,j}\right] \\&=\sum _{t=1}^{j-i-1} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{l=i+t}^{j-1} \; \sum _{i<k_1<k_2<\cdots<k_{t-1}<l} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},l} X_{l,j}\\&=\sum _{t=1}^{j-i-1} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<l<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},l} X_{l,j}\\&=\sum _{t=1}^{j-i-1} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t}<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t},j} \\&=\sum _{t=2}^{j-i} \left( {\begin{array}{c}m\\ t-1\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j}\\&=-X_{i,j}+ \sum _{t=1}^{j-i} \left( {\begin{array}{c}m\\ t-1\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j}. \end{aligned}$$

(**)

(The third equality is obtained by interchanging the order of summation.) Since $\left( {\begin{array}{c}m+1\\ t\end{array}}\right) =\left( {\begin{array}{c}m\\ t-1\end{array}}\right) +\left( {\begin{array}{c}m\\ t\end{array}}\right)$, the induction step is complete because by combining $(*)$ and $(**)$, we have

$$\begin{aligned} (X^{m+1})_{i,j}=\sum _{t=1}^{j-i} \left[ \left( {\begin{array}{c}m\\ t-1\end{array}}\right) +\left( {\begin{array}{c}m\\ t\end{array}}\right) \right] \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j}. \end{aligned}$$

$\square$

Since every Parikh matrix is in $\mathcal {M}_n$ for some integer $n\ge 3$, the Parikh matrix of a word to the power of m (where m is a positive integer) can be computed by Theorem 3.1. The following example illustrates this.

Example 3.2

Consider the word abb in $\{a<b\}^*$. Suppose m is a positive integer. Then the Parikh matrix of the word $(abb)^m$ can be computed as follows:

$$\begin{aligned} \Psi _{\Sigma }((abb)^m)=(\Psi _{\Sigma }(abb))^m&=\begin{pmatrix} 1 &{}\quad 1 &{}\quad 2\\ 0 &{}\quad 1 &{}\quad 2\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^m\\&=\begin{pmatrix} 1 &{}\quad m\cdot 1 &{}\quad m\cdot 2+\left( {\begin{array}{c}m\\ 2\end{array}}\right) \cdot 1\cdot 2\\ 0 &{}\quad 1 &{}\quad m\cdot 2\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}\\&=\begin{pmatrix} 1 &{}\quad m &{}\quad m^2+m\\ 0 &{}\quad 1 &{}\quad 2m\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}. \end{aligned}$$

Definition 3.3

Suppose m and n are positive integers such that $n\ge 2$. We define the function $f_m:\mathcal {M}_n\rightarrow \mathcal {M}_n$ by $f_m(X)=X^m$ for all $X\in \mathcal {M}_n$.

If X is a Parikh matrix, then clearly $f_m(X)$ is a Parikh matrix as well. However, the converse is not necessarily true. In fact, the following is a consequence of Theorem 2.5 and Theorem 3.1 for the binary alphabet which can be used to determine whether $f_m(X)$ is a Parikh matrix.

Proposition 3.4

Suppose $X\in \mathcal {M}_3$ and m is a positive integer. Let $X=\begin{pmatrix} 1 &{} x &{} z\\ 0 &{} 1 &{} y\\ 0 &{} 0 &{} 1 \end{pmatrix}$. The matrix $X^m$ is a Parikh matrix if and only if either of the following holds:

• (1) If either x or y is zero, then $z=0$;

• (2) Otherwise if both x and y are nonzero, then $\dfrac{z}{xy}\le \dfrac{m+1}{2}$.

Proof

The biconditional holds trivially for (1), thus it remains to show (2). By Theorem 3.1, we have $X^m=\begin{pmatrix} 1 &{} mx &{} mz+\dfrac{m(m-1)}{2}xy\\ 0 &{} 1 &{} my\\ 0 &{} 0 &{} 1 \end{pmatrix}$. By Theorem 2.5, the matrix $X^m$ is a Parikh matrix if and only if

$$\begin{aligned} mz+\dfrac{m(m-1)}{2}xy\le mx\cdot my. \end{aligned}$$

The above inequality can be reduced to $\dfrac{z}{xy}\le \dfrac{m+1}{2}$, thus the conclusion holds. $\square$

The following is immediate by Proposition 3.4.

Corollary 3.5

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |=2$. For every matrix $X\in \mathcal {M}_3$ with nonzero entries above the main diagonal, there exists a positive integer M such that $X^m\in \mathcal {P}_\Sigma ^+$ for all integers $m\ge M$.

Example 3.6

Let $\Sigma =\{a<b\}$. Consider the matrix $X=\begin{pmatrix} 1 &{} 2 &{} 9\\ 0 &{} 1 &{} 2\\ 0 &{} 0 &{} 1 \end{pmatrix}$. Then $X^4=\begin{pmatrix} 1 &{} 8 &{} 60\\ 0 &{} 1 &{} 8\\ 0 &{} 0 &{} 1 \end{pmatrix}\in \mathcal {P}_\Sigma$. It can easily be checked by using Theorem 2.5 or Proposition 3.4 that $X^{m}\not \in \mathcal {P}_\Sigma$ for all integers $1\le m<4$. An example of word $w\in \Sigma ^*$ with $\Psi _\Sigma (w)=X^4$ is $w=a^7b^4ab^4$.

The following result shows that for every positive integer m, the function $f_m$ is injective.

Theorem 3.7

Suppose m is a positive integer and $X,Y \in \mathcal {M}_n$ for some integer $n\ge 2$. If $X^m=Y^m$, then $X=Y$.

Proof

Suppose $X^m=Y^m$. We prove by strong induction that the second diagonal, the third diagonal and so forth of X and Y are equal, thus $X=Y$. For the base step (corresponding to the second diagonal), we need to show that $X_{i,j}=Y_{i,j}$ whenever $j-i=1$. (It is understood that $1\le i$ and $j\le n$ must hold.) Fix $1\le i\le n-1$. By Theorem 3.1, $(X^m)_{i,i+1}= m X_{i,i+1}$ and $(Y^m)_{i,i+1}= m Y_{i,i+1}$. Since $X^m=Y^m$, it follows that $X_{i,i+1}=Y_{i,i+1}$.

For the induction step, we need to show that $X_{i,j}=Y_{i,j}$ holds whenever $j-i=N+1$, assuming that $(X)_{i,j'}=(Y)_{i,j'}$ whenever $1\le j'-i\le N$. Fix $1\le i\le n-N-1$ and let $j=i+N+1$. By Theorem 3.1,

$$\begin{aligned} (X^m)_{i,j}= \sum \limits _{t=1}^{j-i} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j} . \end{aligned}$$

Therefore,

$$\begin{aligned} X_{i,j}&= (X^m)_{i,j}-\sum \limits _{t=2}^{j-i} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} X_{i ,k_1}X_{k_1,k_2}\cdots X_{k_{t-1},j}\\&= (Y^m)_{i,j}-\sum \limits _{t=2}^{j-i} \left( {\begin{array}{c}m\\ t\end{array}}\right) \sum _{i<k_1<k_2<\cdots<k_{t-1}<j} Y_{i,k_1}Y_{k_1,k_2}\cdots Y_{k_{t-1},j}=Y_{i,j}, \end{aligned}$$

thus the proof is complete. (Note that the last equality holds by our induction hypothesis and the assumption that $X^m=Y^m$.) $\square$

Corollary 3.8

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |\ge 2$ and $v,w\in \Sigma ^*$. Then either of the following holds:

• (1) $v^m\equiv _M w^m$ for all positive integers m;

• (2) $v^m\not \equiv _M w^m$ for all positive integers m.

Proof

If $v\equiv _M w$, it follows trivially that $v^m\equiv _M w^m$ for all integers m. Hence, it suffices to prove that if there exists an integer $m\ge 2$ such that $v^m\equiv _M w^m$, then $v\equiv _M w$. Suppose $v^m\equiv _M w^m$ for some integer $m\ge 2$. Then $(\Psi _{\Sigma }(v))^m=\Psi _{\Sigma }(v^m)=\Psi _{\Sigma }(w^m)=(\Psi _{\Sigma }(w))^m$. Since $\Psi _{\Sigma }(v),\Psi _{\Sigma }(w)\in \mathcal {M}_{|\Sigma |+1}$, by Theorem 3.7, we have $\Psi _{\Sigma }(v)=\Psi _{\Sigma }(w)$ and thus $v\equiv _M w$. $\square$

We end this section by the following observation on the M-equivalence class of an arbitrary power of any word.

Proposition 3.9

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |\ge 2$ and $w\in \Sigma ^*$. For every positive integer m, we have $|C_{w^m}|\ge |C_w|^m$.

Proof

Fix a positive integer m. If $w_i\equiv _M w$ for all integers $1\le i\le m$, then $w^m=\underbrace{www\cdots w}_{m\text { times}} \equiv _M w_1w_2\cdots w_m$. Thus, $|C_{w^m}|\ge \underbrace{|C_w||C_w|\,\cdots \, |C_w|}_{m \text { times}}=|C_w|^m$. $\square$

Remark 3.10

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |=2$, $w\in \Sigma ^+$ and m is a positive integer. If $|C_{w^m}|=|C_w|^m$, then $|C_w|=1$. The converse however does not hold. For instance, let $w=aba$ (clearly, $|C_w|=1$). Then, $C_{w^2}=\{abaaba,aabbaa,baaaab\}$, therefore $|C_{w^2}|=3$.

4 A normal form of Parikh matrices

Suppose $\Sigma$ is an ordered alphabet. In this section, given a Parikh matrix $M\in \mathcal {P}_{\Sigma }$, we aim to decompose M into a product of some other Parikh matrices, each raised to a certain power. For Parikh matrices with entries large enough, the following decomposition is interesting.

Definition 4.1

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |=s$ and $M\in \mathcal {P}_{\Sigma }^+$.

• Define $\mu (M)=\max \{ n\in \mathbb {N}\,\,|\, M=A\cdot B^n \text { for some }A\in \mathcal {P}_{\Sigma } \text { and } B\in \mathcal {P}_{\Sigma }^+\}$.

• Define $\sigma (M)$ to be the sum of the entries in the second diagonal of M.

• Define $\vartheta (M)$ as follows:

  • if $\mu (M)=1$, then $\vartheta (M)$ is defined to be the minimum element of the following set:

    $$\begin{aligned} \{\sigma (B)\,\,|\,\,B\in \mathcal {P}_{\Sigma }^+ \text { and } M=A\cdot B \text { for some } A\in \mathcal {P}_\Sigma ^+\}\text { with }\mu (A)\ne 1\}, \end{aligned}$$

    provided it is nonempty; otherwise, it is defined to be $\sigma (M)$;

  • if $\mu (M)>1$, then $\vartheta (M)$ is defined to be the maximum element of the following set:

    $$\begin{aligned} \{\sigma (B)\,\,|\,\, B\in \mathcal {P}_{\Sigma }^+ \text { and } M=A\cdot B^{\mu (M)} \text { for some } A\in \mathcal {P}_\Sigma \}. \end{aligned}$$

• Define $S_M=\{(A,B,\mu (M))\,\,|\, A\in \mathcal {P}_\Sigma \text { and } B\in \mathcal {P}_{\Sigma }^+ \text { with } M=A\cdot B^{\mu (M)}\text { and}$$\sigma (B)=\vartheta (M)\}$.

Let k be a nonnegative integer. For every integer $0\le i\le k$, suppose $B_i\in \mathcal {P}_\Sigma$ and $n_i\in \mathbb {N}$. We say that $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_0^{n_0}$ is a rl-Parikh normal form of M if and only if the following holds:

Let $A_0=M$, $A_i=B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_i^{n_i}$ ($1\le i\le k$) and $A_{k+1}=I_{s+1}$.

Then $(A_{i+1},B_i,n_i)\in S_{A_i}$ for all $0\le i\le k$.

Equivalently, we say that M is rl-Parikh normalized to the form $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_0^{n_0}$.

Remark 4.2

The requirement $B\in \mathcal {P}_{\Sigma }^+$ in the first item of Definition 4.1 eliminates the trivial decomposition of a Parikh matrix M into $M=M\cdot I_{s+1}^n$ at each stage as n does not have an upper bound in this case.

Remark 4.3

Suppose $\Sigma$ is an ordered alphabet and $M\in \mathcal {P}_\Sigma ^+$. Let $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_0^{n_0}$ be a rl-Parikh normal form of M. For any integer $0\le i\le k$, the form $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_i^{n_i}$ is a rl-Parikh normal form of the matrix $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_i^{n_i}$.

Remark 4.4

Suppose $\Sigma$ is an ordered alphabet and $M\in \mathcal {P}_\Sigma ^+$. If $M=A\cdot B^n$ for some $A\in \mathcal {P}_\Sigma$, $B\in \mathcal {P}_\Sigma ^+$ and positive integer n, then $\mu (M)\ge n$.

One can see that the rl-Parikh normal form of a Parikh matrix is not necessarily unique. For a trivial example, let $\Sigma =\{a<b\}$ and consider the word $w=abba$. Then, the matrix $\Psi _\Sigma (w)$ has two rl-Parikh normal forms, which are $\Psi _\Sigma (a)[\Psi _\Sigma (b)]^2\Psi _\Sigma (a)$ and $\Psi _\Sigma (b)[\Psi _\Sigma (a)]^2\Psi _\Sigma (b)$.

The following is a feasible approach to find the Parikh normal form(s) of a Parikh matrix for the binary alphabet. (Here, we are only interested in “nontrivial” cases where both entries in the second diagonal are nonzero.)

At each stage of decomposition, given a Parikh matrix $M=\begin{pmatrix} 1 &{} u &{} t\\ 0 &{} 1 &{} v\\ 0 &{} 0 &{} 1 \end{pmatrix}$ with integers $u,v>0$, we aim to find two other Parikh matrices $A=\begin{pmatrix} 1 &{} p &{} r\\ 0 &{} 1 &{} q\\ 0 &{} 0 &{} 1 \end{pmatrix}$ and $B=\begin{pmatrix} 1 &{} x &{} z\\ 0 &{} 1 &{} y\\ 0 &{} 0 &{} 1 \end{pmatrix}$ such that for some positive integer n, we have $M=A\cdot B^n$ where $(A,B,n)\in S_M$.

By Theorem 3.1, we have $B^n=\begin{pmatrix} 1 &{} nx &{} nz+\left( {\begin{array}{c}n\\ 2\end{array}}\right) xy\\ 0 &{} 1 &{} ny\\ 0 &{} 0 &{} 1 \end{pmatrix}$, thus it follows that $A\cdot B^n=\begin{pmatrix} 1 &{} p+nx &{} r+nz+npy+\left( {\begin{array}{c}n\\ 2\end{array}}\right) xy\\ 0 &{} 1 &{} q+ny\\ 0 &{} 0 &{} 1 \end{pmatrix}$. Since $M=A\cdot B^n$, the following system holds:

${\left\{ \begin{array}{ll} p+nx=u,\\ q+ny=v,\\ r+nz+npy+\left( {\begin{array}{c}n\\ 2\end{array}}\right) xy=t.\\ \end{array}\right. }$

Furthermore, by Theorem 2.5, we have

$r\le pq, z\le xy$.

We propose the following algorithm to find the solution to the above system.

Clearly, each $z\in Z$ corresponds to some $A\in \mathcal {P}_\Sigma$, $B\in \mathcal {P}_\Sigma ^+$ and positive integer n such that $M=A\cdot B^n$ and $n=\mu (M)$. It remains to choose the triplet(s) (A, B, n) satisfying the equality $\sigma (B)=\vartheta (M)$ (see Definition 4.1).

Example 4.5

The Parikh matrix

$$\begin{aligned} M=\begin{pmatrix} 1 &{}\quad 8 &{}\quad 16\\ 0 &{}\quad 1 &{}\quad 3\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix} \end{aligned}$$

has the following Parikh normal forms:

• (1) $\begin{pmatrix} 1 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^4\cdot \begin{pmatrix} 1 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 1\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}\cdot \begin{pmatrix} 1 &{}\quad 2 &{}\quad 1\\ 0 &{}\quad 1 &{}\quad 1\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^2;$

• (2) $\begin{pmatrix} 1 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^2\cdot \begin{pmatrix} 1 &{}\quad 0 &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 1\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}\cdot \begin{pmatrix} 1 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^2\cdot \begin{pmatrix} 1 &{}\quad 2 &{}\quad 2\\ 0 &{}\quad 1 &{}\quad 1\\ 0 &{}\quad 0 &{}\quad 1 \end{pmatrix}^2.$

Theorem 4.6

Suppose $\Sigma$ is an ordered alphabet. If $w\in \Sigma ^*$ is M-unambiguous, then the rl-Parikh normal form of $\Psi _\Sigma (w)$ is unique.

Proof

Suppose w is M-unambiguous and let $\Psi _\Sigma (w)=M$. We argue by contradiction. Assume there exist two distinct rl-Parikh normal forms of M; let them be $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_0^{n_0}$ and $C_{j}^{m_{kj}}C_{j-1}^{m_{j-1}}\cdots C_0^{m_0}$ respectively. Since they are distinct, it follows that there exists an integer $0\le l\le \min \{j,k\}$ such that

• (1) $n_i=m_i$ and $B_i=C_i$ for all integers $0\le i\le l-1$;

• (2) $n_l\ne m_l$ or $B_l\ne C_l$.

Let $A\!=\!B_{l-1}^{n_{l-1}}B_{l-2}^{n_{l-2}}\cdots B_0^{n_0}\!=C_{l-1}^{m_{l-1}}C_{l-2}^{m_{l-2}}\cdots C_0^{m_0}$, $B'\!=\!B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_l^{n_l}$ and $C'=C_{j}^{m_{kj}}C_{j-1}^{m_{j-1}}\cdots C_l^{m_l}$. Then, we have $B'\cdot A=M=C'\cdot A$. Since Parikh matrices are invertible, it follows that $B'=C'$. By Remark 4.3, it holds that $n_l=\mu (B')=\mu (C')=m_l$ and $\sigma (B_l)=\vartheta (B')=\vartheta (C')=\sigma (C_l)$. Since $n_l=m_l$, by (2), it must be the case that $B_l\ne C_l$.

Let $v,v'\in \Sigma$ be such that $\Psi _\Sigma (v)=B_l$ and $\Psi _\Sigma (v')=C_l$. Note that $v\ne v'$ because $B_l\ne C_l$. Also, $|v|=|v'|$ because $\sigma (B_l)=\sigma (C_l)$. Let $u,u',y\in \Sigma ^*$ be such that $\Psi _\Sigma (u)=B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_{l+1}^{n_{l+1}}$, $\Psi _\Sigma (u')=C_{j}^{m_{j}}C_{j-1}^{m_{j-1}}\cdots C_{l+1}^{m_{l+1}}$ and $\Psi _\Sigma (y)=A$. Then, $\Psi _\Sigma (uvy)=B'A=M=C'A=\Psi _\Sigma (u'v'y)$. Since $|v|=|v'|$ but $v\ne v'$, it follows that uvy and $u'v'y$ are distinct words. However, this gives us a contradiction as w is M-unambiguous. Thus our conclusion holds. $\square$

Our final result in this section is a characterization of the following class of Parikh matrices. One can see that this class of Parikh matrices arises naturally by Definition 4.1.

Definition 4.7

Suppose $\Sigma$ is an ordered alphabet and $M\in \mathcal {P}_\Sigma$. We say that M is a primitive Parikh matrix if and only if the only rl-Parikh normal form of M is M itself.

Theorem 4.8

Suppose $\Sigma$ is an ordered alphabet and $M\in \mathcal {P}_\Sigma$. The matrix M is a primitive Parikh matrix if and only if every $w\in \Sigma ^*$ with $\Psi _\Sigma (w)=M$ is square-free.

Proof

This is straightforward by Definitions 4.1 and 4.7. $\square$

5 A normal form of words

In this section, we introduce a notion analogous to the one in Sect. 4—in the perspective of words.

Definition 5.1

Suppose $\Sigma$ is an alphabet and $w\in \Sigma ^+$.

• Define $R_w=\{(u,v,n)\in \Sigma ^*\times \Sigma ^+\times \mathbb {N}\,\,|\,\,w=uv^n\}$.

• Define $\tau (w)=\max \{n\in \mathbb {N}\,\,|\,(u,v,n)\in R_w \text { for some }u\in \Sigma ^* \text { and } v\in \Sigma ^+\}$.

• Define $\theta (w)$ as follows:

  • if $\tau (w)=1$, then $\theta (w)$ is defined to be the minimum element of the following set:

    $$\begin{aligned} \{|v|\,\,|\,\,v\in \Sigma ^+ \text { and } w=uv \text { for some } u\in \Sigma ^+\text { with }\tau (u)\ne 1\}, \end{aligned}$$

    provided it is nonempty; otherwise $\theta (w)=|w|$.

  • if $\tau (w)>1$, then $\theta (w)$ is defined to be the maximum element of the following set:

    $$\begin{aligned} \{|v|\,\,|\,\,v\in \Sigma ^+ \text { and } w=uv^{\tau (w)}\text { for some } u\in \Sigma ^+\}. \end{aligned}$$

• Define $\rho (w)=(u',v',\tau (w))$ to be the unique triplet in $R_w$ such that $|v'|=\theta (w)$.

• Let $w_0=w$ and $(w_1,v_0,n_0)=\rho (w_0)$. For all integers $i\ge 1$ and while $w_i\ne \lambda$, recursively define $(w_{i+1},v_i,n_i)=\rho (w_i)$. Let $k\ge 1$ be the largest integer such that $w_k\ne \lambda$.

We say that $v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$ is the rl-Parikh normal form of w, denoted by ${{\mathrm{Pn}}}_r(w)$. Equivalently, we say that w is rl-Parikh normalized to the form $v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$.

Remark 5.2

The requirement $v\in \Sigma ^+$ in the first item of Definition 5.1 eliminates the trivial decomposition of a word w into $w=w\cdot \lambda ^n$ at each stage as n does not have an upper bound in this case.

Remark 5.3

Suppose $\Sigma$ is an ordered alphabet and $w\in \Sigma ^+$. Let ${{\mathrm{Pn}}}_r(w)=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$. For any integer $0\le i\le k$, ${{\mathrm{Pn}}}_r(v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}$.

Remark 5.4

Suppose $\Sigma$ is an ordered alphabet and $w\in \Sigma ^+$. If $w=uv^n$ for some $u\in \Sigma ^*$, $v\in \Sigma ^+$ and positive integer n, then $\tau (w)\ge n$.

Example 5.5

Suppose $\Sigma =\{a,b,c\}$. Then, we have ${{\mathrm{Pn}}}_r(bbabbabba)=(bba)^3$, ${{\mathrm{Pn}}}_r(acccabab)=ac^3(ab)^2$ and ${{\mathrm{Pn}}}_r(cbcbbaabaaba)=(cb)^2ba(aba)^2$. In the last case, it is understood that the rl-Parikh normal form of the word cbcbbaabaaba is $(cb)^2(ba)^1(aba)^2$ and not $(cb)^2b^1a^1(aba)^2$.

The next theorem establishes a significant relation between the rl-Parikh normal form of a word and the rl-Parikh normal form(s) of the Parikh matrix corresponding to that word.

Definition 5.6

Suppose $\Sigma$ is an alphabet and $w,w'\in \Sigma ^*$ are distinct words such that w and $w'$ are M-equivalent. Let ${{\mathrm{Pn}}}_r(w)=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$ and ${{\mathrm{Pn}}}_r(w')={y}_j^{m_j}{y}_{j-1}^{m_{j-1}}\cdots {y}_0^{m_0}$. We write $w\prec w'$ if and only if there exists an integer $0\le N\le \min \{j,k\}$ such that

• (1) $n_i=m_i$ and $v_i=y_i$ for all integers $0\le i\le N-1$; and

• (2) either of the following holds:

  • (i) $n_N<m_N$;

  • (ii) $n_N=m_N=1$ and $|v_N|>|y_N|$;

  • (iii) $n_N=m_N>1$ and $|v_N|<|y_N|$.

Definition 5.7

Suppose $\Sigma$ is an ordered alphabet. We say that the word w is maximal with respect to the relation $\prec$ (or simply $\prec$-maximal), if and only if there exists no other word $w'\in C_w$ such that $w\prec w'$.

Theorem 5.8

Suppose $\Sigma$ is an ordered alphabet and $w\in \Sigma ^*$. Let ${{\mathrm{Pn}}}_r(w)=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$. If w is $\prec$-maximal, then $[\Psi _\Sigma (v_{k})]^{n_{k}}[\Psi _\Sigma (v_{k-1})]^{n_{k-1}}\cdots [\Psi _\Sigma (v_0)]^{n_0}$ is an rl-Parikh normal form of $\Psi _\Sigma (w)$.

Proof

(The notations used here follow from Definitions 4.1 and 5.1.)

Suppose w is $\prec$-maximal. Let $A_0=\Psi _\Sigma (w)$, $A_i=[\Psi _\Sigma (v_{k})]^{n_{k}}[\Psi _\Sigma (v_{k-1})]^{n_{k-1}}\cdots$$[\Psi _\Sigma (v_i)]^{n_i}$ ($1\le i\le k$) and $A_{k+1}=I_{s+1}$. By Definition 4.1, we need to show that $(A_{i+1},\Psi _\Sigma (v_i),n_i)\in S_{A_i}$ for all $0\le i\le k$.

Fix an arbitrary index i. To deduce that $(A_{i+1},\Psi _\Sigma (v_i),n_i)\in S_{A_i}$, we need to show that

$$\begin{aligned} (\mathrm{i})\; A_{i+1}\cdot [\Psi _\Sigma (v_i)]^{n_i}=A_i; (\mathrm{ii})\; n_i=\mu (A_i);\;\mathrm{and \; (iii) }\;\sigma (\Psi _\Sigma (v_i))=\vartheta (A_i). \end{aligned}$$

(i) We have

$$\begin{aligned} A_{i+1}\cdot [\Psi _\Sigma (v_i)]^{n_i}&=\underbrace{[\Psi _\Sigma (v_{k})]^{n_{k}}[\Psi _\Sigma (v_{k-1})]^{n_{k-1}}\cdots [\Psi _\Sigma (v_{i+1})]^{n_{i+1}}}_{A_{i+1}}\cdot [\Psi _\Sigma (v_i)]^{n_i}\\&=[\Psi _\Sigma (v_{k})]^{n_{k}}[\Psi _\Sigma (v_{k-1})]^{n_{k-1}}\cdots [\Psi _\Sigma (v_{i})]^{n_{i}}=A_i. \end{aligned}$$

(ii) We argue by contradiction. Assume $n_i\ne \mu (A_i)$. By definition, if $n_i>\mu (A_i)$, then $n_i>\max \{ n\in \mathbb {N}\,\,|\, A_i=A\cdot B^n \text { for some }A\in \mathcal {P}_{\Sigma } \text { and } B\in \mathcal {P}_{\Sigma }^+\}$. This is a contradiction as $A_i=A_{i+1}\cdot [\Psi _\Sigma (v_i)]^{n_i}$.

Assume $n_i<\mu (A_i)$. By definition, there exist $A\in \mathcal {P}_\Sigma$ and $B\in \mathcal {P}_\Sigma ^+$ such that $A_i=A\cdot B^{\mu (A_i)}$. Choose $u\in \Sigma ^*$ and $v\in \Sigma ^+$ such that $\Psi _\Sigma (u)=A$ and $\Psi _\Sigma (v)=B$. Thus we have $\Psi _\Sigma (uv^{\mu (A_i)})=A_i=\Psi _\Sigma (v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})$. By Remark 5.3, it holds that ${{\mathrm{Pn}}}_r(v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}$.

Let $w'=uv^{\mu (A_i)}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_0^{n_0}$. Since $uv^{\mu (A_i)}\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}$, it follows by the right invariance of M-equivalence that

$$\begin{aligned} w'=\underbrace{uv^{\mu (A_i)}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1}}_{u'} v_0^{n_0}\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1}v_0^{n_0}=w. \end{aligned}$$

Let ${{\mathrm{Pn}}}_r(w')=y_{k'}^{m_{k'}}y_{k'-1}^{m_{k'-1}}\cdots y_1^{m_1}y_0^{m_0}$. Since $w'=u'v_0^{n_0}$, by Remark 5.4, it follows that $m_0\ge n_0$. If $m_0>n_0$, then by Definition 5.6, we have $w\prec w'$ which is a contradiction as w is maximal. Thus $m_0=n_0$.

Case 1

$m_0=n_0=1$.

Since $m_0=1$, by Definition 5.1, it follows that $m_1=\tau (y_{j}^{m_{j}}y_{j-1}^{m_{j-1}}\cdots y_1^{m_1})>1$. Thus, by Definition 5.1 again, it holds that $|y_0|=\theta (w')\le |v_0|$. If $|y_0|<|v_0|$, then by Definition 5.6, we have $w\prec w'$ which is a contradiction. Thus $|y_0|=|v_0|$.

Case 2

$m_0=n_0>1$.

Then, by Definition 5.1, it follows that $|y_0|=\theta (w')\ge |v_0|$. If $|y_0|>|v_0|$, then by Definition 5.6, we have $w\prec w'$ which is a contradiction. Thus, $|v_0|=|y_0|$.

In both cases, we have $|v_0|=|y_0|$. Since both $v_0$ and $y_0$ are suffixes of the word $v_i^{n_i}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1}v_0^{n_0}$, it follows that $v_0=y_0$. Since $n_0=m_0$ and $v_0=y_0$, by similar argument as above, it can be shown that $m_1=n_1$ and $v_1=y_1$. Arguing continuously like this, we have $y_k=v_k$ and $m_k=n_k$ for all $i-1\le k\le 0$.

By our assumption, we have $n_i<\mu (A_i)$. Meanwhile by Definition 5.1, we have $m_i=\tau (uv^{\mu (A_i)})\ge \mu (A_i)$. Thus, $n_i<\mu (A_i)\le m_i$. By Definition 5.6, it follows that $w\prec w'$ which is a contradiction. Therefore, we conclude that $n_i=\mu (A_i)$.

(iii) Note that since the second diagonal of the Parikh matrix of a word contains the Parikh vector of that word, it follows that $\sigma (\Psi _\Sigma (x))=|x|$ for any $x\in \Sigma ^*$. We now argue by contradiction. Assume $\sigma (\Psi _\Sigma (v_i))\ne \vartheta (A_i)$.

Case 1

$\mu (A_i)=n_i=1.$

Consider the set

$$\begin{aligned} \Gamma =\{\sigma (B)\,\,|\,\,B\in \mathcal {P}_{\Sigma }^+ \text { and } A_i=A\cdot B \text { for some } A\in \mathcal {P}_\Sigma ^+\text { with }\mu (A)\ne 1\} \end{aligned}$$

in Definition 4.1.

Case 1.1

The set $\Gamma$ is nonempty.

By Definition 4.1, it holds that $\vartheta (A_i)$ is the minimum element of the set $\Gamma$. Therefore, if $\sigma (\Psi _\Sigma (v_i))<\vartheta (A_i)$, then it is a contradiction as $A_i=A_{i+1}\cdot \Psi _\Sigma (v_i)$.

Assume $\sigma (\Psi _\Sigma (v_i))>\vartheta (A_i)$. Since set $\Gamma$ is nonempty, there exist $A,B\in \mathcal {P}_\Sigma ^+$ such that $A_i=A\cdot B$ with $\mu (A)\ne 1$ and $\sigma (B)=\vartheta (A_i)$. Since $\mu (A)\ne 1$, it follows that $A=A'\cdot B'^{n'}$ for some $A'\in \mathcal {P}_\Sigma$, $B'\in \mathcal {P}_\Sigma ^+$ and integer $n'>1$. Choose $u'\in \Sigma ^*$ and $v',v\in \Sigma ^+$ such that $\Psi _\Sigma (u')=A'$, $\Psi _\Sigma (v')=B'$ and $\Psi _\Sigma (v)=B$. Thus we have $\Psi _\Sigma (u'v'^{n'}v)=A_i=\Psi _\Sigma (v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i)$. Note that $|v|<|v_i|$ because

$$\begin{aligned} |v|=\sigma (\Psi _\Sigma (v))=\sigma (B)=\vartheta (A_i)<\sigma (\Psi _\Sigma (v_i))=|v_i|. \end{aligned}$$

Let $w'=u'v'^{n'}vv_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_0^{n_0}$. Since $u'v'^{n'}v\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_{i+1}^{n_{i+1}}v_i$, it follows by the right invariance of M-equivalence that

$$\begin{aligned} w'=u'v'^{n'}vv_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1} v_0^{n_0}\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_{i+1}^{n_{i+1}}v_iv_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1}v_0^{n_0}=w. \end{aligned}$$

Let ${{\mathrm{Pn}}}_r(w')=y_{k'}^{m_{k'}}y_{k'-1}^{m_{k'-1}}\cdots y_0^{m_0}$. By similar argument as in (ii), it can be shown that $y_j=v_j$ and $m_j=n_j$ for all $0\le j\le i-1$. Now, as for $m_i$, if $m_i>1=n_i$, then $w\prec w'$ by Definition 5.6 and thus a contradiction. On the other hand, if $m_i=1$, then since $n'>1$, it follows that $|y_i|=\theta (u'v'^{n'}v)\le |v|$. Since $|v|<|v_i|$, it follows that $|y_i|\le |v|<|v_i|$. By Definition 5.6, again it follows that $w\prec w'$ which is a contradiction.

Case 1.2

The set $\Gamma$ is empty.

Note that $A_i=[\Psi _\Sigma (v_{k})]^{n_{k}}[\Psi _\Sigma (v_{k-1})]^{n_{k-1}}\cdots [\Psi _\Sigma (v_i)]^{n_i}$. Since $n_i=1$ and the set $\Gamma$ is empty, it follows that $n_j=1$ for all $i\le j\le k$. Meanwhile, by Remark 5.3, it holds that ${{\mathrm{Pn}}}_r(v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}$. Therefore, since $n_j=1$ for all $i\le j\le k$, it must be the case that $i=k$. That is to say, $A_i=\Psi _\Sigma (v_i)$.

Since the set $\Gamma$ is empty, by Definition 4.1, we have $\vartheta (A_i)=\sigma (A_i)$. Then, $\vartheta (A_i)=\sigma (A_i)=\sigma (\Psi _\Sigma (v_i))$, thus a contradiction.

Case 2

$\mu (A_i)=n_i>1.$’

Then, by Definition 4.1, it holds that

$$\begin{aligned} \vartheta (A_i)=\max \{\sigma (B)\,\,|\,\,B\in \mathcal {P}_{\Sigma }^+ \text { and } A_i=A\cdot B^{n_i} \text { for some } A\in \mathcal {P}_\Sigma \}. \end{aligned}$$

Thus if $\sigma (\Psi _\Sigma (v_i))>\vartheta (A_i)$, then it is a contradiction as $A_i=A_{i+1}\cdot [\Psi _\Sigma (v_i)]^{n_i}$.

Assume $\sigma (\Psi _\Sigma (v_i))<\vartheta (A_i)$. Let $A\in \mathcal {P}_\Sigma$ and $B\in \mathcal {P}_\Sigma ^+$ be such that $A_i=A\cdot B^{n_i}$ with $\sigma (B)=\vartheta (A_i)$. Choose $u\in \Sigma ^*$ and $v\in \Sigma ^+$ such that $\Psi _\Sigma (u)=A$ and $\Psi _\Sigma (v)=B$. Thus we have $\Psi _\Sigma (uv^{n_i})=A_i=\Psi _\Sigma (v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})$. By Remark 5.4, it holds that $\tau (uv^{n_i})\ge n_i$. Assume $\tau (uv^{n_i})>n_i$. Then we have $uv^{n_i}=u'v'^{n'}$ for some $u\in \Sigma ^*$ and $v\in \Sigma ^+$ where $n'=\tau (uv^{n_i})$. However note that $A_i=\Psi _\Sigma (u')\cdot [\Psi _\Sigma (v')]^{n'}$ and $n'=\tau (uv^{n_i})> n_i=\mu (A_i)$. This is a contradiction by the definition of $\mu (A_i)$. Thus $\tau (uv^{n_i})=n_i$.

Let $w'=uv^{n_i}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_0^{n_0}$. Since $uv^{n_i}\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}$, it follows by the right invariance of M-equivalence that

$$\begin{aligned} w'=uv^{n_i}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1} v_0^{n_0}\equiv _Mv_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i}v_{i-1}^{n_{i-1}}v_{i-2}^{n_{i-2}}\cdots v_1^{n_1}v_0^{n_0}=w. \end{aligned}$$

Let ${{\mathrm{Pn}}}_r(w')=y_{k'}^{m_{k'}}y_{k'-1}^{m_{k'-1}}\cdots y_0^{m_0}$. By similar argument as in (ii), it can be shown that $y_k=v_k$ and $m_k=n_k$ for all $0\le k\le i-1$. Furthermore, we have $\tau (uv^{n_i})=n_i=\tau (v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_i^{n_i})$ and $|v|>|v_i|$. Thus by Definition 5.6, it follows that $w\prec w'$ which is a contradiction.

In both cases, we obtain a contradiction. Thus $\sigma (\Psi _\Sigma (v_i))=\vartheta (A_i)$. Since (i), (ii) and (iii) hold, our conclusion follows. $\square$

Example 5.9

Suppose $\Sigma =\{a<b\}$. Consider the Parikh matrix M stated in Example 4.5. That matrix M represents the following M-equivalent words:

$$\begin{aligned}&aaaaabbabaa,\,\,aaaabaabbaa,\,\,aaaababaaba,\,\,aaaabbaaaab,\,\,aaabaaababa,\\&aaabaabaaab,\,\,aabaaaaabba,\,\,aabaaaabaab,\,\,abaaaaaabab,\,\,baaaaaaaabb. \end{aligned}$$

Rewriting the above words in their respective Parikh normal forms, we have

$$\begin{aligned} \begin{array}{ccccc} a^5b^2aba^2, &{}\quad a^4ba^2b^2a^2, &{} \quad a^4b(aba)^2, &{} \quad a^4b^2a^4b, &{} \quad a^3ba^3(ba)^2\\ a(aab)^2a^3b, &{}\quad a^2ba^5b^2a, &{}\quad a^2ba^2(aab)^2, &{} \quad aba^5(ab)^2, &{} \quad ba^8b^2.\\ \end{array} \end{aligned}$$

Notice that $a^4b(aba)^2$ and $a^2ba^2(aab)^2$ are the only $\prec$-maximal words. Correspondingly, the only rl-Parikh normal forms of matrix M are

$$\begin{aligned}{}[\Psi _\Sigma (a)]^{4}[\Psi _\Sigma (b)][\Psi _\Sigma (aba)]^{2} \text { and } [\Psi _\Sigma (a)]^{2}[\Psi _\Sigma (b)][\Psi _\Sigma (a)]^{2}[\Psi _\Sigma (aab)]^{2}, \end{aligned}$$

which are in fact the matrices (1) and (2) in Example 4.5.

The following is the converse of Theorem 5.8.

Theorem 5.10

Suppose $\Sigma$ is an ordered alphabet with $|\Sigma |=s$ and $M\in \mathcal {P}_\Sigma$. Assume $B_{k}^{n_{k}}B_{k-1}^{n_{k-1}}\cdots B_0^{n_0}$ is an rl-Parikh normal form of M. Suppose $w\in \Sigma ^*$ such that $w=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$ where for every integer $0\le i\le k$, we have $v_i\in \Sigma ^+$ with $\Psi _\Sigma (v_i)=B_i$. Then, ${{\mathrm{Pn}}}_r(w)=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$ and w is $\prec$-maximal.

Proof

It can be shown that ${{\mathrm{Pn}}}_r(w)=v_{k}^{n_{k}}v_{k-1}^{n_{k-1}}\cdots v_0^{n_0}$ and w is $\prec$-maximal by referring to Definitions 5.1, 4.1, Remarks 4.3, 4.4 and arguing analogously to the proof of Theorem 5.8. However, the explicit proof of this theorem is not presented here as it resembles that of Theorem 5.8. $\square$

6 Conclusion

We have seen that Parikh matrices are versatile in the study of subword occurrences in words which are in the form of powers. In fact, by using Theorem 3.1, one can acquire information on the subword occurrences in arbitrary power of any word by just knowing the base word.

Definitions 4.1 and 5.1 can be modified in a way such that the decompositions commence from left to right. Accordingly, one could term the corresponding forms obtained as the lr-Parikh normal forms. For both Parikh matrices and words, it can then be studied to what extent the rl-Parikh normal forms and lr-Parikh normal forms are related to each other.

Last but not least, Proposition 3.9 is an interesting observation on the study of M-equivalence of powers of words, which we would further investigate in our future contribution. For $\Sigma =\{a<b<c\}$, we see that there exists $w\in \Sigma ^*$ satisfying the equality $|C_{w^2}|=|C_w|^2$ for arbitrary $|C_w|=N$. For the case $N=1$, consider the word $w=abcb$ while for the case $N>1$, consider the word $w=a^{N-1}cb$ (notice that $|C_w|=N$). In both cases, we have $|C_{w^2}|=|C_w|^2$. Thus it is intriguing to know whether the following general result holds:

$$\begin{aligned}&\textit{Suppose }\Sigma =\{a<b<c\} \textit{ and } w\in \Sigma ^*. \textit{ For any positive integer }m, \textit{ there exists }\\&\quad w\in \Sigma ^* \textit{ satisfying the equality }|C_{w^m}|=|C_w|^m \textit{ for arbitrary }|C_w|. \end{aligned}$$