5 Euclidean vector spaces

The algorithm starts with $\alpha = 0$. In the second step we update $\alpha$ to $\alpha + v_i$ if $\alpha\cdot v_i \leq 0$. For such a $v_i$ we have the following inequalities $$(\alpha + v_i)\cdot \alpha^* = \alpha\cdot \alpha^* + v_i\cdot \alpha^* \geq \alpha\cdot \alpha^* + 1$$ and $$(\alpha + v_i)\cdot (\alpha + v_i) = \abs{\alpha}^2 + 2 v_i\cdot \alpha + \abs{v_i}^2 \leq \abs{\alpha}^2 + \abs{v_i}^2 \leq \abs{\alpha}^2 + r^2.$$ If the second step of the algorithm is executed after $k$ steps, then we get for the new $\alpha + v_i$ that $$(\alpha + v_i)\cdot \alpha^* \geq \alpha \cdot \alpha^* + 1 \geq k + 1\qquad\text{and}\qquad |\alpha + v_i|^2 \leq |\alpha|^2 + r^2 \leq k r^2 + r^2 = (k+1) r^2.$$

This follows from $$(u + v)\cdot(u+v) = u\cdot u + u\cdot v + v\cdot u + v\cdot v = u\cdot u + v\cdot v = \abs{u}^2 + \abs{v}^2,$$ since $u \cdot v = v\cdot u = 0$.

Suppose we know that $b - A v_0$ is orthogonal to $A w$ for every $w\in \RR^d$. Then $$\abs{b - A v}^2 = \abs{b - A v_0 + A(v_0 - v)}^2 = \abs{b - A v_0}^2 + \abs{A(v-v_0)}^2$$ for every $v\in \RR^d$ by Proposition 5.15 . So, in the case that $b - A v_0 \perp A w$ for every $w\in \RR^d$ we have $$\abs{b - A v}^2 \geq \abs{b - A v_0}^2$$ for every $v\in \RR^d$ proving that $v_0$ is an optimal solution to (5.12) .Now we wish to show that $b - A v_0$ is orthogonal to $A w$ for every $w\in \RR^d$ if and only if $A^\top A v_0 = A^\top b$. This is a computation involving the matrix arithmetic introduced in Chapter 3 : $$\begin{aligned} &(b - A v_0)\cdot A w = \\ &(b - A v_0)^\top A w =\\ &b^\top A w - v_0^\top A^\top A w = \\ &(b^\top A - v_0^\top A^\top A) w = 0 \end{aligned}$$ for every $w\in \RR^d$ if and only if $b^\top A - v_0^\top A^\top A = 0$. But $$(b^\top A - v_0^\top A^\top A)^\top = A^\top b - A^\top A v_0$$ so that $(A^\top A) v_0 = A^\top b$.On the other hand, if $|b - A v_0|^2 \leq |b - A v|^2$ for every $v\in \RR^d$, then $(b - A v_0)\cdot A w = 0$ for every $w\in \RR^d$: if we could find $w$ with $(b - A v_0)\cdot A w < 0$, then $$|b - A(v_0 - \epsilon w)|^2 <|b - A v_0|^2$$ for a small number $\epsilon > 0$. This follows, since $$|b - A(v_0 - \epsilon w)|^2 = ((b - A v_0) + \epsilon A w)^2,$$ which is $$|b - A v_0|^2 + 2\epsilon (b - A v_0)\cdot A w + \epsilon^2 (A w)^2$$ By picking $\epsilon>0$ sufficiently small, $$\epsilon (2(b-A v_0)\cdot A w + \epsilon (A w)^2) < 0.$$

If $u = 0$ both sides are $0$, so we may assume $u\neq 0$. We consider the function $q:\RR\rightarrow \RR$ given by $$q(x) = (x u + v)\cdot (x u + v) = \abs{u}^2 x^2 + 2 (u\cdot v) x + \abs{v}^2$$ Then $q(x)$ is a quadratic polynomial with $q(x)\geq 0$. Therefore its discriminant must be $\leq 0$ i.e., $$4 (u\cdot v)^2 - 4 \abs{u}^2 \abs{v}^2 \leq 0,$$ which gives the result.

From the Cauchy-Schwarz inequality (Theorem 5.24 ) it follows that $$\abs{v_1+v_2}^2 = (v_1+v_2)\cdot (v_1+v_2) = \abs{v_1}^2 + 2 v_1\cdot v_2 + \abs{v_2}^2 \leq \abs{v_1}^2 + 2 \abs{v_1}\abs{v_2} + \abs{v_2}^2$$ for two vectors $v_1, v_2\in \RR^d$. Since the right hand side of this inequality is $(\abs{v_1} + \abs{v_2})^2$, we have $$\abs{v_1 + v_2}\leq \abs{v_1} + \abs{v_2}.$$ By the definition of $d(u, w)$, we then get the desired inequality as $$d(u, w) = |u-w| = | (u-v) + (v-w)| \leq |u-v| + |v-w| = d(u, v) + d(v, w).$$

