4
$\begingroup$

Let $M:\mathbb{C}\to \mathbb{C}$ be a matrix and equip $\mathbb{C}$ with the norm $$\|x\|_\infty=\max_{1\le j\le n}|x_j|.$$ If the operator norm is given by $$\|M\|=\sup_{\|x\|=1}|Mx|,$$ is it possible to compute the operator norm exactly in terms of the matrix entries?

Since $(Mx)_i=\sum_{j=1}^nm_{ij}x_j$, we have $$\|M\|=\sup_{\|x\|_\infty=1}\max_{1\le i\le n}\bigg|\sum_{j=1}^nm_{ij}x_j\bigg|.$$ From here, it is clear how one might bound this norm, but it is not clear to me how to compute it exactly without knowledge of the matrix.

$\endgroup$
1
  • $\begingroup$ You have written $(Mx)_j$ incorrectly. We have $$ (Mx)_i = \sum_{j=1}^n m_{ij}x_j. $$ $\endgroup$ Commented Jun 16, 2020 at 23:48

1 Answer 1

2
$\begingroup$

Hint: Using the triangle inequality, show that if $\|x\|_\infty = 1$, then $$ |(Mx)_i| \leq \sum_{j=1}^n |m_{ij}|. $$ This gives you an upper bound for $\|M\|$, i.e. a value $C$ that depends on the entries of $M$ for which $\|M\| \leq C$. Using the entries of $M$, find a vector $x$ for which $\|x\|_\infty = 1$ and $\|Mx\|_\infty = C$.

$\endgroup$
5
  • $\begingroup$ So the upper bound for $\|M\|$ that you mentioned is $C=\max_{1\le i\le n}\sum_{j=1}^n|m_{ij}|$? In that case, we can just take x to be the n-tuple with 1 in every entry. Then its infinity norm is 1 and $\|Mx\|=C$. $\endgroup$
    – zbrads2
    Commented Jun 17, 2020 at 0:17
  • $\begingroup$ Actually, it looks like I would need positive matrix entries for that to work. $\endgroup$
    – zbrads2
    Commented Jun 17, 2020 at 0:29
  • $\begingroup$ Your upper bound is correct. As for finding the $x$, fix your solution by taking $x$ to have a $-1$ in the $j$'s corresponding to negative entries $m_{ij}$. $\endgroup$ Commented Jun 17, 2020 at 0:50
  • $\begingroup$ That was my next thought, but it seems like there aren't enough entries in $x$ to record the sign of every $m_{ij}$. In other words, the sign of $x$ would depend on a choice of $i$. $\endgroup$
    – zbrads2
    Commented Jun 17, 2020 at 1:01
  • $\begingroup$ @zbrads2 It only needs to work for the sign of the $i$th row, where $i$ is such that $\sum_{j=1}^n |m_{ij}|$ is maximized $\endgroup$ Commented Jun 17, 2020 at 1:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .