induced (operator) norm

An induced norm answers a physical question: by what largest factor can the matrix A stretch a vector? Pick a vector norm ||.|| for the inputs and outputs, then define ||A|| = max over x != 0 of ||A x|| / ||x||. Because the ratio ignores the length of x, you can equivalently take the max of ||A x|| over all unit vectors.

Each choice of vector norm induces a matrix norm, and three are workhorses. The 1-induced norm is the maximum absolute column sum, max_j sum_i |a_{ij}|. The inf-induced norm is the maximum absolute row sum, max_i sum_j |a_{ij}|. The 2-induced norm, the spectral norm, is the largest singular value sigma_max(A) — geometrically the longest axis of the ellipse that A maps the unit sphere onto.

Induced norms come with two free gifts. They are automatically submultiplicative, ||A B|| <= ||A|| ||B||, because stretching twice multiplies the stretch factors. And they are consistent with their generating vector norm, ||A x|| <= ||A|| ||x||, which is the inequality you reach for whenever you bound how far a transformation can move data.

The catch is cost. The 1- and inf-norms are read off instantly from the entries, but the 2-norm needs the top singular value, an iterative computation. In practice people often bound the spectral norm using sqrt(||A||_1 ||A||_inf) when a quick, certified estimate is enough.