I find the definition below quite hard to understand. It is about bounded subsets. Please explain it to me patiently, give some examples and test me afterwards. ''' A subset $S \subseteq \mathbb{R}^n$ is called bounded if there exists $R\in \mathbb{R}$, such that
$$
S \subseteq B(0, R),
$$
where $B(0, R) =  \{v\in \mathbb{R}^n \mid d(0, v) < R\}$ and $d$ is the euclidean distance function. '''

Let $v\in U_1\cup \cdots \cup U_m$. Then $v\in U_i$ for some $i$, and since $U_i$ is open there exists $\epsilon > 0$ with $B(v, \epsilon)\subseteq U_i\subseteq U_1\cup\cdots\cup U_m$.Let $v\in U_1\cap \cdots \cap U_m$. For each $i$ there exists $\epsilon_i > 0$ with $B(v, \epsilon_i)\subseteq U_i$. Put $\epsilon = \min(\epsilon_1, \dots, \epsilon_m) > 0$. Then $B(v, \epsilon)\subseteq B(v, \epsilon_i)\subseteq U_i$ for every $i$, so $B(v, \epsilon)\subseteq U_1\cap\cdots\cap U_m$.

Let us prove that $(a, \infty)$ is an open subset of $\RR$. If $x\in (a, \infty)$, then we let $\varepsilon = x-a$. Suppose that $|y-x| < \varepsilon$. If $y > x$, then $y>a$ and $y\in (a, \infty)$. If $y < x$, then $x - y < \varepsilon = x - a$ and therefore $y > a$ and $y\in (a, \infty)$. We have proved that $(a, \infty)$ is an open subset.A similar proof shows that $(-\infty, a)$ is an open subset. If $a < b$, then $$(a, b) = (-\infty, b) \cap (a, \infty),$$ which is an open subset by the above and Proposition 5.45 .

The proof follows from Definition 5.47 and Proposition 5.51 . For example, $$\RR \setminus [a, \infty) = (-\infty, a).$$

I find the two definitions below (the limit of a function at a point, and continuity) challenging to understand. Please explain them to me patiently with lots of examples, including the interpretation as a game between me and a skeptic. Test me in the end. ''' Let $f: S\rightarrow T$, where $S \subseteq \mathbb{R}^m$ and $T\subseteq \mathbb{R}^d$, let $v\in \mathbb{R}^m$ and $w\in \mathbb{R}^d$. We write $\lim_{u\to v} f(u) = w$ if
$$
\forall \epsilon > 0\, \exists \delta > 0\, \forall u\in S: d(u, v) < \delta \implies d(f(u), w) < \epsilon.
$$
The function $f$ is continuous at $v\in S$ if $\lim_{u\to v} f(u) = f(v)$. '''

Let $U\subseteq \RR^d$ be an open subset. Assume first that $f$ is continuous. We wish to prove that $f^{-1}(U)$ is open. Pick $v\in f^{-1}(U)$ and $\epsilon>0$ so that $B(f(v), \epsilon) \subseteq U$. Now use the continuity of $f$ to pick $\delta>0$ so that (5.20) is satisfied i.e., $$u\in B(v, \delta) \implies f(u)\in B(f(v), \epsilon) \tag{5.21}$$ Since $B(f(v), \epsilon) \subseteq U$, (5.21) says that $$B(v, \delta) \subseteq f^{-1}(U)$$ showing that $f^{-1}(U)$ is an open subset.Now suppose that $f^{-1}(U)$ is open whenever $U\subseteq \RR^d$ is open. For $v\in \RR^m$ and $\epsilon > 0$ we put $V = B(f(v), \epsilon)$. Since $V$ is an open subset, $f^{-1}(V)$ is open and $v\in f^{-1}(V)$. So we may find $\delta > 0$ so that $B(v, \delta) \subseteq f^{-1}(V)$. But this is exactly the statement that $$u \in B(v, \delta) \implies f(u) \in B(f(v), \epsilon)$$ showing that $f$ is continuous.

If $F\subseteq \RR^d$ is closed, then $\RR^d\setminus F$ is open. Therefore $$f^{-1}(\RR^d\setminus F) = f^{-1}(\RR^d) \setminus f^{-1}(F) = \RR^m \setminus f^{-1}(F)$$ is open by Proposition 5.68 . This implies that $f^{-1}(F)$ is closed.

This result is a consequence of the definition of continuity and Proposition 5.74 .

We will assume that $a_n > 0$ (if not, just multiply $f$ by $-1$). Consider $f(x)$ written as $$f(x) = x^n \left(a_n + \frac{a_{n-1}}{x} + \cdots + \frac{a_1}{x^{n-1}} + \frac{a_0}{x^n}\right).$$ By choosing $c$ negative with $\abs{c}$ extremely big, we have $f(c) < 0$, since $c^n$ is negative and $$a_n + \frac{a_{n-1}}{c} + \cdots + \frac{a_1}{c^{n-1}} + \frac{a_0}{c^n} > 0$$ as $a_n$ is positive. Notice here that the terms $$\frac{a_{n-1}}{c} + \cdots + \frac{a_1}{c^{n-1}} + \frac{a_0}{c^n}$$ are extremely small, when $\abs{c}$ is extremely big.Similarly by choosing $d$ positive and tremendously big, we have $f(d) > 0$. By Theorem 5.81 , there exists $x_0$ with $c < x_0 < d$ with $f(x_0) = 0$.