Posts Tagged ‘companion matrices’

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space X and a function f : X \to X, and under the assumption that f^n has a finite number of fixed points for all n, we define the dynamical zeta function to be the formal power series

\displaystyle \zeta_X(t) = \exp \sum_{n \ge 1} (\text{Fix } f^n) \frac{t^n}{n}.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.


Read Full Post »

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial C(t) with non-negative integer coefficients and C(0) = 0, let r_1, ... r_n be the reciprocals of the roots of C(t) - 1 = 0. Then

\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by C(t). Today we’ll describe this species when C(t) is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.


Read Full Post »

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to \ 2 are the induced subgraphs of the Dynkin diagrams \tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8.

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree 3 in a graph with \rho(G) \le 2. But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

- simply laced Lie groups,

- binary polyhedral groups and the Platonic solids,

- quiver representations, or

- the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.


Read Full Post »


Get every new post delivered to your Inbox.

Join 283 other followers