Every 4-bounded matrix is skew-symmetrizable

Mathieu St-Pierre

Résumé. Dans cet article, nous étudions les diagrammes et les matrices 4-bornés. Ce sont des généralisations des concepts de diagrammes et de matrices 2-finis apparaissant dans la théorie des algèbres amassées.

Abstract. In this paper, we study the 4-bounded matrices and diagrams. These are generalizations of 2-finite matrices and diagrams occuring in the context of cluster algebras.

1 Introduction

Fomin and Zelevinsky introduced (in [1]) the concept of cluster algebra in order to understand the dual canonical basis of the quantized enveloping algebra and total positivity for algebraic groups.

A cluster algebra is determined by a set of variables and a sign-skew-symmetric matrix. Mutations are performed on both and in this way we generate new sets of variables and new matrices. Fomin and Zelevinsky have shown as one of the most important results about cluster algebras (see [2]) that the number of variables obtained by mutations is finite exactly when the sign-skew-symmetric matrix is 2-finite. We propose a generalization of 2-finite matrices that we call 4-bounded matrices and show as the main result of the paper that these matrices are skew-symmetrizable.

No knowledge of cluster algebras is needed to understand this paper. We begin by recalling the important definitions. Then, we will prove as the main result of this paper that every 4-bounded matrix is skew-symmetrizable. Finally we will give some necessary conditions for a matrix to be 4-bounded, including a classification of all 4-bounded cycles.

2 Definitions

All definitions in this section come from [2], except the definition of a 4-bounded matrix which seems to be new.

We first need to recall what a matrix mutation is. Let B = (b_{ij}) and B′ = (b′_{ij}) be real square matrices of the same size. We say that B′ is obtained from B by a matrix mutation in direction k if

