In describing this invariant, we are led naturally to eventually positivity questions, which in turn lead to descriptions of the Poisson boundaries (of random walks affiliated with these processes)

MATRICES OF POSITIVE POLYNOMIALS*

DAVID HANDELMAN**

Abstract. Associated to a square matrix all of whose entries are real Laurent polynomials in several variables with no negative coefficients is an ordered “dimension” module introduced by Tuncel, with additional structure, which acts as an invariant for topological Markov chains, and is also an invariant for actions of tori on AF C*-algebras. In describing this invariant, we are led naturally to eventually positivity questions, which in turn lead to descriptions of the Poisson boundaries (of random walks affiliated with these processes).

There is an interplay between the algebraic, dynamical, and probabilistic aspects, for example, if the (suitably defined) endomorphism ring of the dimension module is noetherian, then the boundary is more easily described, the asymptotic behaviour of powers of the matrix is tractible, and the order-theoretic aspects of the dimension module are less difficult to deal with than in general. We also show that under relatively modest conditions, the largest eigenvalue function is a complete invariant for finite equivalence (early results of Marcus and Tuncel showed that it is not a complete invariant in general, but is so if the large eigenvalue is a polynomial).

Key words. positive polynomial, trace, point evaluation, Newton polyhedron, convex polytope, primitive matrix, random walk, order ideal, (topological) shift equivalence, finite equivalence, Choquet simplex, real analytic function.

AMS subject classifications. 37B10, 46B40, 46L80, 32A38, 60J05, 16W80, 19K14, 15A54.

Introduction.

LetM be a matrix whose entries are polynomials indreal variables with no negative coefficients. Tuncel [Tu] initiated a study of “dimension modules” (certain ordered vector spaces) associated to such matrices, in connection with classification problems for (topological) Markov chains. (See [Tu, Tu2] for details.) In this article, we develop structure and classification theory in somewhat different directions.

LetA be eitherZ[x^±1_i ]orR[x^±1_i ](Laurent polynomial rings indvariables), and letA⁺ denote the corresponding set of Laurent polynomials with no negative coefficients. ThenAis a partially ordered ring with positive coneA⁺, and the space of columns of sizen, denotedAⁿ, is an orderedA-module. IfMis in M_nA⁺(i.e.,M is ann×nmatrix with entries fromA⁺), thenM induces an order preservingA-module map, M : Aⁿ → Aⁿ. Iterating this map, we obtain the dimension module associated toM as the direct limit,

G_M := limA^{n M}−→A^{n M}−→A^{n M}−→. . . .

This is an orderedA-module, consisting of equivalence classes,[c, k]where(c, k)∈Aⁿ×N, and[c, k] = [c^′, k^′]if there existsN ≥ k, k^′ such thatM^N−kc = M^N−k′c^′;[c, k]is in the positive coneG⁺_M if there existsN such thatM^Nc ∈ (Aⁿ)⁺. The shift map sending[c, k]7→ [c, k+ 1]is an order automorphism, with inverseMˆ :G_M →G_M defined viaMˆ([c, k]) = [M c, k]. The structural problems referred to earlier arise from attempts to say something about the positive cone ofG_M. Explicitly, one of the crucial problems is

(

S

) Decide in terms ofM (in M_nA⁺) andc (in Aⁿ) whether there exists an integerN so that the columnM^Nchas all of its entries inA⁺.

(Of course,[c, k]belongs toG⁺_M if and only if such anN exists.) Whenn= 1,M is just a polynomialP inA⁺, andf is a Laurent polynomial with integer (or real) coefficients; in this case, (

S

) asks to decide

* Received by the editors March 28, 2008. Accepted for publication August 31, 2009. Handling Editor:

Robert Guralnick.

** Mathematics Department, University of Ottawa, Ottawa ON K1N 6N5, Canada (dehsg@uottawa.ca).

Supported in part by a Discovery grant from NSERC.

if the Laurent polynomialP^mf has no negative coefficients for some integerm. This was solved in [H3, Theorems A and B]. Special cases had been solved by Meissner [Me]. In this situation, the solution leads to connections with a result of Ney and Spitzer [NS], determining the Martin boundary of the random walk onZ^dassociated withP. There were also connections to the weighted moment map of algebraic geometry [Od, p. 94], and to an affine AGL(d,Z)-invariant for compact lattice polytopes [H5], as well as a real affine (AGL(d,R)) invariant for general compact convex polytopes.

The problem (

S

) arises in other contexts than topological Markov chains. IfA=Z[x^±1_i ], the limiting dimension module is a direct limit of partially ordered abelian groups. LetR be an AF C*-algebra [El]

whose ordered Grothendieck group is the limit obtained by evaluating all the variables appearing everywhere in (1) at 1—in other words, eachx_i7→1:

(2) G_M(1) = limZ^{n M}−−−→⁽¹⁾ Z^{n M}−−−→⁽¹⁾ Z^{n M}−−−→⁽¹⁾ . . . .

(Here M(1) an abbreviation of the real nonnegative matrixM(1,1, . . . ,1).) In other words, K0(R) = G_M(1), as ordered abelian groups. Then there is an actionαof the d-torus T = T^d on R so that the equivariant Grothendieck group ofR, K^T₀(R)isG_M when viewed as a partially ordered module over the representation ring ofT, which of course isA. Alternatively,G_M = K0(R×αT). This is a special case of more general results in [HR], which deals with classification results for locally finite actions of tori and other compact Lie groups on AF C*-algebras.

There is a probabilistic interpretation that is closely related. Begin with the matrixM = (M_ij)with entriesM_ij inA⁺. Form the set of sites,S =Z^d× {1,2, . . . , n}. It is helpful to think ofS asndisjoint copies of the latticeZ^dpiled on top of each other, with the second coordinate indexing the level. A particle at point(z, k)∈S(lattice pointz, levelk) is constrained to jump to leveljin the next unit of time; its motion in this level is governed by the entryM_jk. Write M_jk = P

λ_wx^w where we use multinomial notation x^w = x^w(1)₁ ·. . .·x^w(d)_d , λ_w are all nonnegative real numbers, and we have suppressed the dependence on jk for expository convenience. Then on levelj, the particle moves fromz according to the rule that the probability of displacement by wisλ_w/M_jk(1). Then (

S

) amounts to asking which initial finitely supported signed distributions onSbecome nonnegative after a finite number of iterations of this process.

