Séminaire Lotharingien de Combinatoire 61A (2009), Article B61Ac

CHARACTERISTIC POLYNOMIALS OF NONNEGATIVE INTEGRAL SQUARE MATRICES

AND CLIQUE POLYNOMIALS

SYLVAIN LAVALLÉE AND CHRISTOPHE REUTENAUER

In memory of Pierre Leroux

Abstract. Clique polynomials of vertex-weighted simple graphs coincide with polynomials of the form det(1 − xM), M a square matrix over ℕ.

1. Introduction

Characterizing characteristic polynomials of nonnegative matrices, and in particular matrices over ℕ, is an old problem; see [BH91], and the references therein. An equivalent problem is to characterize polynomials of the form det(1 − xM), for M a nonnegative matrix; this polynomial is the reciprocal polynomial of the characteristic polynomial of M.

In the present Note, we characterize these polynomials when M is a square matrix over ℕ. We show that they coincide with the clique polynomials (also called dependence polynomials) of vertex-weighted finite simple graphs. This polynomial is the sum of all monomials (−1)^{i} x^{j}, for all complete i-subgraphs of the given graph, where j is the sum of the weights of the vertices. Note that the classical clique polynomial correspond to the case where the weight of each vertex is 1.

Since the work of Cartier and Foata [CF69] (see also the website of Séminaire lotharingien de Combinatoire, where this book is available in electronic form), it is known that the inverses of these (weighted) clique polynomials are exactly the Hilbert series of the (graded) free partially commutative monoids. Hence, by our result, these series coincide with the series det(1 − xM)^{−1}, M a square matrix over ℕ (a result in the flavor of the MacMahon Master Theorem, that motivated the work of Cartier and Foata). One direction is easy and follows from their work: the determinants det(1 − xM) are weighted clique polynomials.

Key words and phrases. Characteristic polynomials, clique polynomials, free partially commutative monoids.

For the opposite direction, we have no combinatorial, nor algebraic proof. Instead, the proof is analytic and uses a difficult result of Kim, Ormes and Roush [KOR00], which solve a conjecture of Boyle and Handelman [BH91]: they give a necessary and sufficient condition for a d-tuple (λ_{1}, …, λ_{d}) of complex numbers to be the set of inverses of the nonzero eigenvalues of a primitive matrix over ℕ. In order to show that our clique polynomial satisfies their condition, we use the theory of Cartier–Foata. In particular, we show that if the noncommutation graph is connected, then the Cartier–Foata digraph (which describes the Cartier–Foata normal form) is strongly connected. This allows us to apply the Perron–Frobenius theorem and show that, under the previous hypothesis of connectivity, the Hilbert series of the free partially commutative monoid has a simple dominating root (a result which improves [GS00]). We use also the theorem of Poincaré– Birkhoff–Witt, applied to the free partially commutative Lie algebra (or its monoidal variant giving a factorization into Lyndon elements, by Lalonde), in order to show that the ”trace” positivity hypothesis in the Kim–Ormes–Roush theorem is satisfied.

Our result has also some consequence in graph theory: it implies that each clique polynomial is of the form det(1−xM) for some square matrix M over ℕ. The simplest instance of this result is Mantel’s theorem, which says in essence that 1−a x+b x^{2} is a clique polynomial if and only if it has real roots, that is, if 4 b ≤ a^{2}. However this result, in the spirit of extremal graph theory (see [Bol98]), did not lead us to a general solution. We are indebted to Christophe Paul for indicating us these graph-theoretical references.

2. Main result

Let C be a finite simple graph (undirected edges, no multiple edges, no loops). Associated to it is the clique polynomial (also called dependence polynomial)

1 + ∑_{i} (−1)^{i}g_{i} x^{i},

where g_{i} is the number of complete subgraphs with i vertices in C, see [FS90].

We need a slight generalization of this. We assume that to each vertex of C is assigned a positive integer, its weight. The weight of a subset of vertices is then the sum of their weights. Then the dependence polynomial of this weighted graph is

∑_{B} (−1)^{|B|} x^{weight(B)},

where the sum is over all the subsets B of vertices in C which form a complete subgraph.

By [CF69], the inverse of this polynomial is the generating function (or Hilbert series) of the graded free partially commutative monoid defined as follows: let A be the set of vertices of C, consider the free monoid A^{∗} on A and its congruence ∼_{C} generated by the relations ab ∼_{C} ba if {a, b} is an edge of C, with the degree function on the generators corresponding to the weight. Then the free partially commutative monoid is A^{∗}/ ∼_{C}. Because of his construction, we call as usually C the commutation graph and its complementary graph \overline{C} the non-commutation graph.