b′_{ij} = \{ \begin{matrix}−b_{ij} & if i = k or j = k \\ b_{ij} + \frac{|b_{ik}|b_{kj} + b_{ik}|b_{kj}|}{2} & otherwise. \end{matrix}

I would first like to thank Thomas Brüstle for his help. Thanks also to the NSERC (Natural Sciences and Engineering Research Coucil of Canada) for their financial support.

We will write B′ = μ_{k}(B) if B′ is obtained from B by a matrix mutation in direction k. It is important to know that a matrix mutation of an integral matrix is also integral and that μ_{k}(μ_{k}(B)) = B for any matrix B. Also, if two matrices are obtained from each other by a sequence of matrix mutations followed by a simultaneous permutation of rows and columns, we will say that they are mutation equivalent (see [2]).

Definition 2.1 A square matrix B = (b_{ij}) is sign-skew-symmetric if, for any i and j, either b_{ij} = b_{ji} = 0 or b_{ij}b_{ji} < 0.

Definition 2.2 The diagram of a sign-skew-symmetric matrix B = (b_{ij})_{i,j∈I} is the weighted directed graph Γ(B) with the vertex set I such that there is a directed edge from i to j if and only if b_{ij} > 0, and this edge is assigned the weight |b_{ij}b_{ji}|.

Note that different sign-skew-symmetric matrices can have the same diagram. An example of such a situation follows.

Example 2.3 Consider A = [ \begin{matrix}0 & 4 & −2 \\ −1 & 0 & 3 \\ 2 & −1 & 0 \end{matrix} ] and B = [ \begin{matrix}0 & 2 & −1 \\ −2 & 0 & 1 \\ 4 & −3 & 0 \end{matrix} ]. These two

sign-skew-symmetric matrices have the same diagram as follows:

[figure: 4; 3; 4; 1; 2; 3]

Definition 2.4 A sign-skew-symmetric matrix B is 4-bounded if it has integer entries and every matrix B′ = (b′_{ij}) mutation equivalent to B is sign-skew-symmetric and |b′_{ij}b′_{ji}| ≤ 4 for every i and j.

The definition of a 2-finite matrix is the same as the 4-bounded matrix definition except that we replace the condition |b′_{ij}b′_{ji}| ≤ 4 by |b′_{ij}b′_{ji}| ≤ 3.

Definition 2.5 A square matrix B is skew-symmetrizable if there exists a diagonal matrix D with positive diagonal entries such that DB = −(DB)^{T}.

3 Main theorem

We know from [2, Proposition 7.2] that a 2-finite matrix is skew-symmetrizable. We will extend this result to 4-bounded matrices. This is a more general result because obviously every 2-finite matrix is 4-bounded. However we cannot expect every matrix to be skew-symmetrizable. To determine if a matrix is skew-symmetrizable, we have the following equivalence that is [2, Lemma 7.4].

Lemma 3.1 A matrix B = (b_{ij}) is skew-symmetrizable if and only if, first, it is sign-skew-symmetric and, second for all k ≥ 3, and all i_{1}, ... , i_{k}, it satisfies

b_{i_{1}i_{2}}b_{i_{2}i_{3}}...b_{i_{k}i_{1}} = (−1)^{k}b_{i_{2}i_{1}}b_{i_{3}i_{2}}...b_{i_{1}i_{k}}  (1)

From this lemma, we can easily verify that if the diagram Γ(B) of a sign-skew-symmetric matrix B is a tree, then B is skew-symmetrizable. Also, we obtain the following corollary that will be used in the next section.

Corollary 3.2 Let B be a skew-symmetrizable matrix. Then the product of edge weights along every cycle of the diagram Γ(B) is a perfect square.

Proof. Suppose that we have a cycle in Γ(B) on vertices i_{1}, i_{2},..., i_{k}. Thus the product of edge weights along this cycle is |b_{i_{1}i_{2}}b_{i_{2}i_{1}}b_{i_{2}i_{3}}b_{i_{3}i_{2}}...b_{i_{k}i_{1}}b_{i_{1}i_{k}}| = |b_{i_{1}i_{2}}b_{i_{2}i_{3}}...b_{i_{k}i_{1}}||b_{i_{2}i_{1}}b_{i_{3}i_{2}}...b_{i_{1}i_{k}}|. From (1), we obtain that this product is a perfect square. □

The following theorem is the main result of the paper.

Theorem 3.3 Every 4-bounded matrix is skew-symmetrizable.

Lemma 3.4 In the diagram Γ(B) of a 4-bounded matrix B = (b_{ij}), a non-cyclically oriented triangle must have all edge weights 1.

Proof. Suppose that b_{ij}, b_{ik}, b_{kj} are positive integers for some distinct i, j, k. Thus in B′ = μ_{k}(B) we have b′_{ij} = b_{ij} + b_{ik}b_{kj} ≥ 2 and b′_{ji} = b_{ji} − b_{jk}b_{ki} ≤ −2. To get |b′_{ij}b′_{ji}| ≤ 4 , we have no other choice than b_{ij} = b_{ik} = b_{kj} = 1, b_{ji} = b_{jk} = b_{ki} = −1. □

The next proposition is the analogue of [2, Lemma 7.6] for 4-bounded matrices.

Proposition 3.5 Let B be a 4-bounded matrix. Then

b_{ij}b_{jk}b_{ki} = −b_{ji}b_{kj}b_{ik}  (2)

for any distinct i, j, k. Also, every triangle in Γ(B) is either a non-cyclically oriented triangle with all edge weights 1, or a cyclically oriented triangle with edge weights {1, 1, 1}, {2, 2, 1}, {3, 3, 1}, {4, 1, 1}, {4, 2, 2}, {4, 3, 3} or {4, 4, 4}.

Proof. First note that if any of b_{ij}, b_{jk}, b_{ki}, b_{ji}, b_{kj}, or b_{ik} is zero, then (2) is automatic. Thus, we will suppose that we have a triangle on vertices i, j, k. If the triangle is non-cyclically oriented, by applying Lemma 3.4, then we are done; clearly this case respects (2). So we will only consider the case of a cyclically oriented triangle. It means that we can consider without loss of generality that

B = [ \begin{matrix}0 & a_{1} & −c_{1} \\ −a_{2} & 0 & b_{1} \\ c_{2} & −b_{2} & 0 \end{matrix} ] ,

where a_{1}, b_{1}, c_{1}, a_{2}, b_{2}, c_{2} are positive integers. We can also assume without loss of generality that the entry of maximal absolute value in B is −c_{1}. We will consider three cases pertaining to

μ_{2}(B) = [ \begin{matrix}0 & −a_{1} & −c_{1} + a_{1}b_{1} \\ a_{2} & 0 & −b_{1} \\ c_{2} − a_{2}b_{2} & b_{2} & 0 \end{matrix} ] ,

the other cases making μ_{2}(B) not sign-skew-symmetric.

Case 1. c_{2} − a_{2}b_{2} > 0 and −c_{1} + a_{1}b_{1} < 0. It means that Γ(μ_{2}(B)) is a non-cyclically oriented triangle, so using Lemma 3.4, we know that

μ_{2}(B) = [ \begin{matrix}0 & −1 & −1 \\ 1 & 0 & −1 \\ 1 & 1 & 0 \end{matrix} ] .

Applying μ_{2} to μ_{2}(B) again, we obtain that

B = [ \begin{matrix}0 & 1 & −2 \\ −1 & 0 & 1 \\ 2 & −1 & 0 \end{matrix} ] .

One can easily verify that the entries of B respect (2) and that edge weights of Γ(B) are {4, 1, 1}.

In the last two cases, it is important to keep in mind that the inequalities a_{1}a_{2} ≤ 4, b_{1}b_{2} ≤ 4 and c_{1}c_{2} ≤ 4 must be respected.

Case 2. c_{2} − a_{2}b_{2} = 0 and −c_{1} + a_{1}b_{1} = 0. From these two equalities, we easily find (2). Subcase 2.1. c_{1} = 1. Because c_{1} is maximal, we have a_{1} = b_{1} = a_{2} = b_{2} = c_{2} = 1, so the set of edge weights {a_{1}a_{2}, b_{1}b_{2}, c_{1}c_{2}} is {1, 1, 1}. Subcase 2.2. c_{1} = 2. We know that {a_{1}, b_{1}} = {2, 1}. If c_{2} = 1, then a_{2} = b_{2} = 1, and the set of edge weights {a_{1}a_{2}, b_{1}b_{2}, c_{1}c_{2}} is {2, 2, 1}. If c_{2} = 2, we suppose that a_{1} = 2 and b_{1} = 1 (the case a_{1} = 1 and b_{1} = 2 is analogous). If a_{2} = 1 and b_{2} = 2, then {a_{1}a_{2}, b_{1}b_{2}, c_{1}c_{2}} = {4, 2, 2}. Otherwise a_{2} = 2 and b_{2} = 1, then B is not 4-bounded because |b′_{23}b′_{32}| = 9 in B′ = μ_{1}(B). Subcase 2.3. c_{1} = 3. We have no other choice than {a_{1}, b_{1}} = {3, 1} and c_{2} = a_{2} = b_{2} = 1. In this case, the set of edge weights {a_{1}a_{2}, b_{1}b_{2}, c_{1}c_{2}} is {3, 3, 1}. Subcase 2.4. c_{1} = 4. We know that c_{2} = a_{2} = b_{2} = 1. If a_{1} = b_{1} = 2, then {4, 2, 2} is the set of edge weights of Γ(B). The other possibility is {a_{1}, b_{1}} = {4, 1}. Suppose that a_{1} = 4 and b_{1} = 1 (the other case is similar), then B is not 4-bounded because |b′_{23}b′_{32}| = 9 in B′ = μ_{1}(B).

Case 3. c_{2} − a_{2}b_{2} < 0 and −c_{1} + a_{1}b_{1} > 0. In this case, we obtain

1 ≤ −c_{1} + a_{1}b_{1} ≤ 4,  (3)
−4 ≤ c_{2} − a_{2}b_{2} ≤ −1.  (4)

Subcase 3.1. c_{1} = 1. Because c_{1} is the maximum of {a_{1}, b_{1}, c_{1}, a_{2}, b_{2}, c_{2}}, we would also have a_{1} = b_{1} = a_{2} = b_{2} = c_{2} = 1, contradicting (3) and (4). Subcase 3.2. c_{1} = 2. Then a_{1} = b_{1} = 2 to satisfy (3), and c_{2} − a_{2}b_{2} ≥ −2 to get |(−c_{1} + a_{1}b_{1})(c_{2} − a_{2}b_{2})| ≤ 4. Either c_{2} = 1 or c_{2} = 2. In the former case, {a_{2}, b_{2}} = {2, 1} and we respect (2), again having {4, 2, 2} as the set of edge weights of Γ(B). In the latter case, a_{2} = b_{2} = 2, satisfying (2); the set of edge weights of Γ(B) is {4, 4, 4}. Subcase 3.3. c_{1} = 3. Clearly c_{2} = 1.

1. If {a_{1}, b_{1}} = {3, 2} (suppose that a_{1} = 3 and b_{1} = 2, the other case is analogous), then a_{2} = 1 and b_{2} = 2. It is easy to verify (2) and that the edge weights of Γ(B) are {4, 3, 3}.

2. a_{1} = b_{1} = 2 . If a_{2} = 2 and b_{2} ∈ {1, 2}, then in B′ = μ_{2}μ_{1}(B), |b′_{13}b′_{31}| = 5. If a_{2} = 1 and b_{2} = 2, then in B′ = μ_{2}μ_{3}(B), |b′_{13}b′_{31}| = 5.

3. {a_{1}, b_{1}} = {4, 1}. Suppose that a_{1} = 4 and b_{1} = 1, the other case being analogous. Then a_{2} = 1. If b_{2} = 2, then in B′ = μ_{2}μ_{1}(B), |b′_{13}b′_{31}| = 5. If b_{2} = 3, then μ_{3}(B) is not sign-skew-symmetric. If b_{2} = 4, then μ_{1}(B) is not sign-skew-symmetric.

Subcase 3.4. c_{1} = 4. Then c_{2} = 1. If {a_{1}, b_{1}} = {3, 2} (suppose that a_{1} = 3 and b_{1} = 2, the other case being analogous), then a_{2} = 1 because we must have |a_{1}a_{2}| ≤ 4; it leads to b_{2} = 2 since (4) has to be verified. Then in B′ = μ_{3}(B), |b′_{12}b′_{21}| = 5. Else, {a_{1}, b_{1}} = {4, 2} (suppose that a_{1} = 4 and b_{1} = 2, the other case being similar), then we respect (2) because a_{2} = 1 and b_{2} = 2, and the set of edge weights of Γ(B) is again {4, 4, 4}. □

Now Theorem 3.3 can be proved using Proposition 3.5. In fact, the proof is the same as the proof of [2, Proposition 7.2], replacing 2-finite by 4-bounded.

It suffices to check that every 4-bounded matrix satisfies criterion (1). Suppose this not the case. Among all instances where (1) is violated for some 4-bounded matrix B, pick one with the smallest value of k. Then b_{i_{j},i_{m}} = 0 for any pair of indices (i_{j}, i_{m}) not appearing in (1). (Otherwise we could obtain (1) as a corollary of its counterparts for two smaller cycles.) In other words, the diagram Γ(B) restricted to the vertices i_{1}, ..., i_{k} must be a cycle with no inner edge. Pick any two consecutive edges on this cycle that form an oriented 2-path (that is, b_{i_{j−1}i_{j}}b_{i_{j}i_{j+1}} > 0). (If there is no such pair, we will first need to apply a mutation on an arbitrary vertex i_{j}.) By Equation (2), we have k ≥ 4, hence b_{i_{j−1}i_{j+1}} = 0. Now apply the mutation μ_{i_{j}}. In the resulting matrix, condition (1) for indices i_{1}, ..., i_{j−1}, i_{j+1}, ..., i_{k} will be equivalent to (1) in the original matrix; hence it must fail, contradicting our choice of k. □

4 Classification of 4-bounded chordless cycles

We will now recall the Proposition 8.1 from [2].

Proposition 4.1 For a skew-symmetrizable matrix B, the diagram Γ′ = Γ(μ_{k}(B)) is uniquely determined by the diagram Γ = Γ(B) and an index k ∈ I. Γ′ is obtained from Γ as follows:

• The orientation of all edges incident to k are reversed, their weights intact.

• For any vertices i and j which are connected in Γ via a two-edge oriented path going through k (refer to Figure 1 for the rest of notation), the direction of the edge (i, j) in Γ′ and its weight c′ are uniquely determined by the rule

±\sqrt{c} ± \sqrt{c′} = \sqrt{ab}

where the sign before \sqrt{c} (resp., before \sqrt{c′}) is“+” if i, j, k form an oriented triangle in Γ (resp., in Γ′), and is “−” otherwise. Here either c or c′ can be equal to 0.

• The rest of the edges and their weights in Γ remain unchanged.

[figure: a; b; c; k; \underleftrightarrow{μ_{k}}; a; b; c′; k]

Figure 1. Diagram mutation

In situations where Proposition 4.1 can be applied, we write Γ′ = μ_{k}(Γ), and call the transformation μ_{k} a diagram mutation in direction k (as in [2]). Two diagrams related by a sequence of diagram mutations wil be called mutation equivalent. We will say that a diagram Γ is 4-bounded if in any diagram mutation equivalent to Γ, all edge weights are at most 4. Note that when drawing diagrams, a non-oriented edge can be oriented in any direction.

A chordless cycle will be a cycle that does not contain any smaller cycles, i.e. that has no inner edge.

Lemma 4.2 Every 4-bounded chordless cycle that is not cyclically oriented only has edges of weight 1.

Proof. Let Γ be a 4-bounded chordless cycle which is not cyclically oriented. We will make our proof by induction on n, the number of verices in Γ. The case n = 3 has been done in Lemma 3.4, so consider that n ≥ 4. Now in Γ, choose a vertex j such that there is a path through j from j_{1} to j_{2} (if there is no such vertex, first apply a mutation on any vertex). Let Γ′ = μ_{j}(Γ). Then the subdiagram Γ′′ = Γ′ − {j} is a chordless (n − 1)-cycle not cyclically oriented (otherwise going back to Γ, we would contradict the non-cyclic orientation of Γ). Also Γ′′ must have all edges of weight 1, by the induction assumption. So the triangle on vertices j_{1}, j and j_{2} in Γ′ is cyclically oriented with all edges edge of weight 1. It gives us that all edges in Γ are of weight 1. □

[figure: 2; 2; 3; 3; 4; 2; 2; 4; 3; 3; 4; 4; 4; 4]

[figure: 2; 2; 2; 2; 2; 2; 2; 2; 3; 3]

[figure: 2; 2; 2; 2]

Figure 2. 4-bounded chordless cycles

Lemma 4.3 The following diagrams are not 4-bounded, so they cannot appear as subdiagrams of a 4-bounded diagram.

[figure: 4; a); 4; 2; b); 4; 3; c); 4; 4; d)]

