# Algebraic Properties of Parikh Matrices of Binary Picture Arrays

Authors: Somnath Bera; Sastha Sriram; Atulya K. Nagar; Linqiang Pan; K. G. Subramanian
Journal: Journal of Mathematics
 (2020)

---

## Abstract

A word is a finite sequence of symbols. Parikh matrix of a word is an upper triangular matrix with ones in the main diagonal and nonnegative integers above the main diagonal which are counts of certain scattered subwords in the word. On the other hand, a picture array, which is a rectangular arrangement of symbols, is an extension of the notion of a word to two dimensions. Parikh matrices associated with a picture array have been introduced, and their properties have been studied. Here, we obtain certain algebraic properties of Parikh matrices of binary picture arrays based on the notions of power, fairness, and a restricted shuffle operator extending the corresponding notions studied in the case of words. We also obtain properties of Parikh matrices of arrays formed by certain geometric operations.


---

## Body

## 1. Introduction

“Combinatorics on words” [1] is a comparatively new branch of discrete mathematics with applications in many fields. The work [2] of the Norwegian mathematician Axel Thue (1863–1922) is considered to be the origin for the beginning of this new branch of mathematics. A finite word or simply a word is a finite sequence of symbols in a finite set called an alphabet. The Parikh vector [3] of a finite word, which has played a significant role in the theory of formal languages [3], expresses a numerical property of the word by counting the number of occurrences of the different symbols in the word.The recently introduced notion of the Parikh matrix [4] of a word over an ordered alphabet is an extension of the Parikh vector. The Parikh matrix of a word, which is based on subwords (also called scattered subwords) of the word, is a very interesting and effective tool in the study of certain numerical properties of the word. Intensive work (see, for example, [5–11]) has taken place in investigating properties of words based on associated Parikh matrices. Such theoretical studies have dealt with problems of great interest related to words such as inequalities on the numbers of occurrences of subwords, injectivity of the mapping involved in defining the Parikh matrix, and other directions [12]. An application of the Parikh matrix in message authentication is considered in [13].On the other hand, a picture array or simply an array, having a rectangular arrangement of symbols in rows and columns, is an extension of a word to two dimensions (2D) [3]. Several combinatorial properties of arrays have also been intensively investigated [14–20]. For instance, notions such as repetitions of subarrays in 2D arrays are studied in [15–17, 19], while periodicity in arrays is dealt with in [14, 18]. The notion of the Parikh matrix of a word has been extended to row and column Parikh matrices of picture arrays in [21], and their properties have been studied. The problem of reconstruction of 2D binary images has been studied [22] based on Parikh matrices.Here, we consider binary picture arrays and establish properties of the Parikh matrices of power of an array, fairness of an array, and a restricted shuffle operator on arrays, by extending the corresponding notions [20, 23, 24] investigated in the case of words. We also obtain properties of Parikh matrices of arrays formed by certain geometric operations. A preliminary version of this work was presented in the conference MICOPAM 2018 [25].


## 2. Preliminaries

For notions of formal string language theory and two-dimensional languages, not explained here, the reader is referred to [3]. We recall only some basic notions.A setΣ, called an alphabet, is a finite set of symbols. A word w over Σ is a finite sequence of symbols over Σ. The set of all words over Σ is denoted by Σ∗, and λ is the empty word with no symbols. An alphabet Σ=a1,a2,…,ak, with an order a1<a2<⋯<ak defined on it, is called an ordered alphabet, and we write Σ=a1<a2<⋯<ak. A word u is said to be a scattered subword (or simply subword) of a word w∈Σ∗ if there exist words x1,x2,…,xn,y0,y1,…,yn∈Σ∗ (possibly empty) such that u=x1,x2,…,xn and w=y0x1y1,…,yn−1xnyn. The length of a word w∈Σ∗, denoted by w, is the number of symbols present in w. The number of occurrences of a word u as a subword of w is denoted by wu.A picture array (or simply an array)A over Σ of size m×n,m,n≥1 is a rectangular arrangement of symbols in Σ in m rows and n columns. For example, ababab is a 2×3 binary array over the binary alphabet Σ=a,b. We denote the set of all m×n arrays over Σ by Σm×n. If X∈Σm×n, we denote by Xix, the number of symbol x in the ith row (or in the ith column) Xi of array X, and by Xx, the sum ∑i=1mXi. For two arrays X and Y with the same number of rows (resp. columns), the column (resp. rows) catenation X°Y (resp. X⋄Y) is the array obtained by juxtaposing the array Y on the right (resp. below) of the array X.Throughout the rest of the paper, we consider only a binary ordered alphabetΣ and binary arrays over Σ unless specified otherwise. We now recall the definition of the Parikh matrix mapping [4] restricting it to a binary alphabet. Let ℳ3 be the monoid of 3×3 upper triangular matrices with nonnegative integer entries and unit diagonal with respect to the multiplication of matrices. The unit 3×3 matrix is denoted by I3. For a matrix M∈ℳ3, the i,jth entry is denoted by Mij.Definition 1.
(see [4]). Let Σ=a1<a2 be an ordered alphabet. The Parikh matrix mapping, denoted by ψ3, is the morphism: ψ3:Σ∗⟶ℳ3 defined as follows: ψ3λ=I3 and for 1≤k≤2,ψ3ak=Mij1≤i,j≤3 where Mii=1 for 1≤i≤3, Mkk+1=1, and all other entries are zero. For a word w=w1w2⋯wn with wi∈Σ, the Parikh matrix of w is given by ψ3w=ψ3w1ψ3w2⋯ψ3wn.
IfM1,M2∈ℳ3 are two matrices, then the partial sum M=M1⊕M2 is defined [8] as the usual sum of matrices M1 and M2 except that the diagonal entries of M by definition have the value 1.


