9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # SMALL POLYNOMIAL MATRIX PRESENTATIONS OF NONNEGATIVE MATRICES

SMALL POLYNOMIAL MATRIX PRESENTATIONS OF NONNEGATIVE MATRICES

MIKE BOYLE AND DOUGLAS LIND Abstract. We investigate the use of polynomial matrices to give ef?cient presentations of nonnegative matrices exhibiting prescribed spectral and algebraic behavior.

1. Introduction Let S be a unital subring of the real numbers R, and S+ denote the set of its nonnegative elements. The inverse spectral problem for nonnegative matrices asks for necessary and suf?cient conditions on an n-tuple of complex numbers for it to be the spectrum of an n × n matrix over S+ . When S = R various ingenious and fascinating partial results are known (see results, discussions, and references in [2, 12, 20, 21] and more recently [15, 16]). There is a clear conjectural characterization in [6] of which lists of nonzero complex numbers can be the nonzero part of the spectrum of a matrix over S+ . This conjecture has been veri?ed for many S, including the main cases S = R [6] and S = Z [13], but the problem of determining reasonable upper bounds for the minimum size of a matrix with a given nonzero spectrum is still out of reach, even for S = R. The use of matrices whose entries are polynomials with nonnegative coef?cients to represent nonnegative matrices goes back at least to the original work of Shannon on information theory [24, §1]. Such matrices can provide much more compact presentations of nonnegative matrices exhibiting prescribed phenomena, as well as give a more amenable and natural algebraic framework [4], of particular value in symbolic dynamics [5]. Their use focuses attention naturally on asymptotic behavior having a comprehensible theory. In particular, it seems to us that the problem of determining the minimum size polynomial matrix presenting a given nonzero spectrum is likely to have a satisfactory and eventually accessible solution, which may also be useful for bounding the size of nonpolynomial matrix presentations. In this paper we give realization results, constructing polynomial matrices of small size presenting nonnegative matrices satisfying certain spectral and algebraic constraints. Perhaps the main contribution is to show how certain geometrical

Date: July 6, 2001. 2000 Mathematics Subject Classi?cation. Primary: 15A48, 37B10; Secondary: 15A29, 15A18. Key words and phrases. Nonnegative matrix, polynomial matrix, spectrum, inverse spectral problem, dimension group, Perron. The ?rst author thanks the Milliman Endowment of the University of Washington for partial support of this research.

1

SMALL POLYNOMIAL MATRIX PRESENTATIONS

2

ideas interact with polynomial matrices. We hope that the combined geometricpolynomial viewpoint may be useful in approaching deeper problems. For example, the minimum size problem and the Generalized Spectral Conjecture [5, 7] may be approached in terms of turning the epimorphisms of Theorems 5.1 and 8.8 into isomorphisms. For the statement of our speci?c results, recall a matrix is primitive if it is nonnegative and some power is strictly positive. The inverse spectral problem for nonnegative matrices reduces to the inverse spectral problem for primitive matrices [6]. The Perron Theorem shows that one necessary condition on a list of complex numbers for it to be the spectrum of a primitive matrix is that there be one positive element, called the spectral radius of , that is strictly larger than the absolute value of each of the other elements. If one further requires that be the spectrum of a primitive matrix over S, then must also be S-algebraic, that is, the monic polynomial whose roots are the elements of must have coef?cients in S. In Section 3 we show how to associate naturally to each matrix with entries in S+ [t ] a corresponding matrix with entries in S+ . Handelman [9] showed that an S-algebraic list satisfying the Perron condition above is contained in the spectrum of a primitive matrix over S+ with the same spectral radius corresponding to a 1 × 1 polynomial matrix if and only if no other element of is a positive real number. After developing some machinery for polynomial matrices in Section 3 and Section 4, we show that every S-algebraic satisfying the Perron condition is contained in the spectrum of a primitive matrix with the same spectral radius coming from a 2 × 2 polynomial matrix over S+ [t ]. This answers a question raised in [4, §5.9] and generalizes a result of Perrin (see Remark 6.7). The proof, combined with a simple geometrical observation, allows us to recover Handelman’s original result in Section 7. In Section 8 we re?ne our results for nonzero spectra by ?nding small polynomial matrix presentations for actions on appropriate S-modules. We thank Robert Mouat for suggesting an important simpli?cation in the basic construction of Section 3.

2. Preliminaries We collect here some convenient notation and terminology. Let S denote an arbitrary unital subring of the reals R, so that S is a subring containing 1. Note that S is either the discrete subring Z of integers or is dense in R. Denote by K the quotient ?eld of S. We let S+ = S ∩ [0, ∞) denote the nonnegative semiring of S, and S++ = S ∩ (0, ∞) be the set of strictly positive elements of S. The ring of polynomials with coef?cients in S is denoted by S[t ], and the semiring of polynomials with coef?cients in S+ by S+ [t ]. A list is a collection of complex numbers where multiplicity matters but order does not. We use the notation = λ1 , . . . , λn for a list, so that 1, 1, 2 = 2, 1, 1 = 1, 2 . A list is contained in another list ′ , in symbols ? ′ , if for every λ ∈ the multiplicity of λ in is less than or equal to its multiplicity in ′ .

SMALL POLYNOMIAL MATRIX PRESENTATIONS

3

The spectral radius of a list is the number ρ( ) = maxλ∈ |λ|. A list is Perron if ρ( ) > 0 and there is a λ ∈ of multiplicity one such that λ > |?| for all other elements ? ∈ . In particular, if is Perron then ρ( ) ∈ . Given a list , let f (t) = λ∈ (t ? λ) denote the monic polynomial whose roots are the elements of , with appropriate multiplicity. For example, if = is S-algebraic if 1, 1, 2 then f (t) = (t ? 1)2 (t ? 2). We say that a list f (t) ∈ S[t ]. Matrices are assumed to be square. A matrix is called nonnegative (respectively, positive) if all of its entries are nonnegative (respectively, positive) real numbers. If A is a real matrix, let sp(A) denote the list of (complex) eigenvalues of A and sp× (A) the list of nonzero eigenvalues of A. The spectral radius ρ(A) of A is then just the spectral radius of the list sp(A). We say that A is Perron if sp(A) is Perron. Thus a primitive matrix is always Perron.

3. The ?-construction Let P (t) = [pij (t)] be an r × r matrix over S[t ]. We construct a directed graph ?P (t) whose edges are labeled by elements from S. The adjacency matrix of ?P (t) is denoted by P (t)? , which has entries in S. The process of passing from P (t) to P (t)? is called the ?-construction. To describe ?P (t) , let d(j ) = max1 i r deg(pij ). The vertices of ?P (t) are symbols jk , where 1 j r and 0 k d(j ). For 1 j r and 1 k d(j ) put an edge labeled 1 from jk to jk ?1 . For each monomial at k in pij (t) put an edge labeled a from i0 to jk . This completes the construction of ?P (t) . Example 3.1. Let S = Z and P (t) = 2t + 3 4t 2 + 5t + 6 . 7 8t 2 + 9

The graph ?P (t) is shown in Figure 1.

