# Prove that $k \ge n$

Let $S = \{v_1, .., v_k\}$ be a set in $\mathbb{R}^n$ where $v_1, .. v_k$ are vectors. Prove that if $\text{span } S = \mathbb{R}^n$ then $k \ge n$.

We are essentially doing $c_1v_1 + .. + c_kv_k = b$, where $b$ is a vector in $\mathbb{R}^n$ and $c_1, .. , c_k \in \mathbb{R}$.

By one of the theorems, it follows that $\text{rank } A = n$, where $A$ is the coefficient matrix $[v_1, v_2, .. v_k]$

I know the system contains $k - \text{rank }A = k - n$ free variables

But there must be $0$ free variables, then isn't $k = n$?

• The linear span of $k$ vectors has dimension at most $k$ while $\mathbb{R}^n$ has dimension $n$. Here, you can think of dimension as the smallest cardinality of a family spanning a linear space. – heptagon Feb 5 '17 at 7:59
• @heptagon, not allowed to use dimension – Amad27 Feb 5 '17 at 8:03
• Why do you think there must be 0 free variables? – Sungjin Kim Feb 5 '17 at 8:09
• @i707107, each vector has a unique representation in the span doesnt it? – Amad27 Feb 5 '17 at 8:13
• @Amad27 That is not true in general. Only true if $k=n$. – Sungjin Kim Feb 5 '17 at 8:30