Is this lemma in elementary linear algebra new?

This is a nice lemma: I know a good deal of similar results but this one is unknown to me.

I believe it is suitable, as an answer, to give a proof that works with no restriction on the cardinality of the underlying field $F$. I will frame the answer in terms of matrix spaces. Thus, we have a linear subspace $V \subset M_{n,p}(F)$ such that, for every non-zero vector $X \in F^n$, the space $V$ contains a rank $1$ matrix with column space $F X$ and, for every non-zero vector $Y \in F^p$, the space $V$ contains a rank $1$ matrix with row space $F Y^t$. Note that those assumptions are unchanged in multiplying $V$ by invertible matrices (be it on the left or on the right).

The proof works by induction on $p$. The case where $p=1$ or $n=1$ is obvious. Assume now that $p>1$ and $n>1$. The discussion is split into two cases, where the standard basis of $F^p$ is denoted by $(e_1,\dots,e_p)$.

Case 1: $V e_p=F^n$. Then, one writes every matrix $M$ of $V$ as $M=\begin{bmatrix} A(M) & C(M) \end{bmatrix}$ where $A(M) \in M_{n,p-1}(F)$ and $C(M) \in F^n$. With our assumptions, we find rank $1$ matrices $M_1,\dots,M_{p-1}$ in $V$ with respective row spaces $F e_1^t,\dots,F e_{p-1}^t$. Then, $M_1,\dots,M_{p-1}$ are linearly independent and all belong to the kernel of $V \ni M \mapsto C(M)$. Using the rank theorem, one deduces that $\dim V \geq (p-1)+\dim C(V)=(p-1)+n$.

Case 2 : $V e_p \subsetneq F^n$. Multiplying $V$ on the left by a well-chosen invertible matrix, we lose no generality in assuming that $V e_p \subset F^{n-1} \times \{0\}$. In other words, every matrix $M$ of $V$ may be written as $$M=\begin{bmatrix} A(M) & C(M) \\ R(M) & 0 \end{bmatrix}$$ where $A(M)$ is an $(n-1) \times (p-1)$ matrix, $R(M)$ is a row matrix and $C(M)$ is a column matrix. Then, we note that $A(V)$ satisfies the same set of assumptions as $V$: indeed, if we take a non-zero row $L \in M_{1,p-1}(F)$, then we know that $V$ contains a rank $1$ matrix $M_1$ whose row space is spanned by $\begin{bmatrix} L & 1 \end{bmatrix}$. Obviously the last row of $M_1$ is zero whence $A(M_1)$ is non-zero and its row space is included in $F L$. One works likewise to obtain the remaining part of the condition. Thus, by induction one finds $$\dim A(V) \geq (n-1)+(p-1)-1.$$ Finally, we know that $V$ must contain a non-zero matrix $M_2$ with $A(M_2)=0$ and $C(M_2)=0$, and that it must contain a non-zero matrix $M_3$ with $A(M_3)=0$ and $R(M_3)=0$. Obviously, $M_2$ and $M_3$ are linearly independent vectors in the kernel of $V \ni M \mapsto A(M)$. Using the rank theorem, one concludes that $$\dim V \geq 2+\dim A(V) \geq 2+(n-1)+(p-1)-1=n+p-1.$$

As suggested by Martin, there is a geometric interpretation of this lemma. Though the proof is probably not shorter than the one proposed by Clément. Nevertheless, this is the kind of very classical reasonning one encouters in the study of secant varieties.

Let us put $a = dim A$ and $b = dim B$. If $a \otimes b \in A \otimes B$, I denote its image in $\mathbb{P}(A \otimes B)$ by $[a \otimes b]$.

