Linear Algebra

Linear algebra is the branch of mathematics concerned with vector spaces, linear mappings, and systems of linear equations. It is foundational to virtually every area of applied mathematics, data science, engineering, and physics.

1. Vectors¶

A vector $\mathbf{v} \in \mathbb{R}^n$ is an ordered $n$-tuple of real numbers.

1.1 Operations¶

For $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ and scalar $c$:

Dot product:

where $\theta$ is the angle between the vectors.

Euclidean norm:

Cross product (only in $\mathbb{R}^3$):

The magnitude $\|\mathbf{u} \times \mathbf{v}\| = \|\mathbf{u}\|\,\|\mathbf{v}\|\sin\theta$, equal to the area of the parallelogram spanned by $\mathbf{u}$ and $\mathbf{v}$.

1.2 Linear Independence¶

Vectors $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ are linearly independent if the only solution to

is $c_1 = c_2 = \cdots = c_k = 0$. Otherwise they are linearly dependent.

The span of a set of vectors is the set of all linear combinations. A basis of a vector space is a linearly independent spanning set; its cardinality is the dimension of the space.

2. Matrices¶

An $m \times n$ matrix $A$ has $m$ rows and $n$ columns:

2.1 Basic Operations¶

• Addition: $(A + B)_{ij} = a_{ij} + b_{ij}$ (same dimensions required)

• Scalar multiplication: $(cA)_{ij} = c\,a_{ij}$

• Transpose: $(A^T)_{ij} = a_{ji}$

• Matrix multiplication: $(AB)_{ij} = \displaystyle\sum_{k=1}^n a_{ik}b_{kj}$ (requires $A$ is $m\times n$, $B$ is $n\times p$)

2.2 Special Matrices¶

3. Determinants¶

The determinant $\det(A)$ (or $|A|$) is a scalar associated with a square matrix.

$2 \times 2$ case:

$3 \times 3$ case (cofactor expansion along the first row):

Key properties¶

• $\det(AB) = \det(A)\det(B)$

• $\det(A^T) = \det(A)$

• $\det(A^{-1}) = 1/\det(A)$ (when $A$ is invertible)

• Swapping two rows negates the determinant

• If any row is a linear combination of the others, $\det(A) = 0$

A matrix $A$ is invertible (nonsingular) if and only if $\det(A) \neq 0$. The inverse is then:

where $\operatorname{adj}(A)$ is the transpose of the cofactor matrix.

4. Systems of Linear Equations¶

A system of $m$ equations in $n$ unknowns can be written as $A\mathbf{x} = \mathbf{b}$.

4.1 Gaussian Elimination¶

Form the augmented matrix $[A \mid \mathbf{b}]$ and reduce to row-echelon form using:

1. Swap two rows

2. Multiply a row by a nonzero scalar

3. Add a multiple of one row to another

Continue to reduced row-echelon form (RREF) for a unique representation.

4.2 Solution Types¶

• Unique solution: $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) = n$

• Infinitely many solutions: $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) < n$

• No solution: $\operatorname{rank}(A) < \operatorname{rank}([A|\mathbf{b}])$

4.3 Cramer’s Rule ($n \times n$, $\det(A) \neq 0$)¶

where $A_i$ is $A$ with its $i$-th column replaced by $\mathbf{b}$.

4.4 LU Decomposition¶

For an $n \times n$ matrix: $A = LU$ where $L$ is lower triangular with unit diagonal and $U$ is upper triangular. Solve by forward substitution ($L\mathbf{y} = \mathbf{b}$) then back substitution ($U\mathbf{x} = \mathbf{y}$). This is the basis for most numerical linear solvers.

5. Eigenvalues and Eigenvectors¶

A scalar $\lambda$ and nonzero vector $\mathbf{v}$ satisfy the eigenvector equation:

$\lambda$ is an eigenvalue of $A$ and $\mathbf{v}$ is the corresponding eigenvector.

5.1 Characteristic Equation¶

Eigenvalues are found by solving:

The left side is the characteristic polynomial of degree $n$, so an $n \times n$ matrix has exactly $n$ eigenvalues (counted with multiplicity, possibly complex).

5.2 Properties¶

• $\operatorname{tr}(A) = \displaystyle\sum_{i=1}^n \lambda_i$

• $\det(A) = \displaystyle\prod_{i=1}^n \lambda_i$

• If $A$ is real symmetric, all eigenvalues are real and eigenvectors of distinct eigenvalues are orthogonal

5.3 Diagonalization¶

If $A$ has $n$ linearly independent eigenvectors forming the columns of $P$:

where $\Lambda = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)$. This gives $A^k = P \Lambda^k P^{-1}$, which is efficient for large powers.

6. Vector Spaces and Subspaces¶

A vector space over $\mathbb{R}$ is a set $V$ closed under addition and scalar multiplication and satisfying the eight axioms (associativity, commutativity, identity, inverses, distributivity).

Important subspaces associated with an $m \times n$ matrix $A$:

Rank-Nullity Theorem: $\operatorname{rank}(A) + \operatorname{nullity}(A) = n$.

7. Inner Product Spaces and Orthogonality¶

An inner product on $V$ generalises the dot product. The standard inner product on $\mathbb{R}^n$ is:

Gram–Schmidt Orthogonalisation¶

Given a basis $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$, produce an orthonormal basis $\{\mathbf{e}_1, \ldots, \mathbf{e}_k\}$:

then $\mathbf{e}_j = \mathbf{u}_j / \|\mathbf{u}_j\|$.

