GATE CSE 2021 Set 1 | Question: 52

Question

Consider the following matrix.$$\begin{pmatrix} 0 & 1 & 1 & 1\\ 1& 0& 1 & 1\\ 1& 1 & 0 & 1 \\1 & 1 & 1 & 0 \end{pmatrix}$$The largest eigenvalue of the above matrix is __________.

Comments

$3$ is the correct answer.

---

Elementry Operation On matrix

https://www.geeksforgeeks.org/elementary-operations-on-matrices/

Properties of  Determinent

https://www.geeksforgeeks.org/properties-of-determinants-class-12-maths/

Answer 1

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

Characteristic equation $ \mid A – \lambda I \mid = 0$

$\implies \begin{vmatrix} -\lambda & 1 & 1 & 1\\ 1& -\lambda & 1 & 1\\ 1& 1 & -\lambda & 1 \\1 & 1 & 1 & -\lambda \end{vmatrix} = 0$

Perform the operation, $C_{4} \rightarrow C_{1} + C_{2} + C_{3} + C_{4}$, we get

$\implies \begin{vmatrix} -\lambda & 1 & 1 & 3-\lambda\\ 1& -\lambda & 1 & 3-\lambda\\ 1& 1 & -\lambda & 3-\lambda \\1 & 1 & 1 & 3-\lambda \end{vmatrix} = 0$

$\implies (3 – \lambda) \begin{vmatrix} -\lambda & 1 & 1 & 1 \\ 1& -\lambda & 1 & 1\\ 1& 1 & -\lambda & 1 \\1 & 1 & 1 & 1  \end{vmatrix} = 0$

Perform the operation, $R_{1} \rightarrow R_{1} - R_{4} , R_{2} \rightarrow R_{2} - R_{1}, R_{3} \rightarrow R_{3} - R_{1},$  we get

$\implies (3 – \lambda) \begin{vmatrix} -\lambda - 1 & 0 & 0 & 0 \\ 1 + \lambda & -\lambda-1 & 0 & 0 \\  1 + \lambda & 0 & -\lambda – 1 & 0 \\1 & 1 & 1 & 1  \end{vmatrix} = 0$

$\implies (3-\lambda) (-\lambda – 1)(-\lambda – 1)(-\lambda – 1) = 0$

$\implies \lambda  = -1,-1,-1,3$

$\therefore$ The largest eigenvalue is $3.$

$\textbf{PS:}$  For any matrix $A,$

• The determinant of $A$ equals the product of its eigenvalues.
• The trace of $A$ equals the sum of its eigenvalues.
• The trace of a matrix is defined as the sum of the leading diagonal entries. 
• A real symmetric matrix has only real eigenvalues.

$$\text(OR)$$

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

We can write given matrix as $:3\begin{pmatrix} 0 &\frac{1}{3} &\frac{1}{3} &\frac{1}{3} \\ \frac{1}{3} &0 &\frac{1}{3} &\frac{1}{3} \\ \frac{1}{3} &\frac{1}{3} &0 &\frac{1}{3} \\ \frac{1}{3} &\frac{1}{3} &\frac{1}{3} &0 \end{pmatrix} = 3A$

A Markov matrix is a square matrix with all nonnegative entries, and where the sum of the entries down any column is $1.$ If the entries are all positive, it’s a positive Markov matrix. It is also called a doubly stochastic matrix.

The most important facts about a positive Markov matrix are:

• $\lambda = 1$ is an eigenvalue.
• The eigenvector associated with $\lambda = 1$ can be chosen to be strictly positive.
• All other eigenvalues have a magnitude less than $1.$

So, the correct answer is $3.$

References:

• https://www.math.utah.edu/~zwick/Classes/Fall2012_2270/Lectures/Lecture40_with_Examples.pdf
• https://webpages.uncc.edu/ghetyei/courses/old/F07.3116/birkhofft.pdf

Comments

@Lakshman Patel RJIT  @Sachin Mittal 1

Sir after the row operation i.e. $R_{1} → R_{1} – R_{2}$ will not the $R_{1}$ be “$-\lambda-1$   $1+\lambda$   $0$   $0$ ” ?

---

I have fixed it now.

---

Ok!  Thank you @Lakshman Patel RJIT Sir. 

Answer 2

 

eigen values is 3, -1,-1,-1 and maximun is 3

 

Comments

best answer

Answer 3

The matrix in question is a 4x4 matrix with all diagonal elements as 0 and all off-diagonal elements as 1. This is a special type of matrix known as a Jacobian matrix for a complete graph with 4 nodes. The eigenvalues of such a matrix can be found without much computation.

Here’s the shortcut trick:

For a complete graph with ‘n’ nodes, the eigenvalues are n-1 (with multiplicity 1) and -1 (with multiplicity n-1). Here, n=4, so the eigenvalues are 3 (with multiplicity 1) and -1 (with multiplicity 3).

This is a well-known property of complete graphs. “Multiplicity” here refers to the number of times the same eigenvalue is repeated.

So, for our 4x4 matrix (which corresponds to a complete graph with 4 nodes), we have:

• An eigenvalue of 3 (which is 4-1) with multiplicity 1, and

• An eigenvalue of -1 with multiplicity 3 (which is 4-1).

 

So, the largest eigenvalue of the given matrix is 3.

Comments

Learned something new! Thanks

Answer 4

Easier approach:

Comments

everything you did is fine If I consider that you mean determinant by the square braces! you goofed up big time buddy. You meant determinant but used the matrix notation thus taking 3 common from c1 is impossible

---

in matrix you can't able to take common. and u took common for column 1 and wrote that you took for row. sorry to point out but I have to