Jeremie Guilhot

Cédric Lecouvey

Pierre Tarrago

Pierre Tarrago Basics

J Ér

Émie Guilhot

BASICS ON POSITIVELY MULTIPLICATIVE GRAPHS AND ALGEBRAS

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This paper is devoted to positively multiplicative algebras and positively multiplicative graphs which permit to give a unified background to many problems at the interaction between algebra, combinatorics and probability. Given a finite set Z of indeterminates and a field k containing R, a positively multiplicative algebra is a unital k[Z ±1 ]-algebra A admitting a basis B such that 1 ∈ B and with structure constants in k + [Z ±1 ], the subset of k[Z ±1 ] of Laurent polynomials with nonnegative real coefficients. This class of algebras contains in particular the fusion algebras, the group algebras or the character algebras associated to finite groups, the character algebras of simple Lie algebras but also homology or cohomology rings defined from algebraic varieties related in particular to Schubert calculus or to the geometry of affine Grassmannians.

Due to the positivity of the constant structures in A, the matrix of the multiplication by any positive linear combination s of elements in B expressed in the basis B can be regarded as an adjacency matrix for a weighted graph with set of vertices labelled by B. Conversely, starting from a graph Γ weighted by elements in k + [Z ±1 ], it is a natural question to look for an underlying positively multiplicative algebra structure. We will say that Γ is positively multiplicative at a vertex v i 0 when its adjacency matrix A can be embedded in a matrix algebra which is positively multiplicative with a basis B indexed by the vertices of Γ in such a way that b v i 0 = 1 and the matrix of the multiplication by A expressed in the basis B is the matrix A itself. One may observe here that we have two types of constraints for a graph to be positively multiplicative which are of very different nature.

(1) The first one relates to linear algebra: does there exist a matrix algebra A with a basis B in which b v i 0 = 1 and the matrix of the multiplication by A is A? If so, we will say that Γ is multiplicative at v i 0 . (2) The second one is of geometric nature: does there exists an algebra as in [START_REF] Beauville | Conformal blocks, Fusion rings and the Verlinde formula[END_REF] whose cone C(B) of nonnegative linear combinations of elements in B is stable by multiplication? We shall see that answer to question (1) is positive when the graph Γ has maximal dimension, that is when the algebra K[A] has dimension card(Γ) (here K is the fraction field of k[Z ±1 ]). In this case, the algebra A and its basis B are indeed unique when they exist and can be computed by elementary linear algebra techniques. In contrast, it is highly non trivial to find general conditions sufficient to guarantee a positive answer to question [START_REF] Bertram | Quantum multiplication of Schur polynomials[END_REF]. Moreover, even when a graph Γ is positively multiplicative, it is often very difficult to get a combinatorial description of the structure constants of the basis B, for example by counting paths in Γ. This problem is reminiscent of the description of tensor product multiplicities in representation theory, the determination of combinatorial fusion rules or that of the constant structures in the affine Grassmannians homology rings. For tensor product multiplicities of Kac-Moody algebras, an elegant description exists in terms of the Littelmann path model [START_REF] Littelmann | A Littlewood-Richardson type rule for symmetrizable Kac-Moody algebras[END_REF] or the combinatorics of crystal graphs [START_REF] Kashiwara | On crystal bases[END_REF]. For the symmetric groups, these multiplicities (Kronecker coefficients) are much less understood. The determination of combinatorial descriptions for the fusions rule in conformal field theory [START_REF] Beauville | Conformal blocks, Fusion rings and the Verlinde formula[END_REF] or the constant structures in affine Grassmannians homology rings [START_REF] Lam | k-Schur functions and affine Schubert calculus[END_REF] is yet an unsolved problem.

The goal of the paper is first to propose a unified approach in the study of positively multiplicative graphs independent of the algebraic or geometric context where they appear naturally. The results, presented in an expository style, gather basics on these notions that we will need in future works and for which we did not find explicit references in the literature. Although they use quite elementary tools, we believe that they deserved to be written down. We will explain in particular how to decide whether a graph is multiplicative and then provide simple procedures to compute the related basis. When a graph Γ is positively multiplicative at v i 0 we will also give a general construction (called expansion) yielding an infinite graded rooted graph Γ e defined from Γ for which it is easy to get a complete description of the extremal positive harmonic functions. These functions are essential tools in the study of random walks on graphs or alcoves tilings (see for example [START_REF] Kerov | Asymptotic representation theory of the symmetric group and its applications in analysis[END_REF] and [START_REF] Lecouvey | Alcove random walks, k-Schur functions and the minimal boundary of the k-bounded partition poset[END_REF]). Our second objective is to establish basics results on positively multiplicative algebras and graphs that we will need in [START_REF] Guilhot | Homology rings of affine grassmannians and multiplicative graphs[END_REF] and [START_REF] Guilhot | [END_REF] to study respectively random walks on alcoves tilings and convergences of random particle systems disposed on a circle.

In each of the sections, we have chosen to present numerous examples of the notions we introduced. We hope they will be sufficiently helpful for the reader. The paper itself is organized as follows. Section 2 is devoted to the notion of positively multiplicative algebras and its connection with fusion algebras. We also explain how to construct a symmetric version of such an algebra A starting from any finite-order automorphism of A regarded as a A-module (for example an involutive automorphism of algebra). In Section 3, we define and study multiplicative graphs Γ. We introduce the notion of roots, that is the vertices whose corresponding elements in the multiplicative basis B are invertible. When Γ has maximal dimension, we give a simple procedure to check whether a graph is multiplicative at v i 0 and then to compute its associated basis B. The positively multiplicative graphs are presented in Section 4 where we also study how they behave under conjugation by generalized permutations (i.e. permutation matrices in which the coefficients 1 can be replaced by monomials in k + [Z ±1 ]). When A is commutative, we show in particular that the subset of vertices labelling elements of B which are generalized permutations has the structure of an abelian group. When B itself contains only generalized permutations, it follows that the graph Γ coincides, up to normalization of the weights on its arrows, with the Cayley graph of an abelian group. In Section 5, we detail the expansion procedure evoked previously and explain how to get a parametrization of the minimal boundary (i.e. of the extremal positive harmonic functions) on each extended graph coming from a positively multiplicative graph. Finally, in Section 6 we present two important examples of positively multiplicative graphs whose definition is elementary but with structure constants of high combinatorial complexity. Their generalizations and their study will be our main objective in [START_REF] Guilhot | Homology rings of affine grassmannians and multiplicative graphs[END_REF].

Acknowledgments: The three authors are supported by the Agence Nationale de la Recherche funding ANR CORTIPOM 21-CE40-001. The first author is supported by the Agence Nationale de la Recherche funding ANR JCJC Project ANR-18-CE40-0001 and by the Australian Research Council discovery DP200100712.

Positively multiplicative algebras

In this section, we introduce the notion of positively multiplicative algebra which lies at the heart of the paper. In the following, k is a subfield of C and A a unital algebra over the Laurent polynomial ring k[Z ±1 ] where Z = {z ±1 k | k ∈ X} is a set (possibly empty) of formal indeterminates. Write k + [Z ±1 ] for the subset of k[Z ±1 ] containing the polynomials with nonnegative (real) coefficients. Also let K be the fraction field of k[Z ±1 ].

2.1. Positively multiplicative bases. Definition 2.1. The algebra A is said positively multiplicative (PM for short) when it admits a k[Z ±1 ]-basis B = {b i , i ∈ I} satisfying the following conditions:

(1) 1 ∈ B, (2) for any i, j

∈ I b i b j = k∈I c k i,j b k with c k i,j ∈ k + [Z ±1 ].
It is said strongly positively multiplicative (SPM for short) when it is positively multiplicative and for any (j, k) ∈ I 2 there exists at least an index i in I such that c k i,j = 0. Example 2.2.

(1) For any integer n, the algebra k n is positively multiplicative with PM-basis B = {b i | i = 0, . . . , n -1} where b 0 = (1, . . . , 1) and for i = 1, . . . , n -1, b i = e i where e i is the i-th element of the canonical basis of k n . It is easy to construct other PM-basis for k n : in general a PM basis is not unique. (2) Any finite-dimensional C-algebra A generated by one element is positively multiplicative.

Indeed, if we set A = C[a] and denote by µ a the minimal polynomial of a, we can factorize µ a

µ a (X) = k i=1 (X -α i ) m i
where α 1 , . . . , α k are the k distinct complex roots of µ a . Then, by using the Chinese remainder theorem, we get

A ∼ = k i=1 C[X]/(X -α i ) m i .
The right hand algebra is positively multiplicative because each algebra

C[X]/(X -α i ) m i is for the basis {1, X -α i , . . . , (X -α i ) m i -1 }. ( 3
) Regarded as a two-dimensional R-algebra, the field C of complex numbers is not a positively multiplicative algebra. Indeed if such a basis (1, z) existed, we could assume that z 2 = a + bz with (a, b) ∈ R 2 ≥0 and get that z is a non real root of the polynomial X 2 -bX -a. Since its discriminant is positive, this yields a contradiction. (4) Let A be a finite-dimensional commutative subalgebra of M n (C) (the algebra of complex matrices) stable by the adjoint operation. Then, each matrix A in A is diagonalizable because AA * = A * A. Moreover, since A is commutative, there is a common basis of diagonalization. Therefore, the algebra A is isomorphic to C n which is positively multiplicative. (5) Consider any polynomial P (1) Given a PM-algebra A with Z = ∅, any morphism θ : k[Z ±1 ] → k defines a specialization of A that we shall denote A θ . When θ(z k ) ∈ R >0 for any z k ∈ Z, the algebra A θ remains positively multiplicative. Also if A is strongly positively multiplicative, so is A θ . (2) In § 6.3 we will need to apply the following classical theorem (see [START_REF] Bourbaki | Eléments de mathématiques, Algèbre commutative[END_REF], Corollary 4 page 35) to the algebras k[Z ±1 ] and A. Let A 1 ⊂ A 2 be two algebras over k such that A 2 is an integral domain over A 1 and φ : A 1 → C a morphism of algebras. Then, there exists a morphism ϕ : A 2 → C which coincides with φ on A 1 .

(X) = X n -a n-1 X n-1 -• • • -a 0 with (a n-1 , . . . , a 0 ) ∈ R n
The following theorem is an analogue for SPM algebras of a classical result on fusion algebras. It can be regarded as an analogue of the Perron-Frobenius theorem. Consider a finite-dimensional SPM algebra A over k (thus Z = ∅ here) with basis

B = {b 0 = 1, b 1 , . . . , b n-1 }. Write L i
(respectively R i ) for the matrix of the left multiplication (respectively right multiplication) by b i expressed in the basis B. We have L i = (c k i,j ) k,j , that is the j-th column of L i contains the coefficients c k i,j , k ∈ {0, . . . , n -1}. Similarly, R i = (c k j,i ) k,j . One may observe that for any i, j we have

L i R j = R j L i . Now define S = i∈I L i
so that S = (s k,j ) with s k,j = i∈I c k i,j . One can then consider two linear maps

M l : A → M n (k) b i -→ L i and M r : A → M n (k) b i -→ R i
which are the left and right multiplications by the elements of A expressed in the basis B. Both are injective and we have

M l (xy) = M l (x)M l (y), M r (xy) = M r (y)M r (x)
so that M l is a morphism of algebras and M r an anti-automorphism of algebras.

Theorem 2.6. For any finite dimensional strongly positively multiplicative algebra A over k with basis B = {b 0 = 1, b 1 , . . . , b n-1 }, we have the following properties:

(1) The matrix S is positive (i.e. has real positive entries).

(2) The left Perron-Frobenius 1 vector v > 0 with first coordinate equal to 1 of S is a common eigenvector for all the matrices R i .

(3) If we write t vR i = d i t v, the n-tuple (d 0 , . . . , d n-1 ) belongs to R ≥0 with d 0 = 1. (4) The linear map f : A → k defined by f (b i ) = d i , i = 0, . . . , n -1
for any i = 0, . . . , n -1 is the unique morphism of algebras, positive on B. The n-tuple d = (d 0 , . . . , d n-1 ) is called the vector dimension of the algebra A.

Proof. 1: Assume there exists j and k such that s k,j = n-1 i=0 c k i,j = 0. By definition of S and since the matrices L i only have nonnegative integer entries, we must have c k i,j = 0 for any i ∈ I which contradicts the assumption that A is SPM. We get that S is a positive matrix and it admits a left Perron-Frobenius eigenvector v normalized so that its first coordinate is equal to 1.

2: Since L i R j = R j L i for any i, j = 0, . . . , n-1, we obtain SR i = R i S for any i = 0, . . . , n-1. Therefore v is also an left eigenvector of each matrix R i because R i stabilizes the dimension one eigenspace Rv associated to S.

3: If we set t vR i = d i t v, we must have d i ≥ 0 because t vR i and t v have nonnegative coordinates (recall that R i has nonnegative entries). Also

d 0 = 1 for R 0 = I n . 4: Consider the linear map f : A → R such that f (b i ) = d i , i = 0, . . . , n-1.
We have f (b i ) ≥ 0 by Assertion 3 and it remains to prove this is indeed a morphism of algebras. Since

b i b j = n-1 k=0 c k i,j b k
we need to prove that

d i d j = n-1 k=0 c k i,j d k .
1 We can also use right Perron-Frobenius vectors instead of left ones in this theorem. We choose the left version for compatibility with forecoming results in the paper.

We have