[figure: 3; 2; e); 3; 3; f)]

[figure: 3; g); 3; 2; h); 3; 3; i)]

[figure: 2; 2; j); 2; 2; 2; k)]

[figure: 2; 2; l)]

Figure 3. Some non-4-bounded diagrams

Proof. In every case, we will orient edges from left to right and number vertices from left to right. In case a), a mutation on vertex 2 gives a triangle that is not in the list of 4-bounded triangles in Proposition 3.5. In cases b), c), d), e) and f), a mutation on vertex 2 produces an edge of weight greater than 4. In case g), the sequence of mutations μ_{1} ∘ μ_{2} gives a subdiagram of type a) on vertices 2, 3, 4. In cases h), i), j) and k), a mutation on vertex 2 gives respectively a subdiagram of type e), f), a) and b) on vertices 1, 3, 4. Finally for the case l), we will show by induction on n, the number of vertices in the diagram, that we can obtain, by a sequence of diagram mutations, a subdiagram of type j). Suppose that it is true for a given value of n. Now for n + 1 vertices, we can apply the mutation μ_{2} to get a subdiagram of type l) on n vertices. Using the induction assumption, we get the result. □

Proposition 4.4 Let Γ be a 4-bounded chordless n-cycle diagram with n ≥ 3. Then Γ must be one of the diagrams in the Figure 2.

