Show linear independence of a set of vectors close to an orthonormal basis

This is a question from Linear Algebra Done Right.

Suppose $e_1, \dots, e_n$ is an orthonormal basis of $V$ and $v_1, \dots, v_n$ are vectors in $V$ such that $$ \| e_j - v_j \| < \frac{1} {\sqrt{n}} $$ for each $j$. Prove that $v_1, \dots, v_n$ is a basis of $V$. I tried to show this if $V$ is a two dimensional space by contradiction. However, it seems too messy to use the same idea for a general case.

Does anyone have hints for this problem?

Solution 1:

Thanks to one of the students in my group, I actually solved it a few days ago. The idea is similar to one of the comments. I put my solution here since it is more on linear algebra side without touching matrix.

We prove by contradiction. Assume otherwise, i.e. the set $\{v_i\}$ is not a basis for $V$. Then there exits some $w \in V$, such that $\langle w, v_i\rangle = 0$ for every $i = 1, \dots, n$ where $w \neq 0$. Such $w$ can be chosen from the annihilator of $\text{span}\{v_1, \dots, v_n\}$. Since we know $\dim( \text{span}\{v_1, \dots, v_n\}) < n$, $w$ always exists. Then \begin{align*} \|e_i - v_i\|^2 \|w\|^2 &\ge | \langle e_i-v_i, w\rangle |^2 && (\text{Cauchy-Schwarz}) \\ &= | \langle e_i, w\rangle - \langle v_i, w\rangle |^2 \\ &= | \langle e_i, w\rangle|^2 \end{align*} Now summing over $i = 1, \dots, n$, we get \begin{align*} \sum_{i=1}^n \| e_i - v_i\|^2 \|w\|^2 &\ge \sum_{i=1}^n (\langle e_i, w\rangle)^2 \\ &= \|w\|^2 \end{align*} This implies $\sum_{i=1}^n \|e_i - v_i\|^2 \ge 1$. On the other hand, by assumption, $\sum_{i=1}^n \|e_i-v_i\|^2 < 1$. This is a contradiction.

Hence, $\{v_1, \dots, v_n\}$ must be a basis.

Solution 2:

Define $V$ as a matrix whose columns are $v_i$, taken componentwise in the $e$-basis, and a matrix $Δ = I - V$. Then the elements of $Δ^TΔ$ are of the form of scalar products between all pairs of $(e_i - v_i)$, about which we know that

That's interesting so let's use it!

We know our matrix $Δ^TΔ$ has elements which are never $\frac1n$ or more, and want to prove that $I-Δ$ is regular. A contradiction would be to find a normalized vector $x$ such that

$$x = Δ x.$$

If such vector exists then $x^TΔ^TΔx = \|Δx\|^2 = \|x\|^2 = 1$. Now proceed as

$$1 = \sum_{j,k}|x_j(Δ^TΔ)_{jk}x_k| \le \sum_{jk} |x_j| |(Δ^TΔ)_{jk}| |x_k| < \frac1n \sum_{jk} |x_j| |x_k|$$

(here I used triangle inequality and the fact we know about elements of $Δ^TΔ$, notice the strict $<$ between the two latter terms),

$$\frac1n \sum_{jk} |x_j| |x_k| = n\left(\frac{\sum_j |x_j|}{n}\right)^2 \le n \frac{\sum_j |x_j|^2}{n}$$

(inequality between arithmetic and quadratic mean, probably Cauchy-Schwartz if you rephrase it in a clever way), thus

$$1 < \sum_j |x_j|^2 = 1.$$

That's a contradiction, so that's our proof done. It also shows that the bound is tight: for $\|e_j - v_j\| \le 1/\sqrt n$ you could find a counterexample which saturates each of the $≤$'s (namely, $(e_j - v_j)_k = 1/n, \forall j \forall k$).

Solution 3:

Though if you want a neater proof...* ;-)

*) but don't try that at an exam.

Draw this picture:

enter image description here

Draw this picture:

enter image description here

Generalize.

How it works

The $n$ vectors are linearly independent (and thus form a base) if there's no hyperplane that contains them all. If we draw an $n$-ball about the tip of each of the basis vectors, we mark all possible points that are compatible with the deviation $\|e_j - v_j\| < r$ (or $≤$, depending on whether we include the surface) from the elements of the orthonormal base, $e_j$. The hyperplane defined by the equation

