Reference · October 2016

Linear Algebra
Cheat Sheet

Laurent Lessard · University of Wisconsin–Madison

§01

Matrix Basics

A matrix is an array of numbers. $A \in \mathbb{R}^{m \times n}$ means $A$ has $m$ rows and $n$ columns:

$$A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}$$

Matrix multiplication. Two matrices can be multiplied when their inner dimensions agree:

$$C^{(m\times p)} = A^{(m\times n)}\,B^{(n\times p)}, \quad c_{ij} = \sum_{k=1}^n a_{ik}\,b_{kj}$$
Transpose

The transpose $A^T$ swaps rows and columns. If $A \in \mathbb{R}^{m\times n}$ then $A^T \in \mathbb{R}^{n\times m}$ and $(A^T)_{ij} = A_{ji}$.

Transpose properties
  • $(A^T)^T = A$
  • $(AB)^T = B^T A^T$

Vector products. If $x, y \in \mathbb{R}^n$ are column vectors:

Inner product (dot product)$x^T y \in \mathbb{R}$
Outer product$x y^T \in \mathbb{R}^{n\times n}$

Both are ordinary matrix multiplications.

Inverse

Let $A \in \mathbb{R}^{n\times n}$. If $B \in \mathbb{R}^{n\times n}$ satisfies $AB = I$ (equivalently $BA = I$), then $B$ is the inverse of $A$, written $B = A^{-1}$.

Inverse properties
  • $A^{-1}$ is unique if it exists
  • $(A^{-1})^{-1} = A$
  • $(A^{-1})^T = (A^T)^{-1}$
  • $(AB)^{-1} = B^{-1}A^{-1}$
§02

Vector Norms

A norm $\|\cdot\| : \mathbb{R}^n \to \mathbb{R}$ satisfies three axioms:

Norm axioms
  • Definiteness: $\|x\| = 0$ if and only if $x = 0$
  • Homogeneity: $\|cx\| = |c|\,\|x\|$ for all $c \in \mathbb{R}$
  • Triangle inequality: $\|x + y\| \le \|x\| + \|y\|$

Common norms on $\mathbb{R}^n$:

1-norm$\|x\|_1 = |x_1| + \cdots + |x_n|$
2-norm (Euclidean)$\|x\|_2 = \sqrt{x_1^2 + \cdots + x_n^2}$
Max-norm (∞-norm)$\|x\|_\infty = \max_{1 \le i \le n} |x_i|$
Default convention$\|x\|$ means $\|x\|_2$
$\ell^1$ ball
$\ell^2$ ball
$\ell^\infty$ ball
2-norm (Euclidean) properties
  • $x^T x = \|x\|^2$
  • Cauchy-Schwarz: $x^T y \le \|x\|\,\|y\|$
§03

Linear Independence

Definition

A set of vectors $\{x_1,\ldots,x_n\} \in \mathbb{R}^m$ is linearly independent if

$$c_1 x_1 + \cdots + c_n x_n = 0 \;\Longleftrightarrow\; c_1 = \cdots = c_n = 0$$

Equivalently, define $A = \begin{bmatrix} x_1 & \cdots & x_n \end{bmatrix} \in \mathbb{R}^{m\times n}$. The columns are linearly independent iff

$$Aw = 0 \;\Longleftrightarrow\; w = 0$$

If the vectors are linearly dependent, at least one is redundant — expressible as a linear combination of the others: $\exists\, k$ and scalars $c_i$ such that $x_k = \sum_{i \neq k} c_i x_i$.

§04

Rank of a Matrix

Definition

$\operatorname{rank}(A)$ = the maximum number of linearly independent columns (= maximum number of linearly independent rows).

For $A \in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^{n\times p}$:

Rank inequalities
  • $\operatorname{rank}(A) \le \min(m,n)$
  • $\operatorname{rank}(AB) \le \min(\operatorname{rank}(A),\operatorname{rank}(B)) \le \min(m,n,p)$
  • If $\operatorname{rank}(A) = n$ then $\operatorname{rank}(AB) = \operatorname{rank}(B)$
  • If $\operatorname{rank}(B) = n$ then $\operatorname{rank}(AB) = \operatorname{rank}(A)$

Multiplying by an invertible matrix does not alter the rank.

