Linear Algebra

Elements

Linear algebra is the study of vectors and the transformations that act on them. Its two primitive objects:

• Vector — an ordered list of numbers (components) corresponding to directions in a coordinate system; an element of a vector space.
• Matrix — the representation of a linear transformation: a function $T : V \to W$ that respects addition and scalar multiplication.

The key ideal forms:

• Vector space — the abstract structure: a set closed under addition and scalar multiplication, with a zero vector and additive inverses.
• Basis — a minimal spanning set of linearly independent vectors; every vector in the space has a unique expression as a linear combination of basis vectors.
• Eigenvalue / eigenvector — a scalar $\lambda$ and vector $\mathbf{v}$ such that $A\mathbf{v} = \lambda\mathbf{v}$; the transformation’s invariant directions, its intrinsic form.

Special matrices

The identity matrix $I$ (fixed point of multiplication), the inverse $A^{-1}$ (restores equilibrium), and the zero matrix are the structural poles of the matrix space.

Axiomatic Structure

A vector space over a field $\mathbb{F}$ is defined by eight axioms — closure, commutativity, associativity, identity, inverse, and three distributive laws. Everything else is proven from these:

Core theorems

Rank-Nullity Theorem: for a linear map $T : V \to W$,

$\dim(\ker T) + \dim(\operatorname{im} T) = \dim(V)$

This is a fundamental conservation law: the dimensions lost to the kernel are exactly recovered by the image.

Invertibility criterion: $T$ is invertible $\iff$ $\ker T = \{0\}$ $\iff$ $\det(A) \neq 0$.

Spectral Theorem: every real symmetric matrix has a complete orthonormal basis of eigenvectors. Its eigenvalues are real — the transformation is as “clean” as possible.

Definitions

A vector is a linear combination $\alpha_1 \mathbf{v}_1 + \cdots + \alpha_k \mathbf{v}_k$. Vectors are linearly independent if no such combination with nonzero coefficients equals the zero vector. The span of a set is the smallest subspace containing it.

Procedures

Gaussian Elimination

The master procedure for solving $A\mathbf{x} = \mathbf{b}$:

1. Form the augmented matrix $[A \mid \mathbf{b}]$.
2. Apply row operations to reach row echelon form (upper triangular).
3. Back-substitute from the last equation upward.

Cost: $O(n^3)$. Continued to reduced row echelon form (RREF) gives the complete solution set including the null space.

Matrix Factorizations

Eigenvalue Problem

Solve $\det(A - \lambda I) = 0$ (the characteristic polynomial) for $\lambda$, then find eigenvectors from $(A - \lambda I)\mathbf{v} = 0$. The Gram-Schmidt process orthonormalizes a spanning set for use in QR and projections.

Linear Algebra as a System

The vector space is a closed system: vectors (elements) acted on by linear transformations (operations) yield more vectors. The dynamics are entirely determined by the transformation.

• Identity matrix $I$ — the fixed point; the transformation that changes nothing.
• Inverse $A^{-1}$ — the restoring operation; $A^{-1}A = I$ is the equilibrium condition.
• Eigendecomposition — reveals the system’s invariant directions: eigenvectors are the stable axes, eigenvalues are the rates of stretching along each.

For a system $\mathbf{x}_{t+1} = A\mathbf{x}_t$:

• If $|\lambda_i| < 1$ for all eigenvalues, the system converges to zero (stable).
• If $|\lambda_i| > 1$ for some eigenvalue, the system diverges (unstable).
• The long-run behavior is dominated by the dominant eigenvector — the direction associated with the largest $|\lambda|$.

This is the systems lens on matrix iteration: the eigenstructure is the system’s equilibrium topology.

Computation Under Constraint

The engineering lens treats linear algebra as a tool to be deployed reliably on finite machines.

Least-squares solves overdetermined systems ($m > n$): minimize $\|A\mathbf{x} - \mathbf{b}\|^2$ via the normal equations or, more stably, via QR decomposition. This is the computational core of regression.

SVD-based compression (PCA): truncate $A \approx U_k \Sigma_k V_k^\top$ to retain only the top $k$ singular values. This is the best rank-$k$ approximation in the Frobenius and spectral norms.

Numerical stability — the condition number $\kappa(A) = \sigma_{\max}/\sigma_{\min}$ measures sensitivity: a small residual does not guarantee a small error in $\mathbf{x}$ when $\kappa$ is large. Ill-conditioned matrices amplify floating-point errors; Cholesky and QR are preferred over direct inversion for this reason.

Key objectives:

• Solve least-squares problems with maximum stability (use QR, not normal equations directly).
• Compress with minimal information loss (SVD truncation).
• Control condition number to bound numerical error.