We consider now another class of polynomials: take a square matrix M of order n over the natural numbers and form the polynomial det(1− x M), where 1 denotes the identity matrix of the appropriate size. Note that this polynomial is the reciprocal of the characteristic polynomial of M (in the sense that the symmetry of the coefficients is with respect to n/2).

Theorem 2.1. Clique polynomials of weighted finite simple graphs coincide with reciprocal of characteristic polynomials of square matrices over the natural numbers. In other words, generating functions of graded free partially commutative monoids coincide with the series of the form det(1 − x M)^{−1}, M a square matrix over ℕ.

Before proving this result, we give an example which shows that the hypothesis ”weighted” is necessary: consider the polynomial 1−x−x^{2}; it is of the form det(1 − x M), but not the clique polynomial of a graph in the usual sense (each vertex has weight 1), only in the sense of weighted graphs.

The rest of the Note is devoted to the proof of the Theorem. It is already in the spirit of the work in [CF69] on the MacMahon Master Theorem that each polynomial det(1 − x M), M ∈ ℕ^{n×n}, is a clique polynomial. We indicate briefly their construction of a graded free partially commutative monoid associated to a directed graph, hence to a square matrix over ℕ: M is the adjacency matrix of some directed graph D with vertex set {1, 2, …, n}. By expanding the determinant using the formula involving permutations, and then decomposing the latter into cycles, it is seen that

det(1 − x M) = ∑_{{γ_{1}, ..., γ_{k}}} (−1)^{k} x^{|γ_{1}|+...+|γ_{k}|}.

In this sum, k is in ℕ, {γ_{1}, …, γ_{k}} is a set of k mutually disjoint (no vertex in common) circular paths without repeated vertex, and |γ_{i}| denotes the length of path γ_{i}.

Hence, this polynomial is the clique polynomial of the following weighted finite simple graph C: the vertices of C are the circular paths in D without repeated vertex; there is an edge {γ, γ′} in C if γ and γ′ are disjoint, and the weight of γ is |γ|. Thus det(1 − x M) is a clique polynomial.

In order to prove that each clique polynomial is of the form det(1 − x M), one cannot simply revert the previous construction. Indeed, the function π : D → C, given by the previous construction, from the set of digraphs onto the set of simple graphs is not surjective; for example, if C is the graph

b a  c

with weight function 1, so that its clique polynomial is 1 − 3 x + x^{2}, there is no digraph D such that π(D) = C; otherwise, D should have 3 circular paths of length 1 such that exactly 2 of them are disjoint, which is not possible. However,

1 − 3 x + x^{2} = det (1 − x [\begin{matrix}2 & 1 \\ 1 & 1 \end{matrix}]) .

In order to prove the converse of the theorem, we use a deep result of Kim, Ormes and Roush [KOR00], who prove a conjecture of Boyle and Handelman [BH91]. Their result is as follows: a polynomial P (x) = ∏_{i=1}^{k} (1 − λ_{i} x), where the λ_{i} are nonzero complex numbers, is of the form det(1 − x M) for some primitive square matrix M over ℕ if the following conditions hold:

(i) the coefficients of P (x) are all integers; (ii) there is some i such that for all j ≠ i, λ_{i} > |λ_{j}|; (iii) tr_{n}(λ_{1}, …, λ_{k}) ≥ 0, for all n ≥ 1, where

tr_{n}(λ_{1}, …, λ_{k}) = ∑_{d | n} μ (\frac{n}{d}) (λ_{1}^{d} + … + λ_{k}^{d}) .

We take for P (x) the clique polynomial of some weighted finite simple graph C, which is fixed. Then P (x) = ∏_{i=1}^{k} (1−λ_{i} x), for some nonzero λ_{i} ∈ ℂ, since P (0) = 1.

Let us verify (iii). A classical computation shows that

\frac{1}{P (x)} = ∏_{n≥1} \frac{1}{(1 − x^{n})^{α_{n}}} ,

with α_{n} = \frac{1}{n} tr_{n}(λ_{1}, …, λ_{k}). Now, the theory of [CF69] tells us that \frac{1}{P (x)} is the Hilbert series of the graded monoid A^{∗}/ ∼_{C}; equivalently of its monoid algebra. Since the presentation is a Lie presentation (ab = ba may be written [a, b] = 0) this algebra is an enveloping algebra (see, e.g., [DK93]). Thus we see, by applying the theorem of Poincaré– Birkhoff–Witt, that the α_{n} must be nonnegative integers.

Alternatively, we may apply [Lal95], where is shown that A^{∗}/ ∼_{C} has a factorization into cyclic submonoids.