2 11 4 22 1 21 8 5 1 1 6 20 10 7 9 3

Figure 1. The graph ?P (t) for Example 3.1

SMALL POLYNOMIAL MATRIX PRESENTATIONS

4

Remarks 3.2. (1) If A is a matrix over S, then A? = A. Thus every matrix over S arises from the ?-construction. (2) The ?-construction can be viewed as a generalization of the companion matrix of a polynomial. For if P (t) = [p(t)] is 1 × 1 and m = deg(p), then P (t)? is the companion matrix of t m t ? p(t ?1 ) . (3) Our construction of P (t)? from P (t) is a variation of the ? construction of an S matrix from tP (t) in [14] (where S = Z). In particular, det[I ? t {P (t)? }] = det[I ? t {tP (t)}? ] .

Using the vertex ordering 1 1 , 10 , 22 , 21 , 20 , the adjacency matrix of ?P (t) takes the form ? ? 0 1 0 0 0 ?2 3 4 5 6 ? ? ? ? ?. 0 0 0 1 0 P (t) = ? ? ? ?0 0 0 0 1? 0 7 8 0 9

The ?-construction generally yields smaller matrices than the ?-construction, and so is better suited for our purposes. If A is a matrix over the complex numbers C, then the polynomial det [I ? tA] =

λ∈sp× (A)

(1 ? λt)

determines the list sp× (A) of nonzero eigenvalues of A. The following result, essentially contained in [3, Thm. 1.7] (see also [4, §5.3]), shows that for A = P (t)? this polynomial can be readily computed from the smaller matrix P (t). Proposition 3.3. If P (t) is a polynomial matrix over S[t ], then (3.1) det I ? t {P (t)? } = det I ? t P (t) .

Proof. Let P (t) = [pij (t)] be r × r , and Sr be the permutation group of {1, . . . , r }. Let V = {jk : 1 j r, 0 k d(j )} be the vertex set of ?P (t) , and S(V) denote the permutation group of V. Denote the Kronecker function by δij . Consider the expansion of det I ? t {P (t)? } using permutations in S(V). We ?rst observe that any π ∈ S(V) contributing a nonzero product (3.2)

v ∈V

δv,πv ? t {P (t)? v,πv }

to this expansion must have a special form. For 1 i r we have that π(i0 ) = jk for some 1 j r and 0 k d(j ). Observe that for k 1 the nonzero entries in the jk th row of I ? t {P (t)? } can occur only in columns jk or jk ?1 . Since π(i0 ) = jk , we must then have π(jk ) = jk ?1 . We then see inductively that π(jk ?1 ) = jk ?2 , . . . , π(j1 ) = j0 . An analogous argument for predecessors of jk shows in turn that π(jk +1 ) = jk +1 , . . . , π(jd(j ) ) = jd(j ) . If ak denotes the coef?cient of t k in pij (t), then the subproduct of (3.2) over the subset {i0 } ∪ {j? : 1 ? d(j )} ? V is then (?1)k (?ak t k +1 ).

SMALL POLYNOMIAL MATRIX PRESENTATIONS

5

Let E(σ ) = {πσ,κ : κ ∈ K } ? S(V). Clearly the E(σ ) are pairwise disjoint for σ ∈ Sr . Our previous observations show that σ ∈Sr E(σ ) contains all permutations in S(V) that could possibly contribute a nonzero term to the expansion of det [I ? t {P (t)? }]. Fix σ ∈ Sr . The expansion of

r

