Inner products and norms 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\|]$.

*

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


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


*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
 A: 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 Link 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).
A: 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.