t vd j d i = t vR j R i = t v n-1 k=0 c k i,j R k = t v n-1 k=0 c k i,j d k
because M r an anti-automorphism of algebras. This proves the above relation by considering the first coordinate of the vectors. Now to get the unicity, we start with a morphism f : A → R nonnegative on the b i and define u as the vector whose j-th coordinate is f (b j ). We must have

f (b i )f (b k ) = f (b k )f (b i ) = n-1 j=0 c j i,k f (b j ) for any i, k in {0, . . . , n -1}.
We also have f (b 0 ) = f (1) = 1. Write x k for the k-th coordinate of the vector t uS. We can write

x k = n-1 j=0 s j,k f (b j ) = n-1 j=0 n-1 i=0 c j i,k f (b j ) = n-1 i=0 n-1 j=0 c j i,k f (b j ) = n-1 i=0 f (b k )f (b i ) = f (b k )f n-1 i=0 b i .
Since this is true for any k = 0, . . . , n-1, this means that t u is a left eigenvector with nonnegative coordinates for S associated to the nonnegative eigenvalue

d = f n-1 i=0 b i . Since S is a positive matrix, this implies that u = v because f (b 0 ) = 1 = d 0 .
Remark 2.7.

(1) In the group algebra case (which is a fusion algebra), the unique positive morphism of the theorem corresponds to the trivial representation such that f (g) = 1 > 0 for any g ∈ G.

(2) For the character ring R[G] (which is a fusion algebra), the unique positive morphism f is such that f (χ i ) = χ i (1) = dim V i the dimension of the irreducible representation with character χ i . This justifies the general terminology of vector dimension for d = (d 0 , . . . , d n-1 ). (3) Under the hypotheses of the previous theorem, we can consider any linear combination s ∈ A of the b i 's with nonnegative coefficients and the matrix A s of its right multiplication expressed in the basis B. When it is irreducible, the vector v is yet its normalized Perron-Frobenius vector and, if λ s is the associated eigenvalue, the matrix Π = (π i,j ) such that π i,j = v i λsv j a i,j becomes a stochastic matrix. The stationary distribution of its associated Markov chain is v v 1

. In many cases (see for example [START_REF] Diaconis | Group representations in probability and statistics[END_REF]), this Markov chain is interesting in itself (for example there are cut-off phenomenons). We now assume that there exists a linear automorphism 2 ω : A → A such that ω(b i ) = λ i b σ(i) for any i = 0, . . . , n-1 where σ is a permutation of S n and λ i is a positive monomial in k + [Z ±1 ]. This automorphism is also supposed to have finite order m. Therefore the cyclic group generated by ω acts on the set I = {0, . . . , n-1} just by setting ω•i = σ(i). We can decompose I = {0, . . . , n-1}

as the disjoint union

I = r-1 l=0
O l of the ω-orbits in such a way that O 0 is the orbit of 0. Then, 2 Here ω is not necessarily an algebra automorphism.

for each l = 0, . . . , r -1 write i l = min(O l ) (thus O l is the orbit of i l under the action of ω) and define

s l = m-1 a=0 ω a (b i l ) ∈ V l = span(b i | i ∈ O l ).
For any a = 0, . . . , m -1 and any l = 1, . . . , r, set ω a (b

i l ) = λ a,i l b σ a (i l ) . For any k ∈ O l , we set k = σ p k (i l ) and b k = λ -1 p k ,i l ω p k (b i l ) so that we have m-1 a=0 ω a (b k ) = λ -1 p,i l m-1 a=0 ω a+p k (b k ) = λ -1 p k ,i l s l .
Thus, up to a scalar multiple, s l does not depend on the choice of a representative in O l . We also have

ω(s l ) = m a=1 ω a (b i l ) = m-1 a=0 ω a (b i l ) = s l since ω m = 1.
The elements s l , l = 0, . . . , r -1 are linearly independent because they belong to the subspaces V l , l = 0, . . . , r -1 whose direct sum is equal to A. We can thus consider the subspace

S(A) = ⊕ r-1 l=0 k[Z ±1 ]s l in A. Now assume that A = k[Z ±1 ][T ],
i.e the algebra A is generated by the finite subset T in A (in most applications, the set T will be reduced to a singleton). Finally, for any x ∈ T , let us write m x for the multiplication by x in A (which is an endomorphism of A).

Proposition 2.8. With the previous notation, the following assertions hold.

(1) The space S(A) is the set of elements in A fixed by ω with basis S(B) = {s l | 0 ≤ l < r}.

(2) Assume that ω commutes with m x for any x ∈ T 3 . Then S(A) is an ideal of A which is PM for the S(B).

(3) Assume that ω is an algebra automorphism. Then S(A) is a subalgebra of A with PM basis S(B).

Proof. To prove Assertion 1, consider A 1 = ker(ω -id) the space of elements fixed by ω in A.

Since ω(s l ) = s l for any l = 0, . . . , r -1, we have S(A) ⊂ A 1 . Conversely, if ω(x) = x, by writing

x = n-1 i=0 α i b i = r-1 l=0 m-1 a=0 α σ a (i l ) b σ a (i l )
and applying ω, we get

α i λ i = α σ(i) for any i = 1, . . . , n -1. Fix l ∈ {0, . . . , r -1}. We obtain α σ(i l ) b σ(i l ) = α i l λ i l b σ(i l ) = α i l ω(b i l ). Similarly, α σ 2 (i l ) b σ 2 (i l ) = α σ(i l ) λ σ(i l ) b σ 2 (i l ) = α i l λ i l λ σ(i l ) b σ 2 (i l ) = α i l ω 2 (b i l )
. By using the same arguments, one shows that α σ a (i l ) b σ a (i l ) = α i l ω a (b i l ) for any a = 0, . . . , m -1. Thus, we obtain

x = r-1 l=0 a i l m-1 a=0 ω a (b i l ) = r-1 l=0 a i l s l ∈ S(A)
which proves that S(A) = A 1 is the space of elements fixed by ω and S(B) = {s l | 0 ≤ l < r -1} is a basis for S(A).

3 Since T generates A, this is equivalent to say that ω is an automorphism of the algebra A regarded as a A-module.

For Assertion 2, consider s ∈ A such that σ(s) = s and x ∈ A. Write T = {x 1 , . . . , x p }. One can set x = P (x 1 , . . . , x p ) where P ∈ k[Z ±1 ][T 1 , . . . , T p ] is a polynomial in the indeterminates T 1 , . . . , T p with coefficients in k[Z ±1 ]. The multiplication m x by x in A satisfies m x = P (m x 1 , . . . , m xp ). Since m x 1 , . . . , m xp commute with ω, we get that m x also commutes with ω. This gives

ω(x × s) = ω • m x (s) = m x • ω(s) = m x (x) = x × s.
This shows that x × s = s × x belongs to S(A) as soon as s ∈ S(A). Finally, if we consider l and l in {0, . . . , r -1}, the product s l s l decomposes on the basis B with coefficients in k + [Z ±1 ] and also on the basis S(B). Since the supports of the s l 's as elements of B are disjoint, we get that S(B) is a PM basis of S(A).

For Assertion 3, S(A) is clearly stable by multiplication thus is a subalgebra of A. We get that S(B) is a PM basis of S(A) by using the same arguments as previously.

Remark 2.9. Assertion 2 in the previous proposition holds for any commutative * -algebra by taking for ω the involution * . In particular, since b 0 = 1 is fixed by * , the algebra S(A) is unital in this case.

The structure constants for S(B) can be computed from those of B starting from the equalities

s l × s l = m-1 b=0 ω b (b i l ) × s l = m-1 b=0 ω b (b i l × s l ) and b i l × s l = b i l × m-1 a=0 ω a (b i l ) = n-1 k=0 m-1 a=0 λ a,i l c k i l ,σ a (i l ) b k .
We get in particular the following corollary.

Corollary 2.10. For any l = 0, . . . , r -1, we have s 0 × s l = ms l in S(A). It follows that S(A) is also an algebra with unit 1 m s 0 (which is not the same unit as in A in general). Proof. We apply the previous equality with l = 0 that is i l = 0 and b i l = 1 which gives

s 1 × s l = m-1 b=0 ω b (b i l ) × s l = m-1 b=0 ω b (1 × s l ) = ms l .
Example 2.11. The group algebra A = Ce 0 ⊕Ce 1 ⊕Ce 2 of Z/3Z is a fusion algebra where e * 0 = e 0 and e * 1 = e 2 . The matrix of the multiplication by e 1 in (e 0 , e 1 , e 2 ) is the adjacency matrix of the cyclic graph with 3 vertices. By considering s 0 = e 0 = 1 and s 1 = e 1 + e 2 . We get the PM algebra S(A) = Ce 0 ⊕ C(e 1 + e 2 ) and B = {e 0 , e 1 + e 2 }.

Example 2.12. Consider the algebra A of complex characters of the symmetric group S n . Each irreducible character is labelled by a partition λ of n and we write χ λ for the character associated to λ. The character associated to the trivial representation is χ (n) and the sign ε corresponds to χ (1 n ) . Then for any partition λ, we have εχ λ = χ λ where λ is the conjugate partition of λ. Since ε 2 = 1, the multiplication by ε in A is a linear automorphism. It is clear that it commutes with the multiplication by any element of A so that we can apply Assertion 2 of the previous proposition. Let Π n be the set of partitions of n and choose a subset U n of representatives in each orbit O = {λ, λ | λ = λ }. Then we get

S(A) = λ∈Un C(χ λ + χ λ ) ⊕ λ∈Πn,λ=λ Cχ λ . The basis S(B) = {χ λ + χ λ | λ ∈ U n } ∪ {χ λ | λ ∈ π n , λ = λ } is PM in S(A). For any λ ∈ Π n , we have (χ λ + χ λ )(1 + ε) = 2(χ λ + χ λ )
and S(A) is a unital algebra with the unit 1 2 (1 + ε).

Multiplicative graphs

Let Γ be a finite oriented graph with set of vertices V = {v 0 , . . . , v n-1 } and oriented arrows weighted by polynomials in k + [Z ±1 ]. The entries of the adjacency matrix A of Γ are in k

+ [Z ±1 ]. Recall that K = k(Z) is the field of fraction field in the variables {z 1 , . . . , z m }. The adjacency algebra of A is the algebra k[Z ±1 ][A] of polynomials in A with coefficients in k[Z ±1 ].
In the following, we shall assume that our graphs Γ are strongly connected. This means that for each pair of vertices (v i , v j ), there is an oriented path from v i to v j . Any morphism θ : k[Z ±1 ] → R such that θ(z β ) ∈ R >0 for any β ∈ Z m yields a specialization A θ of the matrix A which can again be regarded as the adjacency matrix of a weighted graph Γ θ . The vertices and arrows of Γ θ are the same as those of Γ but the weights on these arrows become positive reals. In particular Γ θ is also strongly connected.

We will denote by G n the group of generalized permutation matrices of size n. These are matrices in which each row and each column contains exactly one nonzero entry equal to a monomial cz β with c ∈ R >0 and β ∈ Z m . Let G Γ be the subgroup of G n of generalized permutation matrices commuting with A. They correspond to the notion of graph automorphisms in the context relevant to the graphs considered here.

Roughly speaking, a multiplicative graph Γ is a graph from which one can construct a matrix algebra containing A with a basis labelled by its vertices and multiplication by A encoded by its edges. We will examine conditions for the existence and the unicity of such a basis, especially when dim K[A] = n.

The notion of multiplicative graph.

Definition 3.1. The strongly connected graph Γ is said to be multiplicative at v i 0 if its adjacency algebra is contained in an algebra 4 A ⊂M n (K) over K with a basis B i 0 = {b i , i = 0, . . . , n -1} satisfying

(3.1) b i 0 = 1 and Ab i = n-1 j=0
a i,j b j for any i = 0, . . . , n -1.

When Γ is multiplicative, we have

A = n-1 i=0 Kb i ⊂ M n (K).
Definition 3.2. The graph Γ has maximal dimension when dim K[A] = n where n is the number of vertices in Γ.

When Γ has maximal dimension, the commutant of its adjacency matrix is the algebra K

[A]. In particular, we obtain G Γ = G n ∩ K[A]. Example 3.3.
(1) The companion matrix A of any polynomial P (X) = X n -a n-1 X n-1 -• • • -a 0 with coefficients a 0 , . . . , a n-1 in R >0 can be regarded as the adjacency matrix of a multiplicative graph Γ rooted at v 0 with basis B 0 = {I n , A, . . . , A n-1 } of maximal dimension. Below we give an example of such graph with P

(X) = X 4 -2X 3 -X 2 -3X -4. 1 X X 2 X 3 1 3 4 2
(2) In general if A is the complex character algebra of a finite group G with PM basis the set B = {χ 0 , . . . , χ n-1 } of irreducible characters and

ϕ = a 0 χ 0 + • • • + a n-1 χ n-1
with (a 0 , . . . , a n-1 ) ∈ R n , the matrix A ϕ of the multiplication by ϕ in the basis B can be regarded as the transition matrix of a graph with set of vertices the n irreducible representations of G and edges weighted by tensor product multiplicities. The basis

I = {1 C 0 , . . . , 1 C n-1 } of characteristic
s = 2≤i≤n (1, i).
where (i, j) is the transposition which flips i and j, we can consider the Cayley graph Γ of G n associated to the transpositions (1, i) for i = 2, . . . , n. It corresponds to the multiplication by s in the basis

