Image: Let G be the undirected graph with adjacency matrix Draw a diagram of the
ID: 2970689 • Letter: I
Question
Image:
Let G be the undirected graph with adjacency matrix Draw a diagram of the graph G. Compute the characteristic polynomial of A State a specific formula for A3 that is implied by the Cayley - Hamilton Theorem. Your formula should that the form A3 = xA2 + yA + zI where I denotes the identity matrix. You need to find the integers x,y,z that make this equation true. (I tell you this so that you do not just raise A to the tenth power on the computer!) Check by direct calculation that this formula is true. Use the formula to determine A10, and explain the consequences for walks of length 10 on the graph G.Explanation / Answer
I let you draw G.
By expanding by the first row the determinant we have :
det(A-xI) = (1-x)( -x*(1-x)-1 ) - (1-x) = -x^3+2x^2+x-2
According to cayley-hamilton theorem this polynom verifies P(A)=0 => A^3 = 2A^2+A-2I
Let's check :
A^2 =
2 1 1
1 2 1
1 1 2
A^3 =
3 3 2
3 2 3
2 3 3
2A^2+A =
5 3 2
3 4 3
2 3 5
2A^2+A-2I = A^3 => this is true
3 3 2
3 2 3
2 3 3
A^3 = 2A^2+A-2I
A^4 = A*(2A^2+A-2I) = 2A^3+A^2-2A = 2(2A^2+A-2I)+A^2-2A=5A^2-4I
A^6 = (2A^2+A-2I)^2 = 4A^4+A^2+4I+4A^3-8A^2-4A = 4(5A^2-4I)+A^2+4I+4(2A^2+A-2I)-4A^2-4A
A^6 = (20+1+8-8)A^2 + (-8+4-16)I = 21A^2-20I
A^10 = A^6*A^4 = (5A^2-4I)(21A^2-20I) = 105A^4-84A^2-100A^2+80I = 105(5A^2-4I)-184A^2+80I
A^10 = (105*5-184)A^2 +(80-420)I = 341A^2-340I
Hence :
A^10 =
342 341 341
341 342 341
341 341 342
The ij-th entry of the 10-th power of A tells you the number of walks of length 10 from vertex i to vertex j
So they are 341 number of walks of length 10 from vertex i to vertex j (i!=j) and 342 from vertex i to i (same)