Unit 1: Linear Algebra Foundations for Machine Learning

Linear algebra is the foundational mathematical language of machine learning. From simple linear regression to deep multi-layer neural networks, transformers, and diffusion models, virtually every data point, weight parameter, activation map, and gradient update is expressed as a vector, matrix, or higher-order tensor. Mastering vector spaces, subspaces, matrix operations, inner products, norms, projections, and linear transformations is indispensable for understanding data representation, dimensionality reduction, loss optimization, and feature transformations.

1. Vectors, Matrices, and Tensors in Machine Learning

1.1 Vectors

In machine learning, a vector is an ordered finite collection of scalar numbers representing a single data sample, feature set, or model parameter vector.

• Mathematically, an $n$-dimensional real vector $\mathbf{x} \in \mathbb{R}^n$ is written by convention as an $n \times 1$ column vector:
  $\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$
• The transpose $\mathbf{x}^T$ turns it into a $1 \times n$ row vector:
  $\mathbf{x}^T = [x_1, x_2, \dots, x_n]$
• Feature Space Interpretation: Each component $x_i$ denotes the numeric value of feature $i$ (e.g., house area, number of bedrooms, age of structure). A dataset of $m$ samples each having $d$ features can be envisioned as $m$ vectors inhabiting $\mathbb{R}^d$.

Vector Operations

1. Vector Addition: For $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$, $\mathbf{u} + \mathbf{v} = [u_1 + v_1, u_2 + v_2, \dots, u_n + v_n]^T$.
2. Scalar Multiplication: For $c \in \mathbb{R}$, $c\mathbf{u} = [c u_1, c u_2, \dots, c u_n]^T$.
3. Dot Product (Inner Product):
   $\mathbf{u} \cdot \mathbf{v} = \mathbf{u}^T \mathbf{v} = \sum_{i=1}^n u_i v_i$
   Geometric interpretation: $\mathbf{u} \cdot \mathbf{v} = \|\mathbf{u}\|_2 \|\mathbf{v}\|_2 \cos \theta$, where $\theta$ is the angle between the two vectors. If $\mathbf{u}^T \mathbf{v} = 0$, the vectors are orthogonal.
4. Hadamard Product (Element-wise Product):
   $\mathbf{u} \odot \mathbf{v} = [u_1 v_1, u_2 v_2, \dots, u_n v_n]^T$
   Frequently used in neural network activation gating (e.g., LSTMs and GRUs).
5. Outer Product:
   For $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, the outer product produces a rank-1 matrix:
   $\mathbf{u} \mathbf{v}^T \in \mathbb{R}^{m \times n}, \quad (\mathbf{u} \mathbf{v}^T)_{ij} = u_i v_j$

1.2 Matrices

A matrix $A \in \mathbb{R}^{m \times n}$ is a rectangular 2D array of scalars with $m$ rows and $n$ columns:
$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}$

• Design Matrix ($X \in \mathbb{R}^{N \times d}$): In supervised and unsupervised learning, tabular datasets are typically organized into a design matrix where row $i$ represents sample $\mathbf{x}_i^T$ and column $j$ corresponds to feature $j$.
• Weight Matrix ($W \in \mathbb{R}^{d_{out} \times d_{in}}$): In linear layers and neural networks, linear mappings $\mathbf{y} = W\mathbf{x} + \mathbf{b}$ map inputs of dimension $d_{in}$ to dimension $d_{out}$.
• Matrix Multiplication: For $A \in \mathbb{R}^{m \times k}$ and $B \in \mathbb{R}^{k \times n}$, the product $C = AB \in \mathbb{R}^{m \times n}$ is given by:
  $C_{ij} = \sum_{p=1}^k A_{ip} B_{pj}$
  Properties: Associative ($A(BC) = (AB)C$), Distributive ($A(B+C) = AB + AC$), but generally non-commutative ($AB \neq BA$).
