Description
1. Let πΊ have Laplacian matrix
πΏ =
[
2 0 0 β1 β1 0 0
0 2 β1 0 β1 0 0
0 β1 3 0 0 β1 β1
β1 0 0 3 0 β1 β1
β1 β1 0 0 3 0 β1
0 0 β1 β1 0 2 0
0 0 β1 β1 β1 0 3 ]
A. 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.
B. 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
π³ = π° β
π― β
π°
π― β
π―
π―.
This vector π³ is orthogonal to π―.
C. Let π± =
1
βπ―β
π―
π― and π² =
1
βπ³β
π³
π³ and plot the points
(π₯1
, π¦1
), (π₯2
, π¦2
), (π₯3
, π¦3
), (π₯4
, π¦4
), (π₯5
, π¦5
), (π₯6
, π¦6
), (π₯7
, π¦7
)
and for each edge ππ of πΊ, draw the segment joining (π₯π
, π¦π
) to
(π₯π
, π¦π
).
The result in C should be a βniceβ drawing of πΊ, in the sense that
adjacent vertices are close together.
D. Do the same process in parts B and C for the eigenvectors
corresponding to π6 and π7
, the two largest eigenvalues.
E. 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.
A. 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.
B. 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.
C. According to the relative values of column entries, how should the
participants be ranked?
D. In part C, did you find that any player who won fewer games was
more highly ranked than someone who won more games?