\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{multicol}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{cancel}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{1: Motivation: Eigenthings and Orthogonality}{Due Monday, January 13, in class}


Homework problems need to show work and contain proofs in order to receive full credit.  Simply stating an answer is only half of the problem in mathematics; you also need to include an argument that persuades your audience that your answer is correct!  As always, if you have any questions, feel free to contact either Yihan or I via email or office hours.  Have fun!

\begin{enumerate}
\item \begin{enumerate}
\item In class, we found a $2 \times 2$ matrix with no real-valued eigenvalues.  Find a $4 \times 4$ matrix with no real-valued eigenvalues.  Prove that your claim is correct.
\item In class, we found a $n \times n$ matrix with only one eigenvalue, such that the dimension of the subspace formed by all eigenvectors for that eigenvalue was one-dimensional.  Find a $4 \times 4$ matrix with exactly one eigenvalue $\lambda$, such that the dimension of the subspace formed by the collection of all eigenvectors for that eigenvalue is \textbf{two}-dimensional.  Prove that your claim is correct.
\end{enumerate}
\item Consider the Pell sequence $\{p_i\}_{i=1}^\infty$, defined recursively as follows:
\begin{itemize}
\item $p_0 = 0$.
\item $p_1 = 1$.
\item $p_n = 2p_{n-1} + p_{n-2}$.
\end{itemize}
The first ten Pell numbers are listed here:
\begin{align*}
0, 1, 2, 5, 12, 29, 70, 169, 408, 985, \ldots
\end{align*}
\begin{enumerate}
\item Find a matrix $P = \begin{bmatrix} a & b \\ c & d\end{bmatrix}$ such that
\begin{align*}
\begin{bmatrix} a & b \\ c & d\end{bmatrix} \cdot \begin{bmatrix} p_n \\ p_{n-1} \end{bmatrix} =  \begin{bmatrix} p_{n+1} \\ p_{n} \end{bmatrix} .
\end{align*}
\item Find the eigenvalues and corresponding eigenvectors of $P$.
\item Let $\vec{v}$ be an eigenvector of $P$ corresponding to some eigenvalue $\lambda$, and $\vec{w}$ be some other eigenvector of $P$ corresponding to an eigenvalue $\delta \neq \lambda$.  Prove that $\vec{v}$ and $\vec{w}$ are orthogonal.
\item Use all of this information along with the methods we discussed in class to find $p_{50}$.
\end{enumerate}
(In all of your work above, prove that your claims are correct.)
\item Consider the following ``miniature'' model for the internet, made of six webpages:
\begin{multicols}{2}
\begin{itemize}
\item Pets.com: links to boo, Webvan, and Kozmo.
\item boo.com: links to Webvan, Kozmo and eToys.
\item Webvan.com: links to Kozmo, eToys, and DigiScents.
\item Kozmo.com: links to eToys, DigiScents, and Pets.com.
\item eToys.com: links to DigiScents, Pets, and boo.
\item DigiScents.com: links to Pets, boo, and Webvan.
\end{itemize}
\end{multicols}
\begin{enumerate}
\item Draw a diagram with six bubbles, one for each webpage, and arrows between these bubbles representing the links above.
\item Turn this model of the internet into a $6 \times 6$ ``link-matrix'' $A$, as done in the notes.
\item Use this link matrix to find the ``importance vector'' (i.e. eigenvector corresponding to the eigenvalue 1) for this matrix $A$, showing your work and justifying your answer.  Interpret your results: what do they say about the relative importance of these six websites?
\end{enumerate}



\end{enumerate}



\end{document}