Coding the Matrix
Subtitle: Linear Algebra through Computer Science Applications
Publisher: Newtonian Press
Published: Jul 26, 2013
Format: paperback
Number of pages: 528
ISBN-13: 9780615856735
Notes: Source title: Coding the Matrix: Linear Algebra through Computer Science Applications
Table of contents: label: 0
title: The Function (and Other Mathematical and Computational Preliminaries)
pagenum: 1; label: 0.1
title: Set Terminology and Notation
pagenum: 1; label: 0.2
title: Cartesian Product
pagenum: 1; label: 0.3
title: The Function
pagenum: 2; label: 0.3.1
title: Functions Versus Procedures, Versus Computational Problems
pagenum: 3; label: 0.3.2
title: The Two Computational Problems Related to a Function
pagenum: 4; label: 0.3.3
title: Notation for the Set of Functions with Given Domain and Co-domain
pagenum: 5; label: 0.3.4
title: Identity Function
pagenum: 5; label: 0.3.5
title: Composition of Functions
pagenum: 5; label: 0.3.6
title: Associativity of Function Composition
pagenum: 6; label: 0.3.7
title: Functional Inverse
pagenum: 6; label: 0.4
title: Probability
pagenum: 9; label: 0.4.1
title: Probability Distributions
pagenum: 9; label: 0.4.2
title: Events, and Adding Probabilities
pagenum: 10; label: 0.4.3
title: Applying a Function to a Random Input
pagenum: 11; label: 0.4.4
title: Perfect Secrecy
pagenum: 12; label: 0.4.5
title: Perfect Secrecy and Invertible Functions
pagenum: 13; label: 0.5
title: Lab: Introduction to Python—Sets, Lists, Dictionaries, and Comprehensions
pagenum: 14; label: 0.5.1
title: Simple Expressions
pagenum: 15; label: 0.5.2
title: Assignment Statements
pagenum: 16; label: 0.5.3
title: Conditional Expressions
pagenum: 17; label: 0.5.4
title: Sets
pagenum: 17; label: 0.5.5
title: Lists
pagenum: 20; label: 0.5.6
title: Tuples
pagenum: 24; label: 0.5.7
title: Other Things to Iterate Over
pagenum: 25; label: 0.5.8
title: Dictionaries
pagenum: 26; label: 0.5.9
title: Defining One-Line Procedures
pagenum: 30; label: 0.6
title: Lab: Python Modules and Control Structures — and Inverse Index
pagenum: 31; label: 0.6.1
title: Using Existing Modules
pagenum: 31; label: 0.6.2
title: Creating Your Own Modules
pagenum: 32; label: 0.6.3
title: Loops and Conditional Statements
pagenum: 33; label: 0.6.4
title: Grouping in Python Using Indentation
pagenum: 33; label: 0.6.5
title: Breaking Out of a Loop
pagenum: 34; label: 0.6.6
title: Reading from a File
pagenum: 34; label: 0.6.7
title: Mini-Search Engine
pagenum: 34; label: 0.7
title: Review Questions
pagenum: 35; label: 0.8
title: Problems
pagenum: 36; label: 1
title: The Field
pagenum: 39; label: 1.1
title: Introduction to Complex Numbers
pagenum: 39; label: 1.2
title: Complex Numbers in Python
pagenum: 40; label: 1.3
title: Abstracting over Fields
pagenum: 41; label: 1.4
title: Playing with C
pagenum: 42; label: 1.4.1
title: The Absolute Value of a Complex Number
pagenum: 43; label: 1.4.2
title: Adding Complex Numbers
pagenum: 44; label: 1.4.3
title: Multiplying Complex Numbers by a Positive Real Number
pagenum: 46; label: 1.4.4
title: Multiplying Complex Numbers by a Negative Number: Rotation by 180 Degrees
pagenum: 46; label: 1.4.5
title: Multiplying by i: Rotation by 90 Degrees
pagenum: 47; label: 1.4.6
title: The Unit Circle in the Complex Plane: Argument and Angle
pagenum: 49; label: 1.4.7
title: Euler's Formula
pagenum: 50; label: 1.4.8
title: Polar Representation for Complex Numbers
pagenum: 51; label: 1.4.9
title: The First Law of Exponentiation
pagenum: 51; label: 1.4.10
title: Rotation by θ Radians
pagenum: 52; label: 1.4.11
title: Combining Operations
pagenum: 53; label: 1.4.12
title: Beyond Two Dimensions
pagenum: 54; label: 1.5
title: Playing with GF(2)
pagenum: 54; label: 1.5.1
title: Perfect Secrecy Revisited
pagenum: 54; label: 1.5.2
title: Network Coding
pagenum: 56; label: 1.6
title: Review Questions
pagenum: 57; label: 1.7
title: Problems
pagenum: 58; label: 2
title: The Vector
pagenum: 61; label: 2.1
title: What Is a Vector?
pagenum: 63; label: 2.2
title: Vectors Are Functions
pagenum: 64; label: 2.2.1
title: Representation of Vectors Using Python Dictionaries
pagenum: 65; label: 2.2.2
title: Sparsity
pagenum: 65; label: 2.3
title: What Can We Represent with Vectors?
pagenum: 65; label: 2.4
title: Vector Addition
pagenum: 67; label: 2.4.1
title: Translation and Vector Addition
pagenum: 67; label: 2.4.2
title: Vector Addition Is Associative and Commutative
pagenum: 68; label: 2.4.3
title: Vectors as Arrows
pagenum: 69; label: 2.5
title: Scalar-Vector Multiplication
pagenum: 70; label: 2.5.1
title: Scaling Arrows
pagenum: 71; label: 2.5.2
title: Associativity of Scalar-Vector Multiplication
pagenum: 72; label: 2.5.3
title: Line Segments through the Origin
pagenum: 72; label: 2.5.4
title: Lines through the Origin
pagenum: 73; label: 2.6
title: Combining Vector Addition and Scalar Multiplication
pagenum: 74; label: 2.6.1
title: Line Segments and Lines That Don't Go through the Origin
pagenum: 74; label: 2.6.2
title: Distributive Laws for Scalar-Vector Multiplication and Vector Addition
pagenum: 75; label: 2.6.3
title: First Look at Convex Combinations
pagenum: 76; label: 2.6.4
title: First Look at Affine Combinations
pagenum: 77; label: 2.7
title: Dictionary-Based Representations of Vectors
pagenum: 78; label: 2.7.1
title: Setter and Getter
pagenum: 79; label: 2.7.2
title: Scalar-Vector Multiplication
pagenum: 79; label: 2.7.3
title: Addition
pagenum: 80; label: 2.7.4
title: Vector Negative, Invertibility of Vector Addition, and Vector Subtraction
pagenum: 80; label: 2.8
title: Vectors over GF(2)
pagenum: 81; label: 2.8.1
title: Perfect Secrecy Re-Revisited
pagenum: 82; label: 2.8.2
title: All-or-Nothing Secret-Sharing Using GF(2)
pagenum: 82; label: 2.8.3
title: Lights Out
pagenum: 83; label: 2.9
title: Dot-Product
pagenum: 87; label: 2.9.1
title: Total Cost or Benefit
pagenum: 88; label: 2.9.2
title: Linear Equations
pagenum: 89; label: 2.9.3
title: Measuring Similarity
pagenum: 91; label: 2.9.4
title: Dot-Product of Vectors over GF(2)
pagenum: 94; label: 2.9.5
title: Parity Bit
pagenum: 95; label: 2.9.6
title: Simple Authentication Scheme
pagenum: 95; label: 2.9.7
title: Attacking the Simple Authentication Scheme
pagenum: 97; label: 2.9.8
title: Algebraic Properties of the Dot-Product
pagenum: 98; label: 2.9.9
title: Attacking the Simple Authentication Scheme, Revisited
pagenum: 99; label: 2.10
title: Our Implementation of Vec
pagenum: 100; label: 2.10.1
title: Syntax for Manipulating Vecs
pagenum: 100; label: 2.10.2
title: The Implementation
pagenum: 101; label: 2.10.3
title: Using Vecs
pagenum: 101; label: 2.10.4
title: Printing Vecs
pagenum: 101; label: 2.10.5
title: Copying Vecs
pagenum: 101; label: 2.10.6
title: From List to Vec
pagenum: 102; label: 2.11
title: Solving a Triangular System of Linear Equations
pagenum: 102; label: 2.11.1
title: Upper-Triangular Systems
pagenum: 102; label: 2.11.2
title: Backward Substitution
pagenum: 103; label: 2.11.3
title: First Implementation of Backward Substitution
pagenum: 104; label: 2.11.4
title: When Does the Algorithm Work?
pagenum: 105; label: 2.11.5
title: Backward Substitution with Arbitrary-Domain Vectors
pagenum: 105; label: 2.12
title: Lab: Comparing Voting Records Using Dot-Product
pagenum: 106; label: 2.12.1
title: Motivation
pagenum: 106; label: 2.12.2
title: Reading in the File
pagenum: 106; label: 2.12.3
title: Two Ways to Use Dot-Product to Compare Vectors
pagenum: 107; label: 2.12.4
title: Policy Comparison
pagenum: 107; label: 2.12.5
title: Not Your Average Democrat
pagenum: 108; label: 2.12.6
title: Bitter Rivals
pagenum: 108; label: 2.12.7
title: Open-Ended Study
pagenum: 108; label: 2.13
title: Review Questions
pagenum: 108; label: 2.14
title: Problems
pagenum: 109; label: 3
title: The Vector Space
pagenum: 113; label: 3.1
title: Linear Combination
pagenum: 113; label: 3.1.1
title: Definition of Linear Combination
pagenum: 113; label: 3.1.2
title: Uses of Linear Combinations
pagenum: 113; label: 3.1.3
title: From Coefficients to Linear Combination
pagenum: 115; label: 3.1.4
title: From Linear Combination to Coefficients
pagenum: 116; label: 3.2
title: Span
pagenum: 117; label: 3.2.1
title: Definition of Span
pagenum: 117; label: 3.2.2
title: A System of Linear Equations Implies Other Equations
pagenum: 118; label: 3.2.3
title: Generators
pagenum: 119; label: 3.2.4
title: Linear Combinations of Linear Combinations
pagenum: 120; label: 3.2.5
title: Standard Generators
pagenum: 121; label: 3.3
title: The Geometry of Sets of Vectors
pagenum: 122; label: 3.3.1
title: The Geometry of the Span of Vectors over R
pagenum: 122; label: 3.3.2
title: The Geometry of Solution Sets of Homogeneous Linear Systems
pagenum: 124; label: 3.3.3
title: The Two Representations of Flats Containing the Origin
pagenum: 125; label: 3.4
title: Vector Spaces
pagenum: 126; label: 3.4.1
title: What's Common to the Two Representations?
pagenum: 126; label: 3.4.2
title: Definition and Examples of Vector Space
pagenum: 127; label: 3.4.3
title: Subspaces
pagenum: 128; label: 3.4.4
title: Abstract Vector Spaces
pagenum: 130; label: 3.5
title: Affine Spaces
pagenum: 130; label: 3.5.1
title: Flats That Don't Go through the Origin
pagenum: 130; label: 3.5.2
title: Affine Combinations
pagenum: 131; label: 3.5.3
title: Affine Spaces
pagenum: 133; label: 3.5.4
title: Representing an Affine Space as the Solution Set of a Linear System
pagenum: 134; label: 3.5.5
title: The Two Representations, Revisited
pagenum: 135; label: 3.6
title: Linear Systems, Homogeneous and Otherwise
pagenum: 139; label: 3.6.1
title: The Homogeneous Linear System Corresponding to a General Linear System
pagenum: 139; label: 3.6.2
title: Number of Solutions Revisited
pagenum: 140; label: 3.6.3
title: Towards Intersecting a Plane and a Line
pagenum: 141; label: 3.6.4
title: Checksum Functions
pagenum: 141; label: 3.7
title: Review Questions
pagenum: 142; label: 3.8
title: Problems
pagenum: 143; label: 4
title: The Matrix
pagenum: 147; label: 4.1
title: What Is a Matrix?
pagenum: 147; label: 4.1.1
title: Traditional Matrices
pagenum: 147; label: 4.1.2
title: The Matrix Revealed
pagenum: 148; label: 4.1.3
title: Rows, Columns, and Entries
pagenum: 149; label: 4.1.4
title: Our Python Implementation of Matrices
pagenum: 150; label: 4.1.5
title: Identity Matrix
pagenum: 151; label: 4.1.6
title: Converting between Matrix Representations
pagenum: 151; label: 4.1.7
title: `matutil.py`
pagenum: 152; label: 4.2
title: Column Space and Row Space
pagenum: 152; label: 4.3
title: Matrices as Vectors
pagenum: 153; label: 4.4
title: Transpose
pagenum: 153; label: 4.5
title: Matrix-Vector and Vector-Matrix Multiplication in Terms of Linear Combinations
pagenum: 154; label: 4.5.1
title: Matrix-Vector Multiplication in Terms of Linear Combinations
pagenum: 154; label: 4.5.2
title: Vector-Matrix Multiplication in Terms of Linear Combinations
pagenum: 155; label: 4.5.3
title: Formulating Expressing a Given Vector as a Linear Combination as a Matrix-Vector Equation
pagenum: 156; label: 4.5.4
title: Solving a Matrix-Vector Equation
pagenum: 157; label: 4.6
title: Matrix-Vector Multiplication in Terms of Dot-Products
pagenum: 159; label: 4.6.1
title: Definitions
pagenum: 159; label: 4.6.2
title: Example Applications
pagenum: 160; label: 4.6.3
title: Formulating a System of Linear Equations as a Matrix-Vector Equation
pagenum: 162; label: 4.6.4
title: Triangular Systems and Triangular Matrices
pagenum: 163; label: 4.6.5
title: Algebraic Properties of Matrix-Vector Multiplication
pagenum: 165; label: 4.7
title: Null Space
pagenum: 165; label: 4.7.1
title: Homogeneous Linear Systems and Matrix Equations
pagenum: 165; label: 4.7.2
title: The Solution Space of a Matrix-Vector Equation
pagenum: 166; label: 4.7.3
title: Introduction to Error-Correcting Codes
pagenum: 167; label: 4.7.4
title: Linear Codes
pagenum: 168; label: 4.7.5
title: The Hamming Code
pagenum: 168; label: 4.8
title: Computing Sparse Matrix-Vector Product
pagenum: 169; label: 4.9
title: The Matrix Meets the Function
pagenum: 170; label: 4.9.1
title: From Matrix to Function
pagenum: 170; label: 4.9.2
title: From Function to Matrix
pagenum: 170; label: 4.9.3
title: Examples of Deriving the Matrix
pagenum: 171; label: 4.10
title: Linear Functions
pagenum: 173; label: 4.10.1
title: Which Functions Can Be Expressed as a Matrix-Vector Product
pagenum: 173; label: 4.10.2
title: Definition and Simple Examples
pagenum: 173; label: 4.10.3
title: Linear Functions and Zero Vectors
pagenum: 175; label: 4.10.4
title: What Do Linear Functions Have to Do with Lines?
pagenum: 176; label: 4.10.5
title: Linear Functions That Are One-to-One
pagenum: 176; label: 4.10.6
title: Linear Functions That Are Onto
pagenum: 177; label: 4.10.7
title: A Linear Function from $F^C$ to $F^R$ Can Be Represented by a Matrix
pagenum: 178; label: 4.10.8
title: Diagonal Matrices
pagenum: 178; label: 4.11
title: Matrix-Matrix Multiplication
pagenum: 179; label: 4.11.1
title: Matrix-Matrix Multiplication in Terms of Matrix-Vector and Vector-Matrix Multiplication
pagenum: 179; label: 4.11.2
title: Matrix-Matrix Multiplication and Function Composition
pagenum: 182; label: 4.11.3
title: Transpose of Matrix-Matrix Product
pagenum: 184; label: 4.11.4
title: Column Vector and Row Vector
pagenum: 185; label: 4.11.5
title: Every Vector Is Interpreted as a Column Vector
pagenum: 185; label: 4.11.6
title: Linear Combinations of Linear Combinations Revisited
pagenum: 186; label: 4.12
title: Inner Product and Outer Product
pagenum: 187; label: 4.12.1
title: Inner Product
pagenum: 187; label: 4.12.2
title: Outer Product
pagenum: 187; label: 4.13
title: From Function Inverse to Matrix Inverse
pagenum: 187; label: 4.13.1
title: The Inverse of a Linear Function Is Linear
pagenum: 187; label: 4.13.2
title: The Matrix Inverse
pagenum: 188; label: 4.13.3
title: Uses of Matrix Inverse
pagenum: 189; label: 4.13.4
title: More about Matrix Inverse
pagenum: 191; label: 4.14
title: Lab: Error-Correcting Codes
pagenum: 192; label: 4.14.1
title: The Check Matrix
pagenum: 192; label: 4.14.2
title: The Generator Matrix
pagenum: 192; label: 4.14.3
title: Hamming's Code
pagenum: 192; label: 4.14.4
title: Decoding
pagenum: 192; label: 4.14.5
title: Error Syndrome
pagenum: 193; label: 4.14.6
title: Finding the Error
pagenum: 193; label: 4.14.7
title: Putting It All Together
pagenum: 194; label: 4.15
title: Lab: Transformations in 2D Geometry
pagenum: 196; label: 4.15.1
title: Our Representation for Points in the Plane
pagenum: 196; label: 4.15.2
title: Transformations
pagenum: 196; label: 4.15.3
title: Image Representation
pagenum: 197; label: 4.15.4
title: Loading and Displaying Images
pagenum: 198; label: 4.15.5
title: Linear Transformations
pagenum: 198; label: 4.15.6
title: Translation
pagenum: 199; label: 4.15.7
title: Scaling
pagenum: 199; label: 4.15.8
title: Rotation
pagenum: 199; label: 4.15.9
title: Rotation about a Center Other than the Origin
pagenum: 200; label: 4.15.10
title: Reflection
pagenum: 200; label: 4.15.11
title: Color Transformations
pagenum: 200; label: 4.15.12
title: Reflection More Generally
pagenum: 200; label: 4.16
title: Review Questions
pagenum: 200; label: 4.17
title: Problems
pagenum: 201; label: 5
title: The Basis
pagenum: 209; label: 5.1
title: Coordinate Systems
pagenum: 209; label: 5.1.1
title: René Descartes' Idea
pagenum: 209; label: 5.1.2
title: Coordinate Representation
pagenum: 209; label: 5.1.3
title: Coordinate Representation and Matrix-Vector Multiplication
pagenum: 210; label: 5.2
title: First Look at Lossy Compression
pagenum: 210; label: 5.2.1
title: Strategy 1: Replace Vector with Closest Sparse Vector
pagenum: 211; label: 5.2.2
title: Strategy 2: Represent Image Vector by Its Coordinate Representation
pagenum: 212; label: 5.3
title: Two Greedy Algorithms for Finding a Set of Generators
pagenum: 213; label: 5.3.1
title: Grow Algorithm
pagenum: 213; label: 5.3.2
title: Shrink Algorithm
pagenum: 214; label: 5.3.3
title: When Greed Fails
pagenum: 214; label: 5.4
title: Minimum Spanning Forest and GF(2)
pagenum: 216; label: 5.4.1
title: Definitions
pagenum: 216; label: 5.4.2
title: The Grow Algorithm and the Shrink Algorithm for Minimum Spanning Forest
pagenum: 217; label: 5.4.3
title: Formulating Minimum Spanning Forest in Linear Algebra
pagenum: 218; label: 5.5
title: Linear Dependence
pagenum: 219; label: 5.5.1
title: The Superfluous-Vector Lemma
pagenum: 219; label: 5.5.2
title: Defining Linear Dependence
pagenum: 220; label: 5.5.3
title: Linear Dependence in Minimum Spanning Forest
pagenum: 221; label: 5.5.4
title: Properties of Linear (In)dependence
pagenum: 222; label: 5.5.5
title: Analyzing the Grow Algorithm
pagenum: 223; label: 5.5.6
title: Analyzing the Shrink Algorithm
pagenum: 223; label: 5.6
title: Basis
pagenum: 224; label: 5.6.1
title: Defining Basis
pagenum: 224; label: 5.6.2
title: The Standard Basis for F^L
pagenum: 226; label: 5.6.3
title: Towards Showing That Every Vector Space Has a Basis
pagenum: 227; label: 5.6.4
title: Any Finite Set of Vectors Contains a Basis for Its Span
pagenum: 227; label: 5.6.5
title: Any Linearly Independent Subset of Vectors Belonging to V Can Be Extended to Form a Basis for V
pagenum: 228; label: 5.7
title: Unique Representation
pagenum: 228; label: 5.7.1
title: Uniqueness of Representation in Terms of a Basis
pagenum: 228; label: 5.8
title: Change of Basis, First Look
pagenum: 229; label: 5.8.1
title: The Function from Representation to Vector
pagenum: 229; label: 5.8.2
title: From One Representation to Another
pagenum: 229; label: 5.9
title: Perspective Rendering
pagenum: 230; label: 5.9.1
title: Points in the World
pagenum: 230; label: 5.9.2
title: The Camera and the Image Plane
pagenum: 231; label: 5.9.3
title: The Camera Coordinate System
pagenum: 232; label: 5.9.4
title: From the Camera Coordinates of a Point in the Scene to the Camera Coordinates of the Corresponding Point in the Image Plane
pagenum: 233; label: 5.9.5
title: From World Coordinates to Camera Coordinates
pagenum: 235; label: 5.9.6
title: To Pixel Coordinates
pagenum: 236; label: 5.10
title: Computational Problems Involving Finding a Basis
pagenum: 236; label: 5.11
title: The Exchange Lemma
pagenum: 237; label: 5.11.1
title: The Lemma
pagenum: 237; label: 5.11.2
title: Proof of Correctness of the Grow Algorithm for MSF
pagenum: 238; label: 5.12
title: Lab: Perspective Rectification
pagenum: 238; label: 5.12.1
title: The Camera Basis
pagenum: 240; label: 5.12.2
title: The Whiteboard Basis
pagenum: 240; label: 5.12.3
title: Mapping from Pixels to Points on the Whiteboard
pagenum: 241; label: 5.12.4
title: Mapping a Point Not on the Whiteboard to the Corresponding Point on the Whiteboard
pagenum: 242; label: 5.12.5
title: The Change-of-Basis Matrix
pagenum: 243; label: 5.12.6
title: Computing the Change-of-Basis Matrix
pagenum: 243; label: 5.12.7
title: Image Representation
pagenum: 246; label: 5.12.8
title: Synthesizing the Perspective-Free Image
pagenum: 246; label: 5.13
title: Review Questions
pagenum: 247; label: 5.14
title: Problems
pagenum: 248; label: 6
title: Dimension
pagenum: 257; label: 6.1
title: The Size of a Basis
pagenum: 257; label: 6.1.1
title: The Morphing Lemma and Its Implications
pagenum: 257; label: 6.1.2
title: Proof of the Morphing Lemma
pagenum: 258; label: 6.2
title: Dimension and Rank
pagenum: 260; label: 6.2.1
title: Definitions and Examples
pagenum: 260; label: 6.2.2
title: Geometry
pagenum: 262; label: 6.2.3
title: Dimension and Rank in Graphs
pagenum: 262; label: 6.2.4
title: The Cardinality of a Vector Space over GF(2)
pagenum: 263; label: 6.2.5
title: The Dimension Principle
pagenum: 263; label: 6.2.6
title: For a Finite Set D, Every Subspace of F^D Has a Basis
pagenum: 264; label: 6.2.7
title: The Rank Theorem
pagenum: 264; label: 6.2.8
title: Simple Authentication Revisited
pagenum: 266; label: 6.3
title: Direct Sum
pagenum: 267; label: 6.3.1
title: Definition
pagenum: 267; label: 6.3.2
title: Generators for the Direct Sum
pagenum: 268; label: 6.3.3
title: Basis for the Direct Sum
pagenum: 269; label: 6.3.4
title: Unique Decomposition of a Vector
pagenum: 269; label: 6.3.5
title: Complementary Subspaces
pagenum: 270; label: 6.4
title: Dimension and Linear Functions
pagenum: 272; label: 6.4.1
title: Linear Function Invertibility
pagenum: 272; label: 6.4.2
title: The Largest Invertible Subfunction
pagenum: 272; label: 6.4.3
title: The Kernel-Image Theorem
pagenum: 274; label: 6.4.4
title: Linear Function Invertibility, Revisited
pagenum: 275; label: 6.4.5
title: The Rank-Nullity Theorem
pagenum: 275; label: 6.4.6
title: Checksum Problem Revisited
pagenum: 275; label: 6.4.7
title: Matrix Invertibility
pagenum: 276; label: 6.4.8
title: Matrix Invertibility and Change of Basis
pagenum: 277; label: 6.5
title: Duality
pagenum: 278; label: 6.5.1
title: Conversions between Representations
pagenum: 278; label: 6.5.2
title: The Dual of a Vector Space
pagenum: 280; label: 6.5.3
title: The Dual Dimension Theorem
pagenum: 281; label: 6.5.4
title: From Generators for V to Generators for V*, and Vice Versa
pagenum: 282; label: 6.5.5
title: The Duality Theorem
pagenum: 282; label: 6.6
title: Review Questions
pagenum: 283; label: 6.7
title: Problems
pagenum: 283; label: 7
title: Gaussian Elimination
pagenum: 291; label: 7.1
title: Echelon Form
pagenum: 292; label: 7.1.1
title: From Echelon Form to a Basis for Row Space
pagenum: 293; label: 7.1.2
title: Rowlist in Echelon Form
pagenum: 294; label: 7.1.3
title: Sorting Rows by Position of the Leftmost Nonzero
pagenum: 294; label: 7.1.4
title: Elementary Row-Addition Operations
pagenum: 295; label: 7.1.5
title: Multiplying by an Elementary Row-Addition Matrix
pagenum: 296; label: 7.1.6
title: Row-Addition Operations Preserve Row Space
pagenum: 297; label: 7.1.7
title: Basis, Rank, and Linear Independence through Gaussian Elimination
pagenum: 298; label: 7.1.8
title: When Gaussian Elimination Fails
pagenum: 298; label: 7.1.9
title: Pivoting, and Numerical Analysis
pagenum: 299; label: 7.2
title: Gaussian Elimination over GF(2)
pagenum: 299; label: 7.3
title: Using Gaussian Elimination for Other Problems
pagenum: 300; label: 7.3.1
title: There Is an Invertible Matrix M Such That M A Is in Echelon Form
pagenum: 301; label: 7.3.2
title: Computing M without Matrix Multiplications
pagenum: 301; label: 7.4
title: Solving a Matrix-Vector Equation Using Gaussian Elimination
pagenum: 304; label: 7.4.1
title: Solving a Matrix-Vector Equation When the Matrix Is in Echelon Form: The Invertible Case
pagenum: 304; label: 7.4.2
title: Coping with Zero Rows
pagenum: 304; label: 7.4.3
title: Coping with Irrelevant Columns
pagenum: 305; label: 7.4.4
title: Finding a Basis for the Null Space
pagenum: 305; label: 7.5
title: Factoring Integers
pagenum: 306; label: 7.5.1
title: First Attempt at Factoring
pagenum: 307; label: 7.6
title: Lab: Threshold Secret-Sharing
pagenum: 308; label: 7.6.1
title: First Attempt
pagenum: 308; label: 7.6.2
title: Scheme That Works
pagenum: 309; label: 7.6.3
title: Implementing the Scheme
pagenum: 310; label: 7.6.4
title: Generating u
pagenum: 310; label: 7.6.5
title: Finding Vectors That Satisfy the Requirement
pagenum: 311; label: 7.6.6
title: Sharing a String
pagenum: 311; label: 7.7
title: Lab: Factoring Integers
pagenum: 312; label: 7.7.1
title: First Attempt to Use Square Roots
pagenum: 312; label: 7.7.2
title: Euclid's Algorithm for Greatest Common Divisor
pagenum: 312; label: 7.7.3
title: Using Square Roots Revisited
pagenum: 313; label: 7.8
title: Review Questions
pagenum: 318; label: 8
title: The Inner Product
pagenum: 325; label: 8.1
title: The Fire Engine Problem
pagenum: 325; label: 8.1.1
title: Distance, Length, Norm, Inner Product
pagenum: 326; label: 8.2
title: The Inner Product for Vectors over the Reals
pagenum: 326; label: 8.2.1
title: Norms of Vectors over the Reals
pagenum: 326; label: 8.3
title: Orthogonality
pagenum: 328; label: 8.3.1
title: Properties of Orthogonality
pagenum: 328; label: 8.3.2
title: Decomposition of b into Parallel and Perpendicular Components
pagenum: 329; label: 8.3.3
title: Orthogonality Property of the Solution to the Fire Engine Problem
pagenum: 330; label: 8.3.4
title: Finding the Projection and the Closest Point
pagenum: 331; label: 8.3.5
title: Solution to the Fire Engine Problem
pagenum: 332; label: 8.3.6
title: Outer Product and Projection
pagenum: 333; label: 8.3.7
title: Towards Solving the Higher-Dimensional Version
pagenum: 334; label: 8.4
title: Lab: Machine Learning
pagenum: 334; label: 8.4.1
title: The Data
pagenum: 334; label: 8.4.2
title: Supervised Learning
pagenum: 335; label: 8.4.3
title: Selecting the Classifier That Minimizes the Error on the Training Data
pagenum: 335; label: 8.4.4
title: Nonlinear Optimization by Hill-Climbing
pagenum: 336; label: 8.4.5
title: Gradient
pagenum: 337; label: 8.4.6
title: Getting the Data
pagenum: 339; label: 8.4.7
title: Evaluating a Hypothesis
pagenum: 339; label: 8.4.8
title: Finding a Good Hypothesis
pagenum: 339; label: 8.5
title: Review Questions
pagenum: 340; label: 8.6
title: Problems
pagenum: 340; label: 9
title: Orthogonalization
pagenum: 343; label: 9.1
title: Projection Orthogonal to Multiple Vectors
pagenum: 344; label: 9.1.1
title: Orthogonal to a Set of Vectors
pagenum: 344; label: 9.1.2
title: Projecting onto and Orthogonal to a Vector Space
pagenum: 345; label: 9.1.3
title: First Attempt at Projecting Orthogonal to a List of Vectors
pagenum: 346; label: 9.2
title: Projecting b Orthogonal to a List of Mutually Orthogonal Vectors
pagenum: 347; label: 9.2.1
title: Proving the Correctness of project_orthogonal
pagenum: 347; label: 9.2.2
title: Augmenting project_orthogonal
pagenum: 349; label: 9.3
title: Building an Orthogonal Set of Generators
pagenum: 351; label: 9.3.1
title: The orthogonalize Procedure
pagenum: 351; label: 9.3.2
title: Proving the Correctness of orthogonalize
pagenum: 352; label: 9.4
title: Solving the Computational Problem: Closest Point in the Span of Many Vectors
pagenum: 354; label: 9.5
title: Solving Other Problems Using orthogonalize
pagenum: 354; label: 9.5.1
title: Computing a Basis
pagenum: 355; label: 9.5.2
title: Computing a Subset Basis
pagenum: 355; label: 9.5.3
title: augmented_orthogonalize
pagenum: 356; label: 9.5.4
title: Algorithms That Work in the Presence of Rounding Errors
pagenum: 356; label: 9.6
title: Orthogonal Complement
pagenum: 357; label: 9.6.1
title: Definition of Orthogonal Complement
pagenum: 357; label: 9.6.2
title: Orthogonal Complement and Direct Sum
pagenum: 357; label: 9.6.3
title: Normal to a Plane in R^3 Given as Span or Affine Hull
pagenum: 358; label: 9.6.4
title: Orthogonal Complement and Null Space and Dual Space
pagenum: 359; label: 9.6.5
title: Normal to a Plane in R^3 Given by an Equation
pagenum: 359; label: 9.6.6
title: Computing the Orthogonal Complement
pagenum: 359; label: 9.7
title: The QR Factorization
pagenum: 360; label: 9.7.1
title: Orthogonal and Column-Orthogonal Matrices
pagenum: 360; label: 9.7.2
title: Defining the QR Factorization of a Matrix
pagenum: 361; label: 9.7.3
title: Requiring A to Have Linearly Independent Columns
pagenum: 361; label: 9.8
title: Using the QR Factorization to Solve a Matrix Equation Ax = b
pagenum: 362; label: 9.8.1
title: The Square Case
pagenum: 362; label: 9.8.2
title: Correctness in the Square Case
pagenum: 363; label: 9.8.3
title: The Least-Squares Problem
pagenum: 364; label: 9.8.4
title: The Coordinate Representation in Terms of the Columns of a Column-Orthogonal Matrix
pagenum: 364; label: 9.8.5
title: Using QR_solve When A Has More Rows Than Columns
pagenum: 365; label: 9.9
title: Applications of Least Squares
pagenum: 365; label: 9.9.1
title: Linear Regression (Line-Fitting)
pagenum: 365; label: 9.9.2
title: Fitting to a Quadratic
pagenum: 366; label: 9.9.3
title: Fitting to a Quadratic in Two Variables
pagenum: 367; label: 9.9.4
title: Coping with Approximate Data in the Industrial Espionage Problem
pagenum: 367; label: 9.9.5
title: Coping with Approximate Data in the Sensor Node Problem
pagenum: 368; label: 9.9.6
title: Using the Method of Least Squares in the Machine-Learning Problem
pagenum: 369; label: 9.10
title: Review Questions
pagenum: 370; label: 9.11
title: Problems
pagenum: 371; label: 10
title: Special Bases
pagenum: 379; label: 10.1
title: Closest k-Sparse Vector
pagenum: 379; label: 10.2
title: Closest Vector Whose Representation with Respect to a Given Basis Is k-Sparse
pagenum: 380; label: 10.2.1
title: Finding the Coordinate Representation in Terms of an Orthonormal Basis
pagenum: 380; label: 10.2.2
title: Multiplication by a Column-Orthogonal Matrix Preserves Norm
pagenum: 381; label: 10.3
title: Wavelets
pagenum: 382; label: 10.3.1
title: One-Dimensional "Images" of Different Resolutions
pagenum: 382; label: 10.3.2
title: Decomposing V_n as a Direct Sum
pagenum: 383; label: 10.3.3
title: The Wavelet Bases
pagenum: 384; label: 10.3.4
title: The Basis for V_1
pagenum: 385; label: 10.3.5
title: General n
pagenum: 385; label: 10.3.6
title: The First Stage of Wavelet Transformation
pagenum: 386; label: 10.3.7
title: The Subsequent Levels of Wavelet Decomposition
pagenum: 387; label: 10.3.8
title: Normalizing
pagenum: 389; label: 10.3.9
title: The Backward Transform
pagenum: 389; label: 10.3.10
title: Implementation
pagenum: 389; label: 10.4
title: Polynomial Evaluation and Interpolation
pagenum: 390; label: 10.5
title: Fourier Transform
pagenum: 391; label: 10.6
title: Discrete Fourier Transform
pagenum: 393; label: 10.6.1
title: The Laws of Exponentiation
pagenum: 393; label: 10.6.2
title: The n Stopwatches
pagenum: 394; label: 10.6.3
title: Discrete Fourier Space: Sampling the Basis Functions
pagenum: 394; label: 10.6.4
title: The Inverse of the Fourier Matrix
pagenum: 395; label: 10.6.5
title: The Fast Fourier Algorithm
pagenum: 397; label: 10.7
title: The Inner Product for the Field of Complex Numbers
pagenum: 399; label: 10.8
title: Circulant Matrices
pagenum: 401; label: 10.8.1
title: Multiplying a Circulant Matrix by a Column of the Fourier Matrix
pagenum: 402; label: 10.8.2
title: Circulant Matrices and Change of Basis
pagenum: 403; label: 10.9
title: Lab: Using Wavelets for Compression
pagenum: 403; label: 10.9.1
title: Unnormalized Forward Transform
pagenum: 404; label: 10.9.2
title: Normalization in the Forward Transform
pagenum: 405; label: 10.9.3
title: Compression by Suppression
pagenum: 406; label: 10.9.4
title: Unnormalizing
pagenum: 407; label: 10.9.5
title: Unnormalized Backward Transform
pagenum: 407; label: 10.9.6
title: Backward Transform
pagenum: 407; label: 10.9.7
title: Auxiliary Procedure
pagenum: 407; label: 10.9.8
title: Two-Dimensional Wavelet Transform
pagenum: 408; label: 10.9.9
title: Forward Two-Dimensional Transform
pagenum: 409; label: 10.9.10
title: More Auxiliary Procedures
pagenum: 410; label: 10.9.11
title: Two-Dimensional Backward Transform
pagenum: 411; label: 10.9.12
title: Experimenting with Compression of Images
pagenum: 412; label: 10.10
title: Review Questions
pagenum: 412; label: 10.11
title: Problems
pagenum: 412; label: 11
title: The Singular Value Decomposition
pagenum: 415; label: 11.1
title: Approximation of a Matrix by a Low-Rank Matrix
pagenum: 415; label: 11.1.1
title: The Benefits of Low-Rank Matrices
pagenum: 415; label: 11.1.2
title: Matrix Norm
pagenum: 416; label: 11.2
title: The Trolley-Line-Location Problem
pagenum: 416; label: 11.2.1
title: Solution to the Trolley-Line-Location Problem
pagenum: 417; label: 11.2.2
title: Rank-One Approximation to a Matrix
pagenum: 420; label: 11.2.3
title: The Best Rank-One Approximation
pagenum: 420; label: 11.2.4
title: An Expression for the Best Rank-One Approximation
pagenum: 421; label: 11.2.5
title: The Closest One-Dimensional Affine Space
pagenum: 422; label: 11.3
title: Closest Dimension-k Vector Space
pagenum: 423; label: 11.3.1
title: A Gedanken Algorithm to Find the Singular Values and Vectors
pagenum: 423; label: 11.3.2
title: Properties of the Singular Values and Right Singular Vectors
pagenum: 424; label: 11.3.3
title: The Singular Value Decomposition
pagenum: 425; label: 11.3.4
title: Using Right Singular Vectors to Find the Closest k-Dimensional Space
pagenum: 427; label: 11.3.5
title: Best Rank-k Approximation to A
pagenum: 429; label: 11.3.6
title: Matrix Form for Best Rank-k Approximation
pagenum: 430; label: 11.3.7
title: Number of Nonzero Singular Values Is Rank A
pagenum: 430; label: 11.3.8
title: Numerical Rank
pagenum: 431; label: 11.3.9
title: Closest k-Dimensional Affine Space
pagenum: 431; label: 11.3.10
title: Proof That U Is Column-Orthogonal
pagenum: 432; label: 11.4
title: Using the Singular Value Decomposition
pagenum: 433; label: 11.4.1
title: Using SVD to Do Least Squares
pagenum: 434; label: 11.5
title: PCA
pagenum: 434; label: 11.6
title: Lab: Eigenfaces
pagenum: 435; label: 11.7
title: Review Questions
pagenum: 437; label: 11.8
title: Problems
pagenum: 437; label: 12
title: The Eigenvector
pagenum: 441; label: 12.1
title: Modeling Discrete Dynamic Processes
pagenum: 441; label: 12.1.1
title: Two Interest-Bearing Accounts
pagenum: 441; label: 12.1.2
title: Fibonacci Numbers
pagenum: 442; label: 12.2
title: Diagonalization of the Fibonacci Matrix
pagenum: 444; label: 12.3
title: Eigenvalues and Eigenvectors
pagenum: 445; label: 12.3.1
title: Similarity and Diagonalizability
pagenum: 446; label: 12.4
title: Coordinate Representation in Terms of Eigenvectors
pagenum: 448; label: 12.5
title: The Internet Worm
pagenum: 449; label: 12.6
title: Existence of Eigenvalues
pagenum: 450; label: 12.6.1
title: Positive-Definite Matrices
pagenum: 450; label: 12.6.2
title: Matrices with Distinct Eigenvalues
pagenum: 451; label: 12.6.3
title: Symmetric Matrices
pagenum: 452; label: 12.6.4
title: Upper-Triangular Matrices
pagenum: 452; label: 12.6.5
title: General Square Matrices
pagenum: 453; label: 12.7
title: Power Method
pagenum: 454; label: 12.8
title: Markov Chains
pagenum: 454; label: 12.8.1
title: Modeling Population Movement
pagenum: 454; label: 12.8.2
title: Modeling Randy
pagenum: 455; label: 12.8.3
title: Markov Chain Definitions
pagenum: 456; label: 12.8.4
title: Modeling Spatial Locality in Memory Fetches
pagenum: 456; label: 12.8.5
title: Modeling Documents: Hamlet in Wonderland
pagenum: 457; label: 12.8.6
title: Modeling Lots of Other Stuff
pagenum: 458; label: 12.8.7
title: Stationary Distributions of Markov Chains
pagenum: 458; label: 12.8.8
title: Sufficient Condition for Existence of a Stationary Distribution
pagenum: 458; label: 12.9
title: Modeling a Web Surfer: PageRank
pagenum: 459; label: 12.10
title: *The Determinant
pagenum: 459; label: 12.10.1
title: Areas of Parallelograms
pagenum: 459; label: 12.10.2
title: Volumes of Parallelepipeds
pagenum: 461; label: 12.10.3
title: Expressing the Area of a Polygon in Terms of Areas of Parallelograms
pagenum: 462; label: 12.10.4
title: The Determinant
pagenum: 463; label: 12.10.5
title: *Characterizing Eigenvalues via the Determinant Function
pagenum: 465; label: 12.11
title: *Proofs of Some Eigentheorems
pagenum: 466; label: 12.11.1
title: Existence of Eigenvalues
pagenum: 466; label: 12.11.2
title: Diagonalization of Symmetric Matrices
pagenum: 467; label: 12.11.3
title: Triangularization
pagenum: 469; label: 12.12
title: Lab: PageRank
pagenum: 471; label: 12.12.1
title: Concepts
pagenum: 471; label: 12.12.2
title: Working with a Big Dataset
pagenum: 473; label: 12.12.3
title: Implementing PageRank Using the Power Method
pagenum: 473; label: 12.12.4
title: The Dataset
pagenum: 475; label: 12.12.5
title: Handling Queries
pagenum: 475; label: 12.12.6
title: Biasing the PageRank
pagenum: 476; label: 12.12.7
title: Optional: Handling Multiword Queries
pagenum: 476; label: 12.13
title: Review Questions
pagenum: 476; label: 12.14
title: Problems
pagenum: 477; label: 13
title: The Linear Program
pagenum: 481; label: 13.1
title: The Diet Problem
pagenum: 481; label: 13.2
title: Formulating the Diet Problem as a Linear Program
pagenum: 481; label: 13.3
title: The Origins of Linear Programming
pagenum: 482; label: 13.3.1
title: Terminology
pagenum: 483; label: 13.3.2
title: Linear Programming in Different Forms
pagenum: 484; label: 13.3.3
title: Integer Linear Programming
pagenum: 484; label: 13.4
title: Geometry of Linear Programming: Polyhedra and Vertices
pagenum: 484; label: 13.5
title: There Is an Optimal Solution That Is a Vertex of the Polyhedron
pagenum: 487; label: 13.6
title: An Enumerative Algorithm for Linear Programming
pagenum: 488; label: 13.7
title: Introduction to Linear-Programming Duality
pagenum: 488; label: 13.8
title: The Simplex Algorithm
pagenum: 490; label: 13.8.1
title: Termination
pagenum: 490; label: 13.8.2
title: Representing the Current Solution
pagenum: 491; label: 13.8.3
title: A Pivot Step
pagenum: 491; label: 13.8.4
title: Simple Example
pagenum: 493; label: 13.9
title: Finding a Vertex
pagenum: 495; label: 13.10
title: Game Theory
pagenum: 497; label: 13.11
title: Formulation as a Linear Program
pagenum: 499; label: 13.12
title: Nonzero-Sum Games
pagenum: 500; label: 13.13
title: Lab: Learning through Linear Programming
pagenum: 500; label: 13.13.1
title: Reading in the Training Data
pagenum: 501; label: 13.13.2
title: Setting up the Linear Program
pagenum: 501; label: 13.13.3
title: Main Constraints
pagenum: 502; label: 13.13.4
title: Nonnegativity Constraints
pagenum: 503; label: 13.13.5
title: The Matrix A
pagenum: 503; label: 13.13.6
title: The Right-Hand Side Vector b
pagenum: 503; label: 13.13.7
title: The Objective Function Vector c
pagenum: 503; label: 13.13.8
title: Putting It Together
pagenum: 503; label: 13.13.9
title: Finding a Vertex
pagenum: 503; label: 13.13.10
title: Solving the Linear Program
pagenum: 504; label: 13.13.11
title: Using the Result
pagenum: 504; label: 13.14
title: Compressed Sensing
pagenum: 504; label: 13.14.1
title: More Quickly Acquiring an MRI Image
pagenum: 504; label: 13.14.2
title: Computation to the Rescue
pagenum: 505; label: 13.14.3
title: Onwards
pagenum: 506; label: 13.15
title: Review Questions
pagenum: 506; label: 13.16
title: Problems
pagenum: 506