16.3 Measuring a Matrix

Chapter 12 §11 gave the Frobenius norm its own symbol and explained the subscript: a bare $\left\| \cdot \right\|$ already meant the norm of a vector, and a matrix, it warned, would shortly be asked to carry both kinds of measurement. This is that moment. A matrix is a list of $mn$ numbers, and it is also a map; measuring the list is easy, measuring the map is what we usually want, and the two answers are not the same number. This section builds the second measurement, computes it in the three cases anyone computes, and says exactly where the first one fails.

Throughout, $F$ is $\mathbb{R}$ or $\mathbb{C}$ , all spaces are finite-dimensional, and $\left\| \cdot \right\|$ with no subscript is a norm in the sense of Definition 16.1.1.

16.3.1. What a matrix norm has to do

Chapter 10 §10 decided whether $\mathbf{A}^{m} \to 0$ by looking at one entry of one Jordan block at a time. A single number attached to $\mathbf{A}$ would be a far better instrument — but only if it interacts with matrix multiplication, because the questions we want to answer are questions about products: $\mathbf{A}^{m}$ , $\sum_k \mathbf{A}^{k}$ , $e^{\mathbf{A}}$ . A norm that satisfies

$\left\| \mathbf{A}\mathbf{B} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\|$

immediately gives $\left\| \mathbf{A}^{m} \right\| \le \left\| \mathbf{A} \right\|^{m}$ , and with that one line a geometric series is in reach. A norm that does not satisfy it gives nothing at all about powers. So the property is not a technical nicety; it is the entire reason for the definition.

A matrix norm is a norm on matrices that never lets a product be bigger than the product of the sizes.

Definition 16.3.1 (Matrix Norm)

Let $n \ge 1$ . A matrix norm on $M_n(F)$ is a function $\left\| \cdot \right\| \colon M_n(F) \to \mathbb{R}$ which is a norm on $M_n(F)$ as a vector space (Definition 16.1.1) and which is in addition submultiplicative: for all $\mathbf{A}, \mathbf{B} \in M_n(F)$ ,

$\left\| \mathbf{A}\mathbf{B} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\| .$

In words: the first requirement is the ordinary one — clauses (N1), (N2), (N3) of Definition 16.1.1 — and it sees $M_n(F)$ only as the vector space $F^{n^2}$ in disguise. The second requirement is the one that notices the multiplication. Note that submultiplicativity is an inequality, not an equality: it is easy for a norm to make $\left\| \mathbf{A}\mathbf{B} \right\|$ far smaller than $\left\| \mathbf{A} \right\|\left\| \mathbf{B} \right\|$ , and impossible for a matrix norm to make it larger.

The condition needs a square matrix only so that $\mathbf{A}\mathbf{B}$ is defined for every pair; nothing else in the definition cares about the shape.

Example (The Frobenius norm is submultiplicative)

Show that $\left\| \mathbf{A}\mathbf{B} \right\|_F \le \left\| \mathbf{A} \right\|_F\left\| \mathbf{B} \right\|_F$ for all $\mathbf{A}, \mathbf{B} \in M_n(F)$ , so that $\left\| \cdot \right\|_F$ is a matrix norm.

Solution. The entry $(\mathbf{A}\mathbf{B})_{ij} = \sum_k a_{ik}b_{kj}$ is the inner product in $F^n$ of the $i$ -th row of $\mathbf{A}$ with the $j$ -th column of $\mathbf{B}$ (up to a conjugation, which does not change moduli). By Theorem 11.1.5,

$\lvert (\mathbf{A}\mathbf{B})_{ij}\rvert^2 \le \Bigl(\sum_k \lvert a_{ik}\rvert^2\Bigr) \Bigl(\sum_k \lvert b_{kj}\rvert^2\Bigr) .$

Summing over all $i$ and $j$ , and noting that the two bracketed factors depend only on $i$ and only on $j$ respectively,

$\left\| \mathbf{A}\mathbf{B} \right\|_F^2 \le \Bigl(\sum_{i,k}\lvert a_{ik}\rvert^2\Bigr) \Bigl(\sum_{k,j}\lvert b_{kj}\rvert^2\Bigr) = \left\| \mathbf{A} \right\|_F^2\,\left\| \mathbf{B} \right\|_F^2 .$

Both sides are non-negative, so taking square roots gives the claim. That $\left\| \cdot \right\|_F$ is a norm was settled in Chapter 11: it is the norm induced by the Frobenius inner product (Definition 11.1.3), so Theorem 11.1.2 and Corollary 11.1.6 apply.

Now the minimal change that breaks it. Keep the idea “read the matrix as a list of numbers” but measure the list with the maximum instead of the Euclidean length.

Example (The entrywise maximum is not submultiplicative)

For $\mathbf{A} \in M_n(F)$ put $N(\mathbf{A}) = \max_{i,j}\lvert a_{ij}\rvert$ . Show that $N$ is a norm on $M_n(F)$ but not a matrix norm for $n \ge 2$ .

Solution. $N$ is the $\infty$ -norm of the list of $n^2$ entries, so it is a norm (Definition 16.1.1): it vanishes only on the zero matrix, $N(c\mathbf{A}) = \lvert c\rvert N(\mathbf{A})$ , and (N3) holds entry by entry.

Submultiplicativity fails already for $n = 2$ . Take $\mathbf{A} = \mathbf{B} = \mathbf{J} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ . Then $N(\mathbf{J}) = 1$ , while

$\mathbf{J}^2 = \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}, \qquad N(\mathbf{J}^2) = 2 > 1 = N(\mathbf{J})N(\mathbf{J}) .$

The mechanism is plain: an entry of a product is a sum of $n$ terms, each as large as the largest entry, and a maximum taken entry by entry has no way of charging for the length of that sum. For $n \times n$ the same matrix gives $N(\mathbf{J}^2) = n$ .

Warning. Submultiplicativity is a property of the norm, not of matrices. The failure above is not caused by $\mathbf{J}$ being special; it is caused by $N$ being the wrong yardstick. Exercise (C2: Repairing the entrywise maximum) shows that the single rescaling $\mathbf{A} \mapsto nN(\mathbf{A})$ repairs it, which is a good way to see that nothing deep is being violated — only a normalization.

