Linear Algebra

This guide covers the essential linear algebra concepts needed for machine learning, including vectors, matrices, matrix calculus, and their applications.

Basics

Vector: $\mathbf{x} = [x_1, x_2, ..., x_n]^T$

Matrix: $\mathbf{A} \in \mathbb{R}^{m \times n}$

$$\mathbf{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}$$

Transpose: $(\mathbf{A}^T)_{ij} = \mathbf{A}_{ji}$

Matrix Multiplication: $\mathbf{C} = \mathbf{AB}$ where $C_{ij} = \sum_k A_{ik}B_{kj}$ Identity Matrix: $\mathbf{I}_n$ where $I_{ij} = 1$ if $i=j$, else $0$ Inverse: $\mathbf{A}^{-1}\mathbf{A} = \mathbf{AA}^{-1} = \mathbf{I}$

Solving Matrix Equations: For $\mathbf{A}\mathbf{x} = \mathbf{b}$ where $\mathbf{A}$ is invertible:

$$\mathbf{x} = \mathbf{A}^{-1}\mathbf{b}$$

This is used to isolate variables in matrix equations (e.g., in normal equations for linear regression).

Properties:

• $(\mathbf{AB})^T = \mathbf{B}^T\mathbf{A}^T$
• $(\mathbf{A}^T)^T = \mathbf{A}$
• $(\mathbf{A} + \mathbf{B})^T = \mathbf{A}^T + \mathbf{B}^T$
• $(\mathbf{AB})^{-1} = \mathbf{B}^{-1}\mathbf{A}^{-1}$
• $(\mathbf{A}^T)^{-1} = (\mathbf{A}^{-1})^T$

Block Matrix Multiplication: When matrices are partitioned into blocks, multiplication follows the same rules:

For $\mathbf{A} = [\mathbf{A}_1 \; \mathbf{A}_2]$ (horizontal partition) and $\mathbf{B} = \begin{bmatrix} \mathbf{B}_1 \\ \mathbf{B}_2 \end{bmatrix}$ (vertical partition):

$$\mathbf{AB} = [\mathbf{A}_1 \; \mathbf{A}_2] \begin{bmatrix} \mathbf{B}_1 \\ \mathbf{B}_2 \end{bmatrix} = \mathbf{A}_1\mathbf{B}_1 + \mathbf{A}_2\mathbf{B}_2$$

For partitioned matrices $\begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix}$ and $\begin{bmatrix} \mathbf{B}_{11} & \mathbf{B}_{12} \\ \mathbf{B}_{21} & \mathbf{B}_{22} \end{bmatrix}$:

$$\begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix} \begin{bmatrix} \mathbf{B}_{11} & \mathbf{B}_{12} \\ \mathbf{B}_{21} & \mathbf{B}_{22} \end{bmatrix} = \begin{bmatrix} \mathbf{A}_{11}\mathbf{B}_{11} + \mathbf{A}_{12}\mathbf{B}_{21} & \mathbf{A}_{11}\mathbf{B}_{12} + \mathbf{A}_{12}\mathbf{B}_{22} \\ \mathbf{A}_{21}\mathbf{B}_{11} + \mathbf{A}_{22}\mathbf{B}_{21} & \mathbf{A}_{21}\mathbf{B}_{12} + \mathbf{A}_{22}\mathbf{B}_{22} \end{bmatrix}$$

Key Pattern: Block multiplication works like regular matrix multiplication, treating blocks as scalars.

Trace and Determinant

Trace: Sum of diagonal elements

$$\text{tr}(\mathbf{A}) = \sum_{i=1}^n A_{ii}$$

Properties:

• $\text{tr}(\mathbf{A} + \mathbf{B}) = \text{tr}(\mathbf{A}) + \text{tr}(\mathbf{B})$
• $\text{tr}(\mathbf{AB}) = \text{tr}(\mathbf{BA})$
• $\text{tr}(\mathbf{A}^T) = \text{tr}(\mathbf{A})$

Determinant: $\det(\mathbf{A})$ or $|\mathbf{A}|$

For 2×2 matrix:

$$\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = ad - bc$$

Eigenvalues and Eigenvectors

For a square matrix $\mathbf{A}$:

$$\mathbf{Av} = \lambda \mathbf{v}$$

