# Symmetries of the singular vectors of the line graph

Consider the matrix $$A = \left( \begin{matrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/3 & 1/3 & 1/3 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ \vdots & \ & \ddots & & \ddots & \\ 0 & \cdots & 0 & 1/3 & 1/3 & 1/3 \\ 0 & \cdots & 0 & 0 & 1/2 & 1/2 \end{matrix} \right)$$

This question is about the singular vectors of $A$, i.e., the eigenvectors of $A^T A$. Ill denote them by $v_1, \ldots, v_n$. Suppose $n$ is even, and let $P$ be the permutation matrix which flips the vector around the midpoint, i.e., $P$ flips entries $1$ and $n$, entries $2$ and $n-1$, and finally entries $n/2$ and $n/2+1$.

Observation: A few numerical experiments in MATLAB suggest that exactly half of the $v_i$ satisfy $Pv=-v$ and the remainder satisfy $Pv=v$.

My question: Can someone provide an explanation for why this is the case?

Update: I suppose I should note that it isn't surprising that we can find eigenvectors which satisfy either $Pv=v$ or $Pv=-v$. Indeed, we can go through the list of $v_1, \ldots, v_n$ and if $Pv_i \neq v_i$, then because $Pv_i$ is also an eigenvector of $A^T A$ with the same eigenvalue, we can replace $v_i$ with $v_i'=v_i+Pv_i, v_i''=v_i-Pv_i$; then $Pv_i' = v_i', Pv_i'' = -v_i''$; finally we can throw out the redundant vectors. What is surprising to me is that the orthogonal basis returned by the MATLAB eig command has exactly half of the vectors which satisfy $Pv=v$ and exactly half which satisfy $Pv=-v$.

-

The vectors (general vectors, not eigenvectors) with either kind of parity form $n/2$-dimensional subspaces. For instance, a basis for the even vectors is $(1,0,0,\dotsc,0,0,1)$, $(0,1,0,\dots,0,1,0)$, $\dotsc$
You've already explained that we can choose an eigenbasis for $A$ in which all vectors have definite parity. Since there can be at most $n/2$ of either kind, there must be exactly $n/2$ of either kind.
Thanks, this explains 95% of what I am asking for. One small thing still requires an explanation though. I can see that one can pick a basis of eigenvectors of $A^T A$ such that for half of them $Pv=v$ and for half of them $Pv=-v$. But how to show that you can pick an orthogonal basis of eigenvectors with the same property? – robinson Feb 9 '12 at 21:17
@robinson: Eigenvectors for different eigenvalues of a symmetric matrix ($A^TA$ is symmetric) are orthogonal, and vectors of different parity are orthogonal So the only choice lies in eigenvectors with the same parity and the same eigenvalue; since any linear combination of these again has the same parity and eigenvalue, you can simply orthogonalize them. – joriki Feb 9 '12 at 22:43