Linear Algebra Fundamentals University of Massachusetts Amherst
Vectors are the objects we compute with; matrices are linear functions that act on vectors. To analyze algorithms, we need to measure size: norms for vectors, induced norms for matrices. The condition number κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ \kappa(A) = \|A\|\|A^{-1}\| κ ( A ) = ∥ A ∥∥ A − 1 ∥
Vectors and Vector Spaces ¶ The fundamental objects in numerical linear algebra are vectors —elements of a vector space.
A vector space V V V R \mathbb{R} R
Addition: x + y ∈ V \mathbf{x} + \mathbf{y} \in V x + y ∈ V x , y ∈ V \mathbf{x}, \mathbf{y} \in V x , y ∈ V
Scalar multiplication: α x ∈ V \alpha\mathbf{x} \in V α x ∈ V α ∈ R \alpha \in \mathbb{R} α ∈ R x ∈ V \mathbf{x} \in V x ∈ V
satisfying the usual axioms (associativity, commutativity, distributivity, zero element, inverses).
The canonical example is R n \mathbb{R}^n R n n n n
Space Elements Dimension R n \mathbb{R}^n R n Column vectors n n n C n \mathbb{C}^n C n Complex vectors n n n C \mathbb{C} C P n \mathcal{P}_n P n Polynomials of degree ≤ n \leq n ≤ n n + 1 n+1 n + 1 C [ a , b ] C[a,b] C [ a , b ] Continuous functions on [ a , b ] [a,b] [ a , b ] ∞ \infty ∞ L 2 [ a , b ] L^2[a,b] L 2 [ a , b ] Square-integrable functions ∞ \infty ∞
The same linear algebra concepts—basis, dimension, linear maps, norms—apply to all these spaces. When you solve a PDE numerically, you’re doing linear algebra in a function space. The finite-dimensional theory (R n \mathbb{R}^n R n
This is why we emphasize the abstract structure: vectors are elements of a vector space, matrices are linear maps. The specifics of R n \mathbb{R}^n R n
Vector Norms ¶ To analyze errors and convergence, we need to measure the “size” of vectors.
A vector space equipped with a norm is called a normed vector space . If it’s also complete (Cauchy sequences converge), it’s a Banach space —the natural setting for analysis.
The p p p R n \mathbb{R}^n R n ¶ ∥ x ∥ p = ( ∑ i = 1 n ∣ x i ∣ p ) 1 / p \|\mathbf{x}\|_p = \left(\sum_{i=1}^n |x_i|^p\right)^{1/p} ∥ x ∥ p = ( i = 1 ∑ n ∣ x i ∣ p ) 1/ p Name Formula Interpretation 1-norm ∣ x ∣ 1 = ∑ i ∣ x i ∣ |\mathbf{x}|_1 = \sum_i \lvert x_i \rvert ∣ x ∣ 1 = ∑ i ∣ x i ∣ Manhattan distance 2-norm ∣ x ∣ 2 = ∑ i x i 2 |\mathbf{x}|_2 = \sqrt{\sum_i x_i^2} ∣ x ∣ 2 = ∑ i x i 2 Euclidean length ∞ \infty ∞ ∣ x ∣ ∞ = max i ∣ x i ∣ |\mathbf{x}|_\infty = \max_i \lvert x_i \rvert ∣ x ∣ ∞ = max i ∣ x i ∣ Maximum component
Norm Equivalence ¶ All norms on R n \mathbb{R}^n R n equivalent : for any two norms ∥ ⋅ ∥ a \|\cdot\|_a ∥ ⋅ ∥ a ∥ ⋅ ∥ b \|\cdot\|_b ∥ ⋅ ∥ b c , C > 0 c, C > 0 c , C > 0
c ∥ x ∥ a ≤ ∥ x ∥ b ≤ C ∥ x ∥ a for all x c\|\mathbf{x}\|_a \leq \|\mathbf{x}\|_b \leq C\|\mathbf{x}\|_a \quad \text{for all } \mathbf{x} c ∥ x ∥ a ≤ ∥ x ∥ b ≤ C ∥ x ∥ a for all x This is a finite-dimensional phenomenon . In infinite dimensions (function spaces), different norms can give genuinely different notions of convergence—a key subtlety in PDE theory.
Function Space Norms ¶ The same idea extends to functions:
Space Norm Formula C [ a , b ] C[a,b] C [ a , b ] Supremum norm ∣ f ∣ ∞ = max x ∈ [ a , b ] ∣ f ( x ) ∣ |f|_\infty = \max_{x \in [a,b]} \lvert f(x) \rvert ∣ f ∣ ∞ = max x ∈ [ a , b ] ∣ f ( x )∣ L 2 [ a , b ] L^2[a,b] L 2 [ a , b ] L 2 L^2 L 2 ∣ f ∣ 2 = ∫ a b ∣ f ( x ) ∣ 2 d x |f|_2 = \sqrt{\int_a^b \lvert f(x) \rvert^2 dx} ∣ f ∣ 2 = ∫ a b ∣ f ( x ) ∣ 2 d x L p [ a , b ] L^p[a,b] L p [ a , b ] L p L^p L p ∣ f ∣ p = ( ∫ a b ∣ f ( x ) ∣ p d x ) 1 / p |f|_p = \left(\int_a^b \lvert f(x) \rvert^p dx\right)^{1/p} ∣ f ∣ p = ( ∫ a b ∣ f ( x ) ∣ p d x ) 1/ p
These are the continuous analogs of the discrete p p p
Matrices as Linear Maps ¶ Matrices are linear functions between vector spaces. A matrix A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n
T A : R n → R m , T A ( x ) = A x T_A: \mathbb{R}^n \to \mathbb{R}^m, \qquad T_A(\mathbf{x}) = A\mathbf{x} T A : R n → R m , T A ( x ) = A x Linearity means:
Every linear map R n → R m \mathbb{R}^n \to \mathbb{R}^m R n → R m m × n m \times n m × n
In infinite dimensions, linear maps between function spaces are called operators . Differential operators (d / d x d/dx d / d x ∫ K ( x , y ) f ( y ) d y \int K(x,y) f(y) dy ∫ K ( x , y ) f ( y ) d y PDE s are all linear maps—the infinite-dimensional analogs of matrices.
The Matrix-Vector Product ¶ Given A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n x ∈ R n \mathbf{x} \in \mathbb{R}^n x ∈ R n
( A x ) i = ∑ j = 1 n a i j x j , i = 1 , … , m (A\mathbf{x})_i = \sum_{j=1}^{n} a_{ij} x_j, \quad i = 1, \ldots, m ( A x ) i = j = 1 ∑ n a ij x j , i = 1 , … , m Cost: 2 m n 2mn 2 mn
Two views:
Row View Column View Each ( A x ) i (A\mathbf{x})_i ( A x ) i a i T ⋅ x \mathbf{a}_i^T \cdot \mathbf{x} a i T ⋅ x A x A\mathbf{x} A x ∑ j x j a ( j ) \sum_j x_j \mathbf{a}^{(j)} ∑ j x j a ( j )
The column view reveals that A x A\mathbf{x} A x column space (range) of A A A
Geometric Interpretation ¶ Matrix Type Geometric Effect Diagonal Scaling along coordinate axes Orthogonal (Q T Q = I Q^TQ = I Q T Q = I Rotation and/or reflection Symmetric Scaling along eigenvector directions
Matrix Norms ¶ Since matrices are linear maps, we measure their size by how much they “stretch” vectors.
This definition works for any linear map between normed spaces—it’s how we measure operators in functional analysis too.
Name Formula Computation 1-norm ∣ A ∣ 1 = max j ∑ i ∣ a i j ∣ |A|_1 = \max_j \sum_i \lvert a_{ij} \rvert ∣ A ∣ 1 = max j ∑ i ∣ a ij ∣ Maximum column sum ∞ \infty ∞ ∣ A ∣ ∞ = max i ∑ j ∣ a i j ∣ |A|_\infty = \max_i \sum_j \lvert a_{ij} \rvert ∣ A ∣ ∞ = max i ∑ j ∣ a ij ∣ Maximum row sum 2-norm ∣ A ∣ 2 = σ max ( A ) |A|_2 = \sigma_{\max}(A) ∣ A ∣ 2 = σ m a x ( A ) Largest singular value
Key properties: