GATE CSE 2023 | Question: 20

Question

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}=$____________

Answer 1

There are two possible choices for the adjacency matrix for the given undirected graph $G$ and hence two possible answers.

Your first choice could be:

$A(G) = \begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}$

The problem with this matrix is that Handshaking lemma is not satisfied here because sum of each row gives the total degree of each vertex and so here total degree = $12$ and total edges in the graph is $7$.

The reason is, this matrix is made on the assumption that self-loop has degree $1$ and that's why $\textbf{Handshaking Lemma}$ will be failed here because the reason we take the degree of the self-loop as $2$ to make Handshaking Lemma satisfied.

Hence, if we make the assumption that self-loop has degree $1$ then the answer will be $2$ because of self-loops, each with degree $1.$

Now, your second choice could be:

$A(G) = \begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 0 \\
0 & 1 & 2 & 0 & 1 \\
0 & 1 & 0 & 2 & 1 \\
0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}$

Here, Handshaking lemma is satisfied because total degree=$14$ because sum of all the rows is $14.$ and Hence, total number of edges is $7.$

Again the reason is, this matrix is made on the assumption that self-loop has degree $2$ and that's why $\textbf{Handshaking Lemma}$ will be satisfied here because the reason we take the degree of the self-loop as $2$ to make Handshaking Lemma satisfied.

Hence, if we make the assumption that self-loop has degree $2$ then the answer will be $4$ because of self-loops, each with degree $2.$

Most probably, GATE Authority will give answer as $2$ because the convention follows in most of the books whether it is Diestel, Bondy & Murthy, Douglas B. West, Narsingh Deo or Harary, All follows first convention but I have given the true picture so that all of you know about the issue with this question.

Edit: After challenge, answer has been changed from 2 to 2 or 4.

Comments

@ankitgupta.1729 Congratulations for winning the challenge :)

---

The accepted answers were 2 and 4

---

What is actual answere,that must be 2 only right ???

Answer 2

Firstly convert the given undirected graph into an adjacency matrix, we will get:

$A=\begin{pmatrix} 0& 1 &0 &0 &0 \\ 1& 0 &1 &1 &0 \\ 0& 1 & 1 &0 &1 \\ 0& 1 & 0 &1 &1 \\ 0&0 &1 &1 &0 \end{pmatrix}$

now we know that the summation of the eigenvalue is equal to the trace of the matrix.

so the trace of matrix is:

• $\lambda_1=0$
• $\lambda_2=0$
• $\lambda_3=1$
• $\lambda_4=1$
• $\lambda_5=0$

$\therefore \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4+ \lambda_5=0+0+1+1+0=2$

correct answer is $2$

Comments

• Trace of matrix is equal to the sum of eigen values that is fine. But how can we compare the diagonal element to respective eigen value since it is symmetric matrix.There might a case possible in which eigen values are 0,0,0,0,2....since sum of eigen values are asked your logic is not affecting the answer.

Answer 3

           Trace (matrix) : Sum of diagonal elements

 

so , λ1+λ2+λ3+λ4+λ5 = ( 0 + 0 + 1 + 1 + 1 + 0 ) = 2

Answer 4

           Trace (matrix) : Sum of diagonal elements

 

so , λ1+λ2+λ3+λ4+λ5 = ( 0 + 0 + 1 + 1 + 1 + 0 ) = 2