Recalling the Euclidean norm
In Vol I the norm of a vector came from the inner product: ||v|| = sqrt(<v,v>). That length let you talk about orthogonality, projection, and least squares. But the Euclidean length is only one ruler. Perturbation theory needs to compare *how big an error is*, and different problems call for different rulers.
A vector norm is any function ||.|| that is nonnegative (and zero only at 0), scales as ||a*v|| = |a|*||v||, and obeys the triangle inequality ||u+v|| <= ||u|| + ||v||. Any such function is a legitimate way to measure size.
The p-norm family
The most useful family is the p-norms. For p >= 1, ||v||_p = (sum |v_i|^p)^(1/p). Three members do almost all the work: p=1 (sum of absolute values), p=2 (Euclidean, the Vol I norm), and p=infinity (the largest absolute entry).
v = (3, -4, 0)
||v||_1 = |3| + |-4| + |0| = 7
||v||_2 = sqrt(3^2 + 4^2 + 0^2) = 5
||v||_inf = max(|3|, |-4|, |0|) = 4
Observe: ||v||_inf <= ||v||_2 <= ||v||_1
4 <= 5 <= 7Why dimension-finiteness saves us
It looks alarming that the size of a vector depends on which norm you chose. The rescue is the equivalence of norms: on a finite-dimensional space, any two norms ||.||_a and ||.||_b satisfy c*||v||_a <= ||v||_b <= C*||v||_a for fixed positive constants c, C. No vector can be small in one norm and huge in another.
Concretely, in R^n: ||v||_inf <= ||v||_2 <= sqrt(n)*||v||_inf, and ||v||_2 <= ||v||_1 <= sqrt(n)*||v||_2. So a sequence that converges in one norm converges in every norm; a problem that is stable in one is stable in all. We may pick whichever norm is most convenient for a proof.