Computational Linear Algebra

A comprehensive formula sheet for computational methods and algorithms

Matrix Operations

Addition:

\[(A + B)_{ij} = a_{ij} + b_{ij}\]

Scalar Multiplication:

\[(cA)_{ij} = c \cdot a_{ij}\]

Matrix Multiplication:

\[(AB)_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}\]

Properties:

  • Associative: \((AB)C = A(BC)\)
  • Distributive: \(A(B+C) = AB + AC\)
  • Not commutative: \(AB \neq BA\)

Special Matrices

Identity Matrix:

\[I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad AI = A\]

Diagonal Matrix:

\[D = \text{diag}(d_1, d_2, ..., d_n)\]

Triangular:

  • Upper: entries below diagonal = 0
  • Lower: entries above diagonal = 0

Symmetric:

\[A = A^T\]

Transpose & Properties

Definition:

\[(A^T)_{ij} = a_{ji}\]

Properties:

  • \((A^T)^T = A\)
  • \((A + B)^T = A^T + B^T\)
  • \((cA)^T = c(A^T)\)
  • \((AB)^T = B^T A^T\)

Trace:

\[\text{tr}(A) = \sum_{i=1}^{n} a_{ii}\]

Matrix Inverse

Definition:

\[AA^{-1} = A^{-1}A = I\]

2×2 Inverse:

\[A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \quad A^{-1} = \frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}\]

Properties:

  • \((A^{-1})^{-1} = A\)
  • \((AB)^{-1} = B^{-1}A^{-1}\)
  • \((A^T)^{-1} = (A^{-1})^T\)

Determinants

2×2 Determinant:

\[\det(A) = \begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad - bc\]

3×3 Determinant (Rule of Sarrus):

\[\det(A) = a_{11}(a_{22}a_{33} - a_{23}a_{32}) - a_{12}(a_{21}a_{33} - a_{23}a_{31}) + a_{13}(a_{21}a_{32} - a_{22}a_{31})\]

Properties:

  • \(\det(AB) = \det(A)\det(B)\)
  • \(\det(A^T) = \det(A)\)
  • \(\det(A^{-1}) = \frac{1}{\det(A)}\)
  • \(\det(cA) = c^n\det(A)\)

Cofactor Expansion

Expansion along row i:

\[\det(A) = \sum_{j=1}^{n} a_{ij}C_{ij}\]

Cofactor:

\[C_{ij} = (-1)^{i+j}M_{ij}\]

where \(M_{ij}\) is the minor (determinant of submatrix).

Adjugate Matrix:

\[A^{-1} = \frac{1}{\det(A)}\text{adj}(A)\]

Gaussian Elimination

Row Operations:

  • Swap two rows
  • Multiply row by nonzero scalar
  • Add multiple of one row to another

Row Echelon Form:

  • All zero rows at bottom
  • Leading entry (pivot) in each row is right of pivot above
  • Leading entry is 1 (reduced row echelon form)

Back Substitution:

Solve \(Ux = b\) where U is upper triangular.

Systems of Linear Equations

Matrix Form:

\[Ax = b\]

where A is coefficient matrix, x is variables, b is constants.

Solution (if \(\det(A) \neq 0\)):

\[x = A^{-1}b\]

Consistency:

  • Unique solution if \(\text{rank}(A) = \text{rank}([A|b]) = n\)
  • Infinite solutions if \(\text{rank}(A) = \text{rank}([A|b]) < n\)
  • No solution if \(\text{rank}(A) < \text{rank}([A|b])\)

LU Decomposition

Factorization:

\[A = LU\]

where L is lower triangular, U is upper triangular.

Solving Ax = b:

  1. Solve \(Ly = b\) by forward substitution
  2. Solve \(Ux = y\) by back substitution
More efficient than direct inversion for multiple right-hand sides.

Vector Spaces

Span:

Set of all linear combinations of vectors \(v_1, ..., v_k\):

\[\text{span}\{v_1, ..., v_k\} = \{c_1v_1 + ... + c_kv_k : c_i \in \mathbb{R}\}\]

Linear Independence:

\(v_1, ..., v_k\) are linearly independent if:

\[c_1v_1 + ... + c_kv_k = 0 \implies c_1 = ... = c_k = 0\]

Basis: Linearly independent set that spans the space.

Rank & Nullity

Rank: Number of linearly independent rows/columns

\[\text{rank}(A) = \text{dimension of column space}\]

Nullity: Dimension of null space (solution space of \(Ax = 0\))

\[\text{nullity}(A) = \text{dimension of null space}\]

Rank-Nullity Theorem:

\[\text{rank}(A) + \text{nullity}(A) = n\]

where n is the number of columns.

Eigenvalues & Eigenvectors

Definition:

\[Av = \lambda v\]

Characteristic Equation:

\[\det(A - \lambda I) = 0\]

Eigenspace:

\[E_\lambda = \text{null}(A - \lambda I)\]

