4.12. Matrix Norms

This section reviews various matrix norms on the vector space of complex matrices over the field of complex numbers $({\mathbb{C}}^{m\times n},\mathbb{C})$.

We know $({\mathbb{C}}^{m\times n},\mathbb{C})$ is a finite dimensional vector space with dimension $mn$. We will usually refer to it as ${\mathbb{C}}^{m\times n}$.

Matrix norms will follow the usual definition of norms for a vector space.

Definition 4.139 (Matrix norm)

A function $\Vert \cdot \Vert :{\mathbb{C}}^{m\times n}\to \mathbb{R}$ is called a matrix norm on ${\mathbb{C}}^{m\times n}$ if for all $\mathbf{A},\mathbf{B}\in {\mathbb{C}}^{m\times n}$ and all $\alpha \in \mathbb{C}$ it satisfies the following

• [Positivity]

  $$\Vert \mathbf{A}\Vert \ge 0$$

  with $\Vert \mathbf{A}\Vert =0⟺\mathbf{A}=\mathbf{O}$.

• [Homogeneity]

  $$\Vert \alpha \mathbf{A}\Vert =|\alpha |\Vert \mathbf{A}\Vert .$$

• [Triangle inequality]

  $$\Vert \mathbf{A}+\mathbf{B}\Vert \le \Vert \mathbf{A}\Vert +\Vert \mathbf{B}\Vert .$$

We recall some of the standard results on finite dimensional normed vector spaces.

All matrix norms are equivalent. Let $\Vert \cdot \Vert$ and $\Vert \cdot {\Vert }^{\prime }$ be two different matrix norms on ${\mathbb{C}}^{m\times n}$. Then there exist two constants $a$ and $b$ such that the following holds

$$a\Vert \mathbf{A}\Vert \le \Vert \mathbf{A}{\Vert }^{\prime }\le b\Vert A\Vert \mathrm{\forall }\mathbf{A}\in {\mathbb{C}}^{m\times n}.$$

A matrix norm is a continuous function $\Vert \cdot \Vert :{\mathbb{C}}^{m\times n}\to \mathbb{R}$.

4.12.1. Norms like ${\ell }_p$ on Complex Vector Space

Following norms are quite like ${\ell }_p$ norms on finite dimensional complex vector space ${\mathbb{C}}^n$. They are developed by the fact that the matrix vector space ${\mathbb{C}}^{m\times n}$ has one to one correspondence with the complex vector space ${\mathbb{C}}^{mn}$.

Definition 4.140 (Sum norm)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and $\mathbf{A}=[a_{ij}]$.

Matrix sum norm is defined as

$$\Vert \mathbf{A}{\Vert }_S=\sum _{i=1}^m\sum _{j=1}^n|a_{ij}|$$

Definition 4.141 (Frobenius norm)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and $\mathbf{A}=[a_{ij}]$.

Matrix Frobenius norm is defined as

$$\Vert \mathbf{A}{\Vert }_F={\left(\sum _{i=1}^m\sum _{j=1}^n|a_{ij}{|}^2\right)}^{\frac{1}{2}}.$$

Definition 4.142 (Max norm)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and $\mathbf{A}=[a_{ij}]$.

Matrix Max norm is defined as

$$\begin{array}{r}\Vert \mathbf{A}{\Vert }_M=\underset{\begin{array}{c}1\le i\le m\\ 1\le j\le n\end{array}}{max}|a_{ij}|.\end{array}$$

4.12.2. Properties of Frobenius Norm

We now prove some elementary properties of Frobenius norm.

Lemma 4.86

The Frobenius norm of a matrix is equal to the Frobenius norm of its Hermitian transpose.

$$\Vert {\mathbf{A}}^H{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

Proof. This is valid since the norm involves only the absolute values of entries in the matrix.

1. Let

   $$\mathbf{A}=[a_{ij}].$$

2. Then

   $${\mathbf{A}}^H=[\overline{a_{ji}}]$$

3. Then

   $$\begin{gathered} \begin{array}{r}\Vert {\mathbf{A}}^H{\Vert }_F^2=\left(\sum _{j=1}^n\sum _{i=1}^m|\overline{a_{ij}}{|}^2\right)=\left(\sum _{i=1}^m \\ \sum _{j=1}^n|a_{ij}{|}^2\right)=\Vert \mathbf{A}{\Vert }_F^2.\end{array} \end{gathered}$$

4. Now

   $$\Vert {\mathbf{A}}^H{\Vert }_F^2=\Vert \mathbf{A}{\Vert }_F^2⟹\Vert {\mathbf{A}}^H{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

Lemma 4.87 (Expansion in squared norms of columns)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ be written as a row of column vectors

$$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{a}}_1& \dots & {\mathbf{a}}_n\end{array}\right].$$

Then

$$\Vert \mathbf{A}{\Vert }_F^2=\sum _{j=1}^n\Vert {\mathbf{a}}_j{\Vert }_2^2.$$

Proof. We note that

$$\Vert {\mathbf{a}}_j{\Vert }_2^2=\sum _{i=1}^m\Vert a_{ij}{\Vert }_2^2.$$

Now

$$\Vert \mathbf{A}{\Vert }_F^2=\left(\sum _{i=1}^m\sum _{j=1}^n|a_{ij}{|}^2\right)=\left(\sum _{j=1}^n\left(\sum _{i=1}^m|a_{ij}{|}^2\right)\right)=(\sum _{j=1}^n\Vert {\mathbf{a}}_j{\Vert }_2^2).$$

We thus showed that that the square of the Frobenius norm of a matrix is nothing but the sum of squares of ${\ell }_2$ norms of its columns.

Lemma 4.88

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ be written as a column of row vectors

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{c}{\underset{―}{\mathbf{a}}}^1\\ ⋮\\ {\underset{―}{\mathbf{a}}}^m\end{array}\right].\end{array}$$

Then

$$\Vert \mathbf{A}{\Vert }_F^2=\sum _{i=1}^m\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_2^2.$$

Proof. We note that

$$\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_2^2=\sum _{j=1}^n\Vert a_{ij}{\Vert }_2^2.$$

Now

$$\Vert \mathbf{A}{\Vert }_F^2=\left(\sum _{i=1}^m\sum _{j=1}^n|a_{ij}{|}^2\right)=\sum _{i=1}^m\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_2^2.$$

We now consider how the Frobenius norm is affected with the action of unitary matrices.

1. Let $\mathbf{A}$ be any arbitrary matrix in ${\mathbb{C}}^{m\times n}$.

2. Let $\mathbf{U}$ be some unitary matrices in ${\mathbb{C}}^{m\times m}$.

3. Let $\mathbf{V}$ be some unitary matrices in ${\mathbb{C}}^{n\times n}$.

We present our first result that multiplication with unitary matrices doesn’t change Frobenius norm of a matrix.

Theorem 4.141

The Frobenius norm of a matrix is invariant to pre or post multiplication by a unitary matrix. i.e.

$$\Vert \mathbf{U}\mathbf{A}{\Vert }_F=\Vert \mathbf{A}{\Vert }_F$$

and

$$\Vert \mathbf{A}\mathbf{V}{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

Proof. We can write $\mathbf{A}$ as

$$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{a}}_1& \dots & {\mathbf{a}}_n\end{array}\right].$$

So

$$\mathbf{U}\mathbf{A}=\left[\begin{array}{ccc}\mathbf{U}{\mathbf{a}}_1& \dots & \mathbf{U}{\mathbf{a}}_n\end{array}\right].$$

Then applying Lemma 4.87 clearly

$$\Vert \mathbf{U}\mathbf{A}{\Vert }_F^2=\sum _{j=1}^n\Vert \mathbf{U}{\mathbf{a}}_j{\Vert }_2^2.$$

