Hyperplane Geometry Slides Hyperplane Geometry
Vector Spaces and the Geometry of Intersections in \( \mathbb{R}^n \)
LES-01 // GRADUATE LEVEL
The View from \( \mathbb{R}^n \)
In high-dimensional algebra, a single linear equation \( a_1x_1 + ... + a_nx_n = b \) defines a hyperplane of dimension \( n-1 \).
Core Question
"Can you visualize a system where the lines never meet, yet a solution exists in a subspace?"
\( A\mathbf{x} = \mathbf{b} \)
Interpreting as a weighted sum of columns
Existence & Uniqueness
Consistent
At least one solution exists. \(\mathbf{b}\) lies in the column space of \(A\), denoted \( \mathcal{C}(A) \).
Inconsistent
No solution. \(\mathbf{b}\) is outside the span of the columns of \(A\).
Rank \( r \)
The dimension of the subspace spanned by columns or rows. Critical for determining the nullity.
Rank-Nullity Theorem: \( \text{rank}(A) + \text{nullity}(A) = n \)
The Four Fundamental Subspaces
\( \mathcal{C}(A) \)
Column Space
Span of columns in \( \mathbb{R}^m \)
\( \mathcal{N}(A) \)
Nullspace
Solutions to \( A\mathbf{x} = \mathbf{0} \)
\( \mathcal{C}(A^T) \)
Row Space
Span of rows in \( \mathbb{R}^n \)
\( \mathcal{N}(A^T) \)
Left Nullspace
Solutions to \( A^T\mathbf{y} = \mathbf{0} \)
The Row vs. Column View
The Row Picture
Looking for the intersection of \( n \) planes. This is the "traditional" visualization.
Example: Two lines intersecting at a point in 2D.
The Column Picture
Looking for a linear combination of column vectors that produces the vector \( \mathbf{b} \).
Crucial for understanding algorithmic efficiency.
Vector Space Analysis Worksheet Vector Space Analysis
LES-01 // Algorithmic Linear Algebra
Name:
Date:
Part 1: Existence and Rank
Consider the matrix equation \( A\mathbf{x} = \mathbf{b} \), where \( A \in \mathbb{R}^{m \times n} \).
1. Under what precise condition on the rank of \( A \) and the augmented matrix \( [A | \mathbf{b}] \) does the system have at least one solution? Justify your answer using the concept of column span.
2. If \( m > n \) (overdetermined system), explain the geometric interpretation of a system with "no solution" in terms of the fundamental subspaces of \( A \).
Part 2: Nullspace and Uniqueness
Let \( A = \begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 3 & 6 & 3 \end{bmatrix} \).
3. Calculate the rank of \( A \) and find a basis for the nullspace \( \mathcal{N}(A) \).
Part 3: The Geometry of Subspaces
4. Prove that the column space \( \mathcal{C}(A) \) and the left nullspace \( \mathcal{N}(A^T) \) are orthogonal complements in \( \mathbb{R}^m \). How does this relationship help us identify when a solution exists for \( A\mathbf{x} = \mathbf{b} \)?
Challenge: The Intersection Question
Suppose you have three hyperplanes in \( \mathbb{R}^4 \). Each equation represents a 3D subspace. What are the possible dimensions for their intersection? Provide a scenario where the intersection is a line.
End of Analysis // Advanced Systems of Equations
Linear Algebra Facilitation Guide Instructor Key & Facilitation
Algorithmic Linear Algebra // Sequence Overview
Target Outcomes
Master LU factorizations and cost analysis.
Diagnose stability via condition numbers.
Apply iterative methods to sparse data.
Discussion Framework
"Why do we need LU if Gaussian elimination works?"
Focus on the transition from 'calculating once' to 'architecting solvers'.
L1: Vector Spaces & Geometry
Focus on the column space interpretation. Key answer: \( \text{rank}(A) = \text{rank}([A|b]) \) for consistency.
Nullspace of L1 matrix: \( A = [1 2 1; 2 4 2; 3 6 3] \). Rank is 1. Nullity is 2. Basis vectors: \( [-2, 1, 0]^T \) and \( [-1, 0, 1]^T \).
L2: Complexity & Gaussian
Emphasize the \( n^3 \) scaling. If \( n=10^6 \), flops \(\approx 0.33 \times 10^{18} \). At 1 Petaflop (\( 10^{15} \)), time is ~333 seconds (~5.5 min).
L3: LU Factorization
Trace multipliers carefully. For the matrix provided, \( L_{21}=2, L_{31}=0, L_{32}=2 \).
Tip: Remind students that L always has 1s on the diagonal for standard Doolittle factorization.
L4: Stability & Conditioning
Hilbert Matrix Analysis: \( \|H_3\|_\infty = 1+1/2+1/3 = 11/6 \approx 1.83 \). \( \|H_3^{-1}\|_\infty = | -36 | + 192 + | -180 | = 408 \). \( \kappa \approx 748 \). Expect loss of ~3 digits.
L5: Iterative Solvers
Jacobi Trace:
Sequence Culminating Project Ideas
Google PageRank Simulation
Implement the Power Method (an iterative solver) to rank a 500-node simulated internet graph.
Finite Difference Heat Equation
Model heat flow across a metal plate using a sparse Poisson matrix and Gauss-Seidel.
End of Facilitation Guide // Algorithmic Linear Algebra
Gaussian Efficiency Slides Algorithmic Efficiency
Gaussian Elimination and Computational Complexity Analysis
LES-02 // MATRIX COMPUTATION
The Gaussian Algorithm
Step 1: Forward Elimination
Reduce matrix \( A \) to an upper triangular form \( U \). This requires systematic row operations.
Step 2: Back Substitution
Solve for variables starting from the bottom row. Highly efficient once in triangular form.
// Row Operation Matrix
\( E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -\ell_{21} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \)
Elementary matrices are the building blocks of factorization.
Computational Cost
\( O(n^3) \)
Forward Elimination
Specifically \( \approx \frac{1}{3}n^3 \) subtractions and multiplications.
\( O(n^2) \)
Back Substitution
Negligible compared to elimination for large \( n \).
Scale Comparison
n Flops 10 ~333 100 ~333,333 1,000 ~333 Million
Partial Pivoting
Dividing by zero is fatal, but dividing by a very small number is equally dangerous in floating-point math.
The Rule
Always swap the current row with the row having the largest absolute value in the pivot column.
\( PA = LU \)
\( P \) is the permutation matrix documenting our swaps.
Gaussian Complexity Worksheet Computational Complexity
LES-02 // Gaussian Elimination Workshop
Researcher:
Part 1: The Elimination Process
Transform the following system into upper triangular form \( U \) using elementary row operations. Track your multiplier \( \ell_{ij} \) for each step.
\[ A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} \]
1. Eliminate the first column. State your multipliers \( \ell_{21} \) and \( \ell_{31} \).
2. Complete the elimination to find \( U \). Is the matrix singular?
Part 2: Big O Analysis
3. Derive the total number of floating-point operations (flops) required for the forward elimination phase of an \( n \times n \) matrix. Use the summation formula for \( i^2 \) and \( i \).
Part 3: Algorithmic Case Study
Real-World Scaling
A supercomputer can perform \( 10^{15} \) flops per second (1 Petaflop). How long would it take to solve a system with \( n = 1,000,000 \) variables using Gaussian Elimination? Contrast this with a system of size \( n = 1,000 \).
4. Explain why Gaussian elimination without pivoting might fail for the matrix \( A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \). How does partial pivoting resolve this?
End of Complexity Workshop // Algorithmic Efficiency
LU Decomposition Slides Matrix Factorization
The LU Decomposition: Efficiency Through Structural Symmetry
LES-03 // OPTIMIZED SOLVERS
The GPS Problem
Gaussian elimination is great for solving \( A\mathbf{x} = \mathbf{b} \).
But what if you have the same matrix A but thousands of different b vectors?
LU Decomposition allows us to "pre-compute" the elimination steps once and reuse them at \( O(n^2) \) cost per solve.
A = LU
Lower & Upper
Triangular Components
Matrix L
Lower triangular with 1s on the diagonal. It stores the multipliers used during elimination.
\( \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1 \end{bmatrix} \)
Matrix U
Upper triangular. It is the end result of Gaussian elimination (the reduced matrix).
\( \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} \)
The Two-Step Solve
1. Solve \( L\mathbf{y} = \mathbf{b} \)
Forward Substitution
2. Solve \( U\mathbf{x} = \mathbf{y} \)
Back Substitution
\( A\mathbf{x} = (LU)\mathbf{x} = L(U\mathbf{x}) = L\mathbf{y} = \mathbf{b} \)
LU Factorization Worksheet LU Factorization Guide
LES-03 // Numerical Methods
Student ID:
Part 1: Performing the Decomposition
Decompose the following matrix \( A \) into the product \( LU \). Show each step of elimination and the resulting matrices.
\( A = \begin{bmatrix} 1 & 1 & 1 \\ 2 & 4 & 5 \\ 0 & 4 & 0 \end{bmatrix} \)
MATRIX L
MATRIX U
Part 2: Solving Multiple Systems
Using the \( L \) and \( U \) found above, solve for \( \mathbf{x} \) given \( \mathbf{b} = [1, 2, 8]^T \). Solve \( L\mathbf{y} = \mathbf{b} \) first, then \( U\mathbf{x} = \mathbf{y} \).
1. Forward substitution for \( \mathbf{y} \):
2. Backward substitution for \( \mathbf{x} \):
Part 3: Comparative Efficiency Analysis
Compare the computational cost of solving 100 systems of the form \( A\mathbf{x} = \mathbf{b}_i \) using:
Express your answer in terms of \( n^k \) operations.
4. Matrix Symmetry (Cholesky Factorization)
If \( A \) is symmetric and positive definite (SPD), we can use \( A = LL^T \). Explain how this affects memory storage and computation time compared to general LU.
End of LU Exploration // Optimized Systems
Numerical Stability Slides Numerical Stability
Condition Numbers and the Art of Error Analysis
LES-04 // ERROR PROPAGATION
When Math Breaks
In theoretical math, \( 10^{-16} \) is zero. In computational math, it's a bomb.
Ill-Conditioned Systems
Systems where small changes in input (data or rounding) cause catastrophic changes in output.
Geometric Intuition
Nearly Parallel Lines
The Condition Number \( \kappa(A) \)
\( \kappa(A) = \|A\| \cdot \|A^{-1}\| \)
Quantifies how much the solution \( \mathbf{x} \) changes relative to a change in \( \mathbf{b} \).
Interpretation Guide
1: Ideal (Identity Matrix)
10^2: Generally safe
10^6: Losing 6 digits of accuracy
10^16: Complete loss of information
Relative Error Bound
\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \le \kappa(A) \frac{\|\delta \mathbf{b}\|}{\|\mathbf{b}\|} \]
"The error in the answer is at most the condition number times the error in the data."
Numerical Stability = Minimized Error Propagation
Stability Audit Worksheet Conditioning Audit
LES-04 // Stability & Error Analysis
Analyst:
Part 1: The Infamous Hilbert Matrix
The Hilbert matrix \( H_{ij} = \frac{1}{i+j-1} \) is notoriously ill-conditioned. Consider \( H_3 \):
\( H_3 = \begin{bmatrix} 1 & 1/2 & 1/3 \\ 1/2 & 1/3 & 1/4 \\ 1/3 & 1/4 & 1/5 \end{bmatrix} \)
1. Using the \( \infty \)-norm (\( \|A\|_\infty = \max_i \sum_j |a_{ij}| \)), compute \( \|H_3\|_\infty \).
2. Given \( H_3^{-1} = \begin{bmatrix} 9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{bmatrix} \), compute the condition number \( \kappa_\infty(H_3) \). What does this value imply for precision?
Part 2: Sensitivity Simulation
Suppose we solve \( A\mathbf{x} = \mathbf{b} \) where \( \kappa(A) = 10^5 \). Our measurement of \( \mathbf{b} \) has a relative error of \( 10^{-6} \).
3. Estimate the maximum relative error in the calculated solution \( \mathbf{x} \). If we use standard 64-bit floats (approx. 16 decimal digits), how many significant digits can we trust in our answer?
Part 3: Norm Properties and Theoretical Bounds
4. Prove that \( \kappa(A) \ge 1 \) for any matrix norm that satisfies \( \|I\| = 1 \). Under what condition is \( \kappa(A) = 1 \)?
The Singularity Connection
A matrix is "close" to being singular if its condition number is very large. Explain the relationship between the distance to the nearest singular matrix and the condition number.
End of Stability Audit // Numerical Stability
Iterative Solvers Slides Iterative Solvers
Scaling to the Infinite: Solving Large and Sparse Systems
LES-05 // BIG DATA ALGEBRA
Massive & Sparse
Gaussian Elimination is \( O(n^3) \). For a social network with 1 billion nodes, \( n^3 \) is larger than the number of atoms in the universe.
Solution: Iteration
Start with a guess \( \mathbf{x}^{(0)} \). Refine it: \( \mathbf{x}^{(k+1)} = f(\mathbf{x}^{(k)}) \).
Sparse Matrix Concept
1
0
0
3
0
5
0
0
0
0
2
0
4
0
0
1
"Most entries are zero."
The Jacobi Method
Update Rule
\[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j \neq i} a_{ij} x_j^{(k)} \right) \]
Solve for each variable using only the previous iteration's values. Perfect for parallel processing.
Parallel Friendly
All components can be updated simultaneously.
Slow Convergence
Requires more steps than Gauss-Seidel.
Convergence Criteria
Diagonal Dominance
\[ |a_{ii}| > \sum_{j \neq i} |a_{ij}| \]
"If the diagonal is 'stronger' than the rest of the row, iteration will likely converge."
Also governed by the Spectral Radius \( \rho(M) < 1 \).
Iterative Solvers Worksheet Sparse System Workshop
LES-05 // Iterative Algorithms
Scientist:
Part 1: The Jacobi Iteration
Consider the following diagonally dominant system. Perform two iterations of the Jacobi method starting with \( \mathbf{x}^{(0)} = [0, 0]^T \).
\[ \begin{aligned} 4x_1 + x_2 &= 13 \\ x_1 + 3x_2 &= 6 \end{aligned} \]
1. Rewrite the equations in the update form for \( x_1^{(k+1)} \) and \( x_2^{(k+1)} \).
2. Iteration 1 (\( k=1 \)) Result:
3. Iteration 2 (\( k=2 \)) Result:
Part 2: Gauss-Seidel and Successive Relaxation
4. Explain the primary algorithmic difference between the Jacobi method and the Gauss-Seidel method. Why does Gauss-Seidel typically converge faster?
Application: Google PageRank
The PageRank algorithm treats the web as a massive system \( \mathbf{x} = M\mathbf{x} \), where \( M \) is a stochastic matrix. How does the iterative approach handle the sparsity of a web-graph with trillions of potential edges?
5. Spectral Radius Convergence: Prove that if \( A \) is strictly diagonally dominant, the Jacobi iteration must converge to the true solution for any initial guess.
End of Iteration Workshop // Algorithmic Linear Algebra