In the case thatn = 1, this is related to the Poisson boundary, although knowledge of the latter is insufficient to solve (

S

). In this case, letµbe the measure onZ^dobtained fromP: µ({w}) =λ_w/P(1), whereP =P

λ_wx^w. Letν be a finitely supported signed measure, and setν₀=|ν|(any positive measure with the same support asνwill do just as well). The specialization of (

S

) asks if there existsmso that them- fold convolution ofµ, convolved (once) withνbe positive. The answer is affirmative if and only if for every extremal[0,∞]-valued harmonic functionh(onZ^d) finite with respect toν0,P

w∈suppνν(w)h(w) > 0.

Ifν0is mutually absolutely continuous with respect toµor some convolution powerµ^(k)=µ∗ · · · ∗µfor somek, then the set of these extremal harmonic functions is compact (and in this situation is contractible).

However, for generalν₀, the set of such functions need not be either compact or connected (ifd= 1, it is compact, but need not be connected).

Forn >1, there is a choice of initial (row of) measures so that a boundary, analogous to the Poisson boundary, occurs (it is the positive portion of the real maximal ideal space of a partially ordered ring naturally associated toM and is at least compact, although not generally connected). Other choices lead to very complicated situations that must be disentangled in order to attack (

S

).

One can also put the random walk interpretation (actually these admit the same formalism of the

“matrix-valued random walks” occurring in [CW]—although the problems considered are almost entirely unrelated) in the context of subshifts of finite type. By symbol splitting, we may assume that all of the entries ofM are either monomials or zero (although the matrix size may change). FormS =Z^d× {1,2, . . . , n} as we did before, and set

X=S^N X_M =©

x= (w(x, i), k(x, i))∈S^N¯¯Mk(x,i+1),k(x,i)=x^w, w=w(x, i+ 1)−w(x, i)ª .

That is, ifx(i) = (w(x, i), k(x, i))wherew(x, i)∈Z^dandk(x, i)∈ {1,2, . . . , n}, then the sequence x=x(i)belongs toX_Mprovided that for eachiinN, the transition fromw(x, i)tow(x, i+1)is permitted—

that is, w = w(x, i+ 1)−w(x, i) is the exponent of the monomial appearing in thek(x, i+ 1), k(x, i) entry ofM. One can think of this as a shift space on an enormous state space (S), but with relatively few transitions permitted. In general,X_M is not compact, but we may find a lot of compact cylinder sets, by selecting a finite set of elements “z” inSand timesiinN,U ={(z_j, i(j))}(jrunning over a finite index set), and set

K_U ={x∈X_M|there existsjsuch thatx(i(j)) =z_j}.

The pathxbelongs toK_U if it passes through at least one of thez_j at timei(j). This corresponds to the selection of an initial measure.

We normally assumeM is primitive, i.e., some power ofMhas no zero entries; however, at times, we have to face up to the reducible case, which is somewhat more complicated.

The approach used whenn = 1 is elaborated in order to apply to the general case. Associated to the ordered vector spaceG_M is the “bounded subring” (defined in section 1), denotedE_b(G_M). This is a partially ordered ring of endomorphisms of G_M that are bounded in the appropriate sense. Much of the information concerning positivity of elements ofG_M is reflected, although not terribly clearly, in the structure ofE_b(G_M). For example, the (densely defined) traces onG_M in principal permit one to decide positivity of a specific element, and these traces factor through (in the appropriate sense)E_b(G_M). Recall that a trace on an ordered vector space is a nonzero positive linear functional. In this case, “densely defined”

means the domain of the trace is an order ideal inG_M. The (global, that is, everywhere defined) traces ofG_M yield some information about positivity (for example, necessary for[c, k]to be positive is thatτ([c, k])>0 for every global trace onG_M), but these are far from sufficient to determine the ordering, even ifd= 1(in contrast, whenn= d= 1, the global tracesdodetermine the ordering). The pure traces onE_b(G_M)that are not faithful determine ideals ofE_b(G_M), and part of the structure theory is to describe these order ideals, which turn out to correspond (not bijectively) with faces of the convex polytope associated toM by Marcus and Tuncel [MT]. (Whenn= 1, the association is a bijection and many very nice properties hold [H5].)

In the case thatn= 1, the ordered ringE_b(G_M)(in the context ofn= 1, calledR_P [H5]) is always a finitely generated commutative ring/algebra (depending on whether we useZorRin the definition ofA) with no zero divisors. It is easy to see thatE_b(G_M)may have zero divisors and need not be commutative, but generically the characteristic polynomial is irreducible overA, and that case, it is a commutative domain.

Unfortunately, ifn≥2, generically it is not finitely generated; it is not even noetherian; in fact, it does not even satisfy the ascending chain condition on order ideals. This means that the positivity problem is far more complicated than expected. We give necessary conditions in order that this ascending chain condition hold.

Among classification problems is the question of deciding finite equivalence of two such matrices; that is, given squareM andM^′ with entries inA⁺, give criteria in order that there be a nonzero rectangular matrixX with entries in A⁺ such thatM X = XM^′. A necessary condition is given by equality of the corresponding beta functions; for eachr = (r_i)in(R^d)⁺⁺(=©

r∈R^d¯¯ r_i>0, i= 1,2, . . . , dª

),M(r) (all the entries ofMevaluated atr) is a real nonnegative matrix, and our initial primitivity assumption means the large eigenvalue, denotedβ_M(r)(or simplyβ(r)) has multiplicity one; it follows thatr 7→β_M(r)is a real analytic function on(R^d)⁺⁺. A necessary condition for finite equivalence is thatβ_M =β_M^′ on(R^d)⁺⁺. This was conjectured to be sufficient as well. However, Marcus and Tuncel [MT] gave two examples to show this was not the case; I showed (independently, but only in the form of a talk at the Adler conference) that the conjecture failed, for one of the pairs that Marcus and Tuncel considered, by completely different methods. However, it had been known already that ifd= 1, the conjecture is true (Parry), and Marcus and Tuncel [MT2] also showed that ifβ were a polynomial, the conjecture succeeds.

Here we give conditions onMandM^′that guarantee thatβis a complete invariant for finite equivalence.

For any (primitive)M, we can find a left eigenvector forβwhose entries are polynomials inβwith coefficients

