From the free course CS323: Numerical Analysis and Computing on Lykke

Numerical Linear Algebra: Vectors, Matrices, and Norms

Key concepts: Vector and Matrix Algebra · Vector Operations · Linear Independence · Column Space & Null Space · Vector Norms (L1, L2, L-infinity) · Matrix Norms · Condition Number

This section reviews the fundamental building blocks of numerical linear algebra. It covers the definitions and operations of vectors and matrices, key theoretical concepts like span and column space, and the crucial idea of norms for measuring the magnitude of vectors and matrices. Understanding norms is essential for analyzing error and the sensitivity of linear systems.

Numerical Linear Algebra: Vectors, Matrices, and Norms

In most real-world applications, from simulating fluid dynamics to training a deep neural network, we rarely operate on single numbers. Instead, numerical computation is performed on entire collections of numbers. Vector and matrix algebra provides the fundamental mathematical framework for organizing, manipulating, and analyzing this data. This section provides a deep dive into the essential tools of this framework: vectors, matrices, and the concept of a norm, which allows us to measure the 'size' or 'magnitude' of these objects. This ability to quantify size is the bedrock for analyzing the error, stability, and convergence of nearly all numerical algorithms.

Vectors: The Building Blocks

At its core, linear algebra is the study of vectors and the linear transformations that act upon them. Vectors are the fundamental objects, representing points in space, quantities with direction, or simply ordered lists of data.

Definition and Notation

A vector in n-dimensional real space, denoted v ∈ ℝⁿ, is an ordered n-tuple of real numbers. v = (v₁, v₂, ..., vₙ)

By convention in numerical linear algebra, a vector is treated as a column vector, which is an n × 1 matrix:

v = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix}

Its transpose, vᵀ, is a row vector, which is a 1 × n matrix: vᵀ = $$ \begin{pmatrix} v_1 & v_2 & \dots & v_n \end{pmatrix} $$ . This distinction is not merely pedantic; it becomes critical when performing matrix operations. The space ℝⁿ is the set of all such n-dimensional vectors.

Fundamental Vector Operations

The power of vectors comes from the algebraic structure defined on ℝⁿ. The two primary operations are vector addition and scalar multiplication.

  1. Vector Addition: If u, v ∈ ℝⁿ, their sum u + v is defined by component-wise addition: (u + v)ᵢ = uᵢ + vᵢ. Geometrically, this corresponds to the "head-to-tail" rule, forming a parallelogram.

  2. Scalar Multiplication: If v ∈ ℝⁿ and α ∈ ℝ is a scalar, their product αv is defined by multiplying each component of v by α: (αv)ᵢ = αvᵢ. Geometrically, this scales the vector, stretching or shrinking it and possibly reversing its direction if α < 0.

These two operations together allow us to form linear combinations.

  1. Dot Product (Inner Product): The dot product of two vectors u, v ∈ ℝⁿ is a scalar value defined as: u ⋅ v = uᵀv = Σᵢ uᵢvᵢ.

The dot product is immensely useful as it connects algebra to geometry. It can be used to find the length of a vector and the angle between two vectors. The geometric definition of the dot product is u ⋅ v = ||u|| ||v|| cos(θ), where θ is the angle between u and v. This shows that two non-zero vectors are orthogonal (perpendicular) if and only if their dot product is zero.

Concrete Example: Vector Operations in Code

While high-level libraries provide optimized routines, implementing these operations from scratch reveals their underlying mechanics.

import numpy as np
import math

def manual_dot_product(v1: np.ndarray, v2: np.ndarray) -> float:
    """
    Computes the dot product of two 1D NumPy arrays without using np.dot or @.
    This demonstrates the fundamental summation algorithm.
    """
    if v1.shape != v2.shape or v1.ndim != 1:
        raise ValueError("Vectors must be 1D and have the same shape.")
    
    dot_product_sum = 0.0
    for i in range(v1.shape[0]):
        dot_product_sum += v1[i] * v2[i]
    return dot_product_sum

