From 755565dbd51b9bda550709e281c389a7ce3fd609 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Thu, 26 Feb 2015 18:54:14 -0500 Subject: [PS2] 50% of problem 1 --- ps2/main.tex | 164 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 164 insertions(+) create mode 100644 ps2/main.tex (limited to 'ps2') 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} -- cgit v1.2.3-70-g09d2