Subsection 1.3.8 Submultiplicative norms
¶There are a number of properties that we would like for a matrix norm to have (but not all norms do have). Recalling that we would like for a matrix norm to measure by how much a vector is "stretched," it would be good if for a given matrix norm, \(\| \cdots \|: \mathbb C^{m \times n} \rightarrow \mathbb R \text{,}\) there are vector norms \(\| \cdot \|_\mu: \Cm \rightarrow \mathbb R \) and \(\| \cdot \|_\nu: \Cn \rightarrow \mathbb R \) such that, for arbitrary nonzero \(x \in \Cn \text{,}\) the matrix norm bounds by how much the vector is stretched:
or, equivalently,
where this second formulation has the benefit that it also holds if \(x = 0 \text{.}\) When this relationship between the involved norms holds, the matrix norm is said to be subordinate to the vector norms:
Definition 1.3.8.1. Subordinate matrix norm.
A matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be subordinate to vector norms \(\| \cdot \|_\mu: \Cm \rightarrow \mathbb R \) and \(\| \cdot \|_\nu: \Cn \rightarrow \mathbb R \) if, for all \(x \in \Cn \text{,}\)
If \(\| \cdot \|_\mu \) and \(\| \cdot \|_\nu \) are the same norm (but perhaps for different \(m \) and \(n \)), then \(\| \cdot \| \) is said to be subordinate to the given vector norm.
Fortunately, all the norms that we will employ in this course are subordinate matrix norms.
Homework 1.3.8.1.
ALWAYS/SOMETIMES/NEVER: The matrix 2-norm is subordinate to the vector 2-norm.
ALWAYS/SOMETIMES/NEVER: The Frobenius norm is subordinate to the vector 2-norm.
Both are ALWAYS true.
Now prove it.
We first prove that the matrix 2-norm is subordinate to the vector 2-norm.
W.l.o.g., assume \(x \neq 0 \text{.}\) (Why? Because if \(x = 0 \) than obviously \(\| A x \|_\mu \leq \| A \|_{\mu,\nu} \| x \|_\nu \text{.}\))
The second result follows from the fact that \(\| A \|_2 \leq \| A \|_F \text{.}\) We showed that in Homework 1.3.7.2.
Theorem 1.3.8.2.
Induced matrix norms, \(\| \cdot \|_{\mu,\nu}: \mathbb C^{m \times n} \rightarrow \mathbb R \text{,}\) are subordinate to the norms, \(\| \cdot \|_\mu \) and \(\| \cdot \|_\nu \text{,}\) that induce them.
Proof.
W.l.o.g. assume \(x \neq 0 \text{.}\) Then
Corollary 1.3.8.3.
Any matrix \(p\)-norm is subordinate to the corresponding vector \(p\)-norm.
Another desirable property that not all norms have is that
This requires the given norm to be defined for all matrix sizes.
.Definition 1.3.8.4. Consistent matrix norm.
A matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be a consistent matrix norm if it is defined for all \(m \) and \(n \text{,}\) using the same formula for all \(m \) and \(n \text{.}\)
Obviously, this definition is a bit vague. Fortunately, it is pretty clear that all the matrix norms we will use in this course, the Frobenius norm and the \(p\)-norms, are all consistently defined for all matrix sizes.
Definition 1.3.8.5. Submultiplicative matrix norm.
A consistent matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be submultiplicative if it satisfies
Theorem 1.3.8.6.
Let \(\| \cdot \|: \C^n \rightarrow \mathbb R \) be a vector norm defined for all \(n \text{.}\) Define the corresponding induced matrix norm as
Then for any \(A \in \C^{m \times k} \) and \(B \in \C^{k \times n} \) the inequality \(\| A B \| \leq \| A \| \| B \| \) holds.
In other words, induced matrix norms are submultiplicative. To prove this theorem, it helps to first prove a simpler result:
Lemma 1.3.8.7.
Let \(\| \cdot \|: \C^n \rightarrow \mathbb R \) be a vector norm defined for all \(n \) and let \(\| \cdot \|: \mathbb C^{m \times n} \rightarrow \mathbb R \) be the matrix norm it induces. Then \(\| A x \| \leq \| A \| \| x \| \text{..}\)
Proof.
If \(x = 0 \text{,}\) the result obviously holds since then \(\| A x \| = 0 \) and \(\| x \| = 0 \text{.}\) Let \(x \neq 0 \text{.}\) Then
Rearranging this yields \(\| A x \| \leq \| A \| \| x \| \text{.}\)
We can now prove the theorem:
Proof.
Homework 1.3.8.2.
Show that \(\| A x \|_\mu \leq \| A \|_{\mu,\nu} \| x \|_\nu \) for all \(x \text{.}\)
W.l.o.g. assume that \(x \ne 0 \text{.}\) (Why? Because if \(x = 0 \) than obviously \(\| A x \|_\mu \leq \| A \|_{\mu,\nu} \| x \|_\nu \text{.}\))
Rearranging this establishes the result.
Homework 1.3.8.3.
Show that \(\| A B \|_\mu \leq \| A \|_{\mu,\nu} \| B \|_{\nu,\mu} \text{.}\)
Homework 1.3.8.4.
Show that the Frobenius norm, \(\| \cdot \|_F \text{,}\) is submultiplicative.
Hence \(\| A B \|_F^2 \leq \| A \|_F^2 \| B \|_F^2 \text{.}\) Taking the square root of both sides leaves us with \(\| A B \|_F \leq \| A \|_F \| B \|_F \text{.}\)
This proof brings to the forefront that the notation \(\widetilde a_i^T \) leads to some possible confusion. In this particular situation, it is best to think of \(\widetilde a_i \) as a vector that, when transposed, becomes the row of \(A \) indexed with \(i \text{.}\) In this case, \(\widetilde a_i^T = \overline{\widetilde a_i}^H \) and \((\widetilde a_i^T)^H = \overline {\widetilde a_i} \) (where, recall, \(\overline x \) equals the vector with all its entries conjugated). Perhaps it is best to just work through this problem for the case where \(A \) and \(B \) are real-valued, and not worry too much about the details related to the complex-valued case...
Homework 1.3.8.5.
For \(A \in \C^{m \times n} \) define
TRUE/FALSE: This is a norm.
TRUE/FALSE: This is a consistent norm.
Remark 1.3.8.8.
The important take-away: The norms we tend to use in this course, the \(p\)-norms and the Frobenius norm, are all submultiplicative.
Homework 1.3.8.6.
Let \(A \in \mathbb C^{m \times n} \text{.}\)
ALWAYS/SOMETIMES/NEVER: There exists a vector
such that \(\| A \|_\infty = \| A x \|_\infty \text{.}\)
ALWAYS
Now prove it!
Partition \(A \) by rows:
We know that there exists \(k \) such that \(\| \widetilde a_k \|_1 = \| A \|_\infty \text{.}\) Now
where we take \(\frac{ \vert \alpha_{k,j} \vert }{ \alpha_{k,j} } = 1 \) whenever \(\alpha_{k,j} = 0 \text{.}\) Vector
has the desired property.