9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Cluster algebras of finite type and positive symmetrizable matrices

CLUSTER ALGEBRAS OF FINITE TYPE AND POSITIVE SYMMETRIZABLE MATRICES

arXiv:math/0411341v5 [math.CO] 27 Sep 2005

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY Abstract. The paper is motivated by an analogy between cluster algebras and Kac-Moody algebras: both theories share the same classi?cation of ?nite type objects by familiar Cartan-Killing types. However the underlying combinatorics beyond the two classi?cations is di?erent: roughly speaking, Kac-Moody algebras are associated with (symmetrizable) Cartan matrices, while cluster algebras correspond to skew-symmetrizable matrices. We study an interplay between the two classes of matrices, in particular, establishing a new criterion for deciding whether a given skew-symmetrizable matrix gives rise to a cluster algebra of ?nite type.

1. Introduction This paper is motivated by the theory of cluster algebras initiated in [2]. Here we deal exclusively with the combinatorial aspects of the theory, so no knowledge of algebraic properties of cluster algebras (including their de?nition) will be assumed or needed. The reader should just bear in mind an analogy between cluster algebras and Kac-Moody algebras. In both theories, there is an appropriate notion of ?nite type. (For Kac-Moody algebras, “?nite type” just means being ?nite-dimensional, that is, a semisimple Lie algebra.) Cluster algebras of ?nite type were classi?ed in [3], and the resulting classi?cation turns out to be identical to the famous Cartan-Killing classi?cation of semisimple Lie algebras. However the underlying combinatorics beyond the two classes of algebras is di?erent: roughly speaking, Kac-Moody algebras correspond to (symmetrizable) Cartan matrices, while cluster algebras correspond to skew-symmetrizable matrices. In this paper, we study an interplay between the two classes of matrices. In particular, we establish a new criterion for deciding whether a given skew-symmetrizable matrix gives rise to a cluster algebra of ?nite type. To state our main results, we need some terminology. In what follows, by a matrix we always mean a square integer matrix. A matrix A (resp. B ) is symmetrizable (resp. skew-symmetrizable) if DA (resp. DB ) is symmetric (resp. skew-symmetric) for some diagonal matrix D with positive diagonal entries. Thus, in a symmetrizable (resp. skew-symmetrizable) matrix, the two transpose entries have the same sign (resp. opposite signs). We say that a symmetrizable matrix is a quasi-Cartan matrix if all its diagonal entries are equal to 2 (note that a skew-symmetrizable matrix has all diagonal entries equal to 0). We say that a quasi-Cartan matrix A is positive if the symmetrized matrix DA is positive de?nite; by the Sylvester criterion, this means that the principal minors of A are all positive. For a skew-symmetrizable

Date : December 13, 2004; revised June 27, 2005. 2000 Mathematics Subject Classi?cation. Primary: 05E15, Secondary: 05C50, 15A36, 17B67, Research supported by DGAPA grant IN101402-3 (C.G.) and NSF (DMS) grant 0200299 (A.Z.).

1

2

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

matrix B , we will refer to a quasi-Cartan matrix A with |Aij | = |Bij | for all i = j as a quasi-Cartan companion of B . A quasi-Cartan matrix is a (generalized) Cartan matrix if its o?-diagonal entries are non-positive. These are the matrices giving rise to Kac-Moody algebras, see [4]. As shown in [4], the Kac-Moody algebra associated to A is ?nite-dimensional if and only if A is positive. Thus, positive Cartan matrices form the combinatorial backbone of the Cartan-Killing classi?cation: every such matrix can be transformed by a simultaneous permutation of rows and columns to a block-diagonal matrix whose diagonal blocks are of the familiar types An , Bn , Cn , Dn , E6 , E7 , E8 , F4 , and G2 , represented by Dynkin diagrams. On the other hand, cluster algebras are associated with the mutation-equivalence classes of skew-symmetrizable matrices. Recall from [2] that, for each matrix index k , the mutation in direction k transforms a skew-symmetrizable matrix B into another skew-symmetrizable matrix B ′ = ?k (B ), whose entries are given by (1.1)

′ Bij =

?Bij Bij + sgn(Bik )[Bik Bkj ]+

if i = k or j = k ; otherwise,

where we use the notation [x]+ = max(x, 0) and sgn(x) = x/|x|, with the convention sgn(0) = 0 (the formula (1.1) is easily seen to be equivalent to [2, (4.3)]). One easily checks that ?k is involutive, implying that the repeated mutations in all directions give rise to the mutation-equivalence relation on skew-symmetrizable matrices. We are now ready to state the classi?cation result from [3]. Theorem 1.1. For a mutation-equivalence class S of skew-symmetrizable matrices, the following are equivalent. (1) The cluster algebra associated to S is of ?nite type. (2) S contains a matrix B such that the Cartan matrix A with o?-diagonal entries Aij = ?|Bij | is positive. (3) For every B ∈ S and all i = j , we have |Bij Bji | ≤ 3. Furthermore, the Cartan-Killing type of the Cartan matrix A in (2) is uniquely determined by S . In this paper we address the following Recognition Problem. Given a skew-symmetrizable matrix B , ?nd an e?cient way to determine whether the cluster algebra associated with (the mutation-equivalence class of) B is of ?nite type. The problem makes sense since the mutations are hard to control, so each of the conditions (2) and (3) in Theorem 1.1 is hard to check in general. A nice solution of the problem was obtained by A. Seven in [6]. His answer is given in terms of “forbidden minors” of B . Our answer is very di?erent and probably more practical: it is based on extending the criterion in (2) to every representative of a mutation class in question. To state it, we need a little bit more terminology. To a skew-symmetrizable n × n matrix B we associate a directed graph Γ(B ) with vertices 1, . . . , n and directed edges i → j for all i, j with Bij > 0. A chordless cycle in Γ(B ) is an induced subgraph isomorphic to a cycle (thus, the vertices of a

CLUSTER ALGEBRAS AND POSITIVE MATRICES

3

chordless cycle can be labeled by the elements of Z/pZ for some p ≥ 3 so that the edges between them are precisely {i, i + 1} for i ∈ Z/pZ). We are ?nally ready to state our main result. Theorem 1.2. The mutation-equivalence class of a skew-symmetrizable matrix B satis?es the equivalent conditions in Theorem 1.1 if and only if B satis?es: (4) Every chordless cycle in Γ(B ) is cyclically oriented, and B has a positive quasi-Cartan companion. Remark 1.3. We actually prove (2) ? (4) ? (3), which gives a new proof of the implication (2) ? (3), more elementary and straightforward than the one in [3]. Condition (4) in Theorem 1.2 is not completely explicit since B can have many quasi-Cartan companions. Note that a quasi-Cartan companion of B is speci?ed by choosing the signs of its o?-diagonal matrix entries, with the only requirement that sgn(Aij ) = sgn(Aji) for i = j . Thus, the number of choices for A is 2N , where N is the number of edges in Γ(B ). The following two propositions allow us to considerably sharpen Theorem 1.2. Proposition 1.4. To be positive, a quasi-Cartan companion A of a skew-symmetrizable matrix B must satisfy the following sign condition: for every chordless cycle Z in Γ(B ), the product {i,j }∈Z (?Aij ) over all edges of Z must be negative. Proposition 1.5. If every chordless cycle in Γ(B ) is cyclically oriented, then B has a quasi-Cartan companion (not necessarily positive) satisfying the sign condition in Proposition 1.4; furthermore, such a quasi-Cartan companion is unique up to simultaneous sign changes in rows and columns. Proposition 1.4 (resp. Proposition 1.5) is a consequence of Proposition 2.6 (resp. Corollary 5.2) below. In view of these results, in checking condition (4), it is enough to test positivity of just one quasi-Cartan companion of B since simultaneous sign changes in rows and columns do not a?ect positivity. The following example provides an illustration. Example 1.6. Let B (n) be the n×n skew-symmetric matrix with the above-diagonal entries given by ? ? ??1 if j ? i = 1; (1.2) Bij = 1 if j ? i = 2; ? ?0 if j ? i > 2.

