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

\usepackage{graphicx}
\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.4}
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.5}
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.6}
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}



\newpage

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

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

\begin{center}\includegraphics[width=0.4\textwidth]{l-norms.pdf}\end{center}

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

(i) 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 notes.

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$). 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.}

(ii)  Take $\iu$ and $\iv$ in (\ref{cos-thm}) as defining two sides of
a triangle enclosing the desired angle. For
\emph{(a)}, take an equilateral triangle, for \emph{(b)} one with one right
angle and the other two angles $\pi/4$.
\newpage

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

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$.

\textbf{Problem \ref{prob.4}}

The sets \emph{(a)} and \emph{(c)} are independent, \emph{(b)} is not. There
are two ways of doing this: by working from the definition of linear
dependence, and by using determinants.

From the definition (\emph{(a)} only): A set $\{\ia_1,\ldots,\ia_n\}$
of vectors is linearly dependent if \\
(i) there are real numbers $x_1,\ldots,x_n$, not all zero, such
that $x_1\ia_1+\ldots+x_n \ia_n = \inull$, \\
or equivalently if \\
(ii) there is a real vector $\ix = [x_1,\ldots,x_n]^T \not= \inull$ such that
$\iA \ix = \inull$, where $\iA = [\ia_1, \ldots, \ia_n]$ is
the matrix which has $\ia_1,\ldots,\ia_n$ as its columns.\\
If the only numbers $x_i$ satisfying (i) are $x_1 = \ldots = x_n = 0$ (the
only vector $\ix$ satisfying (ii) is the zero vector), then the set $\{\ia_1,
\ldots,\ia_n\}$ is linearly independent.

So let $x_1,x_2$ be such that
\begin{equation}                                \label{dep}
         x_1\left[\begin{array}{c}1\\5\end{array}\right]
        +x_2\left[\begin{array}{c}2\\3\end{array}\right]
        =\left[\begin{array}{c}0\\0\end{array}\right] \;.
\end{equation}
From the first component one finds $x_1 = -2x_2$, and the second component
gives $0 = 5x_1 + 3x_2 = -7x_2$ (substituting for $x_1$ according to the first
equation). From the second equation, it follows that $x_2 = 0$, and from the
first that $x_1 = 0$ as well. So the only pair $x_1,x_2$ satisfying (1) is
$x_1 = x_2 = 0$. According to (i), the vectors $[1,5]^T$ and $[2,3]^T$ are
linearly independent.

{\em Using determinants:} Recall the following facts about
determinants: \\
$\bullet$ A square matrix $\iA$ is singular if and only if
its determinant is zero. \\
$\bullet$ The determinant of a $1\times 1$ matrix (i.e. a real
number) is the number itself. \\
$\bullet$ The determinant of a $2\times 2$ matrix is
\begin{eqnarray*}
        \det\left[\begin{array}{cc}
        a&b \\ c&d
        \end{array}\right]
        = ad-bc \;.
\end{eqnarray*}
$\bullet$ The determinant of a $3\times 3$ matrix can be computed in various
ways; one of them is
\begin{eqnarray*}
\det\left[\begin{array}{ccc}a&b&c\\d&e&f\\g&h&k
                                        \end{array}\right]
=a\cdot\det\left[\begin{array}{cc}e&f\\h&k\end{array}\right]
-b\cdot\det\left[\begin{array}{cc}d&f\\g&k\end{array}\right]
+c\cdot\det\left[\begin{array}{cc}d&e\\g&h\end{array}\right]\;.
\end{eqnarray*}
(Note the pattern: $\bullet$ The signs are alternating. $\bullet$ Each term
in the sum is the product of an element $*$ of the first row and the
determinant of the $2\times 2$ matrix which remains if the row and column of
$*$ are deleted.)

The first fact leads to the following criterion for linear
dependence: \\
\emph{(iii) $n$ vectors $\ia_1, \ldots, \ia_n$ in $n$-dimensional space are
linearly dependent if and only if
the matrix $[\ia_1,\ldots,\ia_n]$ has zero determinant.}\\
(\emph{Proof:} $\det [\ia_1,\ldots,\ia_n] = 0 \iff \mbox{$[\ia_1, \ldots,
\ia_n]$ singular}\iff \mbox{\emph{(ii)} above}$.)

\emph{Application:} \\
\emph{(a)} The determinant of
$\left[\begin{array}{cc}1&2\\5&3\end{array}\right]$ is $1\times 3-2\times
5=-7\not=0$, so $[1,5]$ and $[2,3]$ are
linearly independent. (So are $[1,2]$ and $[5,3]$!) \\
\emph{(b)} The same in 3 dimensions: {\small
\begin{eqnarray*}
\det\left[\begin{array}{rrr}2&-1&1\\1&1&1\\-3&-6&-4
                                        \end{array}\right]
&=&2\cdot\det\left[\begin{array}{rr}1&1\\-6&-4\end{array}\right]
-(-1)\cdot\det\left[\begin{array}{rr}1&1\\-3&-4
                                        \end{array}\right]
+1\cdot\det\left[\begin{array}{rr}1&1\\-3&-6
                                        \end{array}\right]\\
&=&2\times 2-(-1)\times(-1)+1\times(-3)=0 \;,
\end{eqnarray*}%
} so $[2,1,-3]$, $[-1,1,-6]$ and $[1,1,-4]$ are linearly
dependent. \\
\emph{(c)} Here the determinant of the resulting matrix is $-11$, so the
vectors $[1,0,3]$, $[-1,1,2]$ and $[2,0,-5]$ are linearly independent.



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