But we know that unitary matrices are norm preserving. Hence

$$\Vert \mathbf{U}{\mathbf{a}}_j{\Vert }_2^2=\Vert {\mathbf{a}}_j{\Vert }_2^2.$$

Thus

$$\Vert \mathbf{U}\mathbf{A}{\Vert }_F^2=\sum _{j=1}^n\Vert {\mathbf{a}}_j{\Vert }_2^2=\Vert \mathbf{A}{\Vert }_F^2$$

which implies

$$\Vert \mathbf{U}\mathbf{A}{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

Similarly writing $\mathbf{A}$ as

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{c}{\mathbf{r}}_1\\ ⋮\\ {\mathbf{r}}_m\end{array}\right].\end{array}$$

we have

$$\begin{array}{r}\mathbf{A}\mathbf{V}=\left[\begin{array}{c}{\mathbf{r}}_1\mathbf{V}\\ ⋮\\ {\mathbf{r}}_m\mathbf{V}\end{array}\right].\end{array}$$

Then applying Lemma 4.88 clearly

$$\Vert \mathbf{A}\mathbf{V}{\Vert }_F^2=\sum _{i=1}^m\Vert {\mathbf{r}}_i\mathbf{V}{\Vert }_2^2.$$

But we know that unitary matrices are norm preserving. Hence

$$\Vert {\mathbf{r}}_i\mathbf{V}{\Vert }_2^2=\Vert {\mathbf{r}}_i{\Vert }_2^2.$$

Thus

$$\Vert \mathbf{A}\mathbf{V}{\Vert }_F^2=\sum _{i=1}^m\Vert {\mathbf{r}}_i{\Vert }_2^2=\Vert \mathbf{A}{\Vert }_F^2$$

which implies

$$\Vert \mathbf{A}\mathbf{V}{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

An alternative approach for the 2nd part of the proof using the first part is just one line

$$\Vert \mathbf{A}\mathbf{V}{\Vert }_F=\Vert (\mathbf{A}\mathbf{V}{)}^H{\Vert }_F=\Vert {\mathbf{V}}^H{\mathbf{A}}^H{\Vert }_F=\Vert {\mathbf{A}}^H{\Vert }_F=\Vert \mathbf{A}{\Vert }_F.$$

In above we use Lemma 4.86 and the fact that $\mathbf{V}$ is a unitary matrix implies that ${\mathbf{V}}^H$ is also a unitary matrix. We have already shown that pre multiplication by a unitary matrix preserves Frobenius norm.

Theorem 4.142 (Consistency of Frobenius norm)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and $\mathbf{B}\in {\mathbb{C}}^{n\times p}$ be two matrices. Then the Frobenius norm of their product is less than or equal to the product of Frobenius norms of the matrices themselves. i.e.

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_F\le \Vert \mathbf{A}{\Vert }_F\Vert \mathbf{B}{\Vert }_F.$$

Proof. We can write $\mathbf{A}$ as

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{c}{\mathbf{a}}_1^T\\ ⋮\\ {\mathbf{a}}_m^T\end{array}\right]\end{array}$$

where ${\mathbf{a}}_i$ are $m$ column vectors corresponding to rows of $\mathbf{A}$. Similarly we can write $\mathbf{B}$ as

$$\mathbf{B}=\left[\begin{array}{ccc}{\mathbf{b}}_1& \dots & {\mathbf{b}}_p\end{array}\right]$$

where ${\mathbf{b}}_i$ are column vectors corresponding to columns of $\mathbf{B}$.

Then

$$\begin{array}{r}\mathbf{A}\mathbf{B}=\left[\begin{array}{c}{\mathbf{a}}_1^T\\ ⋮\\ {\mathbf{a}}_m^T\end{array}\right]\left[\begin{array}{ccc}{\mathbf{b}}_1& \dots & {\mathbf{b}}_p\end{array}\right]=\left[\begin{array}{ccc}{\mathbf{a}}_1^T{\mathbf{b}}_1& \dots & {\mathbf{a}}_1^T{\mathbf{b}}_p\\ ⋮& \ddots & ⋮\\ {\mathbf{a}}_m^T{\mathbf{b}}_1& \dots & {\mathbf{a}}_m^T{\mathbf{b}}_p\end{array}\right]=\left[\begin{array}{c}{\mathbf{a}}_i^T{\mathbf{b}}_j\end{array}\right].\end{array}$$

Now looking carefully

$${\mathbf{a}}_i^T{\mathbf{b}}_j=⟨{\mathbf{a}}_i,\overline{{\mathbf{b}}_j}⟩.$$

Applying the Cauchy-Schwartz inequality we have

$$|⟨{\mathbf{a}}_i,\overline{{\mathbf{b}}_j}⟩{|}^2\le \Vert {\mathbf{a}}_i{\Vert }_2^2\Vert \overline{{\mathbf{b}}_j}{\Vert }_2^2=\Vert {\mathbf{a}}_i{\Vert }_2^2\Vert {\mathbf{b}}_j{\Vert }_2^2.$$

Now

$$\begin{array}{rl}\Vert \mathbf{A}\mathbf{B}{\Vert }_F^2& =\sum _{i=1}^m\sum _{j=1}^p|{\mathbf{a}}_i^T{\mathbf{b}}_j{|}^2\\ & \le \sum _{i=1}^m\sum _{j=1}^p\Vert {\mathbf{a}}_i{\Vert }_2^2\Vert {\mathbf{b}}_j{\Vert }_2^2\\ & =(\sum _{i=1}^m\Vert {\mathbf{a}}_i{\Vert }_2^2)(\sum _{j=1}^p\Vert {\mathbf{b}}_j{\Vert }_2^2)\\ & =\Vert \mathbf{A}{\Vert }_F^2\Vert \mathbf{B}{\Vert }_F^2\end{array}$$

which implies

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_F\le \Vert \mathbf{A}{\Vert }_F\Vert \mathbf{B}{\Vert }_F$$

by taking square roots on both sides.

Corollary 4.28

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and let $\mathbf{x}\in {\mathbb{C}}^n$. Then

$$\Vert \mathbf{A}\mathbf{x}{\Vert }_2\le \Vert \mathbf{A}{\Vert }_F\Vert \mathbf{x}{\Vert }_2.$$

Proof. We note that Frobenius norm for a column matrix is same as ${\ell }_2$ norm for corresponding column vector. i.e.

$$\Vert \mathbf{x}{\Vert }_F=\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n.$$

Now applying Theorem 4.142 we have

$$\Vert \mathbf{A}\mathbf{x}{\Vert }_2=\Vert \mathbf{A}\mathbf{x}{\Vert }_F\le \Vert \mathbf{A}{\Vert }_F\Vert \mathbf{x}{\Vert }_F=\Vert \mathbf{A}{\Vert }_F\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n.$$

It turns out that Frobenius norm is intimately related to the singular value decomposition of a matrix.

Lemma 4.89 (Frobenius norm and singular values)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$. Let the singular value decomposition of $\mathbf{A}$ be given by

$$\mathbf{A}=\mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^H.$$

Let the singular values of $\mathbf{A}$ be ${\sigma }_1,\dots ,{\sigma }_k$ where $k=min(m,n)$. Then

$$\Vert \mathbf{A}{\Vert }_F=\sqrt{\sum _{i=1}^k{\sigma }_i^2}.$$

Proof. This comes from the invariance of Frobenius norm with unitary transformations.

$$\mathbf{A}=\mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^H⟹\Vert A{\Vert }_F=\Vert \mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^H{\Vert }_F.$$

But

