검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

Kyungpook Mathematical Journal 2022; 62(2): 289-321

Published online June 30, 2022

Copyright © Kyungpook Mathematical Journal.

A Study of Broline-Crowe-Isaacs Matrices of Polygon Dissections

Raùl Felipe

Department of Basic Mathematics, Mathematics Research Center (CIMAT), Callejón Jalisco s/n Mineral de Valenciana, Guanajuato, Gto, México
e-mail : raulf@cimat.mx

Received: May 7, 2020; Revised: December 17, 2021; Accepted: April 18, 2022

The work realized by the authors of [4], [5] and [6] associates a non-negative matrix with positive integers entries to each dissection of a polygon. In the particular case of triangulations, these matrices called BCI-matrices here contain valuable information of their frieze patterns, a concept introduced by Coxeter and Conway. This paper is concerned with the algebraic manipulation and properties of these matrices which are derived from operations acting on dissections.

Keywords: BCL-matrices, non-negative matrix

The Broline-Crowe-Isaacs matrices were introduced in [6] in order to understand the geometry of Coxeter's frieze patterns of positive integers. These last objects are arrays of positive integers in which neighbouring values are linked by a fixed rule. The origin of these structures goes back to Gauss's work on the pentagramma mirificum. Initially, Coxeter found some connections between friezes patterns and various objects such as cross ratios, continued fractions and Farey series. Subsequently, Coxeter and Conway discovered a one-to-one correspondence between friezes of positive integers and triangulations of convex polygons, more exactly, they established a one-to-one correspondence between a periodic finite sequence called quiddity sequence of the first row of the frieze patterns and the triangulations of convex polygons (see [9]). More recently, frieze patterns appeared in other contexts, for instance in the fields of cluster algebras [7] and of Nichols algebras [10], see also [11] to know some generalizations of these structures.

In order to understand the geometric meaning of the remaining rows of a frieze patterns Broline, Crowe and Isaacs defined for each frieze pattern of positive integers a symmetric matrix whose entries constitute the triangular fundamental domain of the frieze pattern (see [12] for details). These matrices were extended and studied for any d-angulation of polygons by Bessenrodt, Holm and Jorgensen in [4] and for the case of arbitrary dissections by Bessenrodt [5]. A notable computation in all the mentioned works is that of the determinant of the matrices associated to polygon dissections. In this direction, we must indicate the work of Baur and Marsh [2] where the determinant of a certain Broline-Crowe-Isaacs type matrix which appears in connection with the corresponding frieze pattern of cluster variables arising from the Fomin-Zelevinsky cluster algebra of type A was calculated.

We start with some definitions.

A real matrix L is said to be non-negative whenever all the entries of L are nonnegative. We use the notation L0 to indicate this fact. It is evident that if L is a non-negative matrix then its transpose matrix Lt is also nonnegative. In our work, we will only consider non-negative matrices of arbitrary order whose off-diagonal entries are positive integers, and which have the following form

L=01l13l1(n1)11l2nl31l(n3)nl(n1)111ln2ln(n3)10,

when, lij0 if |ji|2 and L=Lt. Moreover these matrices have zeros along the principal diagonal and the first diagonals above and below the principal diagonal are 1. Besides this, l1n=ln1=1.

The set of all matrices of this form will be denoted by M() and the subset of matrices of order n by M()n. For two matrices L1,L2M()n we write L1L2 if (L1)ij(L2)ij for all i,j=1,,n.

This partial order makes to M()n a poset and is called the normal order. The elements of the set M() will be called M-matrices.

Matrices of type (1.1) appear as distance matrices which are a natural tool to describe finite metric spaces, see [13].

We recall that the anti-diagonal of a matrix is the diagonal going from the lower left corner to the upper right corner (≠arrow). For an arbitrary matrix K, we denote the transpose matrix with respect to the anti-diagonal by Kτ, that is, Kτ=JKtJ being Kt its usual transpose and J is the matrix with entries 1 on the anti-diagonal and 0 else. Observe that the equalities (Kτ)τ=K and |Kτ|=|K| hold. Moreover, if LM() then LτM().

In the first part of the rest of this section, we proceed to indicate how the space M()n is related to the set of dissections of an n-gon. In [6], Broline, Crowe and Isaacs assigned a M-matrix in M()n to each triangulation of a convex n-gon. In fact, if T is a triangulation of a convex n-gon, and we fix a numbering of vertices and an order to go around the polygon, then there is a unique matrix MTM()n containing the main information of the Coxeter frieze pattern of this triangulation (the reader interested in learning the basic theory and recent developments about frieze patterns can consult [6], [9] and [12]).

Next, we briefly recall the construction of these matrices for an arbitrary d-angulation due to Bessenrodt, Holm and Jorgensen [4], where 3d which in the particular case of d = 3 coincides with that given by Broline, Crowe and Isaacs in [6]. Immediately after, we then illustrate this giving the Broline-Crowe-Isaacs matrices (or in short form, simply the BCI-matrices) for some d-angulations.

Henceforth, the vertices of all n-gons under discussion are labeled counterclockwise by the numbers from 1 to n (for convenience we identify the vertex 1 with n+1 and the vertex n with 0).

By a dissection D of a convex n-gon Pn we mean a division of Pn through m-1 pairwise noncrossing diagonals into m nonoverlapping polygons Pn1,,Pnm called the pieces of the dissection. We use the notation D=(Pn1,,Pnm) in order to specify the dissection. If each piece of the dissection is a d-gon we say that it is a d-angulation denoted by Hd, in this case n=d+(m1)(d2). In particular, if d=3 we have a triangulation for an n-gon. For the case m-1=0 or n=d one has the empty dissection which will be denoted by Dn.

Example 1.1. Let n=10, m-1=3 and d=4; a possible 4-angulation of the 10-gon is the following:

Suppose n=d+(m1)(d2) for some d3 and (m1){0}; let Hd be a d-angulation of an n-gon Pn, and let i and j vertices of Pn, such that i+1j. Indices and vertices are always taken to be reduced modulo n. A sequence w=(Qi+1,,Qj1) of pieces of Hd is called a (counterclockwise) d-path from i to j if it satisfies the following properties

  • 1. The d-gon Qk is incident to vertex k for all k{i+1,i+2,,j1}.

  • 2. In the sequence Qi+1,Qi+2,,Qj2,Qj1, each d-gon of Hd appears at most d-2 times.

For i+1j the number of (counterclockwise) d-paths from i to j is denoted mi,j. In addition, we set mi,i=0, mi,(i+1)=m(i+1),i=1. Then, following [4] we introduce the M-matrix of order n×n, MHd associated to the d-angulation Hd as MHd=(mi,j)1i.jn. As mentioned earlier, this will be called the BCI-matrix corresponding to Hd.

This construction is a direct generalization of the one proposed in [6] for triangulations. In [4], it is proved that MHd is a symmetric matrix. Also, in theorem 1.2 of [4] the authors proved that |MHd|=(1)n1(d1)m, where n=d+(m1)(d2), and m is the number of pieces of the d-angulation Hd of n-gon Pn. For the case d=3 and m=n-2 this determinant reduces to the well known formulae of Broline, Crowe and Isaacs: |MT|=|MH3|=(2)n2.

