Matrix Norm on $ℝ^{m\timesn}$

Yun-Hao Lee, Cheng-Han Huang

Credit: David Jakab from Pexels

1. Matrix Norm on $ℝ^{m\timesn}$

Definition 1.1. A norm $∥ \cdot ∥$ on $ℝ^{m \times n}$ is a function $∥ \cdot ∥ : ℝ^{m \times n} \to ℝ$ satisfying the following

(nonnegativity) $| | A | | \geq 0$ for any $A \in ℝ^{m \times n}$ and $| | A | | = 0$ if and only if $A = 0$ .
(positivity homogeneity) $| | λA | | = | λ | | | A | |$ for any $A \in ℝ^{m \times n}$ and $λ \in ℝ$ .
(triangle inequality) $| | A + B | | \leq | | A | | + | | B | |$ for any $A, B \in ℝ^{m \times n}$ .

Definition 1.2. Given a matrix $A \in ℝ^{m \times n}$ and two $l_{p}$ norms $∥ \cdot ∥_{a}$ and $∥ \cdot ∥_{b}$ on $ℝ^{n}$ and $ℝ^{m}$ , respectively. The induced matrix norm $| | A | |_{a, b}$ is defined by

| | A | |_{a, b} = {max}_{x} {| | Ax | |_{b} : | | x | |_{a} \leq 1}

Proposition 1.3. For any $x \in ℝ^{n}$ , we have the following inequality:

| | Ax | |_{b} \leq | | A | |_{a, b} | | x | |_{a}

Proof. Let $y = \frac{x}{| | x | |_{a}}$ , then $| | Ay | |_{b} \leq | | A | |_{a, b}$ by definition of induced matrix norm. Therefore,

| | A \frac{x}{| | x | |_{a}} | |_{b} \leq | | A | |_{a, b} \Rightarrow \frac{1}{| | x | |_{a}} | | Ax | |_{b} \leq | | A | |_{a, b} \Rightarrow | | Ax | |_{b} \leq | | A | |_{a, b} | | x | |_{a} .

Definition 1.4. If $∥ \cdot ∥_{a} = ∥ \cdot ∥_{b} = ∥ \cdot ∥_{2}$ , then the induced norm of matrix $A \in ℝ^{m \times n}$ is called the spectral norm and is defined by

| | A | |_{2} = | | A | |_{2, 2} = \max {| | Ax | |_{2} : | | x | |_{2} \leq 1}

Theorem 1.5. The spectral norm $| | A | |_{2} = \sqrt{λ_{max} (A^{T} A)} = σ_{max} (A)$

Proof. By Singular Value Decomposition (SVD), $A = U \sum V^{T}$ , where $\sum$ is an $m \times n$ matrix, $U_{m \times m}$ and $V_{n \times n}$ are real orthogonal matrix, and

\sum = (\begin{matrix} σ_{1} & \dots & 0 & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & \dots & σ_{r} & 0 & \dots & 0 \\ 0 & \dots & 0 & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & \dots & 0 & 0 & \dots & 0 \end{matrix}), where σ_{1} \geq σ_{2} \geq σ_{3} \geq . . . \geq σ_{r}

Since

A^{T} A = V {(\sum)}^{T} U^{T} U \sum V^{T} = V N V^{T}, where N = {(\sum)}^{T} \sum, n \times n

Let $V = [v_{1}, v_{2}, . . ., v_{n}]$ , where $v_{i} v_{j} = {\begin{aligned} 0, if i \neq j \\ 1, if i = j \end{aligned}$ . Then

\begin{array}{l} A^{T} AV & = V N V^{T} V = V N \cdot 1 = [v_{1}, v_{2}, . . ., v_{n}] diag [σ_{1}^{2}, σ_{2}^{2}, . . ., σ_{r}^{2}, 0, . . ., 0] \\ = v_{1}^{2} σ_{1}^{2} + v_{2}^{2} σ_{2}^{2} + . . . + v_{r} σ_{r}^{2} = v_{1}^{2} λ_{1} + v_{2}^{2} λ_{2} + . . . + v_{r}^{2} λ_{r}, λ_{i} = σ_{i}^{2}, 1 \leq i \leq r \end{array}

and

| | Ax | |^{2} = x^{T} A^{T} Ax = x^{T} V N V^{T} x = y^{T} Ny, where y = V^{T} x

Hence

\begin{array}{l} | | A | |_{2}^{2} & = \max {{(| | Ax | |_{2})}^{2} : | | x | |_{2} \leq 1} = \max {| | x^{T} A^{T} Ax | |_{2} : | | x | |_{2} \leq 1} \\ = \max {| | y^{T} Ny | |_{2} : | | y | |_{2} \leq 1} = \max {σ_{1}^{2} y_{1}^{2} + σ_{2}^{2} y_{2}^{2} + . . . + σ_{r}^{2} y_{r}^{2} : | | y | |_{2} \leq 1} \\ = σ_{1}^{2} {(1)}^{2} + σ_{2}^{2} {(0)}^{2} + . . . + σ_{n}^{2} {(0)}^{2} = σ_{1}^{2} = λ_{1} \end{array}

Therefore $| | A | |_{2} = \sqrt{λ_{max} (A^{T} A)} = σ_{max} (A)$ .

Definition 1.6. When $∥ \cdot ∥_{a} = ∥ \cdot ∥_{b} = ∥ \cdot ∥_{1}$ , the induced matrix norm of a matrix (1-norm) $A \in ℝ^{m \times n}$ is given by

| | A | |_{1} = \max_{1 \leq j \leq n} \sum_{i = 1}^{m} | A_{i, j} |

Definition 1.7. When $∥ \cdot ∥_{a} = ∥ \cdot ∥_{b} = ∥ \cdot ∥_{\infty}$ , the induced matrix norm of a matrix ( $\infty$ -norm) $A \in ℝ^{m \times n}$ is given by

| | A | |_{\infty} = \max_{1 \leq i \leq m} \sum_{j = 1}^{n} | A_{i, j} |

Example 1.8. Does there exist any matrix norm that is not a induced norm? The answer is Yes. We will give an example, called the Frobenius norm, which is defined by

| | A | |_{F} = \sqrt{\sum_{i = 1}^{m} \sum_{j = 1}^{n} A_{i, j}^{2}} for A \in ℝ^{m \times n}

Reference:

Beck, A. (2014). Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB. Society for Industrial and Applied Mathematics.

Matrix Norm on ℝm×n

1. Matrix Norm on ℝm×n

Reference:

Matrix Norm on $ℝ^{m\timesn}$

1. Matrix Norm on $ℝ^{m\timesn}$