B = {e σ | σ ∈ S n } of k[G n ]
and is clearly multiplicative at any vertex σ 0 for the basis e -1 σ 0 B . Nevertheless, the graph Γ is not of maximal dimension since k[A] is a commutative subalgebra of k[G n ] (which is not commutative) thus has dimension less than n!. Remark 3.4.

(1) For a multiplicative graph Γ at v i 0 , we obtain by induction that for any integer j ≥ 0 and any vertex v k (3.2)

A j b k = n-1 i=0 m k i,j b i
where m k i,j is the sum of the weights of the paths with length k in Γ from the vertex v k to the vertex v i (the weight of a path being the product of the weights of its arrows). ( 2) Let M i 0 be the matrix M = (m i 0 i,j ). Since b i 0 = 1, we have

(3.3) A j b i 0 = A j = n-1 i=0 m i 0 i,j b i .
Given a multiplicative graph Γ, we set as usual for any 0 ≤ i, j ≤ n -1

b i b j = n-1 k=0 c k i,j b k .
Since A is a K-algebra, the structure coefficients c k i,j belong to K. In fact, we shall see that the matrices b i and the coefficients c k i,j have coefficients in a k[Z ±1 ]-submodule of K of the form

1 ∆ k[Z ±1
] where ∆ only depends on A. Lemma 3.5. Assume that Γ is strongly connected and multiplicative. For any 0 ≤ j, k ≤ n -1, there exists at least one i ∈ {0, . . . , n -1} such that c k i,j = 0.

Proof. Assume that we have 0 ≤ j 0 , k 0 ≤ n -1 such that c k 0 i,j 0 = 0 for any i ∈ {0, . . . , n -1}. This means that the ideal (b j 0 ) generated by b j 0 in A is contained in ⊕ k =k 0 Kb k . Thus for any nonnegative integer , we have A b j 0 ∈ ⊕ k =k 0 Kb k by (3.2). By the previous remark, this implies that there cannot exist a path in Γ from v j 0 to v k 0 which contradicts our assumption that Γ is strongly connected.

Multiplicative graphs of maximal dimension. When dim K[A] < n, the algebra K[A]

cannot contain a basis satisfying (3.1). Let us now study the case when Γ has maximal dimension n. 5Proposition 3.6. Let Γ as above with n vertices and adjacency matrix A and assume that Γ has maximal dimension.

(1) There exist bases B = {b j , j = 0, . . . , n -1} of K[A] such that for any i = 0, . . . , n -1