′ ) = j ′ , then j ′ = j . Hence π This observation also shows that if i ′ = i and π(i0 k′ induces a permutation σ ∈ Sr de?ned by σ (i) = j whenever π(i0 ) = jk . Clearly π is determined by σ and the choices of k with 0 k d(j ). Conversely, each σ ∈ Sr and choice of k ’s determine a relevant π . To formalize these observations, de?ne K to be the set of all functions κ : {1, . . . , r } → Z+ such that 0 κ(j ) d(j ). For each σ ∈ Sr and κ ∈ K de?ne ? ? ?(σj )κ(σj ) for k = 0, πσ,κ (jk ) = jk ?1 for 1 k κ(j ), ? ? jk for κ(j ) < k d(j ).

δj,σj ? t pj,σj (t)

j =1

contains monomials parameterized by K , where κ ∈ K determines which monomial from each polynomial to select to form a product. As observed above, the same monomials appear in the expansion of (sgn πσ,κ )

κ ∈K v ∈V

δv,πσ,κ v ? t {P (t)? v,πσ,κ v } , increase over those

r κ(j ) . Since the cycle lengths of π but multiplied by j σ,κ =1 (?1) r in σ by a total amount j =1 κ(j ), it follows that r

(sgn πσ,κ )

j =1

(?1)κ(j ) = sgn σ.

Hence

r

(sgn πσ,κ )

κ ∈K v ∈V

δv,πσ,κ v ? t {P (t)? v,πσ,κ v } = (sgn σ )

j =1

δj,σj ? t pj,σj (t) .

Summing over σ ∈ Sr establishes the result. Example 3.4. If P (t) is the polynomial matrix in Example 3.1, the reader can verify that det [I ? t P (t)] = det[I ? t {P (t)? }] = 1 ? 12t ? 17t 2 ? 25t 3 ? 4t 4 + 16t 5 . Remark 3.5. Let ? be a directed graph. Borrowing terminology from [3], we call a subset R of vertices of ? a rome if ? has no cycle disjoint from R . Alternatively, R is a rome if every suf?ciently long path in ? must pass through R , so that all roads lead to R . A rome is effectively a cross-section for the path structure of ? .

SMALL POLYNOMIAL MATRIX PRESENTATIONS

6

For example, if P (t) is an r × r polynomial matrix, then ?P (t) has a rome R = {10 , 20 , . . . , r0 } of size r . Conversely, suppose that ? is a directed graph whose edges e are labeled by elements wt (e) ∈ S. Suppose that ? has a rome R of size r . For each ordered pair (i, j ) of vertices in R , let ij denote the (?nite) set of paths ω from i to j that do not otherwise contain a vertex in R . For each such ω de?ne its length ?(ω) to be the number of edges, and its weight to be wt(ω) = e∈ω wt(e) ∈ S. Let pij (t) =

ω∈ ij

wt(ω)t ?(ω)?1 ∈ S[t ],

and P = [pij (t)]. If A is the adjacency matrix of ? , then A and P (t)? may be quite different. However, an argument similar to that in Proposition 3.3 shows that det [I ? tA] = det I ? t {P (t)? } = det [I ? t P (t)]. Thus our results amount to ?nding graphs with prescribed spectral behavior having small romes.

4. Manufacturing polynomial matrices Let A be a d × d nonsingular matrix over S, and K be the quotient ?eld of S. It is convenient to use row vectors, and therefore to write the action of matrices on the right. Suppose we have r vectors x1 , . . . , xr ∈ Sd whose images under powers of A span Kd . Further suppose that each image xj A can be written as an S-linear combination of the xi A?k for 1 i r and k 0. Then there are polynomials pij (t) ∈ S[t ] such that x1 A = x1 p11 (A?1 ) + x2 p12 (A?1 ) + · · · + xr p1r (A?1 ), . . . xr A = x1 pr 1 (A?1 ) + x2 pr 2 (A?1 ) + · · · + xr prr (A?1 ). Let P (t) = [pij (t)] be the resulting r × r polynomial matrix. Form P (t)? , say of size n. De?ne a K-linear map ψ : Kn → Kd by ψ(jk ) = xj A?k . It is routine to check that the following diagram commutes. P (t)? Kn ? ? ? ? → Kn ? ? ? ? ψ ψ ? ? → Kd Kd ? A Since the xi generate Kd under powers of A, it follows that ψ is surjective. This method provides the algebraic machinery to obtain given matrices A as quotients of ?-constructions. The next section shows how to use positivity to control the spectral radius as well as obtain primitivity of P (t)? .

SMALL POLYNOMIAL MATRIX PRESENTATIONS

7

5. Small polynomial matrices In this section we realize a given Perron list as a subset of the spectrum of a primitive nonnegative matrix having the same spectral radius obtained via the ?construction from a polynomial matrix that is either 1 × 1 or 2 × 2. Theorem 5.1. Let be an S-algebraic Perron list of nonzero complex numbers. Then there is a polynomial matrix P (t) over S+ [t ] of size at most two such that P (t)? is primitive, ρ( ) = ρ P (t)? , and ? sp× P (t)? . Proof. If = {λ} for some λ ∈ S++ , then let P (t) be the 1 × 1 constant matrix [λ]. Let d denote the cardinality of , which we may now assume is at least 2. Put λ = ρ( ) ∈ , f (t) = ?∈ (t ? ?) ∈ S[t ], and let C be the d × d companion matrix of f (t). If ej denotes the j th standard basis vector, then ej C = ej +1 for 1 j d ? 1. Let v be a left-eigenvector for C corresponding to λ and V = Rv. Denote by W the direct sum of the generalized eigenspaces corresponding to the other elements / W for 1 j d , of , and let πV denote projection to V along W . Note that ej ∈ since W is a C -invariant proper subspace and each ej generates Rd under (positive and negative) powers of C . We identify R with Rv via t ? t v, and think of πV as having range R. Replacing v with ?v if necessary, we may assume that πV (e1 ) > 0, and hence πV (ej ) = πV (e1 C j ?1 ) = λj ?1 πV (e1 ) > 0 for 1 j d . We claim that v, v ? e1 , . . . , v ? ed ?1 are linearly independent. For if not, then v would be a linear combination v = v1 e1 + · · · + vd ?1 ed ?1 . Taking d th coordinates of vC = λv shows that vd ?1 = 0, and then taking (d ? 1)st coordinates shows in turn that vd ?2 = 0, and so on, contradicting v = 0 and proving our claim. Hence the R+ -cone generated by v, v ? e1 , . . . , v ? ed ?1 has nonempty interior. This interior must therefore contain some u ∈ Sd of the form u = c0 v + c1 (v ? e1 ) + · · · + cd ?1 (v ? ed ?1 ), where cj > 0 for 0 v= j d ? 1 and in addition πV (u) > 0. Thus

1 u + c1 e1 + · · · + cd ?1 ed ?1 c0 + c1 + · · · + cd ?1

lies in the interior of the R+ -cone K generated by e1 , . . . , ed ?1 and u, and in addition K ∩ W = {0}. Our goal is to show that for all suf?ciently large N there are elements aj , bj , a , and b in S++ such that ed C N = a1 e1 + · · · + ad ?1 ed ?1 + ad ed + a u (?) = a1 ed C ?d +1 + · · · + ad ?1 ed C ?1 + ad ed + a u, uC N = b1 e1 + · · · + bd ?1 ed ?1 + bd ed + bu = b1 ed C ?d +1 + · · · + bd ?1 ed C ?1 + bd ed + bu.

SMALL POLYNOMIAL MATRIX PRESENTATIONS

8

Suppose for now this goal has been met. Then applying C ?N +1 to both equations puts us into the situation described in Section 4, with r = 2, x1 = ed , x2 = u, and P (t) = a1 t N +d ?2 + a2 t N +d ?3 + · · · + ad ?1 t N + ad t N ?1 at N ?1 . b1 t N +d ?2 + b2 t N +d ?3 + · · · + bd ?1 t N + bd t N ?1 bt N ?1

The graph ?P (t) is strongly connected because aj , bj , a, b > 0. It also has period one since d ≥ 2 and gcd(N ? 1, N) = 1. Therefore P (t)? is primitive. The map ψ de?ned in Section 4 shows that C is a quotient of P (t)? , so that = sp(C) ? ρ P (t)? . The Perron eigenvector for P (t)? is sp× P (t)? , and hence ρ( ) mapped by ψ to a vector which is nonzero (it is a strictly positive combination of e1 , . . . , ed ?1 , and u) and which is therefore an eigenvector of C with eigenvalue ρ P (t)? . This completes the proof except for ρ P (t)? , proving that ρ( ) establishing (?). To prove that (?) holds for suf?ciently large N , we consider separately the cases S = Z and S dense in R. First suppose that S = Z. Since is Z-algebraic and | | = d 2, it follows that | ?∈ ?| = |f (0)| 1, and hence λ = ρ( ) > 1. Let L = Ze1 ⊕ · · · ⊕ Zed ?1 ⊕ Zu be the lattice generated by e1 , . . . , ed ?1 , u. Choose M large enough so that every translate of Q = [1, M ]d contains an element of L. Suppose that w ∈ Zd has the property that w ? Q is contained in the interior K ? of the cone K . Then w ? Q contains an element x = w ? q in L, say x = n1 e1 + · · · + nd ?1 ed ?1 + nu with nj , n ∈ Z. These coef?cients nj , n must then be in Z++ because x ∈ K ? and the representation of x as a linear combination of the linearly independent vectors e1 , . . . , ed ?1 , u is unique. Now q = w ? x ∈ Zd ∩ Q, and so q = q1 e1 + · · · + qd ed with all qj ∈ Z++ . Thus w = x + q = (n1 + q1 )e1 + · · · + (nd ?1 + qd ?1 )ed ?1 + qd ed + nu, where the coef?cient of each vector lies in Z++ . Since v is the dominant eigendirection, its eigenvalue λ > 1, and πV (ed ) > 0, πV (u) > 0, it follows that for all suf?ciently large N both ed C N ? Q and uC N ? Q are contained in K ? . By what we have just done, this shows that (?) is valid in the case S = Z. Finally, suppose that S is dense in R. Let KS denote the set of all elements in K of the form s1 e1 + · · · + sd ?1 ed ?1 + s u, where sj , s ∈ S++ . Clearly KS is dense in K . Let w denote any vector in Sd lying in the interior K ? of K . Then w ? (0, 1)d ∩ K ? is open and nonempty, and so contains some vector x = w ? q ∈ KS ? Sd . By de?nition, x has the form x = x1 e1 + · · · + xd ?1 ed ?1 + x u, where xj , x ∈ S++ . Then q = w ? x ∈ Sd ∩ (0, 1)d , so that q = q1 e1 + · · · + qd ed , where qj ∈ S++ . Hence w = x + q = (x1 + q1 )e1 + · · · + (xd ?1 + qd ?1 )ed ?1 + qd ed + x u, where each coef?cient lies in S++ . Since v is the dominant eigendirection and πV (ed ) > 0, πV (u) > 0, both ed C N and uC N are in K ? for all suf?ciently large N . By the above, we have established (?) when S is dense, and completed the proof.

SMALL POLYNOMIAL MATRIX PRESENTATIONS

9

6. Examples and remarks We illustrate how the ideas in the proof of Theorem 5.1 work in three concrete situations, and also make some general remarks. Example 6.1. Let S = Z and = 2, 1 . Then is an Z-algebraic Perron list with λ = ρ( ) = 2. Using the notation from the proof of Theorem 5.1, C= 0 1 , ?2 3 v = [?1 1], and W = R · [?2 1].

We pick u = v + (v ? e1 ) = [?3 2], so that πV (u) > 0 and v is in the interior K ? of the cone K generated by e1 and u. Here L = Ze1 + 2Ze2 , so we can let Q = [1, 2]2 . The minimal N for which both e2 C N ? Q and uC N ? Q are contained in K ? turns out to be N = 4. We compute e2 C 4 ? [1 1] = [?31 30] = 14[1 0] + 15[?3 2] ∈ L, and uC 4 ? [1 1] = [?19 16] = 5[1 0] + 8[?3 2] ∈ L. Continuing with the method of the proof, we have e2 C 4 = (14e1 + 15u) + (e1 + e2 ) = 15e1 + e2 + 15u, uC 4 = (5e1 + 8u) + (e1 + e2 ) = 6e1 + e2 + 8u. Hence e2 C = 15e1 C ?3 + e2 C ?3 + 15uC ?3 = e2 (15C ?4 + C ?3 ) + u(15C ?3 ), uC = 6e1 C ?3 + e2 C ?3 + 8uC ?3 = e2 (6C ?4 + C ?3 ) + u(8C ?3 ). From this we obtain P (t) = 15t 4 + t 3 15t 3 . 6t 4 + t 3 8t 3

Then P (t)? is a 9 × 9 primitive integral matrix whose characteristic polynomial is t 9 ? 9t 5 ? 15t 4 ? 7t + 30 = (t ? 2)(t ? 1)f (t), where f (t) is an irreducible polynomial of degree 7, all of whose roots have absolute value between 1.46 and 1.86. Thus P (t) satis?es our requirements. Example 6.2. Again let S = Z and put g(t) = t 3 + 3t 2 ? 15t ? 46. Denote the roots of g(t) by λ ? = 3.89167, ?1 ? = ?3.21417, and ?2 ? = ?3.67750. Then = λ, ?1 , ?2 is a Z-algebraic Perron list. The companion matrix C of g(t) turns out to have a positive left-eigenvector v corresponding to λ. Thus we can let u = e3 since v lies in the interior of the positive orthant K = R3 + . Hence we can use the manufacturing technique in Section 4 with r = 1 and the single vector x1 = e1 , yielding a 1 × 1 polynomial matrix. However, since ?1 and ?2 are negative and close in size to λ, it takes a large value of N to force e1 C N inside K . By direct computation we ?nd the smallest N which works is N = 49 and that

SMALL POLYNOMIAL MATRIX PRESENTATIONS

10

e1 C 49 = [a

b

c], where a = 36488554855989658309872537378, b = 11571239128278403776343659967, c = 67410400385366369466556470.

Hence e1 C = a e1 C ?48 + b e1 C ?47 + c e1 C ?46 , resulting in p(t) = at 48 + bt 47 + ct 46 . Then [p(t)]? is a 49 × 49 primitive integral matrix whose characteristic polynomial is g(t)h(t), where h(t) is an irreducible polynomial of degree 46 all of whose roots have absolute value between 3.709 and 3.8915 < λ and the bounds are optimal to the given accuracy. Example 6.3. For this example we use the dense unital subring S = Z[1/6]. Let = 1/2, 1/3 , an S-algebraic Perron list. Here C= 0 1 , ?1/6 5/6 v = [?1 3], and W = R · [?1 2].

We pick u = [?2 5], and let K be the R+ -cone generated by e1 and u. First notice that although uC = ?5/6 13/6 ∈ K ? ∩ S2 has coordinates in S and is an R++ -combination of e1 and u, it is not an S++ combination of e1 and u, since 13 1 e1 + u 30 30 is the unique representation of uC as a linear combination of e1 and u, and 1/30 ∈ / S. This dif?culty explains the necessity in our proof of getting S++ combinations close to the given vectors. Here both e2 C and uC are in K ? . We need to ?nd vectors a e1 + b u that are close to the given vectors, which is effectively a problem in Diophantine approximation of rationals by elements of S. For e2 C , we seek a, b ∈ S++ so that x = a e1 + b u = [a ? 2b 5b] is coordinatewise less than but close to e2 C = [?1/6 5/6]. Thus b < 1/6, so we pick b = 5/36. Then a < ?1/6 + 10/36 = 4/36 and we pick a = 3/36 = 1/12. Then 5 1 5 1 e2 C ? e1 ? u = e1 + e2 , 12 36 36 36 so that 5 5 1 ?1 C + +u . e2 C = e2 9 36 36 A similar calculation gives uC = uC = e2 1 ?1 1 C + 36 72 +u 93 . 216

SMALL POLYNOMIAL MATRIX PRESENTATIONS

11

? 1 5 5 t + ?9 36 36 ? ?. P (t) = ? ?1 1 93 ? t+ 36 72 216 Then P (t)? is a 3 × 3 primitive matrix over S+ whose eigenvalues are 1/2, 1/3, and ?19/72. Remark 6.4. The singleton case = λ in Theorem 5.1 was handled using a 1 × 1 matrix. With the single exception of the case S = Z and = 1 , a 2 × 2 polynomial matrix can also be found satisfying the desired conclusions. For if λ > 1 apply the proof to λ, 1 , and if λ < 1 apply it to λ, λ2 . If λ = 1 and S is dense, pick ? ∈ S ∩ (0, 1) and apply the proof to 1, ? . To discuss the exceptional case, suppose that A is an r × r primitive integral 1. The spectral radius of An matrix, where r 2. Then An > 0 for some n is bounded below by the minimum of the row sums of An , and hence by r . Thus ρ(A) = ρ(An )1/n r 1/n > 1. This shows that when S = Z and = 1 there cannot be a 2 × 2 polynomial matrix satisfying the conclusions of Theorem 5.1. Remark 6.5. The construction in the proof of Theorem 5.1 typically introduces additional nonzero spectrum. When S = Z there is a further restriction on a Zalgebraic Perron list that it be exactly the nonzero spectrum of a primitive integral matrix. De?ne tr ( n ) = λ∈ λn , and the nth net trace to be n tr ( d ), tr n ( ) = ? d

d |n

Hence we ?nd

?

where ? is the M?bius function. If there were a primitive integral matrix A with sp× (A) = , then tr n ( ) would count the number of orbits of least period n in an associated dynamical system (see [19, p. 348]). Hence a necessary (and easily checked) condition for there to be a primitive integral matrix A such that sp× (A) = is that tr n ( ) 0 for all n 1. Kim, Ormes, and Roush [13] have shown that this condition also suf?ces. Their remarkable proof uses, among other things, polynomial matrices to ?nd the required A. When S = Z, an obviously necessary condition replaces the net trace condition above: if tr n ( ) > 0 then tr kn ( ) > 0 for all k 1. The Spectral Conjecture in [6] states that when S = Z this condition is suf?cient for an S-algebraic Perron list to be the nonzero spectrum of a primitive matrix over S+ . The Spectral Conjecture was proven in [6] for the case S = R, and some other cases. Remark 6.6. There are constraints of Johnson-Loewy-London type [11, 20] which put lower bounds on the size of a polynomial matrix P (t) for which P (t)? realizes a given Perron list . For example, for S = Z, if tr 1 ( ) = n and ρ( ) < 2, then the size of P (t) must be at least n (otherwise a diagonal entry of P (t) would have a constant term 2 or greater, forcing ρ( ) ≥ 2). Without trying here to formulate these constraints carefully, it seems reasonable to us to expect that they may give nearly sharp bounds on the smallest size of a polynomial matrix realizing a given nonzero spectrum.

SMALL POLYNOMIAL MATRIX PRESENTATIONS

12

Remark 6.7. As pointed out in [4], one consequence of work by Perrin [22] is a version of Theorem 5.1 without the additional property that P (t)? is primitive. This property is signi?cant because applications of nonnegative matrices are often reduced to or based on the primitive case. Remark 6.8. The technique in Section 4 of manufacturing nonnegative matrices using a general matrix with Perron spectrum was introduced in [17] and used subsequently in various guises (e.g. [8, Thm. 5.14], [10], [18]). 7. Handelman’s theorem We use the geometric point of view developed above to recover the main parts of Handelman’s result [9, Thm. 5]. Suppose that P (t) = [p(t)] with p(t) ∈ S+ [t ]. By Proposition 3.3, every nonzero eigenvalue ? of P (t)? satis?es 1 = ??1 p(??1 ). Several people have observed that strict monotonicity of tp(t) for t > 0 then implies that sp× P (t)? cannot have any positive members except for the spectral radius ρ P (t)? . The following result of Handelman provides a converse to this, and is relevant, for example, in determining the possible entropies of uniquely decipherable codes [10]. Handelman’s original proof employed results about the coef?cients of large powers of polynomials. Our proof combines ideas from the previous section with the following elementary property of linear transformations. In order to state this property, recall that the nonnegative cone generated by a set of vectors in a real vector space is the collection of all ?nite nonnegative linear combinations of vectors in the set. Lemma 7.1. Let B be an invertible linear transformation of a ?nite-dimensional real vector space and suppose that B has no positive eigenvalue. Then for every vector e, the nonnegative cone generated by {eB m : m 0} is a vector subspace. Proof. Given a vector e, let K be the nonnegative cone generated by the {eB m : m 0}, and let W be the real vector space generated by {eB m : m 0}. We claim that K = W . For suppose that K = W . Let K denote the closure of K . Since proper cones are contained in half-spaces [23, Thm. 11.5], it follows that K = W . Then U = K ∩ (?K) is a subspace of W such that U K . Both W and U are mapped into themselves by B . Hence the quotient map D of B on W/U maps the closed cone K/U into itself. Furthermore, K/U has nonempty interior and (K/U ) ∩ (?K/U ) = {0}. It then follows (see [1] or [2, p. 6]) that the spectral radius λD of D is an eigenvalue of D . Because B is invertible and W/U is nonzero, we have that λD > 0. But every eigenvalue of D is an also eigenvalue of B , contradicting the hypothesis on B . Theorem 7.2. Let be an S-algebraic Perron list of nonzero complex numbers having no other positive elements except its spectral radius. Then there is a 1 × 1 polynomial matrix P (t) over S+ [t ] such that P (t)? is primitive, ρ( ) = ρ P (t)? , and ? sp× P (t)? .

SMALL POLYNOMIAL MATRIX PRESENTATIONS

13

Proof. We use the same notation as in the proof of Theorem 5.1, except we do not need the auxiliary vector u. As in that proof, d is the cardinality of , V = Rv is the dominant eigendirection for the companion matrix C of f (t) = ?∈ (t ? ?) ∈ S[t ], and W is the complementary C -invariant subspace. Here the case d = 1 is trivial, so we assume that d 2. Let B be the restriction of C to W , and e be the projection of e1 to W along V . The form of the companion matrix shows that {eB m : m 0} generates the vector space W . It then follows from Lemma 7.1 that 0 is in the strict interior of the convex hull of a ?nite number of the eB m . Thus there is an M d such that v is contained in the strict interior of the positive cone H generated by {e1 C m : 0 m M }. Let I denote the set of nonnegative integral combinations of the {e1 C m : 0 m M }. It is routine to show that I is syndetic in H , so that there is an a > 0 such that if x ? [1, a ]d ? H then (x ? [1, a ]d ) ∩ I = ?. Since v is the dominant eigendirection and πV (e1 ) > 0, it follows that for all suf?ciently large N > M we have that e1 C N ? [1, a ]d ? H . Hence there are vj ∈ [1, a ] and wm ∈ Z+ ? S+ such that

d M

e1 C N ?

j =1

vj ej =

m=0

wm e1 C m .

for all m ∈ Since e1 ? N + 1 C then shows that

d

Cm

Sd

0, we see that each vj ∈ S ∩ [1, a ] ? S++ . Applying

M

e1 C =

j =1

vj e1 C

?N +j

+

m=0

wm e1 C ?N +m+1 .

Thus we are again in the situation of Section 4, with r = 1 and x1 = e1 . Let P = [p(t)] be the resulting 1 × 1 matrix over S+ [t ]. Since vj > 0 for 1 j d and d 2, it follows that P (t)? is primitive. The same arguments as before now show that ρ( ) = ρ P (t)? and ? sp× P (t)? . 8. Direct limit modules A matrix A over S induces an automorphism A of its associated direct limit S-module GS (A) (the de?nitions are given below). The isomorphism class of the S-module automorphism A determines the nonzero spectrum of A, and often gives ?ner information. In the case S is a ?eld, A is the linear transformation obtained by restricting A to the maximal subspace on which it acts nonsingularly, and such an A is classi?ed by its rational canonical form. For more complicated S, the classi?cation of A is more subtle (see [7] and its references): the isomorphism class of A is determined by and determines the shift equivalence class over S of the matrix A (the “algebraic shift equivalence” class in [7]), which in the case S = Z is an important invariant for symbolic dynamics [19]. Let S[t ± ] denote the ring S[t, t ?1 ] of Laurent polynomials with coef?cients in S. As we work with polynomial matrices, it will be convenient for us to consider GS (A) as an S[t ± ]-module, by letting t ?1 act by A (the convention of using t ?1 here rather

SMALL POLYNOMIAL MATRIX PRESENTATIONS

14

than t will be explained later). Knowing the class of GS (A) as an S[t ± ]-module is equivalent to knowing the class of A as an S-module automorphism. We let gS (A) denote the cardinality of the smallest set of generators of the S[t ± ]-module GS (A). Our main result of this section sharpens Theorem 5.1 to show that if A is Perron, then we can always ?nd a P (t) over S+ [t ] of size at most gS (A) + 1 so that P (t)? is primitive with the same spectral radius as A and there is an S[t ± ]-module epimorphism GS (P (t)? ) → GS (A). This result implies Theorem 5.1 by letting A be the companion matrix of f (t). We will also see that the size of P (t) here must always be at least gS (A), and for some A must be at least gS (A) + 1. Now we turn to the promised de?nitions. We ?rst recall the de?nition of direct limits, using the directed set (Z, ), of systems of modules over a commutative ring R . For every i ∈ Z let Mi be an R -module, and for all i j let φij : Mi → Mj be an R -homomorphism such that φii is the identity on Mi , and if i j k then φj k ? φij = φik . Then ({Mi }, {φij }) is called a directed system of R -modules. The direct limit of such a system is the R -module

i ∈Z Mi

/ N,

where N is the R -submodule of the direct sum generated by elements of the form (8.1) . . . , 0, ai , 0, . . . , 0, ?φij (ai ), 0, . . . ,

where ai ∈ Mi occurs in the i th coordinate and ?φij (ai ) ∈ Mj in the j th coordinate. To specialize to our situation, let A be a d × d matrix over S. Consider the directed system ({Mi }, {φij }) of S-modules, where Mi = Sd for all i ∈ Z, and φij = Aj ?i for i j . The direct limit of this system is called the direct limit S-module of A, and is denoted by GS (A). Thus a typical element of GS (A) has the form (si ) + N , where si ∈ Sd for all i and si = 0 for almost all i . Using members of N of the form (8.1), each element (si ) ∈ Z Sd is equivalent modulo N to one of the form (. . . , 0, 0, s, 0, 0, . . . ) with at most one nonzero entry. The S-module homomorphism A of GS (A) is de?ned by A : (si ) + N → (si A) + N . To see that A is an automorphism note that (si A) + N = (si +1 ) + N , so A agrees with the automorphism of GS (A) induced by the left-shift on the direct sum. There is a more concrete description of the direct limit S-module. To describe this, recall that K denotes the quotient ?eld of S. De?ne the eventual range of A to be

∞ d

R(A) =

j =1

Rd Aj =

j =1

Rd Aj .

Then the restriction

A×

of A to R(A) is an invertible linear transformation. Set 0} .

