# CSE 1205 Linear Algebra — Complete Summary

---

## Lecture 1: Linear Systems, Echelon Forms, Row Reduction

### Key Concepts
- **Linear equation**: $a_1x_1 + a_2x_2 + \ldots + a_nx_n = b$ (no products/powers of variables)
- **System of linear equations**: collection of linear equations in the same variables
- **Solution set**: set of all solutions; systems are **consistent** ($\geq 1$ solution) or **inconsistent** (no solution)
- **Equivalent systems**: systems with the same solution set
- **Augmented matrix** $[A \mid b]$: matrix representation of a system
- **Elementary row operations** (preserve solution set):
  - **Replacement**: $R_i \leftarrow R_i + kR_j$
  - **Interchange**: $R_i \leftrightarrow R_j$
  - **Scaling**: $R_i \leftarrow cR_i$ ($c \neq 0$)
- **Row Echelon Form (REF)**:
  1. All zero rows at the bottom
  2. Each leading entry is to the right of the leading entry above
  3. All entries below a leading entry are zero
- **Reduced Row Echelon Form (RREF)** — additional requirements:
  4. Leading entries are all 1 (leading 1s)
  5. Each leading 1 is the only nonzero entry in its column
- **Pivot position**: location of a leading 1 in RREF
- **Pivot column**: column containing a pivot position
- **Basic variables**: correspond to pivot columns; **free variables**: all others

### Existence and Uniqueness Theorem
- **Consistent** $\iff$ RREF of $[A|b]$ has no row $[0\ 0\ \ldots\ 0 \mid d]$ with $d \neq 0$
- **Unique solution** $\iff$ consistent with no free variables
- **Infinitely many solutions** $\iff$ consistent with $\geq 1$ free variable

### Method: Solving a Linear System
1. Write the augmented matrix $[A \mid b]$
2. Row reduce to REF (or RREF)
3. Check consistency (no row $[0 \ldots 0 \mid \text{nonzero}]$)
4. If consistent, continue to RREF
5. Express basic variables in terms of free variables
6. Write solution in parametric form

---

## Lecture 2: Vectors, Linear Combinations, Spans, Matrix-Vector Products

### Key Concepts
- **Vectors in $\mathbb{R}^n$**: column matrices with $n$ entries
- **Linear combination**: $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \ldots + c_p\mathbf{v}_p$ ($c_i$ are scalar weights)
- **$\text{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}$**: set of all linear combinations of $\mathbf{v}_1, \ldots, \mathbf{v}_p$
- **Matrix-vector product** $A\mathbf{x}$: if $A = [\mathbf{a}_1\ \mathbf{a}_2\ \ldots\ \mathbf{a}_n]$ and $\mathbf{x} = (x_1, \ldots, x_n)^T$, then $A\mathbf{x} = x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \ldots + x_n\mathbf{a}_n$
- $A\mathbf{x} = \mathbf{b}$ is consistent $\iff$ $\mathbf{b}$ is a linear combination of the columns of $A$ $\iff$ $\mathbf{b} \in \text{Span}\{\text{columns of } A\}$

### Equivalent Statements (for $m \times n$ matrix $A$)
The following are equivalent:
1. $A\mathbf{x} = \mathbf{b}$ is consistent for every $\mathbf{b}$ in $\mathbb{R}^m$
2. Every $\mathbf{b}$ in $\mathbb{R}^m$ is a linear combination of columns of $A$
3. $\text{Span}\{\text{columns of } A\} = \mathbb{R}^m$
4. $A$ has a pivot in every row

### Method: Is $\mathbf{b}$ in $\text{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}$?
1. Form $[\mathbf{v}_1\ \mathbf{v}_2\ \ldots\ \mathbf{v}_p \mid \mathbf{b}]$
2. Row reduce
3. If consistent $\to$ yes, $\mathbf{b}$ is in the span

### Method: Does $\text{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\} = \mathbb{R}^m$?
- Check if the matrix $[\mathbf{v}_1 \ldots \mathbf{v}_p]$ has a pivot in every row

---

## Lecture 3: Parametric Vector Form, Homogeneous Systems, Linear Independence

### Key Concepts
- **Homogeneous system** $A\mathbf{x} = \mathbf{0}$: always consistent ($\mathbf{x} = \mathbf{0}$ is the trivial solution)
- **Nontrivial solution**: a nonzero solution to $A\mathbf{x} = \mathbf{0}$
- $A\mathbf{x} = \mathbf{0}$ has nontrivial solutions $\iff$ there are free variables $\iff$ more columns than pivots
- **Parametric vector form**: $\mathbf{x} = \mathbf{p} + t_1\mathbf{v}_1 + t_2\mathbf{v}_2 + \ldots$ ($\mathbf{p}$ = particular solution, $\mathbf{v}_i$ from free variables)
- For $A\mathbf{x} = \mathbf{b}$: solution set $= \{\mathbf{p} + \mathbf{v}_h : \mathbf{v}_h \text{ solves } A\mathbf{x} = \mathbf{0}\}$ (translate of the homogeneous solution set)
- **Linearly independent**: $c_1\mathbf{v}_1 + \ldots + c_p\mathbf{v}_p = \mathbf{0}$ only has the trivial solution (all $c_i = 0$)
- **Linearly dependent**: there exist weights, not all zero, such that $c_1\mathbf{v}_1 + \ldots + c_p\mathbf{v}_p = \mathbf{0}$

