\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{4: QR and Schur Decompositions}{Due Monday, February 10, by 1:30pm}


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!  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 Find a QR decomposition of the following matrix:
\begin{align*}
A = 
\begin{bmatrix}
2 & 2 & -4 & -1 \\
3 & 9 & 9 & 7 \\
6 & 3 & 5 & 5\\
0 & 2 & 5 & 11\\
\end{bmatrix}
\end{align*}
\item Use $A$'s QR-decomposition to find a vector $\vec{v}$ such that 
\begin{align*}
A\vec{v} = (-1,28,19,18).
\end{align*}
\end{enumerate}
\item \begin{enumerate}
\item Find the Schur decomposition of the following matrix:
\begin{align*}
A = \begin{bmatrix} 37 & -9 \\ 16 & 13 \end{bmatrix}
\end{align*}
\item Use $A$'s Schur decomposition to find $A^{50}$.  \\
(When finding your answer, do not expand large exponents: i.e. write $9^{50}$, instead of 515377520732011331036461129765621272702107522001.)
\end{enumerate}
\item Consider the following Markov process, used to model a drunkard's walk:
\begin{itemize}
\item States: there are four states.  The first corresponds to the drunkard's home $H_1$; the second and third correspond to a pair of city blocks $C_2, C_3$ near the drunkard's walk, and the fourth corresponds to a black hole $B_4$ that absorbs everything that touches it.
\item Rules: 
\begin{itemize}
\item If the drunkard is home, it falls asleep and stays home: i.e.\ it stays at the first home state $H_1$ with probability 1, and goes to the other three states with probability 0.  
\item If the drunkard is at block $C_2$, it goes home with probability $1/2$, goes to block $C_3$ with probability $1/2$, and never goes to the other states (i.e. goes to them with probability 0.)
\item If the drunkard is at block $C_3$, it goes to block $C_2$ with probability $1/2$, stumbles into the black hole $B_4$ with probability $1/2$, and never goes to the other states.
\item If the drunkard has fallen into the black hole, then it is\footnote{Stephen Hawking may disagree: see \href{http://arxiv.org/abs/1401.5761}{http://arxiv.org/abs/1401.5761}.  Also if you're a physicist and know things about this, find me because I want to understand this paper?} trapped in the black hole forever: i.e.\ it stays at the black hole state $B_4$ with probability 1 and goes to the other 3 states with probability 0.
\end{itemize}
\end{itemize}
\begin{enumerate}
\item Create a matrix $A$ that corresponds to this process.
\item Suppose that our drunk starts at $C_3$.  Over a long enough period of time, what is the likelihood that the drunk makes it home?
\end{enumerate}
\item Suppose that $A$ is a $n \times n$ real-valued symmetric matrix, $Q$ is an orthonormal basis of $\mathbb{R}^n$, and $R$ is an upper-triangular matrix such that $A$'s Schur decomposition is given by the product $QRQ^{-1}$.  Prove that $R$ is a diagonal matrix.
\item Prove or disprove: there is a matrix $A$ such that $A$ is diagonal in some basis, but in $A$'s Schur decomposition $QRQ^{-1}$ the matrix $R$ is not diagonal.
\item[Bonus!]  If you solve this problem, email your answers to me directly; answers sent to the TA only will not be graded.\\
 Generalize the drunkard's walk to a Markov chain on $\mathbb{Z}^2$, the integer lattice, as follows:
\begin{itemize}
\item States: points $(i,j)$, with $i, j \in \mathbb{Z}$.
\item Rules: from any point $(i,j) \neq (0,0)$, your drunkard will move to one of the four points $(i\pm1, j)$, $(i, j\pm1)$, each with probability 1/4.  At $(0,0)$, however, the drunkard is home, and does not leave (i.e.\ it stays at $(0,0)$ with probability 1.)
\end{itemize}
Suppose that your drunk starts at some point $(x,0)$ on the $x$-axis.   Over a long enough run, what is the probability that it will make it home (i.e.\ get to $(0,0)$?)
\end{enumerate}





\end{document}