prove that $k\leq 2n$ when $v_1,\cdots, v_k$ are nonzero vectors in $\mathbb{R}^n$ so that $v_i^T v_j\leq 0$ for $i\neq j$

Question

Prove that $k\leq 2n$ when $v_1,\cdots, v_k$ are nonzero vectors in $\mathbb{R}^n$ so that $v_i^T v_j\leq 0$ for $i\neq j$.

For $n=1,$ clearly there can be at most 2 vectors $v_i$, one positive and one negative. For $n=2,$ write $v_i= (a_i,b_i)$ for each i. Then $a_i a_j + b_i b_j \leq 0$ for all $i\neq j$. I think one can show that there are at most 4 possible vectors in this case by observing that each of the two entries of each vector can be nonnegative or negative, but I'm not sure about the details. As an example, one can consider the vectors $(1,2), (2,-1),(-1,-2),(-2,1).$

It seems that it could be useful to induct on n, but I'm not sure how to show the inductive step. Specifically, assume that the result holds for some $n\ge 2$. We want to prove the result holds for $n+1$. Write each $v_i = (v_i', t_i)$ where $v_i' \in \mathbb{R}^n$. We know that $(v_i')^T v_j' + t_i t_j \leq 0$ for all $i\neq j.$ We want to get a contradiction if we assume that $k > 2n+2$.

Answer 1

This is essentially an extension of my answer here:
Let $ V $ be an Euclidian space of dimension $n$ and let $v_1,...,v_m \in V$ s.t. $\langle v_i,v_j \rangle<0$ for all $i\neq j$. Show $m \leq n + 1 $ this time using Perron-Frobenius theory to accomodate non-negative matrices instead of Perron theory.

Let $G\in \mathbb R^{k \times k}$ be the associated Gram Matrix, i.e. $g_{i,j}=\langle v_i, v_j\rangle$, where I assume the $v_i$ have been rescaled by a positive number to have length 1 and the inner product this time is the dot product so $G=V^TV\succeq \mathbf 0$. We can observe that
$\text{rank }G =\text{rank }\big(V^TV\big) = \text{rank }\big(V\big)=\text{rank }\left(\bigg[\begin{array}{c|c|c|c|c|c|c} v_1 & v_2&\cdots & v_k \end{array}\bigg]\right)\leq \dim \mathbb R^n=n$

Now suppose for contradiction that $n\lt \frac{k}{2}$
$ \implies \text{rank }G\leq n\lt \frac{k}{2}\implies \frac{k}{2}\lt \dim \ker G$ (rank nullity).

Write $G= 2I-M$ where $M$ is a non-negative matrix in the Perron-Frobenius theory sense and has all $1$'s on the diagonal. Let $\lambda_i$ be the eigenvalues of $M$. Since $G$ is real symmetric PSD we know $2 -\lambda_i\geq 0$ for all $i$ and if $\lambda_i = 2$ it is a Perron root, the sole one for a given irreducible (communicating class) of $M$.

Now $\frac{k}{2}\lt \dim \ker G$ so there are strictly more than $\frac{k}{2}$ of these $\lambda_i = 2$ hence strictly more than $\frac{k}{2}$ associated irreducibles in $M$. But if each irreducible was at least a $2\times 2$ matrix then $M$ would be bigger than a $k\times k$ matrix (impossible). Conclude that there is some $r$th irreducible with Perron (eigen) value of $2$ that is a $1\times 1$ matrix i.e. it is just a diagonal entry necessarily $=1$ hence we have $1=\lambda_r =2$ and that is a contradiction.

---

example of meeting the inequality with equality
It can be helpful to consider an explicit example of $\frac{k}{2}=n$. Let $n$ be even and $v_1 = -v_2 = \mathbf e_1$, and $v_3 = -v_4 = \mathbf e_2 $ and so on. Then $G$ is block diagonal and each block is a $2\times 2$ matrix given by $\begin{bmatrix}1& -1 \\ -1 &1\end{bmatrix}$. In turn $M$ is block diagonal where each block (irreducible) is a $2\times 2$ matrix given by $\begin{bmatrix}1& 1 \\ 1 &1\end{bmatrix}$.