6

This is a problem from a linear algebra textbook. Given a finite dimensional inner product space $V$ with orthonormal basis $e_1, \ldots, e_n$, show that if a list of vectors $v_1, \ldots, v_n$ satisfies $\|e_j - v_j\| < \frac{1}{\sqrt{n}}$ for all $j$ in $\{1, \ldots, n\}$, then $v_j$'s form a basis of $V$.

I have no idea. It's intuitive when I think about $\mathbb{R}^2$, looking at little spheres at the tips of the $e_j$'s.

I thought about looking at prefixes, like it should be true that $\|e_j - v_j\| < \frac{1}{\sqrt{i}}$ for all $j$ in $\{1, \ldots, n\}$. So now if $v_i \in \operatorname{span}(v_1, \ldots, v_i)$ then it should violate the inequality. It just looked ugly. Is this even a good direction? Edit: I see it's ridiculous now...

Is this something hard (it's Axler's book, 3rd edition, and the problems aren't marked by difficulty, so I don't want to waste time), or am I just being silly?

Michael Hardy
  • 1
gus
  • 247
  • Looks like a fun problem. So start by looking at the simplest case n=2. Draw a unit square OAXB, so that OA, OB are the two vectors e1,e2. If v1,v2 are OP,OQ, what regions can P,Q lie in? You should see immediately that the result is true. Proceed similarly for n=3. Does that help? – almagest Sep 26 '15 at 19:37
  • For n = 2 it's a tight bound and it's clear that no line through O can intersect both regions. For n = 3 it doesn't seem tight. If I'm not mistaken the distance can go up to sqrt(6)/4. I got that by looking at the equilateral triangle formed by the endpoints of e1, e2, e3. But beyond n = 3 I can't really think geometrically. – gus Sep 26 '15 at 20:11
  • Let the three basis vectors be OA,OB,OC. Let the long diagonal be OD. If the new vectors are OA',OB',OC' then A' lies strictly inside a sphere centre A radius 1/rt 3. But you have to show that the plane OA'B' cannot contain C', so it is slightly trickier than the case n=2, but still doable. However, I am beginning to wonder whether this is not a cul-de-sac for the general case. Hmmm. Maybe not if one switches from geometry to algebra ... – almagest Sep 26 '15 at 20:29
  • I was thinking maybe there's an elimination style algorithm that turns vj's into ej's so that at any point of the algorithm the condition is satisfied, but I'm too tired now to look into it further. – gus Sep 26 '15 at 22:08

3 Answers3

3

Define $u_i := v_i - e_i$ so $v_i = e_i + u_i$ and $||u_i||^2 < \frac{1}{n}$. It is enough to show that $(e_1 + u_1, \ldots, e_n + u_n)$ are linearly independent. Let $a_i \in \mathbb{C}$ be scalars such that $\sum_{i=1}^n a_i (e_i + u_i) = 0$. Then $$ \sum_{i=1}^n a_i e_i = -\sum_{i=1}^n a_i u_i. $$ Taking norms and using the fact that $(e_i)$ is an orthonormal basis, we have $$ \sum_{i=1}^n |a_i|^2 = \left| \left| \sum_{i=1}^n a_i e_i \right| \right|^2 = \left| \left| \sum_{i=1}^n a_i u_i \right| \right|^2. $$ Using the triangle inequality and Cauchy-Schwartz inequality (in $\mathbb{R}^n$), we have $$ \sum_{i=1}^n |a_i|^2 = \left| \left| \sum_{i=1}^n a_i u_i \right| \right|^2 \leq \left( \sum_{i=1}^n |a_i| ||u_i|| \right)^2 \leq \left( \sum_{i=1}^n |a_i|^2 \right) \left( \sum_{i=1}^n ||u_i||^2 \right). $$

Thus, we obtain

$$ \left(\sum_{i=1}^n |a_i|^2 \right) \left( 1 - \sum_{i=1}^n ||u_i||^2 \right) \leq 0.$$

Since $\sum_{i=1}^n ||u_i||^2 < \sum_{i=1}^n \frac{1}{n} = 1$, we must have $\sum_{i=1}^n |a_i|^2 = 0$ showing that $a_i = 0$ for all $1 \leq i \leq n$.

levap
  • 65,634
  • 5
  • 79
  • 122
3