\emph{(a)} The null space of $\iA$ is the set of all vectors $\ix$ such that
$\iA\ix = \inull$. If $\ix$ is such a vector, then
\begin{eqnarray*}
        \iA\ix
        = \left[\begin{array}{rrr} 2 & 0 & 1 \\ 3 & -1 & 2
        \end{array}\right]
        \left[\begin{array}{c}
        x_1 \\ x_2 \\ x_3 \end{array}\right]
        = \left[\begin{array}{c}
        2x_1 + x_3 \\ 3x_1 - x_2 + 2x_3
        \end{array}\right]
        = \left[\begin{array}{c}
         0 \\ 0
         \end{array}\right] \;,
\end{eqnarray*}
and so $x_3 = -2x_1$ and $x_2 = 3x_1 + 2x_3 = -x_1$. In vector notation,
$\ix^T = [x_1,-x_1,-2x_1] = x_1[1,-1,-2]$, that is, the null space of $\iA$
is the set of all scalar multiples of the vector $[1,-1,-2]^T$. A concise
notation for this statement is
\begin{eqnarray*}
        \text{null}{\iA} = \mathbb{R} \left[\begin{array}{r}
        1 \\ -1 \\ -2
        \end{array}\right] \;.
\end{eqnarray*}
\emph{(b)} If $\iy \in \text{null}{\iA^T}$, then
\begin{eqnarray*}
        \inull = \iA^T \iy =
        \left[\begin{array}{rr} 2&3 \\ 0&-1 \\ 1&2 \end{array}\right]
        \left[\begin{array}{c} y_1 \\ y_2 \end{array}\right]
        = \left[\begin{array}{c} 2y_1+3y_2 \\ -y_2 \\ y_1+2y_2
        \end{array}\right]
        = \left[\begin{array}{c}
        0 \\ 0 \\ 0
        \end{array}\right] \;,