I denote by $X_{A,B} = \{(a,b), \textrm{such that} [a \otimes b] \in \mathbb{P}(V) \}$. This is clearly equal to the scheme $(\mathbb{P}(A) \times \mathbb{P}(B)) \cap \mathbb{P}(V)$ (I'll consider only schemes with reduced structure here).

Let us consider the natural projections $p_A : X_{A,B} \longrightarrow \mathbb{P}(A)$ and $p_B : X_{A,B} \longrightarrow B$. The hypothesis given by the OP show that $p_A$ and $p_B$ are surjective. Denote by $\gamma_A$ the dimension of the generic fiber of $p_A$, by $\gamma_B$ the dimension of the generic fiber of $p_B$, by $X_A$ a maximal dimensional irreducible component of the scheme $p_A^{-1}(p_A(X_{A,B}))$ and by $X_B$ a maximal dimensional irreducible component of the scheme $p_B^{-1}(p_B(X_{A,B}))$.

The theorem of the dimension gives $dim \ X_A = a-1 + \gamma_A$ and $dim \ X_B =b-1 + \gamma_B$.

The secant variety $S(X_A,X_B)$ (that is the closure of variety of lines joining a point of $X_A$ and a point of $X_B$) is included in $\mathbb{P}(V)$ and the goal will be to bound below its dimension to get a bound for $dim \ \mathbb{P}(V)$.

The dimension of $S(X_A,X_B)$ is equal to $\dim \ X_A + \dim \ X_B +1 - \delta$, where $\delta$ is the secant defect of $S(X_A,X_B)$. Concretely, if $M$ is a generic point of $S(X_A,X_B)$, then $\delta$ is the dimension of the scheme:

$$\{[a_1 \otimes b_1] \in X_A, \ \textrm{s.t. $\exists [a_2 \otimes b_2] \in X_B$ and $(x,y) \in \mathbb{k}^2$ with $M = x.a_1\otimes b_1 + y.a_2 \otimes b_2$} \}.$$

It is well known that the secant defect of $S(\mathbb{P}(A) \times \mathbb{P}(B),\mathbb{P}(A) \times \mathbb{P}(B))$ is $2$. Indeed, the parameter family to decompose a rank $2$ matrix as a sum of two rank $1$ matrices is $\mathbb{P}^1 \times \mathbb{P}^1$. (short explanation : as one only needs to construct one of these rank $1$ matrices : choose the image (choice of a $\mathbb{k}^1$ in the image of the rank $2$ matrix, which is isomorphic to $\mathbb{k}^2$) and choose a hyperplane containing the kernel of the rank $2$ matrix).

Assume that $S(X_A,X_B)$ consists only of rank $1$ matrices. Since $X_A$ surjects onto $A$ and $X_B$ surjects onto $B$, we easily deduce that $X_A = \mathbb{P}(A) \times b_0$ and $X_B = a_0 \times \mathbb{P}(B)$ for some $a_0$ and $b_0$ fixed. The dimension of $S(X_A,X_B)$ is then obviously seen to be $a-1+b-1-0 = a+b-2$ and then we have $dim \ \mathbb{P}(V) \geq a+b-2$.

Assume that the $S(X_A,X_B)$ contains a matrix of rank $2$. Then, the generic $M \in S(X_A,X_B)$ has rank $2$. Since $X_A \subset \mathbb{P}(A) \times \mathbb{P}(B)$, $X_B \subset \mathbb{P}(A) \times \mathbb{P}(B)$ and the secant defect of $S(\mathbb{P}(A) \times \mathbb{P}(B),\mathbb{P}(A) \times \mathbb{P}(B))$ is $2$, we deduce that $\delta \leq 2$. As a consequence,

$$dim \ S(X_A,X_B) \geq a-1 + \gamma_A + b-1 + \gamma_B +1 - \delta \geq a+b-3.$$

If $\delta \leq 1$, then we get in fact:

$$dim \ S(X_A,X_B) \geq a-1 + \gamma_A + b-1 + \gamma_B-1 \geq a+b-2,$$ and this implies that $dim \ \mathbb{P}(V) \geq a+b-2$, which is what we wanted.

If $\delta = 2$, then the dimension of $$\{[a_1 \otimes b_1] \in X_A, \ \textrm{s.t. $\exists [a_2 \otimes b_2] \in X_B$ and $(x,y) \in \mathbb{k}^2$ with $M = x.a_1\otimes b_1 + y.a_2 \otimes b_2$} \}$$ is $2$. In view of the explicit decomposition of a rank $2$ matrix as the sum of two rank $1$ matrices, this implies that for every $a$ in $\mathbb{P}(A)$, there is at least a $\mathbb{P}^1$ of $b \in \mathbb{P}(B)$ such that $[a \otimes b] \in X_A$. We deduce that $\gamma_A \geq 1$ and finally:

$$\dim S(X_A,X_B) \geq a-1+1 +b-1 + 1 -2 = a+b-2,$$

which again implies $dim \ \mathbb{P}(V) \geq a+b-2$.