Description
-
Use a matrix calculator to find the eigenvalues of ; there should be some pairs of them that have the same value. List them in order
0≤ 2≤ 3≤ 4≤ 5≤ 6≤ 7.
It’s fine (suggested, actually) that you use decimal approximations rather than exact values.
-
Use a matrix calculator to find eigenvectors and corresponding to 2 and 3. It’s fine if you use decimal approximations for these. Compute the vector
The result in C should be a “nice” drawing of , in the sense that adjacent vertices are close together.
-
Do the same process in parts B and C for the eigenvectors corresponding to 6 and 7, the two largest eigenvalues.
-
The end result in part D should cause adjacent vertices to be drawn far apart and give you an idea of how to assign colors to the vertices to determine the chromatic number of . What is this chromatic number?
2. Consider the tournament whose adjacency matrix is
-
-
-
-
-
0
1
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
= 0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
[1
0
1
1
0
0
0]
-
-
-
-
Here, = 1 if player defeated player in the tournament.
-
Use software of your choice to compute 2, 4, 8, 16 – this is most easily accomplished by squaring the matrix successively, rather than by computing the powers individually.
-
As you successively square the matrix, the columns should begin to converge to multiples of each other. What’s happening is that the columns are converging to multiples of the dominant eigenvector.
-
According to the relative values of column entries, how should the participants be ranked?
-
In part C, did you find that any player who won fewer games was more highly ranked than someone who won more games?