Project 6: Eigenvalue/Eigenvector Explorer

A tool that computes eigenvalues and eigenvectors of any matrix and visualizes what they mean: the directions that don’t change orientation under the transformation, only scale.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced (The Engineer)
Main Programming Language Python
Alternative Programming Languages Julia, C, Rust
Coolness Level Level 4: Hardcore Tech Flex
Business Potential 1. The “Resume Gold” (Educational/Personal Brand)
Knowledge Area Spectral Analysis / Linear Algebra
Software or Tool Eigenvector Visualizer
Main Book “Linear Algebra Done Right” by Sheldon Axler

1. Learning Objectives

By completing this project, you will:

  1. Translate math definitions into deterministic implementation steps.
  2. Build validation checks that make correctness observable.
  3. Diagnose numerical, logical, and data-shape failures early.
  4. Explain tradeoffs in interviews using evidence from your own build.

2. All Theory Needed (Per-Concept Breakdown)

This project applies the following theory clusters:

  • Symbolic-to-numeric translation (expressions, data shapes, invariants)
  • Stability constraints (precision, scaling, stopping criteria)
  • Optimization or inference logic (depending on project objective)
  • Evaluation discipline (error analysis, test coverage, reproducibility)

Concept A: Mathematical Representation Discipline

Fundamentals A math expression is not executable until you define representation, ordering, and domain constraints. The same equation can be represented as a token stream, tree, matrix pipeline, or probability graph. Choosing representation determines what bugs you can catch early.

Deep Dive into the concept Most project failures begin before algorithm selection: they start with ambiguous representation. If your parser cannot distinguish unary minus from subtraction, your calculator fails. If your matrix dimensions are implicit rather than validated, your linear algebra pipeline fails silently. If your probabilistic assumptions (independence, stationarity, or class priors) are not explicit, your inference can look accurate on one split and collapse on another. The core implementation move is to treat representation as a contract. Define each object with shape, domain, and semantic intent. Then enforce invariants at boundaries: input parser, preprocessing, training loop, evaluation stage. This makes debugging local instead of global.

How this fits this project You will encode each operation with explicit contracts and invariant checks.

Definitions & key terms

  • Invariant: Property that must hold before and after each operation.
  • Shape contract: Expected dimensional structure of vectors/matrices/tensors.
  • Domain constraint: Allowed value range (for example log input > 0).

Mental model diagram

User Input -> Representation Layer -> Validated Operation -> Observable Output
              (tokens/shapes)        (invariants pass)       (tests/plots/logs)

How it works

  1. Parse/ingest data into typed structures.
  2. Validate shape/domain invariants.
  3. Execute operation.
  4. Compare observed output with expected behavior.
  5. Record failure signature if mismatch appears.

Minimal concrete example

PSEUDOCODE
read expression
tokenize with precedence rules
if token sequence invalid -> return syntax error
evaluate tree
if domain violation -> return bounded diagnostic
print value and confidence check

Common misconceptions

  • “If it runs once, representation is correct.” -> false.
  • “Type checks are enough without shape checks.” -> false.

Check-your-understanding questions

  1. Which invariant catches division-by-zero earliest?
  2. Why does shape validation belong at boundaries rather than only in core logic?
  3. Predict failure if tokenization ignores unary minus.

Check-your-understanding answers

  1. Domain check on denominator before operation execution.
  2. Boundary validation keeps errors local and diagnostic.
  3. Expressions like -2^2 get misinterpreted and produce wrong precedence behavior.

Real-world applications Feature preprocessing, model-serving input validation, and experiment-tracking schema enforcement.

Where you’ll apply it This project and every downstream project in the sprint.

References

  • CSAPP (Bryant & O’Hallaron), floating-point chapter
  • Math for Programmers (Paul Orland), representation-oriented chapters

Key insight Correct representation reduces the complexity of every later decision.

Summary Stable ML math implementations start with explicit contracts, not implicit assumptions.

Homework/Exercises

  1. Write five invariants for your project.
  2. Build a failing test input for each invariant.

Solutions

  1. Include at least one shape, one domain, one convergence, one reproducibility, and one output-range invariant.
  2. Each failing input should trigger exactly one diagnostic to keep root-cause analysis clean.