In order to prove (ii), we need a result which is of independent interest. It is well-known that if a formal series f = ∑_{n≥0} f_{n} x^{n} over ℂ is rational, that is, quotient of two polynomials, then for n large enough, one has

f_{n} = ∑_{i=1}^{ℓ} λ_{i}^{n} P_{i}(n),

for some fixed nonzero λ_{1}, …, λ_{ℓ} ∈ ℂ and nonzero polynomials P_{1}(t), …, P_{ℓ}(t) over ℂ. The multiplicity of λ_{i} is deg(P_{i}) + 1. This expression for f_{n} is called its exponential polynomial and is unique, and the λ_{i}’s are the eigenvalues of f. See e.g. [SS78], [BR88].

Following [Soi76], we say that λ_{1} is a dominating eigenvalue if |λ_{1}| > |λ_{i}|, i = 2, …, ℓ. This root is moreover simple if deg(P_{1}) = 0.

Proposition 2.2. Let ∑_{n≥0} f_{n} x^{n} be the Hilbert series of the free partially commutative monoid A^{∗}/ ∼_{C}. If the complementary graph \overline{C} is connected and if the integers weight(a), a ∈ A, are relatively prime, then this series has a unique dominating root, which is simple.

Remark 2.3.

1. The hypothesis on \overline{C} is very natural and classical. If it does not hold, then A^{∗}/ ∼_{C} is the direct product of the free partially commutative monoid determined by the connected components of \overline{C} (see e.g. [Lal79], [Die90]). Moreover, the clique polynomial of C is the product of the clique polynomials of these components.

2. The fact that the Hilbert series of a free partially commutative monoid is rational is already in [CF69]. That it is even ℕ-rational follows from the normal form in [CF69]; indeed, the latter implies that this monoid is an unambiguous rational subset of itself (result attributed to Sontag in [Fli74] p. 204).

3. The proposition improves [GS00], by the condition ”simple”. Indeed, in this article is proved that the Hilbert series of a free partially commutative monoid, with generators of degree 1, has a dominating root. Their result is not sufficient for our proof, since in the hypothesis (ii) of the Theorem of Kim, Ormes and Roush, simplicity is needed.

Recall the Cartier–Foata normal form for elements of A^{∗}/ ∼_{C}. We say that a subset B of A is commutative is B ≠ ∅ and if ab ∼_{C} ba for any a, b ∈ B. If B_{1}, B_{2} are commutative subsets of A, we say that B_{2} is linked with B_{1} if for each b ∈ B_{2}, either b ∈ B_{1}, or b does not commute, modulo ∼_{C}, with some element in B_{1}.

Then each element in A^{∗}/ ∼_{C} has a unique factorization [B_{1}] [B_{2}] … [B_{k}], for some k ≥ 0, where the B_{i} are commutative subsets of A, where B_{i+1} is linked with B_{i}, for i = 1, …, k −1 and where [B] is the product in A^{∗}/ ∼_{C} of the elements in B.

We define a digraph whose vertices are the commutative subsets of A, with an edge B_{1} → B_{2} if B_{2} is linked with B_{1}. We call this the Cartier–Foata digraph.

Lemma 2.4. If the non-commutation graph \overline{C} is connected, then the Cartier–Foata digraph is strongly connected.

Proof. It is enough to show that the Cartier–Foata digraph D has a subgraph D_{1} such that

- D_{1} is strongly connected;

- for each vertex B of D, there is a path from B into D_{1} and a path from D_{1} to B.

For D_{1}, we take all the vertices B of D which are singletons: B = {a}, a ∈ A. Note that if a, b ∈ A do not commute modulo ∼_{C}, or if a = b, then {b} is linked with {a}. Hence D_{1} has edges a → b and b → a for each a, b ∈ A such that a − b is an edge of \overline{C}. Since \overline{C} is connected, D_{1} is strongly connected.

Now, let B some vertex in D. If b ∈ B, then {b} is linked to B, hence there is an edge B → {b} in D. It remains to show that there is a path in D from D_{1} to B. We may assume that |B| ≥ 2. We prove by induction on |B| and on d(B) = min{d(b_{1}, b_{2}) | b_{1}, b_{2} ∈ B, b_{1} ≠ b_{2}}, where d is the distance in the graph \overline{C}; since B is a commutative subset of A, d(B) ≥ 2.

Let a ∈ A. Define B_{1} = \{b ∈ B | a−b ∈ \overline{C}\} and B′ = (B\B_{1})∪\{a\}. Then B′ is commutative. Moreover B is linked with B′: indeed, if b ∈ B then either b ∈ B \ B_{1} ⊆ B′ or b ∈ B_{1} and b does not commute with a by construction. Thus B′ → B in D.

