Special Eigenvalues of a Matrix in Strang p.368

Question

This question arises from Strang's Linear Algebra p.368. It concerns the matrix $$A = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \right)$$. Some straightforward computation shows that $$AA^T = \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4 \\ \end{array} \right) \ \text{ and } \ (AA^T)^{-1} = \left( \begin{array}{cccc} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 1 \\ \end{array} \right)$$ Now the textbook claims that all eigenvalues of $(AA^T)^{-1}$ have the form $2-2\cos(\theta)$. Is it straightforward from the context?

Answer 1

If we're looking for the fact that each eigenvalue can be expressed as $2 - 2 \cos \theta$ for some $\theta$, which is to say that the eigenvalues fall on the interval $[0,4]$, then there is indeed a straightforward way to confirm that this is the case.

It suffices to note that the eigenvalues are real because $(AA^T)^{-1}$ is symmetric, and that they must satisfy $|\lambda - 2| \leq 2$ either by the Gershgorin disk theorem or by considering either the $p=1$ or $p=\infty$ operator $p$-norm of $(AA^T)^{-1} - 2I$.

---

If we're looking for the exact expression for the eigenvalues, then no, the fact is not quite straightforward. However, we can see this relatively quickly if we correctly "guess" the eigenvectors of this matrix. In particular, every eigenvector has the form $$ v = \left(\sin (\theta), \sin \left( 2\theta\right), \sin \left( 3\theta \right), \sin \left( 4\theta\right) \right)^T $$ For $\theta = \frac{\pi k}{5}$ with $k = 1,\dots,4$. It now suffices to verify that for these $\theta$, we have $$ (AA^T)^{-1}v = \left[2 - 2 \cos(\theta)\right] v. $$

---

Let $\theta$ be arbitrary, let $v$ be the vector above, and let $y = (y_1,\dots,y_4)^T$ be the vector $(AA^T)^{-1}v$. We would like to find the $\theta$ for which $y$ is a multiple of $v$. We compute as follows: $$ y_1 = 2 \sin \theta - \sin(2 \theta) = 2 \sin\theta - 2 \sin\theta \cos \theta = (2 - 2 \cos \theta)\sin \theta = (2 - 2 \cos \theta) v_1 $$ The computations for $y_2$ and $y_3$ are similar. Using the the sum to product identity, we have $$ \begin{align} y_2 &= 2 \sin(2 \theta) - (\sin \theta + \sin (3 \theta)) \\ & = 4 \sin \theta \cos \theta - 2\sin\left( \frac{3 \theta + \theta}{2}\right) \cos \left( \frac{3 \theta - \theta}{2}\right) \\ & = (2 - 2 \cos \theta)\sin(2 \theta) = (2 - 2\cos \theta) v_2 \end{align} $$ In general, we have $$ 2 \sin(k \theta) - (\sin ((k-1)\theta) + \sin ((k+1) \theta)) = (2 - 2 \cos \theta)\sin(k \theta). $$ So, we can similarly say that $y_3 = (2 - 2\cos \theta) v_3$. If you prefer, we could also have handled $y_1$ with this trick, since $$ 2 \sin \theta - \sin(2 \theta) = 2 \sin (1 \cdot \theta) - (\sin(0 \cdot \theta) + \sin (2 \cdot \theta)). $$

So far, we have not deduced any conditions on $\theta$. For the last entry, we reapply the above computational trick to find that $$ \begin{align} y_4 = 2 \sin(4 \theta) - \sin (3 \theta) &= [2 \sin(4 \theta) - (\sin (3 \theta) + \sin(5\theta))] + \sin (5 \theta) \\ & = (2 - 2\cos \theta)\sin(4 \theta) + \sin(5 \theta) = (2 - 2\cos \theta)v_4 + \sin(5 \theta). \end{align} $$ So, we see that $y$ will be a multiple of $v$ (which is to say that $v$ will be an eigenvector) if and only if $\sin(5\theta) = 0$, which leads us to the characterization above.