### Key Facts About Linear Independence
- One vector $\{\mathbf{v}\}$: independent $\iff$ $\mathbf{v} \neq \mathbf{0}$
- Two vectors $\{\mathbf{v}_1, \mathbf{v}_2\}$: dependent $\iff$ one is a scalar multiple of the other
- If $p > n$ (more vectors than entries): always dependent (in $\mathbb{R}^n$)
- If the set contains the zero vector: always dependent
- Columns of $A$ are linearly independent $\iff$ $A\mathbf{x} = \mathbf{0}$ has only the trivial solution $\iff$ every column is a pivot column

### Method: Check Linear Independence
1. Form matrix $A = [\mathbf{v}_1\ \mathbf{v}_2\ \ldots\ \mathbf{v}_p]$
2. Row reduce $A\mathbf{x} = \mathbf{0}$
3. If only trivial solution (no free variables) $\to$ independent
4. If free variables exist $\to$ dependent

### Method: Write Solution in Parametric Vector Form
1. Solve the system (RREF)
2. Express each basic variable in terms of free variables
3. Write $\mathbf{x}$ as a vector with free variables as parameters
4. Factor out the free variable parameters: $\mathbf{x} = \mathbf{p} + t_1\mathbf{v}_1 + t_2\mathbf{v}_2 + \ldots$

---

## Lecture 4: Matrix/Linear Transformations

### Key Concepts
- **Transformation** $T: \mathbb{R}^n \to \mathbb{R}^m$: maps each $\mathbf{x}$ in $\mathbb{R}^n$ to $T(\mathbf{x})$ in $\mathbb{R}^m$
- **Matrix transformation**: $T(\mathbf{x}) = A\mathbf{x}$ for some $m \times n$ matrix $A$
- **Linear transformation**: $T(c\mathbf{u} + d\mathbf{v}) = cT(\mathbf{u}) + dT(\mathbf{v})$ for all scalars $c, d$ and vectors $\mathbf{u}, \mathbf{v}$
  - Equivalently: $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$ and $T(c\mathbf{u}) = cT(\mathbf{u})$
  - Also implies: $T(\mathbf{0}) = \mathbf{0}$
- Every matrix transformation is a linear transformation
- **Standard matrix**: $A = [T(\mathbf{e}_1)\ T(\mathbf{e}_2)\ \ldots\ T(\mathbf{e}_n)]$ where $\mathbf{e}_i$ are standard basis vectors

### Onto and One-to-One
- **Onto** (surjective): every $\mathbf{b}$ in $\mathbb{R}^m$ has at least one $\mathbf{x}$ with $T(\mathbf{x}) = \mathbf{b}$ $\iff$ columns of $A$ span $\mathbb{R}^m$ $\iff$ pivot in every row
- **One-to-one** (injective): $T(\mathbf{x}) = \mathbf{b}$ has at most one solution for every $\mathbf{b}$ $\iff$ columns of $A$ are linearly independent $\iff$ pivot in every column $\iff$ $A\mathbf{x} = \mathbf{0}$ has only trivial solution

### Standard Geometric Transformations in $\mathbb{R}^2$
| Transformation | Standard Matrix |
|---|---|
| Reflection through $x_1$-axis | $\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$ |
| Reflection through $x_2$-axis | $\begin{bmatrix} -1 & 0 \\ 0 & 1 \end{bmatrix}$ |
| Reflection through $x_1 = x_2$ | $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ |
| Reflection through origin | $\begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}$ |
| Rotation by angle $\varphi$ | $\begin{bmatrix} \cos\varphi & -\sin\varphi \\ \sin\varphi & \cos\varphi \end{bmatrix}$ |
| Horizontal scaling by $k$ | $\begin{bmatrix} k & 0 \\ 0 & 1 \end{bmatrix}$ |
| Vertical scaling by $k$ | $\begin{bmatrix} 1 & 0 \\ 0 & k \end{bmatrix}$ |
| Horizontal shear by $k$ | $\begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}$ |
| Vertical shear by $k$ | $\begin{bmatrix} 1 & 0 \\ k & 1 \end{bmatrix}$ |
| Projection onto $x_1$-axis | $\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$ |
| Projection onto $x_2$-axis | $\begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}$ |

### Method: Find the Standard Matrix
1. Determine $T(\mathbf{e}_1), T(\mathbf{e}_2), \ldots, T(\mathbf{e}_n)$
2. $A = [T(\mathbf{e}_1)\ T(\mathbf{e}_2)\ \ldots\ T(\mathbf{e}_n)]$

### Method: Composition of Transformations
- If $T_1$ has matrix $A_1$ and $T_2$ has matrix $A_2$, then $T_2 \circ T_1$ has matrix $A_2 A_1$ (apply right-to-left)

---

## Lecture 5: Matrix Operations

### Key Concepts
- **Matrix addition**: $A + B$ (same dimensions, entry-wise)
- **Scalar multiplication**: $cA$ (multiply every entry by $c$)
- **Matrix multiplication**: $AB$ — entry $(i,j)$ of $AB$ = row $i$ of $A$ $\cdot$ column $j$ of $B$
  - $A$ is $m \times n$, $B$ is $n \times p$ $\to$ $AB$ is $m \times p$
  - Number of columns of $A$ must equal number of rows of $B$
- **Transpose**: $(A^T)_{ij} = A_{ji}$ (flip rows and columns)
- **Powers**: $A^0 = I$, $A^k = A \cdot A \cdots A$ ($k$ times); $A$ must be square