16.3.2. The norm a vector norm induces

The definition above is a filter, not a construction: it says which norms are usable, not where to find one. The construction comes from remembering what $\mathbf{A}$ is for. It sends vectors to vectors, and if both are already measured, we can ask how much $\mathbf{A}$ magnifies.

This is exactly the question Chapter 13 §08 asked of the singular value decomposition, and the question Chapter 13 §12 asked of an oblique projection, in each case computing $\max\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}$ and then promising that the number would get a name here.

Before naming it, we must know that the maximum exists. “Take the largest value of a function over infinitely many vectors” is not something one may write without a reason, and the reason is compactness, already packaged for us in Corollary 16.2.5.

Lemma 16.3.1 (The Largest Stretch Is Attained)

Let $n, m \ge 1$ , let $\left\| \cdot \right\|$ be a norm on $F^n$ and also a norm on $F^m$ , and let $\mathbf{A} \in M_{m \times n}(F)$ . Then the function $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|$ attains a maximum on the unit sphere $S = \{\mathbf{x} \in F^n : \left\| \mathbf{x} \right\| = 1\}$ .

Idea. Two steps, and the second is already packaged for us. ① The function is Lipschitz, hence continuous: Lemma 16.1.1 converts a difference of norms into the norm of a difference, and a crude expansion in the standard basis bounds $\left\| \mathbf{A}\mathbf{z} \right\|$ by a constant times $\left\| \mathbf{z} \right\|$ . ② The unit sphere is closed and bounded, hence compact, and a continuous real function on it attains its bounds — which is exactly what Corollary 16.2.5 says.

Proof. Step 1: a Lipschitz bound. Write $\mathbf{z} = \sum_{j=1}^{n} z_j\mathbf{e}_j$ . By subadditivity and homogeneity,

$\left\| \mathbf{A}\mathbf{z} \right\| \le \sum_{j=1}^{n}\lvert z_j\rvert\,\left\| \mathbf{A}\mathbf{e}_j \right\| \le \Bigl(\max_{j}\left\| \mathbf{A}\mathbf{e}_j \right\|\Bigr)\left\| \mathbf{z} \right\|_1 .$

By Theorem 16.2.2, applied on $F^n$ to the norms $\left\| \cdot \right\|_1$ and $\left\| \cdot \right\|$ , there is a constant $c > 0$ with $\left\| \mathbf{z} \right\|_1 \le c\left\| \mathbf{z} \right\|$ for every $\mathbf{z}$ . Hence $\left\| \mathbf{A}\mathbf{z} \right\| \le M\left\| \mathbf{z} \right\|$ with $M = c\max_j\left\| \mathbf{A}\mathbf{e}_j \right\|$ , a constant depending on $\mathbf{A}$ but not on $\mathbf{z}$ .

Step 2: continuity. Let $\mathbf{x}, \mathbf{y} \in F^n$ . By Lemma 16.1.1, applied to the vectors $\mathbf{A}\mathbf{x}$ and $\mathbf{A}\mathbf{y}$ of $F^m$ , and then by Step 1,

$\bigl\lvert\,\left\| \mathbf{A}\mathbf{x} \right\| - \left\| \mathbf{A}\mathbf{y} \right\|\,\bigr\rvert \le \left\| \mathbf{A}(\mathbf{x} - \mathbf{y}) \right\| \le M\left\| \mathbf{x} - \mathbf{y} \right\| .$

So $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|$ is Lipschitz with constant $M$ , and in particular continuous.

Step 3: compactness. The set $S$ is non-empty, since $n \ge 1$ and $\mathbf{e}_1/\left\| \mathbf{e}_1 \right\| \in S$ , the division being legal because $\mathbf{e}_1 \ne \mathbf{0}$ . By Corollary 16.2.5 the unit sphere of any norm on a finite-dimensional space is compact, and a continuous real-valued function on it attains a maximum. That corollary is where this chapter’s imported facts (A3), the compactness of closed bounded sets, and (A4), the extreme value theorem, are cashed in; here we only apply it, to the continuous function of Step 2. This proves the lemma.

The operator norm of a matrix is the worst stretching it can do to a unit vector.

Definition 16.3.2 (Operator Norm)

Let $n, m \ge 1$ and let a norm $\left\| \cdot \right\|$ be given on $F^n$ and on $F^m$ ; we write both with the same symbol, the argument saying which is meant. The operator norm of $\mathbf{A} \in M_{m \times n}(F)$ induced by those norms is

$\left\| \mathbf{A} \right\| \mathrel{:=} \max\{\,\left\| \mathbf{A}\mathbf{x} \right\| : \mathbf{x} \in F^n,\ \left\| \mathbf{x} \right\| = 1\,\} ,$

which exists by Lemma 16.3.1. When the vector norm is $\left\| \cdot \right\|_p$ on both sides we write $\left\| \mathbf{A} \right\|_p$ , and $\left\| \mathbf{A} \right\|_2$ is also called the spectral norm.

Clause by clause: the maximum is over unit vectors only, so a matrix that stretches one long vector enormously is not thereby given a large norm — what counts is the factor. The norm on the source and the norm on the target may be different, and then $\left\| \mathbf{A} \right\|$ depends on both; the notation hides that, which is why the vector norm must always be named. And the word induced is doing real work: not every matrix norm arises this way, as the end of this section shows.

Three equivalent descriptions are worth having at once. For $\mathbf{A} \ne 0$ ,

$\left\| \mathbf{A} \right\| = \max_{\left\| \mathbf{x} \right\| = 1}\left\| \mathbf{A}\mathbf{x} \right\| = \max_{\mathbf{x} \ne \mathbf{0}}\frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} = \max_{\left\| \mathbf{x} \right\| \le 1}\left\| \mathbf{A}\mathbf{x} \right\| .$

The middle expression equals the first because $\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\| = \left\| \mathbf{A}(\mathbf{x}/\left\| \mathbf{x} \right\|) \right\|$ by homogeneity, and $\mathbf{x}/\left\| \mathbf{x} \right\|$ runs over $S$ as $\mathbf{x}$ runs over the non-zero vectors. The third equals the first because scaling any $\mathbf{x}$ with $0 < \left\| \mathbf{x} \right\| \le 1$ up to the sphere only increases $\left\| \mathbf{A}\mathbf{x} \right\|$ , and $\mathbf{x} = \mathbf{0}$ contributes $0$ .

