GATE CS 2021 Set 1 Q52 — Eigenvalues and Eigenvectors, LU Decomposition

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

We can find the eigenvalues of $A$ using two elegant methods:

Method 1: Row Sum Property

Notice that the sum of elements in each row of the matrix is constant:

• Row 1: $0 + 1 + 1 + 1 = 3$
• Row 2: $1 + 0 + 1 + 1 = 3$
• Row 3: $1 + 1 + 0 + 1 = 3$
• Row 4: $1 + 1 + 1 + 0 = 3$

For any matrix where the sum of each row is a constant $S$, $S$ is guaranteed to be an eigenvalue of that matrix (with the corresponding eigenvector being $[1, 1, 1, 1]^T$). Therefore, $\lambda = 3$ is an eigenvalue of $A$.

Method 2: Using the All-Ones Matrix

We can express $A$ as:

where $J$ is the $4 \times 4$ all-ones matrix and $I$ is the $4 \times 4$ identity matrix:

The matrix $J$ has rank $1$, which means $0$ is an eigenvalue of $J$ with multiplicity $3$ (i.e., $4 - 1$). The remaining eigenvalue is equal to the trace of $J$, which is $1 + 1 + 1 + 1 = 4$. Thus, the eigenvalues of $J$ are $\{4, 0, 0, 0\}$.

Since $A = J - I$, the eigenvalues of $A$ are obtained by subtracting $1$ from each eigenvalue of $J$:

Comparing the eigenvalues $\{3, -1, -1, -1\}$, the largest eigenvalue is 3.