ZoomNotes for Linear Algebra

Part 1: Basic Ideas of Linear Algebra

1.1 Linear Combinations of Vectors

A vector in $\mathbb{R}^n$ is an ordered list of $n$ real numbers, written as a column:

$$v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}$$

A linear combination of vectors $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k$ is formed by multiplying each vector by a scalar and adding the results:

$$c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_k \mathbf{v}_k$$

Key insight: Every linear combination of vectors stays within the same space $\mathbb{R}^n$. The set of all possible linear combinations of a collection of vectors is called their span.

Example in $\mathbb{R}^2$: The vectors $\mathbf{v}_1 = [1,0]^T$ and $\mathbf{v}_2 = [0,1]^T$ span all of $\mathbb{R}^2$ because any vector $[x,y]^T$ can be written as $x\mathbf{v}_1 + y\mathbf{v}_2$.

---

1.2 Dot Products $v \cdot w$ and Lengths $\|v\|$ and Angles $\theta$

The dot product (also called inner product or scalar product) of two vectors in $\mathbb{R}^n$ is:

$$\mathbf{v} \cdot \mathbf{w} = \sum_{i=1}^n v_i w_i = v^T w$$

Length (norm) of a vector:

$$\|\mathbf{v}\| = \sqrt{\mathbf{v} \cdot \mathbf{v}} = \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2}$$

This is the Euclidean distance from the origin to the point $(v_1, \dots, v_n)$, by Pythagoras in $n$ dimensions.

Angle between two vectors:

$$\cos \theta = \frac{\mathbf{v} \cdot \mathbf{w}}{\|\mathbf{v}\| \, \|\mathbf{w}\|}$$

Schwarz Inequality (Cauchy-Schwarz):

$$|\mathbf{v} \cdot \mathbf{w}| \leq \|\mathbf{v}\| \, \|\mathbf{w}\|$$

Equality holds when $\mathbf{v}$ and $\mathbf{w}$ are parallel (one is a scalar multiple of the other).

Perpendicular (Orthogonal) Vectors: $\mathbf{v} \perp \mathbf{w}$ iff $\mathbf{v} \cdot \mathbf{w} = 0$. For perpendicular vectors, the Pythagorean theorem gives:

$$\|\mathbf{v} + \mathbf{w}\|^2 = \|\mathbf{v}\|^2 + \|\mathbf{w}\|^2$$

Unit vectors have length $1$. To normalize any nonzero vector, divide by its length: $\hat{\mathbf{v}} = \mathbf{v} / \|\mathbf{v}\|$.

---

1.3 Matrices Multiplying Vectors

A matrix $A$ of size $m \times n$ multiplies a vector $x \in \mathbb{R}^n$ to produce $Ax \in \mathbb{R}^m$.

Two ways to view $Ax = b$:

Row way (dot product): Each row of $A$ takes the dot product with $x$ to produce one component of $b$:

$$b_i = \sum_{j=1}^n A_{ij} x_j \quad \text{(row $i$ dot $x$)}$$

Column way (linear combination): $Ax$ is a linear combination of the columns of $A$, with coefficients from $x$:

$$Ax = x_1 \text{col}_1(A) + x_2 \text{col}_2(A) + \cdots + x_n \text{col}_n(A)$$

The Identity Matrix: $Ix = x$ for all $x$. $I$ has 1's on the diagonal and 0's elsewhere.

Example:

$$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = x_1 \begin{bmatrix} 1 \\ 3 \end{bmatrix} + x_2 \begin{bmatrix} 2 \\ 4 \end{bmatrix}$$

The column way is fundamental: it tells us that $Ax$ always lies in the column space of $A$.

---

1.4 Column Space and Row Space of $A$

Column Space $C(A)$: The set of all linear combinations of the columns of $A$. Equivalently, $C(A) = \{Ax : x \in \mathbb{R}^n\}$.

• $C(A)$ is a subspace of $\mathbb{R}^m$ (each column has $m$ components).
• The column space contains all possible outputs $b$ for which $Ax = b$ has a solution.
• The rank $r$ is the dimension of $C(A)$, i.e., the number of independent columns.

Row Space $C(A^T)$: The set of all linear combinations of the rows of $A$. Equivalently, the column space of $A^T$.

• The row space is a subspace of $\mathbb{R}^n$ (each row has $n$ components).
• The dimension of the row space also equals $r$ (the rank).

Key Fact: The column space and row space have the same dimension $r$, even though they live in different ambient spaces ($\mathbb{R}^m$ vs $\mathbb{R}^n$).

---