### Properties of Matrix Multiplication
- $A(BC) = (AB)C$ (associative)
- $A(B + C) = AB + AC$ (left distributive)
- $(B + C)A = BA + CA$ (right distributive)
- $c(AB) = (cA)B = A(cB)$ (scalar)
- $IA = AI = A$ (identity)
- $(AB)^T = B^T A^T$ (transpose reverses order)

### WARNING — Things That Do NOT Hold
- $AB \neq BA$ in general (not commutative)
- $AB = AC$ does NOT imply $B = C$ (no cancellation law)
- $AB = 0$ does NOT imply $A = 0$ or $B = 0$
- $(AB)^T \neq A^T B^T$ — the order reverses: $(AB)^T = B^T A^T$

### Method: Multiply Matrices
- **Row-column rule**: $(AB)_{ij} = \sum_k a_{ik} b_{kj}$
- **Column view**: column $j$ of $AB$ = $A \cdot$ (column $j$ of $B$)
- **Row view**: row $i$ of $AB$ = (row $i$ of $A$) $\cdot B$

---

## Lecture 6: Inverse Matrices

### Key Concepts
- $A$ is **invertible** if there exists $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$
- Only square matrices can be invertible
- $A^{-1}$ is unique (if it exists)
- If $A$ is invertible, then $A\mathbf{x} = \mathbf{b}$ has the unique solution $\mathbf{x} = A^{-1}\mathbf{b}$

### Properties of Inverses
- $(A^{-1})^{-1} = A$
- $(AB)^{-1} = B^{-1}A^{-1}$ (order reverses!)
- $(A^T)^{-1} = (A^{-1})^T$
- $(cA)^{-1} = \frac{1}{c}A^{-1}$

### Two-by-Two Inverse Formula
If $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$ and $ad - bc \neq 0$:
$$A^{-1} = \frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$$

### The Invertible Matrix Theorem (IMT)
For an $n \times n$ matrix $A$, the following are **all equivalent**:
1. $A$ is invertible
2. $A$ is row equivalent to $I_n$
3. $A$ has $n$ pivot positions
4. $A\mathbf{x} = \mathbf{0}$ has only the trivial solution
5. Columns of $A$ are linearly independent
6. $A\mathbf{x} = \mathbf{b}$ is consistent for every $\mathbf{b}$ in $\mathbb{R}^n$
7. Columns of $A$ span $\mathbb{R}^n$
8. There exists $C$ with $CA = I$
9. There exists $D$ with $AD = I$
10. $A^T$ is invertible
11. $\det(A) \neq 0$ *(added in Lecture 10)*
12. $\text{Col } A = \mathbb{R}^n$ *(added in Lecture 9)*
13. $\dim \text{Col } A = n$ *(added in Lecture 9)*
14. $\text{rank } A = n$ *(added in Lecture 9)*
15. $\text{Nul } A = \{\mathbf{0}\}$ *(added in Lecture 9)*
16. $\dim \text{Nul } A = 0$ *(added in Lecture 9)*
17. Eigenvalues are all nonzero *(added in Lecture 11)*

### Method: Find $A^{-1}$ (General Algorithm)
1. Form $[A \mid I]$
2. Row reduce to $[I \mid A^{-1}]$
3. If $A$ cannot be reduced to $I$, then $A$ is not invertible

---

## Lecture 8: Subspaces, Null Space, Column Space, Basis

### Key Concepts
- **Subspace** $H$ of $\mathbb{R}^n$: a subset that
  1. Contains the zero vector ($\mathbf{0} \in H$)
  2. Is closed under addition ($\mathbf{u}, \mathbf{v} \in H \implies \mathbf{u} + \mathbf{v} \in H$)
  3. Is closed under scalar multiplication ($\mathbf{u} \in H, c \text{ scalar} \implies c\mathbf{u} \in H$)
- **Column space** $\text{Col } A = \text{Span}\{\text{columns of } A\} = \{\mathbf{b} : A\mathbf{x} = \mathbf{b} \text{ is consistent}\}$ — subspace of $\mathbb{R}^m$
- **Null space** $\text{Nul } A = \{\mathbf{x} : A\mathbf{x} = \mathbf{0}\}$ — subspace of $\mathbb{R}^n$
- **Basis**: a set of vectors that is linearly independent AND spans the subspace

### Method: Find a Basis for $\text{Nul } A$
1. Solve $A\mathbf{x} = \mathbf{0}$ (row reduce $[A \mid \mathbf{0}]$)
2. Write solution in parametric vector form: $\mathbf{x} = t_1\mathbf{v}_1 + t_2\mathbf{v}_2 + \ldots$
3. The vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots\}$ form a basis for $\text{Nul } A$

### Method: Find a Basis for $\text{Col } A$
1. Row reduce $A$ to echelon form
2. Identify the **pivot columns**
3. The **corresponding columns of the ORIGINAL matrix $A$** form a basis for $\text{Col } A$
   - WARNING: Use original columns, NOT the echelon form columns!

### Method: Find a Basis for $\text{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}$
1. Form $A = [\mathbf{v}_1 \ldots \mathbf{v}_p]$ and row reduce
2. Take the original vectors corresponding to pivot columns

---

## Lecture 9: Coordinate Vectors, Dimension, Rank