The smallest cases are worth seeing before any real example, because they pin the scale. For $\mathbf{A} = \mathbf{0}$ every $\mathbf{A}\mathbf{x}$ is $\mathbf{0}$ , so $\left\| \mathbf{0} \right\| = 0$ , as (N1) demands. For $m = n = 1$ , a matrix is a scalar $(a)$ , the only unit vectors are the scalars of modulus $1$ , and $\left\| (a) \right\| = \lvert a\rvert$ : the operator norm of a number is its absolute value, so the definition extends the one-dimensional case rather than replacing it. And for $\mathbf{A} = \mathbf{I}$ , every unit vector satisfies $\left\| \mathbf{I}\mathbf{x} \right\| = \left\| \mathbf{x} \right\| = 1$ , so $\left\| \mathbf{I} \right\| = 1$ for every choice of vector norm — a fact used so often below that it is worth fixing now.

Quick check. Why is the maximum in Definition 16.3.2 taken over $\left\| \mathbf{x} \right\| = 1$ rather than over all $\mathbf{x}$ ? What would the supremum over all $\mathbf{x} \in F^n$ be?

Solution. For a non-zero $\mathbf{A}$ it would be infinite: pick $\mathbf{x}_0$ with $\mathbf{A}\mathbf{x}_0 \ne \mathbf{0}$ ; then $\left\| \mathbf{A}(t\mathbf{x}_0) \right\| = t\left\| \mathbf{A}\mathbf{x}_0 \right\| \to \infty$ as $t \to \infty$ . Restricting to unit vectors measures the ratio of output size to input size, which is what “how much does $\mathbf{A}$ magnify?” means, and by homogeneity the ratio is already known on all of $F^n$ once it is known on the sphere.

Theorem 16.3.2 (Properties of the Operator Norm)

Let $\left\| \cdot \right\|$ be a norm on each of $F^n$ , $F^m$ , $F^{\ell}$ , and let $\mathbf{A} \in M_{m \times n}(F)$ . Then:

(a) $\left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{x} \right\|$ for every $\mathbf{x} \in F^n$ , and $\left\| \mathbf{A} \right\|$ is the smallest constant with this property;
(b) $\left\| \cdot \right\|$ is a norm on the vector space $M_{m \times n}(F)$ ;
(c) $\left\| \mathbf{I}_n \right\| = 1$ ;
(d) $\left\| \mathbf{A}\mathbf{B} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\|$ for every $\mathbf{B} \in M_{n \times \ell}(F)$ . In particular the operator norm induced on $M_n(F)$ by a single norm on $F^n$ is a matrix norm in the sense of Definition 16.3.1.

Idea. Everything is the definition plus homogeneity. The one move worth naming is in (a): a general $\mathbf{x} \ne \mathbf{0}$ is $\left\| \mathbf{x} \right\|$ times a unit vector, so the inequality on the sphere upgrades to an inequality everywhere; and once (a) is available, (d) is two applications of it.

Proof.

(a) For $\mathbf{x} = \mathbf{0}$ both sides are $0$ . For $\mathbf{x} \ne \mathbf{0}$ , the vector $\mathbf{u} = \mathbf{x}/\left\| \mathbf{x} \right\|$ satisfies $\left\| \mathbf{u} \right\| = 1$ , so $\left\| \mathbf{A}\mathbf{u} \right\| \le \left\| \mathbf{A} \right\|$ by Definition 16.3.2; multiplying by $\left\| \mathbf{x} \right\|$ and using homogeneity gives $\left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ . If $K$ is any constant with $\left\| \mathbf{A}\mathbf{x} \right\| \le K\left\| \mathbf{x} \right\|$ for all $\mathbf{x}$ , then taking a unit $\mathbf{x}_0$ at which the maximum is attained (Lemma 16.3.1) gives $\left\| \mathbf{A} \right\| = \left\| \mathbf{A}\mathbf{x}_0 \right\| \le K$ .
(b) Each value is a maximum of non-negative numbers, so $\left\| \mathbf{A} \right\| \ge 0$ . If $\left\| \mathbf{A} \right\| = 0$ then $\mathbf{A}\mathbf{u} = \mathbf{0}$ for every unit $\mathbf{u}$ , hence $\mathbf{A}\mathbf{x} = \mathbf{0}$ for every $\mathbf{x}$ by (a), hence $\mathbf{A} = 0$ . For a scalar $c$ , $\left\| c\mathbf{A} \right\| = \max_{\left\| \mathbf{x} \right\|=1}\lvert c\rvert\left\| \mathbf{A}\mathbf{x} \right\| = \lvert c\rvert\left\| \mathbf{A} \right\|$ . For subadditivity, let $\mathbf{x}$ be a unit vector; then $\left\| (\mathbf{A} + \mathbf{B})\mathbf{x} \right\| \le \left\| \mathbf{A}\mathbf{x} \right\| + \left\| \mathbf{B}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\| + \left\| \mathbf{B} \right\|$ , and taking the maximum over $\mathbf{x}$ gives $\left\| \mathbf{A} + \mathbf{B} \right\| \le \left\| \mathbf{A} \right\| + \left\| \mathbf{B} \right\|$ .
(c) $\left\| \mathbf{I}_n\mathbf{x} \right\| = \left\| \mathbf{x} \right\| = 1$ for every unit $\mathbf{x}$ , so the maximum is $1$ .
(d) Let $\mathbf{x} \in F^{\ell}$ be a unit vector. By (a) applied twice, first to $\mathbf{A}$ and then to $\mathbf{B}$ ,

$\left\| \mathbf{A}\mathbf{B}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{B}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\|\,\left\| \mathbf{x} \right\| = \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\| .$

Taking the maximum over unit $\mathbf{x}$ gives $\left\| \mathbf{A}\mathbf{B} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{B} \right\|$ . This proves the theorem.

Part (c) is small and will do a large amount of work: it is the single property that separates the operator norms from the rest of the matrix norms.

16.3.3. The three formulas

A definition by maximization is not yet a computation. For the three standard vector norms the maximization can be carried out completely, and in two of the three cases the answer is read straight off the entries.