(3.4) Ab j = n-1 i=0 a i,j b i .
( Proof. Let m A be multiplication by A in the algebra K[A]. To establish the proposition, we have to show that there exists a basis

B in K[A] such that Mat B (m A ) = A. Since dim K[A] = n, the set B = {A i , i = 0, . . . , n -1} is also a basis of K[A] and we have Mat B (m A ) = C µ A
, that is the matrix of m A in the basis B is the companion matrix of the minimal polynomial µ A of A. The matrices C µ A and A have entries in K and are conjugate in K because dim K[A] = n is the degree of µ A . Thus A = P C µ A P -1 where P is an invertible matrix P with entries in K. Now, if we define the basis B such that the transfer matrix Mat B (B) is equal to

P , we get Mat B (m A ) = A. Next observe that if B 1 and B 2 are two bases of K[A] such that Mat B 1 (m A ) = Mat B 2 (m A ) = A, the transition matrix Q between B 1 and B 2 commutes with A and thus is an invertible in K[A] (recall that the commutant of A is here equal to K[A] for dim K[A] = n). We can set Q = U (A) where U ∈ K[X] is a polynomial in K[X]
of degree less than n. In particular, as a linear map on K[A], the matrix Q acts as the multiplication by the invertible element U (A). The relation (3.4) is preserved by multiplication by any invertible in K[A]. We so get a transitive action of the abelian group of invertible elements in K[A] on the set of bases satisfying (3.4). This implies that b i 0 is invertible in every basis B satisfying (3.4) or no such basis can exist with b i 0 invertible. The normalization with b i 0 = 1 is easily obtained when b i 0 is invertible up to multiplication by b -1 i 0 .

Remark 3.7.

(1) The previous proposition shows that the existence of a multiplicative basis for strongly connected graphs of maximal dimension depends on the choice of a root. In Example 3.10 we define a graph Γ with 3 vertices v 0 , v 1 and v 2 which can only be rooted at v 1 and v 2 . Also there exist graphs which are not multiplicative whatever the choice of the root (for instance the graph in Example 3.10 with z 1 = z 2 = 1). ( 2) Relation (3.4) permits to get the matrix corresponding to the multiplication of any element of K[A] in the basis B. We nevertheless warn the reader that in general, the action of a linear endomorphism of A does not coincide with the multiplication by its matrix in the basis B (which does not necessarily commute with A). This is in particular the case when we consider generalized permutation matrices associated to the basis B.

When µ A , the minimal polynomial of A, is irreducible, the situation simplifies. Recall that our graph Γ is assumed strongly connected. Proposition 3.8. Assume that µ A is irreducible over K. Then Γ has maximal dimension for any choice of the root i 0 and there is a unique basis in K[A] satisfying (3.1) and b i 0 = 1.

Proof. Consider the Frobenius reduction of the matrix A in the field K. Denote its invariant factors by

µ 1 = µ A , µ 2 , . . . , µ r with µ i+1 | µ i for any i = 1, . . . , r -1. Since µ 1 is irreducible we must have µ 1 = µ 2 = • • • = µ r .
The matrix A is conjugate in K to a matrix B with r identical blocks equal to C µ A the companion matrix of µ A . Let us write B = P AP -1 . The matrix P has entries in the field K thus can be written under the form P = 1 d P where P has coefficients in k[Z ±1 ] and d ∈ k[Z ±1 ]. As a consequence, there exists a specialization f θ such that f θ (z k ) > 0 for any k = 1, . . . , m and f θ (d) = 0. As already observed, the matrix A θ then remains irreducible because Γ is strongly connected, thus its Perron-Frobenius eigenvalue λ corresponds to an eigenspace of dimension 1. This implies that r = 1. Indeed, the matrix A θ is conjugate in C to the matrix B θ with r identical blocks, each of them having the eigenvalue λ because it is a root of θ(µ A ). Since r = 1, the minimal polynomial µ A has degree n and we can apply Proposition 3.6 to get a basis B satisfying (3.1). Further since K[A] K[X]/µ A K[X] we know that K[A] is a field. Now b i 0 = 0 (otherwise Γ is not connected) and we can normalize the basis B by multiplicating its elements by b -1 i 0 .

Recall that M i 0 is the matrix whose coefficient m i,j is obtained by counting in Γ the number of paths of length j from the root v i 0 to the vertex v i . When the matrix M i 0 is invertible, it gives a simple combinatorial criterion to insure that b i 0 is invertible and to compute the normalized basis B. Proposition 3.9.

(1) The graph Γ has maximal dimension and there exists a basis B i 0 as in Proposition 3.6 with b i 0 = 1 if and only if the matrix M i 0 is invertible. Moreover in this case, the columns of M -1 i 0 give the vectors of the normalized basis

B i 0 = {b 0 , . . . , b i 0 = 1, . . . , b n-1 } expressed in the basis {1, A, . . . , A n-1 }. (2)
The entries of the matrices in the basis B belong to

1 det M i 0 k[Z ±1 ]. (3) When µ A is irreducible, the matrix M i 0 is invertible.
Proof. Let us prove Assertion 1. When dim K[A] = n, the matrix M i 0 is by (3.2) the transition matrix of the basis {1, A, . . . , A n-1 } expressed in the basis B i 0 normalized so that b i 0 = 1. Therefore, it is invertible and the columns of M -1 i 0 yields the basis B i 0 .

Assume now that M i 0 is invertible and that there exists a a non trivial n-tuple (x 0 , . . . , x n-1 ) in K n such that n-1 j=0 x j A j = 0. By observing that the j-th column C j of M i 0 coincides with the i 0 -th column of A j , we get n-1 j=0 x j C j = 0 and thus a contradiction. This shows that when M i 0 is invertible, we have dim K[A] = n and there thus exists a basis B i 0 satisfying (3.1). Now, by using the equality A j b i 0 = n-1 i=0 m i 0 i,j b i for any 0 ≤ j ≤ n -1 obtained from (3.1) and the fact that M i 0 is invertible, we get that the family {A j b i 0 | j = 0, . . . , n -1} is also a basis of K[A] (its transfer matrix to the basis B i 0 is the invertible matrix M i 0 ). This can only be true if b i 0 is invertible.

The second assertion follows easily from the first one. The third assertion follows from Assertion 1 and Proposition 3.8.

Example 3.10. Consider the strongly connected graph Γ with 3 vertices v 0 , v 1 , v 2 and transition matrix

A =   0 z 1 z 2 1 0 1 1 1 0   . We have µ A (X) = (X + 1) X 2 -X -z 1 -z 2 thus A is of maximal rank. We get M 0 =   1 0 z 1 + z 2 0 1 1 0 1 1   , M 1 =   0 z 1 z 2 1 0 z 1 + 1 0 1 z 1   , M 2 =   0 z 2 z 1 0 1 z 2 1 0 z 2 + 1   and det M 0 = 0, det(M 1 ) = z 2 -z 2 1 , det(M 2 ) = z 2 2 -z 1 .
Thus, in order to get a multiplicative graph, Γ cannot be rooted at v 0 and can be rooted at v 1 (resp. at v 2 ) if and only if z 2 = z 2 1 (resp. z 1 = z 2 2 ). Observe that when z 1 = z 2 = 1, Γ is never multiplicative whatever the choice of the root.

Example 3.11. Consider the graph Γ with adjacency matrix

A =         0 0 z 1 z 3 z 2 0 1 0 0 0 0 z 2 0 1 0 0 0 z 3 0 1 0 0 0 z 1 0 0 1 1 0 0 0 0 0 0 1 0         We get µ A (T ) = T 6 -2 (z 1 + z 3 ) T 3 -4z 2 T 2 + (z 1 -z 3 ) 2 which is irreducible. The matrices M 0 and M -1 0 are respectively         1 0 0 z 1 + z 3 2z 2 0 0 1 0 0 z 1 + z 3 4z 2 0 0 1 0 0 z 1 + 3z 3 0 0 1 0 0 3z 1 + z 3 0 0 0 2 0 0 0 0 0 0 2 0         and         1 0 0 0 -z 1 +z 3 2 -z 2 0 1 2z 2 z 1 -z 3 2z 2 z 3 -z 1 0 -z 1 +z 3 2 0 0 3z 1 +z 3 2z 1 -2z 3 z 1 +3z 3 2z 3 -2z 1 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 0 0 -1 2z 1 -2z 3 -1 2z 3 -2z 1 0 0         .
The graph Γ rooted at v 0 is multiplicative. One can check that all the entries in {b

0 = 1, . . . , b 6 } belong to Q[z 1 , z 2 , z 3 ]. For example, we have b 2 = 1 z 1 -z 3 2z 2 A + 1 2 (3z 1 + z 3 )A 2 - 1 2 A 5 =         0 z 1 z 2 0 0 z 1 z 3 0 0 z 1 0 z 2 0 1 0 0 0 0 0 0 0 0 0 z 1 z 2 0 1 0 0 0 z 1 0 0 0 1 0 0        
Each element in K[A] can be regarded as a n × n matrix with coefficients in the field K, that is as a linear map on K n = ⊕ n-1 i=0 Ke i where (e 1 , . . . , e n ) is the canonical basis of K n . We can reinterpret the invertibility of the matrix M in this context which gives the following theorem.

Theorem 3.12. The matrix M i 0 is invertible if and only if e i 0 is a cyclic vector for the matrix A. 6 In this case:

(1) The basis

B i 0 = {b 0 , . . . , b i 0 = 1, . . . , b n-1 } of K[A] in Theorem 3.9 satisfies b i (e i 0 ) = e i for any i = 0, . . . , n -1, that is the i 0 -th column of b i is equal to e i . (2) We have for any 0 ≤ i, j ≤ n -1 b i b j = n-1 k=0 c k i,j b k
where the coefficients c k i,j , k = 0, . . . , n -1 are exactly those of the j-th column of the matrix b i .

(3) For any 0 ≤ i, j ≤ n -1, the j-th column of the matrix b i is the same as the i-th column of the matrix b j . (4) The graph Γ is multiplicative at v i 0 if and only e i 0 is cyclic and in this case the entries of the matrices in the basis B i 0 and the coefficients c k i,j all belong to

1 det M i 0 k[Z ±1 ].
Proof. For any 0 ≤ k < n, the vector A k e i 0 is given by the i 0 -th column of A k which coincides with the k-th column of M i 0 . Thus M i 0 is invertible if and only if e i 0 is cyclic.

1: Define the matrix C such that Ce i = b i (e i 0 ). To prove that C belongs to K[A], it suffices to show that C commutes with A (because comm(A) = K[A]). On the one hand, we have for any j = 0, . . . , n -1

CAe j = C n-1 i=0 a i,j e i = n-1 i=0 a i,j Ce i = n-1 i=0 a i,j b i e i 0 .
On the other hand

ACe j = (Ab j )e i 0 = n-1 i=0 a i,j b i e i 0 = n-1 i=0 a i,j b i e i 0
where we use (3.1) in the second equality. Now the matrix C is invertible because {b i e i 0 | 0 ≤ i < n} is a basis of K n . Indeed, if we assume there exists (x 0 , . . . , x n-1 ) in K n such that

0≤i<n x i b i e i 0 = 0, we get Be i 0 = 0 with B = 0≤i<n x i b i ∈ K[A]. Thus B = 0 because e i 0 is 6 Recall that a vector v in K n is cyclic for A when {A m v | 0 ≤ m < n} is a basis of K n . Equivalently, the linear map K[A] → K n sending any B on Bv is injective.
a cyclic vector for A in K n . This shows that B = C -1 B i 0 is a basis of K[A] satisfying (3.1). Moreover for any i = 0, . . . , n -1 we have

b i e i 0 = C -1 b i e i 0 = C -1 Ce i = e i .
Now observe that for any B ∈ K[A] we have

(3.5) B = n-1 i=0 x i b i ⇐⇒ Be i 0 = n-1 i=0
x i e i since b i (e 0 ) = e i . We have for any i = 0, . . . (3.4). But by Proposition 3.9, M is then invertible and B is the basis of K[A] determined by Proposition 3.9 which is thus contained in

B i 0 = {b 0 , . . . , b i 0 = 1, . . . , b n-1 } of a K-algebra A satisfying
1 det M i 0 M n (k[Z ±1 ]
). Also by Assertion 1, e i 0 is a cyclic vector for A and by Assertion 2 the structures constants c k i,j also belong to

1 det M i 0 M n (k[Z ±1 ]).
Remark 3.13.

(1) In the course of the previous proof, we have used the equivalence (3.5) which permits to decompose easily an element of K[A] on the basis B i 0 just by looking to its i 0 -th column.

(2) By Proposition 3.8 and Theorem 3.12, we get a simple combinatorial procedure for computing the unique normalized basis B i 0 satisfying (3.1) when it exists. For instance, we can compute explicitely all the structure constants of the homology ring of affine grassmannians for affine Weyl groups of rank 2 [START_REF] Guilhot | Homology rings of affine grassmannians and multiplicative graphs[END_REF].

Definition 3.14. Let Γ be a multiplicative graph of maximal dimension. An index i 0 ∈ {0, . . . , n -1} is a root for Γ when Γ is multiplicative at v i 0 . We denote by R Γ the set of roots for Γ By Theorem 3.12, the set R Γ is the set of indices i 0 such that e i 0 is a cyclic vector for A or equivalently for which the matrix b i 0 ∈ B i 0 is invertible.

Positively multiplicative graphs

In this section, we introduce positively multiplicative graphs from multiplicative graphs. This notion is implicit in many problems related to representation theory, random walks on graphs or the study of harmonic functions on infinite graphs. The notion of positively multiplicative graphs is related to that of positively multiplicative algebras. Indeed, let A be a positively multiplicative algebra over k[Z ±1 ] with positively multiplicative basis

B 0 = {1 = b 0 , b 1 , . . . , b n-1 }. Consider (4.1) s = n-1 i=0 β i b i where β = (β 0 , . . . , β n-1 ) ∈ R n ≥0 .
Let Γ be the graph with set of vertices {v 0 , . . . , v n-1 } and weighted arrows v j a i,j

→ v i where

sb j = n-1 i=0 a i,j b i .
Then, the graph Γ has adjacency matrix A = (a i,j ) which is the matrix of the multiplication by s in A expressed in the basis B 0 . In general the graph Γ is not strongly connected or even connected. To insure the strong connectivity, we need additional hypotheses on the algebra A.

For example, if A is strongly positive and β ∈ R n >0 , the graph Γ is strongly connected and coincides in fact with a complete weighted graph since we have a i,j = 0 for any pairs of vertices v j and v i . For any a ∈ A, recall that L(a) is the matrix of the left multiplication by a expressed in the basis B. Then the map

ρ : A → M n (K) a -→ L(a)
is an injective morphism of algebras. In particular, L(s) = A. Therefore, Γ is positively multiplicative for the algebra A = ρ(A).

χ λ × χ (n-1,1 ) = (l λ -1)χ λ + µ =λ χ µ
where the sum runs over the partitions µ obtained by moving a box in the Young diagram of λ and l λ is the number of distinct parts in λ. The algebra A of characters for S n is PM for the basis B = {χ λ | λ n}. This implies that the Hamermesh graph Γ (whose adjacency matrix is that of the multiplication by χ (n-1,1) in the basis B) is PM. The graph Γ is not of maximal dimension in general. For example, for n = 4, we get the strongly connected graph with transition matrix

A =       0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0      
whose minimal polynomial has degree 4.

Example 4.5. In general, if we define a matrix Γ as above starting from the algebra A of complex characters of a finite group G and its basis B of irreducible characters, it is known that the graph Γ will be strongly connected if and only if the character s in (4.1) is that of a faithful representation of G.

4.2.

Relabelling of vertices and weight changes on PM graphs. Given a positively multiplicative graph Γ at i 0 with adjacency matrix A, algebra A and basis B i 0 as in Definition 3.1, it is natural to consider a larger class of graphs constructed from Γ by authorizing the two following variations (we will see that they preserve the property of being positively multiplicative):

(1) for a permutation σ ∈ S n , switch the labels of the vertices in Γ: the label i becomes σ(i). This gives a new adjacency matrix A σ = T -1 σ AT σ where T σ is the permutation matrix associated to σ.

(2) for λ 0 , . . . , λ n-1 positive monomials in k + [Z ±1 ] and for any vertex v j in Γ, change each arrow v j a i,j

→ v i into v j (λ j /λ i )a i,j → v i .

This gives a new adjacency matrix

A D = D -1 AD where D = diag(λ 0 , . . . , λ n-1 ).
Recall that G n is the group of n×n generalized permutation matrices and that G Γ is its subgroup containing the matrices which commute with A. Since any generalized permutation matrix of G n can be written under the form P = DT σ , we have an action of G n on the adjacency matrices whose description is easy by composing the two previous transformations. Write Γ P for the image of Γ under the action of P . Its adjacency matrix if P -1 AP . We are going to see that this action of G n (by conjugation on the adjacency matrices) restricts to the set of positively multiplicative graphs.

First, we have for all j = 0, . . . , n -1

Ab j = n-1 i=0 a i,j b i ⇐⇒ Ab σ(j) = n-1 i=0 a σ(i),σ(j) b σ(i) ⇐⇒ A σ b σ(j) = n-1 i=0 a σ i,j b σ(i)
where b i = T -1 σ b i T σ for i = 0, . . . , n -1 and A σ = (a σ i,j ) Thus, by setting b σ i = b σ(i) we obtain that the graph Γ σ with transition matrix A σ is positively multiplicative at σ -1 (i 0 ) with basis B σ σ -1 (i 0 ) = {b σ i | i = 0, . . . , n -1}. Similarly, we get A D = (a i,j × λ j λ i ) and the equivalences

Ab j = n-1 i=0 a i,j b i ⇐⇒ A (λ j b j ) = n-1 i=0 λ j λ i a i,j (λ i b i ) ⇐⇒ A D λ j b j = n-1 i=0 λ i λ j a i,j λ i b i
where b i = D -1 b i D for any i = 0, . . . , n -1. Hence the graph Γ D with transition matrix A D is positively multiplicative at i 0 for the basis

B σ i 0 = {b D i | i = 0, . . . , n -1} where b D i = λ i D -1 b i D. Proposition 4.6.
With the previous notation, for any P = DT σ ∈ G n , the graph Γ is positively multiplicative at i 0 for the basis B i 0 if and only if Γ P is positively multiplicative at σ(i 0 ) for the basis B P σ -1 (i 0 ) = {b P 0 , . . . , b P n-1 } where b P i = λ σ(i) P -1 b σ(i) P for any i = 0, . . . , n -1. The corresponding adjacency algebra is obtained similarly by conjugacing with the same generalized permutation matrix and thus also the multiplicative basis of Theorem 3.12. We will consider in Section 5 the case of generalized permutations in G Γ .

Remark 4.7. When P commutes with each elements in the algebra A (thus in particular with the adjacency matrix A), we get b P i = λ σ(i) b σ(i) and thus B P σ -1 (i 0 ) is just the image of B i 0 by the generalized permutation matrix P . 4.3. Root changes. Assume Γ is positively multiplicative at i 0 and j is another root for Γ (see Definition 3.14). We can try to move the root from v i 0 to v j . This modifies the basis B i 0 . In particular, by Theorem 3.12, we get the new basis B j = b -1 j B i 0 . Indeed, the basis b -1 j B i 0 is the unique basis satisfying (3.4) whose j-th vector is equal to 1. Nevertheless, the structure constants of B j are different from those of B i 0 and the graph Γ is not positively multiplicative at j in general. The positivity property of the basis B is not preserved in general by root moves. We say that a root i 0 is positive when Γ is positively multiplicative at i 0 and denote by R + Γ the set of positive roots of Γ. This suggests the following definition.

Definition 4.8. The graph Γ is is positively multiplicative when R + Γ is not empty. Example 4.9. The graph Γ 1 2 3 q with transition matrix

A =   0 0 1 1 0 q 0 1 0  
is PM because it is PM at v 0 (for M 0 = id) but not at v 1 or v 2 when q > 0 as it can be easily checked.

Remark 4.10. A root change in a graph Γ (which does not modify its adjacency matrix) should not be confused with a relabelling of its vertices as studied in § 4.2 (which changes the adjacency matrix). For instance, the corresponding modifications induced on the basis B i 0 have completely different expressions.

The group of maximal indices

We shall assume in this section that Z = ∅ and k = C and thus only consider C-algebras. In § 4.3, we have seen that in general the property of a finite graph to be positively multiplicative is not stable by changing its root. Let Γ be PM finite graph at the fixed root v i 0 and assume that its associated algebra A is commutative. Consider the cone

C(B i 0 ) = n-1 j=0 R ≥0 b j
in the algebra A. We will consider in this section the set of indices i such that

C(B i 0 )(e i ) = R n ≥0
and prove in particular it admits the structure of a commutative group. We start with PM graphs of maximal dimension and next consider the general situation of PM algebras possibly infinite dimensional. 5.1. Generalized permutations and PM graphs of maximal dimension. Consider a PM graph Γ with adjacency matrix A. We will assume in this paragraph that Γ is PM at 0 and has maximal dimension so that A = C[A] is its associated PM algebra with basis B 0 = {1 = b 0 , . . . , b n-1 }. Also, we can apply Theorem 3.12 to Γ. Thus the vector e 0 is cyclic and the map

ϕ : C[A] → ⊕ n i=0 Ce i P (A) → P (A) • e 0
is an isomorphism of vector spaces. This implies that b i , i = 0, . . . , n -1 is the unique element in A such that b i (e 0 ) = e i .

We say that a label i 0 ∈ {0, . . . , n -1} is maximal if for any µ ∈ R n ≥0 with µ 0 + • • • + µ n-1 = 1 there exists ν ∈ R n ≥0 such that (5.1)

n-1 i=0 ν i b i (e i 0 ) = µ.
This is equivalent to the condition C(B i 0 )(e i 0 ) = R n ≥0 but will be easier to extend to the case of infinite-dimensional algebras. In particular, since b i (e 0 ) = e i for any i = 0, . . . , n -1, we get for any µ as above n-1 i=0 µ i b i (e 0 ) = µ and 0 is maximal. Also, the previous n-tuple ν ∈ R n ≥0 in (5.1) is unique because e 0 is cyclic. Recall that we have defined the subgroup

G Γ = {U ∈ G n | U A = AU }
of G n which is the group of generalized automorphisms of the graph Γ whose action on the vertices and edges is described in § 4.2.

Since the ground field is k = C, the group G Γ is contained in the commutant of A which is equal to A and we have in fact G Γ = G n ∩ A. If we set U (e i ) = λ i e σ(i) with (λ 0 , . . . , λ n-1 ) ∈ R n >0 for i = 0, . . . , n -1 and σ ∈ S n , we get

b i U (e 0 ) = U b i (e 0 ) = U (e i ) = λ i e σ(i) . Then n-1 i=0 µ σ(i) λ i λ 0 b i (e σ(0) ) = n-1 i=0 µ σ(i) λ i b i U (e 0 ) = µ.
This shows that e σ(0) is maximal and b σ(0) = 1 λ 0 U ∈ G Γ because U belongs to A and 1 λ 0 U (e 0 ) = e σ(0) . Let us denote by I m the set of maximal indices for Γ. We will prove in the next paragraph the following properties:

• each e i 0 , i 0 ∈ I m is a cyclic vector for A and thus defines a multiplicative basis B (i 0 ) = {b

(i i 0 ) i , i ∈ I}, • for any i 0 ∈ I m , the basis B (i 0 ) is contained in the group G Γ ,
• the group G Γ acts on I m transitively,

• the set I m itself has the structure of an abelian group. In fact, we will establish a stronger result for PM algebras A with bases indexed by a countable set I. We can formalize this phenomenon by the notion of generalized adjacency algebra. Throughout this section, I is a countable set and V will denote the normed vector space 1 (I) of complex sequences (v i ) indexed by I with the 1 -norm v 1 = i∈I |v i |. The vector space V is complete, and we identify I with the Schauder 7 basis (e i ) i∈I of V given by e i (j) = δ ij for i, j ∈ I. We write V + for the cone of V consisting of complex sequences taking non-negative real values, and V +,1 the subset of V + having 1 -norm equal to one. From a measure theory point of view, V denotes the set of finite complex measures on the set I, while V + (resp. V +,1 ) denotes the set of positive (resp. probability) measures on V .

We denote by B(V ) the set of endomorphisms of V which are bounded with respect to the 1 -norm, namely the set of linear maps T : V → V such that

T 1,1 = sup v∈V, v 1 =1 T v 1 < +∞.
The map T → T 1,1 defines a norm on B(V ). If T ∈ B(V ), we write T ij for the coefficient of T e j along e i for i, j ∈ I. Given T 1 and T 2 in B(V ), we have

T 1 T 2 1,1 ≤ T 1 1,1 T 2 1,1
so that T 1 T 2 also belongs to B(V ). This shows that B(V ) is stable by composition of the operators.

Notation 5.1. Given any normed space E and any subset S ⊂ E, write

C(S) = { s∈S λ s s|λ s ≥ 0, s ∈ S} and C 1 (S) = C(S) ∩ B(0, 1)
where the closure is taken with respect to the norm on E and B(0, 1) is the unit ball. 7 A Schauder basis S of a Banach space V is a subset of V such that any element v ∈ V as a unique writing as a convergent sum s∈S ass with as ∈ C, s ∈ S. This is the natural extension of the definition of the basis of a vector space in the Banach space setting.

Definition 5.2.

• An adjacency operator on I is an operator T ∈ B(V ) such that

T ij ≥ 0
for all i, j ∈ I. • A generalized adjacency algebra on I is a closed commutative unital subalgebra of B(V ) generated by adjacency operators on I.

For an adjacency algebra A (regarded as a normed space as previously), define the adjacency cone of A as the cone

C(A) = C({T ∈ A, T adjacency operator on I}).
By definition, A is then generated by C(A). Since C • C ⊂ C, this implies that (5.2) A = span(C).

Example 5.3. If S is a finite set identified as the basis {e 0 , . . . , e n-1 } of a n-dimensional vector space and A is the adjacency matrix of a graph on S then k[A] is an adjacency algebra on S. We always have C(A k , k ≥ 0) ⊂ C(A), but in general the inclusion is strict. Consider for example

A = 1 0 0 2 where A -A 2 /2 = 1/2 0 0 0 ∈ C(k[A]) \ C(A k , k ≥ 0).
Definition 5.4. Two adjacency algebras A, A on I are isomorphic if there exists an invertible adjacency operator U : V → V such that U -1 is again an adjacency operator and such that

A = {U AU -1 | A ∈ A}.
It is then straightforward to prove that for two isomorphic adjacency algebras A and A we have C(A ) = U C(A)U -1 . As the following lemma shows, isomorphisms between adjacency algebras are approximately equivalent to generalized permutations of the set I i.e. permutations and diagonal rescalling of the basis (e i ) i∈I . Lemma 5.5. If T is an invertible adjacency operator such that T -1 is also an adjacency operator, then T is a permutation up to a multiplication by a diagonal, meaning that there exists a permutation σ of I and a family {λ i } i∈I of positive reals such that T e i = λ i e σ(i) .

Proof. Suppose by contradiction the existence of i 0 ∈ I and i 1 , i 2 ∈ I with i 1 = i 2 such that

T e i 0 = λe i 1 + µe i 2 + i∈I\{i 1 ,i 2 }
l i e i with λ, µ > 0 and l i ≥ 0 for all i ∈ I \ {i 1 , i 2 }. Then, since T -1 T e i 0 = e i 0 and T -1 has nonnegative entries, the latter equality implies that both T -1 e i 1 and T -1 e i 2 belong to R ≥0 e i 0 . But this contradicts the fact that T -1 is invertible.

For i ∈ I and an adjacency algebra A, denote by ev i : A → V the evaluation map A → Ae i . In the following definition, recall that A is a Banach space as a closed subspace of B(V ) and that a linear map f :

E → F between Banach spaces is coercive if inf x∈E, x E =1 f (x) F > 0.
Remark in particular that coercivity implies injectivity for a linear map. Both notion coincide when I is finite because A is then finite-dimensional and its unit ball is compact. Definition 5.6. Let A be an adjacency algebra A on I and consider an element i ∈ I.

• The element i is nondegenerate if ev i is coercive (and thus injective) as a linear map from A to V .

• The element i is maximal if ev i is surjective from C(A) to V + .

In the latter definition, coercivity can be replaced by injectivity when I is finite. We first state a result proving that we mostly have to establish non-degeneracy at one maximal element to get non-degeneracy at any maximal element. Remark also that maximality of an element i ∈ I implies by (5.2) that e i is a cyclic vector for A.

Lemma 5.7. Suppose that i 0 ∈ I is non-degenerate and maximal. Then, any i ∈ I which is maximal is also non-degenerate. If I is finite and i 0 ∈ I is maximal for A, then i 0 is also non-degenerate and dim A = |I|.

Proof. Suppose that i 0 ∈ I is maximal and non-degenerate for A, and set

α = inf T ∈A, T 1,1 =1 ev i 0 (T ) 1 .
We have α > 0 by coercivity of ev i 0 . Let i ∈ I be another element which is also maximal. Let T ∈ C(A) be such that T 1,1 = 1. Since e i and e i 0 are maximal, there exist U ∈ C(A) such that U e i = e i 0 and U ∈ C(A) such that U e i 0 = e i . Hence, U U e i 0 = e i 0 , and by nondegeneracy of e i 0 we have

U U = Id = U U (recall that A is commutative). In particular, T U 1,1 ≥ U -1 1,1 T 1,1 . Hence, ev i (T ) 1 = ev i 0 (T U ) 1 ≥ α T U 1,1 ≥ α U -1 1,1 T 1,1 , so that inf T ∈A, T 1,1 =1 ev i (T ) 1 ≥ α U -1
1,1 > 0, and ev i is is also coercive. Finally, i is also non-degenerate for A.

Suppose that I is finite of cardinal n, so that V is finite dimensional. Then, A is a subalgebra of M n (C). By maximality at i 0 , the map ev i 0 is surjective from A to V , which yields dim(A) ≥ dim V = n. Suppose that T ∈ A is such that T e i 0 = 0. By surjectivity of ev i 0 , for all v ∈ V there exists T v ∈ A such that T v e i 0 = v. Then, by commutativity of A,

T v = T T v e i 0 = T v T e i 0 = 0.
Hence, T v = 0 for all v ∈ V , and so T = 0, which implies that ev i 0 is injective and dim(A) ≥ n. Thus dim A = n and ev i 0 is a linear isomorphism, in particular it is coercive.

Remark 5.8. In general, a commutative sub-algebra of M n (C) can have a dimension much bigger than n: by a theorem of Schur, such an algebra can have dimension at most n 2 /4 + 1, the bound being sharp. Hence, by the latter lemma, a finite-dimensional adjacency algebra for which there exists a maximal element is much closer to the case of a maximal commutative * -subalgebra of M n (C) (see Example 2.2). Beware however that an adjacency algebra is not necessarily diagonalizable, even if there exists a maximal element. This is for example the case for the algebra of upper triangular matrices

A =               λ 1 λ 2 . . . λ n 0 λ 1 . . . . . . . . . . . . λ 2 . . . λ 1      , λ 1 , . . . , λ n ∈ C          ,
for which e n is maximal.

Proposition 5.9. Suppose that A is an adjacency algebra for which i 0 is non-degenerate and maximal. Then, there exists a basis B = {b i } i∈I ⊂ C(A) of A such that C(A) = C(B) and b i e i 0 = e i for all i ∈ I. In particular, A is positively multiplicative.

Proof. Suppose that i 0 is non-degenerate and maximal for A, and denote by b i the element of C(A) such that b i e i 0 = e i . Remark that {b i } i∈I is a free family, since it acts freely on e i 0 by non-degeneracy. Let T ∈ C(A). Then, T e i 0 = i∈I λ i e i , with λ i ≥ 0 because T is an adjacency operator, and

T e i 0 1 = i∈I λ i ≤ T 1,1 e i 0 1 = T 1,1 < +∞.
By non-degeneracy of i 0 , the map ev i 0 is coercive, implying that inf T ∈A,T =0

T e i 0 1

T 1,1 = α > 0. Hence, for i ∈ I we have b i e i 0 1 ≥ α b i 1,1 . On the other hand by construction, b i e i 0 1 = e i = 1 for i ∈ I. Hence, for all i ∈ I we have b

i 1,1 < 1 α . Hence, T := i∈I λ i b i satisfies T 1,1 ≤ 1 α i∈I λ i < +∞
b i = i ∈I λ i
ii b i for some nonnegative λ i ii . Therefore the basis {b i } i∈I is positively multiplicative. We deduce that A is positively multiplicative.

Example 5.10. Given a discrete commutative group G, define

1 (G) = {f : G → C | g∈G |f (g)| < +∞},
and consider the group algebra C[G] = g∈G Cg with multiplication given by the group structure. Consider the left-regular representation ρ of G on the basis {δ g , g ∈ G} of 1 (G) such that ρ(g)δ g = δ gg .

Let A G be the closure of ρ(C[G]) in B( 1 (G)) with respect to the • 1,1 . The algebra A G is then an adjacency algebra G, and the adjacency cone is C(A G ) = g∈G R >0 ρ(g). Indeed, each operator ρ(g) acts by permutation and thus is an adjacency operator. Moreover, since ρ(g)ρ(g ) = ρ(gg ) for g, g ∈ G, we indeed have span(C(A G )) = A G . Remark that every element δ g with g ∈ G is maximal and non-degenerate for A G .

We will see below that the latter example is actually the only example of adjacency algebra on a countable set I for which every element of I is nondegenerate and maximal, up to a normalization. We will fist prove a more general result in Theorem 5.11. If I is countable, any permutation σ of I extend linearly to an operator of B(V ) (also denoted by σ) with the formula σ(e i ) = e σ(i) and we have σ 1,1 = 1.

So, let A be an adjacency algebra on I, and denote by I m ⊂ I the set of elements which are maximal and nondegenerate. We will assume that I m is not empty and that one (and thus all by Lemma 5.7) element of I m is non-degenerate for A. Also denote by G the group of linear automorphisms T : V → V such that T (e i ) = λ i e σ(i) with λ i ∈ R >0 and σ any permutation of I. Recall that G A is the subgroup of G ∩ A.

Theorem 5.11. Under the previous hypotheses, the following assertions hold.

(1) Each i 0 ∈ I m defines a multiplicative basis B (i 0 ) = {b

(i 0 ) i , i ∈ I} for the algebra A. (2) For any i 0 ∈ I m , the set B (i 0 ) = {b (i 0 ) i , i ∈ I} is contained in the group G A .
(3) The group G A acts on I m transitively.

(4) The set I m has the structure of a commutative group. Moreover, there exits a representation ρ of I m on V such that {ρ(i) | i ∈ I m } ⊂ C(A) and ρ(i)e j ∈ R >0 e i•j for i, j ∈ I m , where (i, j) → i • j denotes the product structure on I m .

Example 5.12. We refer to § 7.5 for the example of the fusion rule for the affine group su(2) where the set I m and its associated group structure can be made explicit easily.

The latter theorem says in particular that up to a non-degeneracy condition, the set of maximal elements I m has the structure of an abelian group and, up to a scaling, the action of the group algebra C[I m ] on 1 (I m ) (as introduced in Example 5.10) extends to a representation on all 1 (I) whose image forms an adjacency subalgebra of A. Beware that the group structure on I m is not uniquely defined and depend on the choice of an element in I m . To prove the theorem, we first need the following independent lemma, which roughly says that given a countable commutative group G, there is, up to isomorphism, a unique commutative group G with an exact sequence 0

→ (R >0 , ×) → G → G → 0 (we then say that G is a central extension of G by R >0 ). Namely we then have G G × R >0 . A multiplicative 2-cocycle on a group G is a map f : G × G → R >0 such that f (g, g )f (gg , g ) = f (g, g g )f (g , g ) for all g, g , g ∈ G. It is symmetric when f (g, g ) = f (g , g) and f (1, g) = f (g, 1) = 1 for all g, g ∈ G.
One says that f is a 2-coboundary when there exists a function h :

G → R \ {0} such that f (g, g ) = h(gg ) h(g)h(g ) .
Lemma 5.13. Let G be a commutative countable group. Then any symmetric multiplicative 2-cocycle is a 2-coboundary.

Both sets Z 2 (G, R >0 ) of 2-cocycles and the set B 2 (G, R >0 ) of 2-coboundaries have a commutative group structure given by pointwise multiplication, and

B 2 (G, R >0 ) ⊂ Z 2 (G, R >0 ), so that H 2 (G, R >0 ) = Z 2 (G, R >0 )/B 2 (G, R >0
) is a well-defined abelian group. The proof of the lemma amounts to show that any symmetric 2-cocycle of

Z 2 (G, R >0 ) is sent to 1 G×G in H 2 (G, R >0 ).
Proof. For K a group, denote by Ext(K, R >0 ) the subgroup of H 2 (G, R >0 ) consisting of symmetric 2-cocycles, which is well-defined since all 2-coboundaries are symmetric 2-cocycles. Since G is countable and commutative, we can write G = Z r × G for some r and some finite commutative group G . By Künneth formula (see [START_REF] Karpilovsky | [END_REF]Corollary 2

.6]), Ext(G, R >0 ) Ext(G , R >0 ) × Ext(Z, R >0 ) × • • • × Ext(Z, R >0 ) r times . Since G is finite and the map t → t k , with k the order of G , is an automorphism of R >0 , we have Ext(G , R >0 ) = H 2 (G , R >0 ) = 1 (see [13, Theorem 1.7.(v)]). One also has H 2 (Z, R >0 ) = 1 (see [5, Ch. III, Sec 1]), so that Ext(Z, R >0 ) = 1. Finally Ext(G, R >0 ) = 1.
Hence, if f is a R >0 -valued 2-cocycle on G which is symmetric, then f is a coboundary and there exists h :