# --- Example Usage ---
u = np.array([1.0, -2.0, 3.0])
v = np.array([4.0, 5.0, 6.0])

# Scalar multiplication and vector addition
w = 2 * u + v
print(f"Vector u = {u}")
print(f"Vector v = {v}")
print(f"Result of 2*u + v = {w}\n")

# Dot product comparison
manual_result = manual_dot_product(u, v)
numpy_result = np.dot(u, v)
operator_result = u @ v # Python 3.5+ infix operator for matrix multiplication

print(f"Manual dot product: {manual_result}")
print(f"NumPy's np.dot result: {numpy_result}")
print(f"Using @ operator: {operator_result}\n")

# Geometric application: finding the angle between u and v
# cos(theta) = (u . v) / (||u|| ||v||)
norm_u = math.sqrt(manual_dot_product(u, u))
norm_v = math.sqrt(manual_dot_product(v, v))
cos_theta = manual_result / (norm_u * norm_v)
angle_rad = math.acos(cos_theta)
angle_deg = math.degrees(angle_rad)

print(f"Norm of u: {norm_u:.4f}")
print(f"Norm of v: {norm_v:.4f}")
print(f"Angle between u and v: {angle_deg:.2f} degrees")

Linear Combinations, Span, and Linear Independence

These concepts form the theoretical foundation of vector spaces.

  • A linear combination of a set of vectors {v¹, v², ..., vᵏ} is any vector w that can be written as w = c₁v¹ + c₂v² + ... + cₖvᵏ, where cᵢ are scalar coefficients.

  • The span of a set of vectors is the set of all possible linear combinations of those vectors. The span of a set of vectors in ℝⁿ forms a subspace of ℝⁿ (e.g., a line or a plane passing through the origin).

  • A set of vectors {v¹, v², ..., vᵏ} is linearly independent if the only solution to the equation c₁v¹ + c₂v² + ... + cₖvᵏ = 0 is c₁ = c₂ = ... = cₖ = 0. Intuitively, this means no vector in the set can be expressed as a linear combination of the others. They each contribute a unique, non-redundant direction. If a set is not linearly independent, it is linearly dependent.

Why it matters: Linear independence is a cornerstone concept. In solving systems of equations, it tells us whether a solution is unique. In data science, it relates to multicollinearity, where features are redundant. A set of n linearly independent vectors in ℝⁿ forms a basis for that space, meaning any vector in ℝⁿ can be uniquely represented as a linear combination of these basis vectors.

Matrices: Linear Transformations Encapsulated

A matrix can be viewed in several ways: as a grid of numbers, a collection of vectors, or, most powerfully, as an object that represents a linear transformation between vector spaces.

Definition and Notation

An m × n matrix A is a rectangular array of numbers with m rows and n columns. We write A ∈ ℝ^(m×n). The entry in the i-th row and j-th column is denoted Aᵢⱼ or aᵢⱼ.

A = \begin{pmatrix}
A_{11} & A_{12} & \dots & A_{1n} \\
A_{21} & A_{22} & \dots & A_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{m1} & A_{m2} & \dots & A_{mn}
\end{pmatrix}

Matrix-Vector Multiplication

The product of an m × n matrix A and an n × 1 vector x results in an m × 1 vector y. This operation, y = Ax, is the engine of linear algebra and has two fundamental interpretations.

Interpretation 1: Row-wise (Dot Products) Each component yᵢ of the output vector y is the dot product of the i-th row of A with the vector x.

yᵢ = Aᵢ,₁x₁ + Aᵢ,₂x₂ + ... + Aᵢ,ₙxₙ = Σⱼ Aᵢⱼxⱼ

Interpretation 2: Column-wise (Linear Combination) The output vector y is a linear combination of the columns of A, where the coefficients are the components of x.

y = x₁A₁,: + x₂A₂,: + ... + xₙAₙ,:

The column-wise view is often more insightful. It reveals that the output Ax must lie within the span of the columns of A.

