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

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.

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

$$(e_i - v_i)\cdot(e_i - v_i) = \|e_i - v_i\|^2 < \frac1n,$$ $$|(e_i - v_i)\cdot(e_j - v_j)| \le \|e_i - v_i\|\cdot\|e_j - v_j\| < \frac1n.$$

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$).

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

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

1. Draw this picture:

2. Draw this picture:

3. 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.