### Key Concepts
- **Coordinate vector** $[\mathbf{x}]_\mathcal{B}$: if $\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}$ is a basis and $\mathbf{x} = c_1\mathbf{b}_1 + \ldots + c_n\mathbf{b}_n$, then $[\mathbf{x}]_\mathcal{B} = (c_1, \ldots, c_n)$
- **Dimension** of subspace $H$: $\dim H =$ number of vectors in any basis of $H$
  - $\dim \mathbb{R}^n = n$
  - $\dim\{\mathbf{0}\} = 0$
- **Rank** of $A$: $\text{rank } A = \dim \text{Col } A =$ number of pivot columns
- **Nullity** of $A$: $\text{nullity } A = \dim \text{Nul } A =$ number of free variables

### The Rank Theorem
For $m \times n$ matrix $A$:
$$\text{rank } A + \dim \text{Nul } A = n \quad \text{(number of columns)}$$

Equivalently: (# pivot columns) + (# free variables) = $n$

### The Basis Theorem
If $\dim H = p$, then:
- Any linearly independent set of exactly $p$ vectors in $H$ is a basis
- Any spanning set of exactly $p$ vectors in $H$ is a basis

### Method: Find Coordinates $[\mathbf{x}]_\mathcal{B}$
1. Form $[\mathbf{b}_1\ \mathbf{b}_2\ \ldots\ \mathbf{b}_n \mid \mathbf{x}]$
2. Row reduce to $[I \mid \mathbf{c}]$
3. $[\mathbf{x}]_\mathcal{B} = \mathbf{c}$

---

## Lecture 10: Determinants

### Key Concepts
- **Determinant** $\det(A)$: defined for square matrices
- **$2 \times 2$**: $\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = ad - bc$
- **Cofactor expansion** along row $i$: $\det A = a_{i1}C_{i1} + a_{i2}C_{i2} + \ldots + a_{in}C_{in}$
  - **Cofactor** $C_{ij} = (-1)^{i+j} \det(A_{ij})$, where $A_{ij}$ is the submatrix with row $i$ and column $j$ deleted
  - Can expand along any row or column (choose one with the most zeros)
- **Checkerboard sign pattern**: $\begin{bmatrix} + & - & + \\ - & + & - \\ + & - & + \end{bmatrix}$

### Effects of Row Operations on Determinants
| Row operation | Effect on $\det$ |
|---|---|
| Replacement: $R_i \leftarrow R_i + kR_j$ | $\det$ unchanged |
| Interchange: $R_i \leftrightarrow R_j$ | $\det$ changes sign |
| Scaling: $R_i \leftarrow cR_i$ | $\det$ multiplied by $c$ |

### Properties of Determinants
- $A$ is invertible $\iff$ $\det(A) \neq 0$
- $\det(AB) = \det(A) \cdot \det(B)$
- $\det(A^T) = \det(A)$
- $\det(A^{-1}) = 1/\det(A)$
- $\det(cA) = c^n \det(A)$ for $n \times n$ matrix
- **Triangular matrix**: $\det =$ product of diagonal entries
- If $A$ has a zero row or zero column: $\det(A) = 0$
- If two rows (or columns) are equal: $\det(A) = 0$

### Method: Compute Determinant Efficiently
1. **Small matrices**: use the formula directly ($2 \times 2$) or cofactor expansion ($3 \times 3$)
2. **Larger matrices**: row reduce to triangular form, tracking sign changes and scaling
3. **Expand along a row/column** with many zeros to minimize computation

---

## Lecture 11: Eigenvalues and Eigenvectors

### Key Concepts
- **Eigenvalue** $\lambda$: scalar such that $A\mathbf{x} = \lambda\mathbf{x}$ for some nonzero $\mathbf{x}$
- **Eigenvector** $\mathbf{x}$: nonzero vector such that $A\mathbf{x} = \lambda\mathbf{x}$
- **Eigenspace** for $\lambda$: $\text{Nul}(A - \lambda I) = \{\mathbf{x} : A\mathbf{x} = \lambda\mathbf{x}\}$ (includes zero vector)
- **Characteristic equation**: $\det(A - \lambda I) = 0$
- **Characteristic polynomial**: $\det(A - \lambda I)$ as polynomial in $\lambda$ (degree $n$ for $n \times n$ matrix)
- $\lambda = 0$ is an eigenvalue $\iff$ $A$ is not invertible ($\det A = 0$)
- **Triangular matrix**: eigenvalues are the diagonal entries
- Eigenvectors for **distinct** eigenvalues are linearly independent

### Algebraic vs. Geometric Multiplicity
- **Algebraic multiplicity (a.m.)**: multiplicity of $\lambda$ as root of characteristic polynomial
- **Geometric multiplicity (g.m.)**: $\dim \text{Nul}(A - \lambda I) =$ dimension of eigenspace
- Always: $1 \leq \text{g.m.} \leq \text{a.m.}$

### Method: Find Eigenvalues and Eigenvectors
1. **Find eigenvalues**: solve $\det(A - \lambda I) = 0$
2. **Find eigenvectors**: for each eigenvalue $\lambda$, solve $(A - \lambda I)\mathbf{x} = \mathbf{0}$
3. Write eigenvectors in parametric form $\to$ basis for eigenspace

### Method: $2 \times 2$ Eigenvalues Shortcut
For $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$:
- Characteristic equation: $\lambda^2 - (a+d)\lambda + (ad - bc) = 0$
- $\lambda^2 - \text{tr}(A)\lambda + \det(A) = 0$

---

## Lecture 12: Diagonalization

### Key Concepts
- $A$ is **diagonalizable** if $A = PDP^{-1}$ where $D$ is diagonal
  - $P = [\mathbf{v}_1\ \mathbf{v}_2\ \ldots\ \mathbf{v}_n]$ (eigenvectors as columns)
  - $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ (corresponding eigenvalues on diagonal)
  - The order of eigenvectors in $P$ must match eigenvalues in $D$
- **Power formula**: $A^k = PD^kP^{-1}$ ($D^k = \text{diag}(\lambda_1^k, \ldots, \lambda_n^k)$)

### Diagonalization Theorem
An $n \times n$ matrix $A$ is diagonalizable $\iff$ $A$ has $n$ linearly independent eigenvectors

### Second Diagonalization Theorem
$A$ is diagonalizable $\iff$ for each eigenvalue, g.m. $=$ a.m.

Sufficient condition: if $A$ has $n$ distinct eigenvalues $\to$ $A$ is diagonalizable

### Method: Diagonalize a Matrix
1. Find all eigenvalues (solve $\det(A - \lambda I) = 0$)
2. For each eigenvalue, find a basis for its eigenspace
3. Check: total number of basis vectors $= n$? If yes $\to$ diagonalizable
4. $P = [\text{basis vectors as columns}]$, $D = \text{diag}(\text{corresponding eigenvalues})$
5. Verify: $AP = PD$

### Method: Compute $A^k$
1. Diagonalize: $A = PDP^{-1}$
2. $A^k = PD^kP^{-1}$
3. $D^k$ is easy: just raise each diagonal entry to the $k$th power

---

## Lecture 13: Complex Eigenvalues

### Key Concepts
- Complex eigenvalues of real matrices come in **conjugate pairs**: $\lambda = a + bi$, $\bar{\lambda} = a - bi$
- Complex eigenvectors also come in conjugate pairs
- **Fundamental Theorem of Algebra**: every degree-$n$ polynomial has exactly $n$ roots in $\mathbb{C}$ (counting multiplicity)

### Real Decomposition for $2 \times 2$ Case
If $A$ is $2 \times 2$ with eigenvalue $\lambda = a - bi$ ($b \neq 0$) and eigenvector $\mathbf{v} = \mathbf{r} + \mathbf{s}i$:
$$A = PCP^{-1}$$
where:
- $P = [\text{Re}(\mathbf{v})\ \ \text{Im}(\mathbf{v})] = [\mathbf{r}\ \ \mathbf{s}]$
- $C = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}$ (rotation-scaling matrix)
- $|\lambda| = \sqrt{a^2 + b^2}$ is the scaling factor
- $\varphi = \arctan(b/a)$ is the rotation angle