G → R >0 such that f (g, g ) = h(gg ) h(g)h(g ) .
Proof of Theorem 5.11. Let I m be the subset of maximal elements for A. By hypothesis and Lemma 5.7, they are also non-degenerate. For i ∈ I m , i ∈ I, let b i,i ∈ C(A) be such that b i,i e i = e i . Then, if i ∈ I m , there exists b i ,i ∈ C(A) such that b i ,i e i = e i . This implies that b i ,i b i,i e i = e i , and by non-degeneracy of e i and the fact that Id ∈ C(A), this in turn implies that b i ,i b i,i = b i,i b i ,i = Id. Since b i,i and b i ,i both have positive entries, Lemma 5.5 yields that b i,i and b i ,i belong to G A . Hence, for each i, i ∈ I m , there exists a permutation matrix Σ i,i and a diagonal matrix D i,i with positive diagonal entries such that

(5.3) b i,i = Σ i,i D i,i .
Fix an element i 0 ∈ I m and set b i = b i 0 ,i , Σ i = Σ i 0 ,i and D i = D i 0 ,i . We get the basis B (i 0 ) by Proposition 5.9 and each b i (e i 0 ) = e i for any i ∈ I. We can write

(5.4) b i b i = i ∈I λ i b i ,
for all i, i ∈ I m with λ i ∈ R ≥0 for any i ∈ I. Since b i and b i belong to the group G A , we also have b i b i in G A . Therefore, by looking to the expression on the right hand side of the equality, there should exist j ∈ I such that b i b i = µb j for some µ > 0. Recall that b j (e i 0 ) = e j and i 0 ∈ I m . It follows that we also have j ∈ I m and we can set i

