\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Rnn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cnn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\dist}{dist}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 6}\\
Instructor: Anil Damle\\
Due: December 4, 2023\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including plots and requested output from your code
should be typeset and submitted via the Gradescope as a pdf file. Additionally, please
submit any code written for the assignment. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file to the separate Gradescope assignment.\\
\hrule
\noindent
\subsection*{Question 1:}
Say we are given a symmetric matrix $A$ with distinct eigenvalues $\lambda_i$ (ordered $\lambda_1 > \ldots > \lambda_n$) and associated eigenvectors $v_i.$ Consider a $k$ dimensional subspace represented by the span of the matrix $Q\in\R^{n\times k}$ with orthonormal columns and let $\theta_i$ and $y_i$ be eigenvalue/vector pairs of $T = Q^TAQ.$ If $\theta_i = \lambda_i$ for $i = 1,\ldots,k$ what can we say about the relationship between $Q$ and $v_1,\ldots,v_k$? Does your statement still hold if $\theta_i = \lambda_i$ for $k$ distinct but arbitrary indices?
\subsection*{Question 2 (ungraded):}
The following question will not be graded and you do not have to submit a solution. Nevertheless, it is a result we saw in class and it would be good to think a little bit about how you would prove a result of this type.\\
Assume we are using the Lanczos process to compute some eigenvalues of a real symmetric
matrix $A$ and build the Krylov space starting with vector $z_0.$ Let $A$ have eigenvalues
$\lambda_1,\ldots,\lambda_n$ satisfying $\lambda_1 \geq \cdots \geq \lambda_n$ and associated
eigenvectors $v_1,\ldots,v_n.$
\begin{enumerate}
\item After $k$ steps of the Lanczos process let $T_k$ be the tridiagonal matrix
generated by the process, prove that $\theta_1 = \lambda_1(T_k)$ (the largest
magnitude eigenvalue of $T_k$) satisfies
\[
\lambda_1 \geq \theta_1 \geq \lambda_1 - (\lambda_1-\lambda_n)
\left(\frac{\tan \phi_1}{c_{k-1}(1+2\rho_1)}\right)^2
\]
where $\cos(\phi_1) = \lvert z_0^Tv_1\rvert,$
$\rho_1=\frac{\lambda_1-\lambda_2}{\lambda_2-\lambda_n},$ and
$c_{k-1}(x)$ is the Chebyshev polynomial of degree $k-1.$
\item Compare and contrast this convergence result with that for the power method
(assuming the eigenvalues are such that the power method would converge to $\lambda_1$).
\end{enumerate}
\end{document}