# Why can't vectors $a_1, . . . , a_m$ be linearly independent in $\mathbb{R}^n$ if $m > n$

Fix vectors $a_1, . . . , a_m ∈ \mathbb{R}^n$, and let $S$ be the vector space of such that

$S:=$ {$x∈ \mathbb{R}^n:a_i⋅x=0∀1≤i≤m$} .

Vectors $a_1, . . . , a_m ∈ \mathbb{R}^n$ are linearly independent when for any real numbers $c_1, . . . , c_m$,

$\sum_{j=1}^m c_j a_j = 0 \Leftrightarrow c_i = 0 \mbox{ for all } i =1,\ldots,m.$

Now, I have already made some progress by proving that if $m < n$, then $S$ always contains a nonzero vector.

How could I show that any set $a_1, . . . , a_m$ cannot be linearly independent in $\mathbb{R}^n$ if $m > n$ ?

Going even further, could I claim that the equation $a · x = 0$ always has $n − 1$ linearly independent solutions for $x$, and if so, why?

• Is my question unclear? Or is it something I'm missing?
– Jimm
Commented Jan 22, 2016 at 21:30
• The first line is unclear. I'd write $S:=\{x\in \Bbb R ^n:a_i\cdot x=0\,\forall \, 1\le i\le m\}$. Commented Jan 22, 2016 at 21:33
– Jimm
Commented Jan 22, 2016 at 21:34
• Is your question "why is any set $\{a_1,\cdots, a_m\}$ is linearly depedent if $m>n$" or is it "why does the fact that $m<n$ then $S$ always contains a nonzero vector implies $a_1,\cdots,a_m$ is lin. dep?" Commented Jan 22, 2016 at 21:36
• The first one: Why is any set $a_1 ... a_m$ linearly dependent if $m >n$ ?
– Jimm
Commented Jan 22, 2016 at 21:37

I assume you have no prior knowledge on basis of finite dimensional vector spaces, as otherwise you wouldn't be troubled. First you might need this lemma:

(Steinitz Exchange Lemma, SEL): Let $V$ be a vector space (abbreviated v.s.) over $\mathbb{F}$ and $v_1,\cdots,v_n \in V$. Suppose $y\in V$ such that $y=a_1v_1 + \cdots + a_nv_n$ with $a_i\in \mathbb{F}$ with some $a_k\neq 0$. Then $$\text{Span}(v_1,\cdots,v_n)=\text{Span}(v_1,\cdots,v_{k-1},y,v_{k+1},\cdots,v_n)$$. That is, We can exchange $v_k$ with $y$ without changing Span.

Proof Just notice that $v_k=-(a_1v_1+\cdots+a_{k-1}v_{k-1}-y+\cdots a_nv_n)/a_k \in \text{Span}(v_1,\cdots,y,\cdots,v_n)$

Now consider $V=\mathbb{R}^n$. Let $I=(v_1,\cdots,v_m)$ be a linearly indept. set. Let $S=\{a_1,\cdots,a_n\}$ be a spanning set, i.e. $\text{Span}(S)=V$. We claim that $m\le n$.

Assume for a contradiction that $m>n$. Since $S$ is spanning, $v_1\in \text{Span}(S)$. So we can write

$$v_1=\lambda_1 a_1 + \cdots + \lambda_n a_n$$

and at least one $\lambda_k$ must be non zero, otherwise $v_1=0$ and any set containing $0$ cannot be linearly independent. After suitable relabelling if necessary, we may conclude $\lambda_1\neq 0$, and so by SEL

$$V=\text{Span}(S)=\text{Span}(v_1,a_2,\cdots,a_n)$$

We proceed similarly. We can find $\mu_1,\cdots,\mu_n$ such that

$$v_2=\mu_1 v_1 + \mu_2 a_2 +\cdots \mu_n a_n$$

Now at least one of $\mu_2,\mu_3,\cdots, \mu_n$ is nonzero, otherwise $v_2=\mu_1 v_1$ so $I$ is not linearly independent. Again, we may assume that $\mu_2\neq 0$ and thus we have

$$V=\text{Span}(v_1,v_2,a_3,\cdots,a_n)$$

The idea is that we can repeat this process indefinitely, and if $m>n$ then we'd eventually end up with

$$V=\text{Span}(v_1,\cdots,v_m)$$

and this implies that $v_{m+1}\in \text{Span}(v_1,\cdots,v_m)$, which contradicts the assumption that $I$ was linearly independent.

So $m \le n$.

Clearly, the set $\{e_k\in \mathbb{R}^n: 1\le k \le n\}$ where $e_k$ is unit orthonormal vectors in $\mathbb{R}^n$ is spanning, and so any independent set must have size $\le n$.

• Does this also imply that the equation $a⋅x=0$always has $n−1$ linearly independent solutions for $x$?
– Jimm
Commented Jan 23, 2016 at 0:23
• @Jimm I do not think this directly implies that $W=\{x\in \mathbb{R}^n:a\cdot x=0\}$ is $n-1$-dimensional. But in general, in any finite dimensional inner product space $V$ (which $\mathbb{R}^n$ is), given a subspace $W\subset V$ and the orthogonal complement $W^{\perp}=\{v\in V: v\cdot w=0 \forall w\in W\}$, $W\oplus W^{\perp}=V$. So in particular the solution space to $a\cdot x=0$ is an orthogonal complement of $\text{Span}(a)$, and we know $\dim(\text{Span}(a))=1$, so the solution space has dimension $n-1$ necessarily, which means there are $n-1$ solutions which are linearly independent. Commented Jan 23, 2016 at 2:54