QR Decomposition¶

Any $m \times n$ matrix $A$ (with $m \geq n$ and full column rank) can be written as $A = QR$ where $Q$ has orthonormal columns and $R$ is upper triangular. This is useful for solving least-squares problems.

8. Singular Value Decomposition (SVD)¶

Every $m \times n$ real matrix $A$ can be decomposed as:

where:

• $U$ is $m \times m$ orthogonal (left singular vectors)

• $\Sigma$ is $m \times n$ diagonal with non-negative entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$ (singular values)

• $V$ is $n \times n$ orthogonal (right singular vectors)

The SVD generalises the eigendecomposition to non-square matrices and is widely used for dimensionality reduction, pseudoinverse computation, and data compression.

The rank of $A$ equals the number of nonzero singular values. The pseudoinverse (Moore–Penrose) is $A^+ = V \Sigma^+ U^T$.

9. Linear Transformations¶

A function $T: V \to W$ between vector spaces is a linear transformation if for all $\mathbf{u}, \mathbf{v} \in V$ and scalar $c$:

Every linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$ can be represented by an $m \times n$ matrix $A$ such that $T(\mathbf{x}) = A\mathbf{x}$.

9.1 Kernel and Image¶

• Kernel (null space): $\ker(T) = \{\mathbf{v} \in V : T(\mathbf{v}) = \mathbf{0}\}$

• Image (range): $\operatorname{im}(T) = \{T(\mathbf{v}) : \mathbf{v} \in V\}$

Rank-Nullity Theorem for Transformations: $\dim(\ker T) + \dim(\operatorname{im} T) = \dim V$.

9.2 Common Transformations in $\mathbb{R}^2$¶

9.3 Change of Basis¶

If $P$ is the change-of-basis matrix from basis $\mathcal{B}'$ to $\mathcal{B}$, then the matrix of $T$ in the new basis is:

Two matrices are similar ($A \sim B$) if $B = P^{-1}AP$ for some invertible $P$. Similar matrices represent the same linear transformation in different bases and share the same eigenvalues, determinant, and trace.

10. Positive Definite Matrices¶

A real symmetric $n \times n$ matrix $A$ is positive definite if:

Equivalent Conditions¶

Any one of these implies the rest:

• All eigenvalues of $A$ are strictly positive

• All leading principal minors are positive (Sylvester’s criterion)

• There exists a matrix $R$ with $A = R^T R$ (Cholesky decomposition)

• All pivots (in Gaussian elimination without row swaps) are positive

Positive semi-definite allows $\mathbf{x}^T A \mathbf{x} \geq 0$ and eigenvalues $\geq 0$.

Cholesky Decomposition¶

For positive definite $A$, there exists a unique lower-triangular matrix $L$ with positive diagonal entries such that:

This is roughly twice as efficient as LU decomposition and is used extensively in numerical optimization, statistics, and simulation.

11. Matrix Norms and Condition Numbers¶

11.1 Vector Norms¶

The general $p$-norm:

Special cases: $\|\mathbf{x}\|_1$ (Manhattan), $\|\mathbf{x}\|_2$ (Euclidean), $\|\mathbf{x}\|_\infty = \max_i |x_i|$ (max norm).

11.2 Induced Matrix Norms¶

The operator norm induced by a vector norm:

• $\|A\|_2 = \sigma_1$ (largest singular value)

• $\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2} = \sqrt{\operatorname{tr}(A^T A)}$ (Frobenius norm)

11.3 Condition Number¶

A large condition number means the system $A\mathbf{x} = \mathbf{b}$ is ill-conditioned: small perturbations in $\mathbf{b}$ cause large changes in $\mathbf{x}$.

12. Applications¶

12.1 Least Squares¶

Given an overdetermined system $A\mathbf{x} \approx \mathbf{b}$ ($m > n$), the least-squares solution minimises $\|A\mathbf{x} - \mathbf{b}\|_2^2$:

This is the foundation of linear regression. Numerically, it is better solved via QR or SVD.

12.2 Principal Component Analysis (PCA)¶

Given data matrix $X$ ($n$ samples, $p$ features), centred so each column has mean zero:

1. Compute the covariance matrix $C = \frac{1}{n-1} X^T X$

2. Find eigenvalues $\lambda_1 \geq \cdots \geq \lambda_p$ and eigenvectors of $C$

3. Project data onto the top $k$ eigenvectors for dimensionality reduction

The fraction of variance captured by the first $k$ components is $\sum_{i=1}^k \lambda_i \big/ \sum_{i=1}^p \lambda_i$.

12.3 Markov Chains¶

A Markov chain with $n$ states is described by a transition matrix $P$ where $P_{ij}$ is the probability of moving from state $i$ to state $j$. The columns (or rows, by convention) sum to 1.

The steady-state distribution $\boldsymbol{\pi}$ satisfies $P^T \boldsymbol{\pi} = \boldsymbol{\pi}$, i.e., it is an eigenvector of $P^T$ for eigenvalue 1.

12.4 Graph Theory¶

The adjacency matrix $A$ of a graph with $n$ vertices has $A_{ij} = 1$ if vertices $i$ and $j$ are connected. The Laplacian $L = D - A$ (where $D$ is the diagonal degree matrix) encodes spectral properties:

• The number of zero eigenvalues of $L$ equals the number of connected components

• The second-smallest eigenvalue (Fiedler value) measures connectivity and is used in spectral clustering