GATE CS 2023 Q.30: Linear Algebra

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

Let $\lambda_1, \lambda_2, \lambda_3, \lambda_4$ , and $\lambda_5$ be the five eigenvalues of $A$ . Note that these eigenvalues need not be distinct.

The value of $\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 =$ _______.

Your answer

Official answer and solution

About the official key

Official key accepted both 2 to 2 and 4 to 4 depending on whether a self-loop is represented as 1 or 2 on the matrix diagonal.

Note on this question

Official key accepted both 2 to 2 and 4 to 4 depending on whether a self-loop contributes 1 or 2 to the diagonal.

Solution

Use the property that the sum of the eigenvalues of a matrix equals the trace of the matrix.

The sum of the eigenvalues of any square matrix $A$ equals the trace of $A$ :

\sum_{i=1}^5 \lambda_i = \operatorname{tr}(A) = \sum_{i=1}^5 A_{ii}

In the adjacency matrix of a graph, the diagonal entry $A_{ii}$ records the number of self-loops at vertex $i$ :

The given graph has self-loops at vertex 3 and vertex 4, with vertices 1, 2, and 5 having no self-loops.
In standard graph theory convention, each self-loop contributes 1 to the diagonal ( $A_{33} = 1, A_{44} = 1$ ), giving $\operatorname{tr}(A) = 1 + 1 = 2$ .
In an alternative convention sometimes adopted for undirected graphs (where degree of a loop counts as 2 edges incident to the vertex), each loop contributes 2 to the diagonal, yielding $\operatorname{tr}(A) = 2 + 2 = 4$ .

The official GATE key accepted both 2 and 4.

Final answer

2 (or 4)

Common trap

Attempting to calculate the characteristic polynomial and find the roots directly instead of using the trace property.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.