# An induced matrix norm equal to the matrix $\infty$-norm

Suppose $A\in\mathbb{C}^{m\times n}$. Consider the matrix norm $\|A\|$ induced by two vector $\infty$-norms $\|x\|_{\infty}$ and $\|y\|_{\infty}$ for $x\in\mathbb{C}^n$ and $y\in\mathbb{C}^m$ respectively, $$\|A\| = \max_{\|x\|_{\infty} = 1}\|Ax\|_{\infty}$$ Is this induced norm the same as the matrix $\infty$-norm defined by $$\|A\|_{\infty} = \max_{1\leq i\leq m}\|e_i^H A\|_{1}$$ If so prove it.

I want to know to know what $e_i^H A$ means does the mean I am taking the $i$-th rows of $A$ or the $i$-th columns of $A$? Just need some basic understandings of what I have here, pretty rusty on linear algebra.

Is there another way of writing the induced matrix norm perhaps $$\|A\| = \|x\|_{1}\|A\|_{\infty}$$

• In the title you ask about equivalence. In the Q you ak if they are the same. $\mathbb C^{m\times n}$ is a finite-dimensional vector space. All norms on a finite-dimensional real or complex vector space are equivalent, in that they induce the same topology. Commented May 14, 2016 at 12:45
• edited the title of the question Commented May 14, 2016 at 12:58
• $e_i^H A$ is the $i$th row of $A$, just as $Ae_j$ is the $j$th column of $A$. Commented May 16, 2016 at 12:08
• @Omnomnomnom ok, got it. So then would $Ae_i$ be the $i$th column of $A$ just want to know how these can be varied and there meanings. Commented May 16, 2016 at 12:21
• Perhaps it is helpful to note that $e_i^H A = (A^H e_i)^H$ Commented May 16, 2016 at 12:26

The answer to this is yes. In order to prove it, note that $$\|Ax\|_\infty = \left \| \pmatrix{(e_1^H A)x\\ \vdots \\ (e_m^H A)x} \right\|_\infty = \max_{i=1,\dots,m} \left|(e_i^H A)x\right| \leq \\ \max_{i=1,\dots m } \|(e_i^H A)\|_1 \cdot \|x\|_\infty$$ The inequality comes from the general result $|u^Tv| \leq \|u\|_1 \|v\|_\infty$, which you may consider as an instance of Hölder's inequality. In any case, the proof of the inequality is pretty quick (but it requires expanding the dot-product as a sum, which I'm too lazy to do).
From there, it is necessary to show that this upper bound is attained. That is, it is necessary to find an $x$ with $\|x\|_\infty = 1$ and $\|Ax\|_\infty = \|A\|_\infty$. To that effect, let $i$ be the row of $A$ with the highest $1$-norm, and consider $x$ to be given by $$x_j = \frac{|e_iAe_j|}{e_iAe_j} = \frac{|A_{ij}|}{A_{ij}} \quad j = 1,\dots,n$$ (in the case that $A_{ij} = 0$, set $x_j = 1$).
• If you plug the inequality into the definition of $\|A\|$, you can now verify that $\|A\| \leq \max_{1 \leq i\leq m} \cdots$. However, that on its own does not complete the proof, hence the second part. Commented May 16, 2016 at 12:32
• Right, so after the inequality I am confused about your second part. As in we have to find an $x$ such that $\|x\|_{\infty} = 1$ to show that $\|A\| = \|A\|_{\infty}$. Commented May 16, 2016 at 12:35
• In the first part, we showed that $$\|A\|_\infty = \max_{\|x\|_\infty = 1}\|Ax\|_\infty \leq \max_{\|x\|_\infty = 1}\left( \max_{i=1,\dots m } \|(e_i^H A)\|_1 \cdot \|x\|_\infty\right) = \max_{i=1,\dots m } \|(e_i^H A)\|_1$$ That is, we have shown that $$\|A\|_\infty \leq \max_{i=1,\dots m } \|(e_i^H A)\|_1$$ We have yet to show, however, that $$\|A\|_\infty \geq \max_{i=1,\dots m } \|(e_i^H A)\|_1$$ Commented May 16, 2016 at 12:40