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).

  • $\begingroup$ Why? What's the motivation for this? $\endgroup$ – Gerry Myerson Feb 25 '13 at 2:35
  • 1
    $\begingroup$ 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. $\endgroup$ – mark Feb 25 '13 at 19:12
  • $\begingroup$ 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). $\endgroup$ – Gerry Myerson Feb 25 '13 at 22:36
  • $\begingroup$ @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$ ? $\endgroup$ – Nathan Portland Feb 26 '13 at 2:44
  • $\begingroup$ @nathan yes, thank you, edited $\endgroup$ – 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.

  • $\begingroup$ This is great! How did you move from (4) to the form of $QM+MQ$? $\endgroup$ – mark Feb 27 '13 at 11:36
  • 1
    $\begingroup$ @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. $\endgroup$ – user1551 Feb 27 '13 at 11:51
  • $\begingroup$ 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. $\endgroup$ – mark Feb 27 '13 at 12:24
  • $\begingroup$ 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. $\endgroup$ – mark Feb 27 '13 at 12:54
  • 1
    $\begingroup$ @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). $\endgroup$ – user1551 Mar 5 '13 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.