# Bounding 2nd Eigenvalue of a Pseudo-Rotation-ish matrix

Let $p,q$ be arbitrary primes.

Let $N = p * q$.

Let $I$ be the $N * N$ identity matrix.

Let $R$ be the $N * N$ matrix defined as follows: $R[x_0 * p + y_0, x_1 * p + y_1]=1$ if and only if $x_0+1 \equiv x_1 (\mod q)$ and $y_0 + 1 \equiv y_1 (\mod p)$.

Let $A = \begin{pmatrix} \frac12I & \frac12R \\\\ \frac12R & \frac12I \end{pmatrix}$.

The largest eigenvalue of $A$ is 1.0, associated with the all 1 vector.

Question: how can I show that the second largest (absolute value of) eigenvalue is < 1?

I'm not particularly concerned with the bound. For example, $\lambda < 1 - 2^{p*q}$ is perfectly fine. I just need to show that it's < 1.

Context: derandomization.

-
It seems to me that $R$ can be written as a tensor product of $S \in M_q$ and $T \in M_p$, given by $$S[x_0,x_1] = 1 \Leftrightarrow x_0 + 1 \equiv x_1\ (mod\ p)$$ and $$T[y_0,y_1] = 1 \Leftrightarrow y_0 + 1 \equiv y_1 \ (mod\ p)$$ I suspect that there is a typo, and the condition on $S$ is supposed to be $y_0+1 \equiv y_1\ (mod\ q)$. In any case, this tensor product formulation may be helpful. – Aaron Tikuisis Mar 17 '12 at 14:54

With reference to the tensor product formulation that I gave in my comment, we notice that $S$ is unitarily equivalent to $$diag(\alpha, \alpha^2, \dots, \alpha^q)$$ where $\alpha = exp(2\pi i/q)$, and likewise $T$ is unitarily equivalent to $$diag(\beta, \dots, \beta^p)$$ where $\beta = exp(2\pi i/p)$. Therefore, $A$ is unitarily equivalent to $$1/2 \begin{pmatrix} I_{pq} & diag(\gamma,\dots,\gamma^{pq}) \\ diag(\gamma,\dots,\gamma^{pq}) & I_{pq} \end{pmatrix},$$ where $\gamma=\alpha\beta$. Subtracting $1/2I_{2pq}$ from this gives $$1/2 \begin{pmatrix} 0_{pq} & diag(\gamma,\dots,\gamma^{pq}) \\ diag(\gamma,\dots,\gamma^{pq}) & 0_{pq} \end{pmatrix} = 1/2 \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes diag(\gamma,\dots,\gamma^{pq}).$$

The eigenvalues of $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ are $\pm 1$, while the eigenvalues of $diag(\gamma,\dots,\gamma^{pq})$ are $\gamma,\dots,\gamma^{pq}$, so the eigenvalues of $$1/2 \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes diag(\gamma,\dots,\gamma^{pq})$$ are $\pm\gamma/2,\dots,\pm\gamma^{pq}/2$. The eigenvalues of $A$ are therefore $(1\pm \gamma)/2,\dots,(1\pm\gamma^{pq})/2$. Your desired bound follows.

-
Wait. How do you get from X is unitarity equivalent to Y to: 1/2 [ [I X] [X I]] is unitarilye quivalent to 1/2[[ I Y] [ Y I]] ? – user22209 Mar 17 '12 at 19:10
This makes sense to me now. Thanks! – user22209 Mar 17 '12 at 20:01
While I appreciate that you picked my answer, I think that you may find it worth your while even to look at en.wikipedia.org/wiki/Perron–Frobenius_theorem . The Perron-Frobenius theorem may come in handy for similar problems. (Of course, recognizing when matrices have tensor decompositions can also come in handy.) – Aaron Tikuisis Mar 17 '12 at 20:58

You matrix is non-negative. Thus $1$ is its Perron eigenvalue. You only have to verify that its is irreducible and not cyclic. Then apply Perron-Frobenius theorem (section 8.3 of my book Matrices (Springer-Verlad GTM 216, 2nd edition), together with Section 8.4.

-
Well that's much simpler than what I did. To show that $A$ is nonnegative, must we verify that $\|R\| = \|S\|\|T\| = 1$, or is there a quicker way? – Aaron Tikuisis Mar 17 '12 at 16:55
$A$ is non-negative. In the Perron-Frobenius' theory, this means that every entry $a_{ij}$ is non-negative. Irreducible means that it is not `block-triangular'. Read chapter 8 of my book. This is a very classical topic that more or less every experienced mathematician learn one day or the other. – Denis Serre Mar 17 '12 at 18:28
Sorry, I currently do not have a copy of your book and thus am unable to appreciate the beauty of this proof. – user22209 Mar 17 '12 at 20:02