\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{color,hyperref}
\usepackage{enumerate}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5490 -- Homework 5: Due April 5 by 11:59pm}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions and Python code by uploading them to the Google form: \url{https://forms.gle/5PELk1XogtFrDYFD6}
\item Submit all your Python code in a single .py file using the function templates given in each problem. I will import your functions from this file and test your code.
\item If you use LaTeX to write up your solutions, upload them as a pdf file. Students who use LaTeX to write up their solutions will receive bonus points on the homework assignment (equivalent to 1/3 of a letter grade bump).
\item If you choose to handwrite your solutions and scan them, please either use a real scanner, or use a smartphone app that allows scanning with you smartphone camera. It is not acceptable to submit photos of your solutions, as these can be hard to read.
\end{itemize}


\subsection*{Problems:}



\begin{enumerate}
\item Consider diffusion with a source term $\ff\in \R^m$:
\begin{equation}\label{eq:diffusion_source}
\x_{k+1} = \x_k - \Lr^T \x_k + \ff.
\end{equation}
The interpretation is that we are adding or removing (based on the sign of $\ff$) mass at each iteration. Throughout this problem you should assume the graph is connected.
\begin{enumerate}[(i)]
\item Show that 
\[\one^T\x_{k+1} = \one^T \x_k + \one^T \ff.\]
For the rest of the exercise assume that $\one^T \ff = 0$, so that \eqref{eq:diffusion_source} conserves mass.
\item Show that the the mean zero condition $\one^T\ff=0$ implies that $\ff\in \rng \Lr^T$, and so there exists $\x\in \R^m$ such that $\Lr^T \x = \ff$.
\item Set $\u_k = \x_k - \x$ and show that $\u_k$ satisfies the diffusion equation 
\[\u_{k+1} = \u_k - \Lr^T \u_k.\]
\item Suppose that $\x_0=0$. Use Theorem 8.27 to solve for $\u_k$, and then use that $\x_k = \x + \u_k$ to show that
\[\x_k =\x  -D\sum_{i=1}^m (1-\lambda_i)^k(\x\cdot \p_i) \p_i,\]
where $\p_i$ and $\lambda_i$ are the eigenvectors and eigenvalues of the random walk graph Laplacian $\Lr$. 
\item Assume the graph is aperiodic (in addtion the the assumption that the graph is connected). Show that if $\x\cdot \one = 0$ then $\x_k \to \x$ as $k\to \infty$. What happens if $\x\cdot \one \neq 0$?
\end{enumerate}
\item In this exercise you'll prove convergence of the PageRank iteration for a nonsymmetric graph. In particular, in this exercise we do \emph{not} assume that $W=W^T$. Let us define $P = W^TD^{-1}$. 
\begin{enumerate}[(i)]
\item Show that $P$ is nonexpansive in the 1 norm, that is, show that
\[\|P\x\|_1 \leq \|\x\|_1.\]
\item Show that when $0\leq \alpha <1$ there is a unique solution $\x$ of the PageRank equation
\begin{equation}\label{eq:PR_P}
\x = (1-\alpha)\:\v + \alpha P\x.
\end{equation}
[Hint: Show that \eqref{eq:PR_P} is equivalent to $A\x=\v$ where
\[A = (1-\alpha)^{-1}(I - \alpha P),\]
and then use part (i) to show that $\ker A = \{0\}$.]
\item Let $\x_k$ solve the PageRank iteration
\begin{equation}\label{eq:PR_iter}
\x_{k+1} = (1-\alpha)\:\v + \alpha P\x_k,
\end{equation}
and let $\x$ be the PageRank vector, which satisfies \eqref{eq:PR_P}. Show that 
\begin{equation}\label{eq:PRconv}
\|\x_k -\x\|_1 \leq \alpha^k \|\x_0-\x\|_1.
\end{equation}
[Hint: Subtract \eqref{eq:PR_P} from \eqref{eq:PR_iter} and use part (i) to get that 
\[\|\x_{k+1}-\x\|_1 \leq \alpha \|\x_k-\x\|_1.\]
Then complete the proof by induction.]
\item  Assume that the entries of $\v$ are nonnegative (i.e, $v_i\geq 0$). Show that the PageRank vector $\x$ also has nonnegative entries. [Hint: Choose $\x_0=0$ in the PageRank iteration \eqref{eq:PR_iter}, show that $\x_k$ has nonnegative entries, and use from part (iii) that $\x_k\to \x$ as $k\to \infty$.]
\end{enumerate}
\end{enumerate}

\end{document}