## 3. Row and Column Parikh Matrices of a Binary Picture Array

The notion of the Parikh matrix of a word has been extended to a picture array in [21] by introducing a row Parikh matrix and a column Parikh matrix of an array, which we recall now again restricting to a binary alphabet.Definition 2.
LetΣ=a1<a2 and the array A∈Σm×n. Let the word in the ith row of A be xi, 1≤i≤m, and the vertical word in the jth column of A be yj, 1≤j≤n. Let the Parikh matrices of xi and yj be, respectively, Mxi, 1≤i≤m, and Myj, 1≤j≤n. Then, the row Parikh matrix MrA of A is defined as MrA=Mx1⊕⋯⊕Mxm and the column Parikh matrix McA of A is defined as McA=My1⊕⋯⊕Myn.
As an illustration, consider the arrayA=ababab. Denoting the words in the rows as u=aba and v=bab, the row Parikh matrix of A is MrA=Mu⊕Mv=121011001⊕111012001=132013001.
We first obtain a property of the row (resp. column) Parikh matrix of a binary picture array, extending a corresponding property [8] of the Parikh matrix of a binary word.Theorem 1.
For integersm,n≥1, suppose M=1rt01s001∈ℳ3. If M is the row (resp. column) Parikh matrix of an m×n binary array A, then r+s=mn and t≤nr−∑i=1mri2 (resp. t≤mr−∑i=1nci2), where Aia=ri1≤i≤m (resp. Aia=ci (1≤i≤n)) with Ai being the ith row (resp. column) of A.Proof.
We prove the result only for the row Parikh matrix as the result for the column Parikh matrix can be proved in a similar manner. LetM be the row Parikh matrix of an m×n binary array A. Then, A has mn symbols, ra’s, and sb’s, so that r+s=mn. Let Aia=ri with Ai being the ith1≤i≤m row of A. Then, ∑i=1mri=r, and the number of b’s in the ith row is n−ri. Therefore, the maximum number of ab’s in the ith row is rin−ri. Thus, the maximum number of ab’s in the row Parikh matrix of A is ∑i=1mrin−ri so that t≤nr−∑i=1mri2.Corollary 1.
LetM be as in Theorem 1. If M is the row (resp. column) Parikh matrix of an m×n array, then r+s=mn and t≤nr−r2/m (resp. t≤mr−r2/n).
This result follows from Theorem1 by the Cauchy–Schwarz inequality ∑i=1mri2≥1/m∑i=1mri2.


## 4. Parikh Matrix of Power of an Array