The graph Γ(B (n)) has n ? 2 chordless cycles: they are formed by all triples of consecutive indices. An immediate check shows that all of them are cyclically oriented. Now let A(n) be the quasi-Cartan companion of B (n) such that Aij = Bij for j > i. An immediate check shows that A(n) satis?es the condition in Proposition 1.4. Let dn = det(A(n)), with the convention d0 = 1. It is not hard to show that the generating function of this sequence is given by (1.3)

n≥0

dn xn =

(1 + x)(1 + x + x2 )(1 + x2 )(1 + x3 ) , 1 ? x12

4

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

implying that dn+12 = dn for n ≥ 0. Since the numerator in (1.3) is a polynomial of degree 8, we see that d9 = d10 = d11 = 0. The values of dn for 1 ≤ n ≤ 8 are given by the following table:

n det(A(n))

1 2

2 3

3 4

4 4

5 4

6 3

7 2

8 1

Cartan-Killing type A1 A2 A3 D4 D5 E6 E7 E8 Table 1. Determinants and Cartan-Killing types of the A(n)

By the Sylvester criterion, A(n) is positive if and only if n ≤ 8. Applying Theorem 1.2 and Proposition 1.4, we conclude that the cluster algebra associated to B (n) is of ?nite type precisely when n ≤ 8. The corresponding Cartan-Killing types are given in the last line of Table 1 (their determination is left as an exercise to the reader). The paper is organized as follows. The proof of Theorem 1.2 is carried out in the next three sections. In Section 2, which can be viewed as a “symmetrizable analogue” of [3, Section 9], we establish some needed properties of positive quasiCartan matrices. In Section 3, we show that, under some conditions, the mutationequivalence of skew-symmetrizable matrices can be extended to a natural equivalence of properly chosen quasi-Cartan companions. The results of these two sections are put together in Section 4, where the proof of Theorem 1.2 is completed. The concluding Section 5 is purely graph-theoretic. We call a graph Γ cyclically orientable if it admits an orientation in which any chordless cycle is cyclically oriented. (For example, the full graph on four vertices is not cyclically orientable.) The main result of Section 5 is Theorem 5.1 which gives several properties of graphs that are equivalent to cyclical orientability. As a consequence, we obtain a graph-theoretic statement (Corollary 5.2) which implies Proposition 1.5. The paper concludes with Remark 5.7 discussing a possible strategy for checking condition (4). Remark 1.7. The preliminary version of Theorem 1.2 due to the ?rst two authors was stated in terms of integral quadratic forms rather than quasi-Cartan matrices. (Recall that the quadratic form represented by a symmetric matrix C with positive diagonal entries is called integral if 2Cij /Cii ∈ Z for all i, j ; in our present terminology, this means that C = DA is the symmetrized version of a quasi-Cartan matrix A.) The classi?cation of positive de?nite integral quadratic forms (up to natural equivalence) is well-known, and the answer is once again given by the Cartan-Killing classi?cation, cf. Proposition 2.9. Our results imply that this classi?cation is in agreement with the one given by Theorem 1.1: if A is a positive quasi-Cartan companion of B , then the Cartan-Killing type of the cluster algebra associated to B is the same as the Cartan-Killing type of the quadratic form represented by the symmetrized matrix DA.

CLUSTER ALGEBRAS AND POSITIVE MATRICES

5

2. Properties of positive quasi-Cartan matrices This section is a “symmetrizable analogue” of [3, Section 9]. We start with a simple observation. Lemma 2.1. Let A be a positive quasi-Cartan matrix. Then (a) 0 ≤ Aij Aji ≤ 3 for any i = j . (b) Aik Akj Aji ≥ 0 for any pairwise di?erent i, j, k . Proof. (a) is immediate from the positivity of the principal minor of A on the rows and columns i and j . (b) Let Aik Akj Aji = 0. Since A is symmetrizable, we have Aki Ajk Aij = Aik Akj Aji. The positivity condition for the principal 3 × 3 minor of A on the rows and columns i, j, k can now be rewritten as (2.1) implying our claim. Aik Akj Aji > Aij Aji + Aik Aki + Ajk Akj ? 4 ≥ ?1,

We now introduce the diagram of a quasi-Cartan matrix, which is a symmetrizable analogue of [3, De?nition 7.3]. De?nition 2.2. The diagram Γ(A) of a n×n quasi-Cartan matrix A is a (undirected) graph with vertices {1, 2, . . . , n} and edges {i, j } for each i = j with Aij = 0, where every edge {i, j } is assigned the weight Aij Aji and the sign εij = ? sgn(Aij ) = ? sgn(Aji ). In drawing the diagrams, all unspeci?ed weights will be assumed to be equal to 1. With some abuse of notation, we denote by the same symbol Γ(A) the underlying edge-weighted graph of the diagram, obtained by forgetting signs of the edges, and also the underlying graph obtained by forgetting both signs and edge weights. Note that an edge-weighted graph Γ which is of the form Γ(A) must satisfy the following condition (see [4, Exercise 2.1]) : (2.2) The product of edge weights along every cycle of Γ is a perfect square.

De?nition 2.3. An edge-weighted graph will be called positive if some sign assignment to the edges makes it into the diagram Γ(A) of some positive quasi-Cartan matrix A. The following proposition is an analogue of [3, Proposition 9.3]. Proposition 2.4. Positive edge-weighted trees are precisely Dynkin diagrams. Each of them becomes the diagram of a positive quasi-Cartan matrix under an arbitrary assignment of signs. Proof. Suppose Γ(A) is a tree. We can assume without loss of generality that the signs of all edges are equal to 1, i.e., A is a generalized Cartan matrix (this can be achieved by replacing A if necessary by a positive quasi-Cartan matrix of the form A′ = EAE , where E is a diagonal matrix with entries Eii = ±1). Our statement now follows from the Cartan-Killing classi?cation of positive generalized Cartan matrices, see, e.g., [4, Theorem 4.8] or Theorems 1 and 4 in [1, VI,4].

6

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

In analogy with [3, De?nition 9.1], by a subdiagram of Γ(A) we mean a diagram of the form Γ(A′ ), where A′ is a principal submatrix of A. Thus, Γ(A′ ) is obtained from Γ(A) by taking an induced subgraph on a subset of vertices and keeping all the edge weights and signs the same as in Γ(A). Since the positivity of A implies that of A′ , we obtain the following corollary. Corollary 2.5. None of the following edge-weighted graphs can appear as subdiagrams of the diagram of a positive quasi-Cartan matrix: C2 : B3 :