### Method: Handle Complex Eigenvalues
1. Find eigenvalues: if $\lambda = a - bi$ with $b \neq 0$
2. Find eigenvector $\mathbf{v}$ for $\lambda = a - bi$
3. Decompose: $\mathbf{v} = \text{Re}(\mathbf{v}) + i \cdot \text{Im}(\mathbf{v})$
4. $P = [\text{Re}(\mathbf{v}) \mid \text{Im}(\mathbf{v})]$
5. $C = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}$
6. $A = PCP^{-1}$

---

## Lecture 14: Discrete Dynamical Systems

### Key Concepts
- **Dynamical system**: $\mathbf{x}_{k+1} = A\mathbf{x}_k$ with initial state $\mathbf{x}_0$
- **Solution**: $\mathbf{x}_k = A^k\mathbf{x}_0$
- If $A = PDP^{-1}$: $\mathbf{x}_k = PD^kP^{-1}\mathbf{x}_0 = c_1\lambda_1^k\mathbf{v}_1 + c_2\lambda_2^k\mathbf{v}_2 + \ldots$ where $\mathbf{x}_0 = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \ldots$
- **Long-term behavior** depends on $|\lambda_i|$:
  - $|\lambda| < 1$: component decays to $0$
  - $|\lambda| > 1$: component grows without bound
  - $|\lambda| = 1$: component stays bounded

### Classification of Origin ($2 \times 2$ Real Eigenvalues)
| Condition | Classification | Behavior |
|---|---|---|
| $\|\lambda_1\|, \|\lambda_2\| < 1$ | **Attractor** | All trajectories $\to 0$ |
| $\|\lambda_1\|, \|\lambda_2\| > 1$ | **Repeller** | All trajectories $\to \infty$ |
| $\|\lambda_1\| < 1 < \|\lambda_2\|$ | **Saddle point** | Approach along $\mathbf{v}_1$, diverge along $\mathbf{v}_2$ |

### Complex Eigenvalues Case
- $\lambda = a + bi$ $\to$ trajectories spiral
- $|\lambda| = \sqrt{a^2 + b^2} < 1$: spiral inward (attractor)
- $|\lambda| = \sqrt{a^2 + b^2} > 1$: spiral outward (repeller)
- $|\lambda| = 1$: elliptical orbits

### Method: Analyze a Dynamical System
1. Find eigenvalues and eigenvectors of $A$
2. Diagonalize (or use complex decomposition)
3. Write $\mathbf{x}_0 = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \ldots$ (find coefficients from $P^{-1}\mathbf{x}_0$)
4. $\mathbf{x}_k = c_1\lambda_1^k\mathbf{v}_1 + c_2\lambda_2^k\mathbf{v}_2 + \ldots$
5. Classify origin based on $|\lambda_i|$

