12
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Why is this tagged as [order-theory]? $\endgroup$
    – Asaf Karagila
    Commented Dec 16, 2016 at 23:42
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Dec 16, 2016 at 23:45
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Leon Sot
    Commented Jan 13, 2017 at 16:09
  • $\begingroup$ @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. $\endgroup$
    – Thomas
    Commented Jan 13, 2017 at 19:35
  • $\begingroup$ @LeonSot I edited the question to address your comment. Is it clearer now? $\endgroup$
    – Thomas
    Commented Jan 13, 2017 at 19:50

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks to Thomas for a really challenging problem! $\endgroup$ Commented Jan 19, 2017 at 15:47
  • $\begingroup$ Wow! Thank you for this. I will need to take some time to digest it (and read up on Weyl inequalities). $\endgroup$
    – Thomas
    Commented Jan 20, 2017 at 18:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Keith Rush
    Commented Feb 21, 2022 at 21:36
  • $\begingroup$ @KeithRush Thanks for letting me know! $\endgroup$ Commented Feb 21, 2022 at 22:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .