% 233 Computational Techniques
% Tutorial-3
% London, 2001 January

\documentclass[12pt]{article}

\def\tutno{3}   % Serial number of the tutorial

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{theorem}
\usepackage{verbatim}
\usepackage{ifthen}
\usepackage{fancybox}
\usepackage{fancyhdr}
\usepackage{pstricks,pst-node}

\theoremstyle{break}

\textheight=220mm \textwidth=160mm \oddsidemargin=0pt
\parindent=0pt

\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}


%%%%% One of the following must be defined for the macros
\def\indextype{traditional}
%\def\indextype{new}
%%%%% Input macros
\input adormac.tex
%%%%% End of input of macros

\title{\textbf{233 Computational Techniques}}
\author{Problem Sheet for Tutorial \tutno}
\date{}

\pagestyle{fancy}
 \lhead{\small \sc Computational Techniques}
 \chead{}
 \rhead{\small \sc Tutorial \tutno}
 \lfoot{}
 \cfoot{\thepage}
 \rfoot{}
 \headheight=15pt
 \renewcommand{\headrulewidth}{0.4pt}
 \renewcommand{\footrulewidth}{0.4pt}


\begin{document}

\maketitle

\begin{problem}\label{prob.1}

In 2 dimensions, the $\ell_p$ norm of a vector $\ix=(x_1,x_2)$ is given by
\begin{eqnarray*}
        \|\ix\|_p=\left(|x_1|^p+|x_2|^p\right)^{1/p}
                \quad\mbox{for}\quad 1\leq p<\infty \;, \qquad
        \|\ix\|_{\infty}=\max\{|x_1|,|x_2|\} \;.
\end{eqnarray*}
 Sketch the surfaces of constant $\ell_p$ norm of 1,
\begin{eqnarray*}
        C_p:=\{\ix\in\Rad{2}: \|\ix\|_p=1\}
\end{eqnarray*}
for $p=1,2,\infty$ in a rectangular coordinate system. \\


\end{problem}


\begin{problem}\label{prob.2}

\begin{itemize}
\item[(i)] Using the definition of the angle between two vectors, prove the {\em cosine
theorem} of trigonometry:
\begin{equation}\label{cos-thm}
\|\iu - \iv\|^2_2 = \|\iu\|^2_2 + \|\iv\|^2_2 - 2\|\iu\|_2\|\iv\|_2 \cos\phi
\end{equation}
for all $\iu, \iv\not=\inull$, where $\phi$ is the angle between $\iu$ and
$\iv$. Which theorem is the special case $\phi=\pi/2$?

\item[(ii)] From (\ref{cos-thm}) and the fact that the sum of angles in a triangle is
equal to $\pi$, deduce
\begin{eqnarray*}
\mbox{{\em (a)}}\quad \cos\left(\frac{\pi}{3}\right)=\frac{1}{2} \;, \qquad
\mbox{{\em (b)}}\quad \cos\left(\frac{\pi}{4}\right)=\frac{1}{2}\sqrt{2} \;.
\end{eqnarray*}
\end{itemize}


\end{problem}



\begin{problem}\label{prob.3}

Let $\iA$ and $\iB$ be two matrices
$$
\iA =
\begin{myrmatrix}
-3 & 0 & 4 \\ 1 & 2 & 3
\end{myrmatrix},
\quad
\iB =
\begin{myrmatrix}
-9 & 2 & 3 \\ -4 & 8 & 6 \\ 1 & 5 & 7
\end{myrmatrix}.
$$

Determine $\|\iA\|_1, \ \|\iA\|_\infty$ and $\|\iB\|_1, \ \|\iB\|_\infty$.

\end{problem}

\begin{problem}\label{prob.1}
Which of the following sets of vectors are linearly independent: \\
\emph{(a)} $[1,5]$, $[2,3]$; \\
\emph{(b)} $[2,1,-3]$, $[-1,1,-6]$, $[1,1,-4]$; \\
\emph{(c)} $[1,0,3]$, $[-1,1,2]$, $[2,0,-5]$ ?

\end{problem}


\begin{problem}\label{prob.2}
For
\begin{eqnarray*}
        \iA = \left[\begin{array}{rrr}
        2 & 0 & 1 \\ 3 & -1 & 2
        \end{array}\right] \;,