---

## Lecture 15: Inner Product and Orthogonality

### Key Concepts
- **Inner product** (dot product): $\mathbf{u} \cdot \mathbf{v} = \mathbf{u}^T\mathbf{v} = u_1v_1 + u_2v_2 + \ldots + u_nv_n$
- **Length/norm**: $\|\mathbf{v}\| = \sqrt{\mathbf{v} \cdot \mathbf{v}}$
- **Unit vector**: $\|\mathbf{u}\| = 1$; to normalize: $\mathbf{u} = \mathbf{v}/\|\mathbf{v}\|$
- **Distance**: $\text{dist}(\mathbf{u}, \mathbf{v}) = \|\mathbf{u} - \mathbf{v}\|$
- **Orthogonal**: $\mathbf{u} \perp \mathbf{v} \iff \mathbf{u} \cdot \mathbf{v} = 0$
- **Pythagorean theorem**: if $\mathbf{u} \perp \mathbf{v}$, then $\|\mathbf{u} + \mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2$

### Properties of Inner Product
- $\mathbf{u} \cdot \mathbf{v} = \mathbf{v} \cdot \mathbf{u}$ (commutative)
- $(\mathbf{u} + \mathbf{v}) \cdot \mathbf{w} = \mathbf{u} \cdot \mathbf{w} + \mathbf{v} \cdot \mathbf{w}$ (distributive)
- $(c\mathbf{u}) \cdot \mathbf{v} = c(\mathbf{u} \cdot \mathbf{v})$ (scalar)
- $\mathbf{u} \cdot \mathbf{u} \geq 0$, and $\mathbf{u} \cdot \mathbf{u} = 0 \iff \mathbf{u} = \mathbf{0}$

### Orthogonal Complement
- $W^\perp = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{x} \cdot \mathbf{w} = 0 \text{ for all } \mathbf{w} \in W\}$
- $W^\perp$ is always a subspace
- $(\text{Row } A)^\perp = \text{Nul } A$
- $(\text{Col } A)^\perp = \text{Nul } A^T$
- $\dim W + \dim W^\perp = n$
- $(W^\perp)^\perp = W$

### Orthogonal/Orthonormal Sets
- **Orthogonal set**: all pairs have dot product $0$
- **Orthonormal set**: orthogonal set where every vector has norm $1$
- An orthogonal set of nonzero vectors is linearly independent
- **Orthogonal basis**: basis that is an orthogonal set

### Method: Check if a Set is Orthogonal
- Verify that $\mathbf{u}_i \cdot \mathbf{u}_j = 0$ for all $i \neq j$

### Method: Find Weights in an Orthogonal Basis
If $\{\mathbf{u}_1, \ldots, \mathbf{u}_p\}$ is an orthogonal basis for $W$ and $\mathbf{y} \in W$:
$$\mathbf{y} = \frac{\mathbf{y} \cdot \mathbf{u}_1}{\mathbf{u}_1 \cdot \mathbf{u}_1}\mathbf{u}_1 + \frac{\mathbf{y} \cdot \mathbf{u}_2}{\mathbf{u}_2 \cdot \mathbf{u}_2}\mathbf{u}_2 + \cdots + \frac{\mathbf{y} \cdot \mathbf{u}_p}{\mathbf{u}_p \cdot \mathbf{u}_p}\mathbf{u}_p$$

---

## Lecture 16: Orthogonal Projections

### Key Concepts
- **Orthogonal Decomposition Theorem**: for subspace $W$ of $\mathbb{R}^n$, every $\mathbf{y} \in \mathbb{R}^n$ can be written **uniquely** as:
  $$\mathbf{y} = \hat{\mathbf{y}} + \mathbf{z}, \quad \hat{\mathbf{y}} \in W, \quad \mathbf{z} \in W^\perp$$
  where $\hat{\mathbf{y}} = \text{proj}_W(\mathbf{y})$ is the **orthogonal projection** of $\mathbf{y}$ onto $W$
- **Best Approximation Theorem**: $\text{proj}_W(\mathbf{y})$ is the closest point in $W$ to $\mathbf{y}$:
  $$\|\mathbf{y} - \hat{\mathbf{y}}\| < \|\mathbf{y} - \mathbf{v}\| \quad \text{for all } \mathbf{v} \in W, \mathbf{v} \neq \hat{\mathbf{y}}$$

### Projection Formulas
**Onto a line** ($W = \text{Span}\{\mathbf{u}\}$):
$$\text{proj}_W(\mathbf{y}) = \frac{\mathbf{y} \cdot \mathbf{u}}{\mathbf{u} \cdot \mathbf{u}} \mathbf{u}$$

**Onto a subspace with orthogonal basis** $\{\mathbf{u}_1, \ldots, \mathbf{u}_p\}$:
$$\text{proj}_W(\mathbf{y}) = \frac{\mathbf{y} \cdot \mathbf{u}_1}{\mathbf{u}_1 \cdot \mathbf{u}_1}\mathbf{u}_1 + \cdots + \frac{\mathbf{y} \cdot \mathbf{u}_p}{\mathbf{u}_p \cdot \mathbf{u}_p}\mathbf{u}_p$$

**Onto a subspace with orthonormal basis** $\{\mathbf{u}_1, \ldots, \mathbf{u}_p\}$:
$$\text{proj}_W(\mathbf{y}) = (\mathbf{y} \cdot \mathbf{u}_1)\mathbf{u}_1 + \cdots + (\mathbf{y} \cdot \mathbf{u}_p)\mathbf{u}_p$$

