# Can the number of columns be less than the dimension? I don't see how $$k < m$$ can possibly occur in part (b).

Imagine $$X \in R^{n, k}$$ describes a matrix for the vectors $$x^1$$ to $$x^K$$.

$$m = \dim( span(S)) \leq \min(n,k)$$

Then if $$k < m$$ in part (b), then $$k < m \leq \min(n,k)$$. This inequality chain is impossible.

Imagine n = 100, k = 10.

Then, $$10 < m \leq \min(100, 10)$$

$$10 < m \leq 10$$

m cannot be equal to 10, because $$10 < 10$$ is impossible, and m cannot be less than 10, because $$10 < m < 10$$ is impossible.

What's going on?

• You are confusing $k$ with $K$. Your $X \in R^{n, K}$ and $m \leq \min(n,K)$, while $k$ can be anything. Even $1$ if you just take the first vector, or $0$ if you take none. – Conifold Sep 16 at 5:27
• @Conifold The proof is not complete to me. Why is it not possible that you must take linear combinations of $x_1, ..., x_K$ to generate the basis of size m? Why are we guaranteed to be able to just pick from $x_K$ without any linear combinations? – user3180 Sep 16 at 7:12
• Because, by induction, you can pick $m$ linearly independent vectors by adding $m-k$ from the remaining ones. And any $m$ linearly independent vectors in a subspace of dimension $m$ are its basis. – Conifold Sep 16 at 7:42
• I agree the problem might be the confusion between $k, K$. This is very bad pedagogy... – iarbel84 Sep 16 at 8:47