\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 Spring, 2011 \hspace*{0.4cm} CIS 610}}\\
\vspace{1cm}
{\Large\bf Advanced Geometric Methods in Computer Science\\
Jean Gallier \\
\vspace{0.5cm}
Homework 1}\\[10pt]
February 22, 2011; Due March 17, 2011\\
\end{center}

``A problems'' are for practice only, and should not
be turned in.

\medskip\noindent
{\bf Problem A1.} 
Given a finite dimensional Euclidean space, $E$, 
if $U$ and $V$ are two orthogonal subspaces that span $E$, 
i.e., $E = U \oplus V$, we have the linear projections
$\mapdef{p_U}{E}{U}$ and $\mapdef{p_V}{E}{V}$. Recall:
since every $w\in E$ can be written uniquely as
$w = u + v$, with $u\in U$ and $v\in V$, we have
$p_U(w) = u$, $p_V(w) = v$ and 
$p_U(w) + p_V(w) = w$, for all $w\in E$.
We define the {\it orthogonal
reflection with respect to $U$ and parallel to $V$\/} as the linear
map, $s$, given by
\[
s(w) = 2p_U(w) - w =  w - 2p_V(w),
\]
for all $w\in E$.
Observe that $s\circ s = \id$, that $s$ is the identity on $U$ and $s = -\id$
on $V$.
When $U = H$ is a hyperplane,  $s$ is called a 
{\it hyperplane reflection\/}
(about $H$).

\medskip
(a)
If $w$ is any nonzero vector orthogonal to the hyperplane $H$, prove that
$s$ is given by
\[
s(x) = x - 2\frac{\lag x, w\rag}{\norme{w}^2} w,
\]
for all $x\in E$.
(Here, $\norme{w}^2 = \lag w, w\rag$.)

\medskip
(b)
In matrix form, if the vector $w$ is represented by the column vector $W$,
show that the matrix of the hyperplane reflection about the hyperplane
$K = \{w\}^{\perp}$ is
\[
I - 2\frac{W\transpos{W}}{\transpos{W}W}.
\]
Such matrices are called {\it Householder matrices\/}.

\vspace {0.5cm}\noindent
{\bf Problem A2.} 
Given an $m\times n$ matrix, $A$, prove that its Frobenius norm, 
\[
\norme{A}_F = \sqrt{\sum_{i j} |a_{i\, j}|^2}
\]
satisfies
\[
\norme{A}_F = \sqrt{\mathrm{tr}(A^*A)} = \sqrt{\mathrm{tr}(AA^*)}
\]
where $\mathrm{tr}(B)$ is the trace of the square matrix $B$
(the sum of its diagonal elements).



\vspace {0.25cm}\noindent
{\bf Problem A3.} 
(a)
Find two symmetric matrices, $A$ and $B$, such that
$AB$ is not symmetric.

\medskip
(b)
Find two  matrices, $A$ and $B$, such that
\[
e^Ae^B \not= e^{A + B}.
\]
Try
\[
A = \frac{\pi}{2}\mattc{0}{0}{0}
                        {0}{0}{-1}
                        {0}{1}{0}
\quad\hbox{and}\quad
B = \frac{\pi}{2}\mattc{0}{0}{1}
                        {0}{0}{0}
                        {-1}{0}{0}.
\]


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

\vspace {0.25cm}\noindent
{\bf Problem B1 (40 pts).}
(a) Given a rotation matrix
%
%\medskip
\[R = \matta{\cos\theta}{-\sin\theta}
             {\sin\theta}{\cos\theta},\]
%
%\medskip\noindent
where $0 < \theta < \pi$, 
prove that there is a skew symmetric matrix
$B$ such that
\[R = (I - B)(I + B)^{-1}.\]

\medskip
(b) If $B$ is a skew symmetric $n\times n$ matrix, prove that
$\lambda I_n - B$ and $\lambda I_n + B$ 
are invertible for all $\lambda\not= 0$, and that
they commute.

\medskip
(c)
Prove that
\[R = (\lambda I_n - B)(\lambda I_n + B)^{-1}\]
is a rotation matrix that does not admit $-1$ as an
eigenvalue. (Recall, a rotation is an orthogonal matrix
$R$ with positive determinant, i.e., $\det(R) = 1$.)

