# Is this lemma in elementary linear algebra new?

Is anyone familiar with the following, or anything close to it?

Lemma. Suppose $A$, $B$ are nonzero finite-dimensional vector spaces over an infinite field $k$, and $V$ a subspace of $A\otimes_k B$ such that

(1) For every nonzero $a\in A$ there exists nonzero $b\in B$ such that $a\otimes b\in V$,

and likewise,

(2) For every nonzero $b\in B$ there exists nonzero $a\in A$ such that $a\otimes b\in V$.

Then

(3) $\dim_k(V) \geq \dim_k(A) + \dim_k(B) - 1$.

Remarks: The idea of (1) and (2) is that the spaces $A$ and $B$ are minimal for "supporting" $V$; that is, if we replace $A$ or $B$ by any proper homomorphic image, and we map $A\otimes B$ in the obvious way into the new tensor product, then that map will not be one-one on $V$. The result is equivalent to saying that if one is given a finite-dimensional subspace $V$ of a tensor product $A\otimes B$ of arbitrary vector spaces, then one can replace $A$, $B$ by images whose dimensions sum to $\leq \dim(V) + 1$ without hurting $V$.

In the lemma as stated, if we take for $A$ a dual space $C^*$, and interpret $A\otimes B$ as $\mathrm{Hom}(C,B)$, then the hypothesis again means that $C$ and $B$ are minimal as spaces "supporting" $V$, now as a subspace of $\mathrm{Hom}(C,B)$; namely, that restricting to any proper subspace of $C$, or mapping onto any proper homomorphic image of $B$, will reduce the dimension of $V$.

In the statement of the lemma, where I assumed $k$ infinite, I really only need its cardinality to be at least the larger of $\dim_k A$ and $\dim_k B$.

The proof is harder than I would have thought; my write-up is 3.3K. I will be happy to show it if the result is new.

• Welcome to Mathoverflow! – user6976 Sep 5 '13 at 21:09
• I don't have time to think about this right now, but it seems strikingly familiar to the following theorem of Hopf. If $f:A \otimes B\to C$ is a linear map which is injective on each factor separately, then $\dim f(A\otimes B) \geq \dim A + \dim B - 1.$ However, this theorem is true over $\mathbb{C}$ but false over $\mathbb{R}$ (the proof is given by algebraic topology), so maybe it is only a superficial observation. – Jack Huizenga Sep 6 '13 at 0:50
• This feels like a statement from projective geometry. $\mathbb{P}(V) \subseteq \mathbb{P}(A \otimes B)$ somehow "intersects enough" $\mathbb{P}(A) \times \mathbb{P}(B)$ so that $\dim(\mathbb{P}(V)) \geq \dim(\mathbb{P}(A) \times \mathbb{P}(B))$. – Martin Brandenburg Sep 6 '13 at 1:23
• Probably also related: Flanders' theorem (§8.3 in Prasolov's Linear Algebra book www2.math.su.se/~mleites/Prasolov/prasLinAlg/pr-linAlg-main.dvi ). – darij grinberg Sep 6 '13 at 2:30
• Somehow it feels that the following "dual" result is very closely related, and could for some fields also yield your inequality (by splitting the tensor product into "separable" and "joint" spaces, whose dimensions add up to $d_Ad_B$): On the maximal dimension of a completely entangled subspace..." by K. Parathasarathy; ias.ac.in/mathsci/vol114/nov2004/Pm2342.pdf --- in particular, your subspaces have the "separable" state property, while the cited paper considers "full entangled" subspaces. – Suvrit Sep 6 '13 at 15:04

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.$$

• This is a nice proof. Although it seems to be algebraic, I think it is geometric in disguise. Perhaps someone can formulate this proof coordinate-free, and/or in terms of the the intersection of $\mathbb{P}(V) \subseteq \mathbb{P}(A \otimes B)$ with $\mathbb{P}(A) \times \mathbb{P}(B) \hookrightarrow \mathbb{P}(A \otimes B)$? – Martin Brandenburg Sep 6 '13 at 19:20

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$$.