# Understanding a proof: A set of $m$ orthonormal vectors in $V$, with $m < \operatorname{dim}V$, is not complete.

I read the following proof that in a vector space $V$ of dimension $n$, a set of orthonormal vectors $\{\phi_1, \ldots, \phi_m\}$, with $m<n$, is not complete :

Among the linear combinations $a_1\phi_1 +\cdots +\ a_m\phi_m$, there cannot be $n>m$ linearly independent ones. Hence there must exist, by the fact that there are at most $n$ linearly independent vectors in $V$, an element $f$ which differs from all $a_1\phi_1 +\cdots + a_m\phi_m$, i.e. for which $\psi = f - a_1\phi_1 -\cdots - a_m\phi_m$ is always different from $0$.

(The proof goes on to show that by setting each $a_i$ to $(f,\phi_i)$, we get a non-zero $\psi$ that's orthogonal to all $\phi_i$, and so $\{\phi_1, \ldots, \phi_m\}$ is incomplete.)

I have trouble understanding the part in the quote above, though. First, how can you show that among the linear combinations $a_1\phi_1 +\cdots +\ a_m\phi_m$, there cannot be $n>m$ linearly independent ones? And then, even if you show that, how does it follow from it and the fact that there are at most $n$ linearly independent vectors, that there's an $f$ different from all $a_1\phi_1 +\cdots + a_m\phi_m$?

(I've seen other proofs of this, but I would really like to understand this particular one).

-
Well $m<n$, so you can't have $n>m$ of them. Further, since there are fewer than $n$ linear independent vectors, you know you can extend any linearly independent set to a basis, so that's where $f$ comes from. – Ian Coley Dec 10 '13 at 8:00
You should remove "at most" from "by the fact that there are at most $n$ linearly independent vectors in $V$"; the arguments uses that there exists in fact a set of more than $m$ (rather than at most $n$) independent vectors in $V$. In fact any basis of$~V$ (with exactly $n$ elements) will do as such a set. – Marc van Leeuwen Jun 18 '14 at 7:00

As $\{\phi_1, \dots, \phi_m\}$ is linearly independent, $\operatorname{span}\{\phi_1, \dots, \phi_m\}$ has dimension $m$. If $\psi_1, \dots, \psi_n \in \operatorname{span}\{\phi_1, \dots, \phi_m\}$ with $n > m$, then $\operatorname{span}\{\psi_1, \dots, \psi_n\} \subseteq \operatorname{span}\{\phi_1, \dots, \phi_m\}$ so the dimension of $\operatorname{span}\{\psi_1, \dots, \psi_n\}$ is at most $m$. If $\{\psi_1, \dots, \psi_n\}$ was linearly independent then $\operatorname{span}\{\psi_1, \dots, \psi_n\}$ would have dimension $n > m$, but this is impossible.
In general, you can't have more than $m$ linearly independent vectors in an $m$-dimensional subspace. Also, you can't span an $m$-dimensional subspace with fewer than $m$ vectors.
For your second question, as $\operatorname{span}\{\phi_1, \dots, \phi_m\}$ has dimension $m$ and $V$ has dimension $n > m$, $\operatorname{span}\{\phi_1, \dots, \phi_m\} \subset V$; therefore, $V \setminus\operatorname{span}\{\phi_1, \dots, \phi_m\}$ is non-empty. Now any element $f \in V \setminus\operatorname{span}\{\phi_1, \dots, \phi_m\}$ satisfies the desired conditions. To see this, note that if $f - a_1\phi_1 - \dots - a_m\phi_m = 0$, then $f = a_1\phi_1 + \dots + a_m\phi_m \in \operatorname{span}\{\phi_1, \dots, \phi_m\}$ but this is impossible because $f \in V \setminus\operatorname{span}\{\phi_1, \dots, \phi_m\}$.