diff options
| -rw-r--r-- | ps2/main.tex | 115 |
1 files changed, 88 insertions, 27 deletions
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} |