• Transpose Properties: $(AB)^T = B^T A^T$, $(A + B)^T = A^T + B^T$, $(A^{-1})^T = (A^T)^{-1}$.

1.3 Tensors

A tensor is a multidimensional array that generalizes scalars (order-0 tensors), vectors (order-1 tensors), and matrices (order-2 tensors) to arbitrary dimensions (orders / ranks / modes):

• Order-0: Scalar $s \in \mathbb{R}$ (e.g., loss value, learning rate).
• Order-1: Vector $\mathbf{x} \in \mathbb{R}^d$ (e.g., word embedding, feature vector).
• Order-2: Matrix $M \in \mathbb{R}^{m \times n}$ (e.g., grayscale image $H \times W$, tabular batch).
• Order-3: Tensor $\mathcal{T} \in \mathbb{R}^{C \times H \times W}$ (e.g., color RGB image with 3 color channels, or sequence batch in NLP $[B, T, D]$).
• Order-4: Tensor $\mathcal{X} \in \mathbb{R}^{B \times C \times H \times W}$ (e.g., batch of mini-batch images in convolutional networks, or video frame clip $[B, T, H, W]$).

CODECopy Code
   Scalar (0D)        Vector (1D)          Matrix (2D)            Tensor (3D / 4D)
      [ 5 ]          [ 1, 2, 3 ]        [ [1, 2], [3, 4] ]       Batch of images
                                                              [B, C, H, W]

2. Vector Spaces and Subspaces

2.1 Vector Spaces

A vector space $(V, +, \cdot)$ over a scalar field $\mathbb{R}$ is a set of elements (vectors) endowed with two operations: vector addition ($+: V \times V \to V$) and scalar multiplication ($\cdot: \mathbb{R} \times V \to V$) satisfying the following eight axioms for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ and $\alpha, \beta \in \mathbb{R}$:

1. Associativity of Addition: $\mathbf{u} + (\mathbf{v} + \mathbf{w}) = (\mathbf{u} + \mathbf{v}) + \mathbf{w}$
2. Commutativity of Addition: $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$
3. Additive Identity: There exists $\mathbf{0} \in V$ such that $\mathbf{u} + \mathbf{0} = \mathbf{u}$.
4. Additive Inverse: For every $\mathbf{u} \in V$, there exists $-\mathbf{u} \in V$ such that $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$.
5. Compatibility of Scalar Multiplication: $\alpha(\beta \mathbf{u}) = (\alpha \beta)\mathbf{u}$
6. Scalar Multiplicative Identity: $1 \cdot \mathbf{u} = \mathbf{u}$
7. Distributivity over Vector Addition: $\alpha(\mathbf{u} + \mathbf{v}) = \alpha \mathbf{u} + \alpha \mathbf{v}$
8. Distributivity over Scalar Addition: $(\alpha + \beta)\mathbf{u} = \alpha \mathbf{u} + \beta \mathbf{u}$

2.2 Linear Independence, Span, and Basis

• Linear Combination: Given a set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\} \subset V$, a linear combination is:
  $\mathbf{w} = \sum_{i=1}^k c_i \mathbf{v}_i, \quad c_i \in \mathbb{R}$
• Linear Span: The set of all possible linear combinations of $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$:
  $\text{span}(\mathbf{v}_1, \dots, \mathbf{v}_k) = \left\{ \sum_{i=1}^k c_i \mathbf{v}_i \;\middle|\; c_i \in \mathbb{R} \right\}$
• Linear Independence: A set of vectors $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is linearly independent if and only if the vector equation:
  $c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \dots + c_k \mathbf{v}_k = \mathbf{0}$
  holds only when $c_1 = c_2 = \dots = c_k = 0$. If non-zero coefficients exist satisfying the equation, the vectors are linearly dependent (i.e., at least one vector can be expressed as a linear combination of the others).
