\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}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 3}\\
Instructor: Anil Damle\\
Due: October 4, 2018\\

\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 supporting plots and requested output from your code
must be typeset and submitted via the CMS as a single pdf file. Additionally, please
submit any code written for the assignment via the CMS as well. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file.\\
\hrule
\vspace{1cm}
\noindent

\subsection*{Question 1:}
Given a square matrix $A\in\Cnn$ and QR factorization $A=QR$ is such a factorization unique? (\emph{i.e.,}\ are there some other unitary and upper triangular factors $Q_2\neq Q$ and $R_2\neq R$ such that $A=Q_2R_2$). Justify your response and comment on the implications of it from your perspective, \emph{e.g.} does your answer make such factorizations less useful?

\subsection*{Question 2:}
Let $V\in\Cmn$ with $m\geq n$ have orthonormal columns, prove the following:
\begin{itemize}
\item For any $x\in\C^m,$ $VV^*x$ is the unique closest point in the range of $V$ to $x.$
\item Prove that the orthgonal projector (also often refered to as the spectral projector) onto the range of $V$ is unique. 
\end{itemize}

\subsection*{Question 3:}
Given any $A\in\Cmn$ with $m\geq n,$ $b\in\C^m$ and $\text{rank}(A) < n$ prove that the solution to the least squares problem
\[
\min_x \|Ax-b\|_2
\]
is not unique.


\subsection*{Question 4:}
For square non-singular $A$ implement the computation of a QR factorization via Householder triangularization. This now gives an additional means for solving linear systems $Ax=b.$ For the following you may use your existing code for computing LU decompositions with partial pivoting. 
\begin{itemize}
\item Compare and contrast the runtimes of your QR factorization and your LU factorization with partial pivoting. As part of this, show your implementation of Householder QR is $\cO(n^3).$ 
\item Build a set of problems that are increasingly ill-conditioned (one way to approach this is to explicitly define the desired singular values via a diagonal matrix and then use random orthogonal matrices to generate a matrix, that it not itself diagonal, with the singular values you want) and explore the relationship between the condition number of the problem and the accuracy in the solution of $Ax=b$ using your QR factorization routine.
\end{itemize}

\subsection*{Question 5 (ungraded but fun, and maybe a good exam warm up...):}
Say we would like to compute a QR factorization of $A^k$ for some real, square $A$ and potentially large integer $k.$ 
\begin{itemize}
	\item Even if feasible to simply construct $A^k$ would it be good idea numerically to compute its QR factorization directly? Justify your response. Hint: assuming $A$ is diagonalizable, what can we say about the eigenvalues of $A^k$ and what are the implications of this.
	\item Develop a scheme to compute a QR factorization of $A^k$ via a sequence of $k$ QR factorizations of matrices whose condition number is never larger than that of $A$ itself. As long as you adhere to this constraint, for the purposes of this problem you may assume that computing matrix matrix products with the resulting $Q$ and/or $R$ is fine numerically. Hint: start with a QR factorization of $A$ itself.
\end{itemize}	
\end{document}