May be just use the definition of linear dependence of vectors. Let $\alpha=(\alpha_1,\cdots,\alpha_m)$ such that $\sum_{i=1}^n\alpha_iv_i=0$ then $\sum_{i=1}^n|\alpha_i|^2=\|\sum_{i=1}^n\alpha_ie_i-\sum_{i=1}^n\alpha_iv_i\|^2=\|\sum_{i=1}^n\alpha_i(e_i-v_i)\|^2$ $\leq (\sum_{i=1}^n|\alpha_i|\|(e_i-v_i)\|)^2<(\sum_{i=1}^n|\alpha_i|\frac1{\sqrt{n}})^2<\sum_{i=1}^n|\alpha_i|^2$

then $\alpha=0$

metic
  • 56
  • 3
    The proof by metic is what I had in mind when putting this exercise in Linear Algebra Done Right. For the next edition, I will add an exercise to show that the result is tight (there is some speculation in a comment above that the result is not tight). Specifically, this will be the additional exercise: Suppose $e_1, \dots, e_n$ is an orthonormal list in an inner product space $V$. Show that there is a list $v_1, \dots, v_n$ in $V$ such that $|e_j - v_j| \le \frac{1}{\sqrt{n}}$ but $v_1, \dots, v_n$ is not linearly independent. – Sheldon Axler Sep 27 '15 at 02:23
  • @SheldonAxler Your exercise is quite popular on this site, I could find 8 instances! The additional exercise you mention is a good supplementation to it. There's a quite symmetrical showcase for any fixed $n$, developed in my answer around here. Would be great to receive your feedback. – Hanno Jan 25 '19 at 23:09
0

This scribble is split in two: The first half answers the OP, while $(2)$ offers a general symmetrical example to demonstrate that the assumptions cannot be relaxed from $\,$"$<$"$\,$ to $\,$"$\leq\,$".

$\mathbf{(1)}\:\;$ It is shown that $L\in\mathscr L(V)$, defined by $Le_j =v_j\,$ for $1\leqslant j\leqslant n$, is injective. Then $\{v_1,\ldots,v_n\}\subset V$ is linear independent, hence a basis.

Pick any $\,x=\sum_{j=1}^nx_je_j\in V$. Now a trio of inequalities, namely triangle, Cauchy-Bunyakovsky-Schwarz, and the assumed ones, implies $$\begin{align} \|x\|_2 & \:=\: \left\|\,Lx + \sum\nolimits_{j=1}^nx_j(\mathbb 1 -L)e_j\right\|_2\\[2ex] &\:\leqslant\:\|Lx\|_2\: +\: \sum\nolimits_{j=1}^n|x_j|\cdot\|e_j -Le_j\|_2\\[2ex] &\:\leqslant\:\|Lx\|_2\: +\: \left(\sum\nolimits_{j=1}^n|x_j|^2\right)^{1/2} \underbrace{\left(\sum\nolimits_{j=1}^n\|e_j -v_j\|^2\right)^{1/2}}_ {\qquad\;\displaystyle =c<1} \end{align}$$ Thus $\,\|Lx\|_2\geqslant(1-c)\,\|x\|_2\;\forall x\in V$, proving injectivity of $L\,$.

$\mathbf{(2)}\:\;$ There is an orthogonal projector $P\in\mathscr L(V)$ of rank $\,n-1\,$ such that the $v_j:=Pe_j$ fulfill $\,\|e_j-v_j\|=\tfrac{1}{\sqrt n}$ for all $j\,$. But $\{v_1,v_2,\ldots,v_n\}\subset \operatorname{Im}P\,$ is certainly linear dependent.

Let $\,e=\sum_{j=1}^ne_j\,$ and $\,E=\operatorname{span}\{e\}\,$. The announced $P=P_{E^\perp}$ is the orthogonal projector onto $E^\perp\subset V\,$, and $\,\dim E^\perp=n-1$. We have $$P_{E^\perp}\:=\;\mathbb 1-P_E\;=\;\mathbb 1-\frac1n(\,\cdot\mid e)\,e\,,$$ and setting $\,v_j=P_{E^\perp}(e_j)\,$ gives $$\,\|e_j-v_j\|_2\;=\;\big\|(\mathbb 1 -P_{E^\perp})\,e_j\big\|_2\;=\;\frac1n \|e\|_2 \;=\;\frac{1}{\sqrt n}\quad\forall\:j=1,\ldots,n\,.$$

Hanno
  • 6,302