• Basis: A subset $\mathcal{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ of a vector space $V$ is a basis if:
  1. $\mathcal{B}$ is linearly independent.
  2. $\text{span}(\mathcal{B}) = V$.
     Every vector $\mathbf{v} \in V$ has a unique representation in terms of basis $\mathcal{B}$.
• Dimension: The number of vectors in any basis of $V$ is called the dimension of $V$, denoted $\dim(V)$. For $\mathbb{R}^n$, $\dim(\mathbb{R}^n) = n$.
• Standard Basis: In $\mathbb{R}^n$, the standard canonical basis is $\{\mathbf{e}_1, \dots, \mathbf{e}_n\}$ where $\mathbf{e}_i$ has 1 at index $i$ and 0 elsewhere.

2.3 Subspaces and Fundamental Subspaces of a Matrix

A subset $S \subseteq V$ is a subspace of $V$ if and only if:

1. $\mathbf{0} \in S$ (contains the zero vector).
2. For all $\mathbf{u}, \mathbf{v} \in S$, $\mathbf{u} + \mathbf{v} \in S$ (closed under addition).
3. For all $c \in \mathbb{R}$ and $\mathbf{u} \in S$, $c\mathbf{u} \in S$ (closed under scalar multiplication).

For any matrix $A \in \mathbb{R}^{m \times n}$, there are four fundamental subspaces:

1. Column Space (Range) $\mathcal{C}(A) \subseteq \mathbb{R}^m$:
   $\mathcal{C}(A) = \{ A\mathbf{x} \mid \mathbf{x} \in \mathbb{R}^n \} = \text{span}(\text{columns of } A)$
   Its dimension is the column rank of $A$. In linear regression $\hat{\mathbf{y}} = X\mathbf{w}$, the model predictions $\hat{\mathbf{y}}$ must lie within the column space of $X$.
2. Null Space (Kernel) $\mathcal{N}(A) \subseteq \mathbb{R}^n$:
   $\mathcal{N}(A) = \{ \mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} = \mathbf{0} \}$
   Its dimension is the nullity of $A$.
3. Row Space $\mathcal{C}(A^T) \subseteq \mathbb{R}^n$:
   $\mathcal{C}(A^T) = \{ A^T \mathbf{y} \mid \mathbf{y} \in \mathbb{R}^m \} = \text{span}(\text{rows of } A)$
   Row rank equals column rank, known simply as the rank of $A$, denoted $\text{rank}(A)$.
4. Left Null Space $\mathcal{N}(A^T) \subseteq \mathbb{R}^m$:
   $\mathcal{N}(A^T) = \{ \mathbf{y} \in \mathbb{R}^m \mid A^T \mathbf{y} = \mathbf{0} \}$

The Rank-Nullity Theorem (Fundamental Theorem of Linear Algebra)

For any matrix $A \in \mathbb{R}^{m \times n}$:
$\text{rank}(A) + \text{nullity}(A) = n$
Furthermore, $\mathcal{C}(A^T) \perp \mathcal{N}(A)$ in $\mathbb{R}^n$ (they are orthogonal complements: $\mathbb{R}^n = \mathcal{C}(A^T) \oplus \mathcal{N}(A)$), and $\mathcal{C}(A) \perp \mathcal{N}(A^T)$ in $\mathbb{R}^m$.

3. Norms and Projections

3.1 Vector Norms

A norm on a vector space $V$ is a function $\|\cdot\|: V \to \mathbb{R}_{\ge 0}$ that assigns a non-negative length or magnitude to each vector, satisfying three core axioms:

1. Non-negativity & Definiteness: $\|\mathbf{x}\| \ge 0$, and $\|\mathbf{x}\| = 0 \iff \mathbf{x} = \mathbf{0}$.
2. Absolute Homogeneity: $\|c\mathbf{x}\| = |c| \|\mathbf{x}\|$ for all $c \in \mathbb{R}, \mathbf{x} \in V$.
3. Triangle Inequality: $\|\mathbf{x} + \mathbf{y}\| \le \|\mathbf{x}\| + \|\mathbf{y}\|$.

Common Vector Norms in ML