For the example 1.1, we compute some mij and give the corresponding 4-paths (see [4], example 2.3 for more details). We remember that by definition no quadrangle is allowed to appear more than twice in a 4-path. Let i=2 and j=6. At the vertices 3 and 4 we must take the quadrangle λ while at the vertex 5 we can choose β or δ. Thus, the only 4-paths from vertex 2 to vertex 6 are (λ,λ,δ) and (λ,λ,β), hence m2,6=2. Now, let i=4 and j=9. At both vertices 6 and 7 we have to choose β. Since in all 4-path, each quadrangle appears at the most 2 times, then λ or δ can be taken at the vertex 5 and δ or α for the vertex 8. So we get four 4-paths from vertex 4 to vertex 9:(λ,β,β,δ); (λ,β,β,α); (δ,β,β,α) and (δ,β,β,δ). Hence, we have m4,9=4.

For this 4-angulation H4 of P10 (see [4]), the complete BCI-matrix MH4 has the following form

MH4=0122122111101112212221011332442110133244111101112222331011332233110133112211101112442331011244233110,

for which |MH4|=81=(1)9(41)4.

We give another example

Example 1.2. For the following triangulation T=H3 of the hexagon

the BCI-matrix is

MT=MH3=011121101253110132121011253101132110,

in this case, |MT=H3|=16=(2)62.

We now concentrate on the notion of BCI-matrix of an arbitrary dissection as introduced in [5]. Let D={Pn1,,Pnm} be a dissection through m nonoverlapping polygons of an n-gon Pn, C. Bessenrodt [5] (see also [12]) introduced the notion of (counterclockwise) walk.

A walk from i to j, where i+1j, is a sequence w=(Qi+1,,Qj1) of pieces of BCI such that

  • 1. The polygon Qk is incident to vertex k for all k{i+1,i+2,,j1}.

  • 2. Every polygon Q of BCI appears at most dQ2 times among the pieces Qi+1,Qi+2,,Qj2,Qj1 where dQ is the size of Q.

This definition of walk agrees with the notion of d-path when the dissection BCI is a d-angulation Hd. By counting the walks between two vertices i and j we can define mi,j as the number of walks from vertex i to vertex j. Also, we have mi,i=0 and mi,(i+1)=m(i+1),i=1. In this way, one gets also a symmetric matrix MDM()n for each dissection BCI of Pn for which the determinant is:

|MD|=(1)n1 k=1m(dk1),

and MD will be called the BCI-matrix associated to the dissection BCI (see theorem 2.3 in [5] for more details) as in the case of d-angulation.

In what follows, a walk form i to j will be denoted bywij or wij(P,D) indicating the dependence on the polygon P and on its dissection BCI.

Now, in order to illustrate the definitions of walk and of BCI-matrix for dissections which are not d-angulations, we reproduce the example 2.2 of [5].

Example 1.3. Consider a dissection BCI of a 7-gon formed with three triangles and a quadrangle:

By definition in any walk a triangle can appear at most once and the quadrangle at most 2 times. We indicate the walks from vertex 1 to any vertex j>2 and with this purpose we will use the notation 1j to indicate the set of all walks from the vertex 1 to the vertex j:

1 ⟶ 3 (α), (β),

1 ⟶ 4 (α,β), (α,λ), (β,β), (β,λ),

1 ⟶ 5 (α,β,λ),(β,β,λ),(α,β,δ), (α,λ,δ), (β,β,δ), (β,λ,δ),

1 ⟶ 6 (α,β,λ,δ),(β,β,λ,δ),

1 ⟶ 7 (α,β,λ,δ,β).

For this dissection BCI of P7 the BCI-matrix is

MD=0124621101231121012114210112632101321111011112310,

and |MD|=24=(1)62322.

Observe that the BCI-matrix of order n associated to the empty dissection Dn of an n-gon is

MDn=01111110,

with determinant |MDn|=(1)n1(n1) which shall be called the empty M-matrix of order n (or the empty BCI-matrix). Of course MDnτ=MDn for all n.

This article is organized as follows, in this introduction we have briefly remembered the notion of Broline-Crowe-Isaacs matrix (BCI-matrix) for triangulations and dissections in general. Formulas of the determinant of these matrices were also presented and the BCI-matrices corresponding to some dissections were calculated. In the second section, we introduce on the set MD of all Broline-Crowe-Isaacs matrices a SET operad structure. Section three is reserved to study BCI-matrices through the notion of outer chains of vertices for dissections. In the last section, we introduce and study the concept of enlargement for M-matrices which allows us to construct BCI-matrices by means of others BCI-matrices of a lower order.

We wish to add that this paper is confined to the study of linear algebra of the set of BCI-matrices. As future work we have the intention of to find relationships of the present research with some modern tools mentioned above such as the cluster algebras, Nichols algebras, etc.

