Discrete Math, Sixth Problem Set (June 30) REU 2003

$\begin{exx} % latex2html id marker 794 {\bf (Kronecker)} \ \ If the real numbers... ...ed in $[0,1]^n$, where $\underline{\alpha}=(\alpha_1,\dots,\alpha_n)$. \end{exx}$

$\begin{exercise} % latex2html id marker 796$1,\sqrt{2},\sqrt{3}$\ are linearly independent over $\mathbb{Q}$. \end{exercise}$

$\begin{exx} % latex2html id marker 798$1,\sqrt{2},\dots,\sqrt{p}$\ are linearly independent over $\mathbb{Q}$. \end{exx}$
Gram-Schmidt orthogonalization
input: ${\mathbf{b}}_1,{\mathbf{b}}_2,\dots$ sequence of vectors in a (finite or infinite dimensional) Euclidean space.
output: ${\mathbf{b}}_1^*,{\mathbf{b}}_2^*,\dots$
conditions:
1. ${\mathbf{b}}_i^*\cdot {\mathbf{b}}_j^*=0$ if $i\neq j$ .
2. Let

span $\{{\mathbf{b}}_1,\dots,{\mathbf{b}}_i\}$ . Then also

span $\{{\mathbf{b}}_1^*,\dots,{\mathbf{b}}_i^*\}$ .
3. ${\mathbf{b}}_i-{\mathbf{b}}_i^*\in U_{i-1}$ .

$\begin{exercise} Prove that under the stated condition, the output sequence is unique. \end{exercise}$

$\begin{exercise} % latex2html id marker 826Prove that Gram-Schmidt orthogonali... ...\mathbf{b}}_k)=$\ vol$({\mathbf{b}}_1^*,\dots,{\mathbf{b}}_k^*)$. \end{exercise}$

Definition 0.1 The Gram matrix of ${\mathbf{b}}_1,\dots,{\mathbf{b}}_k$ is

$\displaystyle G({\mathbf{b}}_1,\dots,{\mathbf{b}}_k)=({\mathbf{b}}_i\cdot{\mathbf{b}}_j)_{k\times k}.$

$\begin{exercise} % latex2html id marker 856Prove that $G({\mathbf{b}}_1,\dots,... ...\{{\mathbf{b}}_1,\dots,{\mathbf{b}}_k\}$are linearly independent. \end{exercise}$

Exercise 0.2 Show det $G({\mathbf{b}}_1,\dots,{\mathbf{b}}_k)=$ det $G({\mathbf{b}}_1^*,\dots,{\mathbf{b}}_k^*)$ .

Example 0.3

$\begin{displaymath} % latex2html id marker 1384G({\mathbf{b}}_1^*,\dots,{\math... ...\mathbf 0} & & \Vert{{\mathbf{b}}_k}\Vert^2 \end{array}\right] \end{displaymath}$

$\begin{exercise} % latex2html id marker 896The $k$-dimensional volume of the p... ... {\em Note:} If $k=n$, then the volume itself is an integer. Why? \end{exercise}$

Example 0.4 Let ${\mathbf{a}},{\mathbf{b}}\in {\mathbb{R}}^n$ . Then

vol $\begin{displaymath} % latex2html id marker 1389 ({\mathbf{a}},{\mathbf{b}})^2=\l... ...t{{\mathbf{b}}}\Vert^2-({\mathbf{a}}\cdot{\mathbf{b}})^2\geq0. \end{displaymath}$

Note that the last inequality is the Cauchy-Schwarz inequality.

$\begin{exercise} % latex2html id marker 936Let $A$\ be the $n\times k$\ matrix... ...em Hint.}\ $A^*A=\left([{\mathbf{b}}_i]^*[{\mathbf{b}}_j]\right).$\end{exercise}$