• i := j ∈ I m and λ i,i = λ j > 0 to get b i b i = λ i,i b i•i .
From the commutativity and the associativity of the product in A, we deduce that the product (i, i ) → i • i is commutative and associative. There is also a neutral element given by i 0 , since b i 0 = Id. Likewise, expending b i,i 0 on the basis {b i } i∈I and using a similar argument as before yields an element i ∈ I such that

b i,i 0 = b -1 i = λb i . Hence, this implies b i 0 = Id = λb i b i = λλ i ,i b i •i ,
and i • i = i 0 . Finally, I m has a commutative group structure given by the product (i, i ) → i • i . Let us denote by G Im this group. Then, the map i → b i yields an abelian projective representation of G Im on i∈Im Cb i . Therefore, (i, i ) → λ i,i is a symmetric multiplicative 2-cocycle of G Im with values in R >0 . By Lemma 5.13, λ is a coboundary, and thus there exists

f : G Im → R >0 such that λ i,i = f (i•i ) f (i)f (i ) . Set bi = f (i)b i . Then, bi bi = f (i)f (i )b i b i = f (i)f (i )λ i,i b i•i = λ i,i f (i)f (i ) f (i • i ) bi,i = bi,i , so that the map ρ : i → bi yields a representation of G Im on V such that ρ(i) ∈ G A for all i ∈ I m . Moreover, for i, j ∈ I m , bi e j = f (i)b i b j e i 0 = f (i • j) f (j) b i•j e i 0 = f (i • j) f (j) e i•j ∈ R >0 e i•j ,
which implies that ρ yields a free and transitive permutation representation on the set of halflines {R >0 e i , i ∈ I m }.

As a corollary of Proposition 5.11, we can consider the particular case where all elements of I are maximal for A.

Corollary 5.14. Suppose that A is an adjacency algebra for which each i ∈ I is maximal and nondegenerate. Then, there exists a commutative group structure on I, and a positive diagonal operator Λ such that ΛAΛ -1 = A I , where as in Example 5.10 the algebra A I is the norm-closure of the left-regular representation of C[I] on 1 (I) in the Banach algebra B( 1 (I)).

Proof. By Proposition 5.11, I has a group structure and there is an action ρ : I → B(V ) such that ρ(i) ∈ A for all i ∈ I and ρ(i)e j ∈ R >0 e i•j for all i, j ∈ I. Let i 0 be the neutral element of I and set b i = ρ(i). By the arguments used in the previous proof, for any i ∈ I there exists λ i > 0 such that b i e i 0 = λ i e i•i 0 = λ i e i , with the particular case λ i 0 = 1. Hence, defining the diagonal operator Λ by Λe i = λ -1 i e i , we have Λb i Λ -1 e i 0 = e i . Hence, for i, j ∈ I,

Λb i Λ -1 e j = Λρ(i)Λ -1 Λρ(j)Λ -1 e i 0 = Λρ(i)ρ(j)Λ -1 e i 0 = Λρ(i • j)Λ -1 e i 0 = e i•j .
Let A I be the algebra generated by Λb i Λ -1 , i ∈ I. By the latter results, we have

A I = ρ(C[I]),
where ρ is the left regular representation introduced in Example 5.10. By Proposition 5.9, A is the norm closure of i∈I Cb i . Hence, ΛAΛ -1 is the norm closure of A I , and thus we have

ΛAΛ -1 = A I .
Example 5.15. One can use Corollary 5.14 to construct finite PM-graphs with I = I m . Consider for example the group algebra

A =Ce (0,0) ⊕ Ce (1,0) ⊕ Ce (0,1) ⊕ Ce (1,1)
of Z/2Z × Z/2Z. Let T and T be the matrices of the multiplication by e (1,0) and e (0,1) expressed in the previous basis and (a, b) ∈ R 2 >0 . Then

U = aT + bT =     0 a 0 0 a 0 0 0 0 0 0 a 0 0 a 0     +     0 0 b 0 0 0 0 b b 0 0 0 0 b 0 0     =     0 a b 0 a 0 0 b b 0 0 a 0 b a 0     . Now choose λ = (λ 1 , λ 2 , λ 3 , λ 4 ) ∈ R 4 >0 and set V = DU D -1
where D is the diagonal matrix defined by λ. The matrix

V =      0 a λ 1 λ 2 b λ 1 λ 3 0 a λ 1 λ 2 0 0 b λ 2 λ 4 b λ 1 λ 3 0 0 a λ 3 λ 4 0 b λ 2 λ 4 a λ 3 λ 4 0     
is the adjacency matrix of a PM-graph such that I = I m .

We end this section by showing that the set of positive roots in PM-graphs (see § 4.3) coincides with the set I m of maximal indices in its associated basis B. Proposition 5.16. Let Γ be a finite PM graph rooted at i 0 with basis B i 0 .

(1) The set of maximal indices labels the positive roots of Γ, that is

R + Γ = {v i | i ∈ I m }. (2) Set B m,i 0 = {b i ∈ B i 0 | i ∈ I m }.
Then, we have B m,i 0 = B i 0 ∩ G Γ : the maximal indices labels the generalized permutations appearing in B i 0 .

Proof. Let us prove Assertion 1. Recall that v i belongs to R + Γ if and only if b -1 i B i 0 has nonnegative structure constants. This means that we then have b

-1 i B i 0 ×b -1 i B i 0 ⊂ b -1 i C(A) because C(A)
coincides with C(B i 0 ) by Proposition 5.9. For any i ∈ I m , it follows from Theorem 5.11 that b i is a generalized permutation. Thus b -1 i ∈ C(A) and also b

-1 i B i 0 ⊂ C(A). Now we have b -1 i B i 0 × b -1 i B i 0 = b -1 i (b -1 i B i 0 × B i 0 ) ⊂ b -1 i (C(A) × C(A)) ⊂ b -1 i C(A) because C(A) is stable by product. This shows that I m ⊂ R + Γ . Conversely, assume that i ∈ R + Γ . Then, b i is invertible and b -1 i ∈ b -1 i B i 0 since 1 ∈ b -1 i B i 0 . Thus, we get b -1 i × b -1 i = b -1 i c with c ∈ C(A). This proves that b -1 i ∈ C(A).
Since the cone C(A) is stable by multiplication, it follows that the map c → b i C(A) is a bijection from C(A) on itself (with inverse the multiplication by b -1 i ). This implies that

C(A)(e i ) = C(A)b i (e i 0 ) = b i C(A)(e i 0 ) = C(A)(e i 0 ) = V + .
We get that i is maximal. But it is also nondegenerate by Lemma 5.7 because Γ is finite. Thus, we have R + Γ = I m as desired. To prove Assertion 2, observe first that we have B m,i 0 ⊂ B i 0 ∩ G Γ by Assertion 2 of Theorem 5.11. Now, if b i belongs to B i 0 ∩ G Γ its inverse is an adjacency matrix in A and we have b -1 i ∈ C(A). By using the previous arguments, we get b i C(A) = C(A) and therefore

C(A)v i = C(A)b i v i 0 = C(A)v i 0 = V + which shows that i ∈ I m . Thus, B m,i 0 ⊃ B i 0 ∩ G Γ as desired.

Infinite PM graphs and harmonic functions

The goal of this section is to present a general combinatorial construction (called expansion) yielding infinite rooted graphs from finite ones. To simplify the exposition, we will also assume that all the algebras considered are commutative.

6.1. Expansion of a graph. Let Γ be a strongly connected rooted graph with root v 0 and transition matrix A = (a i,j ) in M n (k + [Z ±1 ]). For any 0 ≤ i, j ≤ n -1, we can set

a i,j = β i,j m i,j z β i,j
with m i,j ∈ R ≥0 and β i,j ∈ N. It will be convenient in this section to replace each arrow v j a i,j → v i weighted by the polynomial a i,j by the collection of arrows v j m i,j z β i,j → v i weighted by the monomials appearing in a i,j . Thus we will now assume the weights on the arrows of Γ are positive monomials in k + [Z ±1 ]. A path π of length on Γ is a sequence of + 1 vertices on Γ starting at v 0 with two consecutive vertices being connected by an oriented arrow. The length of a path π is denoted (π). The weight wt(π) of the path π is the product of the weights of the arrows encountered. Therefore wt(π) is a positive monomial of the form cz β with c > 0. Definition 6.1. The expansion of the graph Γ is the rooted graded graph with graded set of vertices Γ e = (Γ ) ∈N constructed by induction as follows:

• (v 0 , 1, 0) ∈ Γ 0 • if (v i , z β , ) ∈ Γ
and there is an arrow v j m i,j z β i,j → v i in Γ then (v j , z β+β i,j , + 1) ∈ Γ +1 and there is an arrow (v i , z β , )

m i,j → (v j , z β+β i,j , + 1) in Γ e
c k i,j = δ∈N m c k i,j (δ)z δ .
The algebra A is also a k-algebra that we will denote by A k . The k-algebra A k is infinitedimensional algebra with basis {z β b i | i = 0, . . . , n -1 and β ∈ N m }. In order to extend the notion of positively multiplicative graphs to the expansion Γ e of Γ, we will in fact need the larger algebra

A e = A k ⊗ k k[q]
where q is a new indeterminate distinct from z 1 , . . . , z m . The powers of q will record the lengths of the paths starting from the root of Γ e . As a k-algebra, it has basis

B e = {q z β b i | i = 0, . . . , n -1, β ∈ N m , ∈ N}.
Let us write A e for the subspace of A e with basis B e = {q z

β b i | (v i , z β , ) ∈ Γ e }.
Proposition 6.2. With the previous notation, the following assertions hold in A e .

(1) For any vertex

(v j , z β , ) ∈ Γ e qA × q z β b j = (v j ,z β , ) m i,j → (v i ,z β , +1) m i,j q +1 z β b i .
(2) The element 1 = q 0 z 0 b 0 belongs to B e and the product of two elements in the basis B e expands on B e with nonnegative real coefficients. In particular A e is a subalgebra of A e with PM basis B e .

Proof. 1: Consider (v j , z β , ) a vertex in Γ e . We have

qA × q z β bj = q +1 z β Abj = q +1 z β n-1 i=0 ai,jbi = n-1 i=0 mi,jq +1 z β+β i,j bi = (z β ,v j , ) m i,j → (z β ,v i , +1)
mi,jq +1 z β bi.

2: Given q z β b i and q s z γ b j in the basis B e , we can write

q z β b i × q s z γ b j = n-1 k=0 c k i,j q +s z β+γ b k = n-1 k=0 δ∈N m c k i,j (δ)
(v 0 , 0) → (v 1 , 1) → (v 0 , 2) → (v 1 , 3) → • • • .
Remark 6.4. In fact, the interesting finite graphs Γ have often additional properties which simplify the definition and the study of their expansion . This is the case when (1) The weights of Γ are only nonnegative reals (there is no indeterminate z i ) as in the previous example. (2) The length of a path is completly determined by its weight and by its end point in Γ.

In this case, the indeterminate q in the previous construction is redundant and can be omitted. This is for example the case for the graph considered in the example below.

Example 6.5. The graph Γ ∅ z 1 z 2 with transition matrix A = 0 z 1 + z 2 1 0 is PM (the minimal polynomial µ A (X) = X 2 +z 1 +z 2 of A is irreducible) with A = RI 2 ⊕RA and B = {I 2 , A}. We draw the graph Γ e of the expansion of Γ below on the left handside. The indeterminate q can be omitted, since when (v, z β , ) ∈ Γ e we must have = 2 (

β 1 + β 2 ) + 1 if v = and = 2(β 1 + β 2 ) if v = ∅.
We have

