# improved analysis of spectral gap of zigzag product?

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction:

Moreover, the variational definition of the second eigenvalue better captures the symmetry of the zig and zag steps (and gives a better bound than what can be obtained from this asymmetric intuition).

However, by following the asymmetric intuition (that $$\tilde{A}$$ sends most of the mass of a parallel vector to the perpendicular subspace), I am able to obtain a slightly better bound than the paper: I am able to show that the zigzag product of a $$(N, D, \lambda_1)$$ graph and $$(D, D_2, \lambda_2)$$ graph has second eigenvalue $$\leq \lambda_1 + \lambda_2 - \lambda_1\lambda_2$$, while the paper shows a bound of $$\lambda_1 + 2\lambda_2 + \lambda_2^2$$.

Is my proof correct? Pointing out errors will be appreciated. (Borrowing notiations from the paper: $$x^{\parallel}$$ denotes projection of $$x$$ to the parallel subspace, consisting of vectors uniform on each cloud, and $$x^{\perp}$$ denotes the projection to its orthogonal complement)

Let $$G$$ be a $$(N, D, \lambda_1)$$ expander, and let $$H$$ be a $$(D, D_2, \lambda_2)$$ expander. We want to upper bound the second eigenvalue of $$G _{z} H$$.

We want to upper bound $$||Mx||_2$$ subject to $$||x||_2=1, x \perp 1_{V_1 \otimes V_2}$$ where $$M= \tilde{H}\tilde{G}\tilde{H}$$, where $$\tilde{H}= I_{V_1} \otimes H$$ and $$\tilde{G}$$ is the permutation matrix for the permutation $$(v,i) \rightarrow \text{Rot}(v,i)$$. Write $$x = x^{\parallel} + x^{\perp}$$. By triangle inequality $$||Mx|| \leq ||Mx^{\parallel}|| + ||Mx^{\perp}||$$. We have $$||\tilde{H}x^{\perp}|| \leq \lambda_2 ||x^{\perp}|| \implies ||\tilde{H}\tilde{G}\tilde{H}x^{\perp}|| \leq ||Hx^{\perp}|| \leq \lambda_2 ||x^{\perp}||$$

Now we have to upper bound $$||\tilde{H}\tilde{G}\tilde{H}x^{\parallel}|| = ||\tilde{H}\tilde{G}x^{\parallel}||$$. Decompose $$\tilde{G}x^{\parallel} = (Gx^{\parallel})^{\parallel} + (Gx^{\parallel})^{\perp}$$. We have $$||\tilde{H}Gx^{\parallel}|| \leq ||\tilde{H}(\tilde{G}x^{\parallel})^{\parallel}|| + ||\tilde{H}(\tilde{G}x^{\parallel})^{\perp}||\leq ||(\tilde{G}x^{\parallel})^{\parallel}|| + \lambda_2 ||(\tilde{G}x^{\parallel})^{\perp}||$$

It is easy to see $$x^{\parallel} = \alpha \otimes 1_{V_2}$$ for some vector $$\alpha$$ with $$\alpha \perp 1_{V_1}$$ and $$||\alpha|| = ||x^{\parallel}||$$. Easy computations (as done in the paper) show that $$|| \tilde{G} x^{\parallel}|| = ||G \alpha|| \leq \lambda_1|| \alpha|| = \lambda_1 ||x^{\parallel}||$$ Also, since $$\tilde{G}$$ is a permutation, $$||\tilde{G}x^{\parallel}|| = ||x^{\parallel}|| \implies ||(\tilde{G}x^{\parallel})^{\parallel}|| + || (\tilde{G}x^{\parallel})^{\perp}|| = ||x^{\parallel}||$$

Let $$c= ||x^{\parallel}|| = ||\tilde{G}x^{\parallel}||, a= ||(\tilde{G} x^{\parallel})^{\parallel}|| , b= ||(\tilde{G}x^{\parallel})^{\perp}||$$. We have $$c=a+b$$ and we want to upper bound $$a + \lambda_2 b$$, given that $$a \leq \lambda_1 c$$.

Since $$b \geq (1-\lambda_1)c$$, we have

$$a + \lambda_2 b = c - (1-\lambda_2)b \leq (1 - (1-\lambda_1)(1-\lambda_2))c = (\lambda_1 + \lambda_2 - \lambda_1\lambda_2)c$$

So we have $$||\tilde{H}Gx^{\parallel}|| \leq (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2) ||x^{\parallel}||$$ and putting it all together, we get that $$|\tilde{H}\tilde{G}\tilde{H}x|| \leq \lambda_2 ||x^{\perp}|| + (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2) ||x^{\parallel}|| \leq (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2)||x||$$ In the last step we used the fact that $$\lambda_2 \leq \lambda_2 + \lambda_1 - \lambda_1 \lambda_2$$.