It is an easy fact that for a matrix $A \in M_n(\mathbb C)$, the matrix $A' = (|A(i,j)|)_{i,j \leq n}$ has a larger operator norm than $A$. By operator norm I mean the norm as an operator on $\ell^2_n$, or equivalently its largest singular value.

My question is:

What happens when the operator norm is replaced by the Schatten $p$-norm?

Let me recall that for $1 \leq p \leq \infty$ and a matrix $A \in M_n(\mathbb C)$, its Schatten $p$-norm $\|A\|_p$ is the $\ell^p$-norm of its singular values, or equivalently $\|A\|_p= Tr((A^*A)^{p/2})^{1/p}$ if $p<\infty$. If $p=\infty$, this is just the operator norm.

Some remarks:

  • If $p=2$ the equality $\|A\|_2 =\|A'\|_2$ is obvious.
  • If $p$ is an even integer, the inequality $\|A\|_p \leq \|A'\|_p$ holds (just expand $\|A\|_p^p = Tr( (A^*A)^{p/2})$ and use the triangle inequality to prove that $\|A\|_p^p \leq \|A'\|_p^p$).
  • When $A$ is a complex Hadamard matrix (a unitary with all entries having absolute value $1/\sqrt n$), $\|A\|_p < \|A'\|_p$ for $p>2$ and $\|A\|_p> \|A'\|_p$ for $p<2$: indeed, $p$-norm of $A$ is $n^{1/p}$ and the $p$-norm of $A'$ is $\sqrt n$. A naive guess would be that these inequalities always hold, BUT:
  • When $p<6$ and $p \neq 2,4$, the quantities $\|A\|_p$ and $\|A'\|_p$ are not comparable (with constants independant of $n$). For $p<4$, take $A=\begin{pmatrix} 1 & -1 & 0\\ 0 & 1 & 1 \\ 1 & 0 & 1\end{pmatrix}$, and for$4<p<6$ take $A = \begin{pmatrix} 0 & 1&1 & 0\\ 1&0 & 1 & 0 \\ 1 & 0&0 & -1\\0&1&0&1\end{pmatrix}$.

So the question is really for $p>6$. For example, I could not find any matrix $A$ such that $\|A\|_7 > \|A'\|_7$.

Update I was informed by Gilles Pisier that this question has already been considered. This question has been first answered by V. Peller, and the answer was refined successively by B. Simon, M. Dechamps-Gondim, F. Lust-Piquard and H. Queffélec and L. Rosen. The counterexamples given in DLQ are the same as the ones I give in my answer, with a slightly different proof.

  • 2
    $\begingroup$ In the case of circulant matrices, the question is essentially that of the sharp Hardy-Littlewood majorant conjecture, which Hardy and Littlewood already knew to be false. It is also false if one allows the loss of a multiplicative constant, see ams.org/mathscinet-getitem?mr=2488338 . $\endgroup$ – Terry Tao Oct 3 '12 at 6:53
  • $\begingroup$ Thanks Terry for your interesting comment. I guess that your argument is similar to the one given by Peller (although I did not have access to it). However Peller, instead of refering to Hardy Littlewood, mentions a paper by Boas ams.org/mathscinet-getitem?mr=149175 . In the mathscinet review of this paper, it is claimed that Hardy and Littlewood only had a proof for $p=3$. $\endgroup$ – Mikael de la Salle Oct 3 '12 at 7:56
  • $\begingroup$ In fact my previous comment is a bit wrong: Peller's argument seems to be more involved that the one you give. Your argument is exactly the one given by Barry Simon in the link mentioned above. $\endgroup$ – Mikael de la Salle Oct 3 '12 at 8:02
  • $\begingroup$ I think the version that does hold is the following: $\|AA^*\| \le \|A′(A′)^T\|$ for any unitarily invariant norm.... $\endgroup$ – Suvrit Oct 3 '12 at 8:16
  • $\begingroup$ @Suvrit: what do you mean? the $\| \cdot \|_{p/2}$-norm is unitarily invariant, and we discovered that there are plenty of proofs that show that this inequality is false if $p/2$ is not an integer! $\endgroup$ – Mikael de la Salle Oct 3 '12 at 8:24

Let me answer my own question by contructing, for $p>2$ not an even integer (say $2k<p<2k+2$), a matrix $A$ such that $\|A\|_p> \|A'\|_p$. In fact I construct a family of matrices $A_n \in M_n(\mathbb C)$ such that $\|A_n\|_p > \|A_n'\|_p$ whenever $n-k$ is an even positive integer, and $\|A_n\|_p < \|A'_n\|_p$ if $n-k$ is an odd positive integer$.