A e = R[z 1 , z 2 ]I 2 ⊕ R[z 1 , z 2 ]A.
Note that the graph Γ e is in fact the graph of 2-bounded partitions (that is partition parts less than or equal to 2), we draw this graph on the right handside.

(∅,1,0) → v weighted by nonnegative reals a v ,v . For any vertex v i 0 in Γ, let Γ v i 0 be the rooted graph with root v i 0 obtained by considering only the vertices v connected to v i 0 by a path in Γ and the arrows belonging to such a path. Also let Γ \ Γ v i 0 be the graph obtained by deleting in Γ all the vertices of Γ v i 0 and all the edges that end in Γ v i 0 . Definition 6.6. The infinite graph Γ is said

( , 1, 1) (∅, z 1 , 2) (∅, z 2 , 2) ( , z 1 , 3) ( , z 2 , 3) (∅, z 2 1 , 4) (∅, z 1 z 2 , 4) (∅, z 2 2 , 4) ( , z 2 1 , 5) ( , z 1 z 2 , 5) ( , z 2 2 , 5) (∅, z 3 1 , 6) (∅, z 2 1 z 2 , 6) (∅, z 1 z 2 2 , 6) (∅, z 3 2 , 6)
• positively multiplicative when there exists an associative algebra A over k, positively multiplicative for a distinguished basis

B = {b v | v ∈ Γ} ⊂ A, such that b v 0 = 1, and
γb v = v→v a v ,v b v for any v ∈ Γ where 8 γ = v 0 →v a v ,v 0 b v .
• positively quotient multiplicative if it is positively multiplicative for a commutative algebra A and for any v i 0 ∈ Γ, the subspace I v i 0 = ⊕ v∈Γv i 0 kb v is an ideal in the algebra A.

The following proposition justifies our terminology. Proposition 6.7. Assume Γ is positively quotient multiplicative for the commutative algebra A with basis B. For any vertex v i 0 ∈ Γ, the graph Γ \ Γ v i 0 is positively multiplicative for the algebra

A v i 0 = A/I v i 0 with basis B v i 0 = { bv | v / ∈ Γ v i 0 } where x → x is the canonical projection from A to A v i 0 .
Proof. We have by definition of A v i 0 , bv = 0 if v ∈ Γ v i 0 . Assume, there exist v 1 , . . . , v a vertices in Γ \ Γ v i 0 and x 1 , . . . , x a in k a such that a l=0 xb vl = 0.

Since

I v i 0 = ⊕ v∈Γv i 0 kb v , this means that a l=0 x l b v l belongs to ⊕ v∈Γv i 0 kb v which is only possible if each x l is equal to zero because B is a k-basis of A. This implies that B v i 0 is a basis of A v i 0 . For v and v in Γ \ Γ v i 0 , we get bv bv = v ∈Γ c v v,v bv = v ∈Γ\Γv i 0 c v v,v bv for bv = 0 if v ∈ Γ v i 0 .
We have proved that Γ \ Γ v i 0 is positively multiplicative for the algebra

A v i 0 with basis B v i 0 . Definition 6.8. A nonnegative (resp. positive) harmonic function on Γ is a map f : Γ→R ≥0 such that f (v 0 ) = 1 and for any vertex v ∈ Γ f (v) ≥ 0 (resp. f (v) > 0) and f (v) = v→v a v ,v f (v ).
Observe that we have then

1 = f (v 0 ) = v 0 →v a v ,v 0 f (v).
Remark 6.9. Positive harmonic functions on Γ are strongly connected to Markov chains. Indeed, if f is positive harmonic, we can define a Markov H chain on Γ with transition matrix Π such that

Π(v, v ) = a v ,v f (v ) f (v) .
It then becomes possible to study H (for example to get its drift, a law of large number etc.) when f is sufficiently simple, in particular when f is extremal (see [START_REF] Kerov | Asymptotic representation theory of the symmetric group and its applications in analysis[END_REF], [START_REF] Lecouvey | Conditioned random walks from Kac-Moody root systems[END_REF] and [START_REF] Lecouvey | Alcove random walks, k-Schur functions and the minimal boundary of the k-bounded partition poset[END_REF] for examples).

We denote by H(Γ) the set of nonnegative harmonic functions on Γ. This is a convex cone and we write H ∂ (Γ) for its subset of extremal points. Recall the following theorem essentially due to Kerov and Vershik (see [START_REF] Kerov | Asymptotic representation theory of the symmetric group and its applications in analysis[END_REF] and also [START_REF] Lecouvey | Central measures on multiplicative graphs, representations of Lie algebras and weight polytopes[END_REF]).

. , p n ) ∈ R m ≥0 with p 1 + • • • + p n = 1
, the morphism ϕ p corresponding to p being the specialization x i = p i , i = 1, . . . , n. The structure coefficients c ν λ,µ are the Littlewood-Richardson coefficients and it is a classical result that c ν λ,µ > 0 only if ν can be reached from λ by a path in Y n (i.e. λ ⊂ ν). This implies that Y n is also positively quotient multiplicative. 6.3. Positive harmonic functions on expanded graphs. Now let Γ be a finite, strongly connected, positively multiplicative graph rooted at v 0 with coefficient in k + [Z ±1 ]. Let A be its adjacency matrix and Γ e the corresponding expanded graph. We shall assume in the following theorem that algebra A associated to Γ is a domain. Also since Γ is rooted at v 0 , we have b 0 = 1 in the basis B. By Proposition 3.8, we know that A is a domain when µ A is irreducible over K. Theorem 6.12. Under the previous assumption and with the notation of § 6.1, the following assertions hold.

(1) The infinite graph Γ e is positively multiplicative with basis B e .

The set H + ∂ (Γ e ) of extremal positive harmonic functions is parametrized by a subset of R m >0 . More precisely, to any t = (t 1 , . . . , t m ) ∈ R m >0 corresponds an extremal harmonic function f t on Γ e such that f t (v i , z β , q ) = t β s π i for i = 0, . . . , n -1 where π = (π 0 , . . . , π n-1 ) is the left Perron-Frobenius vector of the specialization z k = t k , k = 1, . . . , m in the matrix A and

s =   v 0 →v a v ,v 0 π i   -1 .
Moreover, all the elements in H + ∂ (Γ e ) are obtained in this way. Proof. 1: This immediately follows from Proposition 6.2.

2: By Theorem 6.10, the elements of H + ∂ (Γ e ) are determined by the morphisms ϕ : A e → R positive on the basis B e and such that ϕ(γ) = 1 where

γ = q v 0 →v a v ,v 0 b v .
Consider such a morphism and set ϕ(q) = s ∈ R >0 , ϕ(z k ) = t k ∈ R >0 for each k = 1, . . . , n. For any j = 1, . . . , n -1, we have in the expanded algebra A e Ab j = n-1 i=0 m i,j z β i,j b i (recall that the weights of Γ are now monomials up to addition of arrows) which gives (6.1)

ϕ(b j )ϕ(A) = n-1 i=0 m i,j t β i,j ϕ(b i ).
Let A t be the matrix obtained by specializing each indeterminate z i in t i . If we set π i = ϕ(b i ) for any i = 0, . . . , n -1, then the vector π = (π 0 , . . . , π n-1 ) is a left eigenvector of A t with positive entries for the positive eigenvalue λ = ϕ(A). Since the matrix A t is still irreducible (because the t i 's are positive), π should be equal to the unique left Perron-Frobenius vector of A t and ϕ(A) is the associated Perron-Frobenius eigenvalue. The corresponding positive extremal function f is defined on Γ e by f (v i , z β , q ) = ϕ(q z β b i ) = s t β π i where (6.2)

s =   v 0 →v a v ,v 0 π i   -1 because ϕ(γ) = 1.
Conversely, for any t = (t 1 , . . . , t m ) ∈ R m >0 , let A t be the matrix obtained by specializing in A each indeterminate z i in t i and (π 0 = 1, π 1 , . . . , π n-1 ) its normalized Perron-Frobenius vector. We have a morphism φ : k[Z, q] → R defined by φ(q) = s (s is as in (6.2)) and φ(z k ) = t k for any k = 1, . . . , m. Since A k is a domain and A e = A k ⊗ k k[q], the algebra A e is also a domain.

We have moreover the inclusions of algebras k

[Z, q] ⊂ k[Z, q][A] ⊂ A e
which are all domains. By Lemma 2.4 the algebra A e is an integral domain over k[Z, q], thus also over k[Z, q][A]. Let λ be the left Perron-Frobenius eigenvalue of A t . We can extend φ to a morphism of algebras φ : k[Z, q][A] → R just by setting φ(A) = λ. Now, as explained in Remark 2.5, one can extend φ to a morphism of algebras ϕ : A e → C. Then, the numbers ϕ(b j ), j = 0, . . . , n -1 satisfy the equality (6.1) which means that (ϕ(b 0 ) = 1, ϕ(b 1 ), . . . , ϕ(b n-1 )) is the left eigenvector of φ(A) = A t associated to λ normalized so that its first coordinate is equal to 1. Since, this eigenvector is unique, we must have ϕ(b j ) = π i for any i = 0, . . . , n -1. This proves that we can indeed define from any t = (t 1 , . . . , t m ) ∈ R m >0 a morphism ϕ : A e → R positive on the basis B e and such that ϕ(γ) = 1. Remark 6.13. The arguments used in the proof of the previous theorem show that the morphisms obtained (and thus also the harmonic functions) are essentially determined by their restrictions to k[Z ±1 ] thanks to the Perron-Frobenius theorem. Nevertheless, in the previous construction, it can happen that two elements in R m >0 give the same positive harmonic function.

Column and row KR crystals of affine type A

The goal of this section is to present two particular families of positively multiplicative graphs. In contrast to their combinatorial definition which is very simple, their associated multiplicative algebras have sophisticated structure constants for which no simple combinatorial description is known. They will provide us interesting illustrations of the notions and results presented in the previous sections of the paper. For more detail about their connection with the representation theory of affine quantum groups, we refer the reader to [START_REF] Bump | Crystal Bases: Representations And Combinatorics[END_REF].

C i → C ⇐⇒ (C ) ♦ n-i → C ♦ .
The column C ♦ is obtained by changing each letter i ∈ C by n -i and then reordering. There is also a graph automorphism P called the promotion and such that Fix and order on the vertices of B a k,n and write A a n,k for the adjacency matrix of B a n,k . Example 7.2.

(1) Assume n = 5 and k = 2. We get

A a 2,5 =                
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0

               
with the columns of height 2 ordered as follows and minimal polynomial X 10 -11X 5 -1. In particular, B 2,5 is of maximal dimension. (2) When n = 6 and k = 2, the minimal polynomial of A a 2,6 is X 13 -26X 7 -27X. Thus B a 2,6 is not of maximal dimension. The row P (L) is obtained by adding 1 modulo n to each entries in L and next reordering.

Observe that the partitions λ contained in l n-1 are in bijection with the row tableaux of length l on A n by associating an entry i + 1 to each column of height i ∈ {0, . . . , n -1} appearing in if any). In particular, in the algebra A 1 k,l , the matrix of the multiplication by b (1) in the basis b λ is the adjacency matrix of the KR-crystal B k,n .

(3) The structure constants associated to B a k,l in the algebra A 1 k,l are nonnegative integers. Corollary 7.6. The graph B a k,n with n = l + k is positively multiplicative for the algebra A q k,l with the basis B a k,l . Now, let us turn to the algebra S k,l := Λ k /J k,l = Q k,l / e k = 1 .

Theorem 7.7. (See [START_REF] Beauville | Conformal blocks, Fusion rings and the Verlinde formula[END_REF][START_REF] Bertram | Quantum multiplication of Schur polynomials[END_REF]) Set n = k. In the algebra S k,l the following statements hold. where ν is obtained by adding one box to λ, next by deleting a column of height k if this makes appear one. In particular, in the algebra S k,l , the matrix of the multiplication by b 1 in the basis B s k,l is the adjacency matrix of the KR-crystal labelled by the rows of length l on {1, . . . , k}.

(3) The structure constants associated to B s k,n in the algebra S k,l are nonnegative integers. Corollary 7.8. The graph B s l,n with n = k is positively multiplicative for the algebra S k,l with the basis B s k,n . 7.5. An example: the graph B s l,2 . We consider KR-graphs B s l,2 with one row and l columns filled with integers in {1, 2}. The first examples of these graphs are : The adjacency matrix of B s l,2 is the (l + 1) × (l + 1)-matrix Since e 2 = x 1 x 2 , we just have x 2 = x -1 1 and by setting x = x 1 , the elements of Sym[x 1 , x 2 ]/(e 2 = 1) can be regarded as the Q-algebra L[x, x -1 ] of Laurent polynomials P in the indeterminate x such that P (x -1 ) = P (x). Now in L[x, x -1 ], we have h a (x, x -1 ) = 1≤i≤j≤l|i+j=a x i x -j = x -a a i=0

A l =          0
x 2i = x a+1 -x -a-1

x -x -1 .

Therefore S 2,l is isomorphic to the algebra L[x, x -1 ]/(x l+2 -x -l-2) ). A simple computation shows that h i (x, x -1 ) × h j (x, x -1 ) = j k=0 h i+j-2k (x, x -1 ) Write writing b i , i = 0, . . . , l for the image of h a (x, x -1 ) in L[x, x -1 ]/(x l+2 -x -(l+2) ) and define B = {b 0 = 1, . . . , b l }. By setting x = x mod(x l+2 -x -(l+2) ) we get x l+2 = x -l-2 . Therefore, for any 0 ≤ a ≤ l -1, one has since b l+1+a = x l+a+2 -x -l-a-2

