From 53c67b30ae39def4699f6b2f64fc33a67d4f5f2e Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Fri, 27 Feb 2015 13:37:30 -0500 Subject: [ps2] fix a few typos --- ps2/main.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'ps2/main.tex') diff --git a/ps2/main.tex b/ps2/main.tex index e59a055..ecfba0b 100644 --- a/ps2/main.tex +++ b/ps2/main.tex @@ -111,7 +111,7 @@ Dividing by $x_{i^*}$ both sides (it is non-zero for the same reason as in 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$ 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 +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 @@ -186,7 +186,7 @@ index this path $i^* = i_1,\ldots, i_l = k$. Then: \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 +where we restricted the sum to 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}} @@ -197,7 +197,7 @@ 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 +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}$. -- cgit v1.2.3-70-g09d2