### Projection Matrix
If $U = [\mathbf{u}_1 \ldots \mathbf{u}_p]$ has **orthonormal** columns forming a basis for $W$:
$$P = UU^T$$
Then $\text{proj}_W(\mathbf{y}) = P\mathbf{y}$

**Properties of $P$**:
- $P^2 = P$ (idempotent)
- $P^T = P$ (symmetric)
- If $\mathbf{y} \in W$: $P\mathbf{y} = \mathbf{y}$
- If $\mathbf{y} \in W^\perp$: $P\mathbf{y} = \mathbf{0}$

### Method: Project $\mathbf{y}$ onto $W$
1. **If $W$ has an orthogonal basis** $\{\mathbf{u}_1, \ldots, \mathbf{u}_p\}$: use the projection formula directly
2. **If $W$ has a general basis**: first apply Gram-Schmidt to get an orthogonal basis, then project
3. Compute $\mathbf{z} = \mathbf{y} - \hat{\mathbf{y}}$ to find the component in $W^\perp$
4. **Verify**: check $\hat{\mathbf{y}} \cdot \mathbf{z} = 0$ (or that $\mathbf{z}$ is orthogonal to each basis vector of $W$)

---

## Lecture 18: The Gram-Schmidt Process

### Key Concepts
- Converts **any basis** $\{\mathbf{b}_1, \ldots, \mathbf{b}_p\}$ into an **orthogonal basis** $\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}$ for the same subspace
- To get an **orthonormal basis**: normalize each $\mathbf{v}_i$ to $\mathbf{u}_i = \mathbf{v}_i/\|\mathbf{v}_i\|$
- **Span preservation**: $\text{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} = \text{Span}\{\mathbf{b}_1, \ldots, \mathbf{b}_k\}$ for each $k$
- If a vector $\mathbf{b}_k$ is linearly dependent on previous ones, the process yields $\mathbf{v}_k = \mathbf{0}$ (detect and skip)

### The Gram-Schmidt Algorithm
Given linearly independent $\{\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_p\}$:
$$\mathbf{v}_1 = \mathbf{b}_1$$
$$\mathbf{v}_2 = \mathbf{b}_2 - \frac{\mathbf{b}_2 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1$$
$$\mathbf{v}_3 = \mathbf{b}_3 - \frac{\mathbf{b}_3 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1 - \frac{\mathbf{b}_3 \cdot \mathbf{v}_2}{\mathbf{v}_2 \cdot \mathbf{v}_2}\mathbf{v}_2$$
General formula:
$$\mathbf{v}_k = \mathbf{b}_k - \sum_{j=1}^{k-1} \frac{\mathbf{b}_k \cdot \mathbf{v}_j}{\mathbf{v}_j \cdot \mathbf{v}_j}\mathbf{v}_j$$

### WARNING
- The projection formula for $\text{proj}_W(\mathbf{y})$ **requires an orthogonal basis**
- Using a non-orthogonal basis gives $\hat{\mathbf{y}} \in W$ but $\mathbf{z}$ will NOT be in $W^\perp$

### Method: Gram-Schmidt Process
1. Set $\mathbf{v}_1 = \mathbf{b}_1$
2. For each subsequent $\mathbf{b}_k$: subtract projections onto all previous $\mathbf{v}_j$'s
3. Verify: check $\mathbf{v}_i \cdot \mathbf{v}_j = 0$ for all $i \neq j$
4. Optional: normalize to get orthonormal basis $\mathbf{u}_i = \mathbf{v}_i/\|\mathbf{v}_i\|$

---

## Lecture 19: Least-Squares Problems

### Key Concepts
- When $A\mathbf{x} = \mathbf{b}$ has **no solution** (inconsistent), find the **best approximate solution**
- **Least-squares solution** $\hat{\mathbf{x}}$: minimizes $\|\mathbf{b} - A\hat{\mathbf{x}}\|$ (the residual)
  $$\|\mathbf{b} - A\hat{\mathbf{x}}\| \leq \|\mathbf{b} - A\mathbf{x}\| \quad \text{for all } \mathbf{x}$$
- Geometrically: $A\hat{\mathbf{x}} = \text{proj}_{\text{Col } A}(\mathbf{b})$, so $\mathbf{b} - A\hat{\mathbf{x}} \perp \text{Col } A$

### Normal Equations
$$A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$$
- Always consistent (always has a solution)
- If columns of $A$ are **linearly independent**: $A^T A$ is invertible, unique solution:
  $$\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$$

### Least-Squares Error
$$\text{error} = \|\mathbf{b} - A\hat{\mathbf{x}}\|$$
Often easier to compute $\|\mathbf{b} - A\hat{\mathbf{x}}\|^2$ first, then take square root.

### Linear Models (Curve Fitting)
- **Linear model**: $y = \beta_0 + \beta_1 x$ (line of best fit)
- **Design matrix** $X$ and observation vector $\mathbf{y}$:
$$X = \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n \end{bmatrix}, \quad \mathbf{y} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}, \quad \boldsymbol{\beta} = \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix}$$
- Solve: $X^T X \boldsymbol{\beta} = X^T \mathbf{y}$

