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

Comments

self  loop in graph G is considered as both incoming and outgoing edge (it has degree 2)

also adding one edge increases the degree of each vertex by 1

deg(G) = 2*E

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.

---

Yeah that's true actually. If we had trianglular(lower or upper) then we could have said that principal diagonal elements(aij where i = j) are actual eigen values as well

---

here I was who did not read the question and spent 10 mins finding the eigen values

Answer 3

Here is the solution : 

Answer 4

           Trace (matrix) : Sum of diagonal elements

 

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

Comments

@Rahul_kumar3 how is (0+0+1+1+1+0) = 2 ?

Answer 5

           Trace (matrix) : Sum of diagonal elements

 

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

Comments

You have to consider  λ1+λ2+λ3+λ4+λ5 = ( 0 + 0 + 1 + 1 + 0 ) = 2
Small correction @Rahul_kumar3

Answer 6

The sum of eigen values of a matrix is nothing but sum of diagonal.
The diagonal element in Adjacency matrix is 1 if that element has self loop.
So basically sum of eigen values = total self loops in graph.
Here ans =2 as we have 2 self loops.