5. Recall that for an n x n matrix A, its characteristic polynomial PA(x) is defined byPA(x) := det(xIn – A),where In denotes the n x n identity matrix. Consider the sequence of simple graphsTn = (Vn, En) defined as follows for n 2 0:Vn := {vo, . .., Vn}andEn := {{vi-1, vi} | i = 1, ...,n},with the convention that E, = Ø.Page 2 of 3(a) Find the adjacency matrix An of the graph Tn for each n > 0.(b) Set Po(x) := 1, and for n > 1 let Pn(x) := det(xIm – An-1) be the characteristicpolynomial of A,–1. Find P(x) and P2(x).(c) Show that for n > 2 we have thatPn(x) = xPn-1(x) – Pn-2(x).(Hint for part (c): consider the Laplace expansion of the determinant with respect tothe first column of xI, – An-1-)

Given: The characteristic polynomial of an n×n matrix is PAx=detxIn-A Sequence of simple graphs Tn, Tn=Vn,En defined by Vn:=vo,v1,…,vn and En:=vi-1,vi | i=1,2,…,n, E0=∅ To do: Find the adjacency matrix An of the graph Tn for all n≥0. Find P1x and P2x where Pnx:=detxIn-An-1 and P0x:=1. For n≥2 show that Pnx=xPn-1x-Pn-2x(a.) Given that Tn is a sequence of simple graphs defined by Vn:=vo,v1,…,vn and En:=vi-1,vi | i=1,2,…,n, E0=∅ For a simple graph, the adjacency matrix is defined by An=1vi~vj for i≠j0otherwise where vi~vj represents vi is adjacent to vj. In this case vi is connected to vj by an edge and vj is connected to vi by an edge. Note that main diagonal entries of an adjacency matrix of simple graphs is always zero. From the definition of En, the edges of Tn will be v0~v1, v1~v2,…,vn-1~vn Hence, the adjacency matrix is v0 v1 v2 vn-1 vn An=v0v1v2⋮vn-1vn010⋯00101⋯00010⋯00⋮⋮⋮⋮⋮⋮000⋯01000⋯10n+1×n+1 This is the required adjacency matrix of Tn for all n≥0.(b.) Given that P0x=1 and Pnx=detxIn-An-1 for n≥1 Since P0x=1, the corresponding adjacency matrix is A0=01×1 which is a zero matrix of order 1. This is found from the matrix An with n=0. Let n=1, then P1x=detxI1-A1-1=detxI1-A0=detxI1-0=detxI1=xdetI1=x Hence, P1x=x The adjacency matrix of P1x is the matrix An for n=1. i.e., A1=01102×2 Let n=2, then P2x=detxI2-A2-1=detxI2-A1=detx00x-0110=detx-1-1x=x2+1 Hence, P2x=x2+1(c.) Given Pnx=detxIn-An-1 Substitute the corresponding values and simplify. Pnx=detxIn-An-1 =detx00⋯00x0⋯000x⋯0⋮⋮⋮⋯⋮000⋯x-010⋯0101⋯0010⋯0⋮⋮⋮⋯⋮000⋯0 =x-10⋯0-1x-1⋯00-1x⋯0⋮⋮⋮⋯⋮000⋯x =xx-1⋯0-1x⋯0⋮⋮⋯⋮00⋯x--1-10⋯0-1x⋯0⋮⋮⋯⋮00⋯x Laplace expansion along the first column =x·detx0⋯00x⋯0⋮⋮⋯⋮00⋯x-01⋯010⋯0⋮⋮⋯⋮00⋯0 -detx0⋯00x⋯0⋮⋮⋯⋮00⋯x-01⋯010⋯0⋮⋮⋯⋮00⋯0 =x·detxIn-1-An-2-detxIn-2-An-3 =x·Pn-1x-Pn-2x Hence, Pnx=xPn-1x-Pn-2x