Explain in detail please! Let G be the undirected graph with adjacency matrix Dr

Question

Explain in detail please!

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 take 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 of 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)

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.