r 2 r 2 r r t tr r 2 r

Cn (n > 2) : D4 :

r 2

r

r

r

r 2

r

r r d ? r? d ?d r ? dr

G2 :

r 3 ra ≥ 1 r

Our next result is an analogue of [3, Proposition 9.7]. Proposition 2.6. Positive edge-weighted cycles are precisely those of the following three types: (a)

r ppp r r d dr r ? ? r

(b)

r 2 t 2 t tr r

(c)

r r

2

r d dr

r r

2

Furthermore, a sign assignment makes each of these cycles the diagram of a positive quasi-Cartan matrix if and only if the product of signs along all the edges is equal to ?1. Proof. First suppose that A is a positive quasi-Cartan matrix whose diagram is a cycle not of type (a). Then at least one edge of Γ(A) has weight a > 1. By Lemma 2.1(a), the weight a is either 2 or 3. It follows from (2.2) that at least two edges of Γ(A) have weight a. If a = 3 then the cycle must be a triangle since otherwise it would have a subdiagram G2 , a contradiction to Corollary 2.5. We are left with the case of a 3 × 3 matrix A such that A12 A21 = A23 A32 = 3, and A13 A31 = 1. In view of (2.1), such a matrix A cannot be positive. So, we can assume that all the edge weights are equal to 1 or 2, with at least two edges of weight 2. Then Γ(A) must be of one of the types (b) or (c), since otherwise it would have a subdiagram Cn for some n ≥ 2, again in contradiction to Corollary 2.5. To ?nish the proof, it remains to show that, in each of the cases (a), (b) and (c), the positivity of a quasi-Cartan matrix A is equivalent to the condition that the product of signs along all the edges is equal to ?1. Since in each case, all the proper subdiagrams of Γ(A) are Dynkin diagrams, we only need to show that the above sign condition is equivalent to det(A) > 0. Using simultaneous permutations and

CLUSTER ALGEBRAS AND POSITIVE MATRICES

7

changes of signs of rows and columns, we can assume that Aij < 0 for |j ? i| = 1; and we need to show that det(A) > 0 precisely when A1n and An1 are positive. Dealing with case (a) ?rst, let An (x) be the n × n quasi-Cartan matrix with nonzero o?-diagonal entries Aij = ?1 for |j ? i| = 1, and A1n = An1 = x. By a standard calculation, det(An (x)) = n + 1 + 2x ? x2 (n ? 1); therefore, det(An (1)) = 4, and det(An (?1)) = 0, as required. The cases (b) and (c) are similar (and simpler). Remark 2.7. The sign condition in Proposition 2.6 implies Proposition 1.4. De?nition 2.8. We say that quasi-Cartan matrices A and A′ are equivalent and write A′ ? A if A and A′ have the same symmetrizer D (that is, D is a diagonal matrix with positive diagonal entries such that C = DA and C ′ = DA′ are symmetric), and the symmetrized matrices satisfy C ′ = E T CE for some integer matrix E with determinant ±1. Note that this de?nition does not depend on the choice of a symmetrizer D . We conclude this section by showing that the equivalence classes of positive quasiCartan matrices are classi?ed by Cartan-Killing types. Although this result is wellknown to experts, we were unable to ?nd an adequate reference, so will outline the proofs. Let A be a n × n quasi-Cartan matrix. For each i = 1, . . . , n, de?ne an automorphism si of the lattice Zn by setting si (ej ) = ej ? Aij ei , where {e1 , . . . , en } is the standard basis in Zn . Let W (A) ? GLn (Z) be the group generated by s1 , . . . , sn . Proposition 2.9. The following conditions on a quasi-Cartan matrix A are equivalent: (1) A is positive. (2) The group W (A) is ?nite. (3) There exist a (reduced) root system Φ and a linearly independent subset {β1 , . . . , βn } ? Φ such that Aij = βi∨, βj , where β ∨ is the coroot dual to a root β . (4) A is equivalent to a positive Cartan matrix A0 . Under these conditions, if Φ0 ? Φ is the smallest root subsystem of Φ that contains the set {β1 , . . . , βn } in (3), then the Cartan-Killing type of Φ0 is the same as the Cartan-Killing type of the matrix A0 in (4), and it characterizes A up to equivalence. Furthermore, W (A) is naturally identi?ed with the Weyl group of Φ0 . Proof. The implication (4) =? (1) is trivial. To prove (1) =? (2), suppose that A is positive, and let (α| β ) be the positive de?nite (symmetric) scalar product in Zn given by (ei | ej ) = Cij , where C = (Cij ) = DA is the positive de?nite symmetric matrix corresponding to A. The standard check shows that, with respect to this scalar product, si is the orthogonal re?ection in the orthogonal complement to ei . Thus W is a discrete subgroup of the compact orthogonal group On (R), and so is ?nite, as claimed. The implication (2) =? (3) follows from a well-known classi?cation of ?nite crystallographic re?ection groups given in [1]: namely, every such group is the Weyl group

8

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

of a reduced root system Φ. To be more speci?c, take Φ = W (A) {e1 , . . . , en } ? Zn . If W (A) is ?nite then so is Φ; the fact that Φ satis?es the rest of the axioms of the root systems in [1] is checked easily. Then (3) holds with βi = ei . It remains to prove (3) =? (4). Without loss of generality, we can assume that Φ is the smallest root system containing {β1 , . . . , βn }, that is, Φ = W {β1 , . . . , βn }, where W = W (A) is the group generated by the re?ections corresponding to the roots β1 , . . . , βn . By this assumption, Φ has rank n, and {β1 , . . . , βn } is a Z-basis of the root lattice of Φ. Let (α| β ) be a W -invariant positive de?nite scalar product in the root lattice. By the de?nition, Aij = 2(βi | βj )/(βi | βi ). Thus, the symmetric matrix C = DA corresponding to A has entries Cij = (βi | βj ), with the diagonal entries of D given by Dii = (βi | βi )/2. Let {α1 , . . . , αn } be a system of simple roots in Φ, and A0 the corresponding ∨ 0 (positive) Cartan matrix, so that A0 ij = αi , αj . Thus, the symmetric matrix C = 0 0 0 0 D A corresponding to A has entries Cij = (αi | αj ), with the diagonal entries of D 0 0 given by Dii = (αi | αi )/2. It follows that C = E T C 0 E , where E is the transition matrix from the basis {α1 , . . . αn } to the basis {β1 , . . . , βn } (since both families are Z-bases of the root lattice, the matrix E is invertible over the integers). To ?nish the proof it remains to show that the simple roots α1 , . . . , αn can be chosen in such a way that D 0 = D . In other words, we need to show the following: (2.3) One can reorder the roots β1 , . . . , βn so that (βi | βi ) = (αi | αi ) for all i.

