Let $f:[n]\times [n] \rightarrow [0,1]$ be a function from pair of integers to the real interval [0.1]. I would like to find sets of complex vectors $X= \{x_i\}$ and $Y=\{y_j\}$ satisfying $x_i\cdot y_j=f(i,j)$, in such a way that the vectors in $X$ and in $Y$ are as small as possible. More precisely, set $m= max_{i,j} f(i,j)$ and $N=max_{i,j}[\|x_i\|,\|y_j\|]$.

1) What is the minimal $N$ such that $x_i\cdot y_j = f(i,j)$ for all $i,j\in [n]$?

2) Is there an upper bound on $N$ purely in function of $m$, i.e., with no depenence on $n$?

3) If the answer to question two is no, what is the best upper bound that we can give for $N$ in function of $n$ and $m$? A trivial upper bound is $$N \leq \max_i{\sum_{j} f(i,j) } \leq mn.$$

but I believe that the dependence on $n$ might be lowered.



  • $\begingroup$ Why do you believe such vectors exist? $f(0,1)=f(1, 0)=1, f(0,0)=f(1, 1)=0$, for example. $\endgroup$ – Daniel Litt Jul 9 '10 at 15:59
  • 2
    $\begingroup$ Daniel, I thought this was the snag at first, but I believe Mateus is asking for sequences of vectors $x_1,\ldots,y_1,\ldots$ such that $x_i\cdot y_j=f(i,j)$, that is in effect matrices $X$ and $Y$ with $XY^t=F$ (where $F$ is the function $f$ seen as a matrix). So in your example we can take $x_1=y_2=(1,0)$ and $x_2=y_1=(0,1)$. $\endgroup$ – Robin Chapman Jul 9 '10 at 16:07
  • $\begingroup$ Ah I see; must have misread. $\endgroup$ – Daniel Litt Jul 9 '10 at 16:11
  • $\begingroup$ Thanks Robin for clarifying Daniel's question. Thanks also Mike for your answer. Unfortunately an SDP doesn't help too much in here. I'm really interested in some analytical upper or lower bound on N. Even a non-constructive bound would be very welcome. $\endgroup$ – Mateus de Oliveira Jul 9 '10 at 18:59
  • 2
    $\begingroup$ This question raises the notion of "factoring an operator through $\ell_2$." You may want to consider references on the Pietsch factorization theorem and Grothendiek's inequality. $\endgroup$ – Mike McCoy Jul 9 '10 at 19:55

Such questions have been dealt with. Note first that your $m$ is just the norm of the matrix $F$ (see Robin's comment) as an operator from $\ell_1^n$ to $\ell_\infty^n$. $M$ also has a name, it is the $\gamma_2$ norm of this operator (This is the minimal product of $$\|Y\|_{1\to 2}\|X\|_{2\to\infty}$$ over all factorizations $F=XY$ . $\|Z\|_{p\to q}$ denotes the norm of Z as an operator from $\ell_p$ to $\ell_q$.) It is not hard to see that $M=\gamma_2(F)\le \sqrt n \|F\|_{1\to\infty}=\sqrt n m$. For a random $0,1$ matrix $F$ one gets that this estimate is tight, up to a universal constant. You can look here http://www.springerlink.com/content/px2324p527n19xj2/ for details. In particular Cor 5.2 there (it deals with random $\pm 1$ matrices but it is easy to go between those and random $0,1$ matrices).

| cite | improve this answer | |
  • 1
    $\begingroup$ Back ticks are what you need around some math expressions to make them display correctly, Gideon, so I changed your single quotes to back ticks. $\endgroup$ – Bill Johnson Jul 9 '10 at 23:11
  • $\begingroup$ Hi Gideon, thank you very much for your comment, and for pointing out the reference which I partially read and found very interesting. However I might be missing something. Your $M$ (which I call $N$) seems to be $\min_{XY}\{max_{ij}\|x_i\| \|y_j\|\}$. However in the question I made, the maximum is not over the product of the norms $\|x_i\|\|y_j\|$. Instead in the def. of $N$, I consider the largest line of $X$ and the largest column of $Y$, and take the largest between the two. More precisely, I should have written $\max\{\max_i{x_i}; \max_j{y_j}\}$. Any clue? $\endgroup$ – Mateus de Oliveira Jul 10 '10 at 0:52
  • 1
    $\begingroup$ Mateus, you are right but it is easy to go between my $M$ and your $N$ (for the minimal representation). $M=N^2$. (Note that for the $i,j$ for which the max is attained in $N$ one has $\|x_i\|=\|y_j\|$). So $N= M^{1/2}\le n^{1/4}m^{1/2}$. and the random example shows that this is best possible, up to a universal constant. I hope it's OK now. $\endgroup$ – Gideon Schechtman Jul 10 '10 at 4:44
  • $\begingroup$ Thank you very much Gideon for the great answer! It will help me a lot in proving a lemma in which I was stuck. $\endgroup$ – Mateus de Oliveira Jul 10 '10 at 15:54

This is a partial answer; I'm not sure it will be useful to you. I don't see any analytic expression for (1), but if we restrict ourselves to real vectors and the Euclidean norm, you can compute $N$ using a semidefinite program. Consider the problem

$$\text{minimize } \max_{i,j} \{(W_1)_{ii}, (W_2)_{jj}\} \quad \text{subject to } \begin{bmatrix}W_1& F \newline F' & W_2 \end{bmatrix} \succeq 0, $$

where as in Robin's comment, $F$ is the matrix version of $f$. To compute $x_i$, $y_j$ after finding the optimal matrices $W_1, W_2$, one simply needs to take the Cholesky factorization

$$ \begin{bmatrix} X \newline Y \end{bmatrix} \begin{bmatrix} X^t & Y^t \end{bmatrix} = \begin{bmatrix}W_1& F \newline F' & W_2 \end{bmatrix}, $$

and take the corresponding rows of $X$ and $Y$ as your vectors $x_i, y_j$. Note that the optimal value of this program is $N^2$ (when restricted to real vectors). It is also trivially an upper bound on $N^2$ when considering complex vectors.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.