From 579d1b59775e777e1a3f81000a6620c34519bf70 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 27 Feb 2015 13:27:53 -0500
Subject: [ps2] end of problem 1

---
 ps2/main.tex | 115 +++++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 88 insertions(+), 27 deletions(-)

(limited to 'ps2/main.tex')

diff --git a/ps2/main.tex b/ps2/main.tex
index b6ce969..e59a055 100644
--- a/ps2/main.tex
+++ b/ps2/main.tex
@@ -90,43 +90,43 @@ $m_{i,j}\neq 0\Leftrightarrow j\in C_1$ and the fact that $\sum_{j=1}^n m_{i,j}
 Furthermore $x^1$ and $x^2$ are clearly orthogonal, so they span a vector space
 of dimension 2. Hence the multiplicity of $1$ as an eigenvalue is at least 2.
 
-\paragraph{} Let us now assume that $G$ is connected and let us consider an
-eigenvector $x$ for the eigenvalue 1. We have $M^k x = x$ for all $k$.
-Furthermore since $G$ is connected, we have that $M^n > 0$ (all the entries are
-positive). Indeed, there always exists at least one path of length $n$ between
-any two vertices. Writing $a_{i,j}$ the entries of $M^n$ and choosing $i^*\in
-\{1,\ldots n\}$ such that $|x_{i^*}| = \|x\|_{\infty}$ we have:
+\paragraph{} Let us now assume that $1$ has multiplicity at least $2$. We can
+find an eigenvector $x$ for $1$ orthogonal to $\lambda_1$, that is: $\sum_i x_i
+= 0$. Let us define $C_1 = \{i\in V: x_i > 0\}$ and $C_2 = \{i\in V: x_j\leq 0\}$.
+Because $x\neq 0$ and $\sum_i x_i = 0$, both $C_1$ and $C_2$ are non-empty.
+They are clearly disjoint and their union is $V$. We show that $C_1$ and $C_2$
+are disconnected. Let $i^*$ such that $|x_{i^*}| = \|x\|_{\infty}$. Without
+loss of generality we can assume $x_{i^*} > 0$ (otherwise we consider $x'
+= -x$).
 \begin{displaymath}
-    \sum_{j=1}^n a_{i^*,j}x_j = x_{i^*}
+    \sum_{j=1}^n m_{i^*,j}x_j = x_{i^*}
 \end{displaymath}
 Dividing by $x_{i^*}$ both sides (it is non-zero for the same reason as in
 \textbf{1.}):
 \begin{displaymath}
-    1 = \left|\sum_{j=1}^n a_{i^*,j}\frac{x_j}{x_{i^*}}\right|
-    \leq \sum_{j=1}^n a_{i^*,j}\left|\frac{x_j}{x_{i^*}}\right|
-    \leq \sum_{j=1}^n a_{i^*,j} = 1
+    1 = \left|\sum_{j=1}^n m_{i^*,j}\frac{x_j}{x_{i^*}}\right|
+    \leq \sum_{j=1}^n m_{i^*,j}\left|\frac{x_j}{x_{i^*}}\right|
+    \leq \sum_{j=1}^n m_{i^*,j} = 1
 \end{displaymath}
 where we again used the triangle inequality, the definition of $x_{i^*}$ and
-the fact that the sum of the entries of the rows of $M^n$ is one (indeed we
-have $M\textbf{1} = \textbf{1}$ where $\textbf{1}$ is the all-one vector, so
-$M^n\textbf{1} = \textbf{1}$). Hence, the chain of inequalities is a chain of
-equalities. Since $a_{i^*,j}\neq 0$ for all $j$, this implies that for all $j$:
-$|\frac{x_j}{x_{i*}}|=1$ and all the $\frac{x_j}{x_{i^*}}$ have the same sign.
-That is, for all $j$ $x_j = x_{i^*}$. Hence $x = \alpha \textbf{1}$ for some
-$\alpha$.
-
-We have just proved that $G$ connected implies that the multiplicity of $1$ is $1$
-(the eigenspace is spanned by $\textbf{1}$). The contrapositive gives the
-second part of the equivalence that we were asked to prove.
+the fact that the sum of the entries of the rows of $M$ is one. Hence, the
+chain of inequalities is a chain of equalities. This implies that for all $j$
+such that $m_{i,j} \neq 0$, $x_j=x_{i^*}$. But we can then repeatedly apply the
+same argument to all the neighbors of $i^*$, the neighbors of their neighbors,
+etc. By induction (over the distance to $i^*$), we see that for all vertices
+$j$ in the same connected component as $i^*$, $x_j = x_{i^*}>0$. This implies
+that $C_2$ is disconnected from $C_1$ (none of the vertices in $C_2$ are in the
+same connected component as $x_{i^*}$).
 
 \paragraph{3.} Assuming that $G$ is connected, it is easy to see that $G$
 bipartite is equivalent to $G^2$ being disconnected. Hence assuming $G$
 connected and using \textbf{2.}:
 
 $G$ bipartite $\Leftrightarrow$ $G^2$ disconnected $\Leftrightarrow$ $1$ is an eigenvalue of $M^2$
-of multiplicity at least 2 $\Leftrightarrow$ $\exists x\perp \mathbf{1},\; M^2x
-= x$ $\Leftrightarrow$ $\exists x\perp\mathbf{1},\; Mx
-= \pm x$ $\Leftrightarrow$ $\exists x\perp\mathbf{1},\; Mx = -x$ $\Leftrightarrow$ $-1$ is an eigenvalue of
+of multiplicity at least 2 $\Leftrightarrow$ $\exists x\perp \mathbf{1}, x\neq
+0,\; M^2x
+= x$ $\Leftrightarrow$ $\exists x\perp\mathbf{1}, x\neq 0,\; Mx
+= \pm x$ $\Leftrightarrow$ $\exists x\perp\mathbf{1}, x\neq 0,\; Mx = -x$ $\Leftrightarrow$ $-1$ is an eigenvalue of
 $M$.
 
 The antepenultimate equivalence uses that the eigenvalues of $M^2$ are the
