1
$\begingroup$

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$?

$\endgroup$
2
  • 4
    $\begingroup$ Why did you delete the previous question? It is a disincentive to help people out with queries if the only response is for the question to get deleted without acknowledgement $\endgroup$
    – Yemon Choi
    May 17, 2021 at 13:35
  • $\begingroup$ @ Choi. Sorry for that. I'll redelete them. $\endgroup$ May 27, 2021 at 8:56

1 Answer 1

2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
6
  • $\begingroup$ The matrix $nB$ is not orthogonal. $\endgroup$ Jun 29, 2021 at 13:23
  • 1
    $\begingroup$ @Abeginnermathmatician : It is orthogonal. I have added details on that. $\endgroup$ Jun 29, 2021 at 13:45
  • $\begingroup$ Is there some direct formula from where I can deduce this? I cam see that the matrix you wrote down is real pat of DFT matrix which is unitary. $\endgroup$ Jun 29, 2021 at 13:47
  • 1
    $\begingroup$ I think such sums can be found in handbooks such as Gradshteyn--Ryzhik. $\endgroup$ Jun 29, 2021 at 13:56
  • $\begingroup$ I have done the calculation. It is right. Your construction is quite ingenious! I had some probabilistic examples involving Bernoulli r.v.s . If one takes b_jk to be iid Bernoulli r.v.s with uniform probability distribution then one can work out that with huge probability we have the estimate on the ratio similar to yours. Getting such a concrete example is challenging. However, your example has the same oscillatory nature of Bernoulli r.v.s $\endgroup$ Jun 29, 2021 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.