Matrix Norm

A function $f: \mathbb{R}^{m \times n} \rightarrow \mathbb{R}$ is called a matrix norm if it satisfies that $\forall A, B \in \mathbb{R}^{m \times n}$ and $k \in \mathbb{R}$,

1. $f(A) = 0 \rightarrow A = 0$.
2. $f(kA) = kf(A)$.
3. $f(A + B) \le f(A) + f(B)$.

Frobenius Norm

The Frobenius Norm view a matrix as a vector and is defined as $|A|_F = \sqrt{\sum_{i, j} a_{i,j}^2 }$, where $a_{i,j}$ is the element in the $i$-th row and $j$-th column. Clearly this is a norm.

2-norm or spectral norm

The 2-norm is defined as $|A|_2 = \sigma_1$, where $\sigma_1$ is the maximum singular value of $A$. We prove this is a norm by checking triangle inequality.

Proof: First, note that

This can be verified by writing $A$ as its singular value decomposition

where $u_1, ..., u_r \in \mathbb{R}^m$ are orthogonal, $v_1, v_2, ..., v_r \in \mathbb{R}^n$ are orthogonal and $\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r \ge 0$.

We augment $v_1, v_2, ..., v_r$ to $v_1, .., v_n$ such that they constitutes an orthogonal base of $\mathbb{R}^n$. Then we can write $x \in \mathbb{R}^n$ as

where $\sum_{i = 1}^n x_i^2 = 1$.

Therefore,

Clearly $||Ax||$ is maximized when $x_1 = 1$ and $x_i = 0$ for $i \neq 1$:

Now, for any $x \in \mathbb{R}^n$ and $||x|| = 1$, by triangle inequality of vectors, it holds that

Maximizing over the left hand side gives the desired triangle inequality.