Theorem 16.3.3 (Computing the 1-, 2- and Infinity-Norms)

Let $\mathbf{A} = (a_{ij}) \in M_{m \times n}(F)$ with $m, n \ge 1$ . Then

(a) $\displaystyle \left\| \mathbf{A} \right\|_1 = \max_{1 \le j \le n}\ \sum_{i=1}^{m}\lvert a_{ij}\rvert$ , the largest absolute column sum;
(b) $\displaystyle \left\| \mathbf{A} \right\|_{\infty} = \max_{1 \le i \le m}\ \sum_{j=1}^{n}\lvert a_{ij}\rvert$ , the largest absolute row sum;
(c) $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ , the largest singular value of $\mathbf{A}$ (Definition 13.8.1).

Idea. Each part is an upper bound and a witness. ① For $\left\| \cdot \right\|_1$ the upper bound is subadditivity of the modulus with the column sums pulled out, and the witness is a standard basis vector $\mathbf{e}_k$ selecting the heaviest column. ② For $\left\| \cdot \right\|_\infty$ the upper bound is the same estimate read along a row, and the witness is a vector of unimodular entries chosen to rotate every term of the heaviest row into the positive reals, so that no cancellation occurs. ③ For $\left\| \cdot \right\|_2$ the witness is the first right singular vector, and the upper bound is the singular value decomposition: unitary factors are invisible to the Euclidean norm, so only the diagonal matrix $\boldsymbol{\Sigma}$ is left, and a diagonal matrix stretches most along its largest entry, because it scales each coordinate separately.

Proof. Write $C = \max_j\sum_i\lvert a_{ij}\rvert$ and $R = \max_i\sum_j\lvert a_{ij}\rvert$ .

(a). Let $\left\| \mathbf{x} \right\|_1 = 1$ . Then

$\left\| \mathbf{A}\mathbf{x} \right\|_1 = \sum_{i}\Bigl\lvert \sum_j a_{ij}x_j \Bigr\rvert \le \sum_{j}\lvert x_j\rvert \sum_{i}\lvert a_{ij}\rvert \le C\sum_j \lvert x_j\rvert = C ,$

where the first inequality is subadditivity of the modulus together with an exchange of two finite sums. So $\left\| \mathbf{A} \right\|_1 \le C$ . For the reverse, choose $k$ with $\sum_i\lvert a_{ik}\rvert = C$ . The vector $\mathbf{e}_k$ has $\left\| \mathbf{e}_k \right\|_1 = 1$ and $\mathbf{A}\mathbf{e}_k$ is the $k$ -th column of $\mathbf{A}$ , so $\left\| \mathbf{A}\mathbf{e}_k \right\|_1 = C$ . Hence $\left\| \mathbf{A} \right\|_1 \ge C$ .

(b). Let $\left\| \mathbf{x} \right\|_{\infty} = 1$ . For each $i$ ,

$\Bigl\lvert \sum_j a_{ij}x_j \Bigr\rvert \le \sum_j \lvert a_{ij}\rvert\,\lvert x_j\rvert \le \sum_j \lvert a_{ij}\rvert \le R ,$

so $\left\| \mathbf{A}\mathbf{x} \right\|_{\infty} \le R$ and $\left\| \mathbf{A} \right\|_{\infty} \le R$ . For the reverse, choose $k$ with $\sum_j\lvert a_{kj}\rvert = R$ and define $\mathbf{x}$ by $x_j = \overline{a_{kj}}/\lvert a_{kj}\rvert$ when $a_{kj} \ne 0$ and $x_j = 1$ otherwise. Every $x_j$ has modulus $1$ , so $\left\| \mathbf{x} \right\|_{\infty} = 1$ ; and $a_{kj}x_j = \lvert a_{kj}\rvert$ for every $j$ , the choice being legal exactly because we checked $a_{kj} \ne 0$ before dividing. Hence the $k$ -th entry of $\mathbf{A}\mathbf{x}$ is $\sum_j\lvert a_{kj}\rvert = R$ , giving $\left\| \mathbf{A}\mathbf{x} \right\|_{\infty} \ge R$ .

(c). Let $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ be a singular value decomposition (Theorem 13.8.1), with $\mathbf{U}, \mathbf{V}$ unitary and $\boldsymbol{\Sigma}$ carrying $\sigma_1 \ge \dots \ge \sigma_p \ge 0$ on its diagonal, $p = \min(m,n)$ . Let $\left\| \mathbf{x} \right\|_2 = 1$ and put $\mathbf{y} = \mathbf{V}^{*}\mathbf{x}$ . A unitary matrix is an isometry for $\left\| \cdot \right\|_2$ (Theorem 11.7.3, (a) and (f)), so $\left\| \mathbf{y} \right\|_2 = 1$ and $\left\| \mathbf{A}\mathbf{x} \right\|_2 = \left\| \mathbf{U}\boldsymbol{\Sigma}\mathbf{y} \right\|_2 = \left\| \boldsymbol{\Sigma}\mathbf{y} \right\|_2$ . The vector $\boldsymbol{\Sigma}\mathbf{y}$ has entries $\sigma_i y_i$ for $i \le p$ and zeros below, so

$\left\| \mathbf{A}\mathbf{x} \right\|_2^2 = \sum_{i=1}^{p}\sigma_i^2\lvert y_i\rvert^2 \le \sigma_1^2\sum_{i=1}^{n}\lvert y_i\rvert^2 = \sigma_1^2 .$

Hence $\left\| \mathbf{A} \right\|_2 \le \sigma_1$ . For the reverse, take $\mathbf{x} = \mathbf{v}_1$ , the first column of $\mathbf{V}$ ; then $\mathbf{y} = \mathbf{V}^{*}\mathbf{v}_1 = \mathbf{e}_1$ , so $\left\| \mathbf{A}\mathbf{v}_1 \right\|_2 = \left\| \boldsymbol{\Sigma}\mathbf{e}_1 \right\|_2 = \sigma_1$ , and $\left\| \mathbf{v}_1 \right\|_2 = 1$ because the columns of a unitary matrix are orthonormal. This proves the theorem.