$$\sum_j x_j = 0$$

has the property that for any other hyperplane the distance of at least one of the centers will be equal of higher (the equal ones are those which put a minus in front of some of the coordinates). Therefore it's the optimal candidate for one containing an overlap with all the spheres. If there's no overlap, any $n$-tuple of vectors pointing somewhere one into each of the spheres will be linearly independent.

The distance of each of the centers from this hyperplane is then the upper bound on the radius we can allow without breaking the guarantee of linear independence, and can be easily computed to be $1/\sqrt n$ by any suitable algebraic method.

Solution 4:

Let $a_i \in \mathbb{F}$ such that $\sum_{i=1}^n a_i v_i = 0$. Then we have

$$ 0 = \left \| \sum_{i=1}^n a_i v_i \right \| = \left \| \sum_{i=1}^n a_i (e_i + (v_i - e_i)) \right \| = \left \| \sum_{i=1}^n a_i e_i + \sum_{i=1}^n a_i (v_i - e_i) \right \| \geq \left| \left \| \sum_{i=1}^n a_i e_i \right \| - \left \| \sum_{i=1}^n a_i (v_i - e_i) \right \|\right| $$

which implies that

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

If $a_i \neq 0$ for some $1 \leq i \leq n$ then using Cauchy-Schwartz we have

$$ \sum_{i=1}^n |a_i| \| v_i - e_i \| < \sum_{i=1}^n |a_i| \frac{1}{\sqrt{n}} \leq \left( \sum_{i=1}^n |a_i|^2 \right)^{\frac{1}{2}} \left( \sum_{i=1}^n \frac{1}{n} \right)^{\frac{1}{2}} = \left( \sum_{i=1}^n |a_i|^2 \right)^{\frac{1}{2}}$$

and we have arrived to a contradiction.

Solution 5:

Associate to each list $u = (u_1, \dots, u_n)$ of $n$ vectors in $V$ a linear map \begin{align*} T_u : \mathbb C^n &\to V \\ T_ua &= a_1 u_1 + \cdots + a_n u_n. \end{align*} By the definition of linear independence, $u$ is linearly independent iff $T_u a \neq 0$ for all $a \neq 0$. The idea is, for $a \neq 0$, to bound the distance $T_v a$ from $0$ by (1) bounding it's distance from $T_e a$, and (2) bounding the distance from $T_e a$ to $0$, to show that $\|T_v a - 0\| > 0$, hence $T_v a \neq 0$. Since $a$ was arbitrary, it follows that $v$ is linearly independent, and since $v$ has $n = \dim V$ vectors, it's a basis.

For (1) we use the given condition and the triangle inequality: $$ \|T_e a - T_v a\| = \left\| \sum_{i=1}^n a_i e_i - \sum_{i=1}^n a_i v_i \right\| \leq \sum_{i=1}^n |a_i| \|e_i - v_i\| < \frac{1}{\sqrt{n}} \| a \|_1. $$

For (2), $$ \|T_e a - 0 \| = \left\| \sum_{i=1}^n a_i e_i \right\| = \sqrt{|a_1|^2 + \cdots + |a_n|^2} = \|a\|_2 $$ by the Pythagorean theorem.

It's a consequence of Cauchy-Schwarz that $\frac{1}{\sqrt{n}} \|a\|_1 \leq \|a\|_2$: $$ \|a\|_1 = \langle (|a_1|, \dots, |a_n|), (1, \dots, 1) \rangle \leq \|(|a_1|, \dots, |a_n|)\|_2 \|(1, \dots, 1)\|_2 = \|a\|_2 \sqrt{n}. $$ Then by the reverse triangle inequality $\|u - w\| \geq \big| \|u\| - \|w\| \big|$, it follows that $T_v a$ is a positive distance from $0$: $$ 0 \leq \|a\|_2 - \frac{1}{\sqrt{n}} \|a\|_1 < \|Te_a - 0\| - \|T_e a - T_v a\| \leq \|T_v a - 0\|. $$

In fact, my answer to Regarding linear independence on a normed-linear space given a condition proves essentially the same result with more of a topology/analysis bent.