3. Build Blueprint

  1. Scope the smallest end-to-end slice that produces visible output.
  2. Add deterministic tests and edge-case probes.
  3. Layer complexity only after baseline behavior is stable.
  4. Add metrics logging before optimization.
  5. Run failure drills: perturb inputs, scale values, and check stability.

4. Real-World Outcome (Target)

$ python eigen.py
> A = [[3, 1], [0, 2]]

Eigenvalues: λ₁ = 3.0, λ₂ = 2.0
Eigenvectors:
  v₁ = [1, 0] (for λ₁ = 3)
  v₂ = [-1, 1] (for λ₂ = 2)

[Visual: Grid of points, with eigenvector directions highlighted in red]
[Animation: Apply transformation A, see that v₁ stretches by 3x, v₂ stretches by 2x]
[All other vectors change direction, but eigenvectors just scale!]

> A = [[0, -1], [1, 0]]  # Rotation matrix
Eigenvalues: λ₁ = i, λ₂ = -i  (complex!)
[Visual: No real eigenvectors - this is pure rotation, nothing stays fixed]

Implementation Hints: Power iteration: start with random vector v, repeatedly compute v = A @ v / ||A @ v||. This converges to the dominant eigenvector.

For all eigenvalues of a 2x2 matrix, solve the characteristic polynomial:

det([[a-λ, b], [c, d-λ]]) = 0
(a-λ)(d-λ) - bc = 0
λ² - (a+d)λ + (ad-bc) = 0

Use the quadratic formula!

For larger matrices, use QR iteration or look up the Francis algorithm.

Learning milestones:

  1. Power iteration finds the dominant eigenvector → You understand iterative methods
  2. Visual shows eigenvectors as “special directions” → You have geometric intuition
  3. You understand eigendecomposition A = PDP⁻¹ → You can diagonalize matrices

5. Core Design Notes from Main Guide

Core Question

What makes certain directions in space “special” for a linear transformation, and why do these special directions reveal the fundamental nature of the transformation?

When a matrix transforms space, most vectors change both their direction and magnitude. But eigenvectors are extraordinary–they resist the transformation’s attempt to rotate them. They only stretch or shrink. This is not just mathematical curiosity; it is the key to understanding what a matrix “really does.” When you decompose a transformation into its eigenvectors, you are finding its fundamental axes of action. This is why Google’s PageRank (finding the most important web pages), PCA (finding the most important directions in data), and stability analysis in dynamical systems all reduce to eigenvalue problems.

Concepts You Must Understand First

Stop and research these before coding:

  1. What is a linear transformation and how does a matrix represent it?
    • Why must matrix multiplication preserve linearity (T(av + bw) = aT(v) + bT(w))?
    • What does it mean geometrically when we say a matrix “acts on” a vector?
    • Book Reference: “Linear Algebra Done Right” Chapter 3 - Sheldon Axler
  2. The characteristic polynomial and why det(A - lambdaI) = 0 gives eigenvalues
    • Why do we subtract lambda from the diagonal specifically?
    • What does the determinant being zero tell us about the transformation (A - lambdaI)?
    • Why can we not just solve Av = lambdav directly–why the detour through determinants?
    • Book Reference: “Linear Algebra Done Right” Chapter 5 - Sheldon Axler
  3. Power iteration and why it converges to the dominant eigenvector
    • If we repeatedly multiply a random vector by A, why does it align with the largest eigenvector?
    • What is the rate of convergence and what determines it?
    • Why do we need to normalize at each step?
    • Book Reference: “Numerical Linear Algebra” Chapter 27 - Trefethen & Bau
  4. Diagonalization: what A = PDP^(-1) really means
    • Why does changing basis to eigenvectors make the matrix diagonal?
    • What operations become trivial on diagonal matrices (powers, exponentials)?
    • When is a matrix NOT diagonalizable?
    • Book Reference: “Linear Algebra Done Right” Chapter 5 - Sheldon Axler
  5. Complex eigenvalues and their geometric meaning
    • Why do some real matrices have complex eigenvalues?
    • What does a complex eigenvalue tell you about the transformation (hint: rotation)?
    • Book Reference: “Math for Programmers” Chapter 9 - Paul Orland
  6. The relationship between eigenvalues and matrix properties
    • Trace = sum of eigenvalues. Determinant = product of eigenvalues. Why?
    • How do eigenvalues tell you if a matrix is invertible?
    • What do negative eigenvalues mean geometrically?
    • Book Reference: “Linear Algebra Done Right” Chapter 5 - Sheldon Axler

