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