3.2 Matrix Norms

• Frobenius Norm: Measures the overall magnitude of matrix entries, analogous to the Euclidean norm of vectorized matrix:
  $\|A\|_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n A_{ij}^2} = \sqrt{\text{Tr}(A^T A)}$
• Spectral Norm (Induced 2-Norm):
  $\|A\|_2 = \max_{\mathbf{x} \neq \mathbf{0}} \frac{\|A\mathbf{x}\|_2}{\|\mathbf{x}\|_2} = \sigma_{\max}(A)$
  where $\sigma_{\max}(A)$ is the largest singular value of $A$. Critical in spectral normalization for GAN stability.

3.3 Orthogonality and Projections

Two vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ are orthogonal ($\mathbf{u} \perp \mathbf{v}$) if their inner product is zero:
$\mathbf{u}^T \mathbf{v} = 0$
If in addition $\|\mathbf{u}\|_2 = \|\mathbf{v}\|_2 = 1$, they are orthonormal.

Projection of a Vector onto Another Vector

The orthogonal projection of vector $\mathbf{y}$ onto a non-zero vector $\mathbf{x}$ is:
$\text{proj}_{\mathbf{x}}(\mathbf{y}) = \frac{\mathbf{x}^T \mathbf{y}}{\mathbf{x}^T \mathbf{x}} \mathbf{x} = \frac{\mathbf{x}^T \mathbf{y}}{\|\mathbf{x}\|_2^2} \mathbf{x}$
The residual vector $\mathbf{e} = \mathbf{y} - \text{proj}_{\mathbf{x}}(\mathbf{y})$ is orthogonal to $\mathbf{x}$: $\mathbf{x}^T \mathbf{e} = 0$.

Projection onto a Subspace and Linear Regression

Let $S = \mathcal{C}(A)$ be the subspace spanned by the linearly independent columns of $A \in \mathbb{R}^{m \times d}$ ($m > d$).
To project an arbitrary target vector $\mathbf{y} \in \mathbb{R}^m$ orthogonally onto $\mathcal{C}(A)$, we seek $\hat{\mathbf{y}} = A\hat{\mathbf{w}} \in \mathcal{C}(A)$ minimizing $\|\mathbf{y} - \hat{\mathbf{y}}\|_2^2$.
The orthogonality condition requires the error residual $\mathbf{e} = \mathbf{y} - A\hat{\mathbf{w}}$ to be orthogonal to every column of $A$:
$A^T (\mathbf{y} - A\hat{\mathbf{w}}) = \mathbf{0} \implies A^T A \hat{\mathbf{w}} = A^T \mathbf{y}$
This is the celebrated Normal Equation of Ordinary Least Squares (OLS) regression!
When $A$ has full column rank, $A^T A$ is invertible:
$\hat{\mathbf{w}} = (A^T A)^{-1} A^T \mathbf{y}$
The projection $\hat{\mathbf{y}}$ is given by:
$\hat{\mathbf{y}} = A\hat{\mathbf{w}} = A(A^T A)^{-1} A^T \mathbf{y} = P \mathbf{y}$
where $P = A(A^T A)^{-1} A^T$ is the orthogonal projection matrix (Hat Matrix $H$).
Properties of a projection matrix $P$:

1. Idempotence: $P^2 = P$ (projecting twice gives the exact same result).
2. Symmetry: $P^T = P$ (for orthogonal projections).
3. Eigenvalues: All eigenvalues of an orthogonal projection matrix are either 0 or 1.

4. Linear Operators and Transformations in ML

4.1 Linear Transformations

A mapping $T: V \to W$ between two vector spaces is a linear transformation (or linear map) if and only if it preserves vector addition and scalar multiplication:

1. $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$ for all $\mathbf{u}, \mathbf{v} \in V$.
2. $T(c\mathbf{u}) = c T(\mathbf{u})$ for all $c \in \mathbb{R}, \mathbf{u} \in V$.
   Together: $T(\alpha \mathbf{u} + \beta \mathbf{v}) = \alpha T(\mathbf{u}) + \beta T(\mathbf{v})$.

