# Understanding Gillman's proof of the Chernoff bound for expander graphs

My question is about the proof of Claim 1 in this paper: Gillman (1993). At the end of the proof, the author says:

The matrix product $$U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$$, which is equal to $$(D'-\mu I)(I+(D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U)$$, is singular. Therefore,

\begin{align*} 1&\leq \lVert (D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U \rVert_2 \\ &\leq \frac{1}{\mu-\lambda_2}(\mathrm{e}^x -1). \end{align*}

(The first inequality uses the continuity of the function $$\lambda_2(y)$$.)

I understand why the two expressions at the beginning are equal and I understand the second inequality, but I do not understand the first inequality and also why the matrix product is singular.

Let me provide the definitions so you can avoid reading the whole paper. There is a weighted undirected graph $$G=(V, E, w)$$ where $$w_{ij}=0$$ if $$\{i,j\}\notin E$$. Denote $$w_i:=\sum_j w_{ij}$$. Let $$P$$ denote the transition matrix, so $$P_{ij}:=\frac{w_{ij}}{w_i}$$. Denote by $$\lambda_2$$ the second largest eigenvalue of $$P$$ and by $$\epsilon:=1-\lambda_2$$ the spectral gap. Next, let $$M$$ be the weighted adjacency matrix $$M_{ij}:=w_{ij}$$. Let $$A$$ be a set of vertices and $$\chi_A$$ be an indicator function. Some more definitions are:

\begin{align*} &E_r:=\operatorname{diag}(\mathrm{e}^{r\chi_A}) & &P(r):=PE_r \\ &D:=\operatorname{diag}(\frac{1}{w_i}) & &S:=\sqrt{D}M\sqrt{D} \\ &S_r:=\sqrt{DE_r}M\sqrt{DE_r} & & B(r):=\frac{1}{\mathrm{e}-1}(P(r+1)-P(r)) \end{align*}

Moreover, since $$S$$ is unitarily diagonalizable, there exist a unitary matrix $$U$$ and a diagonal matrix $$D'$$ such that $$D'=U^\top SU$$. Furthermore, there exists a diagonal matrix $$D_A$$ such that $$B(0)=PD_A$$.

Define $$\lambda(r)$$ to be the largest eigenvalue of $$P(r)$$ and $$\lambda_2(r)$$ to be its second largest eigenvalue. As before, $$\epsilon_r := \lambda(r)-\lambda_2(r)$$ is the spectral gap.

In Claim 1 the author lets $$0\leq x\leq r$$ be some number. He also defines $$\mu<\lambda(x)$$ to be any other eigenvalue of $$P(x)$$. At the end of the proof, we are only interested in $$\mu>\lambda_2$$.

Some other facts are:

\begin{align*} &\lVert D' \rVert_2 = \lVert D_A \rVert_2 = 1 & &D'=U^\top\sqrt{D^{-1}}P\sqrt{D}U \\ &P(0)=P & &\lambda(0)=1 & &\lambda_2(0)=\lambda_2 \\ &P=\sqrt{D}S\sqrt{D^{-1}} & &P(r)=\sqrt{DE_r^{-1}}S_r\sqrt{E_rD^{-1}} \end{align*}

I hope I didn't miss anything relevant. Thank you for your help.

First, we'll explain why $$U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$$ is sungular. It is enough to show that $$P+(\mathrm{e}^x-1)B(0)$$ has eigenvalue $$\mu$$. We know that $$\mu$$ is an eigenvalue of $$P(x)$$, so we'll show why $$P+(\mathrm{e}^x-1)B(0) = P(x)$$.
Note that $$E_r:=\operatorname{diag}(\mathrm{e}^{r\chi_A})=(\mathrm{e}^r-1)\operatorname{diag}(\chi_A)+I$$ because $$\chi_A$$ is binary. Therefore, \begin{align*} B(r)&:=\frac{1}{\mathrm{e}-1}(P(r+1)-P(r)) = \frac{1}{\mathrm{e}-1}P\cdot(E_{r+1}-E_r) \\ &= \frac{1}{\mathrm{e}-1}P\cdot((\mathrm{e}^{r+1}-1)\operatorname{diag}(\chi_A) - (\mathrm{e}^r-1)\operatorname{diag}(\chi_A)) \\ &= \frac{1}{\mathrm{e}-1}P\cdot(\mathrm{e}^{r+1}-\mathrm{e}^r)\operatorname{diag}(\chi_A) = \mathrm{e}^rP\operatorname{diag}(\chi_A) \end{align*} And specifically $$B(0)=P\operatorname{diag}(\chi_A)$$. Now,
\begin{align*} P+(\mathrm{e}^x-1)B(0) &= P+(\mathrm{e}^x-1)P\operatorname{diag}(\chi_A) \\ &= P((\mathrm{e}^x-1)\operatorname{diag}(\chi_A)+I) \\ &= PE_x = P(x) \end{align*} Therefore $$\mu$$ is an eigenvalue of $$P+(\mathrm{e}^x-1)B(0)$$ and hence $$U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$$ is sungular.
Second, denote $$C:=(D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U$$. We'll explain why $$1\leq \lVert C \rVert_2$$. We know that \begin{align*} (D'-\mu I)(I+C) &= (D'-\mu I)(I+(D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U) \\ &= U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U \end{align*} which we shown is singular, so $$(D'-\mu I)(I+C)$$ is singular. But $$D'-\mu I$$ is invertible, hence $$I+C$$ is singular. Now, there exists a vector $$v\neq 0$$ such that $$(I+C)v=0$$. So $$Cv=-v$$, and then $$\lVert Cv \rVert = \lVert v \rVert$$. Therefore $$\frac{\lVert Cv \rVert}{\lVert v \rVert} = 1$$ for some vector $$v\neq 0$$.
Finally, by definition $$\begin{equation*} \lVert C \rVert := \sup_{w\neq 0}\frac{\lVert Cw \rVert}{\lVert w \rVert}\geq \frac{\lVert Cv \rVert}{\lVert v \rVert} = 1 \end{equation*}$$
{"ft_lang_label":"__label__en","ft_lang_prob":0.6290871,"math_prob":1.0000058,"size":2399,"snap":"2020-10-2020-16","text_gpt3_token_len":859,"char_repetition_ratio":0.11691023,"word_repetition_ratio":0.012658228,"special_character_ratio":0.35973322,"punctuation_ratio":0.10220441,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000097,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-07T19:16:13Z\",\"WARC-Record-ID\":\"<urn:uuid:31e663ed-ed63-454b-b2c2-442a1bfd78b2>\",\"Content-Length\":\"124062\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:cf43ca3b-a4df-4b5d-86a0-9e31ed5cfdee>\",\"WARC-Concurrent-To\":\"<urn:uuid:a653d94b-d6bc-41a0-9f2a-2ff5572f5af9>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/334758/understanding-gillmans-proof-of-the-chernoff-bound-for-expander-graphs\",\"WARC-Payload-Digest\":\"sha1:HOH6AISILTCC6V3WVRTS4F3ZUYA6SS6I\",\"WARC-Block-Digest\":\"sha1:GZWYPPJPLTCFRONIO2ATKMXG7SMHIHH3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585371805747.72_warc_CC-MAIN-20200407183818-20200407214318-00159.warc.gz\"}"}