CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES

KARIN ERDMANN AND SIBYLLE SCHROLL

Abstract. In this paper we evaluate Chebyshev polynomials of the second-kind on a class of symmetric integer matrices, namely on adjacency matrices of simply laced Dynkin and extended Dynkin diagrams. As an application of these results we explicitly calculate minimal projective resolutions of simple modules of symmetric algebras with radical cube zero that are of finite and tame representation type.

1. Introduction

Chebyshev polynomials are a sequence of recursively defined polynomials. They appear in many areas of mathematics such as numerical analysis, differential equations, number theory and algebra [R]. Although they have been known and studied for a long time, they continue to play an important role in recent advances in many subjects, for example in numerical integration, polynomial approximation, or spectral methods (e.g. [MH]). It is interesting to note that they also play an important part in the representation theory of algebras (e.g. [C, EF, GL, RX]). There are several closely related Chebyshev polynomials. Amongst these, the polynomials usually referred to as Chebyshev polynomials of the first kind, and Chebyshev polynomials of the second kind are the ones that often naturally appear; for example, they arise as solutions of special cases of the Sturm-Liouville differential equation or in dimension counting in representation theory (e.g. [BM, E, MZ]).

For Chebyshev polynomials of the first and the second kind, the recursive definition is equivalent to a definition by a determinant formula. Symmetric integer matrices are a key to this definition. Focusing on the polynomials of the second kind, we exhibit some surprising properties of Chebyshev polynomials in relation to these symmetric matrices. In fact the symmetric matrices we consider are adjacency matrices of Dynkin diagrams and extended Dynkin diagrams. Dynkin diagrams play an import role in Lie theory, where they give a classification of root systems. However, they also appear in areas that have no obvious connection to Lie theory as for example in singularity theory where they are linked to Kleinian singularities, or, for example, in representation theory of algebras where they classify symmetric algebras of radical cube zero of finite and tame representation type [B].

The motivation for the study of the Chebyshev polynomials evaluated on matrices comes from the representation theory of the algebras classified in [B]. We begin with a detailed study of the Chebyshev polynomials evaluated on adjacency matrices of Dynkin diagrams,

2000 Mathematics Subject Classification: (primary),

2 KARIN ERDMANN AND SIBYLLE SCHROLL

where we show that in the case of Dynkin diagrams, the families of polynomials are periodic and in the case of the extended Dynkin diagrams the families grow linearly. We then show as an application how the general results we obtain can be applied to the representation theory of the symmetric algebras of radical cube zero. We will see that the Chebyshev polynomials govern the minimal projective resolutions for these algebras and that they give rise to a method to calculate the constituents of minimal projective resolutions of simple modules.

We will now outline the content of this paper. In the next section we recall the definition of Chebyshev polynomials of the second kind, we define the polynomials we will be working with and we introduce the Dynkin diagrams together with a labeling of these diagrams which we will use throughout the paper. In section 3 we evaluate Chebyshev polynomials on the adjacency matrices of Dynkin diagrams and extended Dynkin diagrams. In section 4 a link with the representation theory of symmetric algebras of radical cube zero of finite and tame representation type is described. In particular, we show how the results of section 3 can be used to calculate minimal projective resolutions of the simple modules. Finally in section 5 we show a more general result on Chebyshev polynomials evaluated on positive symmetric matrices.

2. Definitions

2.1. Chebyshev Polynomials. We briefly recall the definition of Chebyshev polynomials of the second kind; good references are [R, S].

The Chebyshev polynomial of the second kind U_{n}(x) of degree n is defined by

U_{n}(x) = sin(n + 1)θ/sinθ where x = cosθ.

From this definition the following recurrence relations with initial conditions can be deduced

U_{n}(x) = 2xU_{n−1}(x) − U_{n−2}(x) with U_{0}(x) = 1 and U_{1}(x) = 2x.

Furthermore an easy calculation shows (see also [S] page 26) that U_{n}(x) = det(2xI_{n} − A_{n}) where A_{n} is an n × n matrix that has zeros everywhere except directly above and directly below the diagonal where all the entries are equal to one.

We will work with the version of the Chebyshev polynomial defined by

f_{n}(x) = det(xI − A_{n})

where A_{n} is defined as above, and I is the identity matrix. Then an easy calculation shows that f_{n}(x) is defined by the recurrence relation f_{n}(x) = xf_{n−1}(x) − f_{n−2}(x) with initial conditions f_{0}(x) = 1 and f_{1}(x) = x. Furthermore, we set f_{−1}(x) = 0. All matrices have entries in ℚ.

2.2. Dynkin diagrams and adjacency matrices. The Dynkin diagrams and extended Dynkin diagrams we are going to consider are the ones of type A, D, E and Ã, D̃, Ẽ as well as the diagrams of type L, L̃, and D̃L (see Appendix).

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 3

Let G be an undirected graph with n vertices labeled by the set {1, 2, …, n}. The adjacency matrix of G is a n×n matrix where the entry in position (i, j) is given by the number of edges between the vertices i and j. Modulo conjugation by a permutation matrix, the adjacency matrix is independent of the choice of labeling.

However, in what follows we work with particular adjacency matrices corresponding to a particular labeling of the graphs. We refer the reader to the Appendix for the labeling of the diagrams we have chosen. In the case of the Dynkin diagrams this labeling corresponds to the Dynkin labeling. It follows from Lemma 3.1 in the next section that our results are, up to permutation, independent of the labeling.

Our goal is to evaluate the Chebyshev polynomials of the second kind on the adjacency matrices of the Dynkin diagrams and the extended Dynkin diagrams as well as the diagrams of type L, L̃, and D̃L.

3. Evaluating Chebyshev polynomials

3.1. Evaluating Chebyshev polynomials on matrices - general results. In this section we list some useful facts about evaluating the Chebyshev polynomials on matrices. We begin with a lemma collecting some straightforward facts.

Lemma 3.1. For any square matrix M, we have Mf_{k}(M) = f_{k}(M)M and for any symmetric matrix S, the matrix f_{k}(S) is symmetric for all k ≥ 0. If T is an invertible n × n matrix then for all n × n matrices M we have f_{k}(T MT^{−1}) = T f_{k}(M)T^{−1}.

Definition 3.2. Let X be a square matrix, we say that the sequence of matrices (f_{k}(X))_{k≥0} is periodic of period ≤ p, if p > 1 and if p satisfies f_{p−1}(X) = 0 and f_{p}(X) = I.

Remark: Suppose that (f_{k}(X))_{k≥0} is periodic of period ≤ p. Then for any integer k, we can write k = qp + r with 0 ≤ r < p, and f_{k}(X) = f_{r}(X).

Lemma 3.3. Assume X is a square matrix such that f_{d}(X) = 0 for some d > 1. Then for 0 ≤ k ≤ d + 1, we have

(∗)  f_{d+k}(X) + f_{d−k}(X) = 0.

Moreover, f_{2d+1}(X) = 0, f_{2d+2}(X) = I and hence f_{2d+3}(X) = X. Therefore the sequence (f_{k}(X))_{k≥0} is periodic, of period ≤ 2d + 2.

Proof: The recursion for the Chebyshev polynomials can be rewritten as

xf_{m}(x) = f_{m+1}(x) + f_{m−1}(x), for m ≥ 0.

Consider now x^{k}f_{d}(x) for 0 ≤ k ≤ d + 1 and substitute x = X. Since f_{d}(X) = 0, induction on k will show that X^{k}f_{d}(X) = f_{d+k}(X) + f_{d−k}(X) = 0, for 0 ≤ k ≤ d + 1.

4 KARIN ERDMANN AND SIBYLLE SCHROLL

The case k = 0 is clear. Assume now that the statement is true for all j where j ≤ k and suppose k < d + 1. Then

0 = X^{k+1}f_{d}(X) =X[X^{k}f_{d}(X)]
=X[f_{d+k}(X) + f_{d−k}(X)]
=f_{d+k+1}(X) + f_{d+k−1}(X) + f_{d−k+1}(X) + f_{d−k−1}(X)
=f_{d+k+1}(X) + X^{k−1}f_{d}(X) + f_{d−k−1}(X)
=f_{d+k+1}(X) + 0 + f_{d−k−1}(X)

as required.

For the last part, let k = d + 1 and recall that f_{−1}(X) = 0, hence f_{2d+1}(X) = 0. Then let k = d, and recall that f_{0}(X) = I which implies f_{2d}(X) = −I. Since f_{2d+1}(X) = 0 we can apply (*) with 2d + 1 instead of d. We then obtain f_{2d+2}(X) + f_{2d}(X) = 0 and hence f_{2d+2}(X) = I and finally f_{2d+3}(X) = X · I − 0 = X. □

If for some d ≥ 1 the matrices f_{d}(X) and f_{d+1}(X) are equal, then periodicity follows by Lemma 3.3.

Lemma 3.4. Assume X is a square matrix such that f_{d}(X) = f_{d+1}(X) for some integer d ≥ 1. Then for 1 ≤ k ≤ d + 1, we have

f_{d+1+k}(X) = f_{d−k}(X).

