# Maximum 1-norm of matrix times unit vector

If $A$ is a $p \times p$ matrix, what is

$$\max_{||u||_2=1} ||Au||_1 ?$$

I am specifically interested in the case when $A$ is positive definite.

-
What are your thoughts on this? – t.b. Aug 2 '11 at 16:55
It's easy when $A$ is identity, then the maximum is $\sqrt(p)$ since $u=(\sqrt(1/p),...)$. – charles.y.zheng Aug 2 '11 at 17:21
Hint: what happens when you decompose $u$ into eigenvectors of $A?$ – Ross Millikan Aug 2 '11 at 17:56
I don't think there is an explicit form. the norm is between $\|A\|_1$ and $\sqrt{n}\|A\|_1$. – Sunni Aug 2 '11 at 18:00

I'll assume this is over the reals. You're looking for the norm of $A$ as a linear operator from $({\mathbb R}^p, \|\cdot\|_2)$ to $({\mathbb R}^p, \|\cdot\|_1)$. By duality, that is the same as the norm of $A^T$ as a linear operator from $({\mathbb R}^p, \|\cdot\|_\infty)$ to $({\mathbb R}^p, \|\cdot\|_2)$. Now the set of extreme points of the unit ball of $({\mathbb R}^p, \|\cdot\|_\infty)$ is $\{-1,1\}^p$, i.e. the set of $2^p$ vectors with all entries $\pm 1$, so your answer is the maximum of $\|A^T v\|_2$ for $v \in \{-1,1\}^p$.