My question is about the proof of Claim 1 in this paper: [Gillman (1993)](https://pdfs.semanticscholar.org/eae4/a397e716b677e79187ce51ab5dc1f6c3a34d.pdf).
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.



Understanding Gillman's proof of the Chernoff bound for expander graphs
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\*}


