Question

Please prove the following lemma by showing that if M > N, then there is a non-zero vector x such that Cx = Ax = 0:

lemma: Let W = {w^1,...,w^N} be a spanning set for a subspace S in R^I, and let {v^1,...,v^M} be a linearly independent subset of S. then M <= N.

Answer 1

Since $W$ is the spanning set for the subspace $S$, every vector from the set $V = \{v^1, v^2, \dots, v^M\}$ is expressed as linear combination of vectors from the set $W$.

$$v^i = c_1^i w^1 + c_2^i w^2 + \dots + c_N^i w^N$$

Since all the vectors $v^i$ are independent all the vector coefficients

$$c^i = (c_1^i, c_2^i, \dots, c_N^i)$$

are independent.

So we have $M$ linearly independent vectors $c^i$, each of dimension $N$.

Suppose $M > N$. Then any $N$ of $M$ vectors $c^i$ form a basis of $R^N$. Then remaining $M - N$ vectors $C_i$ are expressed via the basis vectors $c^i$ which contradicts to linear independency of $c^i$. Thus $M \leq N$ and the statement is proved.