Induced Matrix Norm
Notes on Induced Matrix Norm. I think the name comes from that fact that it is “induced” by a vector.
Definition:
For a $m$ by $n$ matrix $A$, and a n-dimensional vector $x$,
$$|| A ||_p = \sup \{ ||Ax||_p : ||x||_p = 1\}$$
Note that since given $A$, $ ||Ax||_p$ is a function of $x$, which is closed and bounded as $||x||_p = 1$, $||Ax||_p$ achieves maximum or minimum on some $x$. So we can replace $\sup$ with $\max$.
Claim I : $p = 1$:
$$||A||_1 = \max_{1 \le j \le n} \sum_{i=1}^m a_{ij}$$
First, let us find some upper bound on $||Ax||_1$.
$$||Ax||_1 = || \sum_{i=1}^n A_i x_i ||_1 \le \sum_{i=1}^n |x_i| || A_i ||_1
\le \max_j ||A_j|| \sum_{i=1}^n |x_i| = \max_j ||A_j|| ||x||_1$$
So given A, we have found a constant $K = \max_j ||A_j||$ that will upper bound $||Ax||_1$ by $K||x||_1$:
$$||Ax||_1 \le K ||x||_1$$
Next, we show that there exists $x$ for which we have equality for the above equation. Since $K = \max_j ||A_j||$, we can just let $x = [0, 0, …, 1, .. 0, 0]$ where 1 is at the $k$th position. $k$ is the index that satisfies $||A_k|| = \max_j ||A_j||$.
So we’ve found that ||A||_1 = \max_j ||A_j|| .
Claim II : $p = \infty$:
$$||A||_{\infty} = \max_{1 \le i \le m} \sum_{j=1}^n a_{ij}$$
First, consider $|| Ax ||_{\infty}$. Then,
$$\| Ax \|_{\infty} = \left \| \begin{matrix} \sum_{j=1}^n a_{1j} x_j \\ \sum_{j=1}^n a_{2j} x_j \\ \vdots \\ \sum_{j=1}^n a_{mj} x_j \end{matrix} \right \|_{\infty} = \max_i \left | \sum_{j=1}^n a_{ij} x_j \right | \le \max_i \sum_{j=1}^n \left | a_{ij} x_j \right | \le \max_i \sum_{j=1}^n \left | a_{ij} \right | \max_k \left | x_k \right | = \max_i \left( \sum_{j=1}^n \left | a_{ij} \right | \right) \| x \|_{\infty}$$So given $A$, we have found a constant $K = \max_i \left( \sum_{j=1}^n \left | a_{ij} \right | \right)$ that will upper bound $||Ax||_{\infty}$:
$$\| Ax \|_{\infty} \le K \| x \|_{\infty}$$
To find $\| A \|_{\infty}$, we need to find some $x$ that equates the above inequality, which is fortunately straightforward as in the case of $p = 1$. By examining :
$$\max_i \left | \sum_k a_{ik} x_k \right | = K \max_k | x_k |$$we notice that we achieve the equality if we let
$$x_k = \begin{cases}
\frac{ a_{ik} }{ | a_{ik} |} & (a_{ik} \neq 0) \\
1 & (a_{ik} = 0)
\end{cases}$$
where $k$ is the index such that $A_{k,:} = \max_i \left( \sum_{j=1}^n \left | a_{ij} \right | \right)$ Note: I’m using $A_k$ as denoting the $k$ th column vector of a matrix $A$, and $A_{k, :}$ as denoting the $k$ th row vector of $A$.
Claim III : $p = 2$:
$$\|A\|_2 = \sqrt{ \lambda_{\max} }$$
where $\lambda_{\max}$ is the largest eigenvalue of $A^T A$.
This is the spectral norm!