The Parikh matrix of a wordw raised to an arbitrary power, denoted as wp, for an integer p≥1 has been studied in [23]. Here, we consider power of an array which has been introduced in [20].Definition 3.
LetA be an m×n array. Then, p×q power of A, denoted by Ap×q, is the pm×qn picture array such that Aijp×q=Aimodmjmodn, for all 1≤i≤pm and 1≤j≤qn.Example 1.
LetA=aabbab be a 2×3 two-dimensional array. The 2×4 power of A is given by A2×4=aabaabaabaabbabbabbabbabaabaabaabaabbabbabbabbab.Theorem 2.
LetM=1rt01s001 be the row Parikh matrix of a binary m×n array A over a<b. Then, the row Parikh matrix of the power Ap×q is given by 1pqrpqt+pqq−1/2∑i=1mri⋅si01pqs001, where Aia=ri and Aib=si, with Ai being the ith row of A.Proof.
We haveAp×q=A1×qp×1. Now, A1×q is the column catenation A°⋯°A of A with itself, q times. Let ri, si, and ti denote the number of a’s, b’s, and ab’s in the ith row xi1≤i≤m of A. Then, the ith row of A1×q is xiq. Using the formula in [23] (Theorem 3.1), the Parikh matrix of xiq is given by ψ3xiq=1qriqti+qq−1/2ri⋅si01qsi001. Therefore, the row Parikh matrix of A1×q is =1qrqt+qq−1/2∑i=1mri⋅si01qs001. Since the array Ap×q is the row catenation A1×q⋄⋯⋄A1×q of the array A1×q with itself p times, each of the rows of the array A1×q is repeated p times in the same order in Ap×q. This means that Ap×qa is p times A1×qa, i.e., Ap×qa is pqr. Likewise, for b’s and ab’s. This proves the required result.
The notion ofM-ambiguity of words has been extended to two-dimensional picture arrays in [21]. We now recall this.Definition 4.
The arraysA,B∈Σm×n are said to be iM-row equivalent if MrA=MrB and iiM-column equivalent if McA=McB. The arrays A and B are said to be M-equivalent, denoted by A≡MB, if they are both M-row equivalent and M-column equivalent. An array A∈Σm×n is M-ambiguous (or simply ambiguous) if it is M-equivalent to another distinct array; otherwise, it is unambiguous.
In [23], it is shown that for any two words v,w∈Σ∗, Σ≥2, either of the following statements iorii holds: ivk≡Mwk, for all positive integers k; iivk≢Mwk, for all positive integers k. In the case of binary picture arrays, the situation is different as seen from the following proposition.Proposition 1.
There areM-row equivalent picture arrays whose powers are not M-row equivalent and conversely.
This proposition is illustrated in the following example.Example 2.
We consider binary arraysA=aabbaa and B=abbaaa. Then, A1×2=aabaabbaabaa and B1×2=abbabbaaaaaa Now, MrA=MrB=142012001 so that the binary arrays A and B are M−equivalent.
But,MrA1×2=188014001 and MrB1×2=186014001 so that MrA1×2 and MrB1×2 are not M−equivalent.
We next consider binary arraysC=aabbbbaa and D=aabaabbb. Then, C1×2=aabbaabbbbaabbaa and D1×2=aabaaabaabbbabbb.
We haveMrC=144014001 and MrD=145014001 so that the binary arrays C and D are not M−equivalent.
But,MrC1×2=1816018001=MrD1×2 so that MrC1×2 and MrD1×2 are M−equivalent.
The next result gives a sufficient condition for twoM-row equivalent binary picture arrays to have their powers also M-row equivalent.Theorem 3.
LetA and B be two m×nM-row equivalent binary arrays over Σ=a<b. Then their powers Ap×q and Bp×q are M-row equivalent if ∑i=1mri2=∑i=1mui2, where Aia=ri and Bia=ui, 1≤i≤m, with Ai and Bi being the ith rows of A and B, respectively.Proof.
LetA and B be two m×nM-row equivalent binary arrays over Σ=a<b and MrA=MrB=1rt01s001. Then, ∑i=1mri=∑i=1mui=r where ri and ui, 1≤i≤m, are the number of a’s in the ith row of A and B, respectively. Also, the number of b’s in the ith row of A and B, respectively, is n−ri and n−ui. Suppose ∑i=1mri2=∑i=1mui2. Now, using Theorem 2, we have(1)MrAp×q=1pqrα01pqs001,MrBp×q=1pqrβ01pqs001,where α=pqt+pqq−1/2∑i=1mri⋅n−ri and β=pqt+pqq−1/2∑i=1mui⋅n−ui. We now prove that α=β which will complete the proof.
We have(2)α=pqt+pqq−12∑i=1mri⋅n−ri=pqt+pqq−12n∑i=1mri−∑i=1mri2=pqt+pqq−12n∑i=1mui−∑i=1mui2=pqt+pqq−12∑i=1mui⋅n−ui=β.
This proves thatAp×q and Bp×q are M-row equivalent.Remark 1.
The sufficient condition in Theorem3 is not vacuous as can be seen from the following illustration.
Consider the binary arraysA=aabbabaa and B=aaabbaab which are M−equivalent with the row Parikh matrix 155013001. If the number of subword a in the rows of A (resp. B) are r1 and r2 (resp. u1 and u2), then r12+r22=u12+u22=13. Now, A3×2=aabbaabbabaaabaaaabbaabbabaaabaaaabbaabbabaaabaa and B3×2=aaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaab and MrA=MrB=130510118001 so that the binary arrays A3×2 and B3×2 are M−equivalent.