We can assume without loss of generality that the root system Φ is irreducible. If Φ is simply-laced, i.e., all roots are of the same length, (2.3) becomes tautological. So it is enough to check (2.3) for Φ of one of the types Bn , Cn , F4 and G2 . In each case, there are two di?erent root lengths (“long” and “short”). Our assumption that Φ is the smallest root system containing {β1 , . . . , βn } implies that among the roots βi there is a long one and a short one. This ?nishes the story for G2 . Now let Φ be of type Bn , with the standard choice of simple roots {α1 , . . . , αn } = {e1 ? e2 , . . . , en?1 ? en , en }, where e1 , . . . , en is the standard basis in the root lattice Zn . The long (resp. short) roots form a subsystem of type Dn (resp. An 1 ) consisting of the roots ±ei ± ej (1 ≤ i < j ≤ n) (resp. ±ei (1 ≤ i ≤ n)). To prove (2.3), we observe the following: every subset of Φ containing at most n ? 2 long roots, is contained in a root subsystem of type Bk × Bn?k for some k = 1, . . . , n ? 1 (to see this, represent each long root ±ei ± ej by an edge joining i and j , and use the obvious fact that every graph with n vertices and at most n ? 2 edges is disconnected). Therefore, the set {β1 , . . . , βn } must consist of n ? 1 long roots and a short one, proving (2.3). The type Cn is treated in the same way (with long and short roots interchanged). Finally, let Φ be of type F4 , with the simple roots {α1 , . . . , α4 } = {e2 ? e3 , e3 ? 1 e4 , e4 , 2 (e1 ? e2 ? e3 ? e4 )} (see [1]). In view of the symmetry between the long and short roots, to prove (2.3) it su?ces to show that {β1 , . . . , β4 } cannot consist of one long root and three short ones. Suppose on the contrary that, say β1 = ±e1 ± e2 , 1 and each of the roots β2 , β3 and β4 is of the form ±ei or 2 (±e1 ± e2 ± e3 ± e4 ). An easy inspection shows that W {β1 , . . . , β4 } is then contained in the root subsystem of Φ consisting of all short roots and the eight long roots {±e1 ± e2 , ±e3 ± e4 }, again

CLUSTER ALGEBRAS AND POSITIVE MATRICES

9

in contradiction with our assumption that Φ is the smallest root system containing {β1 , . . . , β4 }. This concludes the proof of (2.3) and hence of the equivalence of conditions (1) ? (4). It is well known that positive Cartan matrices of di?erent types are not equivalent to each other. The rest of the statements in Proposition 2.9 have been already established in the course of the above argument. Remark 2.10. In the case where a quasi-Cartan matrix is assumed to be symmetric, a proof of Proposition 2.9 was essentially given in [5, 1.2] (using the language of unit quadratic forms). 3. Mutations and quasi-Cartan companions In this section, we show that, under some conditions, the mutation-equivalence of skew-symmetrizable matrices can be extended to an equivalence (in the sense of De?nition 2.8) of properly chosen quasi-Cartan companions. De?nition 3.1. For a matrix index k , we say that a quasi-Cartan companion A of a skew-symmetrizable matrix B is k -compatible with B if the signs of its entries satisfy (3.1) if Bik > 0 and Bkj > 0 for some i, j then sgn(Aik Akj Aji) = sgn(Bji).

Proposition 3.2. Let A be a k -compatible quasi-Cartan companion of a skew-symmetrizable matrix B . Then there exists a k -compatible quasi-Cartan companion A′ of B ′ = ?k (B ) such that A′ ? A. Explicitly, the signs of o?-diagonal matrix entries of A′ can be chosen as follows: (3.2) sgn(A′ij ) = sgn(A′ji ) = sgn(Bik ) sgn(Aik ) ′ sgn(Bij Bij ) sgn(Aij ) if i = k, j = k ; if i = k, j = k .

Proof. We ?x k and introduce the following three n × n matrices:

? J is the diagonal matrix with Jkk = ?1 and Jii = 1 for i = k . ? E is the matrix with all the entries outside the k -th column equal to 0, and the k -th column entries given by Eik = Aik 0 if Bik > 0; otherwise.

? F is the matrix with all the entries outside the k -th row equal to 0, and the k -th row entries given by Fkj = We now set (3.3) A′ = (J ? E )A(J ? F ) , Akj 0 if Bkj < 0; otherwise.

10

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

and claim that A′ satis?es all the required properties. First, a direct calculation shows that the entries of A′ = JAJ ? EAJ ? JAF + EAF are given by ? 2 if i = j = k ; ? ? ? ?sgn(B )A if i = k = j ; ik ik (3.4) A′ij = ? ? sgn(Bkj )Akj if i = k = j ; ? ? ? Aij ? sgn(Aik Akj )[Bik Bkj ]+ if i = k, j = k .

Comparing (3.3) with (1.1) and using (3.1), it is easy to see that A′ is a quasi-Cartan companion of B ′ , and that it satis?es (3.2). Furthermore, the claim that A′ is k compatible with B ′ is a direct consequence of (3.2). Finally, to show that A′ ? A, we note that D (J ? E ) = (D (J ? F ))T = (J ? F )T D. Therefore, C ′ = DA′ = D (J ? E )A(J ? F ) = (J ? F )T DA(J ? F ) = (J ? F )T C (J ? F ) ,

and we are done. Corollary 3.3. Suppose a skew-symmetrizable matrix B satis?es condition (4) in Theorem 1.2, and let A be a positive quasi-Cartan companion of B . Then ?k (B ) has a positive quasi-Cartan companion for any matrix index k . Proof. In view of Lemma 2.1 (b), A is k -compatible with B . By Proposition 3.2, the matrix ?k (B ) has a quasi-Cartan companion which is equivalent to A and so is positive. In the rest of this section, we use Proposition 3.2 to obtain more information on positive edge-weighted graphs, see De?nition 2.3. First a piece of notation. Let Γ be an edge-weighted graph, i = j two vertices of Γ, and t a positive integer. We denote by Γ[i, j ; t] the edge-weighted graph obtained from Γ by adjoining t new vertices i1 , . . . , it and t +1 new edges {i, i1 }, {i1 , i2 }, . . . , {it?1 , it }, {it , j }, all of weight one. Lemma 3.4 (Chain Contraction). If the graph Γ[i, j ; t] is positive then so is Γ[i, j ; 1]. As a preparation for the proof, we recall several facts from [3]. First recall from [3, De?nition 7.3] that every skew-symmetrizable matrix B has the diagram Γ(B ) which is a directed edge-weighted graph. As an edge-weighted graph, it is completely analogous to its symmetrizable counterpart in De?nition 2.2: the vertices correspond to matrix indices, with an edge {i, j } for each i = j with Bij = 0, supplied with the weight |Bij Bji |. Note that the edge weights satisfy (2.2). The only di?erence between the two kinds of diagrams is in the way of encoding the signs of matrix entries: while for a quasi-Cartan matrix A, an edge {i, j } in Γ(A) is assigned the sign εij = ? sgn(Aij ) = ? sgn(Aji ), in Γ(B ) we have an arrow i → j whenever Bij > 0 (and so Bji < 0). As before, in drawing the diagram Γ(B ), all unspeci?ed weights will be equal to 1. The next proposition reproduces [3, Proposition 8.1].

CLUSTER ALGEBRAS AND POSITIVE MATRICES

11

Proposition 3.5. For a skew-symmetrizable matrix B , the diagram Γ′ = Γ(?k (B )) is uniquely determined by the diagram Γ = Γ(B ) and a matrix index k . Speci?cally, Γ′ is obtained from Γ as follows: ? The orientations 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 √ √ √ (3.5) ± c ± c′ = ab , √ √ where the sign before c (resp., before c′ ) is “+” if i, j, k form an oriented cycle 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. k r t a t ?b

0 r t tr