4.2 Matrix Representation of Linear Transformations

Every linear transformation $T: \mathbb{R}^n \to \mathbb{R}^m$ can be represented uniquely as multiplication by an $m \times n$ matrix $A$:
$T(\mathbf{x}) = A\mathbf{x}$
The $j$-th column of $A$ is simply the transformation of the $j$-th standard basis vector:
$A_{:, j} = T(\mathbf{e}_j)$

Geometric Interpretations of Elementary Transformations in $\mathbb{R}^2$

• Rotation by angle $\theta$:
  $R(\theta) = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}, \quad \det(R) = 1$
• Scaling by factors $s_x, s_y$:
  $S = \begin{bmatrix} s_x & 0 \\ 0 & s_y \end{bmatrix}, \quad \det(S) = s_x s_y$
• Shearing along $x$-axis:
  $\begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}, \quad \det = 1$
• Reflection across $x$-axis:
  $\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}, \quad \det = -1$

4.3 Change of Basis

Suppose we have a vector $\mathbf{x}$ expressed in the standard basis. If we introduce a new basis $\mathcal{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$, we form the change-of-basis matrix $P = [\mathbf{b}_1 \dots \mathbf{b}_n]$.

• Coordinate transformation: $\mathbf{x} = P [\mathbf{x}]_{\mathcal{B}} \implies [\mathbf{x}]_{\mathcal{B}} = P^{-1} \mathbf{x}$.
• Transformation representation in new basis: If a linear transformation is given by matrix $A$ in standard coordinates, its matrix representation in basis $\mathcal{B}$ is:
  $[T]_{\mathcal{B}} = P^{-1} A P$
  Matrices $A$ and $B = P^{-1} A P$ are said to be similar matrices. They share identical eigenvalues, trace, and determinant.

4.4 Affine Transformations vs Linear Transformations

A linear transformation must always map the origin to the origin: $T(\mathbf{0}) = \mathbf{0}$.
In deep learning layers:
$\mathbf{y} = W\mathbf{x} + \mathbf{b}$
Because of the bias vector $\mathbf{b} \neq \mathbf{0}$, this map does not preserve the origin ($T(\mathbf{0}) = \mathbf{b} \neq \mathbf{0}$). It is therefore not strictly linear, but an affine transformation (a linear transformation followed by a translation).
Using homogeneous coordinates, an affine transformation can be represented as a linear transformation in $\mathbb{R}^{n+1}$:
$\begin{bmatrix} \mathbf{y} \\ 1 \end{bmatrix} = \begin{bmatrix} W & \mathbf{b} \\ \mathbf{0}^T & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ 1 \end{bmatrix}$

5. Comparative Summary & Formula Cheatsheet

6. Common Pitfalls and Exam Traps

1. Confusing Linearity with Affine mappings: In machine learning, $f(\mathbf{x}) = W\mathbf{x} + \mathbf{b}$ is colloquially called a "linear layer", but mathematically it is strictly an affine transformation unless the bias $\mathbf{b} = \mathbf{0}$.
2. Order of Matrix Multiplication: $AB \neq BA$. Furthermore, $(AB)^T = B^T A^T$ and $(AB)^{-1} = B^{-1} A^{-1}$ (order reverses!).
3. Idempotence Property: Remember that any projection matrix satisfies $P^2 = P$. Consequently, $P^k = P$ for all positive integers $k$.
4. Rank of Outer Product: The outer product of two non-zero vectors $\mathbf{u} \mathbf{v}^T$ always produces a matrix of rank exactly 1, regardless of the dimensions of $\mathbf{u}$ and $\mathbf{v}$.
5. Invertibility of $A^T A$: $A^T A$ is invertible if and only if the columns of $A$ are linearly independent (i.e., $A$ has full column rank). If features are multicollinear, $A^T A$ becomes singular.