Prove that $\min_\limits{x\in\{-1,1\}^n} \lVert Ax\rVert_\infty≤ C\sqrt{n\log(n)}$ I’m struggling a lot since few hours on this exercice and I really have no idea how to make the log appears.
The problem is the following:
Let $A$ be a matrix of size $n\times n$ whose entries $a_{ij}$ are such that $\left|a_{ij}\right|\leqslant1$.
Prove that there exists $C>0$ a constant that doesn’t depend on $n$ such that:
$\min_\limits{x\in\{-1;1\}^n}$ $\lVert Ax\rVert_{\infty}\leqslant C\sqrt{n\log(n)}$
I did a lot of exercises dealing with inequalities of matrix norm but I really have no idea for this one.
I learnt about Jensen inequality but it led me nowhere.
Thanks in advance for any kind of help.
 A: Idea: use the probabilistic method.
Namely, come up with some distribution $D$ over $\{-1,1\}^n$ such that
$$
\Pr_{x\sim D}[\|Ax\|_\infty > C\sqrt{n\log n}]
 < 1$$
for some $C>0$. This implies there exists a realization $x^\ast$ for which the inequality  $\|Ax^\ast\|_\infty \leq  C\sqrt{n\log n}$ holds.
Moreover, to show that $
\Pr_{x\sim D}[\|Ax\|_\infty > C\sqrt{n\log n}]
 < 1$, by a union bound it is enough to show that $
\Pr_{x\sim D}[(Ax)_i  > C\sqrt{n\log n}]
 < \frac{1}{n}$ for every fixed choice $i$ of coordinate. (Can you see why?)
More details:  a natural candidate for $D$ is just the uniform distribution on $\{-1,1\}^n$, i.e., the coordinates of $x$ are i.i.d. Rademacher. Then, by a Hoeffding bound, for every fixed $1\leq i\leq n$ and every $t>0$,
$$
\mathbb{E}[(Ax)_i] = 0, \qquad \Pr[ |(Ax)_i| > t] \leq e^{-\frac{t^2}{2n}}
$$
and so, for any $t > \sqrt{2n\ln n}$, we get that, for any fixed $1\leq i\leq n$
$$
\Pr[ |(Ax)_i| > t] < \frac{1}{n}
$$
By a union bound over all $n$ coordinates, this gives
$$
\Pr[\|Ax\|_\infty > t] = \Pr[ \forall 1\leq i \leq n,\, |(Ax)_i| > t] < 1
$$
and you can conclude. (For instance, $C=\sqrt{2.1}$ works.)