Suppose first that d(B) = 2. Then there exist b_{1}, b_{2} ∈ B such that d(b_{1}, b_{2}) = 2 and we may find a ∈ A and the edges b_{1} − a − b_{2} in \overline{C}. Then B_{1} as above satisfies |B_{1}| ≥ 2 ⇒ |B′| < |B| and we conclude by induction on |B|.

Suppose now that d(B) ≥ 3. We may find b_{1}, b_{2} ∈ B such that d(b_{1}, b_{2}) = d(B) and thus a ∈ A such that a − b_{1} in \overline{C} and d(a, b_{2}) = d(b_{1}, b_{2}) − 1 ≥ 2. Then B_{1} as above satisfies |B_{1}| ≥ 1, thus |B′| ≤ |B|. Moreover, a, b_{2} ∈ B′ (since b_{2} ∉ B_{1}, otherwise d(a, b_{2}) = 1), hence d(B′) < d(B). We then conclude by induction on d(B). □

Proof of the proposition.

1. To the Cartier–Foata digraph D, we associate the following adjacency-like matrix M: the rows and columns are indexed by the commutative subsets of A and the entry in position (B_{1}, B_{2}) is x^{weight(B_{2})}. Let λ_{B} be the row vector with 1 in position B, 0 elsewhere, and γ the column vectors with 1 everywhere.

2. Let α be some new symbol and define a new digraph D′ by adding the new vertex α, together with edges α → B for each vertex B in D. Clearly, the set of Cartier–Foata normal forms is in bijection with the paths in D′ starting from α.

3. It thus follows that the Hilbert series of A^{∗}/ ∼_{C} is

1 + ∑_{B} x^{deg(B)} λ_{B} M^{∗} γ,

where the sum is over all commutative subsets B of A, and where M^{∗} = ∑_{n≥0} M^{n}.

4. By the linearization process of [Boy91], Section 5, one associates to M a square matrix N over ℕ such that each coefficient of M^{∗} is equal to a sum of coefficients of (xN)^{∗}. Since the digraph D is strongly connected, N is an irreducible matrix. Moreover since the diagonal entries of M contain x^{weight(a)}, a ∈ A, and since the numbers weight(a) are supposed to be relatively prime, N is even a primitive matrix.

5. We deduce that the Hilbert series of A^{∗}/ ∼_{C} is 1+ a nontrivial sum of terms of the form x^{d} (xN)_{i j}^{∗}, d ∈ ℕ.

6. Since N is primitive, by the Perron–Frobenius theory (see [Gan59] Chap. III, Section 2), its eigenvalues, counted with their multiplicities, are λ_{1}, …, λ_{k}, with λ_{1} > |λ_{2}|, …, |λ_{k}|. In particular, λ_{1} is simple. By Jordan normal form, we deduce that each series (xN)_{i j}^{∗} is of the form ∑_{n≥0} a_{n} x^{n}, with

a_{n} = h λ_{1}^{n} + ∑_{s=2}^{k} P_{s}(n) λ_{s}^{n},

for n large enough.

7. The dominating coefficient, that is h, must be positive. Indeed, since N is primitive, we have N^{r} strictly positive for some r. Then, for any indices u, v, a_{n+2r} = (N^{n+2r})_{i, j} ≥ (N^{r})_{i, u} (N^{n})_{u, v} (N^{r})_{v, j}; thus (N^{n})_{u, v} ≤ C a_{n+2r}, of some constant C. Hence, if we had h = 0, then N^{n} would grow slower that λ_{1}^{n}, contradiction. Hence h ≠ 0 and h > 0 since a_{n} ≥ 0 and a_{n} ∼ h λ_{1}^{n}, when n → ∞.

8. Note that if a_{n} has a positive dominating coefficient, then x^{d} a_{n} also. This implies, in view of 5. that (f_{n}) has λ_{1} as dominating eigenvalue, which moreover is simple.

□

Remark 2.5. One could think that the Hilbert series of the free partially commutative monoid A^{∗}\ ∼_{C} is simply det(1−M)^{−1} = det(1−xN)^{−1}, with the above notations. This would greatly simplify the proof of the Proposition. This is however not true, even for the graph C of the previous figure. Indeed, in this case det(1 − M) = (1 − x)(1 + x)(1 − 3x + x^{2}). It is a general fact that det(1 − M) is always a multiple of P (x). Our proof shows that these two polynomials, although unequal in general, have the same unique and simple root of minimal modulus.

Note that the Cartier–Foata digraph of the example is the graph