c c′ Figure 1. Diagram mutation Proof of Lemma 3.4. It su?ces to show the following: (3.6) If t ≥ 2 then the positivity of Γ[i, j ; t] implies that of Γ[i, j ; t ? 1].

?k ←→

k r t b a)

r

t ? tr

Choose any skew-symmetrizable matrix B such that Γ(B ) = Γ[i, j ; t] (as edgeweighted graphs), and the edges {i, i1 }, {i1 , i2 }, . . . , {it?1 , it }, {it , j } are oriented as i → i1 → · · · → it → j . Since Γ[i, j ; t] is assumed to be positive, B has a positive quasi-Cartan companion A. Clearly, our choice of orientations implies that A is it -compatible with B . By Proposition 3.2, the diagram Γ′ = Γ(?it (B )) is positive (as an edge-weighted graph). By (3.5), Γ′ is obtained from Γ[i, j ; t] by adjoining the edge {it?1 , j }. Thus, Γ′ has Γ[i, j ; t ? 1] as an induced subgraph, and so Γ[i, j ; t ? 1] is positive. This concludes the proof of (3.6) and Lemma 3.4. We conclude this section with one more application of Lemma 3.4, which allows us to construct a family of non-positive edge-weighted graphs. Lemma 3.6. Let Γ be an edge-weighted graph obtained from a cycle Z with all edge weights 1 by adjoining a vertex k joined with an even number of vertices of Z with edges of weights not exceeding 2. Then Γ is non-positive, with the only exception, where k is joined with just two adjacent vertices of Z , both edges having weight 1. Proof. First assume that at least one edge through k has weight 2. In view of (2.2), then every edge through k must have weight 2. If two of these edges connect k with non-adjacent vertices of Z , then they form a subdiagram C2 , so Γ cannot be positive. This leaves us with the case where k is joined with just two adjacent vertices of Z , both edges having weight 2. Then the graph Γ is of the form ?[i, j ; t], where ? is a triangle with edge weights 2, 2 and 1, the edge {i, j } being of weight 1.

12

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

?:

k 2 i

2

? ? ? ?

j

?[i, j ; 1]:

k 2 i

2

? ? ? ?

j

?[i, j ; t]:

k 2

2

?=i1

i

? d ? d it ? ? d d

i1

j

pp

p

By Lemma 3.4, the non-positivity of Γ follows from that of a 4-vertex graph ?[i, j ; 1] obtained from ? by adjoining one more vertex ? = i1 and two edges {i, ?} and {j, ?}, both of weight 1, as shown in the picture above. Arguing as in the proof of Lemma 3.4, choose a skew-symmetrizable matrix B such that Γ(B ) = ?[i, j ; 1] (as edge-weighted graphs), and both triangles {i, j, k } and {i, j, ?} are cyclically oriented. Performing the mutation ?? destroys the edge {i, j }, and so transforms ?[i, j ; 1] into a 4-cycle with edge weights (in cyclical order) 2, 2, 1, 1. By Proposition 2.6, the latter cycle is non-positive, hence by Corollary 3.3, so are ?[i, j ; 1] and Γ. It remains to consider the case where all the 2p edges through k have weight 1. We start with the case p = 1, that is, k is joined with two non-adjacent vertices of Z . Then Γ has exactly three chordless cycles, with each edge belonging to exactly two of these cycles. This makes it impossible to attach the signs to edges to satisfy the sign condition in Proposition 2.6, so Γ cannot be positive. Next let p = 2, that is, k is joined with four vertices of Z . Applying Lemma 3.4 in the same way as above, we can assume that Z has no other vertices, so Γ is made up of four triangles. Orienting all the edges so that these triangles become all cyclically oriented, and performing the mutation ?k transforms Γ into the graph D4 . Thus, Γ is non-positive in this case as well. If p = 3, arguing as above we can assume that Γ is built from a 6-cycle Z with all its vertices joined with k . Orienting the edges of Γ so that these triangles become all cyclically oriented, and performing mutations at two opposite vertices of Z destroys four out of six edges through k , leaving us with the case p = 1 which we already dealt with. Finally, if p ≥ 4 then Γ contains a subdiagram D4 , and so is again non-positive by Corollary 2.5.

4. Proof of Theorem 1.2 The following result is the key ingredient of our proof of Theorem 1.2. Lemma 4.1. Mutations of skew-symmetrizable matrices preserve property (4) in Theorem 1.2. Proof of Theorem 1.2. To deduce Theorem 1.2 from Lemma 4.1, we show that the conditions (2) and (3) in Theorem 1.1 satisfy the implications (2) =? (4) =? (3). The implication (4) =? (3) is immediate from Lemma 4.1 and Lemma 2.1. As for (2) =? (4), it is again immediate from Lemma 4.1 once we observe that a matrix B in condition (2) of Theorem 1.1 satis?es (4) (by virtue of the CartanKilling classi?cation, the graph Γ(B ) is a Dynkin diagram, hence a tree, so there are no (chordless) cycles, and the corresponding condition in (4) is vacuous).

CLUSTER ALGEBRAS AND POSITIVE MATRICES

13

Turning to the proof of Lemma 4.1, we will deduce it from a sharper statement (Lemma 4.4 below). To state it, we need some more terminology. The following de?nition is motivated by Propositions 2.4 and 2.6, and Lemma 3.6. De?nition 4.2. An edge-weighted graph Γ will be called quasi-?nite if it satis?es the following conditions: ? any induced subgraph of Γ which is a tree, is a Dynkin diagram. ? any induced subgraph of Γ which is a chordless cycle, is of one of the types (a), (b), (c) in Proposition 2.6. ? none of the non-positive edge-weight graphs in Lemma 3.6 appears as an induced subgraph of Γ. We say that a skew-symmetrizable matrix B and its diagram Γ(B ) are quasi-?nite if so is the underlying edge-weighted graph. Remark 4.3. Any skew-symmetrizable matrix B which has a positive quasi-Cartan companion is quasi-?nite as follows from Propositions 2.4 and 2.6, and Lemma 3.6. We will say that a skew-symmetrizable matrix B (and its diagram Γ(B )) is cyclically oriented if every chordless cycle in Γ(B ) is cyclically oriented. We will deduce Lemma 4.1 from the following statement. Lemma 4.4. Suppose that two skew-symmetrizable matrices B and B ′ = ?k (B ) are both quasi-?nite. Then B is cyclically oriented if and only if so is B ′ . Assuming Lemma 4.4, we can prove Lemma 4.1 as follows. Proof of Lemma 4.1. Suppose that a skew-symmetrizable matrix B satis?es (4), and let A be a positive quasi-Cartan companion of B . We need to show that B ′ = ?k (B ) satis?es (4) for any k . Note that B is quasi-?nite by Remark 4.3 and cyclically oriented by the de?nition of (4). Note also that A is k -compatible with B : to check (3.1), combine the fact that B is cyclically oriented with Lemma 2.1 (b). Applying Proposition 3.2, we see that B ′ = ?k (B ) has a positive quasi-Cartan companion A′ and therefore B ′ is quasi-?nite, by Remark 4.3. By Lemma 4.4, B ′ is cyclically oriented, and so satis?es (4), as desired. To ?nish the proof of Theorem 1.2, it remains to prove Lemma 4.4. Using Proposition 3.5, in our proof of Lemma 4.4 we can forget about skew-symmetrizable matrices and just work with diagrams and their mutations given by the rules in Proposition 3.5. So in the following argument by a diagram we will just mean a directed edge-weighted graph Γ satisfying (2.2). Proof of Lemma 4.4. Let Γ be a diagram which is quasi-?nite but not cyclically oriented, and let Γ′ be obtained from Γ by mutation in some direction k (here we think of k as a vertex of Γ). We need to show that Γ′ is either not quasi-?nite, or not cyclically oriented. The proof will split into several cases. Case 1. k belongs to some chordless cycle in Γ which is not cyclically oriented. Without loss of generality we can assume that this cycle is the whole diagram Γ. Let {i, k } and {j, k } be the two edges through k in Γ. Case 1.1. The edges {i, k } and {j, k } are oriented both towards k or both away from k . Then Γ′ is obtained from Γ by just reversing the orientations of these edges, and so is not cyclically oriented.

