Let ${\bf f}:U\to \mathbb R^{n-k}$ be a continuously differentiable function. Then ${\bf f}^{-1}(0)$ is a manifold if $[{\bf D}{\bf f}(x)]$ is surjective at all $x$. This is equivalent to the condition that $[{\bf D}{\bf f}(x)]\neq 0$ for all $x\in M$.
Given an $M$ described in this way, is it always possible to find an ${\bf f}$ such that $\{\nabla f_1,\dots,\nabla f_{n-k}\}$ is a linearly independent set of partial derivatives?
The answer is that the partial derivatives will certainly not always be independent, but the gradients will be. This since the gradients will form the rows of the matrix (in order to satisfy the surjectivity condition the matrix $[{\bf D f}]$ must be a wide matrix with full row rank. The partials form the columns of this matrix, and the gradients form the rows. The conclusion follows.
[Note that my statement that the set of gradients was a linearly independent set of partial derivatives is nonsense.]