[PS2] 50% of problem 1

1 files changed, 164 insertions, 0 deletions

diff --git a/ps2/main.tex b/ps2/main.tex
new file mode 100644
index 0000000..b6ce969
--- /dev/null
+++ b/ps2/main.tex
@@ -0,0 +1,164 @@
+\documentclass[10pt]{article}
+\usepackage{fullpage}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,amsfonts,amsthm}
+\usepackage[english]{babel}
+\usepackage[capitalize, noabbrev]{cleveref}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+
+\newenvironment{enumerate*}%
+  {\vspace{-2ex} \begin{enumerate} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{enumerate}}
+ 
+\newenvironment{itemize*}%
+  {\vspace{-2ex} \begin{itemize} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{itemize}}
+ 
+\newenvironment{description*}%
+  {\vspace{-2ex} \begin{description} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{description}}
+
+\DeclareMathOperator{\E}{\mathbb{E}}
+\let\P\relax
+\DeclareMathOperator{\P}{\mathbb{P}}
+\newcommand{\ex}[1]{\E\left[#1\right]}
+\newcommand{\prob}[1]{\P\left[#1\right]}
+\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
+\newcommand{\R}{\mathbf{R}}
+\newcommand{\N}{\mathbf{N}}
+\newcommand{\C}{\mathcal{C}}
+\newcommand{\eps}{\varepsilon}
+\newcommand{\cl}[1]{\text{\textbf{#1}}}
+\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+\newcommand{\llbracket}{[\![}
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{lemma}{Lemma}
+\algrenewcommand\algorithmicensure{\textbf{Output:}}
+\algrenewcommand\algorithmicrequire{\textbf{Input:}}
+
+\author{Thibaut Horel}
+\title{CS 225 Problem Set 2 -- Solutions}
+
+\begin{document}
+\maketitle
+
+Collaborator: Debmalya Mandal
+
+\section*{Problem 2.9}
+
+\paragraph{1.}
+Let $\lambda$ be an eigenvalue of $M$ and $x$ be an associated eigenvector. Let
+$i^*\in\{1,\ldots, n\}$ such that $|x_{i^*}| = \|x\|_{\infty}$. Since $x$ is an
+eigenvector we have:
+\begin{displaymath}
+    \sum_{j=1}^n m_{i^*,j} x_j = \lambda x_{i^*}
+\end{displaymath}
+$x$ is non-zero, hence $x_{i^*}$ is non-zero. Dividing both sides by $x_{i^*}$,
+we obtain:
+\begin{displaymath}
+    |\lambda| = 
+    \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 the first inequality used the triangle inequality and the second
+inequality used the definition of $x_{i^*}$.
+
+\paragraph{2.} Assume $G$ is disconnected. Hence it has at least two connected
+components. We can write $V = C_1\cup C_2$ with $C_1\cap C_2 = \emptyset$ and
+$ C_1\times C_2\cap E = \emptyset$. Then it is clear that $x^1
+= \mathbf{1}_{C_1}$ (the indicator vector of $C_1$) and $x^2
+= \mathbf{1}_{C_2}$ are eigenvectors of $M$ for the eigenvalue 1. For example
+for $x^1$:
+\begin{displaymath}
+    \sum_{j=1}^n m_{i,j} x^1_j =
+    \begin{cases}
+        1&\text{if $i\in C_1$}\\
+        0&\text{otherwise}
+    \end{cases}
+\end{displaymath}
+where the first case follows from the fact that if $i\in C_1$, all the non-zero
+terms $m_{i,j}$ will be preserved by the multiplication by $x^1_j$ since
+$m_{i,j}\neq 0\Leftrightarrow j\in C_1$ and the fact that $\sum_{j=1}^n m_{i,j}
+= 1$. Similarly if $i\in C_2$ $m_{i,j} = 0$ whenever $j\in C_1$.
+
+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:
+\begin{displaymath}
+    \sum_{j=1}^n a_{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
+\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.
+
+\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
+$M$.
+
+The antepenultimate equivalence uses that the eigenvalues of $M^2$ are the
+squares of the eigenvalues of $M$, and the penultimate equivalence uses that
+$x$ cannot be an eigenvector for the eigenvalue $1$ because of \textbf{2}. The
+second equivalence also uses \textbf{2.}.
+
+\paragraph{4.} First observe that $\max_{\|x\|_2 = 1} \inprod{Mx, x}$
+= $\lambda_{max}(M)$ for any symmetric matrix $M$. Indeed, using the spectral
+theorem and writing $M = P^T DP$ with $D$ = $\text{diag}(\lambda_1,\dots,\lambda_n)$
+and observing that $\|x\|_2 =1\Leftrightarrow \|Px\|_2 = 1$ we have:
+\begin{displaymath}
+    \max_{\|x\|_2 = 1} \inprod{Mx, x} = \max_{\|y\|_2=1} y^TDy = \max_{\|y\|_2
+    = 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
+$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
+orthogonal to $\mathbf{1}$ is exactly the largest eigenvalue of $M$ when
+restricted to the vector space orthogonal to $\mathbf{1}$ (restricting $M$ to
+this subspace is allowed since this subspace is invariant by $M$). But since
+the eigenspaces of $M$ are orthogonal, the largest eigenvalue of $M$ restricted
+to the orthogonal of $\mathbf{1}$ is the second largest eigenvalue of $M$.
+
+Hence:
+\begin{displaymath}
+    \lambda_2(M) = \max_{x} \inprod{Mx, x}
+\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.
+\end{document}