## 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?