GATE CS 2021 Set 1 Q.62 (CS Q.52): Linear Algebra

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 __________

Your answer

Official answer and solution

Official answer: 3
From: Official GATE 2021 answer key

Solution

Use the all-ones matrix identity or row-sum property of symmetric matrices.

Let $A$ be the given $4 \times 4$ matrix:

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

Notice that the sum of entries in every row of $A$ is constant:

0 + 1 + 1 + 1 = 3

For any square matrix where all row sums equal a constant $c$ , the vector of all ones $v = (1, 1, 1, 1)^T$ is an eigenvector with eigenvalue $\lambda = c$ . Thus, $\lambda = 3$ is an eigenvalue of $A$ .

To find all eigenvalues, express $A$ in terms of the all-ones matrix $J_4$ and the identity matrix $I_4$ :

A = J_4 - I_4

The eigenvalues of $J_4$ are $4$ (with multiplicity 1) and $0$ (with multiplicity 3). Subtracting $I_4$ shifts every eigenvalue by $-1$ :

\lambda(A) = 4 - 1 = 3, \quad \text{and} \quad 0 - 1 = -1 \;(\text{multiplicity } 3)

The eigenvalues of $A$ are $\{3, -1, -1, -1\}$ . Therefore, the largest eigenvalue is 3.

Final answer

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

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 62 of 65, printed as CS Q.52
Section: Computer Science and Information Technology

Report an error in this question

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

Question

Solution

Source