Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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