Operator Norms and Duality

Linear Functionals

For $V$ over $K$, a linear $T : V \to K$ is a linear functional. In coordinates, $T(x)$ is a $1 \times n$ matrix times $x$. On $K^n$, every linear functional has the form

$$\hat{w} : K^n \to K, \qquad \hat{w}(x) = w^*x$$

Continuity and Boundedness

A linear $T : V \to W$ between normed spaces is continuous iff

$$\sup_{x \neq 0} \frac{\|Tx\|_W}{\|x\|_V} < \infty$$

Proof

$(\Leftarrow)$ Suppose $\frac{\|Tx\|_W}{\|x\|_V} \le M < \infty$ for all $x \neq 0$. Then for any distinct $y, z \in V$, $\frac{\|T(y - z)\|}{\|y - z\|} \le M$, i.e. $\|Ty - Tz\| \le M\|y - z\|$.

$(\Rightarrow)$ Suppose $T$ is continuous. At 0, there is $\delta > 0$ such that $\|y\| \le \delta \Rightarrow \|Ty - T0\| \le 1$. Then for $x \neq 0$

$$\frac{\|Tx\|_W}{\|x\|_V} = \frac{1}{\delta} \left\| T\Big(\delta \frac{x}{\|x\|}\Big) \right\|_W \le \frac{1}{\delta}$$

If $V$ is finite dimensional, every linear $T : V \to W$ is continuous.

Operator Norm

For a continuous linear $T : V \to W$,

$$\|T\| = \sup_{x \neq 0} \frac{\|Tx\|}{\|x\|} = \sup_{\|x\| = 1} \|Tx\|$$

1. $\|T\| = 0$ iff $T = 0$,
2. $\|\alpha T\| = |\alpha| \, \|T\|$,
3. $\|T + S\| \le \|T\| + \|S\|$.

Induced Matrix Norms

$$\|A\|_{p,q} = \max_{x \neq 0} \frac{\|Ax\|_q}{\|x\|_p}$$

$\|A\|_{2,2} = \sigma_1(A)$, since by Rayleigh-Ritz

$$\max_{x \neq 0} \frac{\|Ax\|_2^2}{\|x\|_2^2} = \max_{x \neq 0} \frac{x^*A^*Ax}{x^*x} = \lambda_{\max}(A^*A) = \sigma_1^2(A)$$

$\|A\|_{1,1}$ is the max modulus column sum and $\|A\|_{\infty,\infty}$ is the max modulus row sum.

Proof For $\|A\|_{1,1}$, let $x \neq 0$. Then

$$\|Ax\|_1 = \sum_{i=1}^{m} \Big| \sum_{j=1}^{n} a_{ij} x_j \Big| \le \sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}||x_j| = \sum_{j=1}^{n} |x_j| \sum_{i=1}^{m} |a_{ij}| \le \Big(\max_j \sum_{i=1}^{m} |a_{ij}|\Big) \|x\|_1$$

so $\|A\|_{1,1} \le \max_j \sum_{i=1}^{m} |a_{ij}|$. Let $\hat{j} \in \mathrm{argmax}_j \sum_{i=1}^{m} |a_{ij}|$. Then $\|e_{\hat{j}}\|_1 = 1$ and $\|Ae_{\hat{j}}\|_1 = \max_j \sum_{i=1}^{m} |a_{ij}|$, so equality is attained.

Dual Norm

The dual norm of $\|\cdot\|$ on $K^n$ is

$$\|y\|^D := \max_{x \neq 0} \frac{|y^*x|}{\|x\|}$$

so directly $|y^*x| \le \|x\| \, \|y\|^D$.

Hölder $|y^*x| \le \|x\|_1 \|y\|_\infty$, since

$$|y^*x| = \Big| \sum_i \bar{y}_i x_i \Big| \le \sum_i |y_i||x_i| \le \sum_i \big(\max_j |y_j|\big)|x_i| = \|y\|_\infty \|x\|_1$$ $$\|y\|_1^D = \|y\|_\infty, \qquad \|x\|_\infty^D = \|x\|_1, \qquad \|y\|_2^D = \|y\|_2$$

Hahn-Banach If $x \in V$ is nonzero, there is $f \in V^*$ with $\|f\|_{V^*} = 1$ and $f(x) = \|x\|_V$. On $K^n$: there is $y$ with $\|y\|^D = 1$ and $y^*x = \|x\|$.

The Dual of the Dual

$$\|\cdot\|^{DD} = \|\cdot\|$$

Proof Let $x \neq 0$. Then

$$\|x\|^{DD} = \max_{\|y\|^D = 1} |y^*x| \le \max_{\|y\|^D = 1} \|x\| \, \|y\|^D = \|x\|$$

and by Hahn-Banach there is $y \in K^n$ with $\|y\|^D = 1$ and $y^*x = \|x\|$, so equality holds.

For $A \in M_n(K)$, the norm induced by $\|\cdot\|$ equals the norm of $A^*$ induced by $\|\cdot\|^D$,

$$\|A\|_{\|\cdot\|, \|\cdot\|} = \|A^*\|_{\|\cdot\|^D, \|\cdot\|^D}$$

Proof

$$\begin{aligned} \|A^*\|_{D,D} &= \max_{\|x\|^D = 1} \|A^*x\|^D = \max_{\|x\|^D = 1} \max_{\|y\| = 1} |(A^*x)^*y| = \max_{\|y\| = 1} \max_{\|x\|^D = 1} |(Ay)^*x| \\ &= \max_{\|y\| = 1} \|Ay\|^{DD} = \max_{\|y\| = 1} \|Ay\| = \|A\|_{\|\cdot\|, \|\cdot\|} \end{aligned}$$