Skip to content
GATETECH
Official PYQ · 2023Q20Eigenvalues and Eigenvectors, LU DecompositionNAT1 mark

GATE CS 2023 Q20 — Eigenvalues and Eigenvectors, LU Decomposition

Explain with AI

Let AA be the adjacency matrix of the graph with vertices {1,2,3,4,5}.\{1,2,3,4,5\}.

Let λ1,λ2,λ3,λ4\lambda_{1}, \lambda_{2}, \lambda_{3}, \lambda_{4}, and λ5\lambda_{5} be the five eigenvalues of AA. Note that these eigenvalues need not be distinct.

The value of λ1+λ2+λ3+λ4+λ5=\lambda_{1}+\lambda_{2}+\lambda_{3}+\lambda_{4}+\lambda_{5}=____________

View worked solution

Answer: 2

To find the sum of the eigenvalues of the adjacency matrix AA, we can use a fundamental property from linear algebra:

The sum of the eigenvalues of any square matrix is equal to the trace of the matrix (the sum of its diagonal elements):

∑i=15λi=Tr(A)=∑i=15Aii\sum_{i=1}^{5} \lambda_i = \text{Tr}(A) = \sum_{i=1}^{5} A_{ii}

For the adjacency matrix AA of a graph:

  • The diagonal entry AiiA_{ii} represents the number of self-loops at vertex ii.
  • If there is no self-loop at vertex ii, then Aii=0A_{ii} = 0.
  • If there is a self-loop at vertex ii, then Aii=1A_{ii} = 1.

By observing the given graph, we can see that there are exactly two self-loops (at vertex 11 and vertex 55). All other vertices do not have self-loops.

Thus, the diagonal elements of the adjacency matrix AA are:

A11=1,A22=0,A33=0,A44=0,A55=1A_{11} = 1, \quad A_{22} = 0, \quad A_{33} = 0, \quad A_{44} = 0, \quad A_{55} = 1

Calculating the trace:

Tr(A)=1+0+0+0+1=2\text{Tr}(A) = 1 + 0 + 0 + 0 + 1 = 2

Therefore, the sum of the eigenvalues is:

λ1+λ2+λ3+λ4+λ5=2\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 = 2

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Eigenvalues and Eigenvectors, LU Decomposition questions