$$\Vert \mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^H{\Vert }_F=\Vert \mathrm{\Sigma }{\mathbf{V}}^H{\Vert }_F=\Vert \mathrm{\Sigma }{\Vert }_F$$

since $\mathbf{U}$ and $\mathbf{V}$ are unitary matrices (see Theorem 4.141 ). Now the only nonzero terms in $\mathrm{\Sigma }$ are the singular values. Hence

$$\Vert \mathbf{A}{\Vert }_F=\Vert \mathrm{\Sigma }{\Vert }_F=\sqrt{\sum _{i=1}^k{\sigma }_i^2}.$$

4.12.3. Consistency of a Matrix Norm

Definition 4.143 (Consistent matrix norm)

A matrix norm $\Vert \cdot \Vert$ is called consistent on ${\mathbb{C}}^{n\times n}$ if

(4.19)$$\Vert \mathbf{A}\mathbf{B}\Vert \le \Vert \mathbf{A}\Vert \Vert \mathbf{B}\Vert$$

holds true for all $\mathbf{A},\mathbf{B}\in {\mathbb{C}}^{n\times n}$. A matrix norm $\Vert \cdot \Vert$ is called consistent if it is defined on ${\mathbb{C}}^{m\times n}$ for all $m,n\in \mathbb{N}$ and (4.19) holds for all matrices $\mathbf{A},\mathbf{B}$ for which the product $\mathbf{A}\mathbf{B}$ is defined.

A consistent matrix norm is also known as a sub-multiplicative norm.

With this definition and results in Theorem 4.142 we can see that Frobenius norm is consistent.

4.12.4. Subordinate Matrix Norm

A matrix operates on vectors from one space to generate vectors in another space. It is interesting to explore the connection between the norm of a matrix and norms of vectors in the domain and co-domain of a matrix.

Definition 4.144

Let $m,n\in \mathbb{N}$ be given. Let $\Vert \cdot {\Vert }_{\alpha }$ be some norm on ${\mathbb{C}}^m$ and $\Vert \cdot {\Vert }_{\beta }$ be some norm on ${\mathbb{C}}^n$. Let $\Vert \cdot \Vert$ be some norm on matrices in ${\mathbb{C}}^{m\times n}$. We say that $\Vert \cdot \Vert$ is subordinate to the vector norms $\Vert \cdot {\Vert }_{\alpha }$ and $\Vert \cdot {\Vert }_{\beta }$ if

$$\Vert \mathbf{A}\mathbf{x}{\Vert }_{\alpha }\le \Vert \mathbf{A}\Vert \Vert \mathbf{x}{\Vert }_{\beta }$$

for all $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and for all $\mathbf{x}\in {\mathbb{C}}^n$. In other words the length of the vector doesn’t increase by the operation of $\mathbf{A}$ beyond a factor given by the norm of the matrix itself.

If $\Vert \cdot {\Vert }_{\alpha }$ and $\Vert \cdot {\Vert }_{\beta }$ are same then we say that $\Vert \cdot \Vert$ is subordinate to the vector norm $\Vert \cdot {\Vert }_{\alpha }$.

We have shown earlier in Corollary 4.28 that Frobenius norm is subordinate to Euclidean norm.

4.12.5. Operator Norm

We now consider the maximum factor by which a matrix $\mathbf{A}$ can increase the length of a vector.

Definition 4.145 (Operator norm)

Let $m,n\in \mathbb{N}$ be given. Let $\Vert \cdot {\Vert }_{\alpha }$ be some norm on ${\mathbb{C}}^n$ and $\Vert \cdot {\Vert }_{\beta }$ be some norm on ${\mathbb{C}}^m$. For $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ we define

$$\Vert \mathbf{A}\Vert \triangleq \Vert \mathbf{A}{\Vert }_{\alpha \to \beta }\triangleq \underset{\mathbf{x}\ne 0}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

The term $\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}$ represents the factor with which the length of $\mathbf{x}$ increased by operation of $\mathbf{A}$. We simply pick up the maximum value of such scaling factors over all nonzero $\mathbf{x}$.

The norm as defined above is known as $(\alpha \to \beta )$ operator norm, the $(\alpha \to \beta )$-norm, or simply the $\alpha$-norm if $\alpha =\beta$.

We need to verify that this definition satisfies all properties of a norm.

Nonnegativity

1. Clearly if $\mathbf{A}=\mathbf{O}$ then $\mathbf{A}\mathbf{x}=\mathbf{0}$ always, hence $\Vert \mathbf{A}\Vert =0$.

2. Conversely, if $\Vert \mathbf{A}\Vert =0$ then $\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }=0\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n$.

3. Hence $\mathbf{A}\mathbf{x}=\mathbf{0}$ for every $\mathbf{x}\in {\mathbb{C}}^n$.

4. In particular this is true for the unit vectors ${\mathbf{e}}_i\in {\mathbb{C}}^n$.

5. The $i$-th column of $\mathbf{A}$ is given by $\mathbf{A}{\mathbf{e}}_i$ which is $\mathbf{0}$.

6. Thus each column in $\mathbf{A}$ is $\mathbf{0}$.

7. Hence $\mathbf{A}=\mathbf{O}$.

Homogeneity

1. Consider $c\in \mathbb{C}$.

2. Then

   $$\Vert c\mathbf{A}\Vert =\underset{\mathbf{x}\ne 0}{max}\frac{\Vert c\mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}=|c|\underset{\mathbf{x}\ne 0}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}=|c|\Vert \mathbf{A}\Vert .$$

We now present some useful observations on operator norm before we can prove triangle inequality for operator norm.

1. For any $\mathbf{x}\in \ker (\mathbf{A})$, $\mathbf{A}\mathbf{x}=\mathbf{0}$ hence we only need to consider vectors which don’t belong to the kernel of $\mathbf{A}$.

2. Thus we can write

   $$\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }=\underset{\mathbf{x}\notin \ker (\mathbf{A})}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

3. We also note that

   $$\frac{\Vert \mathbf{A}c\mathbf{x}{\Vert }_{\beta }}{\Vert c\mathbf{x}{\Vert }_{\alpha }}=\frac{|c|\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{|c|\Vert \mathbf{x}{\Vert }_{\alpha }}=\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}\mathrm{\forall }c\ne 0,\mathbf{x}\ne \mathbf{0}.$$

4. Thus, it is sufficient to find the maximum on unit norm vectors:

   $$\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }=\underset{\Vert \mathbf{x}{\Vert }_{\alpha }=1}{max}\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }.$$

5. Note that since $\Vert \mathbf{x}{\Vert }_{\alpha }=1$ hence the term in denominator goes away.

Lemma 4.90 (Operator norm is subordinate)

The $(\alpha \to \beta )$-operator norm is subordinate to vector norms $\Vert \cdot {\Vert }_{\alpha }$ and $\Vert \cdot {\Vert }_{\beta }$. i.e.

$$\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }\le \Vert \mathbf{A}{\Vert }_{\alpha \to \beta }\Vert \mathbf{x}{\Vert }_{\alpha }.$$

Proof. For $\mathbf{x}=\mathbf{0}$ the inequality is trivially satisfied. For $\mathbf{x}\ne \mathbf{0}$, by definition, we have

$$\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }\ge \frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }}{\Vert \mathbf{x}{\Vert }_{\alpha }}⟹\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }\Vert \mathbf{x}{\Vert }_{\alpha }\ge \Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }.$$

Theorem 4.143 (Existence of the maximizer for operator norm)

There exists a vector ${\mathbf{x}}^{\ast }\in {\mathbb{C}}^n$ with unit norm ($\Vert {\mathbf{x}}^{\ast }{\Vert }_{\alpha }=1$) such that

$$\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }=\Vert \mathbf{A}{\mathbf{x}}^{\ast }{\Vert }_{\beta }.$$

