Are all $n\times n$ invertible matrices change-of-coordinates matrices in $\mathbb{R}^n$? More precisely, I'm trying to prove the following problem:
Assume that $\text{Span}\{\vec{v}_{1},\dots,\vec{v}_{k}\}=\mathbb{R}^{n}$
  and that A
  is an invertible matrix. Prove that $\text{Span}\{A\vec{v}_{1},\dots,A\vec{v}_{k}\}=\mathbb{R}^{n}$.
but I think I need the lemma in the title. I find it difficult to prove without large amounts of handwaving. Is the proposition in the title true, and if so, how to prove it?

Yes, but what you're trying to prove is essentially a lemma towards that fact.
Towards the question you've been asked, note that if $\mathrm{Span}\{\vec v_1,\ldots,\vec v_k\}=\mathbb R^n$ then some subset of $\{\vec v_1,\ldots,\vec v_k\}$ is a basis for $\mathbb R^n$, say $\{\vec v_1,\ldots,\vec v_n\}$. Suppose $\text{Span}\{A\vec{v}_{1},\dots,A\vec{v}_{k}\}\neq\mathbb{R}^{n}$. Then
$\text{Span}\{A\vec{v}_{1},\dots,A\vec{v}_{n}\}\neq\mathbb{R}^{n}$, so $\{A\vec v_1,\ldots,A\vec v_n\}$ must not be linearly independent. Thus we have some $c_1,\ldots,c_n\in \mathbb R$ not all $0$ such that $c_1A\vec v_1+\cdots+c_nA\vec v_n=0$, thus $A(c_1\vec v_1+\cdots+c_n\vec v_n)=0$. But since $A$ is invertible this gives us $c_1\vec v_1+\cdots+c_n\vec v_n=0$, contradicting the fact that $\{\vec v_1,\ldots,\vec v_n\}$ is a basis. Thus $\text{Span}\{A\vec{v}_{1},\dots,A\vec{v}_{k}\}=\mathbb{R}^{n}$ after all.
