CPTS553-Assignment 8 Solved

.  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

 .

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 𝐱𝐯 and 𝐲 𝐳 and plot the points  

𝐳

  

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?