\medskip
(d) Given any rotation matrix $R$ that does not admit $-1$
as an eigenvalue, prove  that there is a skew symmetric
matrix $B$ such that
\[R = (I_n - B)(I_n + B)^{-1}= (I_n + B)^{-1}(I_n - B).\]
This is known as the {\it Cayley representation\/} of rotations
(Cayley, 1846).
%\index{Cayley's representation of rotations}%

\medskip
(e) Given any rotation matrix $R$, prove 
that there is a skew symmetric
matrix $B$ such that
\[R = \left((I_n - B)(I_n + B)^{-1}\right)^2.\]


\vspace {0.25cm}\noindent
{\bf Problem B2 (40).}
(a)
Consider the map, $\mapdef{f}{\mathbf{GL}^+(n)}{\mathbf{S}(n)}$,
given by
\[
f(A) = \transpos{A}{A} - I.
\]
Check that
\[
df(A)(H) = \transpos{A}H + \transpos{H}A,
\]
for any matrix, $H$.

\medskip
(b)
Consider the map, $\mapdef{f}{\mathbf{GL}(n)}{\reals}$, given by
\[
f(A) = \det(A).
\]
Prove that $df(I)(B) = \mathrm{tr}(B)$,
the trace of $B$, for any matrix $B$ (here, $I$ is the identity matrix).
Then, prove that
\[
df(A)(B) = \det(A)\mathrm{tr}(A^{-1}B),
\]
where $A\in \mathbf{GL}(n)$. 

\medskip
(c)
Use the map $A \mapsto \det(A) - 1$ to prove that
$\mathbf{SL}(n)$ is a manifold of dimension $n^2 - 1$.

\medskip
(d)
Let $J$ be the $(n+1)\times (n+1)$ diagonal matrix
\[
J = \matta{I_n}{0}{0}{-1}.
\]
We denote by $\mathbf{SO}(n, 1)$ the group of real $(n+1)\times (n+1)$ matrices 
\[
\mathbf{SO}(n, 1) = \{A\in \mathbf{GL}(n+1) \mid
\transpos{A}JA = J\quad\hbox{and}\quad \det(A) = 1\}.
\]
Check that $\mathbf{SO}(n, 1)$ is indeed a group with the inverse of $A$  given by
$A^{-1} = J\transpos{A}J$ (this is the {\it special Lorentz group\/}.)
Consider the function
$\mapdef{f}{\mathbf{GL}^{+}(n+1)}{\mathbf{S}(n+1)}$, given by
\[
f(A) = \transpos{A}JA - J,
\]
where $\mathbf{S}(n+1)$ denotes the space of $(n+1)\times (n+1)$ symmetric matrices.
Prove that 
\[
df(A)(H) =  \transpos{A}JH +  \transpos{H}JA
\]
for any matrix, $H$. Prove that $df(A)$ is surjective for all $A\in \mathbf{SO}(n, 1)$
and  that $\mathbf{SO}(n, 1)$ is a manifold of dimension
$\frac{n(n+1)}{2}$.



\vspace {0.25cm}\noindent
{\bf Problem B3 (40 pts).}
(a) 
Given any matrix
\[
B = \matta{a}{b}{c}{-a}\in \mfrac{sl}(2, \complex),
\]
if $\omega^2  = a^2 + bc$ and $\omega$ is any of the
two complex roots of $a^2 + bc$, prove that if
$\omega\not= 0$, then
\[
e^B = \cosh \omega\, I + \frac{\sinh\, \omega}{\omega}\, B,
\]
and $e^B = I + B$, if $a^2 + bc = 0$.
Observe that $\mathrm{tr}(e^B) = 2\cosh\,\omega$.

\medskip
Prove that the exponential map,
$\mapdef{\exp}{\mfrac{sl}(2, \complex)}{\mathbf{SL}(2, \complex)}$,
is {\it not\/} surjective. For instance, prove that 
\[
\matta{-1}{1}{0}{-1}
\]
is not the exponential of any matrix in $\mfrac{sl}(2, \complex)$.
 
\medskip
(b)
Recall that a matrix, $N$, is {\it nilpotent\/} iff there is some $m\geq 0$ so
that $N^m = 0$. Let $A$ be any $n\times n$ matrix of the
form $A = I - N$, where $N$ is nilpotent. Why is $A$ invertible?
prove that there is some $B$ so that $e^B = I - N$ as follows:
Recall that for any $y\in\reals$ so that $|y - 1|$ is small enough,
we have
\[
\log(y) = -(1 - y) - \frac{(1 - y)^2}{2} - \cdots - \frac{(1 - y)^k}{k} - \cdots.
\]
As $N$ is nilpotent,  we have $N^m = 0$,  where $m$ is the smallest integer
with this propery. Then, the expression
\[
B = \log(I - N) = -N  - \frac{N^2}{2} - \cdots - \frac{N^{m-1}}{m-1}
\]
is well defined.
Use a formal power series argument to show that
\[
e^{B} = A.
\]
We denote $B$ by $\log(A)$.

\medskip
(c) 
Let $A\in \mathbf{GL}(n, \complex)$. 
Prove that there is some matrix, $B$, so that $e^B = A$.
Thus, the exponential map, 
$\mapdef{\exp}{\mfrac{gl}(n, \complex)}{\mathbf{GL}(n, \complex)}$,
is surjective. 

\medskip
First, use the fact that $A$ has a Jordan form,
$PJP^{-1}$. Then, show that finding a log of $A$ reduces to finding
a log of every Jordan block of $J$. As every Jordan block, $J$,  has
a fixed nonzero constant,  $\lambda$, on the diagonal,  with $1$'s
immediately above each diagonal entry and zero's everywhere else, we can write
$J$ as $(\lambda I)(I - N)$, where $N$ is nilpotent.
Find $B_1$ and $B_2$ so that
$\lambda I = e^{B_1}$, $I - N = e^{B_2}$, and $B_1B_2 = B_2B_1$.
Conclude that $J = e^{B_1 + B_2}$.


\vspace {0.25cm}\noindent
{\bf Problem B4 (60 pts).}
Recall from Homework 1, Problem B1, the Cayley parametrization
of rotation matrices in $\mathbf{SO}(n)$ given by
\[
C(B) = (I - B)(I + B)^{-1},
\]
where $B$ is any $n \times n$ skew symmetric matrix.
In that problem, it was shown that $C(B)$ is a rotation
matrix that does not admit $-1$ as an eigenvalue
and that every such rotation matrix is of the form $C(B)$.

\medskip
(a)
If you have not already done so, prove that
the map $B \mapsto C(B)$ is injective.

\medskip
(b)
Prove that
\[
dC(B)(A) =
D_A((I - B)(I + B)^{-1}) = -[I + (I - B)(I + B)^{-1}]A(I + B)^{-1}.
\]
{\it Hint\/}. First, show that
$D_A(B^{-1}) = - B^{-1}AB^{-1}$ (where $B$ is invertible)
and that \\
$D_A (f(B)g(B)) = (D_Af(B))g(B) + f(B)(D_Ag(B))$, where $f$ and $g$
are differentiable matrix functions.

\medskip
Deduce that $dC(B)$ is injective, for every skew-symmetric matrix, $B$.
If we identify the space of $n\times n$ skew symmetric matrices
with $\reals^{n(n-1)/2}$, show that the Cayley map, 
$\mapdef{C}{\reals^{n(n-1)/2}}{\mathbf{SO}(n)}$, is
a parametrization of $\mathbf{SO}(n)$.

\medskip
(c) Now, consider $n = 3$, i.e., $\mathbf{SO}(3)$.
Let $E_1$, $E_2$ and $E_3$ be the rotations about the
$x$-axis, $y$-axis, and $z$-axis, respectively, by the angle $\pi$, i.e.,
\[
E_1 = \mattc{1}{0}{0}
             {0}{-1}{0}
             {0}{0}{-1},
\quad
E_2 = \mattc{-1}{0}{0}
             {0}{1}{0}
             {0}{0}{-1},
\quad
E_3 = \mattc{-1}{0}{0}
             {0}{-1}{0}
             {0}{0}{1}.
\]
Prove that the four maps
\begin{eqnarray*}
B  & \mapsto & C(B) \\
B  & \mapsto & E_1C(B) \\
B  & \mapsto & E_2C(B) \\
B  & \mapsto & E_3C(B) 
\end{eqnarray*}
where $B$ is skew symmetric,
are parametrizations of $\mathbf{SO}(3)$ and that the union
of the images of $C$, $E_1C$, $E_2C$ and $E_3C$ covers
$\mathbf{SO}(3)$, so that  $\mathbf{SO}(3)$ is a manifold.

\medskip
(d)
Let $A$ be {\it any\/} matrix (not necessarily invertible).
Prove that there is some diagonal matrix, $E$, with entries
$+1$ or $-1$, so that $EA + I$ is invertible.

\medskip
(e)
Prove that every rotation matrix, $A\in \mathbf{SO}(n)$, is of the form
\[
A = E(I - B)(I + B)^{-1},
\]
for some skew symmetric matrix, $B$, and some
diagonal matrix, $E$, with entries $+1$ and $-1$, and where
the number of $-1$ is even.
Moreover,   prove that every orthogonal
matrix $A\in \mathbf{O}(n)$ is of the form
\[
A = E(I - B)(I + B)^{-1},
\]
for some skew symmetric matrix, $B$, and some
diagonal matrix, $E$, with entries $+1$ and $-1$.
The above provide parametrizations for  $\mathbf{SO}(n)$ (resp. 
$\mathbf{O}(n)$) that show that  $\mathbf{SO}(n)$ and
$\mathbf{O}(n)$ are manifolds. However, observe that the number
of these charts grows exponentially with $n$.


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

\end{document}