Proof-Based Linear Algebra – Complete Formula Sheet

Vector Spaces

Definition

Set $V$ over field $F$ with $+: V \times V \to V$ and $\cdot: F \times V \to V$

Axioms

Associativity: $(u+v)+w = u+(v+w)$

Commutativity: $u+v = v+u$

Identity: $\exists \mathbf{0} \in V$ s.t. $v+\mathbf{0}=v$

Inverses: $\forall v \exists -v$ s.t. $v+(-v)=\mathbf{0}$

Scalar assoc: $a(bv) = (ab)v$

Distributivity: $a(u+v) = au+av$

$(a+b)v = av+bv$ and $1v=v$

Examples

$\mathbb{R}^n$, $\mathbb{C}^n$ over $\mathbb{R}$ or $\mathbb{C}$

$P_n$ polynomials of degree $\leq n$

$M_{m \times n}$ matrices

$C([a,b])$ continuous functions

Subspaces

Criteria

$W \subseteq V$ is a subspace iff:

$\mathbf{0} \in W$

Closed under $+$: $u,v \in W \implies u+v \in W$

Closed under $\cdot$: $u \in W, c \in F \implies cu \in W$

Common Subspaces

Row/Column space of matrix

Null space $\text{null}(A) = \{x: Ax=0\}$

Eigenspace: $E_\lambda = \{v: Av = \lambda v\}$

Single criterion: $u,v \in W, a,b \in F \implies au+bv \in W$

Linear Combinations & Span

Linear Combination

$v = c_1v_1 + c_2v_2 + \cdots + c_nv_n$ where $c_i \in F$

Span

$\text{span}\{v_1,\ldots,v_n\} = \{c_1v_1 + \cdots + c_nv_n : c_i \in F\}$

Span is always a subspace

$v \in \text{span}\{v_1,\ldots,v_n\}$ iff system solvable

Spanning Set

$S$ spans $V$ iff $\text{span}(S) = V$

Every vector in $V$ is a linear combo of $S$

Linear Independence

Definition

$\{v_1,\ldots,v_n\}$ is lin. indep. iff:

$c_1v_1 + \cdots + c_nv_n = \mathbf{0} \implies c_i = 0 \forall i$

Characterizations

No vector is a combo of others

Matrix $[v_1 \cdots v_n]$ has full rank

System $A\mathbf{x}=\mathbf{0}$ has only trivial solution

Properties

Any subset of lin. indep. set is lin. indep.

Can't have more than $\dim(V)$ lin. indep. vectors

Basis & Dimension

Basis Definition

$\beta = \{v_1,\ldots,v_n\}$ is a basis of $V$ iff:

$\beta$ spans $V$

$\beta$ is linearly independent

Dimension

$\dim(V) = $ number of vectors in any basis

Well-defined: all bases have same cardinality

Existence & Uniqueness

Every nonzero fin.-dim. space has a basis

Every lin. indep. set extends to basis

Every spanning set contains a basis

Dimension Properties

$\dim(V \oplus W) = \dim V + \dim W$

If $W \subseteq V$: $\dim W \leq \dim V$

Linear Transformations

Definition

$T: V \to W$ s.t. $\forall v_1,v_2 \in V, c \in F$:

$T(cv_1 + v_2) = cT(v_1) + T(v_2)$

Examples

Multiplication by matrix $A$: $T(x) = Ax$

Differentiation: $D(p) = p'$

Evaluation: $\text{ev}_a(p) = p(a)$

Properties

$T(\mathbf{0}) = \mathbf{0}$

$T(-v) = -T(v)$

Image $\text{im}(T)$ is subspace of $W$

Kernel & Image

Kernel (Null Space)

$\ker(T) = \{v \in V : T(v) = \mathbf{0}\}$

Subspace of $V$

$\text{nullity}(T) = \dim(\ker T)$

Image (Range)

$\text{im}(T) = \{T(v) : v \in V\}$

Subspace of $W$

$\text{rank}(T) = \dim(\text{im} T)$

Rank-Nullity Theorem

$\dim V = \text{rank}(T) + \text{nullity}(T)$

Injectivity/Surjectivity

$T$ injective iff $\ker(T) = \{\mathbf{0}\}$

$T$ surjective iff $\text{im}(T) = W$

Matrix Representation

Matrix of $T$

If $\beta = \{v_1,\ldots,v_n\}$ basis of $V$, $\gamma = \{w_1,\ldots,w_m\}$ basis of $W$:

$[T]_\gamma^\beta = \begin{bmatrix} | & & | \\ [T(v_1)]_\gamma & \cdots & [T(v_n)]_\gamma \\ | & & | \end{bmatrix}$

Coordinate Vectors

If $v = c_1v_1 + \cdots + c_nv_n$:

$[v]_\beta = \begin{bmatrix} c_1 \\ \vdots \\ c_n \end{bmatrix}$

Computation

$[T(v)]_\gamma = [T]_\gamma^\beta [v]_\beta$

Change of Basis

Transition Matrix

If $\beta$ and $\gamma$ are bases of $V$:

$P_{\gamma \to \beta} = [[v_1]_\gamma \cdots [v_n]_\gamma]$

where $\beta = \{v_1,\ldots,v_n\}$

Coordinate Transformation

$[v]_\gamma = P_{\gamma \to \beta}[v]_\beta$

Matrix Transformation

$[T]_\gamma = P_{\gamma \to \beta}[T]_\beta P_{\beta \to \gamma}$

Properties

$P_{\beta \to \gamma} = (P_{\gamma \to \beta})^{-1}$

$P_{\gamma \to \beta}$ is invertible

Isomorphisms

Definition

$T: V \to W$ is an isomorphism iff:

$T$ is linear

