2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.