@@ -143,7 +143,7 @@ and observing that $\|x\|_2 =1\Leftrightarrow \|Px\|_2 = 1$ we have:
     = 1} \sum_{i=1}^n\lambda_i y_i^2
 \end{displaymath}
 the right-hand side maximum is clearly obtained when $y_i = 1$ for some
-coordinated $i$ such that $\lambda_i = \lambda_{max}(M)$ and $y_j = 0$ for
+coordinate $i$ such that $\lambda_i = \lambda_{max}(M)$ and $y_j = 0$ for
 $j\neq i$. For this $y$ the value is $\lambda_{max}(M)$.
 
 Now observe that $\max_x\inprod{Mx, x}$ when $x$ is taken in the vector space
@@ -159,6 +159,67 @@ Hence:
 \end{displaymath}
 where the maximum is taken over $x$ of length 1 in the orthogonal space of $\mathbf{1}$.
 
-\paragrpha{} Let us now show the second identity given in the problem
-statement.
+\paragraph{} Let us now show the second identity given in the problem
+statement:
+\begin{displaymath}
+    \sum_{(i,j)\in E} (x_i-x_j)^2 = \sum_{(i,j)\in E} x_i^2 +
+    \sum_{(i,j)\in E} x_j^2 - 2\sum_{(i,j)\in E} x_ix_j = \frac{d}{2}\|x\|_2^2
+    + \frac{d}{2}\|x\|_2^2 - d\sum_{i,j} m_{i,j}x_i x_j
+\end{displaymath}
+where the second equality used that for all $i$ (resp. $j$) there are
+$\frac{d}{2}$ edges leaving (entering) and that $m_{i,j} = \frac{2}{d}a_{i,j}$
+where $a_{i,j}$ is the $(i,j)$ entry of the adjacency matrix of $G$. For
+$\|x\|_2 = 1$:
+\begin{displaymath}
+    1- \frac{1}{d}\sum_{(i,j)\in E} (x_i-x_j)^2
+    = \sum_{i,j}m_{i,j}x_i x_j = \inprod{Mx, x}
+\end{displaymath}
+taking the $\max$ both sides gives the second identity.
+
+Let us now consider $x$ such that $\|x\|_2 = 1$ and  $\sum_{i} x_i
+= 0$ and consider $i^*$ such that $|x_{i^*}| = \|x\|_{\infty}$. Because
+$\|x\|_2 =1$, we have $|x_{i^*}| \geq \frac{1}{\sqrt{n}}$. Because, $\sum_i x_i
+= 0$ there is $x_k$ such that $x_k$ has the opposite sign of $x_{i^*}$. Since $G$
+is connected, there is a path of length $l$ at most $n$ from $i^*$ to $k$. Let us
+index this path $i^* = i_1,\ldots, i_l = k$. Then:
+\begin{displaymath}
+    \sum_{(i,j)\in E} (x_i-x_j)^2 \geq  \sum_{s=1}^l (x_{i_{s+1}}
+    - x_{i_s})^2
+\end{displaymath}
+where we restricted the sum on the path from $i^*$ to $k$. Applying the
+Cauchy-Schwartz inequality:
+\begin{displaymath}
+    \sum_{(i,j)\in E} (x_i-x_j)^2 \geq \frac{1}{l} \left(\sum_{s=1}^l x_{i_{s+1}}
+    - x_{i_s}\right)^2= \frac{1}{l} (x_k - x_{i^*})^2\geq \frac{1}{l} x_{i^*}^2
+\end{displaymath}
+where the last inequality used that $x_{i^*}$ and $x_k$ have opposite signs.
+Finally using $x_{i^*}^2 \geq \frac{1}{n}$ and $l\leq n$:
+\begin{displaymath}
+    \sum_{(i,j)\in E} (x_i-x_j)^2 \geq \frac{1}{n^2}
+\end{displaymath}
+Taking the $\min$ over $x$, this implies using, the variational expression for
+$\lambda_2$ (second largest eigenvalue) established at the beginning of the
+question: $\lambda_2\leq 1-\frac{1}{dn^2}$.
+
+\paragraph{5.} We consider the graph $G^2$. As seen in \textbf{3.}, $G^2$ is
+connected since $G$ is connected and nonbipartite. Hence, we can apply question
+\textbf{4.} to $G^2$: $\lambda_2 (M^2)\leq 1-\frac{1}{d^2n^2}$ (the degree of
+$G^2$ is $d^2$). But the eigenvalues of $M^2$ are the squares of the
+eigenvalues of $M$. So all the eigenvalues of $M$ other than 1 have absolute
+value at most:
+\begin{displaymath}
+    \sqrt{1-\frac{1}{d^2n^2}}\leq 1 - \frac{1}{2d^2n^2}
+\end{displaymath}
+where we used $\sqrt{1-x}\leq 1-\frac{x}{2}$ which concludes the question by
+definition of $\lambda(G)$.
+
+\paragraph{6.} The analysis we did in \textbf{4.} used that the length of
+a path from $i^*$ to $k$ had length $l\leq n$. If we know the diameter $D$, we
+have $l\leq D$. The same analysis gives $\lambda_2\leq 1- \frac{1}{dDn}$.
+
+Finally, \textbf{5.} implies that $\gamma(G) \geq \frac{1}{2d^2n^2}$.
+
+\section*{Problem 3.1}
+
+\section*{Problem 3.2}
 \end{document}
-- 
cgit v1.2.3-70-g09d2