$T$ is bijective (injective and surjective)

Characterizations

$T$ injective $+$ $\dim V = \dim W$ $\implies$ isomorphism

$\dim V = \dim W$ and $T$ invertible $\implies$ $T^{-1}$ linear

Isomorphism Classes

$V \cong W$ iff $\dim V = \dim W$ (over same field)

Equivalence relation on vector spaces

Every $n$-dim space over $F$ isomorphic to $F^n$

Dual Spaces

Definition

$V^* = \text{Hom}(V, F) = \{f: V \to F \text{ linear}\}$

$V^*$ is vector space (dual space)

Dual Basis

If $\beta = \{v_1,\ldots,v_n\}$ basis of $V$:

$\beta^* = \{v_1^*,\ldots,v_n^*\}$ where $v_i^*(v_j) = \delta_{ij}$

Properties

$\dim V^* = \dim V$ (if $V$ fin.-dim.)

$\beta^*$ is basis of $V^*$

$(V^*)^* \cong V$ (natural isomorphism)

Dual Transformation

$(T^*)f = f \circ T$ for $T: V \to W$

Inner Product Spaces

Definition

$\langle \cdot, \cdot \rangle: V \times V \to F$ s.t.:

Conj. symmetry: $\langle u,v \rangle = \overline{\langle v,u \rangle}$

Linearity in second: $\langle u,av+w \rangle = a\langle u,v \rangle + \langle u,w \rangle$

Positive definite: $\langle v,v \rangle > 0$ if $v \neq \mathbf{0}$

Examples

Standard: $\langle u,v \rangle = u^*v$ on $\mathbb{C}^n$

Weighted: $\langle u,v \rangle = u^*Wv$ with $W > 0$

Integral: $\langle f,g \rangle = \int_a^b f(x)\overline{g(x)}dx$

Orthonormal Bases & Gram-Schmidt

Orthogonality

$u \perp v$ iff $\langle u,v \rangle = 0$

Orthogonal set: all pairs orthogonal

Orthonormal: orthogonal + $\|v\| = 1$ all $v$

Gram-Schmidt Process

$u_1 = v_1$

$u_k = v_k - \sum_{j=1}^{k-1} \frac{\langle v_k, u_j \rangle}{\langle u_j, u_j \rangle} u_j$

Orthonormal Basis

Normalize: $e_k = \frac{u_k}{\|u_k\|}$

Properties

Every fin.-dim. IPS has orthonormal basis

Uniqueness of coordinates easier

Adjoint of Linear Map

Definition

$T^*: W \to V$ defined by:

$\langle T(v), w \rangle = \langle v, T^*(w) \rangle \forall v \in V, w \in W$

Matrix Form

If $A$ is matrix of $T$ (orthonormal bases):

$[T^*] = A^* = \overline{A^T}$ (conjugate transpose)

Properties

$(T^*)^* = T$

$(ST)^* = T^*S^*$

$(T+S)^* = T^* + S^*$

$(\lambda T)^* = \overline{\lambda} T^*$

Kernel-Image

$\ker(T^*) = (\text{im} T)^\perp$

$\text{im}(T^*) = (\ker T)^\perp$

Normal & Self-Adjoint Operators

Self-Adjoint (Hermitian)

$T^* = T$ (Hermitian matrix: $A^* = A$)

Eigenvalues are real

Eigenvectors from different eigenvalues orthogonal

Normal Operators

$TT^* = T^*T$ (commute with adjoint)

Includes self-adjoint as special case

Orthonormal basis of eigenvectors

Unitary (Isometric)

$T^*T = TT^* = I$

Preserves inner products: $\langle Tv, Tw \rangle = \langle v,w \rangle$

All eigenvalues have $|\lambda| = 1$

Spectral Theorem

Statement

If $T: V \to V$ self-adjoint:

All eigenvalues real

Eigenvectors orthogonalize

$V = \bigoplus_i E_{\lambda_i}$ (orthogonal direct sum)

Spectral Decomposition

$T = \sum_i \lambda_i P_{E_{\lambda_i}}$

where $P_{E_\lambda}$ is projection onto $E_\lambda$

Matrix Form

Diagonalizable by unitary matrix:

$A = UDU^*$ with $D$ diagonal, $U$ unitary

Applications

Quadratic forms classification

Optimization and PCA

Quadratic Forms

Definition

$Q(v) = \langle v, Av \rangle$ or $Q(x) = x^TAx$

Canonical Form

Via change of basis (orthonormal):

$Q(x) = \lambda_1 y_1^2 + \cdots + \lambda_n y_n^2$

where $\lambda_i$ are eigenvalues of $A$

Classification

Positive definite: all $\lambda_i > 0$

Negative definite: all $\lambda_i < 0$

Indefinite: $\lambda_i$ mixed signs

Semi-definite: $\lambda_i \geq 0$ or $\lambda_i \leq 0$

Sylvester's Criterion

$Q$ pos. def. iff all leading principal minors $> 0$

Bilinear Forms

Definition

$B: V \times V \to F$ linear in each argument:

$B(cv, w) = cB(v,w)$

$B(v, dw) = dB(v,w)$

Matrix Representation

$B(v,w) = [v]^T A [w]$ (relative to basis)

Symmetric vs Skew

Symmetric: $B(v,w) = B(w,v)$

Skew-symmetric: $B(v,w) = -B(w,v)$

Decomposition

$B = B_s + B_a$ where

$B_s(v,w) = \frac{1}{2}[B(v,w) + B(w,v)]$

$B_a(v,w) = \frac{1}{2}[B(v,w) - B(w,v)]$

Congruence

$A, B$ congruent iff $B = P^TAP$ for invertible $P$

PROOF-BASED LINEAR ALGEBRA Complete Formula Sheet