// Let A be an m x n matrix and x be an n x 1 vector.
// The product y = Ax is an m x 1 vector.

// Interpretation 1: Dot products with rows
y_i = \sum_{j=1}^{n} A_{ij} x_j \quad \text{for } i=1, \ldots, m

// Example for y_1:
y_1 = (A_{1,1} * x_1) + (A_{1,2} * x_2) + \dots + (A_{1,n} * x_n)

// Interpretation 2: Linear combination of columns
// Let A_{:,j} be the j-th column of A.
y = x_1 A_{:,1} + x_2 A_{:,2} + \dots + x_n A_{:,n}

// Example:
\begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix} = x_1 \begin{pmatrix} A_{1,1} \\ \vdots \\ A_{m,1} \end{pmatrix} + x_2 \begin{pmatrix} A_{1,2} \\ \vdots \\ A_{m,2} \end{pmatrix} + \dots + x_n \begin{pmatrix} A_{1,n} \\ \vdots \\ A_{m,n} \end{pmatrix}

Column Space & Null Space

These two subspaces are intrinsically linked to any matrix A ∈ ℝ^(m×n) and are critical for understanding the behavior of the linear system Ax = b.

  • Column Space C(A): The column space of A is the span of its column vectors. It is a subspace of the output space ℝᵐ.

    • What it is: The set of all possible output vectors b for which the system Ax = b has a solution.
    • Why it matters: If a vector b is not in C(A), then Ax = b is inconsistent and has no solution. The dimension of C(A) is the rank of the matrix, rank(A) = r.
  • Null Space N(A): The null space of A is the set of all input vectors x that are mapped to the zero vector. It is a subspace of the input space ℝⁿ.

    • What it is: The set of all solutions to the homogeneous equation Ax = 0.
    • Why it matters: The null space tells us about the uniqueness of solutions. If N(A) contains only the zero vector, then the solution to Ax = b (if it exists) is unique. If N(A) is non-trivial, there are infinitely many solutions. The dimension of N(A) is the nullity of the matrix.

These two spaces are part of the Four Fundamental Subspaces of linear algebra, which provide a complete geometric picture of a linear transformation.

Subspace Definition Resides in Dimension Interpretation
Column Space C(A) Span of columns of A ℝᵐ r (rank) All possible outputs b for Ax=b
Null Space N(A) All x such that Ax=0 ℝⁿ n-r Solutions to the homogeneous equation
Row Space C(Aᵀ) Span of rows of A ℝⁿ r (rank) Orthogonal complement of N(A)
Left Null Space N(Aᵀ) All y such that Aᵀy=0 ℝᵐ m-r Orthogonal complement of C(A)

This structure leads to a profound result: the Rank-Nullity Theorem.

Theorem (Rank-Nullity): For any matrix A ∈ ℝ^(m×n), the dimension of its column space (rank) plus the dimension of its null space (nullity) equals the number of columns n.

rank(A) + nullity(A) = n

This theorem provides a beautiful accounting of dimensions. It states that the number of dimensions in the input space (n) is split between the dimensions that are preserved and mapped to the output space (rank) and the dimensions that are collapsed to zero (nullity).

Vector Norms: Measuring Magnitude

In numerical analysis, we constantly need to quantify the size of vectors, especially error vectors. A norm is a function that generalizes the concept of "length" or "magnitude" to vector spaces.

Formal Definition of a Norm

A function ||.|| : ℝⁿ → ℝ is a vector norm if for any vectors x, y ∈ ℝⁿ and any scalar α ∈ ℝ, it satisfies:

  1. Non-negativity: ||x|| ≥ 0, and ||x|| = 0 if and only if x = 0.
  2. Absolute Scalability (Homogeneity): ||αx|| = |α| ||x||.
  3. Triangle Inequality: ||x + y|| ≤ ||x|| + ||y||.

The triangle inequality is the most important property. It formalizes the idea that the shortest path between two points is a straight line.

The p-Norms: A Family of Measures