We conclude this introduction by summarizing the principal contributions of this work:

  • 1. Broline-Crowe-Isaacs matrices are difficult and cumbersome to calculate following the usual procedure of to find the number of paths between two specific vertices, especially in the cases of dissections of n-gons in which n is large. In our paper, we show how to construct BCI-matrices of another of smaller dimension through some operations called by us enlargement. We present several types of these operations. In practice it is `enough' to know these matrices in low dimensions.

  • 2. We show a link between the class of polygon dissections and a certain variant of the operad theory. This reveals the possibility that many known structures containing others of Catalan-type can be treated from the perspective of the operad theory.

  • 3. The form of the BCI-matrices is studied through the optics of the outer chains of vertices of their corresponding dissections.

Denote by MD the set of all M-matrices associated to dissections of polygons, that is, MD is the set of all BCI-matrices. Also, let us denote by MD()n the subset MDM()n. On other hand, let Dn be the set of all dissections of an n-gon Pn, and for those formed with m-1 non-crossing diagonals, where 0m1n3, we reserved the notation Dn(m1). Finally, MD()n(m1) is the set of BCI-matrices associated to the dissections of Dn(m1).

For convenience apoint and a segment should be considered polygons with one and two vertices respectively and let us denote these by P1 and P2. We can define formal dissections for P1 and P2. Thus, D1 is the generalized dissection formed by a point labeled by 1, and D2 consists of the generalized dissection formed by two points labeled by 1 and 2 and connected by a line segment. We assign MD()1={MD1} and MD()2={MD2} where

MD1=M1=(0),MD2=M2=0110.

Note that working with polygons with n vertices which are labeled counterclockwise by the set [n] implies that we have an one-to-one correspondence between Dn and MD()n. Hence, we also have a one-to-one correspondence between MD and the set of all dissections D.

Let P be an n-gon. In order to avoid excessive graphics we use the notation (i,j) to indicate the diagonal connecting the vertex i to the vertex j and denote by D[(i1,j1),,(ik,jk)]n with 1kn3, the dissection built with the noncrossing diagonals (i1,j1),,(ik,jk) which we say shape the dissection. In general, if X is a set of noncrossing diagonals of an n-gon then DXn will denote the corresponding dissection.

We return to the BCI-matrices. Clearly MD()3={MD3}. We continue calculating MD()4 and MD()5. It is easy to see that MD()4 is the set formed by the matrices

MD4=0111101111011110,MD[(1,3)]4=0111101211011210,MD[(2,4)]4=0121101121011110.

On other hand, a simple checking shows that MD()5 is composed of MD5 and the following matrices

MD[(1,4)]5= 0 1 1 1 1 1 0 1 1 2 1 1 0 1 2 1 1 1 0 1 1 2 2 1 0 ,MD[(1,3)]5= 0 1 1 1 1 1 0 1 2 2 1 1 0 1 1 1 2 1 0 1 1 2 1 1 0 ,
MD[(2,4)]5= 0 1 2 1 1 1 0 1 1 1 2 1 0 1 2 1 1 1 0 1 1 1 2 1 0 ,MD[(3,5)]5= 0 1 1 2 1 1 0 1 2 1 1 1 0 1 1 2 2 1 0 1 1 1 1 1 0 ,
MD[(2,5)]5= 0 1 2 2 1 1 0 1 1 1 2 1 0 1 1 2 1 1 0 1 1 1 1 1 0 ,MD[(1,3),(1,4)]5= 0 1 1 1 1 1 0 1 2 3 1 1 0 1 2 1 2 1 0 1 1 3 2 1 0 ,
MD[(1,4),(2,4)]5= 0 1 2 1 1 1 0 1 1 2 2 1 0 1 3 1 1 1 0 1 1 2 3 1 0 ,MD[(1,3),(3,5)]5= 0 1 1 2 1 1 0 1 3 2 1 1 0 1 1 2 3 1 0 1 1 2 1 1 0 ,

and

MD[(2,4),(2,5)]5= 0 1 3 2 1 1 0 1 1 1 3 1 0 1 2 2 1 1 0 1 1 1 2 1 0 ,MD[(2,5),(3,5)]5= 0 1 2 3 1 1 0 1 2 1 2 1 0 1 1 3 2 1 0 1 1 1 1 1 0 .

Note that

MD[(1,3)]4τ=MD[(2,4)]4,MD[(1,4)]5τ=MD[(2,5)]5,MD[(1,4),(2,4)]5τ=MD[(2,4),(2,5)]5.

The following remark is evident

Remark 2.4. Let MD be a BCI-matrix associated to the dissection D of an n-gon. Then, (MD)τ is a BCI-matrix, that is, there is a dissection Dτ called the transpose dissection of D such that (MD)τ=MDτ. Moreover, let n be arbitrary and 0m1n3, suppose that MDnMD()n(m1), then (MDn)τMD()n(m1).

We give an example

Example 2.5. It is immediate to see that the transpose dissection for (1.2) is the following dissection

The reader can easily verify that the corresponding BCI-matrix for this is the matrix

M(H4)τ=0113324421101332442111011122113310113322331101332222111011114423310112442331101222122111011112212210,

which matches with (MH4)τ.

Remark 2.6. Note that the transformation DDτ on polygons with the same number of vertices maps a d-angulation in a d-angulation having both the same number of pieces. In general, this transformation leaves invariant the number of pieces. Moreover, it maintains invariant the number of triangles, rectangles, pentagons, hexagons, etc. Thus, for all dissection D we have

|MD|=|MDτ|=|(MD)τ|.

Also, this can be seen as follows |(MD)τ|=|J(MD)tJ|=|(MD)t||J|2=|MD|, because |J|2=1.

Next, we introduce the notion of superposition in MD()n for n5. Suppose that DΔ,DDn. We say that the BCI-matrices MD,MDMD()n can be superposed if DDDn.

Definition 2.7. Suppose that the BCI-matrices MD,MDMD()n can be superposed. In this case, we define the superposition product for these two matrices of the following form

MDMD=MDD.

Notice that if DDn(m1) and DDn(m1), DDDn(m1) where m=m+m1. Thus, MDDMD()n(m1).

It is clear that the product (2.4) is commutative and associative. Also, from remark 2.4 we obtain

(MDMD)τ=M(DD)τ=M(D)τ(D)τ=(MD)τ(MD)τ.

Example 2.8. Let us pause a moment in the case n=5. It is clear that MD5MD5=MD5MD5=MD5 for all MD5MD()5. On other hand, one can easily check that

MD[(1,3)]5MD[(1,4)]5=MD[(1,3),(1,4)]5, MD[(1,4)]5MD[(2,4)]5=MD[(1,4),(2,4)]5, MD[(1,3)]5MD[(3,5)]5=MD[(1,3),(3,5)]5,MD[(2,4)]5MD[(2,5)]5=MD[(2,4),(2,5)]5,

and

MD[(2,5)]5MD[(3,5)]5=MD[(2,5),(3,5)]5. 

Note that MD is not closed under the usual multiplication of matrices of same order. This makes of interest the aim of finding suitable binary products on MD.

It is well known that in the category Set of sets one can define two different types of operads: symmetric and nonsymmetric, depending on the presence or not of actions of symmetric groups. Next, we introduce a nonsymmetric operad related with the BCI-matrices.

Next, we abbreviate the set {1,2,,n1,n} to [n].

Definition 2.9. A nonsymmetric (ns) BCI-operad in Set is by definition a collection of sets O(n)

O=n1O(n),

together with partial composition maps

i:O(n)×O(m)O(n+m1),n,m1,i[n],

and a distinguished element 1O(1), the unit of O, such that

(xiy)i+j1z=xi(yjz),

where xO(n),yO(m),zO(k),i[n] and j[m1], for m2. Moreover

(xiy)j+m1z=(xjz)iy,

for xO(n),yO(m),zO(k),i,j[n] such that i<j and 1<n. Finally

11x=x=xi1,

for xO(n) and i[n].

Our definition of nonsymmetric set operad is slightly different from the usual definition (see [8]), because the value j=m has been excluded in the axiom (2.7). This is why we call it BCI-operad. The reason for not including j=m in (2.7) will be shown a little lower.

It is convenient in this section first to begin with dissections and then incorporate into the discussion the BCI-matrices corresponding to dissections of polygons. As it was introduced above D=n1Dn. We recall that Dn is the set of all dissections of an n-gon. Thus, D is the collection of all dissections of polygons.

Given two polygons Pn, Pm with n and m vertices respectively and i∈[n], we can construct a polygon with n+m-1 vertices Pn+m1(i) of the following form: one glues the vertex i∈[n] of Pn with the vertex 1 of Pm and connects the vertex i+1 of Pn with the vertex m of Pm by a line segment. The sides (i,i+1) of Pn and (1,m) of Pm are removed. To complete the construction we label the vertices of new polygon Pn+m1(i) from the vertex 1 of Pn anticlockwise. In this process, we say that the vertices i of Pn and 1 of Pm form a vertex of Pn+m1(i) and that the vertices i+1 of Pn and m of Pm form a side of Pn+m1(i).

Let D˜Dn and D^Dm, then for i[n], we define partial composition maps

D˜iD^=D¯,

where D¯ is the dissection of Pn+m1(i) (the polygon introduced previously) defined of the following manner: it is formed with the diagonals of the dissection D˜ for the n-gon

Pn, the diagonals of D^ for the m-gon Pm, the side (i,i+1) of Pn and the side (1,m) of Pm. All this is done taking into account the new labeling. The construction discussed here will be called glue of dissections.

For instance

It is clear that °i:Dn×DmDn+m1 for i[n].

We will make this construction a little more formal and rigorous. Let D˜Dn be a dissection of a polygon Pn with n vertices. Then, we labeled counterclockwise the vertices of Pn by the numbers of the set {1,2,,i,i+m,i+m+1,,i+m+n1}. Denote by D˜n+m1 the dissection D˜ with the new labels and D˜n+m1(i)=D˜n+m1(i,i+m). It is clear that D˜n+m1(i) is also a dissection for a polygon Pn+m1 with n+m-1 vertices. On other hand, if D^Dm is a dissection for a second polygon Pm with m vertices, then we label its vertices through the set {i,i+1,,i+m1} also counterclockwise. Similarly, one denotes D^n+m1 to be D^ with the new labels and D^n+m1(i)=D^n+m1(i,i+m1). Then, D^n+m1(i) is also a dissection of Pn+m1. Clearly D˜n+m1(i) D^ n+m1(i)Dn+m1. Then, we have

D˜iD^= D ˜ n+m1(i)D^n+m1(i),

for all D˜Dn and any D^Dm where i[n].

Now, we show that axiom (2.7) does not hold for the product of dissections (2.10) (that is (2.11)) when j=m. In our example n=5, m=4 and k=3, besides i=2 and j=4. Then, for the chosen dissections (in this case, all triangulations) one has

on other hand

It implies that in general (2.7) does not hold for j=m in the case of dissections. What happens in this case is that, for instance, the vertex 3 of P5 in the first double composition forms sides with the vertices 4 of P4 and 3 of P3, while in the second double product the vertex 3 of P5 only forms side with the vertex 3 of P3. This example works in general for all n,m,k3.

However, we have

Theorem 2.10. The collection of all dissections of polygons D has structure of nonsymmetric BCI-operad with respect to the partial composition maps (2.10).

Proof. Define 1 as the unique element of D1, then obviously the axiom (2.9) holds. Throughout the proof we keep the convention of identifying the vertex i of any polygon of n vertices with i+nl for l=1,2,.

In our context, to calculate each side of the axioms (2.7) and (2.8) imply to apply two times the construction of glue of dissections (recall that during the process of gluing of dissections, we assume that any polygon involved in the discussion has a fixed dissection attached). Hence, to prove that the remaining axioms hold, we must show that in the double products of each equality, the pairs of vertices which form vertices and the pairs of vertices forming sides are the same in each side of the equality. In effect, this ensures that the dissections obtained for the final polygons (with n+m+k-2 vertices) coincide for each side of the equalities.

We will do the analysis for each side of the axioms. We begin with the axiom (2.7). Recall that 1in and 1jm1. Hence, the vertex m of Pm does not form vertices in the construction of glue of dissections with the vertex 1 of P(k).

Left side of axiom (2.7)

  • · pairs of vertices forming vertices: The vertex i of Pn and the vertex 1 of Pm form the vertex i of Pn+m1(i). Then, the vertex i+j-1 of Pn+m1(i) with the vertex 1 of Pk forms the vertex i+j-1 of final polygon. Note that the vertex i+j-1 of Pn+m1(i) coincides with the vertex j of Pm.

  • · pairs of vertices which form sides: The vertex i+1 of Pn and the vertex m of Pm form a side of Pn+m1(i). Then, the vertex i+j of Pn+m1(i) and the vertex k of Pk form other side. Observe that the vertex i+j of Pn+m1(i) coincides with the vertex j+1 of Pm.

Right side of axiom (2.7)

  • · pairs of vertices forming vertices: The vertex j of Pm and the vertex 1 of Pk form the vertex j of Pm+k1(j). Then, the vertex i of Pn and the vertex 1 of Pm+k1(j) form the vertex i of final polygon. In this case, the vertex j of Pm+k1(j) becomes the vertex i+j-1 for the final polygon.

  • · pairs of vertices which form sides: The vertices j+1 of Pm and k of Pm form a side. Then, the vertex i+1 of Pn with the vertex m+k-1 of Pm+k1(j) which coincides with the vertex m of Pm forms a side.

Thus, the axiom (2.7) holds. Now, in order to prove the axiom (2.8) observe that i+m1<j+m1. This is because i < j, where i,j∈[n] (the case n=2 for which i=1 and j=2 is not excluded). We divide the proof into two cases. Let us assume first that j=i+1 then

Left side of axiom (2.8) for j=i+1,

  • · pairs of vertices forming vertices: The vertex i of Pn with the vertex 1 of Pm form the vertex i of Pn+m1(i). Observe now that the vertex i+1 of Pn becomes the vertex i+m of Pn+m1(i). Then the vertex i+1 of Pn forms vertex with the vertex 1 of Pk.

  • · pairs of vertices which form sides: The vertices i+1 of Pn and m of Pm form a side. Then, the vertex i+2 of Pn and the vertex k of Pk form other side.

Right side of axiom (2.8) for j=i+1,

  • · pairs of vertices forming vertices: The vertex i+1 of Pn forms vertex with the vertex 1 of Pk. Then, the vertex i of Pn+k1(i+1) which coincides with the vertex i of Pn forms vertex with the vertex 1 of Pm in order to form the vertex i of final polygon.

  • · pairs of vertices which form sides: The vertex i+2 of Pn and the vertex k of Pk form a side of Pn+k1(i+1). Then the vertex i+1 of Pn+k1(i+1) that is equal to the vertex i+1 of Pn forms a side with the vertex m of Pm.

Suppose now that i+1<j. We analyze this case

Left side of axiom (2.8) for i+1<j,

  • · pairs of vertices forming vertices: The vertex i of Pn with the vertex 1 of Pm form the vertex i of Pn+m1(i). Then observe that the vertex j of Pn becomes the vertex j+m-1 of Pn+m1(i). Then the vertex j of Pn forms vertex with the vertex 1 of Pk.

  • · pairs of vertices which form sides: The vertices i+1 of Pn and m of Pm form a side. Then, the vertex j+1 of Pn and the vertex k of Pk form other side.

Right side of axiom (2.8) for i+1<j,

  • · pairs of vertices forming vertices: The vertex j of Pn forms vertex with the vertex 1 of Pk. Now, the vertex i of Pn+k1(j) which coincides with the vertex i of Pn forms vertex with the vertex 1 of Pm in order to form the vertex i of final polygon.

  • · pairs of vertices which form sides: The vertex j+1 of Pn and the vertex k of Pk form a side of Pn+k1(j). Then the vertex i+1 of Pn+k1(j) which is equal to the vertex i+1 of Pn forms a side with the vertex m of Pm.

This shows that axiom (2.8) holds. The theorem is proved.

Let D be a dissection belonging to Dn, then the number of paths from vertex i-1 to vertex i+1 is the number of pieces incident on the vertex i for all i∈[n]. This fact leads to the following definition

Definition 2.11. Let DDn be a dissection and 𝒟 its BCI-matrix. If 5n, the vector

qD=(m2n,m13,m24,m35,,m(n3)(n1),m(n2)n,m1(n1))=(q1,q2,,qn1,qn),

is called the quiddity sequence for the dissection D. Note that quiddity sequence is formed with some entries of the BCI-matrix MD. Really, these entries are in some off-diagonals, specifically the off-diagonals are the third and the penultimate above the principal diagonal.

We have

Lemma 2.12. Consider D1,D2Dn. If D1D2 then MD1MD2.

Proof. In fact, suppose that D1D2 then there exists a vertex i∈[n] for which the number of pieces incident on i with respect to D1 and D2 is different. Thus, m(i1)(i+1)(D1)m(i1)(i+1)(D2) where m(i1)(i+1)(Di) denotes the entry m(i1)(i+1) for the matrix Di. Since the quiddity sequences are different for D1 and D2, this implies the lemma.

Corollary 2.13. There is a one to one correspondence between the sets Dn and MD()n and hence there is a one to one correspondence between the classes D and MD.

Taking advantage of the mentioned one to one correspondence between D and MD, we can introduce a structure of Set operad in the collection MD=n1MD()n of all BCI-matrices. Let MD˜ and MD^ be two arbitrary BCI-matrices such that MD˜MD()n and MD^MD()m, where D˜ and D^ are dissections of Pn and Pm respectively. Then, we can define for i∈ [n]

MD˜iM D^ =M D ˜ °i D^ =MD˜n+m1(i) D^ n+m1(i),

where D˜n+m1(i) D^ n+m1(i) reflects the process of glue of dissections.

A parking function of length m is a sequence of positive integers (a1,,am) such that its non-decreasing rearrangement (b1,,bm) satisfies bii for all i=1,,m. We have

Theorem 2.14. Consider n3 arbitrary and let DDn be any dissection for an n-gon. Then its quiddity sequence

qD=(m2n,m13,m24,m35,,m(n3)(n1),m(n2)n,m1(n1))=(q1,q2,,qn1,qn),

is a parkin function of length n.

Proof. We prove this result by induction on n. Next, we show the sets R3,R4,R5 of non-decreasing rearrangements for the quiddity sequences corresponding to dissections of n-gons in the cases n=3,4,5. They are

R3={(1,1,1)},R4={(1,1,1,1),(1,1,2,2)}R5={(1,1,1,1,1),(1,1,1,2,2),(1,1,2,2,3)},

it is clear that the sequences belong to these sets satisfy the property bi≤ i. Let us assume that the result holds for k=n, that is, any quiddity sequence qD is a parking function for all DDn. Observe now that all dissection D¯Dn+1 can be obtained from one D˜ belongs to Dn by adding a vertex in two different forms, 1) gluing a triangle to one of the sides or 2) placing a new vertex on one of the sides.

Next, we divide the proof in two parts, one for each procedure. Observe first that in both forms of construction, the quiddity sequence qD¯ can be calculate by means of the quiddity sequence qD˜.

If the variant 2) was done in order to obtain D¯ and being (b1,,bn) the non-decreasing rearrangement for qD˜ (so from our hypotheses it follows that bii for all i), then (1,b1,,bn) is the non-decreasing rearrangement corresponding to qD¯. Because qD¯ is obtained from qD˜ by inserting a 1 in the last vector. It implies that qD¯ is a parking function.

On the other case, suppose that the construction 1) was carried out and that the triangle was inserted in the side corresponding to the consecutive vertices i and i+1. Assume alsothat the components qi and qi+1 of qD˜ transform in the components bk and bl of its non-decreasing rearrangement (b1,,bn) where bkbl (the proof for blbk is the same), then the non-decreasing rearrangement corresponding to qD¯ is (1,b1,,bk1,bk+1,bk+1,,bl1,bl+1,bl+1,,bn). It shows again that qD¯ is a parking function.

The proof is concluded.

In this section, we discussed the usefulness of the concept of outer chain of vertices (these chains of vertices correspond to empty sub-polygons located at the border of a given polygon) in the form and construction of the BCI-matrices.

As it was mentioned, for practical purposes in every n-gon we identify the vertex i with i+kn for k=1,2,.

Definition 3.15. Let D be a dissection such that DDn for all n and s ≤ t. We say that a subset of consecutive vertices s,s+1,,t form an outer chain of vertices for D if (s-1,t+1) is a diagonal of D and none of the vertices s,s+1,,t is an end of a diagonal of this dissection. We indicate this fact with the following notation <s,,t>D. The number l<s,,t>D=ts+1 is called the length of <s,,t>D. In this case the (t-s+3)-gon constructed with the vertices s1,s,,t,t+1 is an empty sub-polygon of D. For convenience this polygon (a piece of D) will be denoted by Q(s1,t+1).

For a dissection fixed, outer chains of vertices always exist when it is not the empty dissection.

Example 3.16. In the following dissection for the labeled 6-gon

the vertices 4 and 6 give rise to outer chains of length one while the vertex 2 does not constitute an outer chain.

It is obvious that if D is a dissection of a polygon and all outer chains of vertices have the same length this does not guarantee that D is a d-angulation for some d given. A simple example of this fact is the dissection for the 7-gon (1.7) where each outer chain has length 1, however the dissection is not a triangulation. Now, if D is a d-angulation of a polygon all outer chain must have length equal to d-2.

The following simple observation may be very useful in what follows.

Remark 3.17. Let <s,,t>D be an outer chain of a dissection D for a polygon P or order n. If we remove the vertices s,s+1,,t of P one obtains a new polygon QP\<s,,t>D of order n-(t-s+1). The dissection D of P leads to a dissection D(QP\<s,,t>D) of QP\<s,,t>D that is composed of all diagonals of D except the diagonal (s-1,t+1) which is a border side for the new polygon.

Here an important comment to be considered for what follows is imposed. The vertices of the polygon QP\<s,,t>D must be relabeled starting from the lesser of the vertices that was not canceled. To make explicit the comment, consider the following two dissections for the 6-gon

for which the vertices 1,2 represent an outer chain. Then, after removing these vertices, we obtain the two basic triangulations of a rectangle

We have

Proposition 3.18. Let <s,,t>D be an outer chain of a dissection D for a Polygon. Suppose that the vertex i is not in {s,s+1,t}, then under this assumption, the entries mis,mi(s+1),,mit of the BCI-matrix MD are all equal. Hence, since MD is a symmetric matrix also the entries msi,m(s+1)i,,mti are equal. On other hand, the entries mik for k=s,s+1,,t can be calculated through the following formula

mik=mi(s1)+mi(t+1).

Proof. If the length of the outer chain is 1 the first statement is obvious. Suppose now that 2l<s,,t>D. For every k such that s < k≤ t, all the walks of i to k arise in the following form: let Qi+1,Qi+2,,Qs1 be a walk of i to s, then

Qi+1,Qi+2,,Qs1, Q (s1,t+1),, Q (s1,t+1)(ks+1)times,

is a walk of i to k. Note that the possibility Qs1=Q(s1,t+1) is not excluded. In fact, it will be the case due to ks+1ts+1. Thus, the first statement holds.

Since mis==mit, to prove (3.2) we pay attention in mis (we could have fixed any other entry mik for skt, because the reasoning is the same). The walks wis from i to s arise in the two following ways

  • 1. To any walk wi(s1) of i to s-1, we add the polygon Q(s1,t+1), that is, wis=wi(s1),Q(s1,t+1),

  • 2. To every walk wi(t+1) of i to t+1, we remove the last terms corresponding to the sequence

Q(s1,t+1),,Q(s1,t+1)(ts+1)times,

in other words

wis=wi(t+1)\ Q (s1,t+1),,Q (s1,t+1)the(ts+1)lasttermsofwi(t+1).

This shows (3.2). Thus, the proposition is proved.

Also, we have the following:

Proposition 3.19. Let P be a polygon with n vertices and D a dissection of P. Suppose that <s,,t>D is an outer chain of vertices for D. Consider i, j such that to go from vertex i to the vertex j in the counterclockwise sense the order of appearance is istj. Then, to calculate mij directly (without using the argument of symmetry of the BCI-matrix associated to a dissection D) we can ignore the vertices {s,s+1,t}, in other words these vertices are invisible for this counting. Even more, and this is the main statement of proposition

mij(MD)=mi^j^(MD(QP\<s,,t>D )),

where i^ and j^ are the new label of the vertices i and j for the polygon QP\<s,,t>D.

Proof. All walks wij of i to j arise in the following form

wij=wis, Q (s1,t+1),,Q (s1,t+1)(ts+1)times,wtj,

for wis and wtj conveniently chosen, meaning that they are selected in such a way that the second axiom for walks is satisfied. On the other hand

wi^j^(QP\<s,,t>D,D(QP\<s,,t>D))=wi^(t+1)^,w(s1)^j^,

where wis=wi^(t+1)^,wtj=w(s1)^j^ and wi^(t+1)^,w(s1)^j^ is a walk of i^ to j^ in the polygon QP\<s,,t>D with respect to the dissection D(QP\<s,,t>D). Moreover, in this manner one recovers every walk of i^ to j^.

Proposition 3.20. Let <s,,t>D be an outer chain of vertices of a dissection D for a polygon. Then the BCI-matrix MD associated to D has one of the following two forms:

A) The outer chain satisfies that s<s+1<<t1<t in which case

MD=(A)(X)(B)(Xt)(D(ts+1))(Y)(C)(Yt)(D),

where A is a matrix of order s-1, X has order (s1)×(ts+1), B is of order (s1)×(nt+1). Finally, the matrices C, Y and D have order (nt+1)×(s1), (nt+1)×(ts+1) and (nt+1)×(nt+1) respectively. The columns of the matrix X are all equal. Also, the rows of Y are all equal. Note that in (3.4), necessarily At=A, C=Bt and Dt=D.

On other hand, the matrices A,B,C and D are such that

MD(QP\<s,,t>D)=(A)(B)(C)(D).

B) The outer chain is of the form s,s+1,,n,1,2,,t1,t, then we have

MD=(A)(X)(B)(Xt)(MD(QP\<s,,t>D ))(Y)(C)(Yt)(D),

where At=A, Dt=D and C=Bt. The rows of X and Yt are all equal. If m is the number the vertices of the outer chain <s,s+1,,n,1,2,,t1,t>D then

MDnm=(A)(B)(C)(D).

Proof. Except for the presence of the matrix D(ts+1) in (3.4), the form A) follows from remark 3.17 and propositions 3.18 and 3.19. Now, since <s,,t>D is an outer chain of vertices, hen if i,j{s,,t} and i≠ j it follows that mij=mji=1 and if i=j we have mii=0. This justifies the occurrence of the matrix D(ts+1) in MD. Using the same arguments we can to prove B), the difference consists in that the locations of the empty matrix and MD(QP\<s,,t>D) in MD are exchanged.

Next, we will illustrate (3.1) with examples corresponding to different dissections of a polygon with 6 vertices.

1) For the dissection D[(1,4),(4,6)]6 the vertices 2,3 form an outer chain and we have

MD[(1,4),(4,6)]6=011121101132110132111011233101122110,

hence,

A=(0),B=121,C=121,D=011101110,

and

X=11,Y=132132.

Also, observe that

MD[(1,4)(4,6)]6QP\<2,3> D[(1,4)(4,6)]6 =0121101121011110=MD[(2,4)]4.

2) In the dissection D[(4,6)]6 the vertices 1,2,3 constitute an outer chain and one can see that

MD[(4,6)]6=011121101121110121111011222101111110,

in this case, we only have Y, Yt and D:

Y=121121121,D=011101110,

and

MD[(4,6)]6QP\<1,2,3> D[(4,6)]6 =011101110=MD3.

3) Consider now the dissection D[(1,3)]6. Then, 4,5,6 is an outer chain and we have

MD[(1,3)]6=011111101222110111121011121101121110.

Hence,

A=011101110,X=111222111,

moreover

MD[(1,3)]6QP\<4,5,6> D[(1,3)]6 =011101110=MD3.

We now give an example of case B) in the previous proposition. For the dissection D[(4,7),(5,7)]9 for which 8,9,1,2,3 is an outer chain, we calculate its corresponding BCI-matrix

MD[(4,7),(5,7)]9=011123111101123111110123111111012111222101122333210133111111011111123101111123110.

In this, we have colored the matrices

A,B,C,DandMD[(4,7),(5,7)]9QP\<8,9,1,2,3> D[(4,7),(5,7)]9 =MD[(2,4)]4,

and it is clear that with the matrices A,B,C and D we can construct the matrix MD5.

Here, operations of BCI-matrices are defined which insert rows and columns in a way to keep the symmetry and the BCI-properties. This part of the article is an algebraic version of what was done in the previous section.

Concretely, we study transformations on elements of M(). The k-enlargement of a matrix MM()n where 1kn+1 is the matrix ΠkM of order n+1 defined in the following form: we insert in M one row and one column which become the k-th row and k-th column respectively for ΠkM. First, let us assume that k1 and kn+1, then we set (ΠkM)kk=0 and the remainding entries are filled using the following rule, each entry of the increased row is the sum of the respective entries of the rows k-1 and k of the initial matrix M.

If the additional row is the first or the last for ΠkM, then we should sum the respective elements of the rows 1 and n of M and also put (Π1M)11=0 or (Πn+1M)(n+1)(n+1)=0. Finally, the same procedure is used to fill the remaining entries of the new column. The matrix ΠkM constructed is automatically symmetric.

Example 4.21. It is possible to verify that

Π1MD3=Π3MD3=MD[(2,4)]4,Π2MD3=Π4MD3=MD[(1,3)]4,

and also

Π1MD4=MD[(2,5)]5 Π2MD4=MD[(1,3)]5 Π3MD4=MD[(2,4)]5
Π4MD4=MD[(3,5)]5 Π5MD4=MD[(1,4)]5 Π1MD[(1,3)]4=MD[(2,4),(2,5)]5
Π2MD[(1,3)]4=MD[(1,3),(1,4)]5 Π3MD[(1,3)]4=MD[(1,4),(2,4)]5 Π4MD[(1,3)]4=MD[(1,3),(3,5)]5
Π5MD[(1,3)]4=MD[(1,3),(1,4)]5 Π1MD[(2,4)]4=MD[(2,5),(3,5)]5 Π2MD[(2,4)]4=MD[(1,3),(3,5)]5
Π3MD[(2,4)]4=MD[(2,4),(2,5)]5 Π4MD[(2,4)]4=MD[(2,5),(3,5)]5 Π5MD[(2,4)]4=MD[(1,4),(2,4)]5

Proposition 4.22. Let us assume that MM()n, then its k-enlargement ΠkM belongs to M()n+1 for all k=1,,n+1.

Proof. It is clear that by construction ΠkM0, with entries taking integer values. Observe also that for the same reason the entries of the matrix outside of the three main diagonals are positive. On the other hand, we already know that the matrix ΠkM must be symmetric.

  • · Suppose that k ≠ 1 and k≠ n+1. Then,

    (ΠkM)1(n+1)=(M)11+(M)1n=0+1=1,

    and

    (ΠkM)(n+1)1=(M)n1+(M)nn=1+0=1.

    It only remains to see that the form (see (1.1)) of the three main diagonals is preserved in the new matrix ΠkM. Now, in the matrix M the sub-matrix built with the entries of the rows and columns k-1 and k is 0110 and it becomes in the sub-matrix 011101110 of ΠkM corresponding to their entries of the rows and columns k-1, k and k+1.

  • · We observe that there are two other cases to analyze (that is, k=1 and k=n+1) however they can be proved in a similar way.

Remark 4.23. Let us suppose that M=MD where D is a dissection of an n-gon. Then, ΠmMD for m=1,,n+1 is the matrix corresponding to the induced dissection D^ for D for the (n+1)-gon that results from the insertion of an outer chain of length 1 between the vertices m-1 and m of the initial n-gon. For Π1MD the new vertex is labeled by 1 and for Πn+1MD the new vertex will be the vertex n+1 for the polygon obtained. In other cases, the new vertex becomes the vertex m. Taking into account the new labeling for the initial vertices, let us assume that p and q are the labels of the old vertices m-1 and m, then we have that D^=D(p,q) and ΠmMD=MD^. We can say that in terms of the geometry, this is just gluing a triangle to the dissection. We could view this also as an example of a glue of dissections D˜iD^ where D^ is in D2 and i is depending on m.

The notion of the k-enlargement of an M-matrix can be generalized in the following form.

Definition 4.24. A \textbf{sequential enlargement of length d} of MM()n is a new matrix Π{k,k+1,,k+d1}M of order n+d obtained in the following form: between the columns k-1 and k of M we insert d new columns; also, we insert d new rows between the rows k-1 and k of this matrix. The intersection of the d new columns and rows is the matrix MDd. Π{1,2,,d}M means that we insert d columns and rows before the first row and the first column of M. Now, the meaning of Π{n+1,n+2,,n+d}M is obvious. Since, one must consider that the first row and the first column follow to the last row and last column respectively, then the sequential enlargement Π{n+1,n+2,,n+k1,1,2,,k2}, where k1+k2=d is not excluded.

To the remainder entries of the new matrix (that is, the entries outside the intersection) values following the same rule of a k-enlargement simultaneously are assigned.

It is clear that a k-enlargement is a sequential enlargement of length one. On other hand, each sequential enlargement of an M-matrix gives a symmetric matrix.

Example 4.25. We give a concrete example of the above definition. For instance

Π{1,2}01110111001100111011100112110121110112210111110=MD[(3,5)]5,
Π{2,3}01110111001101101011100111110112110121110112210=MD[(1,4)]5,
Π{3,4}01110111001110101101100122110111210112110111110=MD[(2,5)]5,
Π{4,5}01110111001110111001100111110122110111210112110=MD[(1,3)]5.

Proposition 4.26. For anyMM()n, Π{k,k+1,,k+d1}MM()n+d for k=1,2,,n,n+1 and all d0.

Proof. The proof of this proposition is very similar to the proof of proposition 4.22, hence it will be omitted.

Remark 4.27. In general, Π{k,k+1,,k+d1}MD where DDn is equivalent to find the BCI-matrix corresponding to inserting an outer chain of length d between the vertices k-1 and k of an n-gon dissected by D. The labels of the new (n+d)-gon are assigned following a procedure similar to that of observation 4.23. We could view this as an example of a glue of dissections D˜iD^ where D^ is in Dd1.

Also, we can insert multiple rows and columns in an M-matrix but not consecutively. We capture this fact in a definition

Definition 4.28. A non-sequential enlargement of length d of MM()n is a new matrix Π[k1,k2,,kd]M of order n+d where 1k1<k2<<kdn+d such that ki+1<ki+1 for all i. The new matrix is constructed in the following manner: we insert d new columns and rows in M such that with respect to Π[k1,k2,,kd]M they are the k1-th, k2-th,…,kd-th rows and columns; moreover, the intersection of the row and column ki-th should be considered 0 for all j=1,…, d. To the remainder entries of the new matrix we assign values following the same rule of a k-enlargement listed above. Also, we just have to respect the following order to fill the new entries in the matrix Π[k1,k2,,kd]M: first we must fill the row and column k1, then the row and column k2 and so on until to end with the row and column kd.

Example 4.29. We illustrate the previous definition with two simple examples

Π[1,3]011101110001101011100132110111310122110111210=MD[(2,4),(2,5)]5,
Π[2,4]011101110011010101100112110132110112310112110=MD[(1,3),(3,5)]5,

Proposition 4.30. For any MM()n, we have that Π[k1,k2,,kd]MM()n+d.

Proof. The proof follows of the following equality

Π[k1,k2,,kd]M=ΠkdΠkd1Πk2Πk1M.

Remark 4.31. Taking into account (4.1), we have that Π[k1,k2,,kd]MD is equivalent to find in an iterated fashion the BCI-matrix of a dissection of an polygon with (n+d) vertices corresponding to insert iteratively d outer chains of length 1 between the vertices of an n-gon dissected by D. In this case the insertion is strictly non-consecutive. At each iteration the polygon obtained must be relabeled following the same rules of the usual k-enlargement.

To show the use of the different types of enlargements introduced before, we now see that it is possible to recover the set MD()6{MDn} using this type of operations on BCI-matrices of order 4 and 5. We have

1. For the matrices MD()6(1)

Π1MD5=MD[(2,6)]6 Π2MD5=MD[(1,3)]6 Π3MD5=MD[(2,4)]6
Π4MD5=MD[(3,5)]6 Π5MD5=MD[(4,6)]6 Π6MD5=MD[(1,5)]6
Π{3,4}MD4=MD[(2,5)]6 Π{4,5}MD4=MD[(3,6)]6 Π{5,6}MD4=MD[(1,4)]6

2. For the matrices MD()6(2)

Π{1,2}MD[(1,3)]4=MD[(3,5),(3,6)]6 Π{2,3}MD[(1,3)]4=MD[(1,4),(1,5)]6
Π{3,4}MD[(1,3)]4=MD[(1,5),(2,5)]6 Π{4,5}MD[(1,3)]4=MD[(1,3),(3,6)]6
Π{5,6}MD[(1,3)]4=MD[(1,3),(1,4)]6 Π{1,2}MD[(2,4)]4=MD[(3,6),(4,6)]6
Π{2,3}MD[(2,4)]4=MD[(1,4),(4,6)]6 Π{3,4}MD[(2,4)]4=MD[(2,5),(2,6)]6
Π{4,5}MD[(2,4)]4=MD[(2,6),(3,6)]6 Π{5,6}MD[(2,4)]4=MD[(1,4),(2,4)]6
Π[1,3]MD4=MD[(2,4),(2,6)]6 Π[2,4]MD4=MD[(1,3),(3,5)]6
Π[3,5]MD4=MD[(2,4),(4,6)]6 Π[4,6]MD4=MD[(1,5),(3,5)]6
Π[1,4]MD4=MD[(2,6),(3,5)]6 Π[1,5]MD4=MD[(2,6),(4,6)]6
Π[2,5]MD4=MD[(1,3),(4,6)]6 Π[2,6]MD4=MD[(1,3),(1,5)]6
Π[3,6]MD4=MD[(1,5),(2,4)]6 Π[1,6]MD[(1,3)]4=MD[(2,4),(2,5))]6
Π[1,6]MD[(2,4)]4=MD[(2,5),(3,5))]6

3. For the matrices MD()6(3)

Π[1,3]MD[(1,3)]4=MD[(2,4),(2,5),(2,6)]6 Π[2,4]MD[(1,3)]4=MD[(1,3),(1,5),(3,5)]6
Π[3,5]MD[(1,3)]4=MD[(1,4),(2,4),(4,6)]6 Π[1,4]MD[(1,3)]4=MD[(2,5),(2,6),(3,5)]6
Π[1,5]MD[(1,3)]4=MD[(2,4),(2,6),(4,6)]6 Π[2,5]MD[(1,3)]4=MD[(1,3),(1,4),(4,6)]6
Π[2,6]MD[(1,3)]4=MD[(1,3),(1,4),(1,5)]6 Π[3,6]MD[(1,3)]4=MD[(1,4),(1,5),(2,4)]6
Π[2,4]MD[(2,4)]4=MD[(1,3),(3,5),(3,6)]6 Π[4,6]MD[(2,4)]4=MD[(1,5),(2,5),(3,5)]6
Π[1,4]MD[(2,4)]4=MD[(2,6),(3,5),(3,6)]6 Π[1,5]MD[(2,4)]4=MD[(2,6),(3,6),(4,6)]6
Π[2,5]MD[(2,4)]4=MD[(1,3),(3,6),(4,6)]6 Π[3,6]MD[(2,4)]4=MD[(1,5),(2,4),(2,5)]6

In this section we propose some future work. BCI-matrix for infinite frieze:

The notion of infinite frieze of positive integers was defined in [14] and [3]. They are arrays consisting of infinitely many rows of positive integers, bounded above by a row of zeros followed by a rows of ones, satisfying the unimodular rule everywhere. A way to present graphically an infinite frieze F=(mi,j)i,j,ji2 is the following

00001111m1,1m0,0m1,1m2,2m1,0m0,1m1,2m2,3m1,1m0,2m1,3m2,4

such that, the relation mijmi+1,j+1mi+1,jmi,j+1=1 holds for ji1. Note that mi,i2=0, mi,i1=1 for all i and mij>0 otherwise.

The simplest example might be the following

000001111122222333334444455555,

which is known as the basic infinite frieze F.

Definition 4.32. As a motivation, we give the definition of one-crossing triangulation. For an one-crossing triangulation of a polygon Pwith n vertices, we mean a set of diagonals having only one crossing point of which it is possible to obtain a triangulation of Pby removing one of the diagonals.

In the above definition, the diagonal that is removed to obtain the triangulation has not to be unique. Then at least in the context of one-crossing triangulations, we can assign a quiddity sequence v=(a1,,an) to every one-crossing triangulation T(1), where its entries have the same meaning as in the case of usual triangulations. On other hand, it is clear that an one-crossing triangulation of a polygon can be considered as a triangulation of a punctured disc, see [1] and [3], where we take the puncture to be the crossing of the diagonals. Now, we adapt the notion of path between vertices for an one-crossing triangulation of an arbitrary polygon.

Observe before that each sub-polygon of an one-crossing triangulation is a triangle in the following sense, these triangles are of two types : 1) triangles whose vertices are also vertices for the polygon, 2) triangles for which the puncture is a vertex and the other two vertices are also vertices of the polygon.

Let T(1) be an one-crossing triangulation of an n-gon Pn, and let i and j vertices of Pn, such that i+1j. We identify i+kn with i for all k=1,2,. A sequence Qi+1,,Qj1 of triangles of T(1) is called a (counterclockwise) path from i to j if it satisfies the following properties

  • 1. The triangle Qk is incident to vertex k for all k{i+1,i+2,,j1}.

  • 2. In the sequence Qi+1,Qi+2,,Qj2,Qj1, every triangle of T(1) appears at most once.

For i+1j the number of (counterclockwise) paths from i to j is denoted mi,j. It is clear that mi,i=0. Then, following [12] we introduce the n×n-matrix MT(1) associated to the one-crossing triangulation T(1) as MT(1)=(mi,j)1i.jn which will be called from now the Broline-Crowe-Isaacs (BCI) matrix corresponding to T(1).

This construction is a direct generalization of the one proposed in [6] for non-crossing triangulations.

Example 4.33. This example is quite illustrative. The infinite frieze (4.1) follows from the one-crossing triangulation of 4-gon T(1)={(1,3),(2,4)}

with quiddity sequence v=(2,2,2,2). Each entry represents the number of triangles incident in the respective vertex.

On the other hand, the matrix of Broline-Crowe-Isaacs for this example is

MT(1)=0123301223011230.

Example 4.34. Consider a 5-gon provided with a 1-crossing triangulation as in the following figure

with quiddity sequence v=(3,2,2,3,1). This gives rise to an infinite frieze. We present it below together with its Broline-Crowe-Isaacs matrix:

Fv=0000011111322315352277333164444,

and

MFv=0123730125230131230113570

From (4.5) and (4.6) we see that Fv has two different pyramids in its fundamental domain

Fv=1111322537,Fv=1315227333.

We propose the following problems

  • 1. To study the Broline-Crowe-Issacs-matrix for any punctured discs. In particular, it will be interesting to find a formula for the determinant of the corresponding BCI-matrix in this context (if it exists). For instance, for an one-crossing triangulation the following question arises: Is the determinant of its BCI-matrix related to the number of triangles?

  • 2. To find suitable products between punctured discs that would allow us the use of operad theory between their BCI-matrices.

  1. K. Baur and R. J. Marsh, Frieze patterns for punctured discs, J. Algebraic Combin., 30(2009), 349-379.
    CrossRef
  2. K. Baur and R. J. Marsh, Categorification of a frieze pattern determinant, J. Combin. Theory Ser. A, 119(2012), 1110-1122.
    CrossRef
  3. K. Baur, M. J. Parsons and M. Tschabold, Infinite friezes, European J. Combin., 54(2016), 220-237.
    CrossRef
  4. C. Bessenrodt, T. Holm and P. Jorgensen, Generalized frieze pattern determinants and higher angulations of polygons, J. Combin. Theory Ser. A, 123(2014), 30-42.
    CrossRef
  5. C. Bessenrodt, Conway-Coxeter friezes and beyond: polynomial weighted around disseted polygons and generalized friezes patterns, J. Algebra, 442(2015), 80-103.
    CrossRef
  6. D. Broline, D. W. Crowe and I. M. Isaacs, The geometry of frieze patterns, Geometriae Dedicata, 3(1974), 171-176.
    CrossRef
  7. P. Caldero and F. Chapoton, Cluster algebras as Hall algebras of quiver representations, Comment. Math. Helv., 81(2006), 595-616.
    CrossRef
  8. F. Chapoton, Operads and algebraic combinatorics of trees, S'em. Lothar. Combin., 58(2008).
  9. J. H. Conway and H. S. M. Coxeter, Triangulated polygons and frieze patterns, Math. Gaz., 57(1973), 175-183.
    CrossRef
  10. M. Cuntz and I. Heckenberger, Weyl groupoids of rank two and continued fractions, Algebra Number Theory, 3(2009), 317-340.
    CrossRef
  11. M. Cuntz, On wild frieze patterns, Exp. Math., 26(2017), 342-348.
    CrossRef
  12. S. Morier-Genoud and Coxeter's frieze patterns at the crossroads of algebra, geometry and combinatorics, Bull. Lond. Math. Soc., 47(2015), 895-938.
    CrossRef
  13. J. M. S. Sim˜oes-Pereira and C. M. Zamfirescu, Submatrices and non-tree-realizable distance matrices, Linear Algebra Appl., 44(1982), 1-17.
    CrossRef
  14. M. Tschabold, Arithmetic infinite friezes from pintured discs, Preprint, arXiv, (), 1503.04352.