\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}


\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Tr}{Tr}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 3220: Homework 1}\\
Instructor: Anil Damle\\
Due: September 14, 2020\\

\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. Remember, your solution should be typeset. Your solution, including plots and requested output from your code should be submitted via the CMS as a pdf file. Additionally, please submit any code written for the assignment via the CMS as well.\\
\hrule
\vspace{5mm}
This homework is intended to be a short warm-up exercise for the liner algebra we will use extensively in this class. In addition, some of the problems may touch on material from pre-requisite courses and will hopefully get you thinking about some of those concepts again. 

\subsection*{Question 1:}
Given a matrix $A \in \R^{m\times n}$ show that the number of linearly independent rows is equal to the number of linearly independent columns (this should go beyond citing some of the results from class that are analogous to this fact).

% \subsection*{Question 2:}
% Given two matrices $A$ and $B$ both of which are $n\times n,$ show that the column space of $AB$ is contained in the column space of $A,$ \emph{i.e.}\ show that every vector in the column space of $AB$ is also in the column space of $A.$ When is the column space of $AB$ strictly smaller than the column space of $A,$ \emph{i.e.}\ when can there be vectors in the columns space of $A$ that are not in the columns space of $AB$?

\subsection*{Question 2:}
For $A \in \R^{m\times n}$ show that the null space of $A^TA$ is the same as the null space of $A.$ 

\subsection*{Question 3:}
Let $Q \in \R^{m\times n}$ with $m>n$ be a matrix with orthonormal columns, show that $QQ^T\neq I.$ (Recall that by definition $Q^TQ=I.$ Because we will often deal with matrices that more rows than columns, it is important to keep this distinction in mind as it differs from what is true for square orthogonal matrices. In fact $QQ^T$ is a very special matrix in this case, one we will discuss extensivly later in this class.)

\subsection*{Question 4 (a more involved and interesting question):}
Consider the following three vector norms we talked about in class:
\begin{itemize}
\item $\displaystyle \|x\|_2 = \left(\sum_{i=1}^nx_i^2\right)^{1/2}$
\item $\displaystyle \|x\|_1 = \sum_{i=1}^n\lvert x_i \rvert$
\item $\displaystyle \|x\|_{\infty} = \max_{i\in\{1,2,\ldots,n\}}\lvert x_i\rvert$
\end{itemize}
Now, let $n=2$ and draw the ``unit ball'' for each of these norms. In other words, draw the set of vectors in $\R^2$ whose norm is equal to 1. Provide your plots and address the following questions:
\begin{enumerate}
\item From this plot can you derive any inequalities on $\|x\|_2, \|x\|_1,$ and $\|x\|_{\infty}$? (In other words for any $x$ can you provide an ordering on the actual values of the norms?)
\item What are the set of points for which $\|x\|_2 = \|x\|_1 = \|x\|_{\infty}$?
\item Say you are given a vector $a$ in $\R^2$ that is non-zero in both entries and a scalar $\beta,$ describe the set of solutions to the equation $a^Tx = \beta$ both algebraically and geometrically (hint: recall from linear algebra that such a system has an infinite number of solutions so you will need to describe it in terms of a free parameter).
\item (\textbf{This problem is more challenging, but actually gets at a beautiful geometric idea related to quite recent developments in computer science, statistics, and applied math\textemdash specifically in so-called ``sparse recovery'' problems.}) Building on the previous problem, say someone now asked you the following question: of all the vectors that satisfy $a^Tx = \beta$ find one of the ``sparsest'' ones. In other words, return the solution with the fewest possible non-zero entries. Furthermore, say you are restricted to solving the problem by phrasing it the following way:
\[
\min \|x\|_* \quad \text{subject to} \quad a^Tx = \beta
\]
for $* = \{1,2,\infty\}.$ This means that you simply answer the question by returning the smallest point in the set of solutions to $a^Tx = \beta$ and you get to determine how ``smallest point'' is defined (for the moment do not worry about how one would actually compute this). 

Which norm should you use? (you may assume $\lvert a_1 \rvert \neq \lvert a_2 \rvert.$) Hint: think about this geometrically, consider what the set of solutions to $a^Tx = \beta$ looks like and pair that with your understanding of what ``level sets'' of the norms look like. (They are just scalings of the unit balls you plotted earlier.)
\end{enumerate}


\end{document}