Dynamics on Graphs 16

We introduce the Cartan matrix of a graph, which is the key ingredient in understanding the fundamental duality between the Mutation Game and the Numbers Game that we play on a graph.

Although historically this matrix arose first in the context of Lie theory and representations, here we have a much more elementary view which is also more general, in that it applies to general graphs, not just the ADE graphs that figure in the standard Lie algebra / Lie group theory.

Here is the entire Playlist for this series: Exceptional Structures in Maths and Physics via Dynamics on Graphs (Members only): https://www.youtube.com/playlist?list...

A big thanks to all my Patreon supporters and Members of the Wild Egg Maths channel--- your support and encouragement is much appreciated!

0:01

Hello everyone I'm Norman Wildberger thanks for joining me on this adventure today we're going to

0:05

be introducing the idea of a carton Matrix for a graph this is something that has its origins

0:10

in Lee Theory and representation Theory but actually it's a much more General situation

0:15

and can be viewed as we're trying to promote with a purely a graph theoretical point of view

0:21

and the carton Matrix of a graph is going to be the key ingredient that allows us to connect the

0:26

mutation game on that graph with the numbers game on that graph okay there's The Duality

0:31

between these things become more apparent so the standard notation the carton Matrix of a graph is

0:38

denoted by Capital C and for us the negative of this Matrix and I'm going to use my often

0:46

favorite convention c bar the bar overt denoting the negative of a matrix okay so that's also going

0:53

to be useful for us so I want to illustrate everything with a very explicit example and

0:58

crucially this is not an Ade example so it sort of Falls outside the usual territory in which

1:05

carton matrices are discussed we're going to look at this graph here which we've seen a number of

1:09

times just four vertices connected this way here vertices will be labeled one two three four so

1:16

let's keep that ordering in mind so a population which is just a function of the vertices can be

1:21

represented by a four Vector with components A1 A2 A3 A4 now corresponding to this population there

1:27

is a corresponding weight say w which we might represent with a column Vector say W1 w2w3w4

1:35

and I remind you that the distinction between populations and weights diagrammatically is

1:41

sort of captured by reserving uh closed vertices or solid vertices for describing populations and

1:48

open vertices to signify that we're talking about weights okay so let's see exactly what happens so

1:54

recall that the weight wi by definition it's the change at vertex I of the population p as

2:01

a result of the mutation s i at that vertex okay so if we have a Vertex say I then we can mutate

2:08

any population at that vertex and if we mutate a population P at that vertex that it changes

2:15

only at that vertex and it's the amount of change that is recorded by the value w i of the weight

2:23

okay great so now we can see what actually happens with various mutations on a general population A1

2:32

A2 A3 A4 on this particular graph so A1 A2 A3 A4 these are the values of this population at these

2:40

various vertices and now let's see what happens to these values as we perform the various mutations

2:46

so if we mutate at vertex one so we perform S1 then what happens well this A1 changes to minus

2:55

A1 and then correspondingly we have to add the sum of the neighbors value so we get a

3:01

2 plus minus A1 or all the other minus A1 Plus A2 so that's what the mutation S1 does it changes

3:09

this A1 value to minus A1 Plus A2 on the other hand if we mutated at vertex 2 in other words

3:16

applied S2 then we would get minus A2 plus the sum of the neighboring values so we have to add

3:23

A1 Plus A3 plus A4 that would be the new value at vertex 2. if we performed S3 instead then we going

3:33

from A3 to minus A3 plus A2 plus A4 because those are the directly adjacent neighbors and finally

3:41

if we perform S4 mutation at Vertex 4 then this A4 is going to go to minus A4 plus A2 plus A3

3:49

okay so overall this graph here then records the various changes in the population's values

4:00

that arise from mutations at the various vertices so if we go back to vertex one then

4:08

the total change that we can see happening is the difference between the final population here and

4:15

the initial population so minus A1 Plus A2 minus A1 that's the change altogether A2 minus 2 a 1.

4:26

how about the change if we perform a mutation S2 well final minus initial we'll get A1 Plus

4:33

A3 plus A4 minus 2 A2 okay because there's a minus A2 already there and then we have to

4:39

subtract the initial one so it's minus two eight two at vertex 3 the difference is A2 plus A4

4:46

minus 2 A3 and at A4 it's A2 plus A3 minus 2a4 so these are the values of the corresponding weights

4:57

that correspond to this population there's the population there's the weight all right so we can

5:04

record all of this in Pleasant Matrix form using a little bit of linear algebra because we're really

5:09

going from a vector a row Vector of the population to this column Vector of the corresponding weight

5:16

and when we look at the relationship between these two things we see pleasantly that it's

5:21

actually a linear relationship right the entries of the the P are occurring linearly here in this

5:28

W that means we can express this using linear algebra very compactly okay so to do that let

5:36

me remind you that the adjacency Matrix of the graph x that we're starting with this one here

5:41

is this four by four Matrix a that records that vertex one is connected to vertex two

5:50

so there's a entry here at the two one level or at the one two level the vertex two is connected

5:55

to one three and four so we see uh you know one three four entries in the second column the third

6:02

column has entries in the two and the four telling us that vertex three is connected to where it sees

6:07

two and four and finally on the fourth column we see entries in the two and three positions telling

6:13

us that the neighbors of four are two and three okay so now if we go back to the relationship

6:18

between the um the original population and the weights we see that this Vector of Weights that

6:25

we're that we're getting so we're just recording the various values can be expressed by taking the

6:31

the transpose essentially of the original Vector of population and multiplying by this particular

6:37

4x4 Matrix okay because A2 minus 2a1 is expressed by this first row minus two a one plus one A2 and

6:47

A1 Plus A3 plus A4 minus 2 A2 is expressed by this row here so it's 1a1 minus 2 a 2 plus A3