Part (c) is the promise this section was written to keep. Chapter 13 §08 computed $\sigma_1 = \max\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}$ and said that Chapter 16 would give that quantity a name, the operator norm $\left\| \mathbf{A} \right\|_2$ , “and this computation is why $\left\| \mathbf{A} \right\|_2 = \sigma_1$ ”. The name is Definition 16.3.2; the reason has now been separated from the name, so that the equality is a theorem about two independently defined numbers rather than a definition dressed up as one. Chapter 13 §12 measured an oblique projection by the same maximum and deferred the word twice; Example (The oblique projection, finally measured) below supplies it. And Chapter 12 §11, when it wrote $\left\| \mathbf{A} \right\|_F$ with an obligatory subscript, explained that the bare symbol was reserved because a matrix would soon be asked to be measured both as a list and as a map: parts (a)–(c) are that second measurement, and the rest of this section is the difference between the two.

Example (One matrix, four numbers)

For $\mathbf{A} = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix} \in M_2(\mathbb{R})$ , compute $\left\| \mathbf{A} \right\|_1$ , $\left\| \mathbf{A} \right\|_{\infty}$ , $\left\| \mathbf{A} \right\|_F$ and $\left\| \mathbf{A} \right\|_2$ .

Solution. The column sums of absolute values are $3 + 4 = 7$ and $0 + 5 = 5$ , so $\left\| \mathbf{A} \right\|_1 = 7$ by Theorem 16.3.3 (a). The row sums are $3$ and $9$ , so $\left\| \mathbf{A} \right\|_{\infty} = 9$ by (b). The Frobenius norm is $\sqrt{9 + 16 + 25} = 5\sqrt2$ .

For the spectral norm, form

$\mathbf{A}^{\top}\mathbf{A} = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix} .$

This matrix is $25\mathbf{I} + 20\begin{psmallmatrix} 0 & 1 \\ 1 & 0\end{psmallmatrix}$ , whose eigenvalues are $25 \pm 20$ , namely $45$ and $5$ . So the singular values are $\sigma_1 = 3\sqrt5$ and $\sigma_2 = \sqrt5$ , and $\left\| \mathbf{A} \right\|_2 = 3\sqrt5 \approx 6.708$ by (c).

Two checks come for free. The product $\sigma_1\sigma_2 = 15$ equals $\lvert\det\mathbf{A}\rvert = 15$ , and $\sigma_1^2 + \sigma_2^2 = 50 = \left\| \mathbf{A} \right\|_F^2$ . The four numbers $7$ , $9$ , $5\sqrt2 \approx 7.071$ and $3\sqrt5 \approx 6.708$ are all different, which is the point: “the size of $\mathbf{A}$ ” is not a well-posed phrase until the norm is named.

Example (The oblique projection, finally measured)

Chapter 13 §12 studied a projection $P$ of $F^2$ onto a line, with matrix $\begin{psmallmatrix} 1 & x \\ 0 & 0 \end{psmallmatrix}$ in a suitable orthonormal basis, and found that the largest value of $\left\| P\mathbf{v} \right\|$ over unit $\mathbf{v}$ is $\sqrt{1 + \lvert x\rvert^2}$ , which over $\mathbb{R}$ is $1/\sin\theta$ for the angle $\theta$ between image and kernel. Confirm this with Theorem 16.3.3 (c) for $x = -1$ , the matrix $\mathbf{P}' = \begin{psmallmatrix} 1 & -1 \\ 0 & 0\end{psmallmatrix}$ of Example (Two Oblique Projections, Measured).

Solution. $(\mathbf{P}')^{\top}\mathbf{P}' = \begin{psmallmatrix} 1 & -1 \\ -1 & 1\end{psmallmatrix}$ , with eigenvalues $2$ and $0$ ; so $\sigma_1 = \sqrt2$ and $\left\| \mathbf{P}' \right\|_2 = \sqrt2$ . This agrees with $\sqrt{1 + \lvert -1\rvert^2} = \sqrt2$ , and with $1/\sin\theta$ for $\theta = \pi/4$ , the angle between the two lines. An orthogonal projection, by contrast, has $\left\| P_U \right\|_2 = 1$ whenever $U \ne \{\mathbf{0}\}$ , since it fixes every unit vector of $U$ and shortens the rest.

The two matrix norms now in play compare in a way worth recording, because the Frobenius norm is far cheaper to compute and the spectral norm is usually the one wanted.

Proposition 16.3.4 (Frobenius Against Spectral)

Let $\mathbf{A} \in M_{m \times n}(F)$ be non-zero, of rank $r$ . Then

$\left\| \mathbf{A} \right\|_2 \le \left\| \mathbf{A} \right\|_F \le \sqrt{r}\,\left\| \mathbf{A} \right\|_2 ,$

and the left inequality is an equality if and only if $r = 1$ .

Idea. Write both norms in terms of the singular values: $\left\| \mathbf{A} \right\|_2 = \sigma_1$ and $\left\| \mathbf{A} \right\|_F^2 = \sigma_1^2 + \dots + \sigma_r^2$ . The claim is then the statement that one term of a sum of $r$ non-negative numbers is at most the sum, which is at most $r$ times the largest — and that the first is an equality exactly when there is only one term.

Proof. By Lemma 11.7.5 and $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.8.1), $\left\| \mathbf{A} \right\|_F = \left\| \boldsymbol{\Sigma} \right\|_F$ , so $\left\| \mathbf{A} \right\|_F^2 = \sum_{i=1}^{p}\sigma_i^2$ . Exactly $r$ of the $\sigma_i$ are non-zero (Theorem 13.8.1), and each satisfies $\sigma_i \le \sigma_1$ . Hence

$\sigma_1^2 \le \sum_{i=1}^{p}\sigma_i^2 \le r\sigma_1^2 ,$

which is the displayed chain after taking square roots and using $\left\| \mathbf{A} \right\|_2 = \sigma_1$ (Theorem 16.3.3 (c)). The left inequality is an equality exactly when $\sigma_i = 0$ for all $i \ge 2$ , that is, when $r = 1$ .

So the two norms never differ by a factor worse than $\sqrt{r} \le \sqrt{\min(m,n)}$ , and they agree exactly on the rank-one matrices. What they do not agree on is more interesting.

16.3.4. What submultiplicativity does not buy

