\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, 2008 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 1, Corrected Version}\\[10pt] February 18, 2008; Due March 5, 2008\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm}\noindent {\bf Problem A1.} (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.25cm}\noindent {\bf Problem A2.} (a) If $K = \reals$ or $K = \complex$, recall that the projective space, $\projs{K^{n+1}}$, is the set of equivalence classes of the equivalence relation, $\sim$, on $K^{n + 1} - \{0\}$, defined so that, for all $u, v \in K^{n + 1} - \{0\}$, \[ u \sim v\quad\hbox{iff}\quad v = \lambda u, \quad\hbox{for some}\quad\lambda \in K - \{0\}. \] The map, $\mapdef{p}{(K^{n+1} - \{0\})}{\projs{K^{n+1}}}$, is the projection mapping any nonzero vector in $K^{n+1}$ to its equivalence class modulo $\sim$. We let $\rprospac{n} = \projs{\reals^{n+1}}$ and $\cprospac{n} = \projs{\complex^{n+1}}$. \medskip Prove that for any $n\geq 0$, there is a bijection between $\projs{K^{n+1}}$ and $K^{n} \cup \projs{K^{n}}$ (which allows us to identify them). \medskip (b) Prove that $\rprospac{n}$ and $\cprospac{n}$ are connected and compact. \medskip \hint If \[S^n = \{(x_1,\ldots,x_{n+1})\in K^{n+1}\ |\ x_1^2 + \cdots + x_{n+1}^2 = 1\},\] prove that $p(S^n) = \projs{K^{n+1}}$, and recall that $S^n$ is compact for all $n\geq 0$ and connected for $n\geq 1$. For $n = 0$, $\projs{K}$ consists of a single point. \vspace {0.25cm}\noindent {\bf Problem A3.} Recall that $\reals^2$ and $\complex$ can be identified using the bijection $(x, y) \mapsto x + iy$. Also recall that the subset $U(1)\subseteq \complex$ consisting of all complex numbers of the form $\cos\theta + i\sin\theta$ is homeomorphic to the circle $S^1 = \{(x, y)\in \reals^2\ |\ x^2 + y^2 = 1\}$. If $\mapdef{c}{U(1)}{U(1)}$ is the map defined such that \[c(z) = z^2,\] prove that $c(z_1) = c(z_2)$ iff either $z_2 = z_1$ or $z_2 = -z_1$, and thus that $c$ induces a bijective map $\mapdef{\hli{c}}{\rprospac{1}}{S^1}$. Prove that $\hli{c}$ is a homeomorphism (remember that $\rprospac{1}$ is compact). \vspace {0.5cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (20 pts).} Let $A = (a_{i\, j})$ be a real or complex $n\times n$ matrix. \medskip (1) If $\lambda$ is an eigenvalue of $A$, prove that there is some eigenvector $\novect{u} = (u_1, \ldots, u_n)$ of $A$ for $\lambda$ such that \[\max_{1\leq i\leq n} |u_i| = 1.\] \medskip (2) If $\novect{u} = (u_1, \ldots, u_n)$ is an eigenvector of $A$ for $\lambda$ as in (1), assuming that $i$, $1\leq i \leq n$, is an index such that $|u_i| = 1$, prove that \[(\lambda - a_{i\, i})u_i = \sum_{{j = 1} \atop {j\not= i}}^{n} a_{i\, j} u_j,\] and thus that \[|\lambda - a_{i\, i}| \leq \sum_{{j = 1} \atop {j\not= i}}^{n} |a_{i\, j}|.\] Conclude that the eigenvalues of $A$ are inside the union of the closed disks $D_i$ defined such that \[D_i = \biggl\{z\in \complex\ |\ |z - a_{i\, i}| \leq \sum_{{j = 1} \atop {j\not= i}}^{n} |a_{i\, j}|\biggr\}.\] \medskip \remark This result is known as {\it Gershgorin's theorem\/}. \vspace {0.5cm}\noindent \vspace {0.25cm}\noindent {\bf Problem B2 (10).} Recall that a real $n\times n$ symmetric matrix, $A$, is {\it positive semi-definite\/} iff its eigenvalues, $\lambda_1, \ldots, \lambda_n$ are non-negative (i.e., $\lambda_i \geq 0$ for $i = 1, \ldots, n$) and {\it positive definite\/} iff its eigenvalues are positive (i.e., $\lambda_i >0 $ for $i = 1, \ldots, n$). \medskip (a) Prove that a symmetric matrix, $A$, is positive semi-definite iff $\transpos{X}A X \geq 0$, for all $X\not= 0$ ($X\in \reals^n$) and positive definite iff $\transpos{X}A X > 0$, for all $X\not= 0$ ($X\in \reals^n$). \medskip (b) Prove that for any two positive definite matrices, $A, B$, for all $\lambda, \mu \in \reals$, with $\lambda, \mu \geq 0$ and $\lambda + \mu > 0$, the matrix $\lambda A + \mu B$ is still symmetric, positive definite. Deduce that the set of $n\times n$ symmetric positive definite matrices is convex (in fact, a cone). \vspace {0.25cm}\noindent {\bf Problem B3 (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 B4 (60).} (a) Consider the map $\mapdef{\s{H}}{\reals^3}{\reals^4}$ defined such that \[(x, y, z) \mapsto (xy, yz, xz, x^2 - y^2).\] Prove that when it is restricted to the sphere $S^2$ (in $\reals^3$), we have $\s{H}(x, y, z) = \s{H}(x', y', z')$ iff $(x', y', z') = (x, y, z)$ or $(x', y', z') = (-x, -y, -z)$. In other words, the inverse image of every point in $\s{H}(S^2)$ consists of two antipodal points. \medskip Prove that the map $\s{H}$ induces an injective map from the projective plane onto $\s{H}(S^2)$, and that it is a homeomorphism. \medskip (b) The map $\s{H}$ allows us to realize concretely the projective plane in $\reals^4$ as an embedded manifold. Consider the three maps from $\reals^2$ to $\reals^4$ given by \begin{eqnarray*} \psi_1(u, v) & = & \left( \frac{uv}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{u}{u^2 + v^2 + 1}, \frac{u^2 - v^2}{u^2 + v^2 + 1} \right), \\ \psi_2(u, v) & = & \left( \frac{u}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{uv}{u^2 + v^2 + 1}, \frac{u^2 - 1}{u^2 + v^2 + 1} \right), \\ \psi_3(u, v) & = & \left( \frac{u}{u^2 + v^2 + 1}, \frac{uv}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{1 - u^2}{u^2 + v^2 + 1} \right). \end{eqnarray*} % Observe that $\psi_1$ is the composition $\s{H} \circ \alpha_1$, where $\alpha_1\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{u}{\sqrt{u^2 + v^2 + 1}}, \frac{v}{\sqrt{u^2 + v^2 + 1}}, \frac{1}{\sqrt{u^2 + v^2 + 1}} \right), \] that $\psi_2$ is the composition $\s{H} \circ \alpha_2$, where $\alpha_2\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{u}{\sqrt{u^2 + v^2 + 1}}, \frac{1}{\sqrt{u^2 + v^2 + 1}}, \frac{v}{\sqrt{u^2 + v^2 + 1}} \right). \] and $\psi_3$ is the composition $\s{H} \circ \alpha_3$, where $\alpha_3\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{1}{\sqrt{u^2 + v^2 + 1}}, \frac{u}{\sqrt{u^2 + v^2 + 1}}, \frac{v}{\sqrt{u^2 + v^2 + 1}} \right), \] Prove that each $\psi_i$ is injective, continuous and nonsingular (i.e., the Jacobian is never zero). \medskip Prove that if $\psi_1(u, v) = (x, y, z, t)$, then \[ y^2 + z^2 \leq \frac{1}{4} \quad\hbox{and}\quad y^2 + z^2 = \frac{1}{4} \quad\hbox{iff}\quad u^2 + v^2 = 1. \] Prove that $u$ and $v$ are solutions of the quadratic equations \begin{eqnarray*} (y^2 + z^2)u^2 - zu + z^2 & = & 0 \\ (y^2 + z^2)v^2 - yv + y^2 & = & 0. \end{eqnarray*} Prove that if $y^2 + z^2 \not= 0$, then \[ u = \frac{z(1 - \sqrt{1 - 4(y^2 + z^2)})}{2(y^2 + z^2)} \quad \hbox{if}\quad u^2 + v^2 \leq 1, \] else \[ u = \frac{z(1 + \sqrt{1 - 4(y^2 + z^2)})}{2(y^2 + z^2)} \quad \hbox{if}\quad u^2 + v^2 \geq 1, \] and there are similar formulae for $v$. Prove that the expression giving $u$ in terms of $y$ and $z$ is continuous everywhere in $\{(y, z) \mid y^2 + z^2 \leq \frac{1}{4}\}$ and similarly for the expression giving $v$ in terms of $y$ and $z$. Conclude that $\mapdef{\psi_1}{\reals^2}{\psi_1(\reals^2)}$ is a homeomorphism onto its image. Therefore, $U_1 = \psi_1(\reals^2)$ is an open subset of $\s{H}(S^2)$. \medskip \remark From the equations above, you can prove that $u^2 + v^2 + 1$ is a root of the equation \[ (y^2 + z^2)D^2 - D + 1 = 0. \] Then, \[ D = \frac{1 - \sqrt{1 - 4(y^2 + z^2)}}{2(y^2 + z^2)} \quad \hbox{if}\quad u^2 + v^2 \leq 1, \] else \[ D = \frac{1 + \sqrt{1 - 4(y^2 + z^2}}{2(y^2 + z^2)} \quad \hbox{if}\quad u^2 + v^2 \geq 1. \] \medskip Prove that if $\psi_2(u, v) = (x, y, z, t)$, then $u$ and $v$ are solutions of quadratic equations with coefficients involving $x$ and $y$; find explicit formulae as for $\psi_1^{-1}$ and conclude that $\mapdef{\psi_2}{\reals^2}{\psi_3(\reals^2)}$ is a homeomorphism onto its image. The set $U_2 = \psi_2(\reals^2)$ is an open subset of $\s{H}(S^2)$. \medskip Prove that if $\psi_3(u, v) = (x, y, z, t)$, then $u$ and $v$ are solutions of quadratic equations with coefficients involving $x$ and $z$. As for $\psi_2^{-1}$, conclude that $\mapdef{\psi_3}{\reals^2}{\psi_3(\reals^2)}$ is a homeomorphism onto its image. The set $U_3 = \psi_3(\reals^2)$ is an open subset of $\s{H}(S^2)$. \medskip Prove that the union of the $U_i$'s covers $\s{H}(S^2)$. Conclude that $\psi_1, \psi_2, \psi_3$ are parametrizations of $\rprospac{2}$ as a manifold in $\reals^4$. \medskip Prove that if $(x, y, z, t)\in \s{H}(S^2)$, then \begin{eqnarray*} x^2y^2 + x^2z^2 + y^2z^2 & = & xyz \\ x(z^2 - y^2) & = & yzt. \end{eqnarray*} \medskip The zero locus of these equations strictly contains $\s{H}(S^2)$, prove it. This is a ``famous mistake'' of Hilbert and Cohn-Vossen in {\sl Geometry and the Immagination\/}! In an attempt to fix this bug, prove that when you express $x$ in terms of $y$ and $z$ using $\psi_1$, you get the equation \[ x^2y^2 + x^2z^2 + y^2z^2 = xyz. \] When you express $t$ in terms of $y$ and $z$ using $\psi_1$, you get the equation \[ (y^2 + z^2)(z^2 - y^2 + t^2) = t(z^2 - y^2). \] When you express $t$ in terms of $x$ and $y$ using $\psi_2$, you get the equation \[ 4(x^2 + y^2)((x^2 + y^2)t^2 + (2x^2 + y^2)^2) = (2x^2 + y^2)^2. \] When you express $t$ in terms of $x$ and $z$ using $\psi_3$, you get an equation similar to the previous one. Do these four equations define exactly $\s{H}(S^2)$? (I suspect they do!) \medskip (c) Investigate the surfaces in $\reals^3$ obtained by dropping one of the four coordinates. Show that there are only two of them (the ``Steiner Roman surface'' and the ``crosscap'', up to a rigid motion). \vspace {0.25cm}\noindent {\bf Problem B5 (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 B6 (20 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)$. \vspace {0.25cm}\noindent {\bf Problem B7 (50 pts).} Recall that for any matrix \[ A = \mattc{0}{-c}{b}{c}{0}{-a}{-b}{a}{0}, \] if we let $\theta = \sqrt{a^2 + b^2 + c^2}$ and % \[ B = \mattc{a^2}{ab}{ac}{ab}{b^2}{bc}{ac}{bc}{c^2}, \] then 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$ (Rodrigues's formula (1840)). \medskip (a) Let $R\in \mathbf{SO}(3)$ and assume that $R\not= I$ and $\mathrm{tr}(R) \not= -1$. Then, prove that a log of $R$ (i.e., a skew symmetric matrix, $S$, so that $e^S = R$) is given by \[ \log(R) = \frac{\theta}{2\sin\theta}(R - R^T), \] where $1 + 2\cos\theta = \trace(R)$ and $0 < \theta < \pi$. \medskip (b) Now, assume that $\mathrm{tr}(R) = -1$. In this case, show that $R$ is a rotation of angle $\pi$, that $R$ is symmetric and has eigenvalues, $-1, -1, 1$. Assuming that $e^A = R$, Rodrigues formula becomes \[ R = I + \frac{2}{\pi^2} A^2, \] so \[ A^2 = \frac{\pi^2}{2}(R - I). \] If we let $S = A/\pi$, we see that we need to find a skew-symmetric matrix, $S$, so that \[ S^2 = \frac{1}{2}(R - I) = C. \] Observe that $C$ is also symmetric and has eigenvalues, $-1, -1, 0$. Thus, we can diagonalize $C$, as \[ C = P\mattc{-1}{0}{0} {0}{-1}{0} {0}{0}{0} \transpos{P}, \] and if we let \[ S = P\mattc{0}{-1}{0} {1}{0}{0} {0}{0}{0} \transpos{P}, \] check that $S^2 = C$. \medskip (c) From (a) and (b), we know that we can compute explicity a log of a rotation matrix, although when $\theta \approx 0$, we have to be careful in computing $\frac{\sin\theta}{\theta}$; in this case, we may want to use \[ \frac{\sin\theta}{\theta} = 1 - \frac{\theta^2}{3!} + \frac{\theta^4}{5!} + \cdots. \] Given two rotations, $R_1, R_2\in \mathbf{SO}(3)$, there are three natural interpolation formulae: \[ e^{(1 - t)\log R_1 + t\log R_2}; \quad R_1 e^{t \log(\transpos{R_1}R_2)}; \quad e^{t\log( R_2\transpos{R_1})} R_1, \] with $0 \leq t \leq 1$. \medskip Write a computer program to investigate the difference between these interpolation formulae. The position of a rigid body spinning around its center of gravity is determined by a rotation matrix, $R\in \mathbf{SO}(3)$. If $R_1$ denotes the initial position and $R_2$ the final position of this rigid body, by computing interpolants of $R_1$ and $R_2$, we get a motion of the rigid body and we can create an animation of this motion by displaying several interpolants. The rigid body can be a ``funny'' object, for example a banana, a bottle, etc. \vspace{0.5cm}\noindent {\bf TOTAL: 240 points.} \end{document}