### General Linear Models
- $y = \beta_0 f_0(u) + \beta_1 f_1(u) + \ldots + \beta_k f_k(u)$ (linear in $\boldsymbol{\beta}$, not necessarily in $u$)
- Design matrix: $X_{ij} = f_j(u_i)$
- Can fit polynomials: $y = \beta_0 + \beta_1 x + \beta_2 x^2$ (design matrix has columns $1, x, x^2$)
- Can fit exponentials, trig functions, etc.
- **Residual** for data point $i$: $\varepsilon_i = y_i - \hat{y}_i$

### Method: Solve a Least-Squares Problem
1. Compute $A^T A$ and $A^T \mathbf{b}$
2. Solve $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$
3. If needed, compute the least-squares error $\|\mathbf{b} - A\hat{\mathbf{x}}\|$

### Method: Fit a Least-Squares Line
1. Set up design matrix $X = \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n \end{bmatrix}$ and $\mathbf{y}$
2. Compute $X^T X$ and $X^T \mathbf{y}$
3. Solve $X^T X \boldsymbol{\beta} = X^T \mathbf{y}$
4. Line: $y = \beta_0 + \beta_1 x$

---

## Lecture 20: Symmetric Matrices and Spectral Theorem

### Key Concepts
- **Symmetric matrix**: $A = A^T$
- **Orthogonal matrix**: $P$ such that $P^T P = I$ (equivalently $P^T = P^{-1}$; columns are orthonormal)
- **Orthogonally diagonalizable**: $A = PDP^T$ where $P$ is orthogonal and $D$ is diagonal

### Key Theorems
- Symmetric matrices have **only real eigenvalues** (even though the characteristic polynomial might look complex)
- Eigenvectors for **distinct eigenvalues** of a symmetric matrix are **orthogonal**
- **Spectral Theorem**: An $n \times n$ matrix $A$ is symmetric $\iff$ $A$ is orthogonally diagonalizable
  - $A$ has $n$ real eigenvalues (counting multiplicity)
  - For each eigenvalue: geometric multiplicity $=$ algebraic multiplicity
  - Eigenspaces for different eigenvalues are mutually orthogonal
  - There exists an orthonormal basis for $\mathbb{R}^n$ consisting of eigenvectors of $A$

### Spectral Decomposition
If $A = PDP^T$ with $P = [\mathbf{u}_1 \ldots \mathbf{u}_n]$ orthonormal:
$$A = \lambda_1 \mathbf{u}_1 \mathbf{u}_1^T + \lambda_2 \mathbf{u}_2 \mathbf{u}_2^T + \cdots + \lambda_n \mathbf{u}_n \mathbf{u}_n^T$$

### Method: Orthogonally Diagonalize a Symmetric Matrix
1. Find all eigenvalues of $A$ (solve $\det(A - \lambda I) = 0$)
2. For each eigenvalue, find a basis for its eigenspace
3. If an eigenspace has dimension $> 1$, apply **Gram-Schmidt** within that eigenspace to get orthogonal vectors
4. **Normalize** all eigenvectors to unit length: $\mathbf{u}_i = \mathbf{v}_i/\|\mathbf{v}_i\|$
5. Form $P = [\mathbf{u}_1\ \mathbf{u}_2\ \ldots\ \mathbf{u}_n]$ (orthonormal eigenvectors)
6. Form $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ (matching eigenvalues)
7. Verify: $A = PDP^T$ and $P^T P = I$

### Key Properties
- If $A$ is symmetric and invertible: $A^{-1}$ is also symmetric and orthogonally diagonalizable
  - $A^{-1} = PD^{-1}P^T$ (same $P$, inverse eigenvalues)
- $P^T = P^{-1}$ for orthogonal matrices, so **no need to row-reduce** to find $P^{-1}$

---

## Quick Reference: When to Use What

| Problem Type | Method |
|---|---|
| Solve $A\mathbf{x} = \mathbf{b}$ | Row reduce $[A \mid \mathbf{b}]$ to RREF |
| Is $\mathbf{b} \in \text{Span}\{\mathbf{v}_1,\ldots,\mathbf{v}_p\}$? | Row reduce $[\mathbf{v}_1 \ldots \mathbf{v}_p \mid \mathbf{b}]$, check consistency |
| Linear independence? | Row reduce, check for free variables |
| Find $A^{-1}$ | Row reduce $[A \mid I]$ to $[I \mid A^{-1}]$, or $2 \times 2$ formula |
| Basis for $\text{Nul } A$ | Solve $A\mathbf{x} = \mathbf{0}$, parametric vector form |
| Basis for $\text{Col } A$ | Row reduce $A$, take original pivot columns |
| Determinant | Cofactor expansion or row reduce to triangular |
| Eigenvalues | Solve $\det(A - \lambda I) = 0$ |
| Eigenvectors | Solve $(A - \lambda I)\mathbf{x} = \mathbf{0}$ |
| Diagonalize | Find $n$ linearly independent eigenvectors $\to P, D$ |
| Compute $A^k$ | $A = PDP^{-1}$, then $A^k = PD^kP^{-1}$ |
| Project $\mathbf{y}$ onto $W$ | Use orthogonal basis + projection formula |
| Orthogonal basis | Gram-Schmidt process |
| Least-squares $A\mathbf{x} \approx \mathbf{b}$ | Solve $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ |
| Fit a line/curve | Set up design matrix, solve normal equations |
| Orthogonal diagonalization | Eigenvalues $\to$ eigenspaces $\to$ Gram-Schmidt $\to$ normalize |