Proof. Recall that

$$\Vert \mathbf{A}{\Vert }_{\alpha \to \beta }=\underset{\Vert \mathbf{x}{\Vert }_{\alpha }=1}{max}\Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }.$$

1. The norm function $\Vert \cdot {\Vert }_{\beta }$ is continuous on ${\mathbb{C}}^m$.

2. The mapping $\mathbf{x}\mapsto \mathbf{A}\mathbf{x}$ is continuous.

3. Hence the function $\mathbf{x}\mapsto \Vert \mathbf{A}\mathbf{x}{\Vert }_{\beta }$ is continuous.

4. The set $\{\mathbf{x}\in {\mathbb{C}}^n|\Vert \mathbf{x}{\Vert }_{\alpha }=1\}$ is compact.

5. Hence, the function attains a supremum value over this set.

We are now ready to prove triangle inequality for operator norm.

Lemma 4.91 (Triangle inequality for operator norm)

Operator norm as defined in Definition 4.145 satisfies triangle inequality.

Proof. Let $\mathbf{A}$ and $\mathbf{B}$ be some matrices in ${\mathbb{C}}^{m\times n}$.

1. Consider the operator norm of matrix $\mathbf{A}+\mathbf{B}$.

2. From previous remarks, there exists some vector ${\mathbf{x}}^{\ast }\in {\mathbb{C}}^n$ with $\Vert {\mathbf{x}}^{\ast }{\Vert }_{\alpha }=1$ such that

   $$\Vert \mathbf{A}+\mathbf{B}\Vert =\Vert (\mathbf{A}+\mathbf{B}){\mathbf{x}}^{\ast }{\Vert }_{\beta }.$$

3. Now

   $$\Vert (\mathbf{A}+\mathbf{B}){\mathbf{x}}^{\ast }{\Vert }_{\beta }=\Vert \mathbf{A}{\mathbf{x}}^{\ast }+\mathbf{B}{\mathbf{x}}^{\ast }{\Vert }_{\beta }\le \Vert \mathbf{A}{\mathbf{x}}^{\ast }{\Vert }_{\beta }+\Vert \mathbf{B}{\mathbf{x}}^{\ast }{\Vert }_{\beta }.$$

4. From subordinate property of operator norm, we have

   $$\Vert \mathbf{A}{\mathbf{x}}^{\ast }{\Vert }_{\beta }\le \Vert \mathbf{A}\Vert \Vert {\mathbf{x}}^{\ast }{\Vert }_{\alpha }=\Vert \mathbf{A}\Vert$$

   and

   $$\Vert \mathbf{B}{\mathbf{x}}^{\ast }{\Vert }_{\beta }\le \Vert \mathbf{B}\Vert \Vert {\mathbf{x}}^{\ast }{\Vert }_{\alpha }=\Vert B\Vert$$

   since $\Vert {\mathbf{x}}^{\ast }{\Vert }_{\alpha }=1$.

5. Hence we have

   $$\Vert \mathbf{A}+\mathbf{B}\Vert \le \Vert \mathbf{A}\Vert +\Vert \mathbf{B}\Vert .$$

It turns out that operator norm is also consistent under certain conditions.

Lemma 4.92 (Consistency of operator norm)

Let $\Vert \cdot {\Vert }_{\alpha }$ be defined over all $m\in \mathbb{N}$. Let $\Vert \cdot {\Vert }_{\beta }=\Vert \cdot {\Vert }_{\alpha }$. Then the operator norm

$$\Vert \mathbf{A}{\Vert }_{\alpha }=\underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}$$

is consistent.

Proof. We need to show that

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{\alpha }\le \Vert \mathbf{A}{\Vert }_{\alpha }\Vert \mathbf{B}{\Vert }_{\alpha }.$$

1. Now

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{\alpha }=\underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

2. We note that if $\mathbf{B}\mathbf{x}=\mathbf{0}$, then $\mathbf{A}\mathbf{B}\mathbf{x}=\mathbf{0}$.

3. Hence we can rewrite as

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{\alpha }=\underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

4. Now if $\mathbf{B}\mathbf{x}\ne \mathbf{0}$ then $\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }\ne 0$.

5. Hence

   $$\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}=\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}\frac{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}$$

   and

   $$\underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}\le \underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}\underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

6. Clearly

   $$\Vert \mathbf{B}{\Vert }_{\alpha }=\underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{x}{\Vert }_{\alpha }}.$$

7. Furthermore

   $$\underset{\mathbf{B}\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{B}\mathbf{x}{\Vert }_{\alpha }}{\Vert \mathbf{B}\mathbf{x}{\Vert }_{\alpha }}\le \underset{\mathbf{y}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{y}{\Vert }_{\alpha }}{\Vert \mathbf{y}{\Vert }_{\alpha }}=\Vert \mathbf{A}{\Vert }_{\alpha }.$$

8. Thus we have

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{\alpha }\le \Vert \mathbf{A}{\Vert }_{\alpha }\Vert \mathbf{B}{\Vert }_{\alpha }.$$

4.12.6. $p$-norm for Matrices

We recall the definition of ${\ell }_p$ norms for vectors $\mathbf{x}\in {\mathbb{C}}^n$

$$\begin{array}{r}\Vert \mathbf{x}{\Vert }_p=\{\begin{array}{ll}{\left(\sum _{i=1}^n|\mathbf{x}{|}_i^p\right)}^{\frac{1}{p}}& p\in [1,\mathrm{\infty })\\ \underset{1\le i\le n}{max}|x_i|& p=\mathrm{\infty }\end{array}.\end{array}$$

The operator norms $\Vert \cdot {\Vert }_p$ defined from ${\ell }_p$ vector norms are of specific interest.

Definition 4.146 (Matrix $p$-norm)

The $p$-norm for a matrix $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ is defined as

$$\Vert \mathbf{A}{\Vert }_p\triangleq \underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_p}{\Vert \mathbf{x}{\Vert }_p}=\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert \mathbf{A}\mathbf{x}{\Vert }_p$$

where $\Vert \mathbf{x}{\Vert }_p$ is the standard ${\ell }_p$ norm for vectors in ${\mathbb{C}}^m$ and ${\mathbb{C}}^n$.

As per Lemma 4.92 $p$-norms for matrices are consistent norms. They are also sub-ordinate to ${\ell }_p$ vector norms.

Special cases are considered for $p=1,2$ and $\mathrm{\infty }$.

Theorem 4.144 (Max column sum, max row sum, spectral norms)

Let $\mathbf{A}\in {\mathbb{C}}^{m\times n}$.

For $p=1$ we have

$$\Vert \mathbf{A}{\Vert }_1=\underset{1\le j\le n}{max}\sum _{i=1}^m|a_{ij}|.$$

This is also known as max column sum norm.

For $p=\mathrm{\infty }$ we have

$$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le m}{max}\sum _{j=1}^n|a_{ij}|.$$

This is also known as max row sum norm.

Finally for $p=2$ we have

$$\Vert \mathbf{A}{\Vert }_2={\sigma }_1$$

where ${\sigma }_1$ is the largest singular value of $\mathbf{A}$. This is also known as spectral norm.

Proof. Max column sum norm:

1. Let

   $$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{a}}^1& \dots ,& {\mathbf{a}}^n\end{array}\right].$$

2. Then

   $$\begin{array}{r}\begin{array}{rl}\Vert \mathbf{A}\mathbf{x}{\Vert }_1& ={\Vert \sum _{j=1}^n{x}_j{\mathbf{a}}^j\Vert }_1\\ & \le \sum _{j=1}^n{\Vert x_j{\mathbf{a}}^j\Vert }_1\\ & =\sum _{j=1}^n|x_j|{\Vert {\mathbf{a}}^j\Vert }_1\\ & \le \underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_1\sum _{j=1}^n|x_j|\\ & =\underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_1\Vert \mathbf{x}{\Vert }_1.\end{array}\end{array}$$