The Frobenius norm is a matrix norm: Example (The Frobenius norm is submultiplicative) proved it submultiplicative. It is tempting to conclude that it is therefore the operator norm induced by some vector norm — perhaps a cleverly chosen one. It is not, and the obstruction is a single line.

Warning. Submultiplicative does not mean induced. Every operator norm satisfies $\left\| \mathbf{I}_n \right\| = 1$ by Theorem 16.3.2 (c), whereas

$\left\| \mathbf{I}_n \right\|_F = \sqrt{\underbrace{1 + 1 + \dots + 1}_{n}} = \sqrt{n} .$

So for $n \ge 2$ the Frobenius norm is not induced by any norm on $F^n$ whatsoever — not by a bad choice, but by no choice at all. It is a matrix norm and not an operator norm, and the two phrases must be kept apart.

The identity is the cheapest witness, and it is decisive because $\left\| \mathbf{I} \right\| = 1$ is forced: the identity stretches nothing, so a norm that measures stretching must give it $1$ . A norm that assigns the identity the value $\sqrt{n}$ is measuring something else — the amount of material in the matrix, which for $\mathbf{I}_n$ grows with $n$ .

Warning. Two different objects are called $\left\| \mathbf{A} \right\|_{\infty}$ in the wild. In this book $\left\| \mathbf{A} \right\|_{\infty}$ is the operator norm induced by $\left\| \cdot \right\|_{\infty}$ on vectors, that is, the largest row sum. The entrywise maximum $N(\mathbf{A}) = \max_{i,j}\lvert a_{ij}\rvert$ of Example (The entrywise maximum is not submultiplicative) is a different function, and it is not even submultiplicative. Whenever a source writes $\left\| \mathbf{A} \right\|_{\infty}$ , check which one is meant by evaluating it at $\mathbf{I}_2$ : the row-sum norm gives $1$ , the entrywise maximum gives $1$ as well — so evaluate instead at $\mathbf{J}$ , where the row-sum norm gives $2$ and the entrywise maximum gives $1$ .

Quick check. The Frobenius norm satisfies $\left\| \mathbf{A}\mathbf{x} \right\|_2 \le \left\| \mathbf{A} \right\|_F\left\| \mathbf{x} \right\|_2$ for every $\mathbf{x}$ , by Proposition 16.3.4 and Theorem 16.3.2 (a). Does that make it an operator norm?

Solution. No. Being compatible with a vector norm — satisfying $\left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ — is weaker than being induced by it. The induced norm is the smallest constant that works (Theorem 16.3.2 (a)), and for $\mathbf{A} = \mathbf{I}_n$ with $n \ge 2$ the smallest constant is $1$ while $\left\| \mathbf{I}_n \right\|_F = \sqrt n$ . Compatibility says the number is big enough; being induced says it is exactly right.

Where this leaves us: we have a supply of matrix norms (Definition 16.3.1), among them a distinguished family, the induced ones (Definition 16.3.2), and inside that family three that are computable (Theorem 16.3.3). The next section asks which quantity all of these norms are simultaneously bounding from above, and finds that the answer is the spectral radius.

16.3.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a matrix norm on $M_n(F)$ , and define the operator norm induced by a vector norm.
(b) State the three formulas of Theorem 16.3.3.
(c) Which analysis facts make Definition 16.3.2 legitimate, and where is each used?
(d) Determine whether the following statement is correct, and justify your answer: every matrix norm on $M_n(\mathbb{R})$ is the operator norm induced by some norm on $\mathbb{R}^n$ .
(e) Determine whether the following statement is correct, and justify your answer: for every $\mathbf{A} \in M_n(F)$ and every operator norm, $\left\| \mathbf{A}^2 \right\| = \left\| \mathbf{A} \right\|^2$ .

Solution.

(a) A matrix norm is a norm on the vector space $M_n(F)$ that also satisfies $\left\| \mathbf{A}\mathbf{B} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{B} \right\|$ for all $\mathbf{A}, \mathbf{B}$ (Definition 16.3.1). Given norms on $F^n$ and $F^m$ , the operator norm of $\mathbf{A} \in M_{m \times n}(F)$ is $\left\| \mathbf{A} \right\| = \max\{\left\| \mathbf{A}\mathbf{x} \right\| : \left\| \mathbf{x} \right\| = 1\}$ (Definition 16.3.2).
(b) $\left\| \mathbf{A} \right\|_1$ is the largest absolute column sum, $\left\| \mathbf{A} \right\|_{\infty}$ the largest absolute row sum, and $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ .
(c) Two: the compactness of closed bounded sets, fact (A3) of the chapter introduction, used for the unit sphere $S$ ; and the extreme value theorem, fact (A4), used for $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|$ . Both enter through Corollary 16.2.5, quoted in Step 3 of Lemma 16.3.1. The continuity needed for the second is proved, not imported, and rests on Theorem 16.2.2 and Lemma 16.1.1.
(d) Incorrect. The Frobenius norm is a matrix norm, and $\left\| \mathbf{I}_n \right\|_F = \sqrt n \ne 1$ for $n \ge 2$ , whereas every operator norm has $\left\| \mathbf{I}_n \right\| = 1$ by Theorem 16.3.2 (c).
(e) Incorrect; only $\le$ holds, by Theorem 16.3.2 (d). Take $\mathbf{A} = \begin{psmallmatrix} 0 & 1 \\ 0 & 0 \end{psmallmatrix}$ , for which $\left\| \mathbf{A} \right\|_2 = 1$ but $\mathbf{A}^2 = 0$ , so $\left\| \mathbf{A}^2 \right\|_2 = 0$ .

B. Practice

Exercise (B1: Four numbers for one matrix)

Let $\mathbf{A} = \begin{pmatrix} 2 & -1 \\ 2 & 2 \end{pmatrix} \in M_2(\mathbb{R})$ . Compute $\left\| \mathbf{A} \right\|_1$ , $\left\| \mathbf{A} \right\|_{\infty}$ , $\left\| \mathbf{A} \right\|_F$ and $\left\| \mathbf{A} \right\|_2$ , and verify that $\left\| \mathbf{A} \right\|_2 \le \left\| \mathbf{A} \right\|_F$ .

