and whose ±2 coe¬cient is negative which is impossible.) In particular, all the

(±1 , ±2 ) ¤ 0, ±1 ∈ ∆1 , ±2 ∈ ∆2 and so

(β, ±2 ) ¤ 0, ∀ ±2 ∈ ∆2 .

The irreducibility of ∆ implies that (±1 , ±2 ) = 0 for at least one pair ±1 ∈

∆1 , ±2 ∈ ∆2 . But this scalar product must then be negative. So

(β, ±2 ) < 0

96 CHAPTER 6. THE SIMPLE FINITE DIMENSIONAL ALGEBRAS.

and hence

s±2 β = β ’ β, ±2 ±2

is a root with

s±2 β ’ β 0

contradicting the maximality of β. So we have proved that all the k± are positive.

Furthermore, this same argument shows that (β, ±) ≥ 0 for all ± ∈ ∆. Since the

elements of ∆ form a basis of E, at least one of the scalar products must not

vanish, and so be positive. We have established the second and third items in

the proposition for any maximal β. We will now show that this maximal weight

is unique.

Suppose there were two, β and β . Write β = k± ± where all the k± > 0.

Then (β, β ) > 0 since (β, ±) ≥ 0 for all ± and > 0 for at least one. Since sβ β

is a root, this would imply that β ’ β is a root, unless β = β . But if β ’ β is

a root, it is either positive or negative, contradicting the maximality of one or

the other. QED

Let us label the elements of ∆ as ±1 , . . . , ± , and let us set

±0 := ’β

so that ±0 is the minimal root. From the second and third items in the propo-

sition we know that

±0 + k1 ±1 + · · · + k ± = 0 (6.3)

and that

±0 , ±i ¤ 0

for all i and < 0 for some i.

Let us take the left hand side (call it γ) of (6.3) and successively compute

γ, ±i , i = 0, 1, . . . , . We obtain

« «

···

2 ±1 , ±0 ± , ±0 1

···

¬ ±0 , ±1 2 ± , ±1 · ¬ ·

· ¬k1 ·

· ¬ . · = 0.

¬

. . .

. . . .

¬

···

. . . .

···

±0 , ± ± ’1 , ± 2 k

This means that if we write the matrix on the left of this equation as 2I ’ A,

then A is a matrix with 0 on the diagonal and whose i, j entry is ’ ±j , ±i .

So A a non-negative matrix with integer entries with the properties

• if Aij = 0 then Aji = 0,

• The diagonal entries of A are 0,

• A is irreducible in the sense that we can not partition the indices into two

non-empty subsets I and J such that Aij = 0 ∀ i ∈ I, j ∈ J and

• A has an eigenvector of eigenvalue 2 with all its entries positive.

6.3. GRAPHS. 97

We will show that the Perron-Frobenius theorem allows us to classify all

such matrices. From here it is an easy matter to classify all irreducible root

systems and then all simple Lie algebras. For this it is convenient to introduce

the language of graph theory.

6.3 Graphs.

An undirected graph “ = (N, E) consists of a set N (for us ¬nite) and a

subset E of the set of subsets of N of cardinality two. We call elements of N

“nodes” or “vertices” and the elements of E “edges”. If e = {i, j} ∈ E we

say that the “edge” e joins the vertices i and j or that “i and j are adjacent”.

Notice that in this de¬nition our edges are “undirected”: {i, j} = {j, i}, and we

(1)

do not allow self-loops. An example of a graph is the “cycle” A with + 1

vertices, so N = {0, 1, 2, . . . , } with 0 adjacent to and to 1, with 1 adjacent

to 0 and to 2 etc.

The adjacency matrix A of a graph “ is the (symmetric) 0 ’ 1 matrix

whose rows and columns are indexed by the elements of N and whose i, j-th

entry Aij = 1 if i is adjacent to j and zero otherwise.

(1)

For example, the adjacency matrix of the graph A3 is

«

0101

¬1 0 1 0·

0 1 0 1 .

¬ ·

1010

We can think of A as follows: Let V be the vector space with basis given by

the nodes, so we can think of the i-th coordinate of a vector x ∈ V as assigning

the value xi to the node i. Then y = Ax assigns to i the sum of the values xj

summed over all nodes j adjacent to i.

A path of length r is a sequence of nodes xi1 , xi2 , . . . , xir where each node

is adjacent to the next. So, for example, the number of paths of length 2 joining

i to j is the i, j-th entry in A2 and similarly, the number of paths of length r

joining i to j is the i, j-th entry in Ar . The graph is said to be connected if

there is a path (of some length) joining every pair of vertices. In terms of the

adjacency matrix, this means that for every i and j there is some r such that

the i, j entry of Ar is non-zero. In terms of the theory of non-negative matrices

(see below) this says that the matrix A is irreducible.

Notice that if 1 denotes the column vector all of whose entries are 1, then 1

(1)

is an eigenvector of the adjacency matrix of A , with eigenvalue 2, and all the

entries of 1 are positive. In view of the Perron-Frobenius theorem to be stated

below, this implies that 2 is the maximum eigenvalue of this matrix.

We modify the notion of the adjacency matrix as follows: We start with a

connected graph “ as before, but modify its adjacency matrix by replacing some

of the ones that occur by positive integers aij . If, in this replacement aij > 1,

we redraw the graph so that there is an arrow with aij lines pointing towards

98 CHAPTER 6. THE SIMPLE FINITE DIMENSIONAL ALGEBRAS.

(1)

the node i. For example, the graph labeled A1 in Table A¬ 1 corresponds to

the matrix

02

20

1

which clearly has as an positive eigenvector with eigenvalue 2.

1

(2)

Similarly, diagram A2 in Table A¬ 2 corresponds to the matrix

0 4

1 0

2

which has as eigenvector with eigenvalue 2. In the diagrams, the coe¬cient

1

next to a node gives the coordinates of the eigenvector with eigenvalue 2, and it

is immediate to check from the diagram that this is indeed an eigenvector with

eigenvalue 2. For example, the 2 next to a node with an arrow pointing toward

(1)

it in C satis¬es 2 · 2 = 2 · 1 + 2 etc.

It will follow from the Perron Frobenius theorem to be stated and proved

below, that these are the only possible connected diagrams with maximal eigen-

vector two.

All the graphs so far have zeros along the diagonal. If we relax this condi-

tion, and allow for any non-negative integer on the diagonal, then the only new

possibilities are those given in Figure 4.

Let us call a matrix symmetrizable if Aij = 0 ’ Aji = 0. The main result

of this chapter will be to show that the lists in the Figures 1-4 exhaust all irre-

ducible matrices with non-negative integer matrices, which are symmetrizable