6:55

plus A4 and this one here is expressed by this row and this entry here is expressed by this row

7:02

and now happily if we sort of compare this Matrix here with the adjacency Matrix right

7:08

above it there we see that it's pretty well the same thing except for a crucial difference is that

7:14

here we in addition have minus twos down the diagonal but otherwise they're exactly the same

7:23

so we can capture this by this equation that this W Vector is well it's actually see

7:36

um Bar times the transpose of the population Vector okay where C is this Matrix 2i minus a

7:48

what is 2i minus a well 2i is referring to the identity Matrix okay so uh that's the

7:55

Matrix with ones along the diagonal okay so if we multiply that 2 we get 2's done that angle at

8:00

2 minus a well that's just exactly the negative of what's Happening Here okay so you might say

8:06

why is sort of curious rotation well it's because historically this particular combination is called

8:11

the carton Matrix okay so in in the literature this combination two times the identity minus the

8:17

adjacency Matrix is the carton Matrix of the graph x now that's respect with to the given ordering

8:24

of the vertices so we have chosen an ordering of the vertices one two three four in order to

8:29

write down that Matrix and then C bar is just a negative of this that's going to be a minus 2i

8:39

now a and the identity Matrix I are both symmetric so is this carton Matrix so notice

8:46

the transpose of the carton Matrix is itself so that's great now we have a very simple

8:53

linear algebraic expression for how to go from the population to the corresponding weight just by

9:00

essentially multiplying by this c bar Matrix doing a bit of a transpose and then a c bar where this

9:07

C is 2i minus a this classical carton Matrix so a natural question is can we go the other way around

9:13

can we recover the population P from the way to w well linear algebra tells us yes provided that the

9:23

Matrix C or it's negative is invertible okay so when is this Matrix C invertible well in linear

9:34

algebra a matrix is invertible precisely when it's determinant is non-zero so that's the condition

9:41

that the determinant of two I minus a is not zero well that's the same as the determinant of a minus

9:48

2i not zero because putting in a minus sign just changes that determine it by an either plus or

9:54

minus one okay so uh and this when we write it this way then we sort of recognize a familiar

10:02

condition very important in linear algebra having to do with eigenvalues so this this condition is

10:08

saying that the number two is not an eigenvalue of the Matrix a of The adjacency Matrix okay and

10:18

what's that saying well that's saying that there's no vector v for which a times V equals 2 times V

10:28

well that's a condition that actually we've talked about earlier in this series on okay

10:32

that's exactly the condition that determines an a d e tilde graph not one of these Ade graphs

10:39

which is sort of our primary interest but these 80 tilde graphs which are just adjacent to them

10:44

and closely related to them so the condition that c is invertible really amounts to the

10:49

fact that the graph x that we're starting with is not an Ade tilde graph for those Ade tilde graphs

10:58

we're not going to be able to invert C in other words to go backwards so in our example X that uh

11:08

four vertex graph that we're considering is not an ad Telegraph and so we can check that if we

11:13

take here's C okay so it's 2 times the identity minus the adjacency and I've put the minus signs

11:20

as bars just to get you used to thinking about bars instead of minus signs there's something a

11:26

little more um I don't know Pleasant about this I think okay less confusion between the the name

11:34

of the number and the operation of negation or subtraction okay here's c bar which is just the

11:40

negation of this and now there's the adjacency Matrix and twos down the diagonal with bars

11:46

okay so we can take this thing here and we can just calculate its inverse

11:51

easy enough for the computer and it turns out that c bar inverse this Matrix here

11:56

it's inverse is this four by four Matrix first row zero one one then one two two then one two

12:03

four thirds five-thirds and then one two Five Thirds four-thirds that's the inverse of c bar

12:10

so then these two matrices c bar and its inverse c bar inverse these are the matrices

12:16

that take us from populations to weights and back back again from weights to populations

12:25

so let's illustrate this with an example so here is just some random population on our graph

12:32

minus one or one bar at vertex one one at vertex two five and vertex three four at vertex four and

12:41

the corresponding weight will be this one here so let's just remind ourselves how we get that so the

12:46

value 3 occurs because if we mutated at vertex one here the minus one would change into one and

12:52

then we'd have to add the neighbor that's two so we'd go from one bar to two at the change of three

12:58

that's right there's a three here and you can check this six here a five bar here and a two bar

13:04

here and we can check that indeed if we start with the population Vector take its transpose or write

13:10

it as a column vector and then multiply by this c bar Matrix that's the adjacency Matrix with the uh

13:19

two bars or minus twos down the diagonal that the product of this Matrix times this Vector is

13:24

indeed this weight Vector 3 6 5 bar 2 bar and if we want to go the other way around

13:32

if we want to invert this so if we start with c Bar times P transpose equals W and we want

13:38

to sort of isolate P then P transpose well we multiply by the inverse of c bar so we

13:43

get c bar inverse times w and if we take the transpose then we get that P is equal to W

13:49

transpose times c Bar in vertical stuff c bar is symmetric so it's transpose is the same as itself

13:57

so this is another equation that we could check okay so if we take W transpose times c bar

14:04

inverse so there's W transpose that's the weight diagram now written as a row and here is this c

14:11

bar inverse that I've I've computed separately okay and that's the value that we had and if we

14:17

perform this matrix multiplication then indeed we get one bar one five four okay so this is a

14:25

very specific um illustration of the importance of the carton Matrix of this graph and I want

14:32

to emphasize to you that this is much bigger than just the Ade story here okay it actually extends

14:40

to completely General graphs even graphs which are far from being trees far from from this Lee Theory

14:46

point of view this same game we're going to see is still going to be happening that that's the carton

14:52

Matrix that mediates between the mutation game on populations and the numbers game on weights.