\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input ../adgeomcs/mac.tex
\input ../adgeomcs/mathmac.tex

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Fall, 2003 \hspace*{0.4cm} CIS 610}}\\
\vspace{1cm}
{Advanced geometric methods\\
\vspace{0.5cm}
Homework 3}\\[10pt]
November 11, 2003; Due November 25, beginning of class\\
\end{center}

You may work in groups of 2 or 3. Please, write up your
solutions as clearly and concisely as possible. Be rigorous!
You will have to present your solutions of the problems during
a special problem session.

\vspace{0.5cm}
``A problems'' are for practice only, and should not
be turned in.


\vspace {0.5cm}\noindent
{\bf Problem A1.} 
(1)
Given a unit vector $(-\sin\theta, \cos\theta)$,
prove that the Householder matrix determined by the vector
$(-\sin\theta, \cos\theta)$ is
%
%\medskip
\[\matta{\cos 2\theta}{\sin 2\theta}
       {\sin 2\theta}{-\cos 2\theta}.
\]
%
%\medskip\noindent
Give a geometric interpretation (i.e., why the choice
$(-\sin\theta, \cos\theta)$?).

\medskip
(2)
Given any matrix
%
%\medskip
\[A = \matta{a}{b}{c}{d},\]
%
%\medskip\noindent
prove that there is a Householder matrix
$H$ such that $AH$ is lower triangular, i.e.,
%
%\medskip
\[AH = \matta{a'}{0}{c'}{d'}\]
%
%\medskip\noindent
for some $a', c', d'\in \reals$.

\vspace{0.5cm}\noindent
{\bf Problem A2}. 
Given a Euclidean space $E$ of dimension $n$,
if $h$ is a reflection about some hyperplane
orthogonal to a nonnull vector $\novect{u}$ and
$f$ is any isometry, prove that
$f\circ h \circ f^{-1}$ is the reflection
about the hyperplane orthogonal to $f(\novect{u})$.


\vspace{0.5cm}\noindent
{\bf Problem A3}. 
Let $E$ be a Euclidean space of dimension $n = 2$.
Prove that given any two unit vectors
$\novect{u_1}, \novect{u_2} \in E$ (unit means that
$\smnorme{\novect{u_1}} = \smnorme{\novect{u_2}} = 1$),
there is a unique rotation $r$ such that
\[r(\novect{u_1}) = \novect{u_2}.\]

\medskip
Prove that there is a rotation
mapping the pair $\pairt{\novect{u_1}}{\novect{u_2}}$ to
the pair $\pairt{\novect{u_3}}{\novect{u_4}}$ iff
there is a rotation
mapping the pair $\pairt{\novect{u_1}}{\novect{u_3}}$ to
the pair $\pairt{\novect{u_2}}{\novect{u_4}}$
(all vectors being unit vectors).


\vspace {0.5cm}
``B problems'' must be turned in.

\vspace {0.5cm}\noindent
{\bf Problem B1 (30 pts).} 
This problem is a warm-up for the next problem.
%\medskip
Consider the set of matrices of the form
%\medskip
\[\matta{0}{-a}{a}{0},\]
%
%\medskip\noindent
where $a\in \reals$.

\medskip
(a) Show that these matrices are invertible when  $a\not=0$
(give the inverse explicitly).
Given any two such matrices $A, B$, show that
$AB = BA$.
Describe geometrically  the action of such a matrix
on points in the affine plane $\affreal^2$, with its usual
Euclidean inner product.
Verify that this set of matrices is a vector space
isomorphic to $(\reals, +)$.
This vector space is denoted by $\mfrac{so}(2)$. 

\medskip
(b)
Given an $n\times n$ matrix $A$, we define the {\it exponential\/}
$e^A$ as 
\[e^A = I_n + \sum_{k\geq 1} \frac{A^k}{k!},\]
where $I_n$ denotes the $n\times n$ identity matrix.
It can be shown rigorously that this power series is indeed
convergent for every $A$ (over $\reals$ or $\complex$),
so that $e^A$ makes sense (and you do not have to prove it!).

\medskip
Given any matrix
%
%\medskip
\[A = \matta{0}{-\theta}{\theta}{0},\]
%
%\medskip\noindent
prove that
%
%\medskip
\[e^A = \cos\theta \matta{1}{0}{0}{1} + \sin\theta\matta{0}{-1}{1}{0}
= \matta{\cos\theta}{-\sin\theta}{\sin\theta}{\cos\theta}.\]
%
%\medskip\noindent
\hint
Check that
%
%\medskip
\[\matta{0}{-\theta}{\theta}{0} = \theta\matta{0}{-1}{1}{0}\quad\hbox{and}\quad 
\matta{0}{-\theta}{\theta}{0}^2 = -\theta^2\matta{1}{0}{0}{1},\]
%
%\medskip\noindent
and use the power series for $\cos\theta$ and $\sin\theta$.
%\medskip
Conclude that the exponential map provides
a surjective map $\mapdef{\exp}{{\mfrac{so}}(2)}{\mSO{2}}$
from  $\mfrac{so}(2)$ onto the group $\mSO{2}$
of plane  rotations. Is this map injective?
How do you need to restrict $\theta$ to get an injective map?

\medskip
\remark 
By the way,  $\mfrac{so}(2)$ is the {\it Lie algebra\/}
of the (Lie) group $\mSO{2}$.
\endremark 

\medskip
(c)
Consider the set $\mU{1}$ of complex numbers of the form
$\cos\theta + i\sin\theta$. Check that this is a group under
multiplication. Assuming that we use the standard affine frame
for the affine plane $\affreal^2$, every point $(x, y)$
corresponds to the complex number $z = x + iy$,
and this correspondence is a bijection. Then, every
$\alpha = \cos\theta + i\sin\theta\in \mU{1}$ induces
the map $\mapdef{R_\alpha}{\affreal^2}{\affreal^2}$
defined such that
\[R_\alpha(z) = \alpha z.\]
Prove that $R_{\alpha}$  is the rotation of matrix
%
%\medskip
\[\matta{\cos\theta}{-\sin\theta}{\sin\theta}{\cos\theta}.\]
%
%\medskip\noindent
Prove that the map $\mapdef{R}{\mU{1}}{\mSO{2}}$ defined such that
$R(\alpha) = R_{\alpha}$ is an isomorphism.
Deduce that topologically, $\mSO{2}$ is a circle.
Using the exponential map from $\reals$ to $\mU{1}$ defined
such that $\theta \mapsto e^{i\theta} = \cos\theta + i\sin\theta$,
prove that there is a surjective homomorphism from
$(R, +)$ to $\mSO{2}$. What is the connection with
the exponential map from  $\mfrac{so}(2)$ to $\mSO{2}$?


\vspace {0.5cm}\noindent
{\bf Problem B2 (60 pts).} 

\medskip
(a) 
Recall that the coordinates of the
cross product $\novect{u}\times\novect{v}$ of two vectors
$\novect{u} = (u_1, u_2, u_3)$  and $\novect{v} = (v_1, v_2, v_3)$ 
in $\reals^3$ are 
\[(u_2v_3 - u_3v_2,\, u_3v_1 - u_1v_3,\, u_1v_2 - u_2v_1).\]

\medskip
Letting $U$ be the matrix
%
%\medskip
\[U = \mattc{0}{-u_3}{u_2}{u_3}{0}{-u_1}{-u_2}{u_1}{0},\]
%
%\medskip\noindent
check that the coordinates of 
the cross product $\novect{u}\times\novect{v}$
are given by
%
%\medskip
\[\mattc{0}{-u_3}{u_2}{u_3}{0}{-u_1}{-u_2}{u_1}{0}\trivec{v_1}{v_2}{v_3}
= \trivec{u_2v_3 - u_3v_2}{u_3v_1 - u_1v_3}{u_1v_2 - u_2v_1}.\]

\medskip
(b)
Show that the set of matrices of the form
%
%\medskip
\[U = \mattc{0}{-u_3}{u_2}{u_3}{0}{-u_1}{-u_2}{u_1}{0}\]
%
%\medskip\noindent
is a vector space  isomorphic to $(\reals^3 +)$.
This vector space is denoted by  $\mfrac{so}(3)$.
Show that such matrices are never invertible.
Find the kernel of the linear map associated with a matrix $U$.
Describe geometrically the action of the linear map defined
by a matrix $U$. Show that when restricted to the plane
orthogonal to $\novect{u} = (u_1, u_2, u_3)$
through the origin, it is a rotation by $\pi/2$.

\medskip
(c)
Consider the map
$\mapdef{\psi}{(\reals^3,\times)}{{\mfrac{so}}(3)}$
defined by the formula
%
\[\psi(u_1, u_2, u_3) = \mattc{0}{-u_3}{u_2}{u_3}{0}{-u_1}{-u_2}{u_1}{0}.\]
%
%\medskip\noindent
For any two matrices $A, B\in \mfrac{so}(3)$, defining $[A,\, B]$
as 
\[[A,\, B] = AB - BA,\]
verify that
\[\psi(\novect{u}\times\novect{v})
= [\psi(\novect{u}),\, \psi(\novect{v})].\]

%\medskip
Show that $[-,\, -]$ is not associative.
Show that $[A,\, A] = 0$, and that
the so-called {\it Jacobi identity\/} holds:
\[[A,\, [B,\, C]] + [C,\, [A,\, B]] + [B,\, [C,\, A]] = 0.\]
Show that $[A\, B]$ is bilinear (linear in both $A$ and $B$).

%\medskip
\remark  
$[A,\, B]$ is called a {\it Lie bracket\/},
and under this operation, the vector space
$\mfrac{so}(3)$ is called a {\it Lie algebra\/}.
In fact, it is the Lie algebra of the (Lie) group $\mSO{3}$.
\endremark 

\medskip
(d)
For any matrix
\[A = \mattc{0}{-c}{b}{c}{0}{-a}{-b}{a}{0},\]
%
%\medskip\noindent
letting $\theta = \sqrt{a^2 + b^2 + c^2}$ and
%
\[B = \mattc{a^2}{ab}{ac}{ab}{b^2}{bc}{ac}{bc}{c^2},\]
%
%\medskip\noindent
prove that
\[\eqaligneno{
A^2 &= -\theta^2 I + B,\cr
AB &= BA = 0.\cr
}\]
From the above, deduce that
\[A^3 = -\theta^2 A,\]
and for any $k\geq 0$,
\[\eqaligneno{
A^{4k + 1} &= \theta^{4k} A,\cr
A^{4k + 2} &= \theta^{4k} A^2,\cr
A^{4k + 3} &= -\theta^{4k + 2} A,\cr
A^{4k + 4} &= -\theta^{4k + 2} A^2.\cr
}\]
Then prove that
the exponential map
$\mapdef{\exp}{{\mfrac{so}}(3)}{\mSO{3}}$ is given by 
\[\exp{A} = e^A = \cos\theta\, I_3 + \frac{\sin\theta}{\theta} A + 
\frac{(1 - \cos\theta)}{\theta^2} B,\]
or, equivalently, by
\[e^A = I_3 + \frac{\sin\theta}{\theta} A + 
\frac{(1 - \cos\theta)}{\theta^2} A^2,\]
if $\theta \not= k2\pi$ ($k\in\integs$), with $\exp(0_3) = I_3$.

%\medskip
\remark  
This formula is 
known as Rodrigues's formula (1840).
\endremark 

\medskip
(e)
Prove that $\exp{A}$ is a rotation of axis $(a, b, c)$
and of angle $\theta = \sqrt{a^2 + b^2 + c^2}$.

%\medskip
\hint
Check that $e^A$ is an orthogonal matrix
of determinant $+1$, etc.,
or look up any textbook on kinematics or classical dynamics!

\medskip
(f)
Prove that the exponential map
$\mapdef{\exp}{{\mfrac{so}}(3)}{\mSO{3}}$ is surjective.
Prove that if $R$ is a rotation matrix different from $I_3$,
letting $\novect{\omega} = (a, b, c)$ be a unit vector defining
the axis of rotation, if $\trace(R) = -1$, then
%
%\medskip
\[(\exp(R))^{-1} = \left\{\pm\pi\mattc{0}{-c}{b}{c}{0}{-a}{-b}{a}{0}\right\},\]
%
%\medskip\noindent
and if $\trace(R) \not= -1$, then
\[(\exp(R))^{-1} = \left\{\frac{\theta}{2\sin\theta}(R - R^T)\ \bigg|\
1 + 2\cos\theta = \trace(R)\right\}.\]
%\medskip
(Recall that $\trace(R) = r_{1\, 1} + r_{2\, 2} + r_{3\, 3}$,
the {\it trace\/} of the matrix $R$).
Note that both $\theta$ and $2\pi-\theta$ yield the same matrix
$\exp(R)$.


\vspace {0.5cm}\noindent
{\bf Problem B3 (30 pts).} 
Given $p$ vectors $(\novect{u_1},\ldots,\novect{u_p})$
in a Euclidean space $E$ of dimension $n\geq p$,
the {\it Gram determinant (or Gramian)\/} of the vectors
$(\novect{u_1},\ldots,\novect{u_p})$ is the determinant
%\medskip
\[\Gram(\novect{u_1},\ldots,\novect{u_p}) =
\gramdet{u}{p}.\]

\medskip
(1)
Prove that
\[\Gram(\novect{u_1},\ldots,\novect{u_n}) =
\lambda_{\vectorsmal{E}}(\novect{u_1},\ldots,\novect{u_n})^2.\]

%\medskip
\hint
By a previous problem, if 
$(\novect{e_1},\ldots,\novect{e_n})$ is an orthonormal basis
of $E$ and $A$ is the matrix of the vectors
$(\novect{u_1},\ldots,\novect{u_n})$ over this basis,
\[\det(A)^2 = \det(\transpos{A}A) = \det(\dotprod{A_i}{A_j}),\]
where $A_i$ denotes the $i$th column of the matrix $A$,
and $(\dotprod{A_i}{A_j})$ denotes the $n\times n$ matrix with entries
$\dotprod{A_i}{A_j}$.

\medskip
(2)
Prove that
\[\smnorme{\novect{u_1}\times\cdots\times\novect{u_{n-1}}}^2
=  \Gram(\novect{u_1},\ldots,\novect{u_{n-1}}).\]

%\medskip
\hint
Letting 
$\novect{w} = \novect{u_1}\times\cdots\times\novect{u_{n-1}}$,
observe that
\[\lambda_{\vectorsmal{E}}(\novect{u_1},\ldots,\novect{u_{n-1}}, \novect{w})
= \pairt{\novect{w}}{\novect{w}} = \smnorme{\novect{w}}^2,\]
and show that
\[
\eqaligneno{
\smnorme{\novect{w}}^4 &=
\lambda_{\vectorsmal{E}}(\novect{u_1},\ldots,\novect{u_{n-1}}, \novect{w})^2 =
\Gram(\novect{u_1},\ldots,\novect{u_{n-1}}, \novect{w}) \cr
&=
\Gram(\novect{u_1},\ldots,\novect{u_{n-1}})\smnorme{\novect{w}}^2.\cr
}
\]

\vspace {0.5cm}\noindent
{\bf Problem B4 (50 pts).} 
\label{pb7.11}
Given a Euclidean space $E$, let $U$ be a nonempty affine subspace
of $E$, and let $a$ be any point in $E$.
We define the {\it distance $d(a, U)$\/} of $a$ to $U$ as
\[d(a, U) = \inf\{\smnorme{\libvecbo{a}{b}}\ |\ b\in U\}.\]

\medskip
(a) 
Prove that the affine subspace $\orthog{U}_a$ defined such that
\[\orthog{U}_a = a + \orthog{\vector{U}}\]
intersects $U$ in a single point $b$ such that
$d(a, U) = \smnorme{\libvecbo{a}{b}}$.

%\medskip
\hint
Recall the discussion after Lemma 2.11.2.

\medskip
(b) Let $(a_0, \ldots, a_p)$ be a frame for $U$ (not necessarily 
orthonormal). Prove that
\[d(a, U)^2 = 
\frac{\Gram(\libvecbo{a_0}{a}, \libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_p})}
{\Gram(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_p})}.\]