1.5 Dependent and Independent Columns

A set of vectors $\mathbf{v}_1, \dots, \mathbf{v}_n$ is linearly dependent if one vector can be written as a combination of the others. Equivalently, there exist scalars $c_1, \dots, c_n$, not all zero, such that:

$$c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n = 0$$

A set is linearly independent if the only solution to the above equation is $c_1 = c_2 = \cdots = c_n = 0$.

For columns of a matrix $A$:

• Dependent columns: $Ax = 0$ for some nonzero $x$. At least one free variable exists.
• Independent columns: $Ax = 0$ only when $x = 0$. Every variable is a pivot variable.

For square matrices: If columns are independent, then rows are also independent (and vice versa). The matrix is invertible.

Rank $r$ = number of independent columns = number of independent rows = dimension of $C(A)$ = dimension of $C(A^T)$.

---

1.6 Matrix-Matrix Multiplication $AB$

There are four equivalent ways to multiply matrices $A$ (size $m \times n$) and $B$ (size $n \times p$) to get $C = AB$ (size $m \times p$):

1. Dot products of rows of $A$ with columns of $B$:

$$C_{ij} = (\text{row } i \text{ of } A) \cdot (\text{column } j \text{ of } B) = \sum_{k=1}^n A_{ik} B_{kj}$$

2. $A$ times columns of $B$: Each column of $C$ is $A$ times the corresponding column of $B$:

$$C = A \begin{bmatrix} \mathbf{b}_1 & \mathbf{b}_2 & \cdots & \mathbf{b}_p \end{bmatrix} = \begin{bmatrix} A\mathbf{b}_1 & A\mathbf{b}_2 & \cdots & A\mathbf{b}_p \end{bmatrix}$$

3. Rows of $A$ times $B$: Each row of $C$ is the corresponding row of $A$ times $B$.

4. Column times row (outer product):

$$AB = \sum_{k=1}^n (\text{column } k \text{ of } A)(\text{row } k \text{ of } B)$$

Each term is an $m \times p$ rank-one matrix.

Associative Law: $(AB)C = A(BC)$, which is the foundation for efficient computation (parenthesize to minimize operations).

Block Multiplication: If matrices are partitioned into blocks, multiplication follows the same row-column pattern at the block level:

$$\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} = \begin{bmatrix} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\ A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22} \end{bmatrix}$$

---

1.7 Factoring $A$ into $CR$: Column rank $r$ = Row rank

$CR$ Factorization: Every $m \times n$ matrix $A$ of rank $r$ can be factored as:

$$A = C R$$

• $C$ is $m \times r$: the $r$ independent columns of $A$
• $R$ is $r \times n$: the combination coefficients that express every column of $A$ in terms of the independent columns in $C$

The First Great Theorem: Column Rank = Row Rank

The $CR$ factorization makes this obvious: $C$ has $r$ columns (column rank $r$), $R$ has $r$ rows (row rank $r$), and since $A = CR$, both ranks must equal $r$.

Construction:

1. Pick the first $r$ independent columns of $A$ to form $C$.
2. Solve $A = CR$: each column of $A$ is expressed as the same linear combination of columns of $C$. Those coefficients go into $R$.

Example: If $A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix}$, the rank is 1. $C = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$, $R = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix}$.

---

1.8 Rank One Matrices $A =$ (1 column) $\times$ (1 row)

A rank one matrix has the form:

$$A = \mathbf{u} \mathbf{v}^T = \begin{bmatrix} u_1 \\ u_2 \\ \vdots \\ u_m \end{bmatrix} \begin{bmatrix} v_1 & v_2 & \cdots & v_n \end{bmatrix}$$

Every row is a multiple of $\mathbf{v}^T$, and every column is a multiple of $\mathbf{u}$. The matrix has only one independent row and one independent column.

Building block property: Every rank $r$ matrix can be written as the sum of $r$ rank one matrices:

$$A = \sum_{i=1}^r \mathbf{u}_i \mathbf{v}_i^T$$

This is the outer-product view of matrix multiplication.

The Five Great Factorizations of Linear Algebra:

Factorization	Description
$A = CR$	Independent columns $\times$ row coefficients
$A = LU$	Lower triangular $\times$ Upper triangular (elimination)
$A = QR$	Orthogonal $\times$ Upper triangular (Gram-Schmidt)
$S = Q\Lambda Q^T$	Symmetric $S$ diagonalized by orthogonal eigenvectors
$A = U\Sigma V^T$	Singular Value Decomposition (any matrix)

These five factorizations are the backbone of computational linear algebra.