ZoomNotes for Linear Algebra

Part 3: Vector Spaces and Subspaces, Basis and Dimension

3.1 Vector Spaces and Four Fundamental Subspaces

A vector space is a set of vectors closed under addition and scalar multiplication (i.e., all linear combinations stay in the set).

Subspaces of $\mathbb{R}^n$:

• Any plane through the origin
• Any line through the origin
• The zero vector alone $\{0\}$
• The entire space $\mathbb{R}^n$ itself

The Four Fundamental Subspaces of an $m \times n$ matrix $A$:

1. Column Space $C(A) \subseteq \mathbb{R}^m$: all combinations of columns of $A$
2. Row Space $C(A^T) \subseteq \mathbb{R}^n$: all combinations of rows of $A$
3. Nullspace $N(A) \subseteq \mathbb{R}^n$: all solutions to $Ax = 0$
4. Left Nullspace $N(A^T) \subseteq \mathbb{R}^m$: all solutions to $A^T y = 0$

---

3.2 Basis and Dimension of a Vector Space $S$

A basis for a vector space $S$ is a set of vectors that:

• Spans $S$ (every vector in $S$ is a linear combination of the basis vectors)
• Is linearly independent (no basis vector is a combination of the others)

Key Property: Every vector in $S$ can be written as a unique linear combination of the basis vectors.

Dimension = the number of vectors in any basis for $S$. All bases for a given space have the same number of vectors.

Examples of dimensions:

• $\mathbb{R}^n$ has dimension $n$ (standard basis: $e_1, \dots, e_n$)
• A plane through the origin in $\mathbb{R}^3$ has dimension 2
• A line through the origin in $\mathbb{R}^3$ has dimension 1
• The zero vector space has dimension 0

---

3.3 Column Space and Row Space: Bases by Elimination

Reduced Row Echelon Form (rref): After elimination, the matrix can be reduced further to:

$$R_0 = \begin{bmatrix} I_r & F \\ 0 & 0 \end{bmatrix}$$

(possibly with rows permuted). $I_r$ is the $r \times r$ identity, $F$ is an $r \times (n-r)$ matrix, and there are $m-r$ zero rows.

Basis for Column Space: The $r$ pivot columns of the original matrix $A$ (not the rref) form a basis for $C(A)$.

Basis for Row Space: The $r$ nonzero rows of $R_0$ (the rref) form a basis for the row space $C(A^T)$.

These bases are crucial because they give us the dimensions: $\dim C(A) = \dim C(A^T) = r$.

---

3.4 $Ax = 0$ and $Ax = b$ : $x_{\text{nullspace}}$ and $x_{\text{particular}}$

Solving $Ax = 0$ (Nullspace):

1. Reduce $A$ to rref $R_0 = [I_r \; F]$
2. The special solutions form a basis for $N(A)$:

$$\text{Nullspace basis vectors} = \begin{bmatrix} -F \\ I_{n-r} \end{bmatrix}$$

There are $n-r$ special solutions, one for each free variable.

Solving $Ax = b$ (Complete Solution):

1. Check consistency: elimination must yield $0 = 0$ for the system to have a solution. This means $b$ must be in $C(A)$.
2. Find one particular solution $x_p$ (set free variables to 0 and solve for pivot variables).
3. The complete solution is:

$$x = x_p + x_n$$

where $x_n$ is any vector in $N(A)$. The complete solution is a particular solution plus the entire nullspace.

---

3.5 Four Fundamental Subspaces: $C(A), C(A^T), N(A), N(A^T)$

Fundamental Theorem of Linear Algebra (Part 1):

$$\begin{aligned} \dim C(A) &= r \\ \dim C(A^T) &= r \\ \dim N(A) &= n - r \\ \dim N(A^T) &= m - r \end{aligned}$$

Counting Theorem: For an $m \times n$ matrix:

• There are at least $n-m$ solutions to $Ax = 0$ (when $n > m$)
• If $n > m$ (tall matrix), there is always a nonzero vector in the nullspace

Example: $3 \times 5$ matrix with rank 2:

• $\dim C(A) = 2$
• $\dim N(A) = 5 - 2 = 3$
• $\dim C(A^T) = 2$
• $\dim N(A^T) = 3 - 2 = 1$

---

3.6 Graphs, Incidence Matrices, and Kirchhoff's Laws

A graph consists of nodes (vertices) and edges connecting them. The incidence matrix $A$ has:

• Rows = edges
• Columns = nodes
• Entry $A_{ij} = \begin{cases} -1 & \text{if edge } i \text{ leaves node } j \\ +1 & \text{if edge } i \text{ enters node } j \\ 0 & \text{otherwise} \end{cases}$

Example: For a triangle graph with 3 nodes and 3 edges:

$$A = \begin{bmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{bmatrix}$$

Kirchhoff's Laws:

• Current Law: $A^T y = 0$ (currents entering each node sum to zero)
• Voltage Law: $Ax = 0$ around loops (voltage drops around a closed loop sum to zero)

Trees and Loops:

• A tree is a graph with no loops (cycles). For a tree with $n$ nodes, there are $n-1$ edges and the incidence matrix has full column rank $n-1$.
• Adding edges creates loops: each new edge adds exactly one independent loop.
• A spanning tree uses $r$ independent rows, where $r = n-1$ for a connected graph.

---

3.7 Every Matrix $A$ Has a Pseudoinverse $A^+$

The pseudoinverse (Moore-Penrose inverse) $A^+$ exists for every matrix $A$, even when $A$ is not square or not full rank.

Key Properties:

• $A^+ A$ = projection onto the row space of $A$
• $A A^+$ = projection onto the column space of $A$
• $A^+$ satisfies the four Moore-Penrose conditions:
  1. $A A^+ A = A$
  2. $A^+ A A^+ = A^+$
  3. $(A A^+)^T = A A^+$
  4. $(A^+ A)^T = A^+ A$

Computation via CR factorization: If $A = CR$, then:

$$A^+ = R^+ C^+$$

Computation via SVD: If $A = U \Sigma V^T$, then:

$$A^+ = V \Sigma^+ U^T$$

where $\Sigma^+$ is the diagonal matrix with reciprocals of the nonzero singular values. This is the most numerically reliable method.

When $A$ is invertible: $A^+ = A^{-1}$. The pseudoinverse generalizes the inverse to all matrices.