Closed form for this specific induced matrix norm?

Question

Let $\|\cdot\|_{\alpha_1}$ denote the following norm in $\mathbb{R}^n$: $$\|x\|_{\alpha_1} = \max\limits_{i=1, \ldots, n} |x_i|,$$ and let $\|\cdot\|_{\alpha_2}$ denote the following norm in $\mathbb{R}^{n+1}$: $$\|y\|_{\alpha_2} = \max\limits_{i=1, \ldots, n} |y_i| + |y_{n+1}|.$$

Now, for any $(n+1)\times n$ matrix $A$ let $\|A \|_{\alpha_1, \alpha_2}$ denote the matrix norm induced by these two norms: $$\|A \|_{\alpha_1, \alpha_2} = \sup_{\|x\|_{\alpha_1}=1} \, \|Ax\|_{\alpha_2}.$$

It is easy for me to show that $$\|A \|_{\alpha_1, \alpha_2} \leq \max_{i=1, \ldots, n} \sum_{k=1}^n |a_{ik}| + \sum_{k=1}^p |a_{p+1,k}|.$$

But I am not sure whether this upper bound is the norm $\|A \|_{\alpha_1, \alpha_2}$ that I am looking for.

Is there a well known closed form for the induced norm of this type?

Answer 1

Partition $A$ into $$ A = \pmatrix{\hat A\\ a^T} $$ where $\hat A$ is square and $a$ is a column-vector. We have $$ \|Ax\|_{\alpha_2} = \|\hat Ax\|_\infty + |a^Tx| $$ And we are maximizing this subject to $\|x\|_\infty = 1$. Applying the definition of the induced norm and Hölder, we have $$ \|Ax\| = \|\hat Ax\|_\infty + |a^Tx| \leq \|\hat A\|_\infty \|x\|_\infty + \|a^T\|_\infty \|x\|_\infty $$ And with $\|a^T\|_\infty = \|a\|_1$, this is exactly the inequality that you got. However, this will not generally give us a tight upper bound, since we can't necessarily attain both maxima simultaneously. For example, with $$ A = \pmatrix{1&-1\\1&1} $$ we indeed have $\|A\|_{\alpha_2} \leq 2+2 = 4$. However, we find $$ \max_{|x_1|,|x_2| \leq 1} |x_1 - x_2| + |x_1 + x_2| = \\ \max_{0\leq x_2 < x_1 \leq 1} |x_1 - x_2| + |x_1 + x_2| = \\ \max_{0\leq x_2 < x_1 \leq 1} 2x_1 = 2 $$ I am not aware of any closed form for the desired matrix norm.