3. Thus,

   $$\Vert \mathbf{A}{\Vert }_1=\underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_1}{\Vert \mathbf{x}{\Vert }_1}\le \underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_1$$

   which the maximum column sum.

4. We need to show that this upper bound is indeed an equality.

5. Indeed for any $\mathbf{x}={\mathbf{e}}_j$ where ${\mathbf{e}}_j$ is a unit vector with $1$ in $j$-th entry and 0 elsewhere,

   $$\Vert \mathbf{A}{\mathbf{e}}_j{\Vert }_1=\Vert {\mathbf{a}}^j{\Vert }_1.$$

6. Thus

   $$\Vert \mathbf{A}{\Vert }_1\ge \Vert {\mathbf{a}}^j{\Vert }_1\mathrm{\forall }1\le j\le n.$$

7. Combining the two, we see that

   $$\Vert \mathbf{A}{\Vert }_1=\underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_1.$$

Max row sum norm:

1. For $p=\mathrm{\infty }$, we proceed as follows.

   $$\begin{array}{r}\begin{array}{rl}\Vert \mathbf{A}\mathbf{x}{\Vert }_{\mathrm{\infty }}& =\underset{1\le i\le m}{max}\left|\sum _{j=1}^n{a}_{ij}{x}_j\right|\\ & \le \underset{1\le i\le m}{max}\sum _{j=1}^n|a_{ij}||x_j|\\ & \le \underset{1\le j\le n}{max}|x_j|\underset{1\le i\le m}{max}\sum _{j=1}^n|a_{ij}|\\ & =\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}\underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_1\end{array}\end{array}$$

   where ${\underset{―}{\mathbf{a}}}^i$ are the rows of $\mathbf{A}$.

2. This shows that

   $$\Vert \mathbf{A}\mathbf{x}{\Vert }_{\mathrm{\infty }}\le \underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_1.$$

3. We need to show that this is indeed an equality.

4. Fix an $i=k$ and choose $\mathbf{x}$ such that

   $$x_j=\mathrm{sgn}(a_{kj}).$$

5. Clearly $\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}=1$.

6. Then

   $$\begin{array}{r}\begin{array}{rl}\Vert \mathbf{A}\mathbf{x}{\Vert }_{\mathrm{\infty }}& =\underset{1\le i\le m}{max}\left|\sum _{j=1}^n{a}_{ij}{x}_j\right|\\ & \ge \left|\sum _{j=1}^n{a}_{kj}{x}_j\right|\\ & =\left|\sum _{j=1}^n|a_{kj}|\right|\\ & =\sum _{j=1}^n|a_{kj}|\\ & =\Vert {\underset{―}{\mathbf{a}}}^k{\Vert }_1.\end{array}\end{array}$$

7. Thus,

   $$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}\ge \underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_1.$$

8. Combining the two inequalities we get:

   $$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_1.$$

Spectral norm:

1. Remaining case is for $p=2$.

2. For any vector $\mathbf{x}$ with $\Vert \mathbf{x}{\Vert }_2=1$,

   $$\Vert \mathbf{A}\mathbf{x}{\Vert }_2=\Vert \mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^H\mathbf{x}{\Vert }_2=\Vert \mathbf{U}(\mathrm{\Sigma }{\mathbf{V}}^H\mathbf{x}){\Vert }_2=\Vert \mathrm{\Sigma }{\mathbf{V}}^H\mathbf{x}{\Vert }_2$$

   since ${\ell }_2$ norm is invariant to unitary transformations.

3. Let $\mathbf{v}={\mathbf{V}}^H\mathbf{x}$.

4. Then $\Vert \mathbf{v}{\Vert }_2=\Vert {\mathbf{V}}^H\mathbf{x}{\Vert }_2=\Vert \mathbf{x}{\Vert }_2=1$.

5. Let $k=min(m,n)$.

6. Now

   $$\begin{array}{rl}\Vert \mathbf{A}\mathbf{x}{\Vert }_2& =\Vert \mathrm{\Sigma }\mathbf{v}{\Vert }_2\\ & ={\left(\sum _{j=1}^k|{\sigma }_j{v}_j{|}^2\right)}^{\frac{1}{2}}\\ & \le {\sigma }_1{\left(\sum _{j=1}^k|v_j{|}^2\right)}^{\frac{1}{2}}\\ & ={\sigma }_1\Vert \mathbf{v}{\Vert }_2={\sigma }_1.\end{array}$$

7. This shows that

   $$\Vert \mathbf{A}{\Vert }_2\le {\sigma }_1.$$

8. Now consider some vector $\mathbf{x}$ such that $\mathbf{v}=(1,0,\dots ,0)$.

9. Then

   $$\Vert \mathbf{A}\mathbf{x}{\Vert }_2=\Vert \mathrm{\Sigma }\mathbf{v}{\Vert }_2={\sigma }_1.$$

10. Thus

    $$\Vert \mathbf{A}{\Vert }_2\ge {\sigma }_1.$$

11. Combining the two, we get that $\Vert \mathbf{A}{\Vert }_2={\sigma }_1$.

4.12.7. The $2$-norm

Theorem 4.145

Let $\mathbf{A}\in {\mathbb{C}}^{n\times n}$ have singular values ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n$. Let the eigen values for $\mathbf{A}$ be ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ with $|{\lambda }_1|\ge |{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$. Then the following hold

$$\Vert \mathbf{A}{\Vert }_2={\sigma }_1$$

and if $\mathbf{A}$ is nonsingular, then

$$\Vert {\mathbf{A}}^{-1}{\Vert }_2=\frac{1}{{\sigma }_n}.$$

If $\mathbf{A}$ is symmetric and positive definite, then

$$\Vert \mathbf{A}{\Vert }_2={\lambda }_1$$

and if $\mathbf{A}$ is nonsingular, then

$$\Vert {\mathbf{A}}^{-1}{\Vert }_2=\frac{1}{{\lambda }_n}.$$

If $\mathbf{A}$ is normal then

$$\Vert \mathbf{A}{\Vert }_2=|{\lambda }_1|$$

and if $\mathbf{A}$ is nonsingular, then

$$\Vert {\mathbf{A}}^{-1}{\Vert }_2=\frac{1}{|{\lambda }_n|}.$$

4.12.8. Unitary Invariant Norms

Definition 4.147 (Unitary invariant norm)

A matrix norm $\Vert \cdot \Vert$ on ${\mathbb{C}}^{m\times n}$ is called unitary invariant if $\Vert \mathbf{U}\mathbf{A}\mathbf{V}\Vert =\Vert \mathbf{A}\Vert$ for any $\mathbf{A}\in {\mathbb{C}}^{m\times n}$ and any unitary matrices $\mathbf{U}\in {\mathbb{C}}^{m\times m}$ and $\mathbf{V}\in {\mathbb{C}}^{n\times n}$.

We have already seen in Theorem 4.141 that Frobenius norm is unitary invariant.

It turns out that spectral norm is also unitary invariant.

4.12.9. More Properties of Operator Norms

In this section we will focus on operator norms connecting normed linear spaces $({\mathbb{C}}^n,\Vert \cdot {\Vert }_p)$ and $({\mathbb{C}}^m,\Vert \cdot {\Vert }_q)$. Typical values of $p,q$ would be in $\{1,2,\mathrm{\infty }\}$.

We recall that

$$\Vert \mathbf{A}{\Vert }_{p\to q}=\underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_q}{\Vert \mathbf{x}{\Vert }_p}=\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert \mathbf{A}\mathbf{x}{\Vert }_q=\underset{\Vert \mathbf{x}{\Vert }_p\le 1}{max}\Vert \mathbf{A}\mathbf{x}{\Vert }_q.$$

