• •

2

1 2

. . . ..

• • • ≥1

> LC

1

1 1

. . . ..

•< • • ≥1

LB

1 •r 2 2

......

r• • ≥2

LD

¨¨

1•

Figure 6.4: Loops allowed

102 CHAPTER 6. THE SIMPLE FINITE DIMENSIONAL ALGEBRAS.

If T is irreducible then I + T is primitive.

In this section we will assume that T is non-negative and irreducible.

Theorem 13 Perron-Frobenius.

1. T has a positive (real) eigenvalue »max such that all other eigenvalues of

T satisfy

|»| ¤ »max .

2. Furthermore »max has algebraic and geometric multiplicity one, and has

an eigenvector x with x > 0.

3. Any non-negative eigenvector is a multiple of x.

4. More generally, if y ≥ 0, y = 0 is a vector and µ is a number such that

T y ¤ µy

then

y > 0, and µ ≥ »max

with µ = »max if and only if y is a multiple of x.

5. If 0 ¤ S ¤ T, S = T then every eigenvalue σ of S satis¬es |σ| < »max .

6. In particular, all the diagonal minors T(i) obtained from T by deleting

the i-th row and column have eigenvalues all of which have absolute value

< »max .

We will present a proof of this theorem after ¬rst showing how it classi¬es

the possible connected diagrams with maximal eigenvalue two. But ¬rst let us

clarify the meaning of the last two assertions of the theorem. The matrix T(i) is

usually thought of as an (n ’ 1) — (n ’ 1) matrix obtained by “striking out” the

i-th row and column. But we can also consider the matrix Ti obtained from T

by replacing the i-th row and column by all zeros. If x is an n-vector which is

an eigenvector of Ti , then the n ’ 1 vector y obtained from x by omitting the (0)

i-th entry of x is then an eigenvector of T(i) with the same eigenvalue (unless

the vector x only had non-zero entries in the i-th position). Conversely, if y is

an eigenvector of T(i) then inserting 0 at the i-th position will give an n-vector

which is an eigenvector of Ti with with the same eigenvalue as that of y.

More generally, suppose that S is obtained from T by replacing a certain

number of rows and the corresponding columns by all zeros. Then we may apply

item 5) of the theorem to this n — n matrix, S, or the “compressed version” of

S obtained by eliminating all these rows and columns.

We will want to apply this to the following special case. A subgraph “

of a graph “ is the graph obtained by eliminating some nodes, and all edges

emanating from these nodes. Thus, if A is the adjacency matrix of “ and A

is the adjacency matrix of A, then A is obtained from A by striking out some

rows and their corresponding columns. Thus if “ is irreducible, so that we may

6.4. PERRON-FROBENIUS. 103

apply the Perron Frobenius theorem to A, and if “ is a proper subgraph (so

we have actually deleted some rows and columns of A to obtain A ), then the

maximum eigenvalue of A is strictly less than the maximum eigenvalue of A

is strictly less than the maximum eigenvalue of A. Similarly, if an entry Aij is

> 1, the matrix A obtained from A by decreasing this entry while still keeping

it positive will have a strictly smaller maximal eigenvalue.

We now apply this theorem to conclude that the diagrams listed in Figures

A¬ 1, A¬2, and A¬ 3 are all possible connected diagrams with maximal eigen-

value two. A direct check shows that the vector whose coordinate at each node is

the integer attached to that node given in the ¬gure is an eigenvector with eigen-

value 2. Perron-Frobenius then guarantees 2 is the maximal eigenvalue. But

now that we have shown that for each of these diagrams the maximal eigenvalue

is two, any “larger” diagram must have maximal eigenvalue strictly greater than

two and any “smaller” diagram must have maximal eigenvalue strictly less than

two.

(1)

To get started, this argument shows that A1 is the only diagram for which

there is an i, j for which both aij and aji are > 1. Indeed, if A were such a

matrix, by striking out all but the i and j rows and columns, we would obtain a

two by two matrix whose o¬ diagonal entries are both ≥ 2. If there were strict

inequality, the maximum eigenvalue of this matrix would have to be bigger than

2 (and hence also the original diagram) by Perron Frobenius.

(1)

So other than A1 , we may assume that if aij > 1 then aji = 1.

(2)

Since any diagram with some entry aij ≥ 4 must contain A2 we see that

this is the only diagram with this property and with maximum eigenvalue 2.

So other than this case, all aij ¤ 3.

(1)

Diagram G2 shows that a diagram with only two vertices and a triple bond

(1)

has maximum eigenvalue strictly less than 2, since it is contained in G2 as

a subdiagram. So any diagram with a triple bond must have at least three

(1) (3)

vertices. But then it must “contain” either G2 or D4 . But as both of these

(1)

have maximal eigenvalue 2, it can not strictly contain either. So G2 and

(3)

D4 .are the only possibilities with a triple bond.

(1)

Since A , ≥ 2 is a cycle with maximum eigenvalue 2, no graph can contain

(1)

a cycle without actually being a cycle, i.e. being A . On the other hand, a

(1)

simple chain with only single bonds is contained in A , and so must have

(1)

maximum eigenvalue strictly less than 2, So other than A , every candidate

must contain at least one branch point or one double bond.

If the graph contains two double bonds, there are three possibilities as to

the mutual orientation of the arrows, they could point toward one another as

(1) (2) (2)

in C , away from one another as in D +1 or in the same direction as in A2 .

But then these are the only possibilities for diagrams with two double bonds,

as no diagram can strictly contain any of them.

(1)

Also, striking o¬ one end vertex of C yields a graph with one extreme

vertex with a double bound, with the arrow pointing away from the vertex, and

104 CHAPTER 6. THE SIMPLE FINITE DIMENSIONAL ALGEBRAS.

no branch points. Striking out one of the two vertices at the end opposite the

(1)

double bond in B yields a graph with one extreme vertex with with a double

bound and with the arrow pointing toward this vertex. So either diagram must