In particular, f_{2d+2}(X) = 0.

Proof: Assume f_{d}(X) = f_{d+1}(X). Then we have

f_{d−1}(X) = Xf_{d}(X) − f_{d+1}(X) and f_{d+2}(X) = Xf_{d+1}(X) − f_{d}(X)

and hence f_{d−1}(X) = f_{d+2}(X). For the inductive step, assume the statement is true for 1 ≤ m ≤ k. Then

f_{d−k}(X) =Xf_{d−k+1}(X) − f_{d−k+2}(X)
=Xf_{d+k}(X) − f_{d+k−1}(X)
=f_{d+k+1}(X).  □

Some matrices allow a reduction, based on the following lemma, which gives a criterion to determine when a sequence of matrices has linear growth.

Lemma 3.5. Assume X is a square matrix such that for some matrix Z and for some q ≥ 2 we have f_{q}(X) = f_{q−2}(X) + Z, and where ZX = XZ = 2X. Then

(a) for 1 ≤ t ≤ q − 1, we have

f_{q+t}(X) = \{ \begin{matrix}f_{q−2−t}(X) + 2f_{t} & t odd \\ f_{q−2−t}(X) + 2f_{t} + (−1)^{\frac{t}{2} +1}(2I − Z) & t even, \end{matrix}

(b) if Z = 2I , for t ≥ −1, we have f_{2q+t}(X) = 2f_{q+t}(X) − f_{t}(X), (c) if Z = 2I and m = rq + u where −1 ≤ u ≤ q − 2 and r ≥ 2, we have

f_{rq+u}(X) = rf_{q+u}(X) − (r − 1)f_{u}(X).

Corollary 3.6. Assume X is a square matrix such that for some matrix Z we have f_{q}(X) = f_{q−2}(X) + Z, for q ≥ 2 and where ZX = XZ = 2X and where Z ≠ 2I. Then

f_{2q}(X) − f_{2q−2}(X) = \{ \begin{matrix}2Z − 2I & q odd \\ 2Z − 2I + (−1)^{\frac{q−2}{2} +1}(4I − 2Z) & q even. \end{matrix}

Proof: By the Chebyshev recursion formula we have f_{2q}(X) = Xf_{2q−1}(X) − f_{2q−2}(X) and 2q − 1 = q + (q − 1) and 2q − 2 = q + (q − 2). Therefore we can apply Lemma 3.5 a) and the result follows. □

Remark: (I) Later, the matrix Z will often be equal to 2I. In this case (a) is equal to f_{q+t}(X) = f_{q−2−t}(X) + 2f_{t}. Furthermore, an easy calculation shows that (c) becomes f_{rq+u}(X) = rf_{q−2−u}(X) + (r + 1)f_{u}(X).

(II) Observe that part (a) describes f_{k}(X) for q < k ≤ 2q − 1. Since every natural number m ≥ 2q − 1 can be written in the form given in part (c), this gives a description of f_{k}(X) for all k ≥ q. It thus follows from the formula in part (c) that a sequence (f_{k}(X))_{k} that satisfies the hypotheses of Lemma 3.5 with Z = 2I has linear growth.

Proof of Lemma 3.5: (a) We use induction on t. For t = 1, we have

f_{q+1}(X) =Xf_{q}(X) − f_{q−1}(X)
=Xf_{q−2}(X) + XZ − f_{q−1}(X)
=Xf_{q−2}(X) + 2X − f_{q−1}(X)
=f_{q−3}(X) + 2f_{1}(X)

if we recall that f_{1}(X) = X.

For t = 2, we have

f_{q+2}(X) = Xf_{q+1}(X) − f_{q}(X) = X(f_{q−3}(X) + 2f_{1}(X)) − f_{q}(X)
= Xf_{q−3}(X) + 2Xf_{1}(X) − (f_{q−2}(X) + Z)
= f_{q−4}(X) + 2f_{2}(X) + 2I − Z.

For the inductive step suppose first that t is odd. Then we have

f_{q+t+1}(X) =Xf_{q+t}(X) − f_{q+t−1}(X)
=X[f_{q−2−t}(X) + 2f_{t}(X)] − [f_{q−2−(t−1)}(X) + 2f_{t−1}(X) + (−1)^{\frac{t−1}{2} +1}(2I − Z)]
=f_{q−2−(t+1)}(X) + 2f_{t+1}(X) + (−1)^{\frac{t+1}{2} +1}(2I − Z).

Now suppose that t is even. Then we have

f_{q+t+1}(X) =Xf_{q+t}(X) − f_{q+t−1}(X)
=X[f_{q−2−t}(X) + 2f_{t}(X) + (−1)^{\frac{t}{2} +1}(2I − Z)] − [f_{q−2−(t−1)}(X) + 2f_{t−1}(X)]
=f_{q−2−(t+1)}(X) + 2f_{t+1}(X) + (−1)^{\frac{t}{2} +1}(2X − ZX)
=f_{q−2−(t+1)}(X) + 2f_{t+1}(X)

since ZX = 2X.

(b) The case t = −1 follows from part (a). Let t = 0, then

f_{2q}(X) =Xf_{2q−1}(X) − f_{2q−2}(X)
=X[2f_{q−1}(X)] − [2f_{q−2}(X) + f_{0}(X)]
=2f_{q}(X) − I

where the equality f_{2q−2}(X) = f_{0}(X) + 2f_{q−2}(X) follows from part (a). Let t ≥ 1, and assume the equation holds for t − 1 and t − 2, then

f_{2q+t}(X) =Xf_{2q+(t−1)}(X) − f_{2q+(t−2)}(X)
=X[2f_{q+t−1}(X) − f_{t−1}(X)] − [2f_{q+t−2}(X) − f_{t−2}(X)]
=2f_{q+t}(X) − f_{t}(X).

(c) The case r = 2 follows from part (b). Assume now r ≥ 3 and write rq + u = 2q + t where t = (r − 2)q + u. Then by part (b) we have

(∗)  f_{rq+u}(X) = f_{2q+t}(X) = 2f_{q+t}(X) − f_{t}(X).

If r = 3 then 2q + u = q + t and using part (b) again we have f_{q+t}(X) = 2f_{q+u}(X) − f_{u}(X). Substituting this into equation (*) gives

f_{3q+u}(X) = 2[2f_{q+u}(X) − f_{u}(X)] − f_{q+u}(X) = 3f_{q+u}(X) − 2f_{u}(X)

as required.

Now let r > 3. We write (r − 1)q + u = q + t and (r − 2)q + u = t. Then equation (*) gives

f_{rq+u}(X) =2f_{q+t}(X) − f_{t}(X)
=2[f_{(r−1)q+u}(X)] − f_{(r−2)q+u}(X)
=2[(r − 1)f_{q+u}(X) − (r − 2)f_{u}(X)] − [(r − 2)f_{q+u}(X) − (r − 3)f_{u}(X)]
=rf_{q+u}(X) − (r − 1)f_{u}(X)

and this completes the proof. □

Definition 3.7. Given some n × n matrix X, we define X^{0} to be the matrix obtained from X by reversing the entries in each row. In particular, in I^{0} the i, n−i+1-th entries are equal to 1 for all 1 ≤ i ≤ n and all other entries equal to zero.

Note that (X^{0})^{0} = X, and that X^{0} = X · I^{0}. Furthermore, we write I_{n}^{0} if we need to specify the size of the matrix.

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 7

With this we have the following variation of Lemma 3.5. The proof is a straightforward modification of that of Lemma 3.5 and we leave the details to the reader.

Lemma 3.8. Assume X is a square matrix such that for some matrix Z and for some q ≥ 2 we have f_{q}(X) = f_{q−2}(X) + Z, and where XZ = 2X^{0}. Then

(a) for 1 ≤ t ≤ q − 1, we have

f_{q+t}(X) = f_{q−2−t}(X) + 2f_{t}(X)^{0}.

In particular, f_{2q−2}(X) = 2f_{q−2}(X)^{0} + I and f_{2q−1}(X) = 2f_{q−1}(X)^{0},

(b) for t ≥ −1 we have f_{2q+t}(X) = 2f_{q+t}(X)^{0} − f_{t}(X),

(c) if m = rq + u where −1 ≤ u ≤ q − 2 and r ≥ 2, we have

f_{rq+u}(X) = \{ \begin{matrix}rf_{q+u}(X)^{0} − (r − 1)f_{u}(X) & r even \\ rf_{q+u}(X) − (r − 1)f_{u}(X)^{0} & r odd. \end{matrix}

Remark: Note if Z is equal to 2I^{0} then (c) can be rewritten as

f_{rq+u}(X) = \{ \begin{matrix}rf_{q−u−2}(X)^{0} + (r + 1)f_{u}(X) & r even \\ rf_{q−u−2}(X) + (r + 1)f_{u}(X)^{0} & r odd. \end{matrix}

3.2. Substituting type A. In this paragraph we evaluate the Chebyshev polynomials on the adjacency matrix of a Dynkin diagram of type A. This will be the basis for the calculation of almost all the other finite types as well as all the extended types.

Assume A is the adjacency matrix of a Dynkin diagram of A_{n}, n ≥ 2. Then by the Cayley-Hamilton Theorem we know that f_{n}(A) = 0 and by Lemma 3.3 the sequence (f_{k}(A))_{k≥0} is periodic of period ≤ 2n + 2.

Let Θ_{k} be the subset of Θ = {(i, j) : 1 ≤ i ≤ n, 1 ≤ j ≤ n} given by Θ_{k} = {(i, j) : k + 2 ≤ i + j ≤ 2n − k, i + j ≡ k(mod 2), −k ≤ j − i ≤ k}.

We think of this as a subset of ℕ × ℕ. Note that Θ_{k} consists of the points in Θ of parity i + j ≡ k(mod 2) which lie in the rectangle given by the lines

(1)  x + y = k + 2, x + y = 2n − k, y − x = k, y − x = −k

This rectangle has corners (1, k +1), (k +1, 1) and (n−k, n), (n, n−k). In particular, Θ_{n} = ∅ and Θ_{−1} = ∅.

Write E_{ij} for the usual matrix unit.

Proposition 3.9. For −1 ≤ k ≤ n,

(2)  f_{k}(A) = ∑_{(i,j)∈Θ_{k}} E_{ij}.

In particular, f_{n}(A) = 0.

Corollary 3.10. The family (f_{k}(A))_{k}, k ≥ −1 is periodic of period ≤ 2n + 2.

8 KARIN ERDMANN AND SIBYLLE SCHROLL

Proof: It follows from Lemma 3.3 that for 0 ≤ k ≤ n + 1, f_{n+k}(A) + f_{n−k}(A) = 0. and that the sequence (f_{k}(A))_{k≥0} is periodic of period at most 2n + 2. □

Furthermore, f_{k}(A) = 0 if and only if k = mn + m − 1 = m(n + 1) − 1 for m ≥ 0 and the entries of f_{k}(A) are known, for all k ≥ 0.

Proof of 3.9: Let −1 ≤ k ≤ n and let W_{k} be the expression on the right hand side of (2). To prove (2) it is enough to show that

AW_{k} = W_{k+1} + W_{k−1}.

We have (∑_{l=1}^{n−1} E_{l,l+1})E_{ij} = E_{i−1,j}, except in the case i = 1 where (∑_{l=1}^{n−1} E_{l,l+1})E_{1j} = 0. Note, however, that this only occurs for (1, k + 1), that is in the ‘top corner’ of Θ_{k}. Similarly, (∑_{l=1}^{n−1} E_{l+1,l})E_{ij} = E_{i+1,j} except in the case i = n where (∑_{l=1}^{n−1} E_{l+1,l})E_{nj} = 0. This occurs only for (n, n − k), that is the ‘bottom corner’ of Θ_{k}. Therefore AE_{ij} = E_{i−1,j} + E_{i+1,j} for all (i, j) ∈ Θ_{k}, with the two exceptions as described above.

If we visualize the E_{ij} occurring in W_{k} as grid points in the rectangle defined by Θ_{k} then the terms of AW_{k} are obtained by replacing each (i, j) in this rectangle by the two points below and above, namely (i − 1, j) and (i + 1, j) (with the exceptions of the top corner where (i + 1, j) is missing, and the bottom corner where (i − 1, j) is missing).

Following this process we obtain only the points (r, s) with r + s ≡ k − 1(mod 2) and each point (r, s) inside the rectangle defined by (1) is obtained twice. Additionally we get all points (r, s) lying on the lines

x + y = k + 1, x + y = 2n − k + 1, and y − x = k + 1, y − x = −k − 1

exactly once.

Thus we obtain precisely the points corresponding to W_{k+1} and to W_{k−1}, while the points in the intersection appear twice. □

3.3. Substituting type L. In this paragraph we evaluate the Chebyshev polynomials on the adjacency matrix of a diagram of type L. Let L be the adjacency matrix of a diagram of type L_{n}. Then we can express L in terms of A such that L = A + E_{11} where A is the matrix of type A_{n} as in the previous section. We will now express the matrices f_{k}(L) in terms of the matrices f_{k}(A). For k = 1, 2, …, n − 1 we define

T_{k} := ∑_{1≤i,j,i+j≤k+1} E_{ij}.

That is, each entry in the upper left corner, up to the line i + j = k + 1, is equal to 1 and all other entries are zero.

Proposition 3.11. (a) For k = 1, 2, …, n − 1 we have f_{k}(L) = f_{k}(A) + T_{k}.

(b) f_{n}(L) = f_{n−1}(L).

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 9

(c) For 1 ≤ k ≤ n + 1 we have f_{n−1+k}(L) = f_{n−1−k}(L). In particular f_{2n−1}(L) = I and f_{2n}(L) = 0.

(d) We have f_{4n+1}(L) = 0 and f_{4n+2}(L) = I.

Corollary 3.12. The sequence (f_{k}(L))_{k} is periodic of period ≤ 4n + 2.

Proof (a) The proof is by induction. Clearly, f_{1}(L) = f_{1}(A) + T_{1}. Suppose that k < n − 1 and that f_{k}(L) = f_{k}(A) + T_{k} holds. Then

\begin{aligned}f_{k+1}(L) & = & Lf_{k}(L) − f_{k−1}(L) \\ & = & (A + E_{11})(f_{k}(A) + ∑_{i=1}^{k} ∑_{j=1}^{k+1−i} E_{ij}) − f_{k−1}(L) \\ & = & Af_{k}(A) + ∑_{i=1}^{k} ∑_{j=1}^{k+1−i}(E_{i+1j} + E_{i−1j}) + E_{11}f_{k}(A) + E_{11} ∑_{i=1}^{k} ∑_{j=1}^{k+1−i} E_{ij} \\ & & −f_{k−1}(L) \\ & = & Af_{k}(A) + ∑_{i=1}^{k−1} ∑_{j=1}^{k−i} E_{ij} + ∑_{i=2}^{k+1} ∑_{j=1}^{k+2−i} E_{ij} + ∑_{j=1}^{k+1} E_{1j} − f_{k−1}(L) \\ & = & Af_{k}(A) − f_{k−1}(A) + ∑_{i=1}^{k−1} ∑_{j=1}^{k−i} E_{ij} + ∑_{i=1}^{k+1} ∑_{j=1}^{k+2−i} E_{ij} − ∑_{i=1}^{k−1} ∑_{j=1}^{k−i} E_{ij} \\ & = & f_{k+1}(A) + ∑_{i=1}^{k+1} ∑_{j=1}^{k+2−i} E_{ij}. \end{aligned} .

(b) The calculation in part (a) also holds when k = n − 1 and therefore

f_{n}(L) = Lf_{n−1}(L) − f_{n−2}(L)
= f_{n}(A) + ∑_{i=1}^{n} ∑_{j=1}^{k+1−i} E_{ij}
= 0 + f_{n−1}(L_{n}).

Part (c) and (d) follow from Lemma 3.4. □

Remark 3.13. (I) We keep the record that the calculation in part (a) shows that for k < n − 1

E_{11}T_{k} + AT_{k} − T_{k−1} = T_{k+1}.

(II) Later we have to use the matrices of type L but where the labeling is reversed. Then we have the description as in the above proposition, where the only change is that T_{k} is replaced by B_{k} := I^{0}T_{k}. This matrix is obtained from B_{k} by reflecting in the line i + j = n + 1. For this, the calculation in part (a) shows that for k < n − 1

E_{nn}B_{k} + AB_{k} − B_{k−1} = B_{k+1}.

3.4. Substituting extended type L. Fix n ≥ 2 and let L̃ = L̃_{n} be the adjacency matrix of a diagram of type L̃_{n} as described in section 2.2. In this paragraph we evaluated the Chebyshev polynomial on L̃ and show that the family f_{k}(L̃) is of linear growth.

We note that L̃ can be expressed in terms of the adjacency matrix A of A_{n}. Namely, L̃ = A + E_{11} + E_{nn}. The next Proposition shows that the terms of f_{k}(L̃_{n}) are a sum of f_{k}(A) and an upper and a lower triangular matrix whose entries are all equal to 1. Recall the definition of T_{k} and B_{k} from Section 3.3.

Proposition 3.14. For 1 ≤ k ≤ n − 1, we have f_{k}(L̃) = f_{k}(A) + T_{k} + B_{k}.

Proof: We proof the result by induction. The result holds for k = 1 and a direct calculation shows that it also holds for k = 2. Suppose it holds for all l ≤ k. Then by definition we have f_{k+1}(L̃) = Xf_{k}(L̃) − f_{k−1}(L̃) and by induction hypothesis this is equal to

(A + E_{11} + E_{nn})(f_{k}(A) + T_{k} + B_{k}) − f_{k−1}(A) − T_{k−1} − B_{k−1}.

To prove the stated formula we need

(E_{11} + E_{nn})(f_{k}(A) + T_{k} + B_{k}) + A(T_{k} + B_{k})

−T_{k−1} − B_{k−1} = T_{k+1} + B_{k+1}

This is true by the record kept in remark 3.13. □

Let U be the n × n matrix all of whose entries are equal to 1. Recall also the definition of I^{0} and X^{0}, and note that 2XI^{0} = 2X^{0}. As special cases of the previous, and by applying Lemma 3.8, we have therefore

Corollary 3.15. We have that f_{n−2}(L̃) = U − I^{0}, and f_{n−1}(L̃) = U, and f_{n}(L̃) = U + I^{0}. Hence

f_{n}(L̃) = f_{n−2}(L̃) + 2I^{0}

and the sequence (f_{k}(L̃))_{k≥0} has linear growth.

3.5. General setup for the remaining infinite families. All remaining infinite families of Dynkin and extended Dynkin types are based on the above calculations and fit into a more general set-up described in this section. Namely, in this section we substitute a symmetric block matrix X of the form

X = (\begin{matrix}0 & S \\ S^{t} & W \end{matrix} ) ,

where we assume that SS^{t}S = 2S, and hence that S^{t}S and SS^{t} are projections. Assume further that S has rank one. Then for any matrix M of the appropriate size, SMS^{t} is a scalar multiple of SS^{t}.

The following lemma is a straightforward calculation.

Lemma 3.16. Write f_{k}(X) as block matrix, f_{k}(X) = ( \begin{matrix}H_{k} & S_{k} \\ (S_{k})^{t} & W_{k} \end{matrix} ) . Then we have

H_{k+1} =SS_{k}^{t} − H_{k−1}
S_{k+1} =SW_{k} − S_{k−1}
W_{k+1} =S^{t}S_{k} + W W_{k} − W_{k−1}.

We can express the adjacency matrices of the remaining infinite families in question in terms of S and W and we will apply Lemma 3.16 as follows. Let ε_{1} be the row vector of length n whose first entry is equal to 1 and whose other entries are all equal to 0.

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 11

(1) For type D_{m}, m ≥ 3, of size m, the adjacency matrix of type D_{m} is given by choosing W to be of type A_{n} with n = m − 2, and S to be the matrix with two rows, each row equal to ε_{1}.

(2) For type D̃_{m+1}, m ≥ 4, of size m + 2, we take S as in (1), and for W we take the matrix D of type D_{m} but with the labeling reversed, we will call this matrix V, that is V = I^{0}DI^{0}.

(3) For type Ã_{n}, n ≥ 3, of size n + 1, we take W = A_{n} and S to be the matrix with one row equal to ε_{1}.

(4) For type D̃L_{m}, m ≥ 3, of size m, we take W = I^{0}L_{n}I^{0} with n = m − 2, that is W is L_{n} but with reversed order, and we take S as in (1) so that S is a two row matrix with both rows equal to ε_{1}.

Take X as above, and S_{k}, W_{k} and H_{k} as in the recursion in Lemma 3.16. We will now calculate the first few terms explicitly.

Definition 3.17. We define invariants c and λ_{c} of X, to be the first integer c > 1, and the scalar λ_{c}, such that Sf_{c}(W)S^{t} = λ_{c}SS^{t} is non-zero.

Proposition 3.18. Let c be as above and let 1 ≤ k ≤ c + 2. Then (a)

S_{k} = S(∑_{i≥0} f_{k−1−2i}(W)), W_{k} = f_{k}(W) + ∑_{i≥0} ψ_{k−2−2i}

where ψ_{x} = ∑_{0≤r≤x} f_{r}(W)S^{t}Sf_{x−r}(W).

(b) For k < c + 2

H_{k} = \{ \begin{matrix}0 & k odd \\ I & k ≡ 0 mod 4 \\ SS^{t} − I & k ≡ 2 mod 4. \end{matrix}

(c)

H_{c+2} = \{ \begin{matrix}(1 + λ_{c})SS^{t} − H_{c} & c even \\ λ_{c}SS^{t} & c odd. \end{matrix}

We make the convention that ψ_{x} = 0 and f_{x}(W) = 0 if x < 0.

Proof: (a) Induction on k. The cases k = 1 and k = 2 are clear. So assume true for all j with 1 ≤ j ≤ k, and suppose k < c + 2, then

S_{k+1} = SW_{k} − S_{k−1} = S(f_{k}(W) + ∑_{i≥0} ψ_{k−2−2i}) − S(∑_{j≥0} f_{k−2−2j}(W)).

Let x ≤ k − 2, since k < c + 2 we have x < c, and therefore Sf_{x−y}(W)S^{t} = 0 for all y ≥ 0. This implies that almost all terms of Sψ_{x} are zero, and

Sψ_{x} = SS^{t}Sf_{x}(W) = 2Sf_{x}(W).

Substituting this gives

S_{k+1} = Sf_{k}(W) + 2S(∑_{i≥0} f_{k−2−2i}(W)) − S(∑_{j≥0} f_{k−2−2j}(W)

12 KARIN ERDMANN AND SIBYLLE SCHROLL

which proves the claim.

Next, consider W_{k+1}, substituting the terms using the induction hypothesis we get

W_{k+1} = S^{t}S[∑_{i≥0} f_{k−1−2i}(W)] + W f_{k}(W) + ∑_{i≥0} W ψ_{k−2−2i}

− f_{k−1}(W) − ∑_{i≥0} ψ_{k−3−2i}.

By the recursion, W f_{k}(W) − f_{k−1}(W) = f_{k+1}(W). Moreover, it also follows from the recursion that, for x ≥ 0,

W ψ_{x} − ψ_{x−1} = ψ_{x+1} − S^{t}Sf_{x+1}(W).

Substituting these, and noting that the terms −S^{t}Sf_{x+1}(W) cancel for all x = k − 2 − 2i gives the claim.

(b) and (c) The cases k = 1 and k = 2 are clear. For the inductive step, we have if k < c + 2 that

H_{k+1} = S(S_{k}^{t}) − H_{k−1} = S(∑_{i≥0} f_{k−1−2i}(W))S^{t} − H_{k−1}.

With the assumption, k − 1 − 2i ≤ c for all i ≥ 0, and the only way to get this equal to c is for k = c + 1 and i = 0. Hence

S ∑_{i≥0} f_{k−1−2i}(W)S^{t} = \{ \begin{matrix}Sf_{c}(W)S^{t} & k − 1 = c odd \\ Sf_{c}(W)S^{t} + 2SS^{t} & k − 1 = c even \\ SS^{t} & k − 1 < c, k − 1 even \\ 0 & else \end{matrix}

and recalling that Sf_{c}(W)S^{t} = λ_{c}SS^{t}, this gives the claim. □

3.6. Substituting type D. In this paragraph we evaluate the Chebyshev polynomials on the adjacency matrices of Dynkin diagrams of type D. Let X be the matrix associated to type D_{m}, such that S and W = A_{n} for m = n+2 are as described in section 3.5. According to Proposition 3.9 and the remark on Θ_{k} preceding it, the parameters defined in Definition 3.17 are c = 2n and λ_{c} = 1. Therefore we obtain the expressions of f_{k}(D_{m}) for k ≤ 2n + 2 from Proposition 3.18.

Lemma 3.19. For 1 ≤ k < 2n + 1, f_{k}(D_{m}) ≠ 0 and f_{2n+1}(D_{m}) = 0.

Proof: First, we observe that

(3)  ∑_{i≥0} f_{2n−2i}(W) = 0, ∑_{i≥0} f_{2n−1−2i}(W) = 0.

Namely, each of these is a sum of terms of the form f_{n+t}(W)+f_{n−t}(W) for some 0 ≤ t ≤ n+1, and by Lemma 3.3 this sum is equal to zero. Furthermore, if 1 ≤ r < 2n−1 then the first row of ∑_{i≥0} f_{r−2i}(W) is non-zero: for example, the entries of the first row of f_{0}(W) (or f_{1}(W)) do not cancel.

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 13

We start by showing that for 1 ≤ k < 2n + 1, f_{k}(D_{m}) ≠ 0. Suppose 1 ≤ k < 2n + 1. Then by Proposition 3.18 we have

S_{k} = S[∑_{i≥0} f_{k−1−2i}(W)].

This is the two-row matrix where both rows are equal to the first row of ∑_{i≥0} f_{k−1−2i}(W). By the above this is non-zero except when k = 2n.

Thus for k < 2n we have S_{k} ≠ 0 and therefore f_{k}(D_{m}) ≠ 0. If k = 2n, then k is even and by Proposition 3.18H_{k} ≠ 0, and so f_{2n}(D_{2m}) ≠ 0.

Finally consider f_{2n+1}(D_{m}). It follows from (3) that S_{2n+1} = 0, and Proposition 3.18 implies H_{2n+1} = 0. Recall that f_{2n+1}(W) = 0, and thus

(4)  W_{2n+1} = ∑_{i≥0} ψ_{2n−1−2i} = ∑ f_{r}(W)SS^{t}f_{s}(W)

where the sum is over all r, s ≥ 0 with r + s ≤ 2n − 1 and r + s odd.

Given such r, s, define r′ and s′ by r + r′ = 2n and s′ + s = 2n. Then for 0 ≤ k ≤ n + 1, r = n − k implies r′ = n + k and similarly s = n − k implies s′ = n + k or vice versa. This implies that f_{r}(W) + f_{r′}(W) = 0 and f_{s}(W) + f_{s′}(W) = 0.

It is clear that both r + s′ and s + r′ are odd. We now claim that precisely one of r + s′ and r′ + s is strictly less than 2n.

Assume for a contradiction that r′ + s ≥ 2n and r + s′ ≥ 2n. Then because both expressions are odd, they are both strictly larger than 2n and we have r′ + s > 2n = r′ + r and thus s > r. But r + s′ > 2n = s + s′ implies r > s, a contradiction.

We get a similar contradiction if we assume r′ + s < 2n and r + s′ < 2n and therefore exactly one of r + s′ and r′ + s is strictly less than 2n.

Suppose now that r′ + s < 2n. Then the terms in (3) where labels of the form r, r′, s, s′ occur are precisely

f_{r}(W)S^{t}Sf_{s}(W) + f_{r′}(W)S^{t}Sf_{s}(W).

But this expression is zero since f_{r}(W) + f_{r′}(W) = 0. □

The following two lemmas give more precise information about particular entries of f_{k}(D_{m}).

Lemma 3.20. We have

f_{2n}(D_{m}) = \{ \begin{matrix}I & n even \\ (\begin{matrix}I_{2}^{0} & 0 \\ 0 & I_{n} \end{matrix}) & n odd. \end{matrix}

Proof: Consider W_{2n} = f_{2n}(W) + ∑_{i} ψ_{2n−2−2i}. We know f_{2n}(W) = I and so we must show that ∑ ψ_{2n−2−2i} = 0. However this follows directly from an argument similar to the one in the previous Lemma. Similarly one shows that S_{2n} = 0. The result then follows from Proposition 3.18. □

Lemma 3.21. Assume 1 ≤ k ≤ 2n. Then the last row of f_{k}(D_{m}) is equal to

\begin{matrix}(0 0 ε_{n−k} ) & 1 ≤ k < n \\ (1 1 0 ... 0) & k = n \\ (0 0 ε_{k−n} ) & n < k ≤ 2n. \end{matrix}

Hence the last row of f_{k}(D_{m}) reversed is

\begin{matrix}(ε_{k+1} 0 0) & 1 ≤ k < n \\ (0 ... 0 1 1) & k = n \\ (ε_{n−(k−n)+1} 0 0) & n < k ≤ 2n. \end{matrix}

Proof: (1) We need the last column of S_{k}, the transpose of this gives the first two entries for the required last row.

Recall S_{k} = S[∑_{i} f_{k−1−2i}(W)]. This is the 2-row matrix where each row is equal to the first row of ∑_{i} f_{k−1−2i}(W). We need only the 1n entry of this sum.

The 1n entry of f_{x}(W) is 1 for x = n − 1 and −1 for x = n + 1 and is zero for any other x ≤ 2n.

Case 1 Assume n is odd. Then f_{x}(W)_{1n} = 0 for all odd x ≤ 2n. Set x = k − 1 − 2i, so for k even, the last column of S_{k} is zero.

Now let k be odd, and consider the x = k − 1 − 2i. We have f_{x}(W)_{1n} = 1 for x = n − 1 and = −1 for x = n + 1 and is zero otherwise. It follows that the 1n entry of ∑_{i} f_{k−1−2i}(W) in this case is equal to 1 if k − 1 = n − 1 and is zero otherwise, by cancelation.

This shows that the last column of S_{k} is zero unless k = n and then it is of the form \binom{1}{1}.

Case 2 Assume n is even. Then for k odd (all x even), as before the last column of S_{k} is zero. Assume k is even, consider x = k − 1 − 2i. We have f_{x}(W)_{1n} as before. It follows that the 1n entry of ∑_{i} f_{k−1−2i}(W) is equal to 1 if k − 1 = n − 1 and zero otherwise. Again, the last column of S_{k} is zero unless k = n and then it is of the form \binom{1}{1}.

(2) Now we determine the last row of W_{k}, recall from Proposition 3.18 that W_{k} = f_{k}(W) + ∑_{i≥0} ψ_{k−2−2i}.

Assume first that 1 ≤ k ≤ n. We claim that then the last row of ∑_{i} ψ_{k−2−2i} is zero, hence the last row of W_{k} is equal to ε_{n−k} for k < n, and is zero for k = n.

Consider (Sf_{a}(W))^{t}(Sf_{b}(W)). If this has last row non-zero then we must have that the first row of f_{a}(W) has non-zero 1n entry. This occurs only for a = n − 1 or a = n + 1 but here we have only a + b ≤ k − 2 ≤ n − 2. So this has last row equal to zero. This implies the claim.

Now consider k = n + r where 1 ≤ r ≤ n. Then f_{n+r}(W) = −f_{n−r}(W) and this has last row equal to −ε_{r}. We claim that ∑_{i} ψ_{n+r−2−2i} = 2ε_{r}. [This will imply the statement.]

We use induction on r. Assume first that r = 1.

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 15

Then ∑_{i} ψ_{n−1−2i} = ψ_{n−1} + ∑_{i>0} ψ_{n−1−2i}. In the sum, the last row is zero (by the argument in the previous case). The last row of ψ_{n−1} has non-zero contribution only from f_{n−1}(W)S^{t} and this is 2ε_{1}

For the inductive step, write

∑_{i} ψ_{n+r−2−2i} = ψ_{n+r−2} + ∑_{i≥0} ψ_{n+r−4−2i}.

By the inductive hypothesis the sum is equal to 2ε_{r−2}. Now consider ψ_{n+r−2}. This has only two terms with non-zero last row, and the last row of ψ_{n+r−2} is equal to the last row of

(Sf_{n−1}(W))^{t}Sf_{r−1} + (Sf_{n+1}(W))^{t}Sf_{r−3}.

This is equal to 2ε_{r} − 2ε_{r−2}. In total we get the stated answer. □

Using 4.3 with d = 2n+1, the previous three Lemmas imply that f_{2m−3−k}(D_{m}) = f_{2m−3+k}(D_{m}) for 0 ≤ k ≤ 2m − 3; and the periodicity of (f_{k}(D_{m}))_{k≥0} follows.

Corollary 3.22. The family (f_{k}(D_{m})) is periodic of period ≤ 2(2m − 2).

3.7. Substituting type D̃. Let X be of type D̃_{m+1} of size m + 2 = n + 4. That is, X = (\begin{matrix}0 & S \\ S^{t} & V \end{matrix}), where V is equal to D_{n+2} with reversed order (explicitly V = I^{0}D_{n+2}I^{0}),

and where S = (\begin{matrix}1 & 0 & … & 0 \\ 1 & 0 & … & 0 \end{matrix}) of size 2×m. . Recall from 3.17 the definition of the invariants c and λ_{c}.

Lemma 3.23. For X as described above, we have c = 2n and λ_{c} = 1.

Proof: The parameter λ_{c} is the 11 entry of f_{c}(V), which is equal to the nn entry of f_{c}(D_{m}) when this is non-zero the first time. The nn entry of f_{k}(D_{m}) is the nn entry of the matrix W_{k} occurring in the recursion for type D_{m}, with the notation of section 3.6.

Let k ≤ 2n. We know from Proposition 3.18 that W_{k} = f_{k}(W) + ∑_{i≥0} ψ_{k−2−2i}. We notice that (f_{k}(W))_{nn} ≠ 0 only if f_{k}(W) = ±I and this occurs for the first time when k = 2n.

Now consider the nn entry of ψ_{x} for x ≤ 2n − 2. For this we need the nn entry of (Sf_{r}(W))^{t}(Sf_{s}(W) for r + s = x ≤ 2n − 2. This is equal to

(∗)  2(f_{r}(W))_{1n} · f_{s}(W)_{1n}.

The 1n entry of any f_{t}(W) for t ≤ 2n − 2 is only non-zero for t = n − 1 or n + 1. So the number (*) is zero for r+s < 2n−2. If r+s = 2n−2 then it is only non-zero for r = s = n−1 and then it is equal to 1. □

By Proposition 3.18 we now obtain the expressions for the matrices constituting f_{k}(X) for 1 ≤ k ≤ 2n + 2, and this is enough to prove linear growth. Recall from Definition 3.7 the definition of I_{2}^{0}.

16 KARIN ERDMANN AND SIBYLLE SCHROLL

Proposition 3.24. We have

f_{2n+2}(X) − f_{2n}(X) = \{ \begin{matrix}2I & n odd \\ 2Ĩ & n even \end{matrix}

where

Ĩ = (\begin{matrix}I_{2}^{0} & 0 & 0 \\ 0 & I_{n} & 0 \\ 0 & 0 & I_{2}^{0} \end{matrix})

Hence the sequence (f_{k}(X))_{k} has linear growth.

Proof: By 3.18, using c = 2n and λ_{c} = 1, we have H_{2n+2} − H_{2n} = 2SS^{t} − 2H_{2n} = 2I_{2} for n odd, and H_{2n+2} − H_{2n} = 2(SS^{t} − I_{2}) if n is even.

Now consider S_{2n+2} − S_{2n}. Here most of terms of the sum cancel and we obtain S_{2n+2} − S_{2n} = Sf_{2n+1}(V) = S · 0 = 0.

Finally, for V_{2n+2} − V_{2n} most of the terms of the sum cancel as well and we are left with V_{2n+2} − V_{2n} = f_{2n+2}(V) − f_{2n}(V) + ψ_{2n}. Furthermore, we have

f_{2n+2}(V) − f_{2n}(V) = −2f_{2n}(V) = \{ \begin{matrix}−2I_{n+2} & n even \\ −2U & n odd \end{matrix}

where U is the matrix f_{2n}(D_{m}) reversed.

It remains to calculate ψ_{2n}. For that we note that

(Sf_{0}(V))^{t}(Sf_{2n}(V)) =2E_{11} = (Sf_{2n}(V))^{t}(Sf_{0}(V))
(Sf_{1}(V))^{t}(Sf_{2n−1}(V)) =2E_{22} = (Sf_{2n−1}(V))^{t}(Sf_{1}(V))
. . . . . .
(Sf_{n−1}(V))^{t}(Sf_{n+1}(V)) =2E_{nn} = (Sf_{n+1}(V))^{t}(Sf_{n−1}(V))
(Sf_{n}(V))^{t}(Sf_{n}(V)) =2(E_{n+1,n+1} + E_{n+1,n+2} + E_{n+2,n+1} + E_{n+2,n+2}).

Thus ψ_{2n} = (\begin{matrix}4I_{n} & 0 \\ 0 & 2SS^{t} \end{matrix}), and

V_{2n+2} − V_{2n} = \{ \begin{matrix}2I_{n+2} & n odd \\ (\begin{matrix}2I_{n} & 0 \\ 0 & 2(SS^{t} − I_{2}) \end{matrix}) & n even \end{matrix}

The conclusion follows from Lemma 3.5 with Z = 2I for n odd. For n even, we have Z = 2Ĩ and q = 2n + 2. Since this is an even number, it follows from Corollary 3.6 that f_{4n+4}(X) − f_{4n+2}(X) = 2I, and linear growth follows from Lemma 3.5. □

3.8. Substituting extended type Ã. Let now X be the matrix of type Ã_{n}, that is X is an n + 1 × n + 1 matrix of the form X = (\begin{matrix}0 & S \\ S^{t} & W \end{matrix} ), with

W = A_{n} and S = (1 0 … 0 1) .

where S is a 1 × n matrix. One checks that the invariants c and λ_{c} of X as defined in 3.17 are as follows.

Lemma 3.25. Let 1 ≤ c be minimal such that Sf_{c}(W)S^{t} = λ_{c}SS^{t} ≠ 0. Then c = n − 1, and λ_{c} = 1.

CHEBYSHEV POLYNOMIALS ON SYMMETRIC MATRICES 17

Therefore, by Proposition 3.18 we get the matrices f_{k}(X) for 1 ≤ k ≤ n + 1.

Proposition 3.26. We have

f_{n+1}(X) − f_{n−1}(X) = 2I.

Hence the sequence (f_{k}(X))_{k} has linear growth.

Proof: We have H_{n+1} − H_{n−1} = 2. Furthermore, S_{n+1} − S_{n−1} = Sf_{n}(W) = 0. Consider W_{n+1} − W_{n−1}, this is equal to

f_{n+1}(W) − f_{n−1}(W) + ψ_{n−1}

(since most of the terms of the sums cancel).

We know from type A that f_{n+1}(W)−f_{n−1}(W) = −2I^{0}. A straightforward calculation shows that

ψ_{n−1} = 2(I + I^{0}).

Combining these gives the first statement. We get linear growth from Lemma 3.5. □

3.9. Substituting type D̃L. Let X be the adjacency matrix of type D̃L_{m} with m vertices, and m = n + 2. With the notation of section 3.5 X has the following blocks: S = ( \begin{matrix}1 & 0 & 0 & ... & 0 \\ 1 & 0 & 0 & ... & 0 \end{matrix} ), and W = V where V = I^{0}LI^{0} is the adjacency matrix of type L_{n} reversed.

Recall that f_{2n}(V) = 0 and f_{k}(V) ≠ 0 for 1 ≤ k < 2n. Furthermore f_{2n−1}(V) = I. The invariants c and λ_{c} of X, given by λ_{c}SS^{t} = Sf_{c}(V)S^{t} ≠ 0, and Sf_{k}(V)S^{t} = 0 for 1 < k < c are as follows

Lemma 3.27. We have c = 2n − 1 and λ_{c} = 1.

Proof The parameter Sf_{k}(V)S^{t} is the (1, 1) entry of f_{k}(V) which is equal to the (n, n) entry of f_{k}(L_{n}). It follows from Section 3.3 that this entry is equal to 1 for c = 2n − 1 and equal to 0 for 1 < k < 2n − 1. □

We can now apply Proposition 3.18:

Proposition 3.28. We have

f_{2n+1}(X) − f_{2n−1}(X) = Z

where

Z = (\begin{matrix}SS^{t} & 0 \\ 0 & 2I_{n} \end{matrix})

and XZ = ZX = 2X. Hence the sequence (f_{k}(X))_{k} has linear growth.

Proof: Using the formulae from Proposition 3.18 with c = 2n−1, we have H_{2n+1} −H_{2n−1} = Sf_{2n−1}(V)S^{t} = SS^{t}. Next, consider S_{2n+1} − S_{2n−1}. Here most of the sum cancels and the only expression remaining is

Sf_{2n}(V) = S · 0 = 0.

Consider now V_{2n+1} − V_{2n−1}. This is equal to f_{2n+1}(V) − f_{2n−1}(V) + ψ_{2n−1}.

By Proposition 3.11 c) combined with Lemma 3.3, we have f_{2n+1}(V) − f_{2n−1}(V) = −2I. We now calculate ψ_{2n−1}, this is equal to

ψ_{2n−1} = 2[∑_{r=0}^{n−1}(Sf_{r})^{t} · (Sf_{2n−1−r})].

Similarly to the proof of Proposition 9.2 we find that (Sf_{r})^{t} · (Sf_{2n−1−r}) = 2E_{r+1,r+1}, for 0 ≤ r ≤ n − 1. Hence V_{2n+1} − V_{2n−1} = −2I + 4I = 2I, as required. This proves that the difference f_{2n+1}(X)−f_{2n−1}(X) is as stated, and one checks that XZ = 2X. Now by applying Corollary 3.6 first with q′ = 2q we obtain f_{q′}(X) − f_{q′−2}(X) = Z′ where Z′ = (\begin{matrix}I_{2}^{0} & 0 \\ 0 & 2I_{n} \end{matrix}) and where Z′X = XZ′ = 2X. Then we set q′′ = 2q′ = 4q and by Corollary 3.6 we obtain f_{q′′} (X) − f_{q′′−2}(X) = 2I and then by Lemma 3.5 linear growth follows. □

3.10. Substituting type E. Similar results can be shown for type E. However, all we need for the application to representation theory that we have in mind, are some simple facts that an easy calculation by hand can provide. Namely, we need to know when f_{k}(E_{i}) is equal to zero for the first time when i = 6, 7 or 8 where E_{i} for i = 6, 7, 8 is the adjacency matrix of the Dynkin diagram of type E as given in section 2.2. This happens exactly for f_{11}(E_{6}), f_{17}(E_{7}) and f_{29}(E_{8}).

Furthermore we need the explicit expressions of the matrices preceding this first zero matrix. They are given by

f_{10}(E_{6}) = (ε_{6}, ε_{5}, ε_{3}, ε_{4}, ε_{2}, ε_{1})^{T} ,
f_{16}(E_{7}) = I_{7},
f_{10}(E_{8}) = I_{8}

where ε_{i} is as before, that is, it is the row vector that has a one in place i and zero elsewhere.

3.11. Summary. In the preceding sections we have calculated explicitly the Chebyshev polynomials evaluated on the adjacency matrices of the Dynkin diagrams of types A, D, E, of the extended Dynkin diagrams Ã, D̃, as well as on the diagrams of type L, L̃ and D̃L. In particular we have shown that the Dynkin diagrams and the type L diagram give rise to periodic families and that the extended Dynkin diagrams and the diagrams of types L̃ and D̃L, give rise to families that have linear growth.

Theorem 3.29. Let D be the adjacency matrix of a Dynkin diagram of type A, D, E or a diagrams of type L. Then for r ≥ 1, we have f_{k}(D) = 0 if and only if k = rh − 1 where h denotes the Coxeter number of the associated diagram.

Theorem 3.30. Let D be the adjacency matrix of an extended Dynkin diagram or of a diagram of type L̃ or D̃L. Then for m = rq + u where −1 ≤ u ≤ q − 2 and 2 ≤ r we have the recurrence relation

f_{rq+u}(D) = rf_{q+u}(D) − (r − 1)f_{u}(D)

(a) if D = Ã_{n} then q = n + 1;

(b) if D = D̃_{n} then q = 2n − 4 for n even and q = 4n − 8 for n odd;

(c) if D = L̃_{n} then q = n;

(d) if D = D̃L_{n} then q = 8n − 4;

(e) if D = Ẽ_{6} then q = 12, if D = Ẽ_{7} then q = 72, and if D = Ẽ_{8} then q = 60.

Remark: It is easily checked that for D one of the extended types Ẽ with q given as above we have f_{q}(D) − f_{q−2}(D) = 2I.

4. Application to representation theory

In this section we show how the previous results can be used to calculate the minimal projective resolutions of the simple modules of a class of symmetric algebras – namely those that are of radical cube zero and of tame or of finite representation type. Our method gives the indecomposable projective components in each degree of the projective resolutions through a description of the radical layers of the syzygies.

Let K be a field and let Λ be a finite dimensional K-algebra. Then Λ is symmetric if there exists a linear map ν : Λ → k such that for all a, b ∈ Λ, ν(ab) = ν(ba) such that Ker(ν) contains no non-zero left or right ideal. Recall that the Jacobson radical J(Λ) of the algebra is the smallest ideal of Λ such that the quotient is semisimple.

Let Λ be a finite dimensional symmetric K-algebra such that J^{3}(Λ) = 0. We assume that Λ is indecomposable, and that J^{2}(Λ) ≠ 0. These algebras are classified in [B] according to the minimal projective resolution of non-projective finitely generated Λ-modules. Namely, if S_{1}, S_{2}, …, S_{n} are the simple Λ-modules, let E_{n} = (e_{ij})_{i,j=1,...,n} where e_{ij} = dim Ext_{Λ}^{1}(S_{i}, S_{j}), which is a symmetric matrix. Then if the largest eigenvalue λ of E_{n} is > 2, the dimensions in the minimal projective resolutions of the non-projective finite-dimensional Λ-modules are unbounded, and the algebra is of wild representation type. If λ = 2, the algebra is of tame representation type and the minimal projective resolutions either are bounded or grow linearly, and if λ < 2 they are bounded. In the latter two cases the algebras are classified by Dynkin diagrams A, D, E or the graph L for the finite representation type, and by the extended Dynkin diagrams Ã, D̃, Ẽ or the graphs L̃ and D̃L for the tame representation type.

To each of these diagrams D we associate the quiver Q(D), which is obtained by replacing each edge of the diagram by a pair of arrows pointing in opposite directions. Let K be an algebraically closed field and let KQ(D) be the path algebra of Q(D). Then one has an ideal I of KQ(D) such that the corresponding quotient algebra Λ = KQ(D)/I is a symmetric algebra such that J^{3}(Λ) = 0.

We recall some properties of indecomposable Λ-modules as stated in [B]. The Loewy length of a Λ-module is at most 3. If P is a projective indecomposable Λ-module, then rad^{2}(P) = soc(P) ≅ hd(P). If M is indecomposable but not simple or projective, then the Loewy length of M is equal to 2 and we denote by d(M) the column vector ( \begin{matrix}α(M) \\ β(M) \end{matrix} ) where α(M) = \underline{dim} hd(M) and β(M) = \underline{dim} rad(M) where \underline{dim}V denotes the dimension vector of the finite dimensional Λ-module V. This is the column vector of length n whose ith entry corresponds to the multiplicity of the simple module S_{i} as a composition factor in V. If S is a simple Λ-module then α(S) = \underline{dim} S and β(S) = 0. And if P (S) is a projective cover of S

then the dimension vector of its three radical layers are described by the vector ( \begin{matrix}α(S) \\ E_{n}α(S) \\ α(S) \end{matrix} ).

More generally, the projective cover P (M) of a non-projective indecomposable Λ-module M has in its radical layers the dimension vectors α(M), E_{n}α(M) and α(M). Therefore if Ω(M) is non-simple it has in its radical layers the dimension vectors E_{n}α(M) − β(M) and α(M). Furthermore, d(Ω(M)) = Bd(M) with B = ( \begin{matrix}E_{n} & −I_{n} \\ I_{n} & 0 \end{matrix} ) where I_{n} is the identity n × n matrix. Therefore for M an indecomposable non-projective Λ-module we get the recurrence relation

d(Ω^{k}(M)) = B^{k}d(M)

if none of the Ω^{j}(M) for j = 0, …, k are simple Λ-modules. Furthermore, we observe that the entries of the matrix B^{k} can be given in terms of Chebyshev polynomials.

Lemma 4.1. Let M be an n × n matrix and let B = ( \begin{matrix}M & −I_{n} \\ I_{n} & 0 \end{matrix} ). Then for i ≥ 0,

B^{i} = ( \begin{matrix}f_{i}(M) & −f_{i−1}(M) \\ f_{i−1}(M) & −f_{i−2}(M) \end{matrix} )

where f_{i}(x) is the Chebyshev polynomial of the second-kind defined by the recurrence relation f_{i}(x) = xf_{i−1}(x) − f_{i−2}(x) and with initial conditions f_{0}(x) = 1 and f_{1}(x) = x.

Proof: By definition of B we have f_{0}(M) = I_{n} and f_{1}(M) = M and we pose f_{−1}(M) = 0. Suppose now the result holds for i. Then

B^{i}B = ( \begin{matrix}f_{i}(M) & −f_{i−1}(M) \\ f_{i−1}(M) & −f_{i−2}(M) \end{matrix} ) ( \begin{matrix}M & I_{n} \\ −I_{n} & 0 \end{matrix} ) = ( \begin{matrix}f_{i+1}(M) & −f_{i}(M) \\ f_{i}(M) & −f_{i−1}(M) \end{matrix} ) . □

If Ω(M) is simple then Ω(M) = soc(P (M)) and d(Ω(M)) = (α(M), 0)^{T}, however Bd(M) = (0, α(M))^{T}. Thus we know that Ω^{k}(M) is simple if the first n entries of the vector B^{k}d(M) are zero and if there is only one non-zero entry in the n + 1 to 2n components of B^{k}d(M).

Let Λ be one of the algebras defined above. We say that Λ is of type A, D, E, L, Ã, D̃ etc. (or A_{n}, D_{n}, E_{6}, E_{7}, E_{8}, L_{n}, Ã_{n}, D̃_{n} etc. if we need to specify the number of vertices of the diagram) if the underlying diagram of the quiver of Λ is of that type.

The following two theorems are an application of the results of section 3 . In the case of Theorem 4.2 this gives a proof of a result that can be deduced from Theorem 2.1 in [BBK].

Theorem 4.2. The minimal projective resolutions of the simple Λ-modules are periodic

(a) of period 2n if Λ is of type A_{n},

(b) of period 2n if Λ is of type L_{n},

(c) of period 2n − 3 if Λ is of type D_{n} for n even and of period 2(2n − 3) for n odd,

(d) of period 22 if Λ is of type E_{6}, of period 17 if Λ is of type E_{7} and of period 29 if Λ is of type E_{8}.

Definition 4.3. We call a projective resolution R^{•} of a Λ-module M of linear growth of factor p if given the first p terms

R_{p−1} → ⋯ → R_{1} → R_{0} → M → 0

of R^{•}, all other terms of R^{•} have the form

R_{kp+l} = N_{l}^{⊕k} ⊕ R_{l} for 0 ≤ l ≤ p − 1

where N_{l} is a direct sum of components R_{i} for 0 ≤ i ≤ p.

Let q be as given in Theorem 3.30.

Theorem 4.4. Let Λ be of extended Dynkin type or of type D̃L. Then the minimal projective resolutions of the simple Λ-modules are of linear growth of factor q.

Theorem 4.2 follows directly from the calculation of the syzygies in the next Proposition.

Proposition 4.5. (a) Let Λ be of type A_{n}. Then for all simple Λ-modules S_{i} we have Ω^{j}(S_{i}) is not simple for j < n and Ω^{n}(S_{i}) = S_{n−i+1}.

(b) Let Λ be of type L_{n}. Then for all simple Λ-modules S_{i}, we have Ω^{j}(S_{i}) is not simple for j < 2n and Ω^{2n}(S_{i}) = S_{i}.

(c) Let Λ be of type D_{n}. Then for all simple Λ-modules S_{i}, we have Ω^{j}(S_{i}) is not simple for j < 2n − 3 and

Ω^{2n−3}(S_{i}) = \{ \begin{matrix}S_{2} & if i = 1 and n is odd \\ S_{1} & if i = 2 and n is odd \\ S_{i} & otherwise. \end{matrix}

(d) Let Λ be of type E_{6} , E_{7} or E_{8}. Then for all simple Λ-modules S_{i}, we have

Ω^{j}(S_{i}) = \{ \begin{matrix}S_{i} & if n = 6 and j = 11 and for i = 3, 4 \\ S_{n−i+1} & if n = 6 and j = 11 and for i = 1, 2, 5, 6 \\ S_{i} & if n = 7 and j = 17 and for all i \\ S_{i} & if n = 8 and j = 29 and for all i. \end{matrix}

Proof: The Proposition follows directly from Lemma 4.1 and the results of section 3 □.

Proof of Theorem 4.4: It is enough to establish the recurrence formula for the Chebyshev polynomials evaluated on the adjacency matrices in question, since by Lemma 4.1 it is then straightforward to determine the projective resolutions. Namely, if the algebra has n simple modules, then the indecomposable projectives constituting the rth term in a projective resolution of the simple S_{i} are exactly given by the first n entries of the ith row of the matrix B^{r}.

Let D be the adjacency matrix of the graph underlying Λ (recall that D is not of type L̃). Then it follows from Theorem 3.30 in combination with Lemma 3.5 that given f_{0}(D), …, f_{q}(D) we have for q + 1 ≤ n ≤ 2q − 1, where n = q + l for 1 ≤ l ≤ q − 1, that f_{q+l}(D) = (f_{q−2−l}(D) + f_{l}(D)) + f_{l}(D) since in this case Z = 2I. So if we calculate a minimal projective resolution of the simple S_{i}, then the components of q + lth term, for 1 ≤ l ≤ q − 1, are R_{q+l} = N_{l} ⊕ R_{l} where R_{l} is determined by the ith row of f_{l}(D) and N_{l} = R_{q−2−l} ⊕ R_{l} is determined by the ith row of f_{q−2−l}(D) + f_{l}(D). For n ≥ 2q − 1 we have the following: Write n = rq + l with −1 ≤ l ≤ q − 2. Furthermore, note that here Z = 2I = 2f_{0}(D). Then by Lemma 3.5 and the remark that follows we have, for −1 ≤ l ≤ q − 2, that R_{rq+l} = N_{l}^{⊕r} ⊕ R_{l} where N_{l} = R_{q−2−l} ⊕ R_{l}. □

Remark: Suppose Λ is of type L̃. Then the projective resolution of the simple Λ-modules is almost of linear growth. More precisely in that case we have by Corollary 3.15 that f_{q}(X) − f_{q−2}(X) = Z where Z = 2I^{0} = 2f_{0}(D)^{0}. Given the first q terms in a projective resolution of a simple Λ-module S we then obtain by Lemma 3.8 and the remark that follows the nth term in the projective resolution of S, for n ≥ 2q − 1, in the following way: if we write n = rq + l with −1 ≤ l ≤ q − 2, then

N_{rq+l} = \{ \begin{matrix}(N_{l}^{0})^{⊕r} + R_{l} & r even \\ N_{l}^{⊕r} + R_{l}^{0} & r odd \end{matrix}

where N_{l} is as defined in the proof above and the components in N_{l}^{0} are given by the ith row of I^{0}(f_{q−2−l}(D) + f_{l}(D))I^{0} and R_{l}^{0} is given by the ith row of I^{0}f_{l}(D)I^{0}.

5. Evaluating Chebyshev polynomials on positive symmetric matrices

We conclude by a general statement on evaluating the Chebyshev polynomials (f_{k}(x))_{k} on positive symmetric matrices.

Theorem 5.1. Assume X is a symmetric matrix, with entries in ℤ_{≥0} and assume X is indecomposable. Then

a) f_{d}(X) = 0 for some d ≥ 1 if and only if X is the adjacency matrix of a diagram of type A, D, E or L. b) The family (f_{k}(X))_{k} grows linearly if and only if X is the adjacency matrix of a diagram of type Ã, D̃, Ẽ, L̃ or D̃L.

Proof: a) If X is the adjacency matrix of a Dynkin diagram or of a graph of type L, then the result follows from section 3. Suppose that f_{d}(X) = 0 for some n, then by Lemma 3.3 X annihilates the sequence of polynomials f_{k}(x) periodically. Since X is a symmetric integer matrix with entries in ℤ_{≥0}, then it is the adjacency matrix of a finite connected graph. To this graph we can associate a unique symmetric algebra Λ with radical cube zero, such that the sequence of polynomials (f_{k}(X))_{k≥0} describes the growth of a minimal projective resolution of the simple modules, as explained at the beginning of section 4. To construct this algebra, we replace each edge by a pair of arrows pointing in opposite directions. Then the algebra is the path algebra modulo the ideal generated by quadratic relations in the arrows, and there is a unique choice of such relations making the algebra symmetric with radical cube zero.

Then it follows from section 4 that for such an algebra the minimal projective resolutions of the simple modules are periodic and thus following [B, 1.1] Λ is of type A, D, E or L.

b) If X is of extended Dynkin type or of types L̃ or D̃L then by section 3, (f_{k}(X))_{k} grows linearly. Conversely, suppose that (f_{k}(X))_{k} grows linearly. As in a), X gives rise to a symmetric algebra Λ of radical cube zero. By section 4 this implies that the minimal projective resolutions of the simple Λ-modules grow linearly. Following [B, 1.1] Λ is of type Ã, D̃, Ẽ, L̃, or D̃L. □

Appendix

Dynkin diagrams with labels:

\begin{matrix}A_{n}, n ≥ 2 : •^{1}  •^{2} ⋯ •^{n−1}  •^{n} & L_{n}, n ≥ 2 :  •^{1}  •^{2} ⋯ •^{n−1}  •^{n} \\ D_{n}, n ≥ 4 : [figure: •^{1}; •^{3}; _{•^{4} ⋯ •^{n−1}}; •^{n}; •^{2}] & E_{6} :  •^{6} •^{1}  •^{2}  •^{3}  •^{4}  •^{5} \\ E_{7} :  •^{7} •^{1}  •^{2}  •^{3}  •^{4}  •^{5}  •^{6} & E_{8} :  •^{8} •^{1}  •^{2}  •^{3}  •^{4}  •^{5}  •^{6}  •^{7} \end{matrix}

Extended Dynkin diagrams with labels:

Ã_{n}, n ≥ 2 : [figure: •^{n+1}; •^{1}; _{•^{2} ⋯ •^{n−1}}; •^{n}]  L̃_{n}, n ≥ 2 :  •^{1}  •^{2} ⋯ •^{n−1}  •^{n}

D̃_{n}, n ≥ 3 : [figure: •^{1}; •^{n}; •^{3}; _{•^{4} ⋯ •^{n−2}}; •^{n−1}; •^{2}; •^{n+1}]  D̃L_{n}, n ≥ 3 : [figure: •^{1}; •^{3}; _{•^{4} ⋯ •^{n−1}}; •^{n}; •^{2}]

Ẽ_{6} :  •^{7} •^{6} •^{1}  •^{2}  •^{3}  •^{4}  •^{5}  Ẽ_{7} :  •^{7} •^{8}  •^{1}  •^{2}  •^{3}  •^{4}  •^{5}  •^{6}

Ẽ_{8} :  •^{8} •^{1}  •^{2}  •^{3}  •^{4}  •^{5}  •^{6}  •^{7}  •^{9}

References

[BM] G. Benkart, D. Moon, Tensor product representations of Temperley-Lieb algebras and Chebyshev polynomials. Representations of algebras and related topics, 57–80, Fields Inst. Commun., 45, Amer. Math. Soc., Providence, RI, 2005.

[B] D. J. Benson, Resolutions over symmetric algebras with radical cube zero. J. Algebra 320 (2008), no. 1, 48–56.

[BBK] S. Brenner, M. C. R. Butler, A. King, Periodic algebras which are almost Koszul. Algebras and Representation Theory 5 (2002) 331-367.

[C] H. S. M. Coxeter, The product of the generators of a finite group generated by reflections. Duke Math. J. 18, (1951). 765–782.

[E] K. Erdmann, Tensor products and dimensions of simple modules for symmetric groups. Manuscripta Math. 88 (1995), no. 3, 357–386.

[EF] K. Erdmann, Q. Fu, Schur-Weyl duality for infinitesimal q-Schur algebras s_{q}(2, r)_{1}. J. Algebra 320 (2008), no. 3, 1099–1114.

[GL] J. J. Graham, G. I. Lehrer, Cellular algebras. Invent. Math. 123 (1996), no. 1, 1–34.

[MH] J. C. Mason, D. C. Handscomb, Chebyshev polynomials. Chapman & Hall/CRC, Boca Raton, FL, 2003. 341 pp.

[MZ] R. Martínez-Villa, D. Zacharia, Auslander-Reiten sequences, locally free sheaves and Chebysheff polynomials. Compos. Math. 142 (2006), no. 2, 397–408.

[R] T.J. Rivlin, Chebyshev polynomials: From Approximation Theory to Algebra and Number Theory, (2nd ed.) Wiley 1990.

[RX] H. Rui, C. Xi, The representation theory of cyclotomic Temperley-Lieb algebras. Comment. Math. Helv. 79 (2004), no. 2, 427–450.

[S] M.A. Snyder, Chebyshev methods in numerical approximation, Prentice Hall 1966.

Mathematical Institute, University of Oxford, UK

E-mail address: erdmann@maths.ox.ac.uk

Department of Mathematics, University of Leicester, UK

E-mail address: schroll@mcs.le.ac.uk