The table below [78] shows how to compute different $(p,q)$ norms. Some can be computed easily while others are NP-hard to compute.

Table 4.1 Typical $(p\to q)$ norms

$p$	$q$	$\Vert \mathbf{A}{\Vert }_{p\to q}$	Calculation
1	1	$\Vert \mathbf{A}{\Vert }_1$	Maximum $l_1$ norm of a column
1	2	$\Vert \mathbf{A}{\Vert }_{1\to 2}$	Maximum $l_2$ norm of a column
1	$\mathrm{\infty }$	$\Vert \mathbf{A}{\Vert }_{1\to \mathrm{\infty }}$	Maximum absolute entry of a matrix
2	1	$\Vert \mathbf{A}{\Vert }_{2\to 1}$	NP hard
2	2	$\Vert \mathbf{A}{\Vert }_2$	Maximum singular value
2	$\mathrm{\infty }$	$\Vert \mathbf{A}{\Vert }_{2\to \mathrm{\infty }}$	Maximum $l_2$ norm of a row
$\mathrm{\infty }$	1	$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to 1}$	NP hard
$\mathrm{\infty }$	2	$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to 2}$	NP hard
$\mathrm{\infty }$	$\mathrm{\infty }$	$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}$	Maximum $l_1$-norm of a row

The topological dual of the finite dimensional normed linear space $({\mathbb{C}}^n,\Vert \cdot {\Vert }_p)$ is the normed linear space $({\mathbb{C}}^n,\Vert \cdot {\Vert }_{p^{\prime }})$ where

$$\frac{1}{p}+\frac{1}{p^{\prime }}=1.$$

• ${\ell }_2$-norm is dual of $l_2$-norm. It is a self dual.

• ${\ell }_1$ norm and ${\ell }_{\mathrm{\infty }}$-norm are dual of each other.

When a matrix $\mathbf{A}$ maps from the space $({\mathbb{C}}^n,\Vert \cdot {\Vert }_p)$ to the space $({\mathbb{C}}^m,\Vert \cdot {\Vert }_q)$, we can view its conjugate transpose ${\mathbf{A}}^H$ as a mapping from the space $({\mathbb{C}}^m,\Vert \cdot {\Vert }_{q^{\prime }})$ to $({\mathbb{C}}^n,\Vert \cdot {\Vert }_{p^{\prime }})$.

Theorem 4.146 (Operator norm and conjugate transpose)

Operator norm of a matrix always equals the operator norm of its conjugate transpose. In other words

$$\Vert \mathbf{A}{\Vert }_{p\to q}=\Vert {\mathbf{A}}^H{\Vert }_{q^{\prime }\to p^{\prime }}$$

where

$$\frac{1}{p}+\frac{1}{p^{\prime }}=1,\frac{1}{q}+\frac{1}{q^{\prime }}=1.$$

Specific applications of this result are:

$$\Vert \mathbf{A}{\Vert }_2=\Vert {\mathbf{A}}^H{\Vert }_2.$$

This is obvious since the maximum singular value of a matrix and its conjugate transpose are same.

$$\Vert \mathbf{A}{\Vert }_1=\Vert {\mathbf{A}}^H{\Vert }_{\mathrm{\infty }},\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}=\Vert {\mathbf{A}}^H{\Vert }_1.$$

This is also obvious since max column sum of $\mathbf{A}$ is same as the max row sum norm of ${\mathbf{A}}^H$ and vice versa.

$$\Vert \mathbf{A}{\Vert }_{1\to \mathrm{\infty }}=\Vert {\mathbf{A}}^H{\Vert }_{1\to \mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{1\to 2}=\Vert {\mathbf{A}}^H{\Vert }_{2\to \mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to 2}=\Vert {\mathbf{A}}^H{\Vert }_{2\to 1}.$$

We now need to show the result for the general case (arbitrary $1\le p,q\le \mathrm{\infty }$).

Proof. TODO

Theorem 4.147 ($1\to p$ norm)

$$\Vert \mathbf{A}{\Vert }_{1\to p}=\underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_p.$$

where

$$\mathbf{A}=\left[\begin{array}{ccc}{\mathbf{a}}^1& \dots ,& {\mathbf{a}}^n\end{array}\right].$$

Proof. Expanding:

$$\begin{array}{rl}\Vert \mathbf{A}\mathbf{x}{\Vert }_p& ={\Vert \sum _{j=1}^n{x}_j{\mathbf{a}}^j\Vert }_p\\ & \le \sum _{j=1}^n{\Vert x_j{\mathbf{a}}^j\Vert }_p\\ & =\sum _{j=1}^n|x_j|{\Vert {\mathbf{a}}^j\Vert }_p\\ & \le \underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_p\sum _{j=1}^n|x_j|\\ & =\underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_p\Vert \mathbf{x}{\Vert }_1.\end{array}$$

Thus,

$$\Vert \mathbf{A}{\Vert }_{1\to p}=\underset{\mathbf{x}\ne \mathbf{0}}{max}\frac{\Vert \mathbf{A}\mathbf{x}{\Vert }_p}{\Vert \mathbf{x}{\Vert }_1}\le \underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_p.$$

We need to show that this upper bound is indeed an equality.

Indeed for any $\mathbf{x}={\mathbf{e}}_j$ where ${\mathbf{e}}_j$ is a unit vector with $1$ in $j$-th entry and 0 elsewhere,

$$\Vert \mathbf{A}{\mathbf{e}}_j{\Vert }_p=\Vert {\mathbf{a}}^j{\Vert }_p.$$

Thus

$$\Vert \mathbf{A}{\Vert }_{1\to p}\ge \Vert {\mathbf{a}}^j{\Vert }_p\mathrm{\forall }1\le j\le n.$$

Combining the two, we see that

$$\Vert \mathbf{A}{\Vert }_{1\to p}=\underset{1\le j\le n}{max}\Vert {\mathbf{a}}^j{\Vert }_p.$$

Theorem 4.148 ($p\to \mathrm{\infty }$ norm)

$$\Vert \mathbf{A}{\Vert }_{p\to \mathrm{\infty }}=\underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_q$$

where

$$\frac{1}{p}+\frac{1}{q}=1.$$

Proof. Using Theorem 4.146, we get

$$\Vert \mathbf{A}{\Vert }_{p\to \mathrm{\infty }}=\Vert {\mathbf{A}}^H{\Vert }_{1\to q}.$$

Using Theorem 4.147, we get

$$\Vert {\mathbf{A}}^H{\Vert }_{1\to q}=\underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_q.$$

This completes the proof.

Theorem 4.149 (Consistency of $p\to q$ norms)

For two matrices $\mathbf{A}$ and $\mathbf{B}$ with $p,q,s\ge 1$, we have

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to q}\le \Vert \mathbf{B}{\Vert }_{p\to s}\Vert \mathbf{A}{\Vert }_{s\to q}.$$

Proof. We start with

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to q}=\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert \mathbf{A}(\mathbf{B}\mathbf{x}){\Vert }_q.$$

From Lemma 4.90, we obtain

$$\Vert \mathbf{A}(\mathbf{B}\mathbf{x}){\Vert }_q\le \Vert \mathbf{A}{\Vert }_{s\to q}\Vert (\mathbf{B}\mathbf{x}){\Vert }_s.$$

Thus,

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to q}\le \Vert \mathbf{A}{\Vert }_{s\to q}\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert (\mathbf{B}\mathbf{x}){\Vert }_s=\Vert \mathbf{A}{\Vert }_{s\to q}\Vert \mathbf{B}{\Vert }_{p\to s}.$$

