Matrix Norms
Definition. A matrix norm is mapping $|\cdot|:\mathbb{F}^{m\times n} \to \mathbb{R}$ such that
- $|A| \ge 0$ for every $A \in \mathbb{F}^{m\times n}$ with $|A| = 0$ if and only if $A = 0$.
- $|A + B| \le |A| + |B|$ for all $A, B\in \mathbb{F}^{m\times n}$.
$|\alpha A| = \alpha |A|$ for all $\alpha\in\mathbb{F}$ and $A \in \mathbb{F}^{m\times n}$.
| Remark. An obvious combination of the triangle inequality and homogeneity shows that $|\alpha A + \beta B| \le | \alpha | |A| + | \beta | |B|$. |
Remark. Again, we’re not to interested in the general abstract notion of a norm but rather some very specific ones.
Definition. Suppose that $|\cdot|{(n)}$ is a norm on $\mathbb{F}^n$ and $|\cdot|{(m)}$ on $\mathbb{F}^m$. Then the matrix norm induced by these two norms is given by
\[\|A\|_{(m,n)} := \sup_{x\neq 0} \frac{\|Ax\|_{(m)}}{\|x\|_{(n)}} = \sup_{\|x\|_{(n)} = 1} \|Ax\|_{(m)}.\]In particular, if both $|\cdot|{(m)}$ and $|\cdot|{(n)}$ are both $p$-norm (same $p$ for both), then we call the induced norm $|A|_p$.
Remark. This supremum always exists. We can see this by noting the region determined by
\[\|x\|_{(n)} = 1\]is a compact subset of $\mathbb{F}^n$. Since norms are continuous, the extreme value theorem guarantees that the supremum exists and is also a maximum.
Proposition. $|Ax|{(m)} \le |A|{(m,n)} |x|_{(n)}$.
Proof. Follows immediately from the definition.
Proposition. Let $A \in \mathbb{F}^{m\times n}$ and $B \in \mathbb{F}^{n\times s}$. Then $|AB|{(m,s)} \le |A|{(m,n)} |B|_{(n,s)}$.
Proof.
\[\|AB\|_{(m,s)} := \sup_{x\neq 0} \frac{\|ABx\|_{(m)}}{\|x\|_{(s)}} \le \frac{\|A\|_{(m,n)} \|B\|_{(n,s)} \|x\|_s}{\|x\|_s}.\]Proposition. $|\overline{A}|_p = |A|_p$.
Proof. Since $|\overline{x}|_p = |x|_p$ for any $x$, it follows that
\[\|\overline{A}\|_p = \sup_{x\neq 0} \frac{\|\overline{A}x\|_{p}}{\|x\|_{p}} = \sup_{x\neq 0} \frac{\|A\overline{x}\|_{p}}{\|\overline{x}\|_{p}} = \|A\|_p.\]| Proposition. Let $D = \mathrm{diag}(d_i)$. Then $|D|_p = \max_i | d_i | =: M$. |
Proof. Let $x = [x_1, \ldots, x_m]^T$. Then
\(\|Dx\|_p = \left(\sum_{i=1}^m |d_i x_i|^p\right)^{1/p} = \left(\sum_{i=1}^m |d_i|^p |x_i|^p\right)^{1/p} \le M\left(\sum_{i=1}^m |x_i|^p\right)^{1/p} = M\|x\|_p.\) So it follows that $|D|_p \le M$. We claim that the $\ge$ direction holds as well. Suppose that $|d_k| = M$. Then
\[\|De_k\|_p = \|d_ke_k\|_p = |d_k| = M.\]Since $M = |De_k|_p \le |D|_p$, the claim follows and we are done.
Remark. Since we are so interested in $1$, $2$, and $\infty-$norms of vectors, it is natural to investigate the corresponding induced norms.
Proposition. Let $A \in\mathbb{F}^{m\times n}$.
- If $A = [a_1, \ldots, a_n]$, then $|A|_1 = \max_i |a_i|_1$.
- If the rows of $A$ are $a_1^T, \ldots, a_m^T \in \mathbb{F}^{1\times n}$. Then $|A|_\infty = \max_i |a_i|_1$.
Proof. (a) Let $M := \max_i |a_i|_1$. Then
\[\|Ax\|_1 = \|x_1a_1 + \cdots + x_na_n\|_1 \le |x_1|\|a_1\|_p + \cdots + |x_n|\|a_n\|_p \le M(|x_1| + \cdots + |x_n|) = M\|x\|_1.\]Thus, $|A|_1 \le M$. Now suppose that $|a_k|_1 = M$. Then
\[\|Ae_k\|_1 = \|a_k\|_1 = M.\]Since $M = |Ae_k|_1 \le |A|_1 |e_k|_1 = |A|_1$, it follows that $|A|_1 \ge M$.
(b) Let $M := \max_i |a_i|_1$. Then
\[\|Ax\|_\infty = \max_i |a_i^T x| \le \|a_k\|_1 \|x\|_\infty = M \|x\|_\infty.\]The last inequality is an application of Holder’s inequality (TODO: justify rigorously). So then $|A|_\infty \le M$. Suppose that $|a_k|_1 = M$. Then
\[\|A\|_\infty \ge \|Ax\|_\infty \ge |a_k|_1 = M\](TODO: fill details in!).