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.



Bounding 2nd Eigenvalue of a Pseudo-Rotation-ish matrix
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.