Theorem 4.150 (Consistency of $p\to \mathrm{\infty }$ norms)

For two matrices $\mathbf{A}$ and $\mathbf{B}$ and $p\ge 1$, we have

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}\Vert \mathbf{B}{\Vert }_{p\to \mathrm{\infty }}.$$

Proof. We start with

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to \mathrm{\infty }}=\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert \mathbf{A}(\mathbf{B}\mathbf{x}){\Vert }_{\mathrm{\infty }}.$$

From Lemma 4.90, we obtain

$$\Vert \mathbf{A}(\mathbf{B}\mathbf{x}){\Vert }_{\mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}\Vert (\mathbf{B}\mathbf{x}){\Vert }_{\mathrm{\infty }}.$$

Thus,

$$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}\underset{\Vert \mathbf{x}{\Vert }_p=1}{max}\Vert (\mathbf{B}\mathbf{x}){\Vert }_{\mathrm{\infty }}=\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }}\Vert \mathbf{B}{\Vert }_{p\to \mathrm{\infty }}.$$

Theorem 4.151 (Dominance of $p$-norm on $p\to \mathrm{\infty }$ norm)

$$\Vert \mathbf{A}{\Vert }_{p\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_p.$$

In particular

$$\Vert \mathbf{A}{\Vert }_{1\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_1.$$

Also:

$$\Vert \mathbf{A}{\Vert }_{2\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_2.$$

Proof. Choosing $q=\mathrm{\infty }$ and $s=p$ and applying Theorem 4.149

$$\Vert \mathbf{I}\mathbf{A}{\Vert }_{p\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{p\to p}\Vert \mathbf{I}{\Vert }_{p\to \mathrm{\infty }}.$$

But $\Vert \mathbf{I}{\Vert }_{p\to \mathrm{\infty }}$ is the maximum ${\ell }_p$ norm of any row of $\mathbf{I}$ which is $1$. Thus

$$\Vert \mathbf{A}{\Vert }_{p\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{p\to p}.$$

Consider the expression

$$\begin{array}{r}\underset{\begin{array}{c}\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)\\ \mathbf{z}\ne \mathbf{0}\end{array}}{min}\frac{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}{\Vert \mathbf{z}{\Vert }_p}.\end{array}$$

The constraint $\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H),\mathbf{z}\ne \mathbf{0}$ means there exists some vector $\mathbf{u}\notin \ker ({\mathbf{A}}^H)$ such that $\mathbf{z}={\mathbf{A}}^H\mathbf{u}$.

This expression measures the factor by which the non-singular part of $\mathbf{A}$ can change the length of a vector.

Theorem 4.152

The following bound holds for every matrix $\mathbf{A}$:

$$\begin{array}{r}\underset{\begin{array}{c}\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)\\ \mathbf{z}\ne \mathbf{0}\end{array}}{min}\frac{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}{\Vert \mathbf{z}{\Vert }_p}\ge \Vert {\mathbf{A}}^{†}{\Vert }_{q\to p}^{-1}.\end{array}$$

If $\mathbf{A}$ is surjective (onto), then the equality holds. When $\mathbf{A}$ is bijective (one-one onto, square, invertible), then the result implies

$$\begin{array}{r}\underset{\begin{array}{c}\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)\\ \mathbf{z}\ne \mathbf{0}\end{array}}{min}\frac{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}{\Vert \mathbf{z}{\Vert }_p}=\Vert {\mathbf{A}}^{-1}{\Vert }_{q\to p}^{-1}.\end{array}$$

Proof. The spaces $\mathcal{C}({\mathbf{A}}^H)$ and $\mathcal{C}(\mathbf{A})$ have same dimensions given by $\mathrm{rank}(\mathbf{A})$.

1. We recall that ${\mathbf{A}}^{†}\mathbf{A}$ is a projector onto the column space of ${\mathbf{A}}^H$.

   $$\mathbf{w}=\mathbf{A}\mathbf{z}⟺\mathbf{z}={\mathbf{A}}^{†}\mathbf{w}={\mathbf{A}}^{†}\mathbf{A}\mathbf{z}\mathrm{\forall }\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H).$$

2. As a result we can write

   $$\frac{\Vert \mathbf{z}{\Vert }_p}{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}=\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}$$

   whenever $\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)$ and $\mathbf{z}\ne \mathbf{0}$.

3. Now

   $$\begin{array}{r}{\left[\underset{\begin{array}{c}\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)\\ \mathbf{z}\ne \mathbf{0}\end{array}}{min}\frac{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}{\Vert \mathbf{z}{\Vert }_p}\right]}^{-1}=\underset{\begin{array}{c}\mathbf{z}\in \mathcal{C}({\mathbf{A}}^H)\\ \mathbf{z}\ne \mathbf{0}\end{array}}{max}\frac{\Vert \mathbf{z}{\Vert }_p}{\Vert \mathbf{A}\mathbf{z}{\Vert }_q}=\underset{\begin{array}{c}\mathbf{w}\in \mathcal{C}(\mathbf{A})\\ \mathbf{w}\ne \mathbf{0}\end{array}}{max}\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}\le \underset{\mathbf{w}\ne \mathbf{0}}{max}\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}.\end{array}$$

4. When $\mathbf{A}$ is surjective, then $\mathcal{C}(\mathbf{A})={\mathbb{C}}^m$.

5. Hence

   $$\begin{array}{r}\underset{\begin{array}{c}\mathbf{w}\in \mathcal{C}(\mathbf{A})\\ \mathbf{w}\ne \mathbf{0}\end{array}}{max}\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}=\underset{\mathbf{w}\ne \mathbf{0}}{max}\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}.\end{array}$$

6. Thus, the inequality changes into equality.

7. Finally

   $$\underset{\mathbf{w}\ne \mathbf{0}}{max}\frac{\Vert {\mathbf{A}}^{†}\mathbf{w}{\Vert }_p}{\Vert \mathbf{w}{\Vert }_q}=\Vert {\mathbf{A}}^{†}{\Vert }_{q\to p}$$

   which completes the proof.

4.12.10. Row Column Norms

A common way of measuring the norm of a matrix is to compute the ${\ell }_p$ norm for each row and then compute the ${\ell }_q$ norm of the resultant column vector. Such norms are known as row column norms.

1. If $p=q=2$, then the resultant norm is same as the Frobenius norm.

2. If $p=q=1$, then the resultant norm is same as the sum norm.

3. If $p=q=\mathrm{\infty }$, then the resultant norm is same as the max norm.

Thus, one can think of the row column norms as a generalization of these norms.

Definition 4.148 (Row-column norms)

Let $\mathbf{A}$ be an $m\times n$ matrix with rows ${\underset{―}{\mathbf{a}}}^i$ as

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{c}{\underset{―}{\mathbf{a}}}^1\\ ⋮\\ {\underset{―}{\mathbf{a}}}^m\end{array}\right]\end{array}$$

Then we define

$$\Vert \mathbf{A}{\Vert }_{p,\mathrm{\infty }}\triangleq \underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_p=\underset{1\le i\le m}{max}{\left(\sum _{j=1}^n|{\underset{―}{a}}_j^i{|}^p\right)}^{\frac{1}{p}}$$

where $1\le p<\mathrm{\infty }$. In other words, we take ${\ell }_p$-norms of all row vectors and then find the maximum.

We define

$$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty },\mathrm{\infty }}=\underset{i,j}{max}|a_{ij}|.$$

This is equivalent to taking ${\ell }_{\mathrm{\infty }}$ norm on each row and then taking the maximum of all the norms.

