Some estimates on tensor norms

Question

Denote $M_n$ to be $n\times n$ matrix. For $X\in M_n$ define $\|X\|_1:=\max\limits_{1\leq j\leq n}\sum_{i=1}^n|x_{ij}|$ and $\|B\|_2:=\max\{|\sum_{i,j=1}^nb_{ij}x_iy_j|:|x_i|=|y_j|=1,\ 1\leq i,j\leq n\}.$ Denote $C(n):=\sup\{\sum_{i,k=1}^n|\sum_{j=1}^nx_{kj}b_{ij}|:\|(x_{kj})\|_1\leq 1,\ \|(b_{ij})\|_2\leq 1\}$. Is $\lim\limits_{n\to\infty}C(n)<\infty$?

Answer 1

The answer is no. Let $B=(b_{ij}\colon i\in J_n,\;j\in J_n)$, where \begin{equation} b_{kj}:=\frac1n\sqrt{\frac2n}\cos\frac{2\pi kj}n \end{equation} for $k$ and $j$ in $J_n:=\{0,\dots,n-1\}$; it will be more convenient for us to use the index set $J_n$ instead of $[n]:=\{1,\dots,n\}$. Using Euler's formula $\cos t=\frac12\,(e^{it}+e^{-it})$, it is straightforward to check that the matrix $nB$ is orthogonal. Here are these calculations in Mathematica:

Hence, \begin{equation} \Big|\sum_{i,j=0}^{n-1}b_{ij}x_iy_j\Big|=|x^T By|\le\|x\|_2\|By\|_2 =\frac1n\,\|x\|_2\|y\|_2=1 \end{equation} if $|x_i|=|y_j|=1$ for all $i,j\in J_n$. So, $\|B\|_2\le1$. Let $X=(x_{ij}\colon i\in J_n,\;j\in J_n)$ with $x_{ij}=1(i=j)$, so that $\|X\|_1=1$.

However, \begin{equation} \sum_{i,k\in J_n}^n\Big|\sum_{j\in J_n}x_{kj}b_{ij}\Big| =\sum_{i,k\in J_n}|b_{ik}| =\frac1n\sqrt{\frac2n}\sum_{j,k\in J_n}\Big|\cos\frac{2\pi kj}n\Big|\ge c\sqrt n \tag{1} \end{equation} for some universal real constant $c>0$ and all natural $n$. So, your $C(n)$ goes to $\infty$.

---

Details on the inequality in (1): Let $P_n$ denote the set of all pairs $(k,j)\in J_n^2$ such that the fractional part of $\dfrac{kj}n$ is in the interval $[0,1/6]$. Take any natural $n\ge100$, any natural $k\in[n/24,n/12]$, and any integer $m\in[0,(n-5)/24]$. Then the interval $\Big[\dfrac{mn}k,\dfrac{(m+1/6)n}k\Big]$ is of length $n/(6k)\ge2$ and contained in the interval $[0,n-1]$. So, there is some $j_{k,m}\in J_n\cap\Big[\dfrac{mn}k,\dfrac{(m+1/6)n}k\Big]$, and then \begin{equation} \dfrac{kj_{k,m}}n\in[m,m+1/6], \tag{2} \end{equation} so that $(k,j_{k,m})\in P_n$. Moreover, by (2), for any given natural $n$ and $k$, the values of $j_{k,m}$ are distinct for distinct values of $m$. Each of the intervals $[n/24,n/12]$ (for the values of $k$) and $[0,(n-5)/24]$ (for the values of $m$) contains $\sim n/24$ integers (as $n\to\infty$). It follows that the cardinality $|P_n|$ of the set $P_n$ is $\gtrsim(n/24)^2$. So, \begin{equation} \sum_{j,k\in J_n}\Big|\cos\frac{2\pi kj}n\Big| \ge\sum_{(k,j)\in P_n}\cos\frac{2\pi kj}n\gtrsim(n/24)^2/2, \end{equation} since $\cos\dfrac{2\pi kj}n\ge1/2$ for all $(k,j)\in P_n$.

Thus, the inequality in (1) follows.