Solution. Absolute column sums: $2 + 2 = 4$ and $1 + 2 = 3$ , so $\left\| \mathbf{A} \right\|_1 = 4$ . Absolute row sums: $2 + 1 = 3$ and $2 + 2 = 4$ , so $\left\| \mathbf{A} \right\|_{\infty} = 4$ . Also $\left\| \mathbf{A} \right\|_F = \sqrt{4 + 1 + 4 + 4} = \sqrt{13}$ .

For the spectral norm,

$\mathbf{A}^{\top}\mathbf{A} = \begin{pmatrix} 8 & 2 \\ 2 & 5 \end{pmatrix},$

with trace $13$ and determinant $40 - 4 = 36$ , so its eigenvalues solve $\lambda^2 - 13\lambda + 36 = 0$ , giving $\lambda = 9$ and $\lambda = 4$ . Hence $\sigma_1 = 3$ , $\sigma_2 = 2$ and $\left\| \mathbf{A} \right\|_2 = 3$ by Theorem 16.3.3 (c). Finally $3 \le \sqrt{13}$ , as Proposition 16.3.4 requires; the inequality is strict because $\operatorname{rank}\mathbf{A} = 2$ .

Exercise (B2: A rank-one matrix)

Let $\mathbf{u} \in F^m$ and $\mathbf{v} \in F^n$ be non-zero and put $\mathbf{A} = \mathbf{u}\mathbf{v}^{*}$ .

(a) Prove that $\left\| \mathbf{A} \right\|_2 = \left\| \mathbf{u} \right\|_2\left\| \mathbf{v} \right\|_2$ .
(b) Verify the formula for $\mathbf{u} = (1, 2)$ and $\mathbf{v} = (2, -1)$ in $\mathbb{R}^2$ by computing $\sigma_1(\mathbf{A})$ directly.

Solution.

(a) For $\mathbf{x} \in F^n$ we have $\mathbf{A}\mathbf{x} = (\mathbf{v}^{*}\mathbf{x})\mathbf{u}$ , so $\left\| \mathbf{A}\mathbf{x} \right\|_2 = \lvert\mathbf{v}^{*}\mathbf{x}\rvert\,\left\| \mathbf{u} \right\|_2$ . By Theorem 11.1.5, $\lvert\mathbf{v}^{*}\mathbf{x}\rvert = \lvert\langle \mathbf{x}, \mathbf{v} \rangle\rvert \le \left\| \mathbf{x} \right\|_2\left\| \mathbf{v} \right\|_2$ , with equality when $\mathbf{x} = \mathbf{v}/\left\| \mathbf{v} \right\|_2$ . Hence for unit $\mathbf{x}$ the quantity $\left\| \mathbf{A}\mathbf{x} \right\|_2$ is at most $\left\| \mathbf{u} \right\|_2\left\| \mathbf{v} \right\|_2$ and attains that value, so $\left\| \mathbf{A} \right\|_2 = \left\| \mathbf{u} \right\|_2\left\| \mathbf{v} \right\|_2$ .
(b) Here $\mathbf{A} = \begin{psmallmatrix} 2 & -1 \\ 4 & -2 \end{psmallmatrix}$ and $\mathbf{A}^{\top}\mathbf{A} = \begin{psmallmatrix} 20 & -10 \\ -10 & 5\end{psmallmatrix}$ , of trace $25$ and determinant $100 - 100 = 0$ . So the eigenvalues are $25$ and $0$ , giving $\sigma_1 = 5$ . And $\left\| \mathbf{u} \right\|_2\left\| \mathbf{v} \right\|_2 = \sqrt5 \cdot \sqrt5 = 5$ , in agreement. Note also $\left\| \mathbf{A} \right\|_F = 5 = \left\| \mathbf{A} \right\|_2$ , as Proposition 16.3.4 predicts for a rank-one matrix.

Exercise (B3: The star trick)

Let $\mathbf{A} \in M_{m \times n}(F)$ . Prove that $\left\| \mathbf{A}^{*}\mathbf{A} \right\|_2 = \left\| \mathbf{A} \right\|_2^2$ . Hint: the eigenvalues of $\mathbf{A}^{*}\mathbf{A}$ .

Solution. By Definition 13.8.1 the eigenvalues of $\mathbf{A}^{*}\mathbf{A}$ are $\sigma_1^2 \ge \dots \ge \sigma_n^2 \ge 0$ , where the $\sigma_i$ are the singular values of $\mathbf{A}$ padded with zeros if $n > m$ . The matrix $\mathbf{A}^{*}\mathbf{A}$ is positive semidefinite, hence Hermitian, so by Corollary 12.4.3 it is $\mathbf{W}\mathbf{D}\mathbf{W}^{*}$ with $\mathbf{W}$ unitary and $\mathbf{D} = \operatorname{diag}(\sigma_1^2, \dots, \sigma_n^2)$ . Then $(\mathbf{A}^{*}\mathbf{A})^{*}(\mathbf{A}^{*}\mathbf{A}) = \mathbf{W}\mathbf{D}^2\mathbf{W}^{*}$ , whose eigenvalues are $\sigma_i^4$ , so the singular values of $\mathbf{A}^{*}\mathbf{A}$ are the $\sigma_i^2$ and its largest is $\sigma_1^2$ . By Theorem 16.3.3 (c), applied to $\mathbf{A}^{*}\mathbf{A}$ and then to $\mathbf{A}$ ,

$\left\| \mathbf{A}^{*}\mathbf{A} \right\|_2 = \sigma_1^2 = \left\| \mathbf{A} \right\|_2^2 .$

This proves the claim. Notice that it is an equality, whereas Theorem 16.3.2 (d) alone would give only $\left\| \mathbf{A}^{*}\mathbf{A} \right\|_2 \le \left\| \mathbf{A}^{*} \right\|_2\left\| \mathbf{A} \right\|_2$ .

C. Going deeper

Exercise (C1: The spectral norm between the other two)

Let $\mathbf{A} \in M_{m \times n}(F)$ .

(a) Prove that $\left\| \mathbf{A} \right\|_2 \le \sqrt{\left\| \mathbf{A} \right\|_1\left\| \mathbf{A} \right\|_{\infty}}$ .
(b) Check the inequality on the matrix of Example (One matrix, four numbers), and say how far it is from equality.

