On linearly independent matrices

I have been reading J.S. Milne's lecture notes on fields and Galois theory and came across the normal basis theorem (Thm 5.18 on page 66 of the notes). Trying to find my own proof, the following problem in linear algebra quickly arose:

Question: Let $F$ be a field. Given linearly independent matrices $A_1, \dots, A_n \in \operatorname{GL}_n(F)$, does there necessarily exist some $b\in F^n$ such that $A_1b, \dots, A_nb$ are linearly independent over $F$?

This is clearly not true if the matrices are not linearly independent. Also, if they are not invertible, the claim is false in general: e.g. set $n=2$ and consider

$$A_1 = \begin{pmatrix} 1 & 0 \\ 0& 0\end{pmatrix},\quad A_2 = \begin{pmatrix} 0 & 1 \\ 0& 0\end{pmatrix}$$

Going through a case-by-case analysis, I think I can prove the claim for $n=2$, so there seems to be some hope...

Any help would be appreciated. Thanks!

-
(I'm rambling here) In characteristic zero, let $c_1, c_2 \neq 0.$ Then $c_1 A_1 b + c_2 A_2 b = (c_1 A_1 + c_2 A_2) b.$ But $c_1 A_1 + c_2 A_2 \neq 0,$ and so $c_1 A_1 b + c_2 A_2 b$ is non-zero as long as $b$ is in the row space of $c_1 A_1 + c_2 A_2.$ Now if we can find $c_1, c_2$ such that $c_1 A_1 + c_2 A_2$ is non-singular, then there necessarily exists such $b$?? – user2468 Jul 31 '12 at 18:19
You have $A_1 \in GL_n(F)$ and $b \in F^n$. What multiplication are you using for $A_1b$? (I'm a random noob trying to understand the problem) – xavierm02 Jul 31 '12 at 18:48
@xavierm02: Just plain old matrix multiplication (identifying $F^n = F^{n\times 1}$) – Sam Jul 31 '12 at 18:51
Proof for $n = 2$: since the problem is invariant under left multiplication by an invertible matrix, you may assume WLOG that $A_1 = I$. If $A_2 b$ is always a scalar multiple of $b = A_1 b$, then it is not hard to show that $A_2$ must be a scalar multiple of the identity, but this contradicts the assumption of linear independence. – Qiaochu Yuan Jul 31 '12 at 19:35
@EdGorcenski: it's just "the" definition of linear independence in an arbitrary vector space. Linear independence is a property of a set of vectors (and, of course, the set of all matrices is a vector space) . – Martin Argerami Jul 31 '12 at 20:48

Consider, for $F=\mathbb{R}$, $n=3$, $$A_1=\begin{bmatrix}1&0&0\\0&1&0\\ 1&2&3\end{bmatrix}, \ A_2=\begin{bmatrix}1&0&0\\0&1&0\\ 2&3&1\end{bmatrix}, \ A_3=\begin{bmatrix}1&0&0\\0&1&0\\ 3&1&2\end{bmatrix}.$$ These three matrices are linearly independent, because the last three rows are. They are invertible, since the are triangular with nonzero diagonal.
For any $b=\begin{bmatrix}x\\ y\\ z\end{bmatrix}\in\mathbb{R}^3$, the three vectors we obtain are $$A_1b=\begin{bmatrix}x\\ y\\ x+2y+3z\end{bmatrix}, \ A_2b=\begin{bmatrix}x\\ y\\ 2x+3y+z\end{bmatrix}, \ A_3b=\begin{bmatrix}x\\ y\\ 3x+y+2z\end{bmatrix}. \$$ And for any choice of $x,y,z$, these vectors are linearly dependent. To see this, note that the three vectors are colinear. Or, more algebraically, we need to find coefficients, not all zero, such that $\alpha\,A_1b+\beta\,A_2b+\gamma\,A_3b=0$. The first two rows require $\alpha+\beta+\gamma=0$. And the third row requires $(x+2y+3x)\alpha+(2x+3y+z)\beta+(2x+y+2x)\gamma=0$. As it is a homogeneous system of two equations in three variables, it will always have nonzero solutions.
A tiny bit simpler: $$\pmatrix{1&0&0\cr0&1&0\cr1&0&1\cr},\pmatrix{1&0&0\cr0&1&0\cr0&1&1\cr},\pmatrix‌​{1&0&0\cr0&1&0\cr0&0&1\cr}$$ Then $yA_1b-xA_2b+(x-y)A_3b=0$ gives a non-trivial linear dependence unless $x=y=0$, in which case $A_1b-A_2b=0$. – Gerry Myerson Aug 1 '12 at 3:46