Upper bound for the rank of a Gram-type matrix

Question

Let $V = (v_{1},...,v_{N})$ and $W = (w_{1},...,w_{N})$ be 2 sets, each containing $N$ vectors from $\mathbb{R}^{n}$; i.e, $v_{j}, w_{j} \in \mathbb{R}^{n}$ for all $1 \leq j \leq N$. Assume that $N$ is (much) larger then $n$. We define their Gram matrix $A = (a_{jk})_{j,k=1}^{N}$ as $a_{jk} := \langle w_{j},v_{k} \rangle$. It is easy to verify that $rankA \leq n$; indeed, $A = CB$ where $C$'s rows are $W$ and $B$'s columns are $V$.

I am interested in the following, symmetric, gram-type matrix $D = (d_{jk})_{j,k=1}^{N}$, defined by $d_{j,k} = \langle w_{j},v_{k} \rangle $ for $j \geq k$ and $d_{j,k} = \langle w_{k}, v_{j} \rangle $ for $j < k$. Equivalently, $D$ is obtained from $A$ by deleting the upper-triangular half of $A$ and replacing it by the reflection of the lower triangular half, so that the resulting matrix is symmetric.

Can we find a useful upper bound on $rankD$? Preferably, independent of $N$, like in the classical Gram matrix?

Answer 1

The rank can be $N$, for any $n\ge 1$.

We can show this by induction on $N$. Let's take $n=1$, for convenience.

Of course, it is clear that $D$ can be non-singular for small $N$. For the induction step, notice that $D_{11}=v_1w_1$, and this is the only matrix element that contains $w_1$. So if we take $v_1=1$, say, then $\det D = w_1 (\det D' +o(1))$ as $w_1\to\infty$, where $D'$ denotes the matrix with the first row and column deleted. This is of the same type as $D$, so by the induction hypothesis, we can make $\det D'\not= 0$ by choosing $v_2,w_2,\ldots , v_N, w_N$ suitably.