Proof. From Lemma 4.2, we know that all 4-bounded chordless cycles that are not cyclically oriented must have all edge weights 1. So we will now only consider cyclically oriented chordless cycles. The work for triangles has been done in Proposition 3.5, so we can restrict our study to the cases where n ≥ 4. Using Lemma 4.3, we can exclude the possibility of having an edge of weight 4.

Now, we will focus on diagrams that contain an edge of weight 3. Because diagrams e) and f) of the Figure 3 are not 4-bounded, the adjacent edges to an edge of weight 3 must be of weight 1. Moreover, an edge of weight 3 cannot occur if n ≥ 5 since diagrams g), h) and i) of Figure 3 are also not 4-bounded. Now the result of the Corollary 3.2 will be important. Because the product of edge weights along a cycle must be a perfect square, then the only remaining possibility is the square with edges of weight 1 and 3 shown in Figure 2.

Thus, we now have to consider diagrams that have only edges of weight 1 and 2. In cases n ≥ 5, we cannot have two adjacent edges of weight 2 since we know that cases j) and k) in Lemma 4.3 are not 4-bounded; the only remaining possible diagram in case n = 5 is the pentagon shown in Figure 2. For n ≥ 6, the only possible case is that we have the hexagon in Figure 2 because a subdiagram of type l) of Figure 3 cannot occur. The only remaining possibility is the case n = 4. In this situation, keeping in mind that the product of edge weights along a cycle must be a perfect square, we get the last three chordless 4-cycles with edge of weight 1 and 2. □