where $\lambda$ is the eigenvalue and $\mathbf{v}$ is the eigenvector.

Diagonalizable Matrix: A matrix $\mathbf{A}$ is diagonalizable if it can be written as:

$$\mathbf{A} = \mathbf{PDP}^{-1}$$

where:

• $\mathbf{D}$ is a diagonal matrix containing the eigenvalues of $\mathbf{A}$
• $\mathbf{P}$ is an invertible matrix whose columns are the eigenvectors of $\mathbf{A}$ (corresponding to the eigenvalues in $\mathbf{D}$)

Conditions for Diagonalizability:

• $\mathbf{A}$ has $n$ linearly independent eigenvectors (where $n$ is the dimension of $\mathbf{A}$)
• If $\mathbf{A}$ is symmetric, it is always diagonalizable (Spectral Theorem)

Properties:

• $\det(\mathbf{A}) = \prod_i \lambda_i$
• $\text{tr}(\mathbf{A}) = \sum_i \lambda_i$

Norms

Norm — A norm is a function $N : V \longrightarrow [0, +\infty[$ where $V$ is a vector space, and such that for all $\boldsymbol{x}, \boldsymbol{y} \in V$, we have:

• $N(\boldsymbol{x} + \boldsymbol{y}) \leq N(\boldsymbol{x}) + N(\boldsymbol{y})$ (Triangle inequality)
• $N(a\boldsymbol{x}) = |a|N(\boldsymbol{x})$ for $a$ scalar (Absolute homogeneity)
• If $N(\boldsymbol{x}) = 0$, then $\boldsymbol{x} = \boldsymbol{0}$ (Positive definiteness)

For $\boldsymbol{x} \in V$, the most commonly used norms are:

Norm	Notation	Definition	Use case
Manhattan, $L^1$	$\| \boldsymbol{x} \|_1$	$\displaystyle\sum_{i=1}^{n} \|x_i\|$	LASSO regularization
Euclidean, $L^2$	$\| \boldsymbol{x} \|_2$	$\displaystyle\sqrt{\sum_{i=1}^{n} x_i^2}$	Ridge regularization
$p$-norm, $L^p$	$\| \boldsymbol{x} \|_p$	$\displaystyle\left(\sum_{i=1}^{n} x_i^p\right)^{\frac{1}{p}}$	Hölder inequality
Infinity, $L^\infty$	$\| \boldsymbol{x} \|_\infty$	$\displaystyle\max_i \|x_i\|$	Uniform convergence

Matrix Calculus

Matrix-Vector Product Derivatives:

$$\frac{\partial \mathbf{Ax}}{\partial \mathbf{A}} = \mathbf{x}^T$$

$$\frac{\partial \mathbf{Ax}}{\partial \mathbf{x}} = \mathbf{A}$$

Matrix Product Derivatives:

$$\frac{\partial \mathbf{AB}}{\partial \mathbf{A}} = \mathbf{B}^T$$

$$\frac{\partial \mathbf{AB}}{\partial \mathbf{B}} = \mathbf{A}^T$$

Chain of Matrix-Vector Products:

For $\mathbf{Y} = \mathbf{EXw}$ where $\mathbf{E}$ and $\mathbf{X}$ are matrices and $\mathbf{w}$ is a vector:

$$\frac{\partial (\mathbf{EXw})}{\partial \mathbf{w}} = \mathbf{EX}$$

$$\frac{\partial (\mathbf{EXw})}{\partial \mathbf{X}} = \mathbf{E}^T$$

$$\frac{\partial (\mathbf{EXw})}{\partial \mathbf{E}} = (\mathbf{Xw})^T$$

Dot Product Derivatives:

For $z = \mathbf{y}^T\mathbf{x}$:

$$\frac{\partial z}{\partial \mathbf{x}} = \mathbf{y}, \quad \frac{\partial z}{\partial \mathbf{y}} = \mathbf{x}$$

Quadratic Form (very important!):

For $f(\mathbf{x}) = \mathbf{x}^T\mathbf{Ax}$:

$$\frac{\partial (\mathbf{x}^T\mathbf{Ax})}{\partial \mathbf{x}} = (\mathbf{A} + \mathbf{A}^T)\mathbf{x}$$

If $\mathbf{A}$ is symmetric:

$$\frac{\partial (\mathbf{x}^T\mathbf{Ax})}{\partial \mathbf{x}} = 2\mathbf{Ax}$$

Linear Form:

$$\frac{\partial (\mathbf{a}^T\mathbf{x})}{\partial \mathbf{x}} = \mathbf{a}$$

$$\frac{\partial (\mathbf{x}^T\mathbf{a})}{\partial \mathbf{x}} = \mathbf{a}$$

Function Linearity in Parameters:

A function $f(\theta)$ is linear in $\theta$ if it can be written as a dot product $\mathbf{a}^{\top}\theta$ (or $\theta^{\top}\mathbf{a}$), where $\mathbf{a}$ is a vector of constants or input features that do not depend on $\theta$.

Example: Consider the model:

$$y = \theta^{\top}\left(\frac{\mathbf{x}}{||\mathbf{x}||_{2}}\right)$$

The term $\left(\frac{\mathbf{x}}{||\mathbf{x}||_{2}}\right)$ is a transformed feature vector (let's call it $\mathbf{x}'$) that does not depend on $\theta$. Thus, $y = \theta^{\top}\mathbf{x}'$ is a linear function of $\theta$, even though it involves normalization of the input features.

info

Spherical Codes: When $||\mathbf{x}||_2 = 1$, the feature vector lies on the unit sphere (unit circle in 2D, unit sphere in 3D, etc.). This normalization is common in machine learning because:

• It removes scale dependence between features
• The dot product $\theta^{\top}\mathbf{x}$ directly relates to the angle between $\theta$ and $\mathbf{x}$: $\theta^{\top}\mathbf{x} = ||\theta||_2 \cos(\angle(\theta, \mathbf{x}))$
• It simplifies optimization and makes models more robust to feature scaling

Key Point: A function can be linear in the parameters $\theta$ even if it involves non-linear transformations of the input features $\mathbf{x}$, as long as those transformations do not depend on $\theta$.

Norm Squared:

$$\frac{\partial (\mathbf{x}^T\mathbf{x})}{\partial \mathbf{x}} = 2\mathbf{x}$$

$$\frac{\partial \|\mathbf{x}\|^2}{\partial \mathbf{x}} = 2\mathbf{x}$$

Hessian Matrix:

For a scalar function $f: \mathbb{R}^n \to \mathbb{R}$, the Hessian matrix is the matrix of second-order partial derivatives:

$$\mathbf{H} = \nabla^2 f(\mathbf{x}) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$$

Or more compactly: $H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}$

Matrix Definiteness

For a symmetric matrix $\mathbf{H}$, we can classify its definiteness based on the quadratic form $\mathbf{z}^T\mathbf{H}\mathbf{z}$:

Type	Condition	Eigenvalues	Use in ML
Positive Definite (PD)	$\mathbf{z}^T\mathbf{H}\mathbf{z} > 0$ for all $\mathbf{z} \neq \mathbf{0}$	All $\lambda_i > 0$	Convex optimization (unique minimum)
Positive Semi-Definite (PSD)	$\mathbf{z}^T\mathbf{H}\mathbf{z} \geq 0$ for all $\mathbf{z}$	All $\lambda_i \geq 0$	Convex functions
Negative Definite (ND)	$\mathbf{z}^T\mathbf{H}\mathbf{z} < 0$ for all $\mathbf{z} \neq \mathbf{0}$	All $\lambda_i < 0$	Concave optimization (unique maximum)
Negative Semi-Definite (NSD)	$\mathbf{z}^T\mathbf{H}\mathbf{z} \leq 0$ for all $\mathbf{z}$	All $\lambda_i \leq 0$	Concave functions
Indefinite	Otherwise	Mixed signs	Saddle points

Connection to Convexity:

For a twice-differentiable function $f(\mathbf{x})$:

• $f$ is convex if and only if $\nabla^2 f(\mathbf{x})$ (Hessian) is PSD everywhere
• $f$ is strictly convex if and only if $\nabla^2 f(\mathbf{x})$ is PD everywhere
• $f$ is concave if and only if $\nabla^2 f(\mathbf{x})$ is NSD everywhere
• $f$ is strictly concave if and only if $\nabla^2 f(\mathbf{x})$ is ND everywhere