## 5. Fair Picture Arrays

Fair words and their properties have been studied in [24]. A weak ratio property for an array is introduced in [21]. We now extend the notion of fair words to two-dimensional arrays. We also recall the notion of the weak ratio property restricting it to binary arrays.Definition 5.
(i)
A binary arrayA∈Σm×n is called fair if the total number of subwords ab in the rows (respectively, columns) of A is equal to the total numbers of subwords ba in the rows (respectively, columns) of A(ii)
LetA and B be two binary arrays over Σ=a<b. The arrays A and B are said to satisfy a weak ratio property if Aa/Ba=Ab/Bb=k where k is a nonzero constantTheorem 4.
LetA and B be two fair binary arrays over Σ=a<b, both having the same number of rows, satisfying the weak ratio property. Then, the arrays A∘B and B∘A are also fair. A corresponding result holds good for A⋄B and B⋄A.Proof.
LetA∈Σm×n and B∈Σm×l be two fair words satisfying the weak ratio property with ratio constant α. Denoting the total number of subwords ab in the rows of a binary array by Xabr, we have Aabr=Abar and Babr=Bbar. Also, we have Aa/Ba=Ab/Bb=α. This implies that mn=A=Aa+Ab=αBa+Bb=αml, i.e., n=αl.
SinceA∘B is the column catenation of A and B, the column Parikh matrix of A∘B is McA∘B=McA⊕McB . Therefore, the number of subword ab’s column wise in A∘B is the same as the number of ba’s column wise in A∘B.
Letxi and ui, 1≤i≤m, be the words in the ith row of A and B, respectively. Now, the number of ab’s row wise in A∘B is given by(3)A∘Babr=∑i=1mxiab+yiab+xia⋅yib=Aabr+Babr+∑i=1mxia⋅yib.
We also have(4)A∘Bbar=∑i=1mxiba+xiba+xib⋅yia=Abar+Bbar+∑i=1mxib⋅yia=Aabr+Babr+∑i=1mxibl−yib,since(5)yi=l=Aabr+Babr+l∑i=1mxib−∑i=1mxibyib=Aabr+Babr+αl∑i=1myib−∑i=1mxibyib=Aabr+Babr+∑i=1mαl−xibyib=Aabr+Babr+∑i=1mn−xibyib,since(6)n=αl=Aabr+Babr+∑i=1mxia⋅yib=A∘Babr.
This proves thatA∘B is a fair array. In a similar manner, it can be shown that B∘A is also a fair array.


## 6. Restricted Shuffle Operator on Picture Arrays

