Introduction to
Linear Algebra

For any set A, the power set of A, denoted P(A), is the set whose elements are all subsets of A. Formally,

If A has n elements, then P(A) has 2ⁿ elements.

• P(A)the power set of A — the collection of all subsets of A.

If A and B are two sets, the notation B^A refers to the set of all functions from A to B:

Each function f ∈ B^A assigns to every element of A exactly one element of B.

• B^Athe set of all functions f : A → B.

When the codomain is the field of real numbers ℝ, the set ℝ^A is the space of all real‑valued functions on A. This set becomes a vector space with pointwise addition and scalar multiplication:

for all f, g ∈ ℝ^A, α ∈ ℝ, and x ∈ A.

• ℝ^Athe vector space of real‑valued functions on A.

For a finite set A, the cardinality |A| is the number of elements in A. If A is finite, then ℝ^A can be identified with the familiar coordinate space ℝ^|A| by enumerating the elements of A.

• |A|cardinality (number of elements) of the finite set A.
• ℝ^|A|the standard coordinate space of dimension |A|, isomorphic to ℝ^A when A is finite.

For a subset C ⊆ A, the indicator function of C is the function 1_C : A → {0,1} defined by

The notation 1_x∈C is sometimes used as a compact equivalent of 1_C(x).

• 1_Cindicator function of the set C; maps any x to 1 if x ∈ C, else 0.
• 1_x∈Calternative compact notation for 1_C(x).

The d-dimensional Euclidean space ℝ^d consists of all ordered d-tuples of real numbers. Its elements (called vectors) are usually written as column vectors with coordinates indexed by parenthesized exponents:

The parentheses around the index distinguish a coordinate from a power. Thus x⁽ⁱ⁾ denotes the i-th coordinate, not the i-th power of x.

• ℝ^dthe d-dimensional Euclidean space.
• x⁽ⁱ⁾the i-th coordinate of vector x, i = 1,…, d.

Geometrically, ℝ^d can be seen in two ways:

• As an affine space: its elements are points — fixed locations.
• As a vector space: its elements are vectors — directions and magnitudes that can be added and scaled.

After choosing the origin 0_d, every point can be identified with the vector from the origin to that point. In this text we will not distinguish notationally between points and vectors; both are treated as elements of the vector space ℝ^d.

• affine spacea set of points; a point is a position.
• vector spacea set of vectors; a vector is a translation (direction + magnitude).

Three fundamental objects are given special notation:

• Zero vector 0_d: the vector in ℝ^d with all coordinates 0.
• Ones vector 1_d: the vector in ℝ^d with all coordinates 1.
• Identity matrix I_d: the d × d matrix with 1 on the main diagonal and 0 elsewhere.

• 0_dthe d-dimensional zero vector.
• 1_dthe d-dimensional ones vector.
• I_dthe d × d identity matrix.

The columns of the identity matrix I_d form the canonical basis (or standard basis) of ℝ^d. They are denoted e₁, e₂, …, e_d, where e_i has a 1 in the i-th coordinate and zeros elsewhere:

Every x ∈ ℝ^d can be uniquely expressed as x = ∑_i=1^d x⁽ⁱ⁾ e_i.

• e_ithe i-th standard basis vector, i = 1,…, d.

The Euclidean norm (or ℓ² norm) of a vector x ∈ ℝ^d is denoted |x| and defined by

It satisfies the axioms of a norm: positive definiteness, homogeneity, and the triangle inequality. The notation ∥x∥₂ is also used.

• |x|the Euclidean (ℓ²) norm of x.
• ∥x∥₂alternative notation for the Euclidean norm.

For any real number p ≥ 1, the ℓ^p norm of x ∈ ℝ^d is defined by

