I need to bound the absolute maximum of each entry of a matrix-vector product:
$\max_{|x|_{1}=1} |Ax|_{\infty}$
I tried to pose this in terms of the induced infinity norm of $A$, as in $|Ax|_{\infty} \leq |A|_{\infty}|x|_{\infty}$ but that doesn’t have the decay properties I need. It is known that $x_i \geq 0$, but $A_{ij}$ may be positive or negative. I was wondering if there’s a known bound on the above quantity when the entries of vector $x$ are known to be non-negative. Here $|x|_1 = \sum_i x_i$ and $|x|_{\infty} = \max_i |x_i|$. Any help would be appreciated.
Best Answer
Notice that if $|a_{km}|=max_{i,j}|a_{ij}|$ then $|Ae_m|_{\infty}=|a_{km}|$, where $e_m$ is the column vector with 1 in the $m$ entry and $0$ otherwise.
It is clear that $|Ax|_{\infty}\leq |a_{km}|$, if $x\geq 0$ and $|x|_1=1$ .
So $max_{|x|_1=1\ ,\ x\geq 0}|Ax|_{\infty}=max_{i,j}|a_{ij}|$