%\medskip
\hint
$\Gram$ is unchanged when a linear combination
of other vectors is added to one of the vectors, and thus
\[{\Gram(\libvecbo{a_0}{a}, \libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_p})}
=  {\Gram(\libvecbo{b}{a}, \libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_p})},\]
where $b$ is the unique point defined in question (a).

\medskip
(c)
If $D$ and $D'$ are two lines in $E$ that are not coplanar, 
$a, b\in D$ are 
distinct points on $D$, and $a', b' \in D'$
are distinct points on $D'$,
prove that if $d(D, D')$ is the shortest distance between
$D$ and $D'$ (why does it exist?), then
\[d(D, D')^2 = \frac{\Gram(\libvecbo{a}{a'}, \libvecbo{a}{b}, \libvecbo{a'}{b'})} 
{\Gram(\libvecbo{a}{b}, \libvecbo{a'}{b'})}.\]


\vspace {0.5cm}\noindent
{\bf Problem B5 (30 pts).} 
In $\eucreal^3$, consider the closed convex set (cone), $A$, defined
by the inequalities
\[
x\geq 0,\quad y\geq 0,\quad z\geq 0, \quad z^2 \leq xy,
\]
and let $D$ be the line given by
$x = 0, z = 1$. Prove that $D \cap A = \emptyset$, both $A$ and $D$ are convex
and closed, yet every plane containing $D$ meets $A$.
Therefore, $A$ and $D$ give another counter-example to the Hahn-Banach
theorem where $A$ is closed
(one cannot relax the hypothesis that $A$ is open).


\vspace {0.5cm}\noindent
{\bf Problem B6 (30 pts).}
In $\eucreal^n$, consider the polar duality $A \mapsto A^*$,
with respect to the origin, $O$.

\medskip
(i)
For any nonempty subsets, $A, B\subseteq \eucreal^n$,
prove the following properties:  
\begin{enumerate}
\item[(a)]
$A^{*} = A^{***}$.
\item[(b)]
For any $\lambda \not= 0$, we have
$(\lambda A)^* = (1/\lambda) A^*$.
\item[(c)]
$(A\cup B)^* = A^* \cap B^*$.
\item[(d)]
$A^{**} = \overline{\chullb{A\cup \{O\}}}$, the topological closure
of the convex hull of $A$ and the origin.
\item[(e)]
If $A$ and $B$ are closed, convex and both contain $O$, then
$(A\cap B)^* = \overline{\chullb{A^* \cup B^*}}$,  
the topological closure of the convex hull of $A^* \cup B^*$.
\end{enumerate}

(ii)
If $A, B\subseteq \eucreal^n$, for any $\lambda$, 
the set
\[(1 - \lambda) A + \lambda B = \{(1 - \lambda)a + \lambda b \mid
a\in A,\> b\in B\}
\]
is the {\it Minkowski sum\/} of $A$ and $B$.
Assume that  $0 \leq \lambda \leq 1$.
Check that $(1 - \lambda) A + \lambda B$ is convex if $A$ and $B$ are convex.
Prove that $(1 - \lambda) A + \lambda B$ is a polytope if $A$ and $B$
are polytopes.

\medskip
(iii) ({\bf Extra Credit\/})
The Minkowski sum can be viewed as a way of interpolating
between two polytopes and gives a way of {\it morphing\/}
one polytope to another. 
The vertices of \\
$(1 - \lambda) A + \lambda B$ are convex
combinations of the vertices of $A$ and $B$.
However, not all of these convex combinations are vertices.
Investigate (in $\eucreal^3$) practical algorithms for displaying the
result of morphing polytopes using the Minkowski sum
(You may want to begin with the case of polygons in
$\eucreal^2$.)


\vspace{0.5cm}\noindent
{\bf TOTAL: 230 points.}


\end{document}