Questions to Guide Your Design

Before implementing, think through these:

  1. How will you represent polynomials? The characteristic polynomial for an nxn matrix has degree n. Will you use coefficient arrays, or symbolic representations?

  2. For power iteration, how do you know when to stop? What is your convergence criterion? How do you handle the case where there are two eigenvalues with equal magnitude?

  3. How will you visualize “eigenvector-ness”? What visual will make it clear that eigenvectors do not rotate–they only scale? Consider showing what happens to the unit circle under transformation.

  4. How do you find ALL eigenvectors, not just the dominant one? Power iteration gives you the largest. What about deflation–subtracting out the found eigenvector’s contribution?

  5. What happens when eigenvalues are complex? Can you still visualize this? Consider showing that pure rotation matrices have no real eigenvectors–every direction gets rotated.

  6. How will you verify your eigenvalues/eigenvectors are correct? The ultimate check: Av should equal lambda * v for each eigenpair.

Thinking Exercise

Before writing any code, trace through power iteration by hand:

Given matrix A = [[3, 1], [0, 2]], find the dominant eigenvector using power iteration:

Starting vector: v0 = [1, 1]

Step 1: Multiply by A
  A * v0 = [[3,1],[0,2]] * [1,1] = [4, 2]
  Normalize: v1 = [4,2] / |[4,2]| = [4,2] / sqrt(20) = [0.894, 0.447]

Step 2: Multiply by A
  A * v1 = [[3,1],[0,2]] * [0.894, 0.447] = [3.129, 0.894]
  Normalize: v2 = [3.129, 0.894] / |...| = [0.961, 0.275]

Step 3: Multiply by A
  A * v2 = [[3,1],[0,2]] * [0.961, 0.275] = [3.158, 0.550]
  Normalize: v3 = [0.985, 0.173]

Continue... converges to [1, 0]

Verify: A * [1, 0] = [3, 0] = 3 * [1, 0]. So [1, 0] is an eigenvector with eigenvalue 3!

Now find the eigenvalue using the characteristic polynomial:

  • det(A - lambdaI) = det([[3-lambda, 1], [0, 2-lambda]]) = (3-lambda)(2-lambda) - 0 = 0
  • Solutions: lambda = 3 or lambda = 2
  • Eigenvalue 3 corresponds to eigenvector [1, 0]
  • Eigenvalue 2 corresponds to eigenvector [-1, 1] (verify: A[-1,1] = [-2,2] = 2[-1,1])

Interview Questions

  1. “What is an eigenvector and eigenvalue intuitively?” Expected answer: An eigenvector is a direction that does not rotate under transformation–only scales. The eigenvalue is the scaling factor.

  2. “Why do we compute eigenvalues from det(A - lambdaI) = 0?” Expected answer: We are finding values of lambda where (A - lambdaI) is singular–meaning there exists a non-zero vector v that gets mapped to zero, so Av = lambdav.

  3. “Explain power iteration and when it fails.” Expected answer: Repeatedly multiply and normalize. Converges because components along dominant eigenvector grow fastest. Fails when top two eigenvalues have equal magnitude or when starting vector is orthogonal to dominant eigenvector.

  4. “What does it mean for a matrix to be diagonalizable? When is it not?” Expected answer: Diagonalizable means it has n linearly independent eigenvectors. Fails when there is a repeated eigenvalue without a full set of eigenvectors (defective matrix).

  5. “How are eigenvalues related to matrix stability in dynamical systems?” Expected answer: For x_{t+1} = Ax_t, eigenvalues determine long-term behavior. lambda < 1 means decay (stable), lambda > 1 means growth (unstable), lambda = 1 means oscillation.

  6. “Why do covariance matrices always have real, non-negative eigenvalues?” Expected answer: Covariance matrices are symmetric positive semi-definite. Symmetric matrices have real eigenvalues, and positive semi-definiteness ensures they are non-negative (representing variance in each principal direction).

  7. “What is the computational complexity of eigenvalue computation, and why does power iteration matter for large matrices?” Expected answer: Full eigendecomposition is O(n^3). Power iteration is O(n^2) per iteration and may converge quickly for dominant eigenvalue, making it practical for huge sparse matrices like in PageRank.

