Problem Statement

Given an $n \times n$ square matrix with $n$ on the diagonal entries and $1$ in every other entry. Find eigenvalues and eigenvectors of this matrix and justify why.

This is one of the problems that I was quizzed on in my Linear Algebra & Applied Matrix Theory course at Stanford. I recently re-discovered it while reading the lecture notes and the textbook to review SVD.

Give yourself sufficient amount of time to attempt this problem and read the solutions below.

Solution

Let $\mathbf A_n$ denote the $n \times n$ matrix of our interest.

First Pass: A Naïve Approach

For a $2 \times 2$ matrix, it's not difficult to manually find the eigenvalues and eigenvectors. With

and solve for the characteristic polymonial $\det (\mathbf A_2 - \lambda I_2) = 0$. We have $(2 - \lambda)^2 - 1 = 0$, hence $\lambda_1 = 1$ and $\lambda_2 = 3$. The associated eigenvectors are, respectively,

We can proceed with a similar approach with $\mathbf A_3$. However, as we can see without going further, the characteristic polynomial we have to solve gets increasingly complicated. Fortunately, once we discover a pattern, an elegant solution presents itself.

Transforming $\mathbf A_n$ Into a Matrix of All Ones

Since all the entries except for the diagonal entries are $1$, we can focus on a second type of matrix $\mathbf B_n = \mathbf A_n - (n-1)\mathbf I_n$. Notice that $\mathbf B_n$ is a matrix of all $1$ s, or equivalently, $\mathbf 1 \mathbf 1^\top$, hence a rank-1 matrix. That $\mathbf B_n$ is rank 1 is not difficult to see, since all $n$ column vectors are identical and its column space $\text{Col}(\mathbf B_n) = \text{span}\left( \begin{bmatrix} 1, 1, 1, 1 \end{bmatrix}^\top \right)$. By the rank-nullity theorem, the nullity of $\mathbf B_n$ is $n-1$. This in turn signifies that $\mathbf B_n$ has $n-1$ eigenvalues of $0$ and a single non-zero eigenvalue.

By inspection, we can see that $\begin{bmatrix} 1, 1, 1, 1 \end{bmatrix}^\top$ is the eigenvector of $\mathbf B_n$ with the associated eigenvalue $n$. In the case of $3 \times 3$ example,

Since all the other eigenvalues are $0$ s, we can obtain the eigenvectors by computing $\mathbf B_n \mathbf v = 0$, where $\mathbf v = \begin{bmatrix}v_1, \cdots, v_n \end{bmatrix}^\top$ is the eigenvector. For an arbitrary $n \geq 1$, this yields the equation $v_1 + v_2 + \cdots + v_n = 0$ and thus $v_1 = -v_2 -\cdots - v_n$. Jumping ahead quite a tedious computation, we end up with the following

where not all of $v_i$ 's where $2 \leq i \leq n$ are zeroes. We have just found $n-1$ other eigenvectors!

Let's put it together now. From the definition of eigenvalues and eigenvectors, we have $\mathbf B_n \mathbf v = \lambda \mathbf v$. Then, if we let $\mu$ be the eigenvalue of $\mathbf A_n$,

Since the eigenvalues of $\mathbf B_n$ are $0$ with multiplicity $n-1$ and $n$ with multiplicity $1$, we conclude that the eigenvalues of $\mathbf A_n$ are $n-1$ with multiplicity $n-1$ and $2n - 1$ with multiplicity $1$. The eigenvectors are invariant, hence identical as above.

Ending Remarks

I always find linear algebra so enticing and its theorems beautiful. There are plenty of intriguing high-quality problems on websites such as Stack Overflow, and I intend to present more problems of this kind in the future. Send me a message if you have any problems to suggest!