A broad and useful family of norms are the p-norms (or Lp-norms), defined as: ||x||_p = (Σᵢ |xᵢ|^p)^(1/p) for p ≥ 1.

The three most common instances of p-norms are essential tools in scientific computing and machine learning.

  • L1 Norm (p=1, Manhattan Norm): ||x||₁ = Σᵢ |xᵢ|.

    • How it works: It sums the absolute values of the components. It's called the "Manhattan norm" because it represents the distance a taxi would travel on a grid of streets.
    • Why it matters: The L1 norm is widely used in machine learning (e.g., Lasso regression) because it promotes sparsity. Minimizing the L1 norm of a vector of parameters tends to drive many of the parameters to exactly zero, effectively performing feature selection.
  • L2 Norm (p=2, Euclidean Norm): ||x||₂ = sqrt(Σᵢ xᵢ²).

    • How it works: This is the standard geometric length of a vector, calculated via the Pythagorean theorem. It is the square root of the dot product of a vector with itself: ||x||₂ = sqrt(xᵀx).
    • Why it matters: It is the most natural measure of distance. It is used everywhere, from calculating residuals in least-squares problems to regularization in Ridge regression. Unlike the L1 norm, it is differentiable everywhere (except at the origin), which is a convenient property for optimization algorithms.
  • L-infinity Norm (p→∞, Max Norm): ||x||_∞ = maxᵢ |xᵢ|.

    • How it works: It is simply the largest absolute value among the components of the vector.
    • Why it matters: The L-infinity norm is used when we care about the worst-case error. It isolates the component with the maximum magnitude, which is often crucial in error analysis and ensuring stability.

Geometric Interpretation and Use Cases

The "unit ball" for each norm (the set of all vectors x such that ||x|| ≤ 1) reveals their geometric character.