Hints in Layers (Treat as pseudocode guidance)

Hint 1: Start with 2x2 matrices only. For 2x2, the characteristic polynomial is always quadratic: lambda^2 - trace*lambda + det = 0. Use the quadratic formula. This avoids polynomial root-finding for now.

Hint 2: Power iteration in pseudocode:

v = random_vector()
v = v / norm(v)
for _ in range(max_iterations):
    v_new = A @ v
    eigenvalue = norm(v_new)  # Rayleigh quotient approximation
    v_new = v_new / norm(v_new)
    if norm(v_new - v) < tolerance:
        break
    v = v_new

Hint 3: To find ALL eigenvectors with power iteration, use deflation: after finding (lambda1, v1), compute A’ = A - lambda1 * outer(v1, v1) and run power iteration again on A’. The dominant eigenvector of A’ is the second eigenvector of A.

Hint 4: For visualization, draw the unit circle, then draw what A does to the unit circle (it becomes an ellipse). The ellipse’s major and minor axes ARE the eigenvectors! The axis lengths are eigenvalues .

Hint 5: Complex eigenvalues always come in conjugate pairs for real matrices. If you get lambda = a + bi, there is also lambda = a - bi. The rotation angle is arctan(b/a) and the scaling is sqrt(a^2 + b^2).

Books That Will Help

Topic Book Chapter
Eigenvalue Fundamentals “Linear Algebra Done Right” - Sheldon Axler Chapter 5
Power Iteration Algorithm “Numerical Linear Algebra” - Trefethen & Bau Chapter 27
Geometric Interpretation “Math for Programmers” - Paul Orland Chapter 7
Applications in ML (PCA, etc.) “Hands-On Machine Learning” - Aurelien Geron Chapter 8
Complex Eigenvalues “3D Math Primer for Graphics” - Dunn & Parberry Chapter 6
Diagonalization Theory “Introduction to Linear Algebra” - Gilbert Strang Chapter 6
Numerical Stability “Numerical Recipes” - Press et al. Chapter 11

6. Validation, Pitfalls, and Completion

Common Pitfalls and Debugging

Problem 1: “Outputs drift after a few iterations”

  • Why: Hidden numerical instability (unscaled features, aggressive step size, or repeated subtraction of nearly equal values).
  • Fix: Normalize inputs, reduce step size, and track relative error rather than only absolute error.
  • Quick test: Run the same task with two scales of input (for example x and 10x) and compare normalized error curves.

Problem 2: “Results are inconsistent across runs”

  • Why: Random seeds, data split randomness, or non-deterministic ordering are uncontrolled.
  • Fix: Set seeds, log configuration, and store split indices and hyperparameters with each run.
  • Quick test: Re-run three times with the same seed and confirm metrics remain inside a tight tolerance band.

Problem 3: “The project works on the demo case but fails on edge cases”

  • Why: Tests only cover happy-path inputs.
  • Fix: Add adversarial inputs (empty values, extreme ranges, near-singular matrices, rare classes).
  • Quick test: Build an edge-case test matrix and ensure every scenario reports expected behavior.

Definition of Done

  • Core functionality works on reference inputs
  • Edge cases are tested and documented
  • Results are reproducible (seeded and versioned configuration)
  • Performance or convergence behavior is measured and explained
  • A short retrospective explains what failed first and how you fixed it

7. Extension Ideas

  1. Add a stress-test mode with adversarial inputs.
  2. Add a short benchmark report (runtime + memory + error trend).
  3. Add a reproducibility bundle (seed, config, and fixed test corpus).

8. Why This Project Matters

Eigenvalues/eigenvectors are the most important concept for ML. PCA finds eigenvectors of the covariance matrix. PageRank is an eigenvector problem. Neural network stability depends on eigenvalues. Building this intuition visually is invaluable.

This project is valuable because it creates observable evidence of mathematical reasoning under real implementation constraints.