# Find shortest vectors $u_1,v_1,\cdots,u_N,v_N$ such that $\langle u_i,v_j\rangle=1$ if $i\le j$ and $\langle u_i,v_j\rangle=0$ if $i>j$

The following problem has come up in my work. Any help would be appreciated.

Problem. Given $$N \in \mathbb{N}$$, find vectors $$u_1, u_2, \cdots, u_N, v_1, v_2, \cdots, v_N \in \mathbb{R}^d$$ which satisfy $$\forall i,j \in \{1, 2, \cdots, N\} ~~~~~~~~~~ \langle u_i, v_j \rangle = \left\{ \begin{array}{cl} 1 & \text{if } i \leq j \\ 0 & \text{if } i > j \end{array} \right.$$ and which minimize $$A := \max_{i,j \in \{1, 2, \cdots, N\}} \|u_i\|_2 \cdot \|v_j\|_2.$$ Let $$A_*(N)$$ denote the optimal value of $$A$$ for a given value of $$N$$.

I'm mainly interested in the asymptotic behavior of $$A_*(N)$$ as $$N \to \infty$$. I don't care what $$d$$ is.

(EDIT: To be clear, $$A_*(N)$$ is defined to be the infimum -- taken over all $$d \in \mathbb{N}$$ and all $$u_1, \cdots, u_N, v_1, \cdots, v_N \in \mathbb{R}^d$$ satisfying the constraint -- of the objective $$A$$. That is, I place no constraint on $$d$$.

Note that $$d$$ must depend on $$N$$; in particular, $$d \geq N$$ is necessary for the constraint to be satisfiable.

However, without loss of generality, $$d = 2N$$: If $$d<2N$$, we can add superfluous dimensions. If $$d>2N$$, then we can project the solution to the space spanned by $$\{u_1, \cdots, u_N, v_1, \cdots, v_N\}$$, which has dimension at most $$2N$$.)

Question. What is $$A_*(N)$$? In particular, what is $$c_* := \limsup_{N \to \infty} \frac{\log A_*(N)}{\log \log N}~~~?$$

The value $$c_*$$ is what I really want to know, as it governs the asymptotics. i.e. $$A_*(N) \approx (\log N)^{c_*}$$.

I can prove $$0 \leq c_* \leq 1$$. Any improved bounds (such as showing $$c_*>0$$ or showing $$c_*<1$$) would be really helpful.

By Cauchy-Schwartz, $$A_*(N) \geq \|u_1\|_2 \cdot \|v_1\|_2 \geq \langle u_1, v_1 \rangle = 1$$ and, hence, $$c_* \geq 0$$, but I have no nontrivial lower bound.

The obvious upper bound is to let $$u_1, \cdots, u_N$$ be the standard basis vectors and then let $$v_j = \sum_{i=1}^j u_i$$. Unfortunately, this only shows $$A_*(N)\leq\sqrt{N}$$; we can do better:

The following inductive construction shows $$A_*(N) \leq \lceil \log_2 N \rceil + 1$$ and, hence, $$c_* \leq 1$$.

We will construct a solution for powers of $$2$$ i.e. $$N=2^n$$ with $$n \in \mathbb{N}$$. The solution we construct will be denoted $$u_1^n, \cdots, u_{2^n}^n, v_1^n, \cdots, v_{2^n}^n \in \mathbb{R}^{2^{n+1}-1}$$.

The base case is $$u_1^0 = v_1^0 = (1)$$. For $$n \geq 1$$ and $$1 \leq i \leq 2^{n-1}$$, define $$u_i^{n} = \left( \begin{array}{c} 1 \\ u_i^{n-1} \\ 0^{2^{n}-1} \end{array} \right), ~~~~~~~~ u_{2^{n-1}+i}^{n} = \left( \begin{array}{c} 0 \\ 0^{2^{n}-1} \\ u_i^{n-1} \end{array} \right), ~~~~~~~~ v_i^{n} = \left( \begin{array}{c} 0 \\ v_i^{n-1} \\ 0^{2^{n}-1} \end{array} \right), ~~~~~~~~ v_{2^{n-1}+i}^{n} = \left( \begin{array}{c} 1 \\ 0^{2^{n}-1} \\ v_i^{n-1} \end{array} \right),$$ where $$0^m \in \mathbb{R}^m$$ denotes the $$m$$-dimensional zero vector.

It is easy to verify inductively that this construction satisfies the constraint and achieves $$\|u_i^n\|_2 \leq \sqrt{n+1}$$ and $$\|v_i^n\|_2 \leq \sqrt{n+1}$$ for $$1 \leq i \leq 2^n$$, as required to show $$A_*(2^n)\leq n+1$$.

Clearly, $$A_*$$ is an increasing function. Hence $$A_*(N) \leq A_*\left(2^{\lceil \log_2 N \rceil}\right) \leq \lceil \log_2 N \rceil +1$$ for all $$N \in \mathbb{N}$$, as desired.

• Why is this tagged as [order-theory]? Commented Dec 16, 2016 at 23:42
• It asks about encoding the order relation $i \leq j$ as an inner product. (One could ask a more general question about encoding any relation this way.) I don't know what good tags for this are -- suggestions are appreciated. Commented Dec 16, 2016 at 23:45
• This problem doesn't seem that well defined to me? You say you don't care about $d$ but surely your answer will depend on it. In your example, $d$ increases with $N$, were as if we treated $d$ as a constant then it seems to me that $A_*(N)$ would eventually level out. In fact, if $d=1$ then no such vectors exist for $N>1$. Commented Jan 13, 2017 at 16:09
• @LeonSot Without loss of generality $d \leq 2N$, as we can work in the subspace spanned by $\{u_1, \cdots, u_N, v_1, \cdots, v_N\}$. We also require $d \geq N$ to satisfy the constraints. By "I don't care what $d$ is", I simply mean that I don't want to add any restriction on $d$ that would make the problem harder. Commented Jan 13, 2017 at 19:35
• @LeonSot I edited the question to address your comment. Is it clearer now? Commented Jan 13, 2017 at 19:50

I will prove the lower bound $A_{\ast}(N) \geq \tfrac{1}{2 \pi} \log N$, within a constant factor of the OP's upper bound.

Let $A$ and $B$ be the matrices whose columns are $u_i$ and $v_i$. Let $S$ be the $N\times N$ matrix $$\begin{pmatrix} 1&1&1&1&1 \\ 0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&1&1 \\ 0&0&0&0&1 \end{pmatrix} .$$ So $S=A^T B$. Let the singular values of $A$, $B$ and $S$ be $\alpha_i$, $\beta_i$ and $\sigma_i$ respectively, with $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n \geq 0$ and likewise for the $\beta$'s and $\sigma$'s. We adopt the convention that $\alpha_M=\beta_M=\sigma_M=0$ for $M>N$.

We have $$\max |A_i|^2 \geq \frac{1}{N} \sum |A_i|^2 = \frac{1}{N} \mathrm{Tr}(A^T A) = \frac{1}{N} \sum \alpha_i^2$$ and similarly $$\max |B_j|^2 \geq \frac{1}{N} \sum \beta_j^2 .$$

So $$\max |A_i| |B_j| \geq \frac{1}{N} \left( \sum \alpha_i^2 \right)^{1/2} \left( \sum \beta_j^2 \right)^{1/2} \geq \frac{1}{N} \sum \alpha_i \beta_i$$ where the second inequality is Cauchy-Schwartz.

Now, the multiplicative version of Weyl's inequality says that $\alpha_i \beta_i \geq \sigma_{2i-1}$. I'm having trouble finding a reference for Weyl's inequality for singular values (as opposed to eigenvalues), especially with nonsquare matrices, so I may come back and write up the proof if you don't know/believe it. So $$\max |A_i| |B_j| \geq \frac{1}{N} \sum_{j \geq 1}^{\lfloor (N+1)/2 \rfloor} \sigma_{2j-1}.$$

Now, here is the amazing fact -- we can actually compute the singular values of $S$ explicitly!

Lemma The singular values of $S$ are $$\sigma_k = \frac{1}{2 \sin \tfrac{(2k-1) \pi}{4N+2}}.$$

Proof: We note that $$S^{-1} = \begin{pmatrix} 1&-1&0&0&0 \\ 0&1&-1&0&0 \\ 0&0&1&-1&0 \\ 0&0&0&1&-1 \\ 0&0&0&0&1 \end{pmatrix}$$ has singular values $\sigma_k^{-1}$ and $$C:=S^{-T} S^{-1} = \begin{pmatrix} 1&-1&0&0&0 \\ -1&2&-1&0&0 \\ 0&-1&2&-1&0 \\ 0&0&-1&2&-1 \\ 0&0&0&-1&2 \end{pmatrix}$$ has eigenvalues $\sigma_k^{-2}$, so it suffices to show that the eigenvalues of $C$ are $4 \sin^2 \tfrac{(2k-1) \pi}{4N+2} = 2-2 \cos \tfrac{(2k-1) \pi}{2N+1}$. Writing $\phi_N(\lambda)$ for the characteristic polynomial of $C$, we have $$\phi_N(\lambda) = (\lambda-2) \phi_{N-1}(\lambda) - \phi_{N-2}(\lambda)$$ which is the appropriately shifted version of the recursion for Chebyshev polynomials. $\square$

So, we have $$\max |A_i| |B_j| \geq \frac{1}{N} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{1}{2 \sin \tfrac{(4j-3) \pi}{4N+2}}.$$ Bounding $\sin x < x$, this is $$\geq \frac{4N+2}{2 \pi N} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{1}{4j-3} > \frac{1}{2\pi} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{2}{2j-3/2}.$$ We can view the last sum as a Riemann sum for $\int_{x=1}^N \tfrac{dx}{x}$, over rectangles of width $2$. I didn't write down the proof of this carefully, but the Riemman sums appear greater than the integral, and in any case are only off by $O(1)$, so we finally conclude $$\max |A_i| |B_j| > \frac{1}{2 \pi} \log N$$ as promised.

• Thanks to Thomas for a really challenging problem! Commented Jan 19, 2017 at 15:47
• Wow! Thank you for this. I will need to take some time to digest it (and read up on Weyl inequalities). Commented Jan 20, 2017 at 18:39
• @DavidESpeyer, advising that myself and a few co-authors included the argument above (crediting this post of course, and filling in some details / references) in a recent paper, see appendix C. Commented Feb 21, 2022 at 21:36
• @KeithRush Thanks for letting me know! Commented Feb 21, 2022 at 22:57