Norm Formula Geometric Shape (Unit Ball in ℝ²) Common Use Case
L1 Norm (` x
L2 Norm (` x
L-infinity Norm (` x

Real-World Usage: Gradient Clipping in Deep Learning

In training deep neural networks, gradients can sometimes become excessively large, leading to unstable training. A common technique to prevent this is gradient clipping, which uses a norm to rescale gradients if their magnitude exceeds a threshold.

import torch

# Imagine this is a gradient tensor for a layer's weights during backpropagation
gradients = torch.tensor([-2.5, 0.8, 1.2, -4.0, 0.1])

# Calculate different norms of the gradient vector
l1_norm = torch.linalg.vector_norm(gradients, ord=1)
l2_norm = torch.linalg.vector_norm(gradients, ord=2)
linf_norm = torch.linalg.vector_norm(gradients, ord=float('inf'))

print(f"Gradient Tensor: {gradients}")
print(f"L1 Norm (Sum of absolute values): {l1_norm:.4f}")
print(f"L2 Norm (Euclidean length): {l2_norm:.4f}")
print(f"L-infinity Norm (Max absolute value): {linf_norm:.4f}")

# A common use case: Gradient Clipping by L2 norm
# If the L2 norm of the gradients exceeds a threshold, scale it down.
max_norm_threshold = 2.0
if l2_norm > max_norm_threshold:
    clip_coefficient = max_norm_threshold / l2_norm
    clipped_gradients = gradients * clip_coefficient
    
    print(f"\nL2 norm ({l2_norm:.2f}) exceeded threshold {max_norm_threshold}. Gradients clipped.")
    print(f"Clipped Gradients: {clipped_gradients}")
    print(f"New L2 Norm: {torch.linalg.vector_norm(clipped_gradients, ord=2):.4f}")

Matrix Norms: Quantifying Amplification

Just as we need to measure the size of vectors, we also need to measure the "size" or "strength" of matrices. A matrix norm quantifies the maximum effect a matrix can have on a vector.

Induced (or Operator) Norms

The most natural way to define a matrix norm is by its action on vectors. An induced norm measures the maximum "stretching factor" that the matrix applies to any vector, as measured by a specific vector norm.

The matrix norm ||A|| induced by a vector norm ||.|| is defined as: ||A|| = sup_{x≠0} (||Ax|| / ||x||) = sup_{||x||=1} ||Ax||

This definition means the matrix norm is the largest possible value of the ratio ||Ax|| / ||x||. It answers the question: "What is the maximum amplification this matrix can produce?"

Each vector p-norm induces a corresponding matrix p-norm.

  • Matrix 1-Norm: ||A||₁ = max_j Σᵢ |Aᵢⱼ| (Maximum absolute column sum).
  • Matrix ∞-Norm: ||A||_∞ = max_i Σⱼ |Aᵢⱼ| (Maximum absolute row sum).
  • Matrix 2-Norm (Spectral Norm): ||A||₂ = σ_max(A), where σ_max is the largest singular value of A. This norm corresponds to the true maximum stretching factor but is the most computationally expensive to calculate.

The Frobenius Norm: An Alternative View

Not all matrix norms are induced. The Frobenius norm is a commonly used alternative that is easier to compute. It treats the matrix as if it were a single long vector and calculates its L2 norm.

The Frobenius norm of a matrix A ∈ ℝ^(m×n) is defined as: ||A||_F = sqrt(Σᵢ Σⱼ Aᵢⱼ²) = sqrt(tr(AᵀA))

Pitfall: While the Frobenius norm is a valid matrix norm (it satisfies the three defining properties), it is not an induced norm. It does not represent the maximum amplification factor in the same way ||A||₂ does. However, its computational simplicity makes it popular for applications like low-rank matrix approximation.

Norm Type Formula Computational Cost
Matrix 1-Norm (` A
Matrix ∞-Norm (` A
Matrix 2-Norm (` A
Frobenius Norm (` A

Example: Calculating Matrix Norms from the Command Line

We can use command-line tools like Octave/MATLAB for quick calculations, demonstrating another environment where these concepts are applied.

# Using octave-cli for a quick, interactive calculation of various norms for a matrix.
# This shows how these concepts are built into numerical computing environments.

# Define a 2x2 matrix A = [[1, -7], [-2, -3]]
octave-cli --eval "A = [1, -7; -2, -3]; \
                   norm_1 = norm(A, 1); \
                   norm_inf = norm(A, inf); \
                   norm_2 = norm(A, 2); \
                   norm_fro = norm(A, 'fro'); \
                   printf('Matrix A:\n'); disp(A); \
                   printf('1-Norm (max col sum of |1|+|-2|=3 and |-7|+|-3|=10): %f\n', norm_1); \
                   printf('Inf-Norm (max row sum of |1|+|-7|=8 and |-2|+|-3|=5): %f\n', norm_inf); \
                   printf('2-Norm (spectral norm, max singular value): %f\n', norm_2); \
                   printf('Frobenius Norm (sqrt(1^2 + (-7)^2 + (-2)^2 + (-3)^2)): %f\n', norm_fro);"

Output:

Matrix A:
   1  -7
  -2  -3

1-Norm (max col sum of |1|+|-2|=3 and |-7|+|-3|=10): 10.000000
Inf-Norm (max row sum of |1|+|-7|=8 and |-2|+|-3|=5): 8.000000
2-Norm (spectral norm, max singular value): 7.333245
Frobenius Norm (sqrt(1^2 + (-7)^2 + (-2)^2 + (-3)^2)): 7.937254

This example clearly shows that different norms give different measures of the "size" of the same matrix, each with its own interpretation and use case. The concepts of norms are the foundation for the condition number of a matrix, which is one of the most critical quantities in numerical analysis for determining the stability and reliability of a solution to a linear system.

Numerical Linear Algebra: Vectors, Matrices, and Norms - CS323: Numerical Analysis and Computing - diagram 1
Numerical Linear Algebra: Vectors, Matrices, and Norms - CS323: Numerical Analysis and Computing - diagram 1

Source Materials

Study CS323: Numerical Analysis and Computing on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages

Numerical Linear Algebra: Vectors, Matrices, and Norms — CS323: Numerical Analysis and Computing | Lykke