This will imply that $\|A\|_p \leq \|A'\|_p$ for all $n$ and all $A \in M_n$ if and only if $p$ is an even integer or $p=\infty$. For other values of $p$, these two quantities are not comparable, and if we go the the Schatten classes (ie we allow infinite matrices), there is no implication between the properties $\|A\|_p<\infty$ and $\|A'\|_p<\infty$.

Here is the construction. For every integer $n$, consider $S_n \in M_n(\mathbb C)$ to be the matrix of a cyclic permutation of $\{{1,\dots,n\}}$ in which one of the $1$'s is replaced by a $-1$. Take $A_n=Id+S_n$, so that $A_n'=Id+S_n'$. I only sketch the proof that $A_n$ works, since I might be the only one interested ;).

There are two independent claims:

Claim 1: the function $p \mapsto \|A_n\|_p^p - \|A_n'\|_p^p$ has at most $n-1$ zeros (counting multiplicities).

Claim 2: $\|A_n\|_p = \|A_n'\|_p$ for all even integers $2 \leq p \leq 2n-2$.

These two claims together imply that $\|A_n\|_p^p -\|A_n'\|_p^p$ is non zero outside of $\{{2,4,\dots,2n-2\}}$ and changes signs at each of these values of $p$. Since it is negative for $p=2n$, we have the announced properties.

The second claim is easier. A first observation is that $Tr(S_n^k) = Tr({S'_n}^k)$ for every $k$ with $-n+1 \leq k \leq n-1$: $k=0$ is obvious, and if $k \neq 0$ both matrices have a zero diagonal. Hence, since $A_n^* A_n = 2+S_n +S_n^*$ and ${A'_n}^* A'_n = 2+ S'_n +{S'_n}^{*}$ we have $\|A_n\|_p = \|A_n'\|_p$ for all even integers $p \leq 2n-2$.

To prove the first claim, first notice that the eigenvalues of $S'_n$ (resp. $S_n$) are $\lambda_k=\exp(2ki\pi/n)$, $k=1\dots n$ (resp. $ \mu_k=\exp( (2k+1) i \pi/n)$, $k=1\dots n$). Thus the singular values of $A'_n$ (resp. $A_n$) are $|1+\lambda_k|$ (resp. $|1+\mu_k|$). In particular if $N(B)$ denotes the number of distinct non-zero singular values of a matrix $B$, we have $N(A_n)+N(A'_n)=n$. Hence $\|A_n\|_p^p - \|A_n'\|_p^p$ can be written in the form $\sum_{j=1}^n \alpha_j e^{\beta_j p}$, and such a function cannot have more than $n-1$ zeros unless it is identically zero.

  • $\begingroup$ I edited just to prove that someone else was interested. :) $\endgroup$ – Bill Johnson Sep 27 '12 at 21:22
  • 2
    $\begingroup$ +1: Mikael, I'm always interested in anything that you say on MO! $\endgroup$ – Suvrit Sep 28 '12 at 7:40

Mikael's explicit construction is extremely nice. Here's an ugly numerical example for those who like matlab based counterexamples.

This problem turned out to be quite hard to defeat numerically by brute force, which is a common characteristic of many singular value inequalities. I tried slightly more structured matrices, and am tempted to believe that I have found computational counterexamples.

Here's the brute-force construction.

m=gallery('tridiag', b*ones(n,1), a*ones(n+1,1), c*ones(n,1));
m(n,1)=-2;   % this additional entry is important.
lhs = norm(svd(m),p);
rhs = norm(svd(abs(m)),p);

Now, if you loop over the above random "almost" tridiagonal matrices, Matlab quickly reports a counterexample where "lhs" is bigger than "rhs" (I tried $n=9$ and $p=7$).

  • 3
    $\begingroup$ In fact I also found the counterexamples with the help of a computer: I first looked at matrices with entries in $\{{-1,0,1\}}$. I then realized that all the counterexamples produced this way had exactly 2 nonzero entries on each row and column. I therefore looked at matrices of the form $1_n+P$ for a permutation matrix $P$ with signs, and realized that these were counterexamples when $P'$ was of order $n$. The only thing that remained was to find a proof. $\endgroup$ – Mikael de la Salle Oct 1 '12 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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