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$

Solution 1:

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.