x -x -1 = x -l-2+a -x l+2-a x -x -1 = -b l+1-a .

This gives if we assume i ≥ j

b i b j = b i-j + b i-j+2 + • • • + b i+j if i + j ≤ l and b i b j = j k=0 b i+j-2k = b i-j + • • • + b l + 0 -b l -• • • -b i+j-l-1 = b i-j + • • • + b 2(l+1)-i-j-1 if i + j > l.
This can be summarize by the rules

b i b j = b |i-j| + • • • + b i+j if i + j ≤ l, b |i-j| + • • • + b 2(l+1)-i-j-1 if i + j > l.
One may recognize the fusion rules for the fusion algebra su 2 (see [START_REF] Di Francesco | Conformal Field Theory[END_REF]) at level l. This construction is related to Conformal Field Theory. The Perron-Frobenius eigenvalue of the adjacency matrix of B s l,2 is λ = 2 cos π l+2 with normalized associated eigenvector 1 sin π l+2 (sin aπ l + 2 ) 1≤a≤l+1 .

It is also possible to determine the set I m of maximal indices and its group structure studied in Section 5 and Theorem 5.11. Indeed, the previous fusion rules shows that b 0 b j = 1 and b l b j = b l-j for any j = 0, . . . , l. Also when i = 1, . . . , l -1 the action of b i does not yields a generalized permutation of the basis B. Thus I m = {0, l} and the group structure is given by l • l = 0, l • 0 = 0 • l = l, 0 • 0 = 0.

≥0andA

  its companion matrix. Then k[A] is a n-dimensional positively multiplicative subalgebra of M n (k) for the basis {A k | k = 0, . . . , n -1}.[START_REF] Bump | Crystal Bases: Representations And Combinatorics[END_REF] For any finite group G, the group algebra C[G] is a PM algebra for the basis {g | g ∈ G}. (7) For any finite group G, its complex character ring R[G] is a commutative PM algebra with basis the set of irreducible characters. Observe that R[G] is isomorphic to C n just by considering the basis of indicator functions associated to the conjugacy classes of G. (8) Homology and cohomology rings associated to algebraic varieties are other important examples of PM algebras. The last two previous examples are particular cases of fusion algebras. Recall that a fusion algebra is an algebra over k = C (here Z = ∅) with a positively multiplicative basis B = {b i , i ∈ I} and an involutive anti-automorphism * satisfying (2.1) b * i = b i * with i * ∈ I for any i ∈ I and c k i,j = c j i * ,k for any i, j, k ∈ I. Lemma 2.3. Every fusion algebra is strongly positively multiplicative. Proof. Let A be a fusion algebra with basis B. Since * is an anti-automorphism, we have c k i,j = c k j * ,i * = c i * j,k by (2.1). Assume there exists (j, k) ∈ I 2 such that c k i,j = 0 for any i ∈ I. By the previous argument, we have c i * j,k = 0 for any i ∈ I and thus c i j,k = 0 for any i ∈ I since the map i -→ i * is a bijection on I. We get the equality b j b k = 0. This implies that b j * b j b k b k * = 0. Now observe that c 1 j * ,j = c j j,1 = 1 and similarly c 1 k,k * = 1. Since 1 ∈ B and the structure constants of the fusion algebra A are nonnegative, the coefficient of 1 in the product b j * b j b k b k * is positive. Hence b j * b j b k b k * = 0 and we get the desired contradiction. We resume the general setting of Definition 2.1. Lemma 2.4. Assume A is positively multiplicative with I finite. Then it is integral over k[Z ±1 ]. Proof. Since A is generated over k[Z ±1 ] by the elements b i , i ∈ I of the basis B, it suffices to show that the elements b i are integral over k[Z ±1 ]. For any such b i , the matrix of the left multiplication L i by b i in A in the basis B has coefficients in k[Z ±1 ] (in fact in k + [Z ±1 ]). Thus the characteristic polynomial of L i has coefficients in k[Z ±1 ]. This implies that its minimal polynomial, which is also the minimal polynomial of b i also has coefficients in k[Z ±1 ]. This shows that b i is integral over k[Z ±1 ]. Remark 2.5.

2. 2 .

 2 Symmetrization. Consider a commutative algebra A with positively multiplicative basis B = {1 = b 0 , . . . , b n-1 }. As usual, we set b i b j = b k for any i, j = 0, . . . , n -1.

) 3 )

 3 The group of invertible elements of K[A] acts transitively by translation on the set of such bases. In particular, two bases satisfying (3.4) coincide up to multiplication by an invertible of K[A]. For each vertex i 0 in Γ, the matrix b i 0 is either always invertible or never invertible. (When b i 0 is invertible, there exists a unique basis B of K[A] satisfying (3.4) and such that b i 0 = 1 (i.e. so that Γ is multiplicative at i 0 ).

  , n-1 the equalities b i b i 0 (e i 0 ) = b i (e i 0 ) = e i and thus, by the previous argument, b i b i 0 = b i . Since B is a basis of K[A], we must have b i 0 invertible and this implies that b i 0 = 1. We have obtained that our basis B satisfies (3.1) and b i 0 = 1. By Theorem 3.9 it should coincide with B i 0 and C = id. 2: We have b i b j e i 0 = n-1 k=0 c k i,j b k e i 0 ⇐⇒ b i e j = n-1 k=0 c k i,j e k hence the desired assertion. 3: This follows from the fact that b i b j = b j b i in the commutative algebra K[A]. 4: If Γ is multiplicative at i 0 , their should exist a basis

4. 1 . 1 . 4 . 2 .

 1142 The notion of positively multiplicative graphs. Definition 4.1. A positively multiplicative graph at v i 0 is a multiplicative graph at v i 0 for which the structure constants c k i,j of the basis B i 0 belong to k + [Z ±1 ] for any 0 ≤ i, j, k ≤ n -Remark For a positive multiplicative graph we can and will replace the K-algebra of Definition 3.1 by its k[Z ±1 ]-analogue A =⊕ n i=0 k[Z ±1 ]b i in which we can specialize the indeterminates in Z to any positive real numbers.

Example 4 . 3 . 3 . 4 . 4 .

 43344 In Example 3.11, one can check that the matrices of the elements in the basis B 0 have coefficients in Z + [z 1 , z 2 , z 3 ]. Thus the graph is positively multiplicative at i 0 . This is also the case for the graphs in Example 3.ExampleHere is an example of a positively multiplicative graph which is not of maximal dimension. Recall that the characters of the symmetric group S n are parametrized by the partitions λ of n. Let χ λ be the character associated to λ. It was proved by Hamermesh that

5. 2 .

 2 Generalized adjacency algebra and positivity. Consider a positively multiplicative commutative algebra A and assume it has a countable distinguished basis B = {b i , i ∈ I}. Then, the (possibly infinite) matrix A i of the multiplication by any b i expressed in the basis B can be regarded as the adjacency matrix of a graph with weighted arrows b j c k i,j → b k for any i, k in I. When n = card(I) is finite, the family {A i , i ∈ I} generates a sub-algebra of M n (C) isomorphic to A.

  and thus is a well-defined element of C(A) which satisfies T e i 0 = T e i 0 . By non-degeneracy, T = T , and thus T ∈ C(b i , i ∈ I). Therefore, C(A) = C(b i , i ∈ I). For i, i ∈ I, we have b i b i ∈ C(A) and by the previous result b i

  Let Γ be a positively multiplicative finite graph with associated algebra A and basisB = {b 0 = 1, b 1 , . . . , b n-1 }. By definition A is an algebra over k[Z ±1 ] whose structure constants c k i,j belong to k + [Z ±1] and can thus be written on the form

  q +s z δ+β+γ b k which shows that z β b i × z γ b j expands positively on B e . To get assertion 2, it then suffices to observe that B e is the subset of B e containing the elements q z β b i , ≥ 0 which appear with a positive coefficients in the expansions of the powers (qA) , ≥ 0 on the basis B e . Example 6.3. Let Γ the graph v 0 v 1 . It is positively multiplicative with A = RI 2 ⊕ RA and B = {I 2 , A} where A = 0 1 1 0 . It expansion is the graph below where we have omitted the power of z which is always equal to 1:

∅Figure 1 .

 1 Figure 1. The graph Γ e and the graph of 2-bounded partitions

Theorem 6 . 10 .

 610 Assume that k = R and Γ is positively multiplicative with associated algebra A and basisB = {b v | v ∈ Γ} with 1 ∈ B. Then the map f : Γ → R ≥0 belongs to H ∂ (Γ) if and only if the linear form ϕ : A → R such that ϕ(γ) = 1 and ϕ(b v ) = f (v) for any v ∈ Γ is a morphism of R-algebras.Example 6.11. Let Y n be the Young lattice of partitions with at most n parts. Recall that its vertices are the Young diagrams λ associated to the partitions with at most n parts and we have an arrow λ → µ if the Young diagram of µ is obtained by adding a box to the Young diagram of λ. Let A = Sym[x 1 , . . . , x n ] be the R-algebra of symmetric functions in the indeterminates x 1 , . . . , x n and B = {s λ | λ ∈ Y n } where s λ is the Schur function associated to λ. Then Y is positively multiplicative for A with distinguished basis B. Its extremal positive harmonic functions are the morphisms ϕ : A → R such that ϕ(s λ ) ∈ R >0 . One can show in this case that these morphisms are parametrized by the vectors p = (p 1 , . .

7. 1 .Example 7 . 1 . 2 .

 1712 Partition, column and row tableaux. A partition of length k is a sequence of integers λ = (λ 1 ≥ • • • ≥ λ k ≥ 0). It is conveniently identified with its Young diagram as illustrated by the example below λ = (5, 3, 3, 2) ←→ By a column tableau of length k on the alphabet A n = {1 < 2 < • • • < n}, we mean a filling of the Young diagram of shape (1, 1, . . . , 1) (with k ones) by letters of A n which strictly increase from top to bottom. By a row tableau of length l on the alphabet A n , we mean a filling of the Young diagram of shape (l) by letters of A n which increase from left to right. For n = 5, k = 3 and l = 4The Kirillov-Reshetikhin (KR) column crystals. Given integers n ≥ 2 and 1 ≤ k ≤ n, the KR crystal B a k,n is the colored oriented graph with vertices the set of column tableaux of length k on the alphabet A n and arrows• C i → C with i ∈ {1, . . . ,n -1} if and only if i ∈ C, i + 1 / ∈ C and C is the column obtained by replacing i -1 by i in C; • C 0 → C if and only if n ∈ C, 0 / ∈ C and C is the column obtained by replacing n by 0 in C and then reordering. The crystal B a k,n admits an anti-automorphism of graph ♦ such that

  column P (C) is obtained by adding 1 modulo n to each entry in C and then reordering (taking {1, . . . , n} as set of residues). Observe that there is a simple bijection between the columns of height k on {1 < 2 < • • • < n} and the partitions contained in the rectangle (n -k) k .It associates to each columnC = {c k > c k-1 > • • • > c 1 ) the partition λ = (c k -k, c k-1 -k + 1, . . . , c 1 }.It is easy to check that for any partition λ ⊂ (n -k) k the action of the promotion operator satisfiesP (λ) = (λ 1 + 1, . . . , λ k + 1) if λ 1 < n -k, (λ 2 , . . . , λ k , 0) if λ 1 = n -k.

Figure 2 . 6 7. 3 . 0 →

 2630 Figure 2. The graph B a 2,6

( 1 ). ( 2 ) 1 b 1 •

 1211 The set B s k,l = {b λ mod J k,l | λ ⊂ l k-1 } is a Z-basis of S k,l so that dim S k,l = l+k-1 l In S k,l , we have for any λ ⊂ l k-b λ = ν⊂l k-1 b ν

.

  The algebra S 2,l is by construction equal to the quotient Sym[x 1 , x 2 ]/(e 2 = 1, h l+1 = 0).

The algebra A is not assumed commutative even if will be often the case in the following.

In particular, if the graph Γ is multiplicative, its associated algebra is commutative and equal to K[A].

Note that γ is given by the fact that we must have γbv 0 = v→v a v ,v b v and γbv 0 = γ.

the Young diagram of λ. This time, the action of the promotion operator adds a box in each column of λ and next deleting the column of height n if any.

Example 7.3. The graph B s 3,3 is as follows

. . , e k ] be the algebra of symmetric polynomials in the k variables x 1 , . . . , x k . Here

Write P k for the set of partitions with at most k parts. It is well-known that that Λ k admits the two distinguished bases We define the ideals I q k,l = h l+1 , . . . , h l+k-1 , h l+k = (-1) k-1 q and J k,l = h l+1 , . . . , h l+k-1 , e k = 1 and set Q k,l := Λ k /I k,l , A q k,l := Λ k /I q k,l and S k,l := Λ k /J k,l . Clearly the algebras Q k,l and A q k,l are isomorphic by sending h l+k mod I k,l on (-1) k-1 q. They were considered in [START_REF] Bertram | Quantum multiplication of Schur polynomials[END_REF] and [START_REF] Lapointe | Quantum cohomology and the k-Schur basis[END_REF] from where we can extract the following theorems gathering some important properties of these algebras.

Theorem 7.5. (see [START_REF] Lapointe | Quantum cohomology and the k-Schur basis[END_REF]) Set n = l + k.

(

where ν is obtained by adding one box to λ or deleting the first row and column when λ 1 = l and λ has k rows (i.e. by removing the unique possible hook of length l + k -1