# Why does this matrix have 3 nonzero distinct eigenvalues

Consider the $n \times n$ matrix $$A=\left[ \begin{array}{cccc} 0 & 1 & ... & 1 \\ 1 & 0 & & 0 \\ \vdots & & \ddots & \\ 1 & 0 & & 0% \end{array}% \right]$$ (A has $n-1$ ones in the first row, $n-1$ ones in the first column, and zeros anywhere else), and let $$G=A(I_n-\theta A)^{-1},$$ where $\theta$ is a scalar such that $I_n-\theta A$ is positive definite.

Let $W$ be a nontrivial subspace of $\mathbb{R}^{n}$ including the vector of all ones, and no eigenvectors of $A$. Let $M$ be the orthogonal projector onto the orthogonal complement of $W$.

Let $$Q=G-\frac{1}{n}\mathrm{trace}(G) I_{n}.$$

Show that $$MQ+QM$$ has exactly 3 nonzero distinct eigenvalues (for any $n$, any $\theta$ such that $I_n-\theta A$ is positive definite, any $W \subset \mathbb{R}^{n}$ including the vector of all ones).

• Why? What's the motivation for this? – Gerry Myerson Feb 25 '13 at 2:35
• In a statistical model whose variance matrix is a function of the adjacency matrix of the star graph, I need to study the properties of $y^T(MQ+QM)y$, where $y$ is a $n \times 1$ Gaussian vector. In this context $W$ is the column space of the regressors. Numerically it seems that $MQ+QM$ has always 3 nonzero distinct eigenvalues, which would simplify the distribution theory enormously. The fact that the vector of all ones belongs to $E_1 \oplus E_2$, where $E_1$ and $E_2$ are the two 1-dimensional eigenspaces of $A$ seems to play an important role in the result. – mark Feb 25 '13 at 19:12
• OK. What can you say about the values of $\theta$ for which $I_n-\theta A$ is positive definite? (I doubt I'll be able to contribute anything toward the solution of your problem, but I am curious about this part of it). – Gerry Myerson Feb 25 '13 at 22:36
• @mark, your definition of $Q$ is incorrect, no? When you wrote $Q=\left( G-\frac{1}{n}\mathrm{trace}(G)\right) M$, did you mean $Q=\left( G-\frac{1}{n}\mathrm{trace}(G)I_n\right) M$ ? – Nathan Portland Feb 26 '13 at 2:44
• @nathan yes, thank you, edited – mark Feb 26 '13 at 11:45

Here is a sketch of proof. Since the eigenvalues of a linear operator are independent of the choice of basis, for ease of presentation, when we mention $A,G,Q$ or $M$ below, they are viewed as linear operators rather than matrices.
Consider an ordered orthonormal basis $\mathcal{U}=\left\{u_1,\ u_2,\ \ldots,\ \right\}$ where \begin{align*} u_1&=\frac1R(1,1,\ldots,1)^T,\\ u_2&=\frac1R(r,\,-1/r,\,\ldots,\,-1/r)^T \end{align*} with $r=\sqrt{n-1}$ and $R=\sqrt{n}$. One can verify that under $\mathcal{U}$, the matrix of $A$ is given by $A'\oplus0_{(n-2)\times(n-2)}$ and the matrix of $G$ is given by $G'\oplus0_{(n-2)\times(n-2)}$, where \begin{equation} A'=\frac{r}{R^2}\begin{pmatrix}2r&r^2-1\\ r^2-1&-2r\end{pmatrix}, \quad G'=\frac{A'+r^2\theta I_2}{1-r^2\theta^2}.\tag{1} \end{equation} We will now prove your assertion under the assumption that $u_2\notin W^\perp$. (The case $u_2\in W^\perp$ is similar but simpler and hence it is omitted here.) Let $\mathcal{V}=\{v_1,\ldots,v_n\}$ be an orthonormal basis such that $v_1,\ldots,v_k$ form a basis of $W$ and the other $v_i$s form a basis of $W^\perp$. Here $v_1,v_2$ and $v_{k+1}$ are chosen as follows: \begin{align} v_1&=u_1,\\ v_{k+1}&=\frac{Mu_2}{\|Mu_2\|},\tag{2}\\ v_2&=\frac{(I-M)u_2}{\|(I-M)u_2\|}\tag{3}. \end{align} Recall that $u_1\perp u_2$ and by assumption, $u_1\in W \perp Mu_2\in W^\perp$. Therefore $u_1,\,Mu_2$ and $(I-M)u_2$ are orthogonal to each other. Also, as the matrix of $A$ is $A'\oplus0_{(n-2)\times(n-2)}$ under the basis $\{u_1,u_2,\ldots\}$, some two eigenvectors of $A$ are spanned by $u_1$ and $u_2$. However, by the given conditions, $u_1\in W$ and the eigenvectors of $A$ do not lie inside $W$. Therefore $u_2$ must not lie inside $W$. Hence $Mu_2\not=0$. Yet we have assumed that $u_2\notin W^\perp$. So $(I-M)u_2$ is also nonzero. Hence the denominators in $(2)$ and $(3)$ are nonzero and $\{v_1,v_2,v_{k+1}\}$ is indeed an orthonormal set of vectors.
Now, since $\mathcal{V}$ is orthonormal, for $i\not=1,2,k+1$, we have $v_i\perp\operatorname{span}\{v_1,v_2,v_{k+1}\}$ and hence $v_i\perp u_1, u_2$. Therefore the matrix of $G$ under $\mathcal{V}$ is of the form \begin{equation} \left[\begin{array}{ccc|cc} \ast&\ast&&a\\ \ast&\ast&&b\\ &&0\\ \hline a&b&&\ast\\ &&&&0 \end{array}\right]\tag{4} \end{equation} where the two zero matrices are of sizes $(k-2)\times(k-2)$ and $(n-k-1)\times(n-k-1)$ respectively. By $(1)$, $Gu_1$ has a nonzero component in $u_2$. Since $u_2\notin W$ and $W^\perp$, it follows that $a\not=0$ in $(4)$. Therefore the matrix of $QM+MQ$ under $\mathcal{V}$ is of the form \begin{equation} \left[\begin{array}{ccc|cc} 0&&&a\\ &0&&b\\ &&0_{(k-2)\times(k-2)}\\ \hline a&b&&c\\ &&&&sI_{n-k-1} \end{array}\right] \end{equation} where $s=-\frac1n\operatorname{trace}(G)=\frac{-2r^2\theta}{n(1-r^2\theta^2)}$. This matrix is permutation similar to \begin{equation} \left[\begin{array}{ccc|cc} 0&0&a\\ 0&0&b\\ a&b&c\\ \hline &&&0_{(k-2)\times(k-2)}\\ &&&&2sI_{n-k-1} \end{array}\right]=S\oplus0_{(k-2)\times(k-2)}\oplus(2sI_{n-k-1}). \end{equation} So, if $\theta\not=0$ and $n-k-1>0$ (i.e. if $\theta\not=0$ and $\dim W\le n-2$, otherwise your assertion is not true), one nonzero but perhaps repeated eigenvalue of $QM+MQ$ is $\lambda=2s=\frac{-4r^2\theta}{n(1-r^2\theta^2)}$, which is contributed by the block $2sI_{n-k-1}$. Also, the characteristic equation of $S$ is $x(x^2-cx-a^2-b^2)=0$. As $a\not=0$, this equation has one zero root and two distinct nonzero roots. If you can show that these two nonzero roots are not equal to $2s$, then we are done. However, since $W$ is chosen arbitrarily, I think there might be a measure-zero set of failure cases.
• This is great! How did you move from (4) to the form of $QM+MQ$? – mark Feb 27 '13 at 11:36
• @mark The basis $\mathcal{V}$ is chosen such that $v_1,\ldots,v_k$ span $W$ and the rest of $v_i$s span $W^\perp$. So, the matrix of $M$ under this basis is $0_{k\times k}\oplus I_{n-k}$. Now, simply compute $QM+MQ$ directly. – user1551 Feb 27 '13 at 11:51
• Thank you, I feel like I'm learning a lot. Would your method of proof still apply if $A$ is transformed to a row-stochastic matrix by diving each of its rows by the corresponding row sum. In that case $u_{1}$ is an eigenvector of (the transformed) $A$, but we loose symmetry. The reason I'm asking is that, from my numerical experiments, it seems like my statement (with your added conditions) holds also in that case. – mark Feb 27 '13 at 12:24
• Thanks for the clarifying questions. I am interested in the case when $(1-\theta A)^{-1}$ is p.d. (but probably all is needed is that it is invertible). $M$ would still be an orthogonal projector. And I would consider $QM+(QM)^T$. I will provide a numerical example next. – mark Feb 27 '13 at 12:54
• @mark Recall that the matrix of $G$ under $\mathcal{U}$ is of the form $G'\oplus0_{(n-2)\times(n-2)}$. Thus $Gv=0$ for every $v\perp u_1,u_2$. Since $v_i\perp u_1,u_2$ for every $i\not=1,2,k+1$, it follows that $G$ has a zero $i$-th column for every such $i$. As $G$ is symmetric, we get (4). – user1551 Mar 5 '13 at 1:01