14

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

Case 1.2. The edges {i, k } and {j, k } are oriented as i → k → j . Case 1.2.1. The cycle Γ has at least four vertices. Then in Γ′ we have j → k → i → j , and so, removing the vertex k from Γ′ leaves us with a cycle which is again not cyclically oriented. Case 1.2.2. The cycle Γ is a triangle with vertices i, j, k and weighted edges oriented as follows: k r t a t ?b i c j Applying (3.5), we see that the weight c′ of the edge {i, j } in Γ′ satis?es √ √ √ c′ = ( ab + c)2 = ab + 2 abc + c ≥ 4,

0E t tr r

so in this case Γ′ is not quasi-?nite. Case 2. k does not belong to any non-oriented chordless cycle in Γ. Since Γ is not cyclically oriented, it has at least one non-oriented chordless cycle Z . Without loss of generality we can assume that Γ is just the union of Z and {k }. In order for the mutation ?k to change Z , there must be at least two edges through k in Γ. Furthermore, if we list these edges in the cyclical order along Z , then the incoming and outgoing edges must alternate, in particular, there must be an even number of them; otherwise, k would belong to a non-oriented cycle. Since Γ is assumed to be quasi-?nite, the cycle Z is of one of the three types (a), (b), or (c) in Proposition 2.6. Case 2.1. Z is of type (b), i.e., it is a non-oriented triangle with edge weights 2, 2, and 1. Let k be joined with vertices i and j of Z , with orientations i → k → j . Since the triangle {i, j, k } in Γ must be oriented, the edge {i, j } is oriented as j → i. The mutation ?k reverses the orientations of the edges {i, k } and {j, k }, and changes the weight and orientation of the edge {i, j } in accordance with (3.5) (in particular, the latter edge can be absent in Γ′ ). An easy inspection shows that the only chance for Γ′ to be cyclically oriented, while Γ is not cyclically oriented, is to have the edge {i, j } to be of opposite orientations in Γ and Γ′ . By (3.5), this can only happen if {i, j } has weight 1 in Γ, while each of the remaining four edges has weight 2. But then Γ has a subdiagram of type C2 (see Corollary 2.5), so cannot be quasi-?nite. Case 2.2. Z is of type (c), i.e., it is a non-oriented 4-vertex cycle with edge weights (in cyclic order) 1, 2, 1, 2.

Case 2.2.1 2 r j k

r ? 2 ? ? d 2 d d

Case 2.2.2 2 j

d d d 2 d

r

Case 2.2.3 2

d ? 2? d d ? ? d 2d ? ? d

k

2

i

r

d d d

k

2

i

2

Figure 2. Di?erent cases to be considered Case 2.2.1. k is joined precisely with the two adjacent vertices i and j of Z . The same argument as in Case 2.1 shows that, the only chance to have Γ′ cyclically

CLUSTER ALGEBRAS AND POSITIVE MATRICES

15

oriented and Γ not cyclically oriented appears if {i, j } has weight 1 in Γ, while both {i, k } and {j, k } have weight 2. But then Γ has a subdiagram of type C2 , so cannot be quasi-?nite. Case 2.2.2. k is joined precisely with the two opposite vertices i and j of Z . This case is even easier than the previous one: in view of Proposition 2.6, to satisfy (2.2), the edges {i, k } and {j, k } must have weights 1 and 2, which again forces Γ to have a subdiagram of type C2 . Case 2.2.3. k is joined with all four vertices of Z . The only balance of edge weights that makes Γ quasi-?nite is the one shown in Figure 2. Furthermore, since we are still in Case 2, all four triangles containing k must be cyclically oriented. Performing the mutation ?k , we obtain a diagram, which contains a subdiagram B3 and so is not quasi-?nite. Case 2.3. Z is of type (a), i.e., has all edge weights equal to 1. According to Lemma 3.6, if Γ is quasi-?nite then k is joined with just two adjacent vertices i and j of Z , both edges {i, k } and {j, k } having weight 1. As before, the triangle {i, j, k } must be cyclically oriented. Applying the mutation ?k destroys the edge {i, j }, and so transforms Γ into a chordless cycle. If this cycle is cyclically oriented, then so is the original cycle Z , contradicting our assumption. This completes the proofs of Lemma 4.4 and Theorem 1.2.

5. Cyclically orientable graphs This section is purely graph-theoretic. We call a graph Γ cyclically orientable if it admits an orientation in which any chordless cycle is cyclically oriented. For example, the full graph on four vertices is not cyclically orientable. We will give several properties of graphs that are equivalent to cyclical orientability. This requires some notation. For a given graph Γ, we denote by Ver(Γ) its set of vertices, by Edg(Γ) its set of edges, by Con(Γ) its set of connected components, and by Cyc(Γ) its set of chordless cycles; if no confusion can arise, we drop the dependence of Γ. For a ?nite set X , let FX 2 denote the vector space of functions f : X → F2 with the values in the 2-element ?eld F2 . To any incidence relation I ? X × Y between ?nite sets X and Y we Y associate a linear map ρ = ρI : FX 2 → F2 given by (5.1) (ρf )(y ) =

(x,y )∈I

f (x) .

In particular, there is a natural sequence of linear maps: (5.2) 0 → FCon → FVer → FEdg → FCyc →0, 2 2 2 2

where all the maps are of the form (5.1) associated to the obvious incidence relations.

16

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

Theorem 5.1. Each of the following conditions on a ?nite graph Γ is equivalent to cyclical orientability: (5.3) (5.4) (5.5) The edges of Γ can be linearly ordered so that di?erent chordless cycles in Γ will have di?erent maximal edges. | Cyc | = | Edg | ? | Ver | + | Con | . The sequence (5.2) is exact.

Using (5.5), we obtain the following corollary implying Proposition 1.5. Corollary 5.2. In a cyclically orientable graph, one can attach the signs ±1 to all edges in such a way that the product of these signs along every chordless cycle is equal to ?1. Furthermore, such an attachment is unique up to simultaneous changes of signs for all edges incident to a given vertex. As a preparation for the proof of Theorem 5.1, we show that certain weaker versions of (5.3)-(5.5) hold for arbitrary ?nite graphs. Proposition 5.3. The following properties hold for an arbitrary ?nite graph Γ: (5.6) The edges of Γ can be linearly ordered so that an edge is maximal in some chordless cycle if and only if it is one of the last | Edg | ? | Ver | + | Con | edges on the list. | Cyc | ≥ | Edg | ? | Ver | + | Con | .