Résumé substantiel en français. Le sujet de cet article est directement lié aux algèbres amassées. Ce sont les travaux de Fomin et Zelevinsky, entre autres dans [1] et [2], qui ont initié l’étude de ce type d’algèbres. Les matrices 2-finies sont intimement liées aux cas où les algèbres amassées sont de type fini. Nous dirigerons notre intérêt vers les matrices 4-bornées, une généralisation des matrices 2-finies.

Nous rappelons tout d’abord les définitions importantes, qui proviennent toutes de [2], exception faite de la définition d’une matrice 4-bornée. Pour deux matrices carrées réelles B = (b_{ij}) et B′ = (b′_{ij}) de même dimension, nous dirons que B′ a été obtenue de B par une mutation matricielle de B dans la direction de k si

b′_{ij} = \{ \begin{matrix}−b_{ij} & si i = k ou j = k \\ b_{ij} + \frac{|b_{ik}|b_{kj} + b_{ik}|b_{kj}|}{2} & sinon. \end{matrix}

Si une matrice peut être obtenue d’une autre par une suite de mutations matricielles et de permutations de lignes et simultanément des colonnes correspondantes, nous dirons qu’elles sont équivalentes par mutations. Une matrice carrée B = (b_{ij}) est anti-symétrique pour les signes si, pour n’importe quels i et j, soit b_{ij} = b_{ji} = 0, soit b_{ij}b_{ji} < 0. Enfin, une matrice carrée B sera dite 4-bornée si elle est entière et si toute matrice B′ = (b′_{ij}) équivalente par mutations à B est anti-symétrique pour les signes tout en respectant |b′_{ij}b′_{ji}| ≤ 4 pour tous les i et j.

Il nous est maintenant possible d’énoncer le théorème principal de cet article.

Théorème Toute matrice 4-bornée est anti-symétrisable.

Finalement, nous obtenons d’autres conditions nécessaires pour qu’une matrice antisymétrique pour les signes soit 4-bornée en considérant son diagramme. Le diagramme d’une matrice anti-symétrique pour les signes B = (b_{ij})_{i,j∈I} est le graphe ayant comme sommets les éléments de l’ensemble I et tel qu’il y a une arête dirigée de i vers j si et seulement si b_{ij} > 0, et on assigne à cette arête le poids |b_{ij}b_{ji}|. Premièrement, si le diagramme d’une matrice 4-bornée contient des cycles, alors ceux-ci doivent faire partie des cycles présentés à la Figure 2. Par ailleurs, aucun des diagrammes de la Figure 3 ne peut apparaître comme sous-diagramme du diagramme d’une matrice 4-bornée.

References

[1] S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002), 497-529.

[2] S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification, Inv. Math. 154 (2003), no 1. 63-121.

Mathieu St-Pierre Département de mathématiques, Université de Sherbrooke Sherbrooke, Qc, Canada, J1K 2R1 Adresse électronique: mathieu.h.st-pierre@usherbrooke.ca