For $1\le p,q<\mathrm{\infty }$, we define the norm

$$\Vert \mathbf{A}{\Vert }_{p,q}\triangleq {\left[\sum _{i=1}^m{(\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_p)}^q\right]}^{\frac{1}{q}}.$$

In other words, we compute ${\ell }_p$-norm of all the row vectors to form another vector and then take ${\ell }_q$-norm of that vector.

Note that the norm $\Vert \mathbf{A}{\Vert }_{p,\mathrm{\infty }}$ is different from the operator norm $\Vert \mathbf{A}{\Vert }_{p\to \mathrm{\infty }}$. Similarly $\Vert \mathbf{A}{\Vert }_{p,q}$ is different from $\Vert \mathbf{A}{\Vert }_{p\to q}$.

Theorem 4.153

$$\Vert \mathbf{A}{\Vert }_{p,\mathrm{\infty }}=\Vert \mathbf{A}{\Vert }_{q\to \mathrm{\infty }}$$

where

$$\frac{1}{p}+\frac{1}{q}=1.$$

Proof. From Theorem 4.148 we get

$$\Vert \mathbf{A}{\Vert }_{q\to \mathrm{\infty }}=\underset{1\le i\le m}{max}\Vert {\underset{―}{\mathbf{a}}}^i{\Vert }_p.$$

This is exactly the definition of $\Vert \mathbf{A}{\Vert }_{p,\mathrm{\infty }}$.

Theorem 4.154

$$\Vert \mathbf{A}{\Vert }_{1\to p}=\Vert {\mathbf{A}}^H{\Vert }_{p,\mathrm{\infty }}.$$

Proof. We note that:

$$\Vert \mathbf{A}{\Vert }_{1\to p}=\Vert {\mathbf{A}}^H{\Vert }_{q\to \mathrm{\infty }}.$$

From Theorem 4.153

$$\Vert {\mathbf{A}}^H{\Vert }_{q\to \mathrm{\infty }}=\Vert {\mathbf{A}}^H{\Vert }_{p,\mathrm{\infty }}.$$

Theorem 4.155

For any two matrices $\mathbf{A},\mathbf{B}$, we have

$$\frac{\Vert \mathbf{A}\mathbf{B}{\Vert }_{p,\mathrm{\infty }}}{\Vert \mathbf{B}{\Vert }_{p,\mathrm{\infty }}}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}.$$

Proof. Let $q$ be such that $\frac{1}{p}+\frac{1}{q}=1$.

1. From Theorem 4.150, we have

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{q\to \mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}\Vert \mathbf{B}{\Vert }_{q\to \mathrm{\infty }}.$$

2. From Theorem 4.153

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{q\to \mathrm{\infty }}=\Vert \mathbf{A}\mathbf{B}{\Vert }_{p,\mathrm{\infty }}$$

   and

   $$\Vert \mathbf{B}{\Vert }_{q\to \mathrm{\infty }}=\Vert \mathbf{B}{\Vert }_{p,\mathrm{\infty }}.$$

3. Thus

   $$\Vert \mathbf{A}\mathbf{B}{\Vert }_{p,\mathrm{\infty }}\le \Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}\Vert \mathbf{B}{\Vert }_{p,\mathrm{\infty }}.$$

Theorem 4.156 (Relations between $(p,q)$ and $(p\to q)$ norms)

Relations between $(p,q)$ norms and $(p\to q)$ norms

$$\Vert \mathbf{A}{\Vert }_{1,\mathrm{\infty }}=\Vert \mathbf{A}{\Vert }_{\mathrm{\infty }\to \mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{2,\mathrm{\infty }}=\Vert \mathbf{A}{\Vert }_{2\to \mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{\mathrm{\infty },\mathrm{\infty }}=\Vert \mathbf{A}{\Vert }_{1\to \mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{1\to 1}=\Vert {\mathbf{A}}^H{\Vert }_{1,\mathrm{\infty }}.$$

$$\Vert \mathbf{A}{\Vert }_{1\to 2}=\Vert {\mathbf{A}}^H{\Vert }_{2,\mathrm{\infty }}$$

Proof. The first three are straight forward applications of Theorem 4.153. The next two are applications of Theorem 4.154. See also Table 4.1.

4.12.11. Block Diagonally Dominant Matrices and Generalized Gershgorin Circle Theorem

In [35] the idea of diagonally dominant matrices (see Diagonally Dominant Matrices) has been generalized to block matrices using matrix norms. We consider the specific case with spectral norm.

Definition 4.149 (Block diagonally dominant matrix)

Let $\mathbf{A}$ be a square matrix in ${\mathbb{C}}^{n\times n}$ which is partitioned in following manner

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{cccc}{\mathbf{A}}_{11}& {\mathbf{A}}_{12}& \dots & {\mathbf{A}}_{1k}\\ {\mathbf{A}}_{21}& {\mathbf{A}}_{22}& \dots & {\mathbf{A}}_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathbf{A}}_{k1}& {\mathbf{A}}_{k2}& \dots & {\mathbf{A}}_{kk}\end{array}\right]\end{array}$$

where each of the submatrices ${\mathbf{A}}_{ij}$ is a square matrix of size $m\times m$. Thus $n=km$.

$\mathbf{A}$ is called block diagonally dominant if

$$\Vert {\mathbf{A}}_{ii}{\Vert }_2\ge \sum _{j,j\ne i}\Vert {\mathbf{A}}_{ij}{\Vert }_2.$$

holds true for all $1\le i\le k$.

If the inequality satisfies strictly for all $i$, then $\mathbf{A}$ is called block strictly diagonally dominant matrix.

Theorem 4.157 (Nonsingularity of block strictly diagonally dominant matrices)

If the partitioned matrix $\mathbf{A}$ of Definition 4.149 is block strictly diagonally dominant matrix, then it is nonsingular.

For proof see [35].

This leads to the generalized Gershgorin disc theorem.

Theorem 4.158 (Generalized Gershgorin disc theorem)

Let $\mathbf{A}$ be a square matrix in ${\mathbb{C}}^{n\times n}$ which is partitioned in following manner

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{cccc}{\mathbf{A}}_{11}& {\mathbf{A}}_{12}& \dots & {\mathbf{A}}_{1k}\\ {\mathbf{A}}_{21}& {\mathbf{A}}_{22}& \dots & {\mathbf{A}}_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathbf{A}}_{k1}& {\mathbf{A}}_{k2}& \dots & {\mathbf{A}}_{kk}\end{array}\right]\end{array}$$

where each of the submatrices ${\mathbf{A}}_{ij}$ is a square matrix of size $m\times m$.

Then each eigenvalue $\lambda$ of $\mathbf{A}$ satisfies

$$\Vert \lambda \mathbf{I}-{\mathbf{A}}_{ii}{\Vert }_2\le \sum _{j,j\ne i}\Vert {\mathbf{A}}_{ij}{\Vert }_2\text{ for some }i\in \{1,2,\dots ,k\}.$$

For proof see [35].

Since the $2$-norm of a positive semidefinite matrix is nothing but its largest eigen value, the theorem directly leads to the following result.

Corollary 4.29 ($2$ norm of a Hermitian positive semidefinite matrix)

Let $\mathbf{A}$ be a Hermitian positive semidefinite matrix. Let $\mathbf{A}$ be partitioned as in Theorem 4.158. Then its $2$-norm $\Vert \mathbf{A}{\Vert }_2$ satisfies

$$|\Vert \mathbf{A}{\Vert }_2-\Vert {\mathbf{A}}_{ii}{\Vert }_2|\le \sum _{j,j\ne i}\Vert {\mathbf{A}}_{ij}{\Vert }_2\text{ for some }i\in \{1,2,\dots ,k\}.$$