# Closed form for this specific induced matrix norm?

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?

## 1 Answer

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.

• Of course, we also have the lower bound $$\min\{\|Ax\|_\infty, \|a\|_1\}$$ – Omnomnomnom Jan 18 '17 at 1:45