edited by
12,729 views
9 votes
9 votes

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

edited by

4 Answers

Best answer
27 votes
27 votes

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.

edited by
10 votes
10 votes

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$

0 votes
0 votes

           Trace (matrix) : Sum of diagonal elements

 

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

0 votes
0 votes

           Trace (matrix) : Sum of diagonal elements

 

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

Answer:

Related questions

19 votes
19 votes
4 answers
1
5 votes
5 votes
1 answer
2
23 votes
23 votes
6 answers
3
gatecse asked Feb 14, 2018
10,124 views
Consider a matrix $A= uv^T$ where $u=\begin{pmatrix}1 \\ 2 \end{pmatrix} , v = \begin{pmatrix}1 \\1 \end{pmatrix}$. Note that $v^T$ denotes the transpose of $v$. The larg...