fromA, i.e., inR[x^±1_i ][β], and each entry is real analytic and strictly positive on(R^d)⁺⁺. If we can arrange that each entry of the eigenvector is bounded above and below away from zero by a quotient of elements ofA⁺(this is a simplification of the real definition; the actual definition is more general), then we sayM satisfies (%) (a local criterion, using the facial structure ofM, can also be given, 8.7). For example, ifβis polynomial, or ifM is a companion matrix or the transpose thereof, or if the Newton polyhedra of all the entries of some power ofM are the same, then (%) holds. We sayM satisfies (#) if the ratio of the second largest absolute value of eigenvalues ofM(r)toβ_M(r)is bounded above by1−ǫasrvaries over(R^d)⁺⁺. This holds if for every faceFof the convex set associated toM_F, there is a unique irreducible block which hits the spectral radius, and it is primitive (actually, in the statement of the result, the last “primitive” can be deleted), so it is relatively easy to test for.

Imprecisely, we show that among matrices satisfying (#) and (%), the beta function is a complete invariant for finite equivalence. It is conceivable that (#) implies (%), so the latter condition may be redundant. It is also possible that (%) alone is sufficientβto be a complete invariant for finite equivalence.

In results leading up to this, we note that analytic and algebraic functions that are positive on(R^d)⁺⁺can behave rather strangely, and this strangeness is reflected in boundary behaviour. Explicitly, ifρ : (R^d)⁺⁺ → R⁺⁺ is algebraic (i.e., satisfies a polynomial equation with coefficients fromA) and real analytic, and if X :R⁺→(R^d)⁺⁺is the exponential of a ray inR^dwith directional derivativev, then

t→∞lim

logρ(X(t)) logt

may depend on the starting point of the ray; ifρis bounded above and below by integer multiples of a rational function (whose numerator and denominator are inA⁺), then the limit does not depend on the starting point.

This provides a notion of (local) “linkages” between the various blocks ofM_F (for a fixed faceF), which would be part of the data for shift equivalence. In the survey article [Tu2], Tuncel provides a global way of linking blocks.

Principal results. Theorem 4.5 describes completely the pure (global) traces onG_M and its order ideals under the mildest of conditions, as well as the faithful pure traces on E_b(G_M). Roughly speaking, they factor through the left Perron eigenvector forβevaluated at points of(R^d)⁺⁺.

The unfaithful pure traces on order ideals ofE_b(G_M)and ofG_M are described in several situations, completely if the necessary condition for noetherianness holds (sections 5 and 6). Roughly speaking, they factor through quotients corresponding to taking facial matrices. In fact, the unfaithful pure traces could be completely described in this form if an innocuous-looking conjecture were true.

The consequences, and subsequent non-genericity, of the ascending chain condition on order ideals of G_M are discussed in section 7. Some of the relevant conditions can be simply expressed in terms of the weighted graph associated toM.

The finite equivalence result discussed above, Theorem 10.7, is proved in section 10.

In section 12, necessary and sufficient conditions on a size 2 matrixM are determined in order that it satisfy the condition (%) discussed previously. It turns out to be easy to express but difficult to prove:

(%) holds if and only if the discriminant of the matrix divides a polynomial with no negative coefficients, Theorem 12.1. It follows that for size 2 matrices wherein the diagonal entries have no common monomials, (%) is equivalent toM +pI satisfying (#) for somepinA⁺(this property is called weak (#), and admits a much less awkward formulation).

Finally, in section 13, we have a weak realization theorem, which says that under suitable circumstances, given suitable functionsβ, there exists a primitive matrixM for whichβ_M =β^N for some undetermined integerN; moreover,Mmay be selected to satisfy a strong condition, (**), which asserts that in some power ofM, the Newton polyhedra of all the entries are identical.

This paper is a considerable elaboration of results in the preprint, “Eventual positivity and finite equiv- alence for matrices of polynomials”, versions of which were distributed from 1987 on.

Table of contents 1 The bounded endomorphism ring

2 A brief look at the bounded endomorphism ring as an invariant 3 The many faces ofM

4 Faithful traces

5 Attack of the perfidious traces 6 Return of the perfidious traces

7 A F O Ggy example and generic nonnoetherianess 8 LinkingM&Ms

9 Local and global characterization of (#)

10 Finite equivalence for matrices satisfying (%) and weak (#) 11 Structural similarity

12 Two by two matrices

13 Eventual weak similarity to matrices satisfying (**) Appendix Nonnegative real matrices

References

1 The Bounded Endomorphism Ring

In this section, we define and develop the basic properties needed of the ring (algebra) of bounded endomor- phisms. Curiously, even in the case of zero variables, the notion is of some interest.

We recall some notation and definitions from the introduction. The ring of Laurent polynomials in the dvariablesx1,x2,. . . ,x_dover either the integers or reals is denotedA, and the set of elements ofAhaving no negative coefficients is a positive coneA⁺ for A, making the latter into a partially ordered ring. The ring ofn×nmatrices with entries fromAwill be denoted M_nA; of course, M_nA⁺ will denote the set of matrices with entries fromA⁺. For an integern,Aⁿ will denote the set of columns of sizen, viewed as an orderedA-module (with the direct sum ordering). FixnandM in M_nA⁺. The real matrix obtained by evaluating all the variables at1will be denotedM(1), an abbreviation forM(1,1, . . . ,1). Define the direct limit, as orderedA-modules,

(1) G_M = limA^{n M}−→A^{n M}−→A^{n M}−→. . . . This is the set of equivalence classes,

{(a, k)|a∈Aⁿ, k∈N}/∼,

where(a, k) ∼(a^′, k^′)if there existsm > k, k^′such thatM^m−ka=M^m−k′a^′. TheA-module structure is obvious, andG_M admits an ordering making it into a directed partially orderedA-module, by means of the positive cone

G⁺_M =©

[a, k]∈G_M¯¯there exists(a^′, k^′)∼(a, k)witha^′∈(Aⁿ)⁺ª .

We observe that[a, k] = [M a, k+ 1], andM induces an order isomorphism (that commutes with the action ofA) by means ofMˆ[a, k] = [M a, k]; its inverse is given by a “shift”,Mˆ⁻¹[a, k] = [a, k+ 1]. More generally, ifN is in M_nAand commutes withM, thenN induces anA-module endomorphism ofG_M via Nˆ[a, k] = [N a, k]. This will be positive (i.e., order preserving) if and only if there exists an integermso thatN M^k belongs to M_nA⁺. Thus bdescribes an assignment (actually a homomorphism ofA-modules and of rings), from the centralizer ofMin M_nA,C_A(M), to the ring ofA-module endomorphisms ofG_M, End_AG_M.

The matrixMis an element of the centre ofC_A(M), and we may formally invertM; if the determinant ofM is nonzero, this amounts to adjoiningM⁻¹from the matrices with entries in the field of fractions of A(the rational functions in thedvariables). In general, the construction is given as limit ring,

C_A(M)[M⁻¹] = limC_A(M)−−→^×M C_A(M)−−→^×M C_A(M)−−→^×M . . . .

We have been a little sloppy in notation; if the determinant of M is zero, then the ideal of C_A(M), {N ∈C_A(M)|MⁿN = 000}will be factored out. So, despite the notation,C_A(M)will not be a subring of C_A(M)[M⁻¹]. Note that sinceM belongs to ann×nmatrix ring over a field (the rational functions in thedvariables), for any columnasuch thatM^sais zero, it follows thatMⁿais also zero. In any case, b induces a map fromC_A(M)[M⁻¹]to End_AG_M.

DefineE(G_M) =n

e∈End_AG_M

¯¯

¯ eMˆ = ˆM eo

; then the range ofb :C_A(M)[M⁻¹]→ End_AG_M is obviously insideE(G_M). In fact the range is onto, and the map is an isomorphism.

Lemma 1.1

The map

b :C_A(M)[M⁻¹]→E(G_M)

is an isomorphism of rings and

A

-modules.

Proof: It is routine to verify the map is a well-defined homomorphism of rings andA-modules. We first show the map is onto. SelecteinE(G_M). LetE_j (j = 1,2, . . . , n) denote the standard basis elements for Aⁿ. Then we may find elementsa_j inAⁿ together with integersk(j)such thate[E_j,1] = [a_j, k(j)]. We may assume thatk(j)are all equal, say tok, so thate[E_j,1] = [a_j, k]for allj. DefineN0to be then×n matrix with entries fromAwhosejth column isa_j. Obviously,( ˆM)^−(k−1)Nˆ0has the same effect aseon the[E_j,1]’s. It is a routine verification thatP

j[E_j,1]Ais essential (as anA-module) inG_M, so that if two A-module endomorphisms agree on{[E_j,1]}, they are equal. As the mapC_A(M)→C_A(M)[M⁻¹]is not necessarily one to one, it is not immediate thatN0commutes withM. However, it easily follows that there exists an integersso thatN₀M^scommutes withM. SetN =N₀M^s, and observe that( ˆM)^−(k−1+s)Nˆ =e.

Thus the map is onto.

It is immediate from the definitions that the map is one to one: NˆMˆ^−t= 0implies[N E_j,1] = [0,1], so thatM^sN E_j = 0for somes(and allj), whenceM^sN = 0, which meansN is in the kernel of the map

C_A(M)→C_A(M)[M⁻¹]. •

Remark. 1: The portion of the preceding that does not involve the ordering applies if A is a general commutative unital ring andM is an arbitrary square matrix (see [BoH, p. 125ff] whereE(·)is defined for square matrices with entries in a commutative ring).

Now we discuss the positive cone ofE(G_M). The natural definition of a positive cone on a ring of endomorphisms is the following:

E(G_M)⁺ =©

e∈E(G_M)¯¯e(G⁺_M)⊆G⁺_Mª . Lemma 1.2

Under the map

b :C_A(M)[M⁻¹]→E(G_M),

an element of

C_A(M)[M⁻¹]

is sent to a positive element

M^ˆ−kNˆ

of

E(G_M)

if and only if there exists a positive integer

m

such that

M^mN

belongs to M

_nA⁺

.

Proof: Letedenote the endomorphism described byMˆ^−kNˆ. Ife≥ 0,e[E_j,1]≥ [0,1]for allj. Hence there existsksuch that for allj,e[E_j,1] = [a_j, k]wherea_jbelongs to(Aⁿ)⁺. It follows from the definitions that multiplication by some power ofMwill render all the columns ofN positive, which is what we want.

The converse is trivial. •

Now we observe that every element ofE(G_M)is a difference of elements of its positive cone (i.e., as a partially ordered abelian group,E(G_M)isdirected).

Finally, we can define the bounded subring ofE(G_M). Let I :G_M →G_Mdenote the identity element ofE(G_M). Set

E_b(G_M) ={e∈E(G_M)|there existsk∈Nsuch that −kI ≤e≤kI} E_b(G_M)⁺=E_b(G_M)∩E(G_M)⁺

We observe that with the relative ordering,E_b(G_M)is a partially ordered ring; it need not be commu- tative, although this is generic; it is an order ideal inE(G_M), and moreover I is an order unit forE_b(G_M).

ObviouslyG_M is an ordered module over E_b(G_M). However, thatAdoes not act onE_b(G_M), because (informally) all of the former’s elements (except the constants) are unbounded in any reasonable sense.

For now, we make the standing hypothesis that the real matrixM(1)is primitive. This is equivalent to saying that there exists a power ofM so that every entry is not zero. One of the reasons for doing this is to guarantee that ifHis any nonzero order ideal ofG_M then its bounded subring is the same asE_b(G_M), so that all order ideals ofG_M may be viewed as ordered modules over a common partially ordered ring.

Now letHbe an order ideal ofG_M. Recall from the introduction that to describe the ordering onG_M we must analyze all the pure states of the order ideals (that have order units).

Specifically, suppose that G is a partially ordered unperforated abelian group and a is an element thereof. If there exists an order ideal with order unit ofG, I, containingasuch that for all (pure) traces τ of I, τ(a) > 0, then ais in the positive cone of G. If no such order ideal exists, then ais not in the positive cone; in particular, there need not be a minimal order ideal containinga, or there could be a trace on a minimal order ideal with order unit among those containinga, at whichτ(a)<0.

To analyze the traces on an order idealI, we examine the bounded subringsE_b(I); these automatically containIas an order ideal, and their pure trace spaces are compact. Moreover, there is a natural map from the pure trace space of the latter to that ofI. The pure trace spaces are described in sections 4–6.

We may formE(H) = {e∈E(G_M)|eH ⊆H}, and put the relative order on it. It is an ordered subring. Unfortunately, even ifHadmits an order unit,E(H)need not admit the identity as an order unit, so the latter is not generally equal to its bounded subring (which we shall define shortly) even whenn=d= 1.

Example 1.3

An order ideal

H

in

G_M

which has an order unit but for which

E(H)

does not admit the identity as an order unit.

Heren=d= 1, soM =P a polynomial in one variable. SetP = 1 +x+x³. As in [H5],G_M is the ring R[x, x⁻¹, P⁻¹], and the bounded subring,E_b(G_M)is justR_P =R[x/P,1/P]. The positive cone of the latter is generated additively and multiplicatively by©

1/P, x/P, x³/Pª

[H5, I.4]. LetH =Ibe the ideal of R_P generated by{1/P, x/P}. As in [H5], this is also an order ideal ofR_P (hence ofG_M), and(1 +x)/P is an order unit forI. Since each ofx/P², x²/P², andx³/P² belong toI, multiplication by x²/P is a positive endomorphism ofI, which obviously extends to a positive endomorphism ofG_M. However, it is not bounded by a multiple of the identity endomorphism (so that the identity is not an order unit forE(H)).

To see this, we it is sufficient to show that there does not exist an integerksuch that(x²/P)·1 ≤ k·1, i.e.,x²/P ≤ kis impossible. Ifx²/P ≤k, then according to the definition of the ordering, there would existKso thatx²P^K−1≤kP^K with respect to the usual ordering onA=R[x^±1]. In other words, every monomial appearing inx²(1 +x+x³)^K−1would have to appear inP^k. It is a simple exercise to show that x^3K−1appears in the former but not in the latter.

In the case thatn= 1, failure ofE(H)to admit an order unit ifHis an order ideal ofR_P forces the latter ring to be not integrally closed in its field of fractions (see [H5, Section III]). •

IfHis an order ideal ofG_M, we define its bounded subring

E_b(H) ={e∈E(H)|there existsk∈Nsuch that −kI ≤e≤kI} E_b(H)⁺=E_b(H)∩E(H)⁺.

We will show thatE_b(H) =E_b(G_M), at least whenM(1)is primitive. ThusE_b(H)is independent of the choice of (nonzero)H. This requires a series of lemmas.

Lemma 1.4

Suppose that

M(1)

is primitive. If

e

belongs to

E(G_M)⁺

and

eh= 0

for some

h

in

G⁺_M\ {0}

, then

e= 0

.

Proof. We may write h = [a, k] for some a in (Aⁿ)⁺ and some integer k, and we may also assume that e = ˆM^−sNˆ for some matrix N commuting with M, all of whose coefficients lie in A⁺. Then eh= [N a, s+k] = [0, s+k]. This forcesM^tN a= 0for some positive integert. Evaluate all the variables at(1,1, . . . ,1). This yieldsN(1)M^t(1)a(1) = 0. SinceM(1)is primitive and the entries ofa(1)are all nonnegative real numbers (and not all zero, unlesshwere zero to start with), there exists a larger value of tso that all the entries ofM^t(1)a(1)are strictly positive. Since all the entries ofN(1)are nonnegative,

N(1)a(1)6= 0, a contradiction. •

Corollary 1.5

Suppose that

M(1)

is primitive and

H

is an order ideal in

G_M

. If

e

belongs to

E(G_M)⁺

and

eH = 0

, then

e= 0

.

We think ofM as giving rise to a graph on thenpoints {1,2, . . . , n}(each of which will be called a state), with edges being labelled either by the exponents or the corresponding monomials. Thus ifx^w appears in the Laurent polynomialM_i,j position, there is an edge joiningitojwith weightw. (We do not worry about multiplicities for now.) This will be called the (multiplicity-free) graph ofM.

Lemma 1.6

If

M(1)

is primitive, then there exist

w

in

Z^d

and a positive integer

k

such that

x^wM^−k

belongs to

E_b(G_M)

.

Proof. The conclusion amounts tox^wI ≤KM^l for some positive integerK, the ordering computed with respect to that on E(G_M). Form the graph ofM. Select a loop from 1to1 that contains every state in {1,2, . . . , n} at least once (this is of course possible, becauseM(1)is primitive). Letkbe the length of the path; so ifw is the sum of the weights along the loop,x^w appears in the(1,1)entry ofM^k. For any particular statei, we can obtain a loop of the same length by starting at the first occurrence ofiinstead of the first1. Since the resulting loop is a cyclic permutation of the original, it has the same sum of weights. This means that each diagonal entry ofM^kcontainsx^w; it follows immediately thatx^wI ≤KM^l, as desired.• Since everything remains the same for our immediate purposes if we replaceM byx^−wM^k, we may even assume that I ≤ KM (that is,0 ∈ LogM_i,i for alli). We will have to be a bit more careful about this when we come consider the invariants∆andΓof Krieger (our assumption for now is that they are the same).

Lemma 1.7

Suppose that

M(1)

is primitive. If

H

is a nonzero order ideal of

G_M

, then

A[ ˆM^±1]·H=G_M

and

A[ ˆM^±1]⁺·H⁺=G⁺_M.

Proof.The order ideal contains an element of the form[x^wE_j, k]for some integersjandk, and some lattice pointw. By multiplying by an element of the formax^−w(forainA⁺), we obtain[aE_j, k]. By multiplying by a power (positive or negative) ofM, we obtain anything of this form but with arbitraryˆ k. Finally, by primitivity ofM(1)and the convexity ofH, we can always findw^′andk^′(depending onj) so that for any statej,[x^w′E_j, k^′]belongs toH. Hence by applying suitable elements ofaand powers ofM, an arbitraryˆ element ofG⁺_M is attainable; this yields the second assertion and the first follows immediately. • Proposition 1.8

Suppose that

M(1)

is primitive. Let

H

be a nonzero order ideal of

G_M

, and let

e

be an element of

E(G_M)

such that

eH = 000

. Then

e

is zero.

Proof. Select [x^wE_j, k]inH. ApplyM using the identity[M a, k+ 1] = [a, k]. From the convexity of H together with the primitivity ofM(1), we may findk^′, together with lattice pointsw_j such that for all j = 1,2, . . . , n, [x^wjE_j, k^′]belongs toH. Writee = ˆM^sNˆ. AsMˆ is an automorphism, we must have Nˆ[x^wjE_j, k^′] = 000for allj. Thusx^wjMⁿN E_j are all zero, and this obviously forcesMⁿN = 000. Hencee

is zero. •

Proposition 1.9

Suppose that

M(1)

is primitive. If

H

is an order ideal in

G_M

, then

E_b(G_M) = E_b(H)

.

Proof. We first show thatE_b(H) is the order ideal ofE(G_M) generated by the identity. By definition, E_b(H)is a subring ofE(G_M). Suppose thatebelongs toE(G_M)ande(H⁺)⊆H⁺; we wish to show that e(G⁺_M)⊆G⁺_M. This follows from Lemma 1.7. Thus the relative ordering onE_b(H)agrees with the natural ordering.

Since the identity element ofE_b(H)is automatically an order unit for it,E_b(H)is directed. Finally, suppose thate^′≤ewhereeande^′are positive elements ofE(G_M)andebelongs toE_b(H). Ase(H⁺)⊆ H⁺andH is an order ideal, it easily follows thate^′(H⁺) ⊆H⁺, so thate(H)⊆H. Hencee^′belongs to E(H); bute^′≤KI_Hfor someK(since the same inequality holds fore), so thate^′belongs toE_b(H).

HenceE_b(H)is an order ideal ofE(G_M)and has the identity as an order unit. However, by definition E_b(G_M)is the order ideal generated by the identity. So the two must be equal. • Now we show thatE_b(G_M)is a shift invariant forM. Recall that ifRis a (unital) partially ordered commutative ring, andMandM^′are square matrices with entries fromR⁺, then we say that they are(lagl) shift equivalent(overR⁺) if there exist rectangular matricesRandSwith entries fromR⁺such that

M R=RM^′ SM =M^′S RS=M^l SR= (M^′)^l.

If all the matrices involved have entries inRbut not necessarily in the positive cone, then we sayM and M^′arealgebraically shift equivalent(overR).

The reasonG_M itself isnota shift invariant is that it depends on the choice ofA, that is, on the number of variables, and how they are labelled. Let B be a subgroup ofZ^d, and suppose that all the entries of M have all of their exponents lying inB. LetA0 denote the subring (ifA = Z[x^±1_i ]) or subalgebra (if A =R[x^±1_i ]) generated byB. We say thatM isdefined overA0. We may defineG_M,0by replacingAⁿ withAⁿ₀ throughout (1). Then it is immediate thatG_M is naturally isomorphic (in all possible ways) with the tensor product of orderedA₀-modules,G_M,0⊗A0 A.

Lemma 1.10

Under these conditions,

E_b(G_M) =E_b(G_M,0).

Proof: SelectbinG⁺_M,0, and formH0, the order ideal generated bybtherein. We claim thatH is also an order ideal inG_M. WriteA = F[B1](giving the nameB1to the standard copy ofZ^d) andA0 = F[B], whereF is either the integers or the reals. LetT be a transversal ofB inB1; that is,T is a subset ofB1

such thatB =∪t∈T(t+B)and for allt6=t^′inT,t−t^′does not belong toB. We may assume that zero belongs toT. Obviously,A=⊕t∈Tx^tA0. Since the coefficients of the entries ofM all lie inA0, we have that for allt,M((x^tA₀)ⁿ)⊆(x^tA₀)ⁿ. It easily follows thatG_Mdecomposes as⊕t∈Tx^tG_M,0, as ordered A₀[ ˆM^±1]-modules. Moreover, each summand is an order ideal inG_M, so thatH (being an order ideal in the summand corresponding tot = 0) is also an order ideal. (Order ideals in order ideals of a dimension group are themselves order ideals in the big dimension group.)

Next, we observe that ifG = ⊕G_i, a direct sum of partially ordered (directed) abelian groups with the coordinatewise ordering on G, ande : G → Gis a positive endomorphism such thate ≤ KI_G (as endomorphisms), then for eachi,e(G_i) ⊆G_i. To see this, selectginG⁺_i . Thene(g) ≤Kg, so thate(g) belongs to the order ideal generated byg; this obviously is contained inG_i. SinceG_iis directed, it follows thate(G_i)⊆G_i.

Hence ifeis inE_b(G_M), for allt,e(x^tG_M,0) ⊆ x^tG_M,0. We have an order-preserving ring homo- morphism,∆ : E_b(G_M,0) →E_b(G_M), by permittingeto commute with eachx^t. By Proposition 1.8, an element ofE_b(G_M)is determined by its effect on a nonzero order ideal. Hence the map is onto (since these

endomorphisms must commute with elements ofA). •

2. A brief look atE_b(G_M)as a shift invariant

Suppose thatM andM^′are matrices with entries fromA⁺(a common Laurent polynomial ring) and they are shift equivalent; by enlarging the ring we may assume that the entries in the implementing matricesRand Sare also inA(this is not really necessary—a result in [PT] asserts that the equivalence can be implemented by matrices with entries inA⁺).

Proposition 2.1

If

M

and

M^′

are defined over a common Laurent polynomial ring

A

, and are shift equivalent (with the shift equivalence implemented over

A

), then the shift equivalence induces an order-isomorphism of ordered

A

-algebras,

E(G_M)→E(G_M^′)

, and an isomorphism of ordered rings

E_b(G_M)→E_b(G_M^′)

.

Proof.The equationM R=RM^′induces an order-preservingA-module homomorphism,Rˆ :G_M^′→G_M by means of [a, k]_M^′ 7→ [Ra, k]_M. It is a triviality to check that MˆRˆ = ˆRMˆ^′. Similarly, S induces Sˆ :G_M →G_M^′, that also intertwinesMˆ^′andMˆ. In general, having two such intertwining homomorphisms is not sufficient to obtain a ring homomorphism, either E(G_M) → E(G_M^′) or between their bounded subrings (examples exist in the case thatd= 0). However, we also see fromRS =M^landSR = (M^′)^l, thatRˆSˆ = ˆM^l andSˆRˆ = (Mˆ^′)^l. Defineφ_R : E(G_M^′) → E(G_M)as follows. Picke^′ inE(G_M^′)and denoteφ_R(e^′)bye. ForhinG_M, define

e(h) = ( ˆM)^−lReˆ ^′( ˆSh).

The intertwining relations guarantee thate(h) = ( ˆR)e^′³

S( ˆˆ M)^−lh´

, as well. The so-definedeis clearly linear. It commutes with the actions ofAandMˆ (and thus withMˆ⁻¹), because of the following identities:

e(aMˆ^th) = ˆM^−lReˆ ^′³

Sˆ·a·Mˆ^th´

= ˆM^−lReˆ ^′³

aMˆ^′tShˆ ´

= ˆM^−lRˆ·a·Mˆ^′te^′( ˆSh)

=aMˆ^′te( ˆSh)

Ife^′≥000, then it follows thatφ_R(e^′)is also positive. Soφ_R(e^′)is at least well-defined. We check thatφ_R is a ring homomorphism.

φ_R(e^′₁◦e^′₂)(h) = ˆM^−lR(eˆ ^′₁◦e^′₂)( ˆSh)

= ˆR(e^′₁◦e^′₂)( ˆSMˆ^−lh)

=φ_R(e^′₁)h

Reˆ ^′₂( ˆSMˆ^−lh)i

= ˆRh

SˆMˆ^−lReˆ ^′₂( ˆSMˆ^−lh)i

= ˆRe^′₁³

e^′₂( ˆSMˆ^−lh)´

=φ_R(e^′₁◦e^′₂)(h).

Hence under the assumptionsM R=RM^′,SM =M^′S, andSR = (M^′)^l, we deduce thatφ_Ris an order-preservingA-module ring homomorphism that intertwines the action of the original pair of matrices.

One definesφ_S in a similar fashion, and a five-line computation reveals that they are mutually inverse.

It is routine to verify that the bounded subrings are mapped isomorphically to each other under these

isomorphisms. •

Beginning with shift equivalentM andM^′, find a Laurent polynomial ring over which they and the implementing matrices are all defined. We have just obtained a pair of natural inverse ring isomorphisms between the rings of endomorphisms (after enlarging the polynomial rings). These isomorphisms induce an isomorphism on the bounded subrings; however, the latter are independent of the choice of coefficient ring.

So the bounded subring is a shift invariant. (In fact, a little more is true—if the first three equations hold, we obtain a map induced byφ_Rfrom the bounded subring corresponding toM^′to that corresponding toM.) Example 2.2

Zero variables.

Suppose thatd = 0, so thatM = M(1) = M₀is a matrix of constants with entries from eitherZorR.

Assume the former, and thatM0is primitive. ThenG_M0is simply Krieger’s dimension group, and it is simple (as a dimension group) with a unique trace. LetvinR^1×nbe the unique (up to positive scalar multiple) strictly positive left eigenvector ofM0, with corresponding eigenvalueρ, which is of course the spectral radius. The unique traceV :G_M →Ris determined viaV[c, k] =v·c/ρ^k. ThenG⁺_M\ {000}=V⁻¹((0,∞)). IfNis a matrix commuting with(M0), thenVNˆ =λ(N)V, whereλ(N)is the eigenvalue ofN whose eigenvector isv. It follows easily thatE(G_M0) =E_b(G_M0). (This equality can only occur ifd= 0, or other equally degenerate situations.)

ThusE_b(G_M0) =CZ(M₀)[M₀⁻¹]. This is a finer shift invariant (overZ) thanZ[1/ρ]studied in [BMT], but not so fine as the complete invariant (whend= 0) which isG_M0as a module overE_b(G_M0).

For example, letaandbbe positive integers. Set M₀=

·a 8b b a

¸

M₀^′ =

· a 4b 2b a

¸ .

Both matrices have ρ = a+ 2b√

2. The centralizer ofM0 is the centralizer of h0 8

1 0

i

(subtractatimes the identity and divide byb); this is the companion matrix for the polynomialx²−8. HenceCZ(M0) ∼= Z[2√

2], and thusE_b(G_M0)∼=Z[2√

2][(a+ 2b√

2)⁻¹](the isomorphisms are given by the effect on the left eigenvector, or the functionλdefined earlier). On the other hand, the centralizer ofM₀^′ is that of

h0 2 1 0

i . ThusE_b(G_M^′

0)∼=Z[√

2][(a+ 2b√

2)⁻¹]. It is straightforward to check that the two bounded endomorphism rings are isomorphic if and only if

(∗) Z[2√

2][(a+ 2b√

2)⁻¹] =Z[√

2][(a+ 2b√ 2)⁻¹]

(note the equality). This will occur if and only if there exists a positive integerkso that(a+ 2b√ 2)^k√

2 = c+ 2d√

2for some integerscandd. On taking norms, this would imply2(a²−8b²)^k =c²−8d². Hence2 dividesc, so4divides the right side. Thus2dividesa². Conversely, ifais even,ρ²= 2(aρ−2a²−4b²), so that invertibility ofρentails invertibility of2and thus (∗) holds.

We have deduced that (∗) holds if and only ifais even. However,Z[√

2]is a principal ideal domain, soZ[√

2][(a+ 2b√

2)⁻¹]is as well. Hence, with very little effort, we obtain thatM0is shift equivalent to M₀^′if and only ifais even.

On the other hand, if

M0=

·4 3 5 4

¸

M₀^′ =

·4 15 1 4

¸ , we have that the bounded endomorphism rings of both matrices areZ[√

15](as4 +√

15 is a unit). The matrices correspond to the two ideal classes ofZ[√

15], and so are not shift equivalent (this is easy to see directly—as the matrices are invertible, shift equivalence is the same as conjugacy via GL(2,Z)).

If we add the identity to both matrices, the bounded endomorphism ring is thenZ[√

15][(5 +√ 15)⁻¹].

This is a principal ideal domain (as the ideal inZ[√

15]that contains5and√

15represents the non-trivial

ideal class). Hence in this case the matrices are shift equivalent. •

Example 2.3

FOG examples (two variables).

Now letd= 2; instead ofx1,x2, we writex,y. We consider a pair of matrices suggested by Jack Wagoner and Mike Boyle in connection with FOG (“finite order generation”) and other murky conjectures, most of which have been resolved:

M =



x 1 0 0 y 1 1 0 1



 M^′=



y 1 0 0 x 1 1 0 1



.

The second matrix is obtained from the first by interchangingxandy. These matrices arise from the graphs:

• •

ր ց ր ց

°y• ←− •

°x •

°x ←− •

°y

(The unlabelled arrows have weight1 = x⁰y⁰.) The automorphism of A = Z[x^±1, y^±1]given by inter- changingx andy induces an order isomorphismG_M → G_M^′, and correspondingly between the rings of endomorphisms, and the rings of bounded endomorphisms. These do not implement module isomorphisms, because they do not (in the first two cases) commute with the action ofA. Although the matrices are conjugate via an elementary matrix of GL(3,A), they are not shift equivalent; in fact they are not even finitely equiva- lent, a fact that was discovered independently by Marcus and Tuncel [MT2] using quite general techniques and by me (using completely ad hoc methods).

By examining the left eigenvector for the large eigenvalue function ofM, it is routine to check that in factM is conjugate (i.e., using GL(3,A)) to the companion matrix for its characteristic polynomial. Thus C_A(M) =A[M], the polynomial algebra (overA) inM. SoE(G_M) =A[M^±1]—but the bounded subring, E_b(G_M)is more difficult to compute.

We shall have more to say about this example in section 7. •

Now we prove a result which is related to the converse of Proposition 2.1. This is already known.

Proposition 2.4

If

M

and

M^′

are defined over a common Laurent polynomial ring (algebra)

A

, then any order isomorphism between

G_M

and

G_M^′ asA[ ˆM]-modules

is induced by a shift equivalence between

M

and

M^′

, up to a power of

M^ˆ

.

Proof. Supposeφ : G_M → G_M^′ is a positiveA-module homomorphism satisfyingφMˆ = ˆM^′φ. Then there exists an integerktogether with positive columnsa_j inA^n′ such that for allj= 1,2, . . . , n,

φ([E_j,1]) = [a_j, k].

Define then^′×nmatrixR0by setting its jth column to bea_j. All the entries of R0 lie inA⁺, and we observe that as φintertwines the shift(s) and is an A-module homomorphism, φ has the same effect on G_M as applyingR0to the equivalence classes and following this withMˆ^(k−1). In particular,Rˆ0is well- defined and satisfiesRˆ0Mˆ = ˆM^′Rˆ0. It follows immediately that(R0M −M^′R0)Mⁿ = 000. If we replace R0 by R1 = R0Mⁿ, then we see thatR1has all its entries inA⁺, intertwinesM andM^′, and satisfies Rˆ=φMˆ^n−k+1.

Similarly, ifψ :G_M^′ →G_M is positive and intertwinesMˆ andMˆ^′, there exists a rectangular matrix S with entries from A⁺ that intertwines M andM^′and implements ψ, up to a power ofMˆ orMˆ^′. By

multiplying on or the other ofR1orSby a power ofMwe may assume that the power ofMˆ that indicates the perturbation fromφandψis the same; sayRˆ1=φMˆ^landSˆ= ˆM^lψ.

Now suppose thatφψ= ˆM^tfor some integert. ThenSˆRˆ1= ˆM^t+2l. As before,(SR1−M^t+2l)Mⁿ= 000. ReplacingR1byR=R1Mⁿ, we obtain thatSR=M^t+2l+n, andRis positive and still intertwinesM andM^′. By incorporating another power ofM^′ intoS, we obtain that ifφψ= ( ˆM^′)^t, thenRS is also a

power ofM^′. In particular, this yields a shift equivalence. •

Remark. 2. If we let A be an arbitrary commutative unital ring andM an arbitrary square matrix (see Remark 1), then the unordered versions of Proposition 2.1 and Proposition 2.4 still hold, where we now use algebraic shift equivalence.

In view of Proposition 2.1 and Proposition 2.4, what is the point of discussingE_b(G_M) (especially since it generally is more difficult to compute thanG_M)? For determining the pure traces on the order ideals, it is essential (the trace space ofE(G_M)is inadequate for this purpose). Moreover, the preceding depends on the choice ofA. There is a close relationship betweenE_b(G_M)andE(G_M)ifM is defined over the minimal possibleA.

Krieger [Kr] has defined two invariants for shift equivalence, which amount to the following (where tr denotes trace). Iff = P

λ_wx^w is a polynomial indvariables expressed in monomial notation, then Logf =©

w∈Z^d¯¯λ_w6= 0ª .

Γ(M) =h [∞ j=1

Log trM^j i

∆(M) = [∞ j=1

¡Log trM^j −Log trM^j¢ .

The angle bracketsh iindicate the group generated by the contents. If S andT are subsets ofZ^d, then S−T ={s−t|s∈S, t∈T}. Note that∆(M)is already a group.

Lemma 2.5

If

M(1)

is primitive, then

Γ(M) =h©

w∈Z^d¯¯ x^wM^−l∈E_b(G_M)

for some

l∈Nª i

∆(M) =h© w−w0

¯¯x^wM^−l, x^w0M^−l ∈E_b(G_M)

for some

l∈Nª i.

Proof: Selectz in Log trM^l. This means thatzis the total weight of a loop of lengthlwhose initial and terminal state¹ isj for somej. There exists a loop of lengthkthat passes through every state (asM(1) is primitive). Let its total weight be denoted w. In this latter loop, insert the original loop immediately adjacent to an occurrence ofj. This creates a loop of lengthk+lcontaining every state, of weightz+w.

As the loop of weight wcontains every state, wbelongs to Log ¡ M^k¢

ii for alli = 1,2, . . . , n and thus x^wI ≤ M^k for some positive integerK (as endomorphisms ofG_M. Thusx^wMˆ^−k belongs toE_b(G_M).

Similarly,x^z+wMˆ^−(k+l)belongs toE_b(G_M). Hencez=z+w−wbelongs to the right side.

Conversely, ifx^wMˆ^−l is a member ofE_b(G_M), thenx^wI[E_j,1]≤KMˆ^l[E_j,1]for someK and all j. Hence there exists an integerN so thatM^N ¡

KM^l−x^wI¢

E_j has all of its entries inA⁺. This simply means that all the entries of the matrixKM^l+N −x^wM^N belong toA⁺. Taking a diagonal entry, we see that ifubelongs to Log¡

M^N¢

iifor somei, thenu+wbelongs to Log ¡

M^l+N¢

ii. Hencew=u+w−u expresseswas the difference of two elements ofΓ(M).

The argument for∆(M)is parallel. •

1We use ‘vertex’ in another context.