\end{eqnarray*}
and so $y_2=y_1=0$. It follows that null${\iA^T} = \{\inull\}$. Another way to
see this is to notice that the two columns in $\iA^T$ are linearly
independent; therefore $\iA^T\iy = \inull$ forces $\iy = \inull$. A third way
is to do \emph{(c)} first and to use the first of the dimension formulae
\begin{eqnarray*}
        \dim(\text{range}{\iA}) + \dim(\text{null}{\iA^T})&=&
        \mbox{$\#$ of rows of $\iA$}\;, \\
        \dim(\text{range}{\iA^T}) + \dim(\text{null}{\iA})&=&
        \mbox{$\#$ of columns of $\iA$}.
\end{eqnarray*}
For the range space of $\iA$ is two-dimensional, and so the null space of
$\iA^T$ is zero-dimensional. The only zero-dimensional vector space is
$\{\inull \}$. \\
\emph{(c)} The range of $\iA$ consists of all vectors in $\Rad{2}$ which can
be written in the form $\iA\ix$ for some $\ix\in\Rad{3}$. As
\begin{eqnarray*}
        \iA\ix = x_1\left[\begin{array}{r} 2 \\ 3 \end{array}\right]
        + x_2\left[\begin{array}{r} 0 \\ -1 \end{array}\right]
        + x_3\left[\begin{array}{r} 1 \\ 2 \end{array}\right] \;,
\end{eqnarray*}
the range space of $\iA$ is spanned by the three vectors $[2,3]^T$,
$[0,-1]^T$, and $[1,2]^T$. Now it is easy to see that any two of these
vectors are linearly independent; so their span is the entire $\Rad{2}$. In
other words, range${\iA} = \Rad{2}$, and $\dim(\text{range}{\iA}) = 2$. \\
\emph{(d)} The range of $\iA^T$ is
\begin{eqnarray*}
        \text{range}{\iA^T} = \{\iA^T \iy: \iy \in \Rad{2}\}
        = \left\{
        y_1 \left[\begin{array}{c} 2 \\ 0 \\ 1 \end{array}\right]
        + y_2 \left[\begin{array}{r} 3 \\ -1 \\ 2 \end{array}\right]\;:
        \quad y_1,y_2 \in \mathbb{R} \right\} \;.
\end{eqnarray*}
Its dimension is indeed two, since the two generating vectors
are linearly independent. \\
\emph{(e)} null${\iA^T} = \{\inull \}$, and the zero vector is orthogonal to
any vector. For null${\iA}$ and range${\iA^T}$, it suffices to check that the
vectors which generate them are orthogonal. Indeed,
\begin{eqnarray*}
[1,-1,-2] \left[\begin{array}{c} 2 \\ 0 \\ 1 \end{array}\right] = 0
\qquad\mbox{and}\qquad [1,-1,-2] \left[\begin{array}{r} 3
\\ -1 \\ 2 \end{array}\right] = 0 \;.
\end{eqnarray*}
\emph{(f)} One way to do this is to compute the coefficients $\lambda_i$ in
\begin{eqnarray*}
        \left[\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right]
= \underbrace{\lambda_1\left[\begin{array}{r}1\\-1\\-2\end{array}\right]
}_{\ix_N} + \underbrace{ \lambda_2 \left[
\begin{array}{c}2\\0\\1\end{array}\right]
+ \lambda_3 \left[\begin{array}{r} 3 \\ -1 \\ 2 \end{array}\right] }_{\ix_R}
\;;
\end{eqnarray*}
$\ix_N$ and $\ix_R$ are then given by the bracketed terms.

%\begin{comment}
%Alternatively, we can use orthogonal projection onto
%$\nulll{\b{A}}$,
%%(see sheet 4),
%since we know that the nullspace
%of $\b{A}$ and the range space of $\b{A}^T$ are orthogonal to
%each other. We want to split
%\begin{eqnarray*}
%        \left[\begin{array}{c}1\\1\\1\end{array}\right]
%=\underbrace{
%\lambda_1\left[\begin{array}{r}1\\-1\\-2\end{array}\right]
%}_{\b{x}_N}+\b{x}_R \;.
%\end{eqnarray*}
%We take the scalar product with $[1,-1,-2]$, knowing that this
%must be orthogonal to $\b{x}_R$. The resulting equation is
%$-2=6\lambda_1$, or $\lambda_1=-1/3$. This gives
%\end{comment}

$\ix_N = -(1/3) [1,-1,-2]=[-1/3,1/3,2/3]$ and $\ix_R = [1,1,1] -
[-1/3,1/3,2/3] = [4/3,2/3,1/3]$. These two vectors are indeed orthogonal:
$\ix_N^T \ix_R = -(1/3)\times 4/3 + 1/3\times 2/3 + 2/3\times 1/3 = 0$.


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

\emph{(a)}
$\iB = \iI\iB = (\iC\iA) \iB = \iC(\iA\iB) = \iC\iI = \iC$. \\
\emph{(b)} If $\iA = [\ia_1, \ldots, \ia_n]$ and $\ix = [x_1, \ldots, x_n]^T$,
then $\iA\ix = x_1 \ia_1 + \ldots + x_n \ia_n$. Now suppose that the right
hand side is zero. Then $\iA\ix = \inull$, and by pre-multiplying with the
inverse $\iA^{-1}$, it follows that $\ix = \inull$, and so the columns
$\ia_1,\ldots,\ia_n$ are linearly independent. \\
\emph{(c)} To prove that $\iA\iB$ is nonsingular, we have to show $\iA\iB\iz
= \inull \Rightarrow\iz = \inull$. So suppose that $\iA\iB\iz = \inull$. Then,
as $\iA$ is nonsingular, it follows that $\iB\iz = \inull$, and since $\iB$
is also nonsingular, that $\iz = \inull$. For the inverse of $\iA\iB$, it
suffices to check that
\begin{eqnarray*}
        (\iA\iB)(\iB^{-1}\iA^{-1})
        = \iA(\iB\iB^{-1})\iA^{-1}
        = \iA\iI\iA^{-1}
        =\iA\iA^{-1} = \iI \;,
\end{eqnarray*}
so $\iB^{-1}\iA^{-1}$ is indeed the inverse of $\iA\iB$.\\
\emph{(d)} To prove that $\iE$ is nonsingular, we have to show that $\iE\iz =
\inull \Rightarrow \iz = \inull$. So suppose that $\iE\iz = \inull$. As $\iE =
\iI - \alpha \iu\iv^T$, this is equivalent to
\begin{equation}\label{z}
        \iz = \alpha (\iv^T\iz)\iu \;.
\end{equation}
We compute $\iv^T\iz$ by taking the scalar product of the last equation with
$\iv^T$; the result is $\iv^T\iz = \alpha (\iv^T\iz)(\iv^T\iu)$, or
$\iv^T\iz(1 - \alpha \iu^T\iv) = 0$. But it was assumed that $\alpha \iu^T\iv
\not= 1$; so it follows that $\iv^T\iz = 0$. By (2), this also implies $\iz =
\inull$.

Again, it remains to check that $\iI - \beta \iu\iv^T$ is really the inverse
of $\iE$:
\begin{eqnarray*}
        (\iI - \alpha \iu\iv^T)(\iI - \beta \iu\iv^T)
        &=& \iI - \beta \iu\iv^T - \alpha \iu\iv^T
        + \alpha \beta(\iv^T\iu) \iu\iv^T \\
        &=& \iI + \{\alpha \beta (\iu^T\iv) - \alpha - \beta\}
                \iu\iv^T \;;
\end{eqnarray*}
here the term in the curly bracket is
\begin{eqnarray*}
        \beta(\alpha\iu^T\iv - 1) - \alpha = \alpha - \alpha = 0 \;.
\end{eqnarray*}


\end{document}