General properties
  • $\operatorname{rank}(A + B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$
  • $\operatorname{rank}(A) = \operatorname{rank}(A^T) = \operatorname{rank}(A^T A) = \operatorname{rank}(A A^T)$
  • $A \in \mathbb{R}^{n\times n}$ is invertible $\Longleftrightarrow$ $\operatorname{rank}(A) = n$
§05

Linear Equations

Given $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^m$, we solve $Ax = b$ for $x \in \mathbb{R}^n$. Three possibilities exist:

No solutionse.g. $x_1+x_2=1$ and $x_1+x_2=0$
Exactly onee.g. $x_1=1$ and $x_2=0$
Infinitely manye.g. $x_1+x_2=0$
Common cases
  • Overdetermined ($m > n$): typically no solution. Approach: least squares — minimize $\|Ax - b\|_2$.
  • Underdetermined ($m < n$): typically infinitely many solutions. Approach: regularization — find the solution to $Ax=b$ with minimum $\|x\|_2$.
§06

Least Squares

When $Ax = b$ is overdetermined and no exact solution exists, find $x$ that minimizes the residual:

$$\operatorname{minimize}_x \;\|Ax - b\|_2$$

This problem always has a solution (not necessarily unique).

Normal Equations

$\hat{x}$ minimizes the residual $\Longleftrightarrow$ $\hat{x}$ satisfies the normal equations:

$$A^T A\,\hat{x} = A^T b$$

The normal equations have a unique solution iff the columns of $A$ are linearly independent. In that case:

$$\hat{x} = (A^T A)^{-1} A^T b$$
§07

Range & Nullspace

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

Range $\mathcal{R}(A) = \{Ax \mid x \in \mathbb{R}^n\} \;\subseteq\; \mathbb{R}^m$
Nullspace $\mathcal{N}(A) = \{x \in \mathbb{R}^n \mid Ax = 0\} \;\subseteq\; \mathbb{R}^n$
The following are equivalent (existence of solution):
There exists a solution to $Ax = b$
$b \in \mathcal{R}(A)$
$\operatorname{rank}(A) = \operatorname{rank}(\begin{bmatrix}A & b\end{bmatrix})$
The following are equivalent (uniqueness of solution):
Solutions to $Ax = b$ are unique
$\mathcal{N}(A) = \{0\}$
$\operatorname{rank}(A) = n$
Rank–Nullity Theorem

$$\operatorname{rank}(A) + \dim(\mathcal{N}(A)) = n$$

Note: $\operatorname{rank}(A) = \dim(\mathcal{R}(A))$.

§08

Orthogonal Matrices

Definition

$U \in \mathbb{R}^{m\times n}$ is orthogonal if $U^T U = I$ (requires $m \ge n$).

Properties of orthogonal $U$, $V$
  • Columns are orthonormal: $u_i^T u_j = \delta_{ij}$
  • Preserves angles & distances: $(Ux)^T(Uz) = x^T z$ and $\|Ux\|_2 = \|x\|_2$
  • Certain matrix norms are invariant: $\|UAV^T\|_2 = \|A\|_2$ and $\|UAV^T\|_F = \|A\|_F$
  • If $U$ is square: $U^T U = UU^T = I$ and $U^{-1} = U^T$
  • $UV$ is orthogonal
Orthonormal Basis Existence

For any $A \in \mathbb{R}^{m\times n}$, there exists an orthogonal $U \in \mathbb{R}^{m\times r}$ such that $\mathcal{R}(A) = \mathcal{R}(U)$ where $r = \operatorname{rank}(A)$. One construction: Gram–Schmidt.

§09

Projections

Projection matrix

$P \in \mathbb{R}^{n\times n}$ is a projection matrix if $P^2 = P$. It maps $\mathbb{R}^n \to S$ for some subspace $S \subseteq \mathbb{R}^n$. If $P$ is a projection, so is $(I - P)$.

Any vector $x$ can be uniquely decomposed as

$$x = u + v, \quad u \in S,\; v \in S^\perp \qquad (u = Px,\; v = (I-P)x)$$
Pythagorean Theorem

$\|x\|_2^2 = \|u\|_2^2 + \|v\|_2^2$

If $A \in \mathbb{R}^{m\times n}$ has linearly independent columns, the projection onto $\mathcal{R}(A)$ is

$$P = A(A^TA)^{-1}A^T$$
Least-squares decomposition
  • $b = A(A^TA)^{-1}A^T b + (I - A(A^TA)^{-1}A^T)b = A\hat{x} + (b - A\hat{x})$
  • $\hat{x} = (A^TA)^{-1}A^Tb$ is the LS estimate
  • The optimal residual $(b - A\hat{x})$ is orthogonal to $A\hat{x}$
§10

Singular Value Decomposition

Every $A \in \mathbb{R}^{m\times n}$ can be factored as:

$$A^{(m\times n)} = U_1^{(m\times r)}\;\Sigma_1^{(r\times r)}\;V_1^{T\,(r\times n)} \qquad \text{(economy SVD)}$$

where $r = \operatorname{rank}(A)$, and the full SVD extends to square orthogonal matrices:

$$A = U\Sigma V^T, \quad U^{(m\times m)},\; \Sigma^{(m\times n)},\; V^{(n\times n)}$$
$U_1$Orthogonal; columns are the left singular vectors $u_i$
$V_1$Orthogonal; columns are the right singular vectors $v_i$
$\Sigma_1$Diagonal; $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$ are the singular values
Singular valuesAn intrinsic property of $A$; every SVD of $A$ shares the same $\Sigma_1$

Singular vectors and singular values satisfy $Av_i = \sigma_i u_i$ and $A^T u_i = \sigma_i v_i$.

PropertyFormula
Rank$\operatorname{rank}(A) = r$
Transpose$A^T = V\Sigma U^T$
Pseudoinverse$A^\dagger = V_1\Sigma_1^{-1}U_1^T$
Range of $A$$\mathcal{R}(U_1) = \mathcal{R}(A)$,   $\mathcal{R}(U_2) = \mathcal{R}(A)^\perp$
Nullspace of $A$$\mathcal{R}(V_1) = \mathcal{N}(A)^\perp$,   $\mathcal{R}(V_2) = \mathcal{N}(A)$
Spectral norm$\|A\|_2 = \sigma_1$
Frobenius norm$\|A\|_F = \sqrt{\sigma_1^2 + \cdots + \sigma_r^2}$