Trace & Determinant:

  • \(\sum \lambda_i = \text{tr}(A)\)
  • \(\prod \lambda_i = \det(A)\)

Diagonalization

Diagonal Form:

\[A = PDP^{-1}\]

where D is diagonal matrix of eigenvalues, P is matrix of eigenvectors.

Conditions:

  • A must have n linearly independent eigenvectors
  • Symmetric matrices are always diagonalizable

Powers of A:

\[A^k = PD^kP^{-1}\]

Orthogonality

Dot Product:

\[u \cdot v = \sum_{i=1}^{n} u_i v_i = u^T v\]

Orthogonal Vectors:

\[u \perp v \iff u \cdot v = 0\]

Vector Norm:

\[\|v\| = \sqrt{v \cdot v} = \sqrt{\sum_{i=1}^{n} v_i^2}\]

Projection of u onto v:

\[\text{proj}_v(u) = \frac{u \cdot v}{\|v\|^2}v\]

Gram-Schmidt Process

Convert linearly independent vectors to orthonormal basis:

Algorithm:

\[u_1 = v_1\]
\[u_k = v_k - \sum_{j=1}^{k-1} \frac{v_k \cdot u_j}{\|u_j\|^2}u_j\]

Normalization:

\[e_k = \frac{u_k}{\|u_k\|}\]

Result: \(\{e_1, e_2, ..., e_n\}\) is orthonormal basis.

QR Decomposition

Factorization:

\[A = QR\]

where Q has orthonormal columns, R is upper triangular.

Computing QR:

Apply Gram-Schmidt to columns of A.

Solving Least Squares:

\[x = R^{-1}Q^Tb\]
Numerically stable for solving \(Ax = b\)

Singular Value Decomposition (SVD)

Factorization:

\[A = U\Sigma V^T\]

where U, V orthogonal; \(\Sigma\) diagonal with singular values \(\sigma_i \geq 0\).

Computing:

  • Eigenvalues of \(AA^T\) give \(\sigma_i^2\)
  • Eigenvectors of \(AA^T\) give columns of U
  • Eigenvectors of \(A^TA\) give columns of V

Pseudoinverse:

\[A^+ = V\Sigma^+ U^T\]

Least Squares Approximation

Problem: Minimize \(\|Ax - b\|^2\)

Normal Equations:

\[A^TAx = A^Tb\]

Solution:

\[x = (A^TA)^{-1}A^Tb\]

Residual:

\[r = b - Ax\]

Optimal approximation:

\[\hat{b} = \text{proj}_{\text{col}(A)}(b) = A(A^TA)^{-1}A^Tb\]

Markov Chains

Transition Matrix: Columns sum to 1

\[P = \begin{pmatrix} p_{11} & p_{12} \\ p_{21} & p_{22} \end{pmatrix}\]

State at time n:

\[x_n = P^n x_0\]

Stationary Distribution:

\[P\pi = \pi \implies \pi \text{ is eigenvector with } \lambda = 1\]

Properties:

  • All eigenvalues have \(|\lambda| \leq 1\)
  • Always has eigenvalue \(\lambda = 1\)

Rotations & Computer Graphics

2D Rotation (angle θ):

\[R(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}\]

3D Rotation about z-axis:

\[R_z(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix}\]

Homogeneous Coordinates (2D):

\[\begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} = \begin{pmatrix} a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} x \\ y \\ 1 \end{pmatrix}\]

Matrix Norms

Frobenius Norm:

\[\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2} = \sqrt{\text{tr}(A^TA)}\]

Spectral Norm:

\[\|A\|_2 = \sqrt{\lambda_{\max}(A^TA)}\]

Operator Norms:

  • \(\|A\|_1\) = max column sum
  • \(\|A\|_\infty\) = max row sum

Condition Number:

\[\kappa(A) = \|A\| \cdot \|A^{-1}\|\]

Inner Product Spaces

Inner Product: \(\langle u, v \rangle\)

Properties:

  • Symmetric: \(\langle u, v \rangle = \langle v, u \rangle\)
  • Linear: \(\langle au + bw, v \rangle = a\langle u, v \rangle + b\langle w, v \rangle\)
  • Positive: \(\langle u, u \rangle > 0\) for \(u \neq 0\)

Cauchy-Schwarz Inequality:

\[|\langle u, v \rangle| \leq \|u\| \cdot \|v\|\]

Orthogonal Matrices

Definition:

\[Q^TQ = QQ^T = I\]

Equivalently: \(Q^{-1} = Q^T\)

Properties:

  • \(\det(Q) = \pm 1\)
  • \(\|Qx\| = \|x\|\) (preserves length)
  • Eigenvalues have \(|\lambda| = 1\)
  • Columns/rows are orthonormal

Computational Applications

Solving Ax = b: Gaussian elimination, LU decomposition

Least Squares: Normal equations, QR decomposition

Eigenvalue Problems: QR algorithm, power method

Low-Rank Approximation: Truncated SVD

Data Analysis: PCA via eigendecomposition

Image Compression: SVD-based rank reduction