(5.7) (5.8)

is exact. → FCyc The sequence 0 → FCon → FVer → FEdg 2 2 2 2

Proof. To construct a linear ordering of edges satisfying (5.6), take the ?rst | Ver | ? | Con | edges (in an arbitrary order) so that they form a spanning forest in Γ (the union of spanning trees in all connected components). Then order the remaining | Edg | ? | Ver | + | Con | edges so that every new edge connects two vertices at the minimal possible distance in the graph formed by the preceding edges. By virtue of this construction, each of the last | Edg | ?| Ver | + | Con | edges becomes the maximal edge in at least one chordless cycle of Γ. The bound (5.7) follows at once from (5.6). Finally, the only statement in (5.8) which may be not immediately clear is the inclusion Ver → FEdg → FCyc Ker(FEdg 2 ) . 2 ) ? Im(F2 2 To prove this inclusion, ?rst consider the case where Γ is a forest. In this case, is surjective, which is well-known (and we need to show that the map FVer → FEdg 2 2 follows easily by induction on the number of edges). Returning to the general case, choose a linear ordering of the edges satisfying (5.6). It is clear that a function g ∈ Ker(FEdg → FCyc 2 2 ) is uniquely determined by its restriction to the ?rst | Ver | ? | Con | edges. Since these edges form a forest, there is a function f ∈ FVer whose image in 2 FEdg agrees with g on them; therefore, the image of f is g , as desired. 2 Proof of Theorem 5.1, (5.3)?? (5.4)?? (5.5). The implication (5.5) =? (5.4) is clear, while (5.4) =? (5.3) is immediate from (5.6). Finally, to show (5.3) =? (5.5), we note that, in view of (5.8), the exactness of the sequence (5.2) simply means that

CLUSTER ALGEBRAS AND POSITIVE MATRICES

17

its right-most map FEdg → FCyc is surjective. The latter condition follows easily 2 2 from (5.3), and we are done. To complete the proof of Theorem 5.1, we will show that the cyclical orientability of Γ is equivalent to (5.3). First some preparation. Let i and j be two non-adjacent vertices of a ?nite graph Γ′ , and let Γ be obtained from Γ′ by adjoining the edge {i, j }. By a chain connecting i and j in Γ′ we will mean a sequence of t ≥ 3 distinct vertices (i = i1 , i2 , . . . , it = j ) such that the only edges between them are {ip , ip+1 } for p = 1, . . . , t ? 1. It is then clear that the chordless cycles in Γ containing the edge {i, j } are in a bijection with the chains connecting i and j in Γ′ . In particular, i and j belong to a unique chordless cycle in Γ if and only if they are connected by a unique chain in Γ′ . Lemma 5.4. Suppose Γ′ is a cyclically orientable graph, and i and j are two nonadjacent vertices of Γ′ connected by a unique chain (i = i1 , i2 , . . . , it = j ). Then there exists an orientation of Γ′ making all chordless cycles cyclically oriented and having the chain (i1 , i2 , . . . , it ) linearly oriented: i1 → i2 → · · · → it . Proof. Let Γ′′ be the induced subgraph of Γ′ on the set of vertices Ver(Γ′ ) ? {i1 , . . . , it }. For p = 1, . . . , t ? 1, let Γp denote the union of all connected components of Γ′′ joined by an edge with ip and ip+1 . We claim that the subgraphs Γ1 , . . . , Γt?1 are pairwise disjoint, and so are disconnected from each other in Γ′′ . Indeed, if Γp ∩ Γq = ? for some p < q then ip and iq+1 would be connected by a chain having all interior vertices in Γ′′ ; but this contradicts the uniqueness of a chain connecting i and j . Clearly, if an edge {ip , ip+1 } belongs to some chordless cycle Z in Γ′ , then the rest of the vertices of Z belong to Γp .

Γ2 v Γ1 v v ¨ v r ¨ r ¨¨ rrv ¨¨ rrv

i1 i2 ′ i3

Now take any orientation of Γ making all the chordless cycles cyclically oriented. If all the edges {ip , ip+1 } are oriented as ip → ip+1 , there is nothing to prove. Otherwise, modify the orientation as follows: reverse every directed edge ip+1 → ip together with all the edges inside Γp and all the edges connecting ip and ip+1 with Γp . Clearly, the new orientation still has all the chordless cycles in Γ′ cyclically oriented, so we are done. Proof of Theorem 5.1, (5.3)=? cyclical orientability. Thus, we assume that Γ is a ?nite graph whose edges are ordered in accordance to (5.3). To show that Γ is cyclically orientable, we proceed by induction on the number of edges N of Γ. If N = 0, there is nothing to prove; so we assume that Γ has at least one edge. Let e = {i, j } be the maximal edge in the chosen ordering, and let Γ′ be the graph obtained from Γ by removing e. Since e belongs to at most one chordless cycle in Γ, it is easy to see that the chordless cycles in Γ′ are precisely the chordless cycles in Γ that do not contain e. It follows that Γ′ satis?es (5.3). By induction, we can assume that Γ′ is cyclically orientable. Choose an orientation of Γ′ making all the chordless cycles cyclically oriented. If Γ has no chordless cycle containing e then i and j belong to di?erent connected components of Γ′ , and so e can be oriented either way, making

qqq

Γt?1 v ¨ v r ¨¨ rrv

it?1 it

18

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

all chordless cycles in Γ cyclically oriented. This leaves us with the case where Γ has a unique chordless cycle containing e. Then i and j are connected by a unique chain in Γ′ . By Lemma 5.4, we can assume that this chain is linearly oriented in a chosen orientation of Γ′ . Therefore, orienting e so that the only chordless cycle containing e becomes cyclically oriented, yields an orientation of Γ making all chordless cycles cyclically oriented, thus showing that Γ is cyclically orientable. It remains to show that a cyclically orientable graph satis?es (5.3). Again we need some preparation. We start with two lemmas. Lemma 5.5. Let Γ be a cyclically orientable graph, and suppose two chordless cycles Z and Z ′ share a common edge {i, j }. Then i and j are the only common vertices of Z and Z ′ , and {i, j } is the only edge joining a vertex of Z with a vertex of Z ′ . Proof. Let i, j, i1 , . . . , ip (resp. i, j, i′1 , . . . , i′q ) be all the vertices of Z (resp. Z ′ ) written in the cyclical order. Without loss of generality, we can assume that i1 = i′1 (this can be always achieved by replacing {i, j } with another edge if necessary). To show that i and j are the only common vertices of Z and Z ′ , we suppose that ik = i′? for some k and ?, and choose the smallest possible k with this property. Thus, the sequence of vertices j, i1 , . . . , ik , i′??1 , . . . , i′1 , j forms a cycle of length k + ?. Now choose r ∈ {1, . . . , k } and s ∈ {1, . . . , ? ? 1} so that ir and i′s are joined by an edge, and r + s is smallest possible with this property. Then the vertices j, i1 , . . . , ir , i′s , i′s?1 , . . . , i′1 form a chordless cycle, say Z ′′ . To obtain the desired contradiction, it remains to observe that no orientation of edges of Γ can make all three chordless cycles Z, Z ′, and Z ′′ cyclically oriented: indeed, if say j is a head of {i, j } then j must be a tail of both {j, i1 } and {j, i′1 }, and so Z ′′ will not be cyclically oriented. Having proven that the vertices i1 , . . . , ik , i′1 , . . . , i′? are all distinct, the same argument as above shows that there are no edges of the form {ir , i′s }, and we are done. Lemma 5.6. Suppose that in a cyclically orientable graph Γ, there is at least one edge through a vertex j . Then there is an edge through j that belongs to at most one chordless cycle. Proof. Fix an orientation of Γ making all chordless cycles cyclically oriented. Arguing by contradiction, suppose that every edge through j belongs to at least two chordless cycles. Start with an arbitrary edge {j, i1 }, let Z1 be a chordless cycle containing this edge, and let {j, i2 } be the second edge through j that belongs to Z1 . Then pick a chordless cycle Z2 = Z1 that contains the edge {j, i2 }, and let {j, i3 } be the second edge through j that belongs to Z2 . Continuing in the same way, we construct a sequence of chordless cycles Z1 , Z2 , . . . and a sequence of vertices i1 , i2 , . . . such that each Zk contains edges {j, ik } and {j, ik+1 }. Renaming the vertices if necessary, we can assume without loss of generality that the vertices i1 , . . . , ip and the chordless cycles Z1 , . . . , Zp are pairwise distinct, but ip+1 = i1 and Zp+1 = Z1 . In view of Lemma 5.5, we have p ≥ 3. Also since all the chordless cycles Z1 , . . . , Zp must be cyclically oriented, p is even, and so p ≥ 4.

CLUSTER ALGEBRAS AND POSITIVE MATRICES

19

i3 ip ppppppp ? s d d s ? dr ? r? d ? T ? d ?

d ? c r r ? d ? d d ? ? ? ? d

j

i1

d s d r'

? ? r?

i2

Now let i1 , . . . , i2 , . . . , i3 , . . . , ip , . . . , i1 be the sequence of vertices in Z1 ∪ · · · ∪ Zp ? {j } written in the natural cyclical order, so that each interval ik , . . . , ik+1 is a chain Zk ? {j }. Choose a shortest possible interval (in the cyclical order) j1 , . . . , jq in this sequence consisting of q ≥ 3 pairwise distinct vertices and such that {j1 , jq } is also an edge. (It is easy to see that such intervals exist because every three consecutive vertices in our sequence are distinct.) The vertices j1 , . . . , jq obviously form a chordless cycle. Clearly, this chordless cycle is not a part of any Zk ? {j }. Thus, it must contain some ik as an interior vertex. But this contradicts the cyclical orientability since the two edges through ik belong to the chordless cycles Zk and Zk?1 (with the convention that Z0 = Zp ) and so either both are oriented towards ik , or both are oriented away from ik . This contradiction proves the result. Proof of Theorem 5.1, cyclical orientability =? (5.3). Let Γ be a cyclically orientable graph having at least one edge. By Lemma 5.6, Γ has an edge e belonging to at most one chordless cycle. Let Γ′ be obtained from Γ by removing the edge e. While proving the reverse implication, we have already noticed that the chordless cycles in Γ′ are precisely the chordless cycles in Γ that do not contain e. It follows that an orientation of Γ making all chordless cycles cyclically oriented, restricts to the orientation of Γ′ with the same property. Thus, Γ′ is cyclically orientable. By induction on the number of edges, there is a linear ordering of the edges of Γ′ satisfying (5.3). Adding e as the maximal element gives a desired linear ordering of edges for Γ, ?nishing the proof of Theorem 5.1.

Remark 5.7. Theorem 5.1 suggests the following way to check whether a given skew-symmetrizable matrix satis?es condition (4) in Theorem 1.2. Start by checking whether the edges of (the underlying graph of) the diagram Γ(B ) can be ordered in accordance with (5.3) (we leave aside the question of a practical implementation of such a check). If (5.3) cannot be satis?ed, then B is not of ?nite type. Otherwise, go over the list of edges ordered in accordance with (5.3), and attach the signs to them in the following way. If a current edge {i, j } is not maximal in any chordless cycle, choose the sign εij arbitrarily; otherwise, {i, j } is maximal in a unique chordless cycle Z , and we determine εij from the condition that the product of signs along the edges of Z is equal to ?1. Finally, de?ne a quasi-Cartan companion A of B by setting Aij = ?εij |Bij | for all i = j . Then B satis?es (4) and so is of ?nite type if and only if A is positive (the latter condition can be checked for example by using the Sylvester criterion).

20

MICHAEL BAROT, CHRISTOF GEISS, AND ANDREI ZELEVINSKY

Acknowledgments The ?rst solution of the recognition problem for cluster algebras of ?nite type was given by A. Seven in [6] as a part of his Ph.D. thesis written under the supervision of A. Zelevinsky at Northeastern University. M. Barot and C. Geiss started working on an alternative solution after attending A. Seven’s talk at the Sixth International Joint AMS-SMM Meeting in May 2004. They joined forces with A. Zelevinsky after he attended their presentation of a preliminary version of Theorem 1.2 at the XI International Conference on Representations of Algebras, Mexico, August 2004. The authors thank Alex Postnikov for stimulating discussions and help in proving the results in Section 5. References

[1] N. Bourbaki, Groupes and alg` ebres de Lie, Ch. 4,5 et 6. Hermann, Paris 1968. [2] S. Fomin, A. Zelevinsky, Cluster algebras I: Foundations. J. Amer. Math. Soc. 15 (2002), no. 2, 497-529. [3] S. Fomin, A. Zelevinsky, Cluster algebras II: Finite type classi?cation. Invent. Math. 154 (2003), no 1. 63-121. [4] V. Kac, In?nite dimensional Lie algebras, 3rd edition, Cambridge University Press, 1990. [5] C. M. Ringel, Tame algebras and integral quadratic forms, Lecture Notes in Mathematics, 1099, Springer-Verlag, Berlin, 1984. [6] A. Seven, Recognizing cluster algebras of ?nite type, math.CO/0406545. ?ticas, UNAM, Ciudad Universitaria, 04510 Mexico D.F., MexInstituto de Matema ico E-mail address : barot@matem.unam.mx ?ticas, UNAM, Ciudad Universitaria, 04510 Mexico D.F., MexInstituto de Matema ico E-mail address : christof@matem.unam.mx Department of Mathematics, Northeastern University, Boston, MA 02115, USA E-mail address : andrei@neu.edu

赞助商链接

- 电脑配件申请单
- Cluster Algebras and Semipositive Symmetrizable Matrices
- Diamonds of finite type in thin Lie algebras
- Nottingham Lie algebras with diamonds of finite type
- A graph theoretic expansion formula for cluster algebras of classical type
- Cluster Algebras and Semipositive Symmetrizable Matrices
- Recognizing Cluster Algebras of Finite type
- Cluster-tilted algebras of finite representation type
- Information Geometry of Positive Matrices and Isospectral Flow
- Bounded Ratios of Products of Principal Minors of Positive Definite Matrices
- Cluster algebras II Finite type classification
- Tame concealed algebras and cluster quivers of minimal infinite type
- An Analysis of Completely-Positive Trace-Preserving Maps on 2x2 Matrices
- Positivity and canonical bases in rank 2 cluster algebras of finite and affine types
- Action of a finite quantum group on the algebra of complex NxN matrices

更多相关文章：
更多相关标签：