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 dependence
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



Inner products and norms
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](https://doi.org/10.1007/s00493-007-2160-5) 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).


