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.

Improve this question
$\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$
    – Aaron Tikuisis
    Commented Mar 17, 2012 at 14:54

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented Mar 17, 2012 at 19:10
  • $\begingroup$ This makes sense to me now. Thanks! $\endgroup$
    – user22209
    Commented 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$
    – Aaron Tikuisis
    Commented 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.

Improve this answer
$\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$
    – Aaron Tikuisis
    Commented 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$
    – Denis Serre
    Commented 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
    Commented Mar 17, 2012 at 20:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .