0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 17, 2012 at 14:54

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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]] ? $\endgroup$
    – user22209
    Mar 17, 2012 at 19:10
  • $\begingroup$ This makes sense to me now. Thanks! $\endgroup$
    – user22209
    Mar 17, 2012 at 20:01
  • $\begingroup$ 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.) $\endgroup$ Mar 17, 2012 at 20:58
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Mar 17, 2012 at 16:55
  • $\begingroup$ $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. $\endgroup$ Mar 17, 2012 at 18:28
  • $\begingroup$ Sorry, I currently do not have a copy of your book and thus am unable to appreciate the beauty of this proof. $\endgroup$
    – user22209
    Mar 17, 2012 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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