\end{eqnarray*}
find \\
{\em (a)} the nullspace of $\iA$, \\
{\em (b)} the nullspace of $\iA^T$, \\
{\em (c)} the range of $\iA$, \\
{\em (d)} the range of $\iA^T$. \\
{\em (e)} Check that null${\iA^T}$ is orthogonal to range${\iA}$, and that
null${\iA}$ is orthogonal to range${\iA^T}$. \\
{\em (f)} For $\ix = [1,1,1]^T$, find the two vectors $\ix_R \in
\text{range}{\iA^T}$ and $\ix_N \in \text{null}{\iA}$ which satisfy $\ix =
\ix_R + \ix_N$. Check that $\ix_R$ and $\ix_N$ are orthogonal!


\end{problem}

\begin{problem}\label{prob.3}
Prove: \\
\emph{(a)} If $\iA \in \Rad{n\times n}$ is invertible, then its right and
left inverses are equal; that is, if $\iA\iB = \iI$ and $\iC\iA = \iI$ then
$\iB = \iC$.\\
{\em (b)} If $\iA$ has an inverse, then the columns of
$\iA$ are linearly independent. \\
{\em (c)} If $\iA$ and $\iB$ are both nonsingular, then $\iA\iB$ is
nonsingular, and
$(\iA\iB)^{-1}=\iB^{-1}\iA^{-1}$. \\
{\em (d)} Suppose $\alpha\in\mathbb{R}$ and $\iu,\iv\in\Rad{n}$ such that
$\alpha \iu^T\iv \not= 1$. Then $\iE = \iI_n - \alpha \iu\iv^T$ is
nonsingular, and its inverse is $\iI_n - \beta \iu\iv^T$, where
\begin{eqnarray*}
        \beta = \frac{\alpha}{\alpha \iu^T\iv - 1} \;.
\end{eqnarray*}

\end{problem}

\end{document}

\newpage

\cl{\textbf{\Large Solution}} \chead{Solution}

\vspace{9mm} \textbf{Problem \ref{prob.1}}

\emph{(a)}
%\begin{figure}[h]
%\unitlength 1cm
%\begin{picture}(15,6)
%\end{picture}
%\caption{} \label{triangle}
%\end{figure}

\begin{figure}[h]
\begin{center}
 \psset{xunit=20mm, yunit=20mm}
\begin{pspicture}(-1,-1)(1.45,1.45)\showgrid
 \psline[arrowsize=6pt]{->}(-1,0)(1.25,0)\rput(1.45,0){$x_1$}
 \psline[arrowsize=6pt]{->}(0,-1)(0,1.25)\rput(0,1.45){$x_2$}
 \pscircle(0,0){2}
 \pspolygon(-1,0)(0,1)(1,0)(0,-1)
 \pspolygon(-1,-1)(-1,1)(1,1)(1,-1)
 \rput(1.44,1.4){$C_{\infty}$}
  \psline[linestyle=dashed,arrowsize=6pt]{->}(1.25,1.3)(0.8,1)
 \rput(1.44,0.707){$C_{2}$}
  \psline[linestyle=dashed,arrowsize=6pt]{->}(1.25,.707)(0.707,0.707)
 \rput(1.44,-0.5){$C_{1}$}
  \psline[linestyle=dashed,arrowsize=6pt]{->}(1.25,-0.5)(0.5,-0.5)
%\pscaption{} \label{triangle}
\end{pspicture}
\caption{} \label{triangle}
\end{center}
\end{figure}


\emph{Explanation:} $\|\ix\|_2=\sqrt{x_1^2+x_2^2}$ is the Euclidean distance
of $\ix$ from the origin; so $C_2$ is the set of all points which have
Euclidean distance 1 from the origin, which is the unit circle.

Next, note that the $\ell_p$-norm of a vector $\ix=[x_1,x_2]$ depends only on
the \emph{absolute} value of $x_1$ and $x_2$, not on their signs. This means
that once we know the part of the surface $C_p$ which lies, say, in the
\emph{positive quadrant} $x_1,x_2\geq 0$, then we can obtain the entire
surface by simply taking this part together with its four reflections at the
axes $x_1=0$ and $x_2=0$.

For $C_1$, the part lying in the positive quadrant is the set of all
$\ix=[x_1,x_2]$ such that $x_1,x_2\geq 0$ and $x_1+x_2=1$, or $x_2=1-x_1$. The
graph of this function is a straight line through the points $[0,1]$ and
$[1,0]$; so the part of $C_1$ in the positive quadrant is the line segment
between $[0,1]$ and $[1,0]$, including the endpoints. Hence $C_1$ is the
``diamond''-shaped curve shown in the diagram.

