\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 Summer 1, 2009 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 3}\\[10pt] June 23, 2009; Due June 30 2009\\ \end{center} \vspace {0.5cm} ``B problems'' must be turned in. \vspace{0.5cm}\noindent {\bf Problem B1 (30 pts)}. Let $(v_1, \ldots, v_n)$ be a sequence of $n$ vectors in $\reals^d$ and let $V$ be the $d\times n$ matrix whose $j$-th column is $v_j$. Prove the equivalence of the following two statements: \begin{enumerate} \item[(a)] There is no nontrivial positive linear dependence among the $v_j$, which means that there is no nonzero vector, $y = (y_1, \ldots, y_n)\in \reals^n$, with $y_j \geq 0$ for $j = 1, \ldots, n$, so that \[ y_1v_1 + \cdots + y_nv_n = 0 \] or equivalently, $V y = 0$. \item[(b)] There is some vector, $c\in \reals^d$, so that $\transpos{c} V > 0$, which means that $\transpos{c} v_j > 0$, for $j = 1, \ldots, n$. \end{enumerate} \vspace{0.5cm}\noindent {\bf Problem B2 (20 pts)}. Let $E$ be a real vector space of finite dimension, $n\geq 1$. Say that two bases, $(u_1, \ldots, u_n)$ and $(v_1, \ldots, v_n)$, of $E$ have the {\it same orientation\/} iff $\det(P) > 0$, where $P$ the change of basis matrix from $(u_1, \ldots, u_n)$ and $(v_1, \ldots, v_n)$, namely, the matrix whose $j$th columns consist of the coordinates of $v_j$ over the basis $(u_1, \ldots, u_n)$. \medskip (a) Prove that having the same orientation is an equivalence relation with two equivalence classes. \medskip An {\it orientation\/} of a vector space, $E$, is the choice of any fixed basis, say $(e_1, \ldots, e_n)$, of $E$. Any other basis, $(v_1, \ldots, v_n)$, has the {\it same orientation\/} as $(e_1, \ldots, e_n)$ (and is said to be {\it positive\/} or {\it direct\/}) iff $\det(P) > 0$, else it said to have the {\it opposite orientation\/} of $(e_1, \ldots, e_n)$ (or to be {\it negative\/} or {\it indirect\/}), where $P$ is the change of basis matrix from $(e_1, \ldots, e_n)$ to $(v_1, \ldots, v_n)$. An {\it oriented\/} vector space is a vector space with some chosen orientation (a positive basis). \medskip (b) Let $B_1 = (u_1, \ldots, u_n)$ and $B_2 = (v_1, \ldots, v_n)$ be two orthonormal bases. For any sequence of vectors, $(w_1, \ldots, w_n)$, in $E$, let $\det_{B_1}(w_1, \ldots, w_n)$ be the determinant of the matrix whose columns are the coordinates of the $w_j$'s over the basis $B_1$ and similarly for $\det_{B_2}(w_1, \ldots, w_n)$. \medskip Prove that if $B_1$ and $B_2$ have the same orientation, then \[ \mathrm{det}_{B_1}(w_1, \ldots, w_n) = \mathrm{det}_{B_2}(w_1, \ldots, w_n). \] \medskip Given any oriented vector space, $E$, for any sequence of vectors, $(w_1, \ldots, w_n)$, in $E$, the common value, $\det_{B}(w_1, \ldots, w_n)$, for all positive orthonormal bases, $B$, of $E$ is denoted \[ \lambda_E(w_1, \ldots, w_n) \] and called a {\it volume form\/} of $(w_1, \ldots, w_n)$. \medskip (c) Given any Euclidean oriented vector space, $E$, of dimension $n$ for any $n - 1$ vectors, $w_1, \ldots, w_{n - 1}$, in $E$, check that the map \[ x \mapsto \lambda_E(w_1, \ldots, w_{n - 1}, x) \] is a linear form. Then, prove that there is a unique vector, denoted $w_1\times \cdots \times w_{n-1}$, such that \[ \lambda_E(w_1, \ldots, w_{n-1}, x) = (w_1\times \cdots \times w_{n-1}) \cdot x, \] for all $x\in E$. The vector $w_1\times \cdots \times w_{n-1}$ is called the {\it cross-product\/} of $(w_1, \ldots, w_{n-1})$. It is a generalization of the cross-product in $\reals^3$ (when $n = 3$). \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 If $(\novect{e_1},\ldots,\novect{e_n})$ is an orthonormal basis 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).} (1) If an upper triangular $n\times n$ matrix $R$ is invertible, prove that its inverse is also upper triangular. \medskip (2) If an upper triangular matrix is orthogonal, prove that it must be a diagonal matrix. \medskip If $A$ is an invertible $n\times n$ matrix and if $A = Q_1R_1 = Q_2R_2$, where $R_1$ and $R_2$ are upper triangular with positive diagonal entries and $Q_1, Q_2$ are orthogonal, prove that $Q_1 = Q_2$ and $R_1 = R_2$. \vspace{0.5cm}\noindent {\bf TOTAL: 160 points.} \end{document}