# How hard (P, NP, NP-hard) is it to compute Schur norms of matrices (as multipliers)?

Given a matrix $A\in M_n(\mathbb{C})$, I will denote by $||A||_\infty$ the operator norm of $A$, as seen acting on the Hilbert space $\mathbb{C}^n$. This makes $M_n(\mathbb{C})$ into a Banach space (actually a Banach algebra, actually a $C^*$ algebra).

We will define a new norm on $M_n(\mathbb{C})$ in the following way: A matrix $T$ acts on $M_n(\mathbb{C})$ by pointwise multiplication (i.e. Schur product), giving rise to an operator $M_T:M_n(\mathbb{C})\longrightarrow M_n(\mathbb{C})$. For example for

$$T=\left[\begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array}\right]$$ we have

$$M_T\left(\left[\begin{array}{cc} a & b \\ c & d \end{array}\right]\right)= \left[\begin{array}{cc} a & 2b \\ 3c & 4d \end{array}\right]$$

We will denote by $||T||_{Schur}$ the norm of the operator $M_T$, as an operator of the Banach space $M_n(\mathbb{C})$. How hard is it to compute/estimate this norm? Are there polynomial algorithms (in $n$ and the approximation error) that can do it? Is it actually NP?

• Wouldn't $||T||_{Shur}$ be just $max_{i,j}(t_{ij})$? – Michael Oct 26 '13 at 3:29
• I think it can be NP-Hard; I'll see if I can locate a more precise statement (on a side note: what would it mean for this problem to be in NP, could you make that precise?) – Suvrit Oct 26 '13 at 4:10
• See e.g., by the following paper: math.uwaterloo.ca/~krdavids/Preprints/DavDon_schur.pdf which says that calculation of this norm is often even "impossible"! – Suvrit Oct 26 '13 at 15:40

It turns out that this norm can be computed efficiently (i.e., it is in $P$). This wasn't known at the time that the Davidson paper (originally linked in a comment above) was written, which is why it suggests that the computation is hard.

To compute the norm, first use the equivalence of points (1) and (2) in Theorem 1.1 of the Davidson paper. This tells us that $\|T\|_{schur} = \|T\|_{cb}$, where $\|\cdot\|_{cb}$ refers to the "completely bounded" norm of $T$.

It was shown in "J. Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217-238, 2009" that the completely bounded norm can be computed efficiently via semidefinite programming.

For what it's worth, using this method tells me that the norm $\|\cdot\|_{schur}$ of the map stated in the question is $4$. However, this norm is not always equal to $\max_{i,j}\{t_{i,j}\}$. The simplest example I have been able to find to demonstrate this fact is $$T = \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix},$$ which has $\|T\|_{schur} = 2/\sqrt{3} > 1$.

Edit: Here is some (surprisingly simple) MATLAB code that computes this norm. You must first install CVX before running this code. Just modify the first line of code with whatever operator $T$ you want to compute the norm of.

T = [1 2;3 4];

n = length(T);
cvx_begin sdp quiet
cvx_precision high;
variable Y0(n,n) hermitian
variable Y1(n,n) hermitian
minimize max(diag(Y0))/2 + max(diag(Y1))/2
subject to
[Y0, T; T', Y1] >= 0;
Y0 >= 0;
Y1 >= 0;
cvx_end
cvx_optval

• very nice find! Btw, does the Thm tell that the Schur multiplier norm is equal to the 'cb' norm---it seems a brief extra argument is needed... – Suvrit May 20 '14 at 1:55
• Good point. It is indeed the case that equality holds -- this is proved in Theorem 8.7 of Paulsen's book (ref. [15] of the Davidson paper). – Nathaniel Johnston May 20 '14 at 2:13
• Nathaniel: did you implement the SDP for computing this? if so, could you share that script? thanks! – Suvrit May 21 '14 at 0:55
• Suvrit: Yep, I implemented the SDP in MATLAB. I've now posted code above, which actually simplifies really nicely after using the fact that these maps have such a special form. – Nathaniel Johnston May 21 '14 at 1:54
• Note that the above code is actually based on the SDP in Section 3.2 of arXiv:1207.5726. I imagine they both simplify down similarly though. Not sure if it might be possible to simplify further and even find an explicit formula in certain special cases. – Nathaniel Johnston May 21 '14 at 1:59

EDIT. In light of Nathaniel's answer above, I must admit that the hardness intuition was wrong, and the problem is indeed tractable. However, I'm leaving the original answer as is, to preserve the context.

Too long for a comment, but some background information that suggests why it might be usually very hard to compute $\|T\|_{\text{S}}$.

The following theorem is usually attributed to Haagerup (though the Davidson paper cited above suggests that it was already known to previous authors, and it could also be essentially attributed to Grothendieck).

Thm. Let $T$ be any matrix. Then \begin{equation*} \|T\|_S = \min\{ \|X\|_{\infty,2} \|Y\|_{\infty,2} \mid T = X^*Y\}, \end{equation*} where $\|\cdot\|_S$ denotes the Schur-multiplier norm, while $\|X\|_{\infty,2} = \max_{1 \le j \le n} \|x_j\|_2$, where $x_j$ is the $j$-th column of $X$.

If $T$ is unitary, then $\|T\|_S=1$; if $T$ is symmetric positive definite, then $\|T\|_S = \max_i t_{ii}$. For many other special matrix structures, this norm can be computed, and the Davidson paper linked to in my comment to the OP provides several such examples.