Return to Answer

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

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

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

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

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.

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