In [6], a restricted shuffle operator on two binary words, denoted as SShuf, is considered and properties of Parikh matrices of words under this operator are derived, especially over a binary alphabet. Here, we extend this operator to picture arrays and obtain properties of Parikh matrices of arrays under this operator.Definition 6.
LetA,B∈Σm×n be two picture arrays over Σ=a<b such that A=a11⋯a1n⋮⋱⋮am1⋯amn and B=b11⋯b1n⋮⋱⋮bm1⋯bmn. Then, the restricted row shuffle operator on the pair of arrays A and B is defined by(7)RSShufA,B=a11b11a12b12⋯a1nb1na21b21a22b22⋯a2nb2n⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅am1bm1am2bm2⋯amnbmn,and similarly the restricted column shuffle operator is defined by(8)CSShufA,B=a11a12⋯a1nb11b12⋯b1n⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅am1am2⋯amnbm1bm2⋯bmn.Example 3.
LetA,B∈Σ3×3 over the binary alphabet Σ=a<b be given by A=aabbaa , B=baaaba. Then, RSShufA,B=abaababaabaa and CSShufA,B=aabbaabaaaba.
We observe a few facts which are immediate from the definition:(i)
MrCSShufA,B=MrA⊕MrB(ii)
McRSShufA,B=McA⊕McB
In [7], the authors introduced a notion of the positions of letters in a word and using this notion characterized the M-equivalent words over the binary alphabet. The sum of positions of a letter a in a word w of length n over an alphabet Σk, denoted by Saw, is defined by Saw=∑wi=a,1≤i≤ni.
Here, we introduce the sum of positions of a letter in a binary array overΣ=a<b as follows.Definition 7.
LetA be a binary m×n array over a<b, then the row-wise sum of positions of a letter a in A is defined by SarA=∑1≤i≤mSaxi, where xi is the ith row of the array A.
Similarly, the column-wise sum of positions of a lettera in A is defined by SacA=∑1≤i≤nSayi, where yi is the ith column of the array A.Theorem 5.
Two arraysA and B over a<b is M-row equivalent (column equivalent) to each other if each row (column) of A and B has the same number of b’s and SbrA=SbrB (SbcA=SbcB, respectively).Proof.
Letxi and yi be the ith row of the arrays A and B, respectively. Also, let xib=yib, for all 1≤i≤m, and SbrA=SbrB. Then, the number of ab’s in the row Parikh matrix of A is equal to ∑1≤i≤mxiab. Now,(9)∑1≤i≤mxiab=∑1≤i≤mSbxi−xibxib+12=∑1≤i≤mSbxi−∑1≤i≤mxibxib+12=∑1≤i≤mSbyi−∑1≤i≤myibyib+12=∑1≤i≤mSbyi−yibyib+12=∑1≤i≤myiab,which is the number of ab’s in the row Parikh matrix of B. Hence, the binary arrays A and B are M-row equivalent.
Similarly, the other case ofM-column equivalence can be proved.Lemma 1.
LetA,B∈Σm×n where Σ=a<b, then iSbrRSShufA,B=2SbrA+SbrB−Ab and iiSbrCSShufA,B=2SbcA+SbcB−Ab where Ab is the number of b’s in the array A.Proof.
Letxi and yi be the ith row of the arrays A and B, respectively. Then, we have(10)SbrRSShufA,B=∑i=1mSbSShufxi,yi=∑i=1m2Sbxi+Sbyi−xib=2∑i=1mSbxi+∑i=1mSbyi−∑i=1mxib=2SbrA+SbrB−Ab.Similarly, we can prove the statementii. A sufficient condition for the row shuffle operator of two binary arrays is given as follows.Theorem 6.
LetA,B∈Σm×n where Σ=a<b, then RSShufA,B≡MRSShufB,A if Ab=Bb.This can be seen using Lemma1 and the fact that McRSShufA,B=McA⊕McB.


## 7. Geometric Operations on Picture Arrays

Geometric operations on picture arrays such as reflection and rotation are now considered. Properties of Parikh matrices of the arrays resulting from the geometric operations are obtained.Proposition 2.
LetA be a binary m×n picture array over a<b. Reflection of A about its rightmost vertical yields an array Av with the following properties:(i)
Ava=Aa and Avb=Ab(ii)
The column Parikh matrices ofA and Av are the same(iii)
The number ofab’s row wise in Av is Avabr=∑1≤i≤mriarib−riab, where ri is the ith row of A
Similarly, reflection of A about its bottommost horizontal yields an arrayAh with the following properties:(i)
Aha=Aa and Ahb=Ab(ii)
The row Parikh matrices ofA and Ah are the same(iii)
The number ofab’s column wise in Ah is Ahabc=∑1≤i≤nciacib−ciab, where ci is the ith column of A
The following proposition is a consequence of Proposition2.Proposition 3.
If two arraysA and B of the same sizes are M-equivalent, then their reflections about their rightmost verticals and their bottommost horizontals are also M-equivalent.Definition 8.
LetA∈Σm×n be a picture array over Σ=a<b such that A=a11⋯a1n⋮⋱⋮am1⋯amn. A picture array obtained from A by rotating it by 90° clockwise, denoted by A90°, is defined as A90°=am1⋯a11⋮⋱⋮amn⋯a1n.
Note thatA90° is an array of size n×m such that the first row of A is the last column of A90°, the second row of A is the last but the second column of A90°, and so on, and the last row of A is the first column of A90°.
Similarly, one can defineA180° (which is the same as A90°90°), A270°, and A360°. It is easy to see that A360°=A.
Now we state in the following proposition, the relations between the row and column Parikh matrices of the rotated arrays.Proposition 4.
LetA∈Σm×n be a picture array where Σ=a<b, then iMrA90°=McAh and McA90°=MrA, iiMrA180°=MrAv and McA180°=McAv, and iiiMrA270°=McA and McA270°=MrAv where Ah and Av are the reflections of the array A about its bottommost horizontal and rightmost vertical.


## 8. Concluding Remarks

Motivated by applications in areas such as pattern recognition and computer vision several studies have been done on combinatorial properties of two-dimensional arrays [15]. The study done in this paper is a contribution to this area as well, and it extends notions and concepts well studied in the context of strings. It will be of interest to consider picture arrays of three or more symbols and examine the applicability of the notions and results considered here.



---

*Source: 3236405-2020-06-29.xml*