Why, if we have more columns than rows, can the columns not be linearly independent?
Why, if we have more columns than rows, can the columns not be linearly independent?
For example, suppose I have a set of vectors $\{ v_1, v_2, v_3, v_4\}$, $\forall v_i \in \mathbb{R}^3$.
Your question is related to the dimension of a vector space. There are a few fundamental facts about this concept, such as:
If $V$ is a finite-dimensional vector space, and $U\subset V$ is a subspace, then $\dim U\leq\dim V$.
A set of $n$ linearly independent vectors spans an $n$-dimensional vector space.
Combining these two facts yields the desired proof.
If $n$ is the dimension of your vector space, then any set of vectors which contains strictly more than $n$ elements cannot possibly be linearly independent.
Proof
Denote by $(e_1,\ldots,e_n)$ the standard basis of $\mathbb R^n$ and suppose that $(f_1,\ldots,f_{n+1})$ is linearly independent. We can write $$f_1=\sum_{k=1}^n a_k e_k$$ and since $f_1\ne 0$, $\exists a_k\ne 0$ and WLOG suppose $a_1\neq0$ then $$e_1=\frac{1}{a_1}\left(f_1-\sum_{k=2}^n a_k e_k\right)$$ hence we see that $(f_1,e_2,\ldots,e_n)$ spans $\mathbb R^n$.
Now repeat the same method $n-1$ more times and we find that$(f_1,\ldots,f_{n})$ spans $\mathbb R^n$ so the vector $f_{n+1}$ is a linear combination of the other vectors $f_i$ which is a contradiction.
I'm not great with math proofs or the notation on this site, but here's (hopefully) a more intuitive way to think about it.
For vectors to be linearly independent (Wikipedia article) we have this:
A set of vectors is said to be linearly dependent if one of the vectors in the set can be defined as a linear combination of the other vectors. If no vector in the set can be written in this way, then the vectors are said to be linearly independent.
Let's try making some vectors that aren't dependent on one another.
Let's define $v_x$ = <1, 0, 0> - That is, the unit vector going in the direction of the x axis(this doesn't have to be a unit vector, but unit vectors are fun so that's what I'm using). Then we also define $v_y$ = <0, 1, 0>, and $v_z$ = <0, 0, 1>.
Note: $v_y$ and $v_z$ cannot be defined in terms of $v_x$ or each other - all three of these vectors are independent.
We've essentially defined the three axes we all know and love for $\mathbb{R}^3$. So, the question is, how will you define $v_w = <a, b, c>$ such that a, b, and c can't be made of some combination of $v_x, v_y, v_z$ - and you'll find that you can't do that. No matter how you define $v_w$, you will be defining it in terms of $v_x, v_y, v_z$. Eg. $v_w = <0.5, 0.1, 0.2>$ = 0.5$v_x$ + 0.1$v_y$ + 0.2$v_z$
Since $v_w$ can be defined in terms of the other vectors, it is dependent.
You can do this for other vector spaces too, it doesn't matter how large they are. The key in an $\mathbb{R}^n$ vector space, is that you have $n$ directions you can move that are orthogonal to each other. Once you have a vector describing each orthogonal direction, you can't make another vector that isn't somehow dependent on the vectors you already have.
The number of rows is the dimension of the vector space. (This is actually a not-so-trivial theorem.) The dimension, in turn, is the maximum number of linearly independent vectors a set can have. That proves what you are looking for.