GS (A) = { x ∈ R(A) ∩ Kd : xAm ∈ Sd for some m

The restriction A of A to GS (A) is an S-module automorphism of GS (A). Lemma 8.1. There is an S-module isomorphism between GS (A) and GS (A) which intertwines A and A.

SMALL POLYNOMIAL MATRIX PRESENTATIONS

15

Proof. As observed above, each element (si ) + N ∈ GS (A) has a representation as (. . . , 0, 0, si , 0, 0, . . . ) + N , where si occurs in the i th coordinate. By using another element of N of the form (8.1) and increasing i if necessary, we may also assume that si ∈ R(A) ∩ Kd . De?ne ψ : GS (A) → GS (A) by mapping such an element to (A× )?i si ∈ GS (A). It is routine to show that ψ is a well-de?ned isomorphism which intertwines A and A. In view of this result, we will often identify GS (A) with GS (A). Example 8.2. (a) Let d = 1, S = Z, and A = [2]. Then GS (A) = GZ ([2]) = Z[1/2], and A acts by multiplication by 2. 1 1 (b) Let d = 2, S = Z, and B = . Then GZ (B) = Z[1/2] · [1, 1], and B 1 1 again acts by multiplication by 2. Here A and B give isomorphic direct limit S[t ± ]-modules. Remark 8.3. Since A× is invertible over S[1/(det A× )], it follows that R(A) ∩ Sd ? GS (A) ? R(A) ∩ S[1/(det A× )]d . Hence if 1/(det A× ) ∈ S, then GS (A) = R(A) ∩ Sd , and in particular GK (A) = R(A) ∩ Kd . Notice that I ? tA : S[t ± ]d → S[t ± ]d is an S[t ± ]-module homomorphism. Denote its cokernel S[t ± ]-module by coker (I ? tA) = S[t ± ]d / S[t ± ]d (I ? tA). Lemma 8.4. Let A be a matrix over S. Then there is an S[t ± ]-module isomorphism between GS (A) and coker (I ? tA). Proof. There are obvious S-module identi?cations

d ZS

? =

d i i ∈Z S t

? = S[t ± ]d .

In the de?nition of GS (A), the S-submodule N is generated by elements of the form (. . . , 0, s, ?sA, 0, . . . ), with s in say the i th coordinate. This element is identi?ed with s t i ? sA t i +1 = st i (I ? tA). It follows that N = S[t ± ]d (I ? tA). Hence GS (A) = as S[t ± ]-modules. Note that I = tA on coker (I ? tA). Hence under the isomorphisms coker (I ? tA) ? = GS (A) ? = GS (A) from the previous two lemmas, the action of t ?1 on coker (I ? tA) corresponds to the action of A on GS (A). This explains our earlier de?nition of the S[t ± ]-module structure on GS (A). We next highlight the measure of the complexity of GS (A) which was used in the preamble to this section. De?nition 8.5. Let A be a matrix over S. De?ne gS (A) to be the size of the smallest generating set for GS (A) as an S[t ± ]-module.

d ZS

/N ? = S[t ± ]d / S[t ± ]d (I ? tA)

SMALL POLYNOMIAL MATRIX PRESENTATIONS

16

Suppose that A is d × d . Since S[t ± ]d is generated by d elements over S[t ± ], and since GS (A) is a quotient of S[t ± ]d by Lemma 8.4, it follows that gS (A) d . When S = K is a ?eld, then gK (A) is simply the number of blocks in the rational canonical form of A× over K. Also, if K is the quotient ?eld of S then any set which generates GS (A) over S[t ± ] will generate GK (A) over K[t ± ], so that gK (A) gS (A). However, this inequality can be strict. Example 8.6. Let B be a d × d cyclic permutation matrix, and A = I + 2B . Since the eigenvalues of A are distinct, it follows that A is similar over Q to the companion matrix of its characteristic polynomial, so that gQ (A) = 1. Consider the map φ : Z[t ± ]d / Z[t ± ]d (I ? tA) → Zd / Zd (I ? A) induced by φ(t) = 1. Any set of Z[t ± ] generators for GZ (A) maps to a spanning set for the (Z/2Z)-vector space Zd / Zd (I ? A) = Zd / Zd (?2B) ? = (Z/2Z)d . This shows that gZ (A) d . Our remarks above show that gZ (A) d , so that gZ (A) = d . We now turn to polynomial matrices. Let P (t) be an r × r matrix over S[t ], and P (t)? be the n × n matrix resulting from the ?-construction. Proposition 3.3 and Lemma 8.4 suggest introducing the S[t ± ]-module GS P (t) de?ned by GS P (t) = S[t ± ]r / S[t ± ]r I ? tP (t) = coker I ? tP (t) . Lemma 8.7. GS P (t) and GS P (t)? are isomorphic S[t ± ]-modules. Proof. Recall from Section 3 that P (t)? is indexed by symbols jk , where 1 j r and 0 k d(j ). Let ejk ∈ S[t ± ]n be the corresponding elementary basis vector, and similarly ej ∈ S[t ± ]r . De?ne φ : S[t ± ]n → S[t ± ]r by φ(ejk ) = t k ej . Then for 1 k d(j ), φ ejk I ? t {P (t)? } while φ ej0 I ? t {P (t)? } Hence φ S[t ± ]n I ? t {P (t)? } = S[t ± ]r I ? tP (t) . This shows that φ induces an isomorphism of S[t ± ]-modules

φ ? → coker I ? tP (t) ? GS (P (t)? ) ? = coker I ? t {P (t)? } ? = GS P (t)

= φ(ejk ) ? tφ(ejk?1 ) = 0,

= ej ? t pj 1 (t)e1 ? · · · ? t pj r (t)er = ej I ? tP (t) .

completing the proof. Since coker I ? tP (t) is generated by the images of the r elementary basis vectors, it follows that gS (P (t)? ) r , although P (t)? may have size much larger than r . Suppose that A is a matrix over S, and that P (t) is an r × r polynomial matrix such that there is a S[t ± ]-homomorphism from GS (P (t)? ) onto GS (A). Then

SMALL POLYNOMIAL MATRIX PRESENTATIONS

17

gS (A) ≤ gS (P (t)? ) r , so that gS (A) is a lower bound for the size of any such polynomial matrix. Our ?nal result shows that, even with a further Perron restriction, we can always come within one of this lower bound. Theorem 8.8. Let A be a Perron matrix over S. Then there exists a polynomial matrix P (t) over S+ [t ] of size at most gS (A) + 1 such that ρ P (t)? = ρ(A), P (t)? is primitive, and there is a S[t ± ]-module homomorphism from GS (P (t)? ) onto GS (A). Proof. Suppose that A is a d × d Perron matrix over S. As before, let K denote the quotient ?eld of S. Let λ = ρ(A) > 0 be the spectral radius of A, and v be an eigenvector corresponding to λ. Let m be the dimension of the eventual range R(A) of A. Set V = Rv, and de?ne πV : R(A) → V to be projection to V along the direct sum of the generalized eigenspaces of the other eigenvalues of A× = A|R(A) . Identifying V with R via t v ? t means we can think of πV as having range R. Let g = gS (A). We identify GS (A) with GS (A), and for notational simplicity use A instead of A. By de?nition there are elements x1 , . . . , xg ∈ GS (A) that generate GS (A) over S[t ± ]. Since R(A) ∩ Sd ? GS (A) spans R(A) ∩ Kd using K-linear combinations, there must be at least one xj with πV (xj ) = 0. Replacing xj with ?xj if necessary, we can assume that πV (xj ) > 0. Then by adding to each xi a large enough integral multiple of xj , we can also assume that πV (xi ) > 0 for 1 i g. For a ?nite set W of vectors in Rd , let K(W) = w∈W R+ w denote the nonnegative real cone generated by W. Since GS (A) spans R(A) ∩ Kd using K-linear combinations, for all suf?ciently large D the cone K {xi Aj : 1 i g, ?D j D}

has nonempty interior in R(A). We extract vectors b1 , . . . , bm?1 from {xi Aj : 1 i g, ?D j D } such that {b1 , . . . , bm?1 , v} is linearly independent. Proceeding as in the construction of u in Theorem 5.1, we choose c0 , c1 , . . . , cm?1 from K++ to de?ne xg +1 = c0 v + c1 (v ? b1 ) + · · · + cm?1 (v ? bm?1 ) such that πV (xg +1 ) > 0 and v is in the interior of K {b1 , . . . , bm?1 , xg +1 } . De?ne bm = xg +1 . Applying a large power of A and adjusting D if necessary, we may assume that each bj ∈ Sd . Set X = {xi Aj : 1 i g + 1, ?D j D}

and B = {b1 , . . . , bm }. Let πR(A) : Rd → R(A) denote the projection to R(A) along the eventual nullspace of A. For each standard basis vector ej ∈ Rd let uj = πR(A) (ej ). Observe that uj = (ej Ad )(A× )?d , and so uj ∈ GS (A) for every j . Since the xi generate under S[t ± ], by increasing D if necessary one last time we may assume

SMALL POLYNOMIAL MATRIX PRESENTATIONS

18

there are γj (x) ∈ S such that uj = ?=

x∈X γj (x)x. d

Set

|γj (x)|.

j =1 x∈X

We claim that for any v ∈ GS (A) ∩ Sd , (8.2) v=

x∈X

γ (x)x, where γ (x) ∈ S and |γ (x)|

d j =1 vj ej

? v

∞

for all x ∈ X.

To check this claim, suppose that v = |vj | v ∞ for 1 j d . Then

d

∈ GS (A) ∩ Sd , where vj ∈ S and

d

v = πR(A) (v) =

j =1 d

vj πR(A) (ej ) =

j =1 d

vj uj

=

j =1

vj

x∈X

γj (x)x =

x∈X j =1 d

vj γj (x) =

x∈X

γ (x)x,

where |γ (x)| =

j =1

vj γj (x)

? v

∞

for all x ∈ X,

establishing (8.2). Our goal now is to show that if z ∈ GS (A) with πV (z) > 0, then for all suf?ciently large N > D we can write zAN as an S++ -combination of vectors from X. Applying this to z = x1 , . . . , z = xg +1 puts us into the situation of Section 4, and the construction of the required polynomial matrix P (t) of size g + 1 then follows using the same method as in the proof of Theorem 5.1. As in the proof of Theorem 5.1, we consider separately the cases S = Z and S dense. First suppose that S = Z. Then | det A× | = ?∈sp× (A) |?| ∈ Z++ , and hence λ 1. If λ = 1, then since A is Perron we must have that sp× (A) = {1} and GZ (A) = R(A) ∩ Zd ? = Z. In this case simply take P (t) = [1]. m Now suppose that λ > 1. The lattice j =1 Zbj has a fundamental domain m [ 0 , 1 ) b . Let C = max { w : w ∈ F }. Choose ∈ Z++ such that F = j ∞ j =1 d d > 2C? and x ∈ Z for all x ∈ X. Put y = x∈X x ∈ GZ (A) ∩ Z . Suppose that z ∈ GZ (A) and πV (z) > 0. Since λ > 1 and v ∈ K(B)? , for all suf?ciently large N we have that zAN ? y ∈ K(B)? . Hence there are nj ∈ Z+ such that

d

zAN ? y =

j =1

nj bj + w,

where w ∈ F and so w ∞ C . Since zAN , y, and the bj are in GZ (A) ∩ Zd , it follows that w ∈ GZ (A) ∩ Zd . By (8.2), w = x∈X γ (x)x, where γ (x) ∈ Z and

SMALL POLYNOMIAL MATRIX PRESENTATIONS

19

|γ (x)|

? w

∞

C? for all x ∈ X. Thus

d

zAn =

j =1

nj bj +

x∈X

+ γ (x) x.

Since B ? X and

> |γ (x)| for all x ∈ X, we have that zAN =

x∈X

ξ(x)x,

where ξ(x) ∈ Z++ for all x ∈ X. This completes the case S = Z. Finally, suppose that S is dense in R. Let z ∈ GS (A) with πV (z) > 0. Then for all suf?ciently large N we have that zAN ∈ Sd and zAN ∈ K(B)? . Since S is dense, we can ?nd δ ∈ S++ such that δ x ∈ Sd for all x ∈ X and also that zAN ? δ

x∈X

x ∈ K(B)? .

By density of S, we can choose sj ∈ S+ such that

m

zA ? δ

x∈X

N

x=

j =1

sj bj + w,

where w ∞ < δ/2? . Then w ∈ GS (A) ∩ Sd , and so by (8.2) we have that δ/2 for all x ∈ X. ? w ∞ w = x∈X γ (x)x, where γ (x) ∈ S and |γ (x)| Thus

m

xAN =

j =1

sj bj +

x∈X

δ + γ (x) x.

Since B ? X and δ > |γ (x)| for all x ∈ X, we have that zAN =

x∈X

ξ(x)x,

where ξ(x) ∈ S++ for all x ∈ X. Example 8.9. It is not possible to strengthen the statement of Theorem 8.8 by simply replacing gS (A) + 1 with gS (A). For let A be the companion matrix of p(t) = t 2 ? 3t + 1 and S = Z. Clearly gS (A) = 1. Now suppose P (t)? is primitive and there is an S[t ± ]-module homomorphism from GS (P (t)? ) onto GS (A). Then the two positive roots of p(t) must be contained in the eigenvalues of P (t)? , and therefore the size of P (t) must be greater than 1 by Section 7. Remark 8.10. In Theorem 8.8 we considered possibly singular matrices A. This is necessary: when S is not a principal ideal domain, it can happen for a singular matrix A over S there is no nonsingular matrix B over S such that the S[t ± ]-modules GS (A) and GS (B) are isomorphic [7, Prop. 2.1].

SMALL POLYNOMIAL MATRIX PRESENTATIONS

20

References

[1] Garrett Birkhoff, Linear transformations with invariant cones, Amer. Math. Monthly 72 (1967), 274–276. [2] Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. [3] Louis Block, John Guckenheimer, Michal Misiurewicz, and Lai Sang Young, Periodic points and topological entropy of one dimensional maps, Global Theory of Dynamical Systems, Lecture Notes in Math. 118, 18–34, Springer, Berlin, 1980. [4] Mike Boyle, Symbolic dynamics and matrices, Combinatorial and Graph-Theoretic Problems in Linear Algebra, IMA Vol. Math. Appl. 50, 1–38, Springer, New York, 1993. [5] Mike Boyle, Positive K-theory and symbolic dynamics, preprint (2001). [6] Mike Boyle and David Handelman, The spectra of nonnegative matrices via symbolic dynamics, Annals of Math. 133 (1991), 249–316. [7] Mike Boyle and David Handelman, Algebraic shift equivalence and primitive matrices, Trans. Amer. Math. Soc. 336 (1993), no. 1, 121–149. [8] Mike Boyle, Brian Marcus and Paul Trow, Resolving maps and the dimension group for shifts of ?nite type, Mem. Amer. Math. Soc. 70 (1987), no. 377. [9] David Handelman, Spectral radii of primitive integral companion matrices and log concave polynomials, Symbolic Dynamics and itsApplications, Contemporary Mathematics 135 (1992), Amer. Math. Soc., Providence. [10] Jacob Goldberger, Douglas Lind, and Meir Smorodinsky, The entropies of renewal systems, Israel J. Math. 33 (1991), 1–23. [11] Charles R. Johnson, Row stochastic matrices that are similar to doubly stochastic matrices, Linear and Multilinear Algebra 10 (1981), 113-120. [12] Charles R. Johnson, Thomas J.Laffey, and Raphel Loewy, The real and the symmetric nonnegative inverse eigenvalue problems are different, Proc. Amer. Math. Soc. 124 (1996), 3647–3651. [13] Ki Hang Kim, Nicholas S. Ormes, and Fred W. Roush, The spectra of nonnegative integer matrices via formal power series, J. Amer. Math. Soc. 13 (2000), 773–806. [14] Ki Hang Kim, John B. Wagoner and Fred W. Roush, Characterization of inert actions on periodic points I, Forum Math. 12(2000), no. 5, 565–602. [15] Thomas J. Laffey, Realizing matrices in the nonnegative inverse eigenvalue problem, in Matrices and group representations (Coimbra, 1998), 21–32, Textos Mat. Sér. B, 19, Univ. Coimbra, Coimbra, 1999. [16] Thomas J. Laffey and Eleanor Meehan, A characterization of trace zero nonnegative 5 × 5 matrices, Linear Algebra Appl. 302/303 (1999), 295–302. [17] Douglas Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory & Dynam. Systems 4 (1984), 283–300. [18] Douglas Lind, The spectra of topological Markov shifts, Ergodic Theory & Dynam. Systems 6 (1986), 571–582. [19] Douglas Lind and Brian Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge, New York, 1995. [20] Raphael Loewy and David London, A note on an inverse problem for nonnegative matrices, Linear and Multilinear Algebra 6 (1978), 83-90. [21] Henryk Minc, Nonnegative Matrices, Wiley-Interscience, New York, 1988. [22] Dominique Perrin, On positive matrices, Theoretical Computer Sci. 94 (1992), 357–366. [23] R. Tyrrell Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, 1970. [24] Claude E. Shannon, The mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379–423. Reprinted by Univ. of Illinois Press, 1963.

SMALL POLYNOMIAL MATRIX PRESENTATIONS

21

Mike Boyle, Department of Mathematics, University of Maryland, College Park, MD 20742 E-mail address: mmb@math.umd.edu Home page: www.math.umd.edu/?mmb Douglas Lind, Department of Mathematics, Box 354350, University of Washington, Seattle, WA 98195 E-mail address: lind@math.washington.edu

- The spectral norm of a nonnegative matrix
- On the complexity of nonnegative matrix factorization
- On the equivalence of nonnegative matrix factorization and spectral clustering
- GENERALIZATIONS OF M-MATRICES WHICH MAY NOT HAVE A NONNEGATIVE INVERSE
- Shifted Normal Forms of Polynomial Matrices
- Computing generalized inverse of polynomial matrices by interpolation
- Polynomial instances of the positive semidefinite and Euclidean distance matrix completion
- Ergodic properties of nonnegative matrices. I
- A characterization of trace zero nonnegative 5 × 5 matrices
- On the characteristic polynomial of a random unitary matrix
- Dynamics of piecewise linear maps and sets of nonnegative matrices
- Stability of 2-D Polynomial Matrices 1
- Optimality, computation and interpretation of nonnegative matrix factorizations
- On the complexity of nonnegative matrix factorization
- The spectral norm of a nonnegative matrix

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