Let $A_n$ be the following $n\times n$ matrix: $(A_n)_{i,j}= \frac{1}{\sqrt{n}}\omega_n^{i\cdot j}$ for all $0 \le i,j <n$, where $\omega_n=e^{\frac{2\pi i}{n}}$.
I want to understand how $A_n$ acts on the set $\{0,1\}^n \subseteq \mathbb{C}^n$ in the following specific sense:
- Let $f(n)= \max_{v\in\{0,1\}^n} |A_n( v)|_1$. What upper bounds on $f$ exist? What is its asymptotic behavior? Is there a general form for some $v\in \{0,1\}^n$ at which $f$ attains its maximum, or is relatively close to its maximum?
Here are more delicate questions:
- What can be said about $f(n,w):=\max_{v\in\{0,1\}^n, |v|_1=w} |A_n( v)|_1$?
- What can be said about $g(n,C):=2^{-n} \{v \in \{0,1\}^n \mid |A_n (v)|_1 \le C\}$?
For the $L_2$ norm these questions are much easier as $A_n$ is unitary and preserves the norm.