Hint for (a): apply Theorem 11.1.5 to the splitting $\lvert a_{ij}\rvert = \lvert a_{ij}\rvert^{1/2}\cdot\lvert a_{ij}\rvert^{1/2}\lvert x_j\rvert$ inside one row.

Solution.

(a) Write $C = \left\| \mathbf{A} \right\|_1$ and $R = \left\| \mathbf{A} \right\|_{\infty}$ for the largest column and row sums (Theorem 16.3.3). Let $\left\| \mathbf{x} \right\|_2 = 1$ . For each $i$ , Theorem 11.1.5 applied to the vectors with entries $\lvert a_{ij}\rvert^{1/2}$ and $\lvert a_{ij}\rvert^{1/2}\lvert x_j\rvert$ gives
$\Bigl\lvert\sum_j a_{ij}x_j\Bigr\rvert^2 \le \Bigl(\sum_j \lvert a_{ij}\rvert\Bigr) \Bigl(\sum_j \lvert a_{ij}\rvert\,\lvert x_j\rvert^2\Bigr) \le R\sum_j \lvert a_{ij}\rvert\,\lvert x_j\rvert^2 .$

Summing over $i$ and exchanging the two finite sums,

$\left\| \mathbf{A}\mathbf{x} \right\|_2^2 \le R\sum_j \lvert x_j\rvert^2\sum_i \lvert a_{ij}\rvert \le RC\sum_j\lvert x_j\rvert^2 = RC .$

Taking the maximum over unit $\mathbf{x}$ gives $\left\| \mathbf{A} \right\|_2^2 \le RC$ , as claimed.
(b) There $\left\| \mathbf{A} \right\|_1 = 7$ and $\left\| \mathbf{A} \right\|_{\infty} = 9$ , so the bound is $\sqrt{63} \approx 7.937$ , while $\left\| \mathbf{A} \right\|_2 = 3\sqrt5 \approx 6.708$ . The bound overestimates by about 18 per cent. It is sharp in general: for $\mathbf{A} = \mathbf{I}_n$ all three numbers are $1$ .

Exercise (C2: Repairing the entrywise maximum)

For $\mathbf{A} \in M_n(F)$ let $N(\mathbf{A}) = \max_{i,j}\lvert a_{ij}\rvert$ , as in Example (The entrywise maximum is not submultiplicative).

(a) Prove that $N(\mathbf{A}\mathbf{B}) \le nN(\mathbf{A})N(\mathbf{B})$ , and deduce that $\mathbf{A} \mapsto nN(\mathbf{A})$ is a matrix norm.
(b) Deduce that $nN(\cdot)$ is not an operator norm for any $n \ge 2$ .
(c) Explain why (a) and (b) together show that submultiplicativity and $\left\| \mathbf{I} \right\| = 1$ are independent requirements.

Solution.

(a) For all $i, j$ ,
$\lvert(\mathbf{A}\mathbf{B})_{ij}\rvert = \Bigl\lvert\sum_k a_{ik}b_{kj}\Bigr\rvert \le \sum_k \lvert a_{ik}\rvert\,\lvert b_{kj}\rvert \le n\,N(\mathbf{A})N(\mathbf{B}),$

so $N(\mathbf{A}\mathbf{B}) \le nN(\mathbf{A})N(\mathbf{B})$ . Put $\left\| \mathbf{A} \right\| = nN(\mathbf{A})$ . It is a norm, being a positive multiple of the norm $N$ , and

$\left\| \mathbf{A}\mathbf{B} \right\| = nN(\mathbf{A}\mathbf{B}) \le n^2N(\mathbf{A})N(\mathbf{B}) = \left\| \mathbf{A} \right\|\,\left\| \mathbf{B} \right\| .$
(b) $\left\| \mathbf{I}_n \right\| = nN(\mathbf{I}_n) = n \ne 1$ for $n \ge 2$ , while every operator norm gives the identity the value $1$ (Theorem 16.3.2 (c)).
(c) $N$ itself is a norm with $N(\mathbf{I}_n) = 1$ that is not submultiplicative; $nN$ is submultiplicative with $nN(\mathbf{I}_n) = n$ . So neither property implies the other, and an operator norm is precisely a matrix norm that also passes the identity test — a necessary condition which, as $\left\| \cdot \right\|_F$ already showed, is still not sufficient on its own for $n$ large.

Exercise (C3: When is a bound an equality?)

Let $\mathbf{A} \in M_{m \times n}(F)$ be non-zero.

(a) Prove that $\left\| \mathbf{A} \right\|_2 = \left\| \mathbf{A} \right\|_F$ if and only if $\operatorname{rank}\mathbf{A} = 1$ .
(b) Give an example with $m = n = 2$ where $\left\| \mathbf{A} \right\|_F = \sqrt2\,\left\| \mathbf{A} \right\|_2$ , the worst case allowed by Proposition 16.3.4.
(c) Is there a non-zero $\mathbf{A}$ with $\left\| \mathbf{A} \right\|_F < \left\| \mathbf{A} \right\|_2$ ? Justify your answer.

Solution.

(a) This is the equality case of Proposition 16.3.4, proved there: $\left\| \mathbf{A} \right\|_F^2 = \sum_i\sigma_i^2$ and $\left\| \mathbf{A} \right\|_2^2 = \sigma_1^2$ , so the two agree exactly when $\sigma_i = 0$ for every $i \ge 2$ , which by Theorem 13.8.1 says $\operatorname{rank}\mathbf{A} = 1$ .
(b) Take $\mathbf{A} = \mathbf{I}_2$ . Its singular values are $1, 1$ , so $\left\| \mathbf{A} \right\|_2 = 1$ and $\left\| \mathbf{A} \right\|_F = \sqrt2$ . Any matrix with two equal non-zero singular values does the same, for instance any $2 \times 2$ unitary matrix.
(c) No. $\left\| \mathbf{A} \right\|_2 = \sigma_1 \le \bigl(\sum_i \sigma_i^2\bigr)^{1/2} = \left\| \mathbf{A} \right\|_F$ always, since every term of the sum is non-negative. The Frobenius norm counts all the singular values and the spectral norm only the largest, so the Frobenius norm can never be the smaller of the two.