Final Exam Topics
Geometric Algorithms
Boston University
Fall 2023

(Systems of) Linear Equations

• Counting solutions
  
  • Consistency
    
  • Uniqueness
    
  • Infinite solutions
    
• Coefficient matrices
  
• Augmented matrices
  
• Finding solutions
  
  • Elimination
    
  • Back substitution
    
• Verifying solutions
  
• Elementary row operations
  
  • Replacement
    
  • Interchange
    
  • Scaling
    
• Row Equivalence
  

Gaussian elimination

• Echelon forms
  
• Reduced echelon forms
  
• Pivot positions and pivot rows
  
• Performing Gaussian elimination
  
  • Elimination
    
  • Back substitution
    
• Interpreting echelon forms
  
  • Basic variables
    
  • Free variables
    
  • General-form solutions
    
• EXCLUDING: FLOP counts
  

Vector equations

• (Column) vectors
  
• Vector operations
  
  • Addition
    
    • Parallelogram rule
      
    • Tip-to-tail rule
      
  • Multiplication
    
  • Scaling
    
  • Algebraic properties
    
• Linear combinations
  
• Vector equations
  
  • Equivalence with systems of linear equations
    
• Span
  

Ax = b

• Matrix-vector multiplication
  
  • Algebraic properties
    
    • Additivity
      
    • Homogeneity
      
• The matrix equation
  
  • Equivalence with systems of linear equations
    
• Inner products
  
• The identity matrix
  

Linear independence

• Linear dependence
  
• Spanning sets
  
• EXCLUDING: Network flow
  

Linear transforms

• Definitions
  
  • Domain
    
  • Codomain
    
  • Image
    
  • Range
    
• Linearity
  
• Algebraic properties (of Linear Transformations)
  
• Simple linear transformations
  
  • Shearing
    
  • Contraction
    
  • Dilation
    
  • Rotation
    
  • Reflection
    
  • Projection
    
• Simple non-linear transformations
  
  • Translation
    
• Non-geometric word problems
  
  • Manufacturing example
    

Matrix of a linear transformation

• Finding the matrix implementing a linear transformation
  
• Kinds of linear transformations
  
  • One-to-one
    
  • Onto
    
• 2 × 2 Determinants
  
  • EXCLUDING: Relationship with area
    

Matrix algebra

• Matrix Operations
  
  • Addition
    
  • Multiplication
    
    • Relation to composition
      
  • Scaling
    
  • Algebraic properties
    
    • Matrix multiplication is not commutative
      
  • Powers
    
  • Transposition
    
• Inner product
  
• EXCLUDING: Computational viewpoint
  

Matrix inverses

• Invertibility
  
• Singular vs. non-singular matrices
  
• Determinants
  
• Equivalence to solving systems of linear equations
  
• EXCLUDING:
  
  • Computational view
    
  • Ill-conditioned matrices
    

The invertible matrix theorem

Markov chains

• Linear dynamical systems/linear difference equations
  
• Probability vectors
  
• Stochastic matrices
  
• Steady-states
  
• Convergence to steady states
  

Matrix factorization

• LU factorization
  
• Elementary matrices
  
• EXCLUDING:
  
  • Forward substitution
    
  • FLOP counts
    
  • Pivoting
    

Computer graphics

• Homogeneous coordinates
  
• Rotation matrices
  
• Perspective projections
  
• Composing transformation
  
• EXCLUDING: programming aspects of graphics
  

Subspaces

• Equivalence with spans
  
• Column space
  
• Null space
  
• Basis
  
  • of column space
    
  • of null space
    

Dimension and rank

• Coordinate systems
  
• Dimension of a subspace
  
  • of column space
    
  • of null space
    
• Rank
  
• Rank-nullity theorem
  
• EXCLUDING: Isomorphism
  

Eigenvectors and eigenvalues

• Checking eigenvectors/values
  
• Finding eigenvectors
  
• Eigenspace
  
• Eigenvalues of triangular matrices
  
• Invertibility and eigenvalues
  
• EXCLUDING: Eigenvalues solve difference equations
  

The characteristic equation

• Determinants
  
• Finding the characteristic polynomial
  
• Finding eigenvalues
  
• Similarity
  
• EXCLUDING: complete solution for a Markov chain
  

Diagonalizability

• Diagonal matrices
  
• Similar Matrices
  
• Diagonalizability
  
• Eigenbasis
  
• EXCLUDING: Exposing the behavior of dynamical systems
  

PageRank

• Random walks
  
• Reflecting vs. absorbing boundaries
  
• The power method
  
• EXCLUDING: The history
  

Analytic geometry

• Inner product/dot product
  
• Norm
  
• Distance
  
• Angle
  
• Orthogonality
  
• EXCLUDING: Cosine similarity
  

Orthogonal Sets and Projection

• Orthogonal basis
  
• Orthogonal projection
  
• Projections and coordinates
  
• Orthonormal sets
  
• Orthogonal matrices
  

Least Squares

• Finding least squares
  
• Normal equations
  
• Projecting onto a basis
  

Linear Models

• Best fit line/quadratic
  
• Multiple regression
  
• Design matrices
  

Symmetric matrices

• Orthogonal diagonalization
  
• Quadratic forms
  
• EXCLUDING:
  
  • Definiteness
    
  • Constrained optimization