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.

cordially,

mateus

vectors$x_1,\ldots,y_1,\ldots$ such that $x_i\cdot y_j=f(i,j)$, that is in effectmatrices$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)$. – Robin Chapman Jul 9 '10 at 16:07