IAE Academy

GATE 2023 CS Q.30: solution and answer

GATE 2023 · CSQ.30 · 1 mark · NAT

Let be the adjacency matrix of the graph with vertices .

Let , and be the five eigenvalues of . Note that these eigenvalues need not be distinct.

The value of ______ .

GATE 2023 CS question 30: An undirected graph on vertices 1 to 5.Tap to open full size
Figure from the GATE 2023 CS paper. It is part of the question.
Figure description

An undirected graph on vertices 1 to 5. Edges: 1-2, 2-3, 2-4, 3-5, 4-5. Vertex 3 (top) has a self-loop, and vertex 4 (bottom) has a self-loop. Vertices 3 and 4 are joined to 2 on the right and to 5 on the left, so 2-3-5-4 forms a four-cycle with 1 attached to 2 as a pendant vertex.

Answer and solution

ANSWER

The sum of the eigenvalues is , the trace of .

Official answer: 2, or 4Source: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. Read the graph from the figure. The edges are , , , and . There is also a self-loop at vertex and a self-loop at vertex .

  2. In the adjacency matrix, when and are joined. A self-loop at puts a on the diagonal entry . A vertex with no loop has .

  3. So the diagonal is .

  4. The eigenvalues of a square matrix, counted with multiplicity, sum to its trace: . Repeated eigenvalues are counted each time, so the fact that they need not be distinct does not matter.

  5. , so .

  6. Some texts count a loop in an undirected graph as on the diagonal. Then the trace would be . The official key accepts both and , so the standard convention (loop gives ) gives the answer .

KEY IDEA

The sum of the eigenvalues, counted with multiplicity, equals the trace of the matrix. You can read the trace straight off the diagonal without finding any eigenvalue. Here the diagonal entries come only from the self-loops.

WATCH OUT FOR

Trying to find the characteristic polynomial and the eigenvalues of the matrix. Another slip is forgetting that a self-loop gives a diagonal entry, which makes the trace .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 78 Linear algebra questions, with notes

More Linear algebra questions