For $C_{\infty}$, the part lying in the positive quadrant is the set of all
$\ix=[x_1,x_2]$ such that $x_1,x_2\geq 0$ and $\max\{x_1,x_2\}=1$. So if
$x_1\leq x_2$, then $x_2=1$, and $0\leq x_1\leq 1$; in this case, $\ix$ lies
on the line segment between $[0,1]$ and $[1,1]$, including both endpoints.
However if $x_1> x_2$, then $x_1=1$ and $0\leq x_2<1$, and $\ix$ lies on the
line segment between $[1,0]$ and $[1,1]$ (including the former, but not the
latter). This gives the positive quadrant of the square shown in the diagram.

\emph{(b)} First suppose $\|\ix\|_2=1$, i.e.\ that $\ix$ lies on $C_2$, which
is the unit circle. If $\ix$ is one of the corners of $C_1$ (the ``diamond''),
it also lies on $C_\infty$ (the square) and hence all three norms of $\ix$ are
equal. Otherwise $\ix$ lies on the outside of $C_1$ and on the inside of
$C_\infty$; this means that the $\ell_1$ norm of $\ix$ is greater than 1, and
that the $\ell_{\infty}$ norm of $\ix$ is smaller than one. So the inequality
is true in this case!

Note that the inequality is also true if $\|\ix\|_2=0$; for in this case,
$\ix$ is the zero vector, and so the other two norms are also zero.

Now the remaining case: $\|\ix\|_2\not\in\{0,1\}$. But we know already that
the inequality is true for vectors with $\ell_2$ norm equal to $1$. So we
divide $\ix$ by its $\ell_2$ norm and get $\hat{\ix}=\lambda \ix$ with
$\lambda= 1 / \|\ix\|_2\not=0$. It follows from the general properties of a
vector norm that $\hat{\ix}$ has $\ell_2$ norm
$\|\hat{\ix}\|_2=|\lambda|\left\|\ix\right\|_2=1$. So we have the inequality
$\|\hat{\ix}\|_1\geq\|\hat{\ix}\|_2\geq\|\hat{\ix}\|_{\infty}$, or
\begin{eqnarray*}
        |\lambda|\|\ix\|_1\geq\|\lambda|\|\ix\|_2
                        \geq\|\lambda|\|\ix\|_{\infty} \;,
\end{eqnarray*}
and, dividing by $|\lambda|$ we obtain the general result.


\vspace{9mm} \textbf{Problem \ref{prob.2}}

The left hand side of (\ref{cos-thm}) is
\begin{eqnarray*}
(\iu - \iv)^T (\iu - \iv) = \iu^T \iu - \iu^T \iv - \iv^T \iu + \iv^T \iv =
\iu^T \iu + \iv^T \iv - 2\iu^T \iv \;.
\end{eqnarray*}
Here $\iu^T \iu =\|\iu\|_2^2$ and $\iv^T \iv = \|\iv\|_2^2$. The remaining
term is
\begin{eqnarray*}
-2\iu^T \iv = -2\|\iu\|_2\|\iv\|_2{ \frac{\iu^T \iv}{\|\iu\|_2\|\iv\|_2}} =
-2\|\iu\|_2\|\iv\|_2\cos\phi \;,
\end{eqnarray*}
by the definition of the angle between two vectors which was given in the
lecture.                           \hfill$\blacksquare$

The cosine theorem allows to compute the angles of a triangle provided the
lengths of the sides are known. If $\iu$ and $\iv$ are two sides of the
triangle, then their lengths are $\|\iu\|_2$ and $\|\iv\|_2$, and the length
of the third side is $\|\iu - \iv\|_2$ (see Fig. \ref{triangle}). If
$\phi=\pi/2$, then the angle between $\iu$ and $\iv$ is a right angle, and the
cosine theorem then says that the squared lengths of the sides adjoining the
right angle add up to the squared length of the side opposite. This is
\emph{Pythagoras' theorem.}

\vspace{9mm} \textbf{Problem \ref{prob.4}}

Reminder:
\begin{center}
\begin{tabular}{|ll|}
\hline
& \\
$\norm{\iA}_1 = \displaystyle\max_j \norm{\ia_j}_1 $ & the maximum
absolute column sum, \\
& \\
$\norm{\iA}_{\infty} = \displaystyle\max_i \norm{\ia^i}_1 $ & the
maximum absolute row sum. \\
& \\
\hline
\end{tabular}
\end{center}
Therefore, for $\iA$: $\norm{\iA}_1 = \max\{3+1,\ 2, \ 4+3\} = \max\{4,2,7\}
= 7$ \\ and
$\norm{\iA}_\infty = \max\{3+4,\ 1+2+3\} = \max\{7,6\} = 7$. \\
Accidentally, the two norms are equal. \\[3mm]
For $\iB$: $\norm{\iB}_1 = \max\{14,15,16\} = 16$ and $\norm{\iB}_\infty =
\max\{14,18,13\} = 18$.

\end{document}