a  b  c ac

and that the matrix M is

[\begin{matrix}x & x & 0 & 0 \\ x & x & x & x^{2} \\ 0 & x & x & 0 \\ x & x & x & x^{2} \end{matrix}] .

We may now prove (ii). We claim that we may assume the two following conditions:

(1) \overline{C} is connected;

(2) the numbers deg(a), a ∈ A, are relatively prime. The claim will be proved below. Then the proposition implies that

\frac{1}{P (x)} = ∑_{n≥0} f_{n} x^{n}

and for n large enough,

f_{n} = h λ_{1}^{n} + ∑_{i=2}^{ℓ} P_{i}(n) λ_{i}^{n},

with λ_{1} > |λ_{2}|, …, |λ_{ℓ}| and h ≠ 0. It follows classically (see e.g.

[BR88] and [SS78]) that ∑_{n≥0} f_{n} x^{n} is the sum of a polynomial, of \frac{h}{1−λ_{1} x} and of a ℂ-linear combination of fractions of the form \frac{x^{s}}{(1−λ_{i} x)^{t}}, i ≥ 2. Hence, its denominator, that is P (x), is a product of (1 − λ_{1} x) with factors of the form (1 − λ_{i} x)^{t}, which proves (ii).

It remains to prove the claim. If \overline{C} is not connected, then the clique polynomial of C is a product of smaller clique polynomials. It then suffices to take for M the diagonal sum of the corresponding matrices.

If the integers deg(a) are not relatively prime, let p their greatest common divisor and take as new degree the function deg′(a) = \frac{1}{p} deg(a). Thus it is enough to show that for any square matrix M over ℕ, det(1 − x M) |_{x→x^{p}} is also of the form det(1 − x M′), for some square matrix M′ over ℕ. This is proved by applying once more the linearization process of [Boy91], section 5.

Acknowledgments

We thank the two referees for their useful suggestions. One of them suggested the following sharpening of the main result: a series is of the form det(1 − Mx)^{−1}, with M a primitive square matrix over ℕ, if and only if it is the generating function (Hilbert series) of some graded free partially commutative monoid, with relatively prime degrees of the generators and with a connected non-commutation graph. The proof of this result follows along the line of the present article, and we leave it to the reader.

References

[BR88] J. Berstel and C. Reutenauer. Rational series and their languages. Springer–Verlag, 1988.

[Bol98] B. Bollobás. Modern graph theory. Springer–Verlag, 1998.

[Boy91] M. Boyle. Symbolic dynamics and matrices. Combinatorial and graphtheoretical problems in Linear Algebra, IMA Volumes in Mathematics and its Applications, 50, 1991.

[BH91] M. Boyle and D. Handelman. The spectra of nonnegative integer matrices via symbolic dynamics. Annals of Mathematics, 133(2):249–316, 1991.

[CF69] P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangement. Lecture Notes in Mathematics, Springer–Verlag, Volume 85, 1969.

[Die90] V. Diekert. Combinatorics on traces. Lecture Notes in Computer Sciences, 454, Springer, 1990.

[DK93] G. Duchamp and D. Krob. Free partially commutative structures. Journal of Algebra, 156(2):318–361, 1993.

[FS90] D.C. Fisher and A.E. Solow. Dependence polynomials. Discrete Mathematics, 82:251–258, 1990.

[Fli74] M. Fliess. Matrices de Hankel. Journal de mathématiques pures et appliquées, 53(2):197–224, 1974.

[Gan59] F.R. Gantmacher. Applications of the theory of matrices. Interscience, 1959.

[GS00] M. Goldwurm and M. Santini. Clique polynomials have a unique root of smallest modulus,. Information and Processing Letters, 75:127–132, 2000.

[KOR00] K.H. Kim, N.S. Ormes, and F.W. Roush. The spectra of nonnegative integer matrices via formal power series. Journal of the American Mathematical Society, 13(4):773–806, 2000.

[Lal79] G. Lallement. Semigroups and combinatorial applications. John Wiley & Sons, 1979.

[Lal95] P. Lalonde. Lyndon heaps: an analogue of Lyndon words in free partially commutative monoids. Discrete Mathematics, 145(1):171–189, 1995.

[SS78] A. Salomaa and S. Soittola. Automata-theoretic aspects of formal power series. Springer–Verlag, 1978.

[Soi76] M. Soittola. Positive rational sequences. Theoretical Computer Science, 2(3):317–322, 1976.

Département de mathématiques, Université du Québec à Montréal, Canada

  E-mail address: lavallee.sylvain.2@courrier.uqam.ca
  E-mail address: reutenauer.christophe@uqam.ca