For every p ≥ 1, ∥·∥_p satisfies the triangle inequality (Minkowski's inequality) and therefore is a genuine norm. Important special cases:

• p = 1: Manhattan (or ℓ¹) norm.
• p = 2: Euclidean norm (|x|).
• p → ∞: maximum norm (the largest absolute coordinate).

• ∥x∥_pthe ℓ^p norm of x, p ≥ 1.

For 0 < p < 1 the formula (1.1) remains well‑defined, but it does not define a norm: the triangle inequality fails. Despite this, the family is used in the study of sparsity because the limit

counts exactly the number of non‑zero coordinates of x. This quantity is called the ℓ⁰ "norm" (though it is not a norm). It is the natural measure of sparsity.

• ∥x∥_p (0 < p < 1)a non‑norm quantity; fails the triangle inequality.
• ∥x∥₀the number of non‑zero entries of x; the ℓ⁰ "norm".

Throughout the text we follow these conventions:

• Single bars |·| are used for norms of finite‑dimensional vectors (typically the Euclidean norm).
• Double bars ∥·∥ are reserved for norms of infinite‑dimensional objects, such as functions in Hilbert spaces.
• The notation |A| with a set A denotes the cardinality of A; the meaning (vector norm vs. set size) is always clear from context.

• |·|norm on a finite‑dimensional space.
• ∥·∥norm on an infinite‑dimensional space.
• |A|cardinality of the set A.

The set of all m × d real matrices (i.e., matrices with m rows and d columns, all entries real) is denoted M_m,d(ℝ), or simply M_m,d. When m = d we also write M_d for the space of square matrices of size d × d.

The subset of d × d matrices that are invertible (i.e., have a two‑sided multiplicative inverse) is the general linear group, denoted GL_d(ℝ):

• M_m,d(ℝ)the set of all real m × d matrices; often just M_m,d.
• M_dshorthand for M_d,d, the set of d × d square matrices.
• GL_d(ℝ)the general linear group: the set of invertible d × d real matrices.

Given m column vectors x₁, …, x_m ∈ ℝ^d, the notation [x₁, …, x_m] stands for the d × m matrix whose j-th column is x_j. Thus the d × d identity matrix can be written as

where e₁, …, e_d are the canonical basis vectors.

• [x₁, …, x_m]the d × m matrix formed by horizontally stacking the column vectors x₁, …, x_m.

For a matrix A ∈ M_m,d(ℝ), the entry in row i and column j is denoted either A(i, j) or A⁽ⁱ⁾_j. The whole i-th row (as a row vector) is denoted A⁽ⁱ⁾, and the j-th column (as a column vector) is denoted A_j. Thus

• A(i, j)the entry of A in row i, column j (first index = row).
• A⁽ⁱ⁾_jalternative notation for the same entry; superscript in parentheses = row.
• A⁽ⁱ⁾the i-th row of A (a row vector).
• A_jthe j-th column of A (a column vector).

For a matrix A ∈ M_m,d, its operator norm (induced by the Euclidean vector norm) is defined by

It measures the maximum factor by which A can stretch a unit vector. Equivalently, |A|_op is the largest singular value of A.

• |A|_opthe operator norm of A (induced by the Euclidean norm).

The set of d × d real symmetric matrices (satisfying A^T = A) is denoted S^d. Two important subsets are defined by the sign of the quadratic form x^T A x:

• Positive semi‑definite (PSD) matrices: S₊^d = { A ∈ S^d ∣ x^T A x ≥ 0 for all x ∈ ℝ^d }.
• Positive definite (PD) matrices: S₊₊^d = { A ∈ S^d ∣ x^T A x > 0 for all non‑zero x ∈ ℝ^d }.

Every A ∈ S₊₊^d is invertible, but the converse is false.

• S^dthe set of d × d real symmetric matrices.
• S₊^dthe set of positive semi‑definite d × d matrices.
• S₊₊^dthe set of positive definite d × d matrices.

For m ≤ d, the set O_m,d consists of all m × d real matrices A whose rows are orthonormal, i.e.,

When m = d, we write O_d for the set of orthogonal matrices (square matrices with orthonormal rows and columns). A matrix A ∈ O_d satisfies A^T = A⁻¹ and has determinant ±1.

The special orthogonal group SO_d is the subset of O_d consisting of orthogonal matrices with determinant exactly 1; these are precisely the rotation matrices in ℝ^d.

• O_m,d (m ≤ d)set of m × d matrices with orthonormal rows (A A^T = I_m).
• O_dthe orthogonal group: d × d matrices with A^T A = I_d.
• SO_dthe special orthogonal group: { A ∈ O_d ∣ det(A) = 1 }, i.e., rotation matrices.

A vector space over a field 𝔽 (we take 𝔽 = ℝ throughout, unless noted) is a set V together with an addition + : V × V → V and a scalar multiplication · : 𝔽 × V → V satisfying, for all u, v, w ∈ V and α, β ∈ 𝔽:

Elements of V are called vectors. The spaces ℝ^d, M_m,d, and ℝ^A introduced earlier are all examples of vector spaces over ℝ.

• Va vector space over 𝔽.
• 0 ∈ Vthe additive identity (zero vector) of V.
• −vthe additive inverse of v.

A subset W ⊆ V is a subspace of V if W is itself a vector space under the addition and scalar multiplication inherited from V. Equivalently, W is a subspace if and only if:

Conditions (ii) and (iii) can be combined into a single closure condition: αu + βv ∈ W for all u, v ∈ W, α, β ∈ ℝ.

• W ⊆ Va subspace of V.

If U, W are subspaces of V, their sum is

U + W is itself a subspace of V, and is in fact the smallest subspace containing both U and W.

• U + Wthe sum of subspaces U and W.

If U and W are subspaces of V, then U ∩ W is also a subspace of V.

Proof. Since 0 ∈ U and 0 ∈ W, we have 0 ∈ U ∩ W. Now let x, y ∈ U ∩ W and α, β ∈ ℝ. Since x, y ∈ U and U is a subspace, αx + βy ∈ U. Likewise αx + βy ∈ W. Hence αx + βy ∈ U ∩ W, so U ∩ W is closed under linear combinations and contains 0 — it is a subspace. ∎

The sum U + W is called a direct sum, written U ⊕ W, if every element of U + W can be written uniquely as u + w with u ∈ U, w ∈ W. This holds if and only if U ∩ W = {0}.

• U ⊕ Wdirect sum of U and W; well‑defined exactly when U ∩ W = {0}.

Given vectors v₁, …, v_k ∈ V and scalars α₁, …, α_k ∈ ℝ, the vector

is called a linear combination of v₁, …, v_k. The scalars α_i are the coefficients of the combination.

• α_icoefficient of v_i in the linear combination.

The span of a set S = {v₁, …, v_k} ⊆ V is the set of all linear combinations of its elements:

By convention, span(∅) = {0}. A set S is said to span V (or to be a generating set) if span(S) = V.

• span(S)the set of all finite linear combinations of vectors in S.

For any S ⊆ V, span(S) is a subspace of V, and it is the smallest subspace of V containing S: if W is any subspace with S ⊆ W, then span(S) ⊆ W.

Proof sketch. Closure under linear combinations is immediate from the definition of span. For minimality: any subspace containing S must, by closure, contain every linear combination of elements of S, hence must contain span(S). ∎

Vectors v₁, …, v_k ∈ V are linearly independent if the only solution to

is the trivial one, α₁ = α₂ = ⋯ = α_k = 0. If a non‑trivial solution exists, the vectors are linearly dependent.

• linearly independentno non‑trivial linear combination of the vectors equals 0.

Vectors v₁, …, v_k (with k ≥ 2) are linearly dependent if and only if at least one v_i can be written as a linear combination of the others.

Proof. (⇒) If dependent, some non‑trivial combination ∑ α_iv_i = 0 has a coefficient α_j ≠ 0. Solving for v_j gives v_j = −α_j⁻¹ ∑_i≠j α_iv_i, a combination of the others. (⇐) If v_j = ∑_i≠j β_iv_i, then v_j − ∑_i≠j β_iv_i = 0 is a non‑trivial combination summing to zero (coefficient of v_j is 1 ≠ 0). ∎

If {v₁, …, v_m} is linearly independent and {w₁, …, w_n} spans V, then m ≤ n, and it is possible to replace m of the w_i with the v_i so that the resulting set still spans V.

A set B = {v₁, …, v_d} ⊆ V is a basis of V if it is both:

• linearly independent, and
• spanning, i.e., span(B) = V.

Equivalently, B is a basis if and only if every v ∈ V can be written uniquely as a linear combination of elements of B.

• Ba basis of V.

If V is spanned by a finite set, then V has a basis. Moreover, any spanning set contains a basis, and any linearly independent set can be extended to a basis.

Proof sketch. Start with a finite spanning set S. If S is linearly dependent, remove a vector that is a linear combination of the others (A1.29); the smaller set still spans V. Repeat until the remaining set is linearly independent — it is then a basis (the process terminates since S is finite). ∎

If V has a finite basis, then every basis of V has the same number of elements.

Proof. Let B₁ = {v₁,…,v_m} and B₂ = {w₁,…,w_n} both be bases. Since B₁ is linearly independent and B₂ spans V, the Exchange Lemma (A1.30) gives m ≤ n. By symmetry (swapping the roles), n ≤ m. Hence m = n. ∎

The dimension of a vector space V, denoted dim(V), is the number of vectors in any basis of V (well‑defined by A1.33). A vector space is finite‑dimensional if it has a finite basis, and infinite‑dimensional otherwise (e.g., ℝ^ℕ, the space of all real sequences).

• dim(V)the dimension of V; size of any basis of V.

If U, W are finite‑dimensional subspaces of V, then

In particular, if the sum is direct (U ∩ W = {0}), then dim(U ⊕ W) = dim(U) + dim(W).

Fix an ordered basis B = (v₁, …, v_d) of V. By the basis property, every v ∈ V has a unique representation v = ∑_i=1^d α_iv_i. The coordinate vector of v relative to B is

The map v ↦ [v]_B is a linear bijection (an isomorphism, A1.50) between V and ℝ^d.

• [v]_Bthe coordinate vector of v relative to ordered basis B.

If B = (v₁,…,v_d) and B′ = (v′₁,…,v′_d) are two ordered bases of V, the change‑of‑basis matrix P from B to B′ is the matrix whose j-th column is [v_j]_B′. It satisfies

P is always invertible, with P⁻¹ the change‑of‑basis matrix from B′ to B.

• Pchange‑of‑basis matrix from B to B′.

If W is a subspace of a finite‑dimensional V, then dim(W) ≤ dim(V), with equality if and only if W = V.

Proof. Any linearly independent subset of W is also linearly independent in V, so by the Exchange Lemma its size cannot exceed dim(V); hence a basis of W has at most dim(V) elements. If dim(W) = dim(V), a basis of W is a maximal independent set in V and therefore must already span V, so W = V. ∎

A function T : V → W between vector spaces is a linear transformation (or linear map, or linear operator when V = W) if for all u, v ∈ V and α ∈ ℝ:

Equivalently, T(αu + βv) = αT(u) + βT(v) for all scalars α, β — linear maps "commute" with linear combinations. The set of all linear maps from V to W is denoted ℒ(V, W); it is itself a vector space.

• T : V → Wa linear transformation from V to W.
• ℒ(V, W)the vector space of all linear maps from V to W.

If T : V → W is linear, then T(0_V) = 0_W.

Proof. T(0) = T(0 · 0) = 0 · T(0) = 0, using homogeneity with α = 0. ∎

Let {v₁,…,v_d} be a basis of V, and let w₁,…,w_d ∈ W be arbitrary. There exists a unique linear map T : V → W with T(v_i) = w_i for each i, given by

The kernel (or null space) of a linear map T : V → W is

ker(T) is always a subspace of V (it is non‑empty since T(0) = 0, and closed under linear combinations by linearity of T).

• ker(T)the kernel/null space of T; preimage of 0.

The image (or range) of T : V → W is

im(T) is a subspace of W. The dimension of im(T) is called the rank of T, denoted rank(T), and the dimension of ker(T) is called the nullity of T.

• im(T)the image/range of T.
• rank(T)dim(im(T)).
• nullity(T)dim(ker(T)).

A linear map T : V → W is injective (one‑to‑one) if and only if ker(T) = {0}.

Proof. (⇒) If T is injective and v ∈ ker(T), then T(v) = 0 = T(0), so v = 0. (⇐) Suppose ker(T) = {0} and T(u) = T(v). By linearity, T(u − v) = 0, so u − v ∈ ker(T) = {0}, i.e., u = v. ∎

Let T : V → W be a linear map with V finite‑dimensional. Then

Proof sketch. Extend a basis {u₁,…,u_k} of ker(T) to a basis {u₁,…,u_k,v₁,…,v_r} of V. One shows {T(v₁),…,T(v_r)} is a basis of im(T), giving dim(V) = k + r = nullity(T) + rank(T). ∎

A linear map T : V → W is an isomorphism if it is bijective (both injective and surjective). Two vector spaces are isomorphic, written V ≅ W, if there exists an isomorphism between them. Isomorphic spaces are "the same" as far as linear‑algebraic structure is concerned.

• V ≅ WV and W are isomorphic (related by a bijective linear map).

Two finite‑dimensional vector spaces V and W are isomorphic if and only if dim(V) = dim(W). In particular, every d-dimensional real vector space is isomorphic to ℝ^d (via the coordinate map of A1.36).

Fix bases B = (v₁,…,v_d) of V and C = (w₁,…,w_m) of W. For a linear map T : V → W, the matrix representation [T]_C,B ∈ M_m,d is the matrix whose j-th column is the coordinate vector [T(v_j)]_C:

It satisfies [T(v)]_C = [T]_C,B [v]_B for every v ∈ V — applying T corresponds exactly to matrix–vector multiplication in coordinates.

• [T]_C,Bmatrix of T relative to bases B (domain) and C (codomain).

For A ∈ M_m,d and x ∈ ℝ^d, the product Ax ∈ ℝ^m is defined coordinate‑wise by

Equivalently, Ax = ∑_j=1^d x^(j) A_j — a linear combination of the columns of A, weighted by the entries of x. The map x ↦ Ax is linear, and every linear map ℝ^d → ℝ^m arises this way for a unique A (A1.41).

For A, B ∈ M_m,d and α ∈ ℝ, addition and scalar multiplication are defined entrywise:

Under these operations M_m,d is itself a vector space, isomorphic to ℝ^md, with dim(M_m,d) = md.

For A ∈ M_m,n and B ∈ M_n,d, the product AB ∈ M_m,d is defined by

Equivalently, the j-th column of AB is A applied to the j-th column of B: (AB)_j = A B_j. The number of columns of A must equal the number of rows of B.

• ABmatrix product, defined when A is m×n and B is n×d.

If S : U → V and T : V → W are linear maps with matrix representations [S] and [T] (relative to compatible bases), then the composition T ∘ S : U → W is linear and

Proof sketch. Both sides agree on every basis vector of U by direct computation using A1.49; by A1.41, agreement on a basis implies the maps (matrices) are identical. ∎

For matrices of compatible sizes:

Crucially, matrix multiplication is not commutative in general: AB ≠ BA, even when both products are defined (e.g., when A, B are square).

The transpose of A ∈ M_m,d is the matrix A^T ∈ M_d,m defined by A^T(i,j) = A(j,i). Transposition satisfies:

• A^Tthe transpose of A.

The trace of a square matrix A ∈ M_d is the sum of its diagonal entries:

Trace is linear (tr(αA + βB) = α tr(A) + β tr(B)) and satisfies the cyclic property: for compatible A, B, tr(AB) = tr(BA) (even though AB ≠ BA in general).

• tr(A)the trace of square matrix A.

For x ∈ ℝ^d and A ∈ M_d, the scalar quadratic form can be rewritten using trace:

This identity is heavily used to manipulate expectations of quadratic forms, since tr and expectation (a linear operator) commute: 𝔼[x^TAx] = tr(A · 𝔼[xx^T]).

A matrix A ∈ M_d is invertible if there exists A⁻¹ ∈ M_d such that AA⁻¹ = A⁻¹A = I_d (see A1.14, GL_d(ℝ)). If it exists, the inverse is unique.

Proof of uniqueness. If B and C both satisfy AB = I = AC, then B = B(AC) = (BA)C = IC = C. ∎

For A ∈ M_d, the following are equivalent:

• (i) A is invertible;
• (ii) the linear map x ↦ Ax is bijective on ℝ^d;
• (iii) ker(A) = {0} (the only solution to Ax = 0 is x = 0);
• (iv) rank(A) = d (the columns of A are linearly independent and span ℝ^d);
• (v) det(A) ≠ 0 (see A1.65).

Proof sketch. (i)⟺(ii) is the definition of an inverse function. (ii)⟺(iii) is A1.44 combined with rank–nullity (A1.45), since for a square matrix injective implies surjective. (iii)⟺(iv) follows directly from the definition of linear independence and span applied to the columns. (iv)⟺(v) is proved once the determinant is introduced. ∎

The determinant det : M_d → ℝ is the unique function satisfying:

• (i) det is linear in each column of A separately, with the other columns fixed (multilinearity, cf. A1.20 in the earlier notation block);
• (ii) det changes sign when two columns are swapped (alternating);
• (iii) det(I_d) = 1 (normalization).

These three properties determine det uniquely on all of M_d.

• det(A)the determinant of A; also written |A| in some texts (context disambiguates from the norm, A1.13).

For A ∈ M_d, let A_ij denote the (d−1)×(d−1) submatrix obtained by deleting row i and column j. Expanding along row i:

The quantity C_ij = (−1)^i+j det(A_ij) is the cofactor of entry (i,j). For the base case d = 1, det([a]) = a; for d = 2, det = ad − bc for A = [[a,b],[c,d]].

• A_ijthe (d−1)×(d−1) minor obtained by deleting row i and column j.
• C_ijthe (i,j) cofactor.

For A, B ∈ M_d,

Consequently, if A is invertible, det(A⁻¹) = 1/det(A), and det(A) ≠ 0 is necessary for invertibility — this completes the proof of A1.58 (v).

A direct consequence is that the alternating/multilinear properties of A1.59 hold equally well for rows as for columns.

If A is upper‑ or lower‑triangular (all entries on one side of the diagonal are zero), then

— the determinant is simply the product of the diagonal entries. This is the computational basis for evaluating determinants via LU‑type decompositions.

|det(A)| equals the d-dimensional volume of the parallelepiped spanned by the columns of A. The sign of det(A) records whether the linear map x ↦ Ax preserves orientation (det > 0) or reverses it (det < 0). A linear map scales every volume by exactly the factor |det(A)|.

A square matrix A is invertible if and only if det(A) ≠ 0, in which case

where adj(A), the adjugate, is the transpose of the cofactor matrix: adj(A)(i,j) = C_ji.

If A is block upper‑triangular with square diagonal blocks A₁,…,A_k,

If A ∈ O_d (A1.19 in the earlier notation block), then AA^T = I_d, so by A1.61 and A1.62, det(A)² = det(AA^T) = det(I_d) = 1, hence

det(A) = +1 corresponds to a rotation (A ∈ SO_d); det(A) = −1 corresponds to a rotation composed with a reflection.

An inner product on a real vector space V is a function ⟨·,·⟩ : V × V → ℝ satisfying, for all u, v, w ∈ V and α ∈ ℝ:

The standard (Euclidean) inner product, or dot product, on ℝ^d is ⟨x,y⟩ = x^Ty = ∑_i=1^d x⁽ⁱ⁾y⁽ⁱ⁾, and induces the Euclidean norm via |x| = √⟨x,x⟩.

• ⟨u, v⟩inner product of u and v.
• x^Tythe standard dot product on ℝ^d.

For all x, y in an inner product space,

with equality if and only if x and y are linearly dependent (parallel).

Proof sketch. For any t ∈ ℝ, 0 ≤ ⟨x − ty, x − ty⟩ = |x|² − 2t⟨x,y⟩ + t²|y|². This quadratic in t is non‑negative for all t, so its discriminant must be ≤ 0, which rearranges directly to the inequality. ∎

For non‑zero x, y ∈ ℝ^d, the Cauchy–Schwarz inequality guarantees that the quantity

lies in [−1, 1], defining the angle θ between x and y. This quantity, also called cosine similarity, is widely used directly (without inverting to recover θ) as a similarity score.

Vectors x, y are orthogonal, written x ⟂ y, if ⟨x, y⟩ = 0. A set of vectors is orthogonal if every distinct pair is orthogonal, and orthonormal if it is orthogonal and every vector has unit norm.

• x ⟂ yx is orthogonal to y, i.e., ⟨x,y⟩ = 0.

If x ⟂ y, then

Proof. |x+y|² = ⟨x+y,x+y⟩ = |x|² + 2⟨x,y⟩ + |y|² = |x|² + |y|², using ⟨x,y⟩=0. ∎

If v₁,…,v_k are pairwise orthogonal and non‑zero, they are linearly independent.

Proof. Suppose ∑_i α_iv_i = 0. Taking the inner product of both sides with v_j: ∑_i α_i⟨v_i,v_j⟩ = α_j|v_j|² = 0 (all cross terms vanish by orthogonality). Since v_j ≠ 0, α_j = 0, for every j. ∎

A basis {u₁,…,u_d} of V that is orthonormal is called an orthonormal basis. The canonical basis {e₁,…,e_d} of ℝ^d is the prototypical example. Relative to an orthonormal basis, coordinates are obtained simply by inner products:

Given linearly independent v₁,…,v_k, define recursively

Then {u₁,…,u_k} is an orthogonal set with span(u₁,…,u_i) = span(v₁,…,v_i) for every i. Normalizing each u_i by its norm produces an orthonormal set spanning the same subspace, and underlies the QR decomposition A = QR with Q orthonormal columns and R upper triangular.

For a subspace W ⊆ V, the orthogonal complement is

W^⟂ is always a subspace, and when V is finite‑dimensional, V = W ⊕ W^⟂ (direct sum, A1.24), so dim(W) + dim(W^⟂) = dim(V).

• W^⟂orthogonal complement of W.

Let W ⊆ ℝ^d be a subspace. For every x ∈ ℝ^d there is a unique p ∈ W, called the orthogonal projection of x onto W and written p = proj_W(x), satisfying (x − p) ⟂ W. It is also the unique closest point of W to x:

If {u₁,…,u_k} is an orthonormal basis of W, then proj_W(x) = ∑_i=1^k ⟨x,u_i⟩ u_i.

If U ∈ M_d,k has orthonormal columns spanning W, the orthogonal projection onto W is given by the matrix

A projection matrix P is characterized algebraically by being idempotent and symmetric: P² = P and P^T = P.

• P_Worthogonal projection matrix onto subspace W.

If {u₁,…,u_k} is orthonormal in V, then for any x ∈ V,

with equality if and only if x ∈ span(u₁,…,u_k). This is an immediate consequence of the Pythagorean theorem applied to x = proj_W(x) + (x − proj_W(x)).

If {u₁,…,u_d} is an orthonormal basis of ℝ^d, then for any x,

Norm is preserved exactly when expressed in orthonormal coordinates — a special case of Bessel's inequality (A1.79) becoming an equality because the basis spans the whole space.

For A ∈ M_d, a non‑zero vector v ∈ ℝ^d is an eigenvector of A with corresponding eigenvalue λ ∈ ℂ if

Geometrically, A acts on an eigenvector purely by scaling — it does not rotate or change the direction of v. The set of all eigenvalues of A is the spectrum of A.

• λan eigenvalue of A.
• van eigenvector of A associated with λ.

For an eigenvalue λ of A, the eigenspace is

E_λ is a subspace of ℝ^d (the null space of A − λI) of dimension at least 1. Its dimension is the geometric multiplicity of λ.

• E_λeigenspace of A for eigenvalue λ.

λ is an eigenvalue of A if and only if A − λI is not invertible, i.e., det(A − λI) = 0 (A1.65). The function

is the characteristic polynomial of A, a degree‑d polynomial in λ. Its roots are exactly the eigenvalues of A. The multiplicity of λ as a root of p_A is the algebraic multiplicity of λ, and is always ≥ the geometric multiplicity (A1.82).

• p_A(λ)the characteristic polynomial det(A − λI).

Every A ∈ M_d(ℂ) has at least one (complex) eigenvalue, since the characteristic polynomial p_A has degree d ≥ 1 and, by the fundamental theorem of algebra, every non‑constant complex polynomial has a root. Real matrices may have genuinely complex eigenvalues (occurring in conjugate pairs), which is why the spectrum is defined over ℂ even for real A.

If A is triangular, its eigenvalues are exactly its diagonal entries A(1,1),…,A(d,d), since A − λI is also triangular and (A1.63) det(A − λI) = ∏_i(A(i,i) − λ).

If λ₁,…,λ_d are the eigenvalues of A (with multiplicity, over ℂ), then

This follows from expanding the characteristic polynomial p_A(λ) = ∏_i(λ_i − λ) and comparing coefficients with det(A − λI).

If λ₁,…,λ_k are distinct eigenvalues of A with eigenvectors v₁,…,v_k, then {v₁,…,v_k} is linearly independent.

Proof sketch (induction). Suppose, for contradiction, a minimal dependent relation ∑ α_iv_i = 0 with all α_i ≠ 0. Apply A: ∑ α_iλ_iv_i = 0. Subtract λ_k times the original relation: ∑_i<k α_i(λ_i − λ_k)v_i = 0, a shorter non‑trivial relation (since λ_i ≠ λ_k) — contradicting minimality. ∎

A ∈ M_d is diagonalizable if there exists an invertible P ∈ M_d and diagonal D ∈ M_d such that

The columns of P are eigenvectors of A, and the diagonal entries of D are the corresponding eigenvalues. Diagonalization expresses A as "the same scaling operation as D, viewed in a different basis."

A ∈ M_d is diagonalizable if and only if ℝ^d (or ℂ^d) has a basis of eigenvectors of A, which holds if and only if, for every eigenvalue, the geometric multiplicity equals the algebraic multiplicity. A sufficient (but not necessary) condition is that A has d distinct eigenvalues (by A1.87).

If A = PDP⁻¹, then for any integer k ≥ 1,

where D^k is obtained by simply raising each diagonal entry to the k-th power — turning an expensive repeated matrix product into d scalar exponentiations.

If A ∈ S^d (real symmetric, A^T=A), then:

• (i) all eigenvalues of A are real;
• (ii) eigenvectors corresponding to distinct eigenvalues are orthogonal;
• (iii) A is diagonalizable by an orthogonal matrix: there exists U ∈ O_d and diagonal D such that

This is arguably the single most important theorem in applied linear algebra: every symmetric matrix has a complete orthonormal eigenbasis.

• Uorthogonal matrix of eigenvectors (eigenbasis) of A.
• ∑_i λ_i u_i u_i^Tthe spectral decomposition of A.

Real eigenvalues: if Av = λv with v possibly complex, then v̄^TAv = λ v̄^Tv; taking conjugate transposes and using A^T=A real shows λ̄ = λ, so λ is real.

Orthogonality: if Av = λv, Aw = μw with λ ≠ μ, then λ⟨v,w⟩ = ⟨Av,w⟩ = ⟨v,A^Tw⟩ = ⟨v,Aw⟩ = μ⟨v,w⟩, forcing ⟨v,w⟩=0.

Full diagonalization: by induction on dimension using the existence of at least one real eigenvector (from (i)) and restricting A to the orthogonal complement of that eigenvector, which is itself invariant under A. ∎

For A ∈ S^d with eigenvalues λ₁,…,λ_d (all real, by A1.91):

Proof sketch. Write x = ∑ c_iu_i in the eigenbasis; then x^TAx = ∑_i λ_ic_i² by orthonormality. This is non‑negative for all x (all c_i) iff every λ_i ≥ 0, and strictly positive for all x≠0 iff every λ_i > 0. ∎

For A ∈ S^d, the Rayleigh quotient is

If λ_max and λ_min are the largest and smallest eigenvalues of A, then

with equality at the corresponding eigenvectors. More generally, the eigenvectors are exactly the stationary points of R, and successive eigenvalues solve constrained maximizations of R over the orthogonal complement of previously found eigenvectors.

For A ∈ S^d,

i.e., the operator norm (A1.17) equals the largest eigenvalue in absolute value, a direct consequence of the Rayleigh quotient bound (A1.94) applied to ±A.

Every matrix A ∈ M_m,d (not necessarily square or symmetric) admits a decomposition

where U ∈ O_m, V ∈ O_d are orthogonal, and Σ ∈ M_m,d is rectangular‑diagonal with non‑negative entries σ₁ ≥ σ₂ ≥ ⋯ ≥ σ_r > 0 (and zeros elsewhere), called the singular values of A, where r = rank(A).

• U, Vorthogonal matrices of left/right singular vectors.
• σ_ithe i‑th singular value of A.

The matrices A^TA ∈ S^d and AA^T ∈ S^m are both positive semidefinite (A1.93), since x^T(A^TA)x = |Ax|² ≥ 0. By the spectral theorem (A1.91), they are orthogonally diagonalizable, and:

Proof sketch. Diagonalize A^TA = VΛV^T. Set σ_i = √λ_i for λ_i > 0, and u_i = Av_i/σ_i; one checks these u_i are orthonormal and extend to a full orthogonal basis U of ℝ^m, giving A = UΣV^T. ∎

Given A = UΣV^T with rank r, the singular vectors decompose the domain and codomain exactly:

• v₁,…,v_r: orthonormal basis for im(A^T) ("row space");
• v_r+1,…,v_d: orthonormal basis for ker(A);
• u₁,…,u_r: orthonormal basis for im(A) ("column space");
• u_r+1,…,u_m: orthonormal basis for ker(A^T).

This refines the rank–nullity theorem (A1.45) into an explicit, orthogonal geometric picture of how A acts.

Given the SVD A = ∑_i=1^r σ_i u_i v_i^T, the best rank‑k approximation to A (for k < r) in operator norm — and also in the Frobenius norm — is obtained by truncating the sum:

with approximation error |A − A_k|_op = σ_k+1.

The Frobenius norm of A ∈ M_m,d is defined by

It treats A as a vector in ℝ^md and applies the Euclidean norm — it is the matrix analogue of the ℓ² norm and is the natural choice for measuring reconstruction error in matrix factorization.

• |A|_FFrobenius norm of A.

For A = UΣV^T (possibly non‑square, non‑invertible), the pseudoinverse is

where Σ⁺ replaces each non‑zero singular value σ_i with 1/σ_i and transposes the rectangular shape. When A is square and invertible, A⁺ = A⁻¹. In general, x = A⁺b gives the minimum‑norm solution to the least‑squares problem min_x|Ax − b|.

• A⁺the Moore–Penrose pseudoinverse of A.

Recall (A1.24–A1.25 of the notation block) that a quadratic form is q(x) = x^TAx for symmetric A. Using the spectral theorem, substituting x = Uy (a rotation of coordinates) diagonalizes the form:

In the eigenbasis, every quadratic form is simply a weighted sum of squares — geometrically, level sets q(x)=c are ellipsoids (PD case) whose axes point along eigenvectors and whose lengths scale as 1/√λ_i.

For invertible A, the condition number (in the operator norm) is

A large condition number indicates A is "nearly singular" and that solving Ax = b (or optimizing a quadratic with Hessian A) is numerically sensitive to perturbations — small changes in input can produce large changes in output.

For a differentiable function f : ℝ^d → ℝ, the gradient at x is the vector of partial derivatives

characterized as the unique vector satisfying the first‑order approximation f(x+h) = f(x) + ⟨∇f(x), h⟩ + o(|h|) as h → 0. The gradient points in the direction of steepest increase of f.

• ∇f(x)gradient of f at x.

For a ∈ ℝ^d and symmetric A ∈ S^d:

If A is not symmetric, the more general identity is ∇_x(x^TAx) = (A + A^T)x.

For a differentiable vector‑valued function F : ℝ^d → ℝ^m, the Jacobian at x is the m × d matrix of partial derivatives

which gives the best local linear approximation: F(x+h) ≈ F(x) + J_F(x) h. Each row of J_F is the gradient (transposed) of the corresponding component function F_i.

• J_F(x)the Jacobian matrix of F at x.

If G : ℝⁿ → ℝ^d and F : ℝ^d → ℝ^m are differentiable, then F ∘ G is differentiable and

i.e., Jacobians compose by matrix multiplication, exactly mirroring composition of linear maps (A1.52). This single identity, applied recursively through a network's layers, is the chain rule that backpropagation implements.

For a twice‑differentiable f : ℝ^d → ℝ, the Hessian at x is the matrix of second partial derivatives

By equality of mixed partials (Clairaut's theorem, under mild continuity assumptions), H_f(x) is symmetric: H_f(x) ∈ S^d. It is the Jacobian of the gradient: H_f(x) = J_∇f(x).

• H_f(x)the Hessian of f at x.

For twice‑differentiable f,

This is the quadratic local model of f: a linear term (gradient) plus a curvature correction (Hessian). The Hessian term captures exactly the "bowl shape" of the function near x.

Suppose x⋆ is a critical point of f (i.e. ∇f(x⋆) = 0). Then:

• if H_f(x⋆) ≻ 0 (positive definite), x⋆ is a strict local minimum;
• if H_f(x⋆) ≺ 0 (negative definite), x⋆ is a strict local maximum;
• if H_f(x⋆) is indefinite (mixed‑sign eigenvalues), x⋆ is a saddle point.

This follows directly from A1.93 and A1.102 applied to the quadratic term of A1.109.

A twice‑differentiable function f : ℝ^d → ℝ is convex on a convex domain if and only if H_f(x) ⪰ 0 for every x in the domain, and strictly convex if H_f(x) ≻ 0 everywhere. Convex functions have the crucial property that every local minimum is a global minimum.

Given a random vector x ∈ ℝ^d with mean μ = 𝔼[x], the covariance matrix is

Σ is always symmetric positive semidefinite (A1.93): for any w, w^TΣw = Var(w^Tx) ≥ 0. For a data matrix X ∈ M_n,d with rows being n centered observations, the empirical covariance is Σ̂ = (1/n) X^TX.

• Σthe covariance matrix of x.

Given centered data with empirical covariance Σ̂, the first principal component direction u₁ is the unit vector maximizing the variance of the projected data:

Subsequent components u₂, u₃, … solve the same maximization subject to being orthogonal to all previously found components.

• u₁the first principal component direction.

The variational problem of A1.113 is solved exactly by the eigenvectors of Σ̂: if Σ̂ = ∑_i λ_i u_i u_i^T with λ₁ ≥ λ₂ ≥ ⋯ ≥ 0 (spectral theorem, A1.91), then u_i is the i-th principal component, and the maximal variance achieved is exactly λ_i.

Proof sketch. This is the Rayleigh quotient maximization of A1.94, restricted to the unit sphere and, successively, to orthogonal complements — exactly the setting in which the variational characterization of eigenvalues applies. ∎

If X ∈ M_n,d is the centered data matrix and X = UΣV^T is its SVD, then since X^TX = VΣ²V^T, the columns of V are exactly the principal component directions, and the principal component scores (projected coordinates) are the columns of XV = UΣ.

This avoids ever explicitly forming the (potentially ill‑conditioned) covariance matrix Σ̂.

Projecting onto the top k principal components and reconstructing minimizes the total squared reconstruction error among all rank‑k linear projections, with

the sum of the discarded eigenvalues — a direct corollary of the Eckart–Young theorem (A1.99) applied to the data matrix.

Given Σ = UΛU^T ≻ 0, the matrix square root Σ^1/2 = UΛ^1/2U^T and inverse square root Σ^−1/2 = UΛ^−1/2U^T are well‑defined symmetric PD matrices satisfying Σ^1/2Σ^1/2 = Σ. The whitening transform

produces a random vector z with identity covariance: Cov(z) = I_d — uncorrelated, unit‑variance coordinates.

Given a PD covariance matrix Σ, the Mahalanobis distance between x and a reference point μ is

It equals the ordinary Euclidean distance after the whitening transform of A1.117: d_Σ(x,μ) = |Σ^−1/2(x−μ)|. It accounts for the scale and correlation of each coordinate, unlike the raw Euclidean norm.

For A ≻ 0, the function |x|_A = √(x^TAx) defines a genuine norm on ℝ^d (the "A‑norm" or "energy norm"), since positive definiteness of A supplies exactly the positive‑definiteness axiom required of a norm, and the triangle inequality follows from Cauchy–Schwarz applied to the inner product ⟨x,y⟩_A = x^TAy.

Given X ∈ M_n,d and y ∈ ℝⁿ, the least squares problem seeks

Geometrically (A1.77), this asks for the point Xβ in im(X) closest to y — i.e., Xβ̂ is the orthogonal projection of y onto the column space of X.

• Xthe design (feature) matrix.
• β̂the least squares estimate.

The least squares objective f(β) = |Xβ − y|² is convex (its Hessian is 2X^TX ⪰ 0, A1.111), and setting the gradient (A1.105) to zero gives the normal equations:

Proof. ∇_β|Xβ−y|² = ∇_β(β^TX^TXβ − 2y^TXβ + y^Ty) = 2X^TXβ − 2X^Ty; setting to 0 gives the claim. Since f is convex, any solution of the normal equations is a global minimizer. ∎

If X^TX is invertible — equivalently (A1.58), if X has full column rank (its columns/features are linearly independent) — the least squares solution is unique:

If X^TX is singular (e.g., more features than samples, or collinear features, A1.28), infinitely many minimizers exist; the pseudoinverse X⁺ (A1.101) selects the minimum‑norm one among them.

Ridge regression modifies the least‑squares objective by adding a penalty on the norm of β:

Setting the gradient to zero gives (X^TX + γI)β = X^Ty, so

Crucially, X^TX + γI ≻ 0 for any γ > 0, regardless of the rank of X (since adding γI shifts every eigenvalue of the PSD matrix X^TX up by γ, by A1.93) — so the ridge solution is always unique, even when ordinary least squares is not.

Using the SVD X = UΣV^T, the ridge fitted values can be written

Each principal direction of X is shrunk by the factor σ_i²/(σ_i²+γ) ∈ (0,1) — directions with small singular values (i.e., noisy or poorly‑determined directions) are shrunk the most.

For f(x) = (1/2)x^TAx − b^Tx with A ≻ 0 (so ∇f(x) = Ax − b), the gradient descent update with step size η is

Writing the error e_k = x_k − x⋆ in the eigenbasis of A, each coordinate evolves independently as e_k+1⁽ⁱ⁾ = (1 − ηλ_i)e_k⁽ⁱ⁾ — a direct application of A1.90.

Gradient descent on the quadratic of A1.125 converges (x_k → x⋆) if and only if |1 − ηλ_i| < 1 for every eigenvalue λ_i of A, i.e., 0 < η < 2/λ_max. The optimal step size η⋆ = 2/(λ_min + λ_max) gives an asymptotic convergence rate governed by

Given two classes with means μ₁, μ₂ and a shared (pooled) within‑class covariance Σ_W ≻ 0, Fisher's linear discriminant seeks the direction w maximizing the ratio of between‑class to within‑class variance:

This is a generalized eigenvalue problem; the closed‑form solution follows from a whitening change of variables (A1.117) that reduces it to an ordinary Rayleigh quotient maximization (A1.94).

For symmetric A and symmetric PD B, the generalized eigenvalue problem seeks (λ, v) with v ≠ 0 satisfying

Substituting v = B^−1/2u (A1.117) transforms this into the ordinary eigenvalue problem (B^−1/2AB^−1/2)u = λu, so all guarantees of the spectral theorem (A1.91) — real eigenvalues, orthogonal (in the B‑inner‑product) eigenvectors — carry over.

For compatible matrices A, B and a vector x:

Proof. The first is immediate from the definition of the operator norm (A1.17). For the second, |ABx| ≤ |A|_op|Bx| ≤ |A|_op|B|_op|x|, and taking the max over unit x gives the claim. ∎

The chain of results above forms a single continuous argument: vector spaces and bases (A1.20–A1.41) give us coordinates; linear maps and matrices (A1.39–A1.58) give us the operations of models; determinants (A1.59–A1.67) certify when those operations are reversible; inner products and orthogonality (A1.68–A1.80) give us geometry — angle, distance, projection; eigenvalues and the spectral theorem (A1.81–A1.95) diagonalize symmetric structure wherever it appears (covariance, Hessians, kernels); the SVD (A1.96–A1.101) extends that diagonalization to arbitrary matrices and underlies optimal compression; and finally, quadratic forms, gradients, and Hessians (A1.102–A1.129) connect all of the above to the calculus of optimization — gradient descent, Newton's method, least squares, ridge regression, and PCA are, in the end, applications of the spectral theorem and the variational characterization of eigenvalues to specific quadratic objectives.