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*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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