Linear Algebra

The mathematics of data structures and transformations.

Vectors

Definition

An ordered list of numbers:

\[\mathbf{v} = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix} \in \mathbb{R}^n\]

Operations

Operation Definition

Addition

\(\mathbf{u} + \mathbf{v} = (u_1 + v_1, \ldots, u_n + v_n)\)

Scalar multiplication

\(c\mathbf{v} = (cv_1, \ldots, cv_n)\)

Dot product

\(\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^{n} u_i v_i\)

Norm

stem:[

\mathbf{v}

= \sqrt{\mathbf{v} \cdot \mathbf{v}}]

Orthogonality

Vectors are orthogonal if \(\mathbf{u} \cdot \mathbf{v} = 0\).

Matrices

Definition

An m × n array of numbers:

\[A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}\]

Matrix Multiplication

For A (m × n) and B (n × p):

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

Complexity: \(O(mnp)\), or \(O(n^3)\) for square matrices.

Properties

Property Note

Associative

\((AB)C = A(BC)\)

Distributive

\(A(B + C) = AB + AC\)

NOT commutative

\(AB \neq BA\) in general

Linear Transformations

Matrices represent linear transformations.

2D Transformations

Rotation by angle θ:

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

Scaling:

\[S(s_x, s_y) = \begin{pmatrix} s_x & 0 \\ 0 & s_y \end{pmatrix}\]

3D Graphics

Homogeneous coordinates enable translation as matrix multiplication:

\[\begin{pmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} = \begin{pmatrix} x + t_x \\ y + t_y \\ z + t_z \\ 1 \end{pmatrix}\]

Eigenvalues and Eigenvectors

Definition

For matrix A, if:

\[A\mathbf{v} = \lambda\mathbf{v}\]

Then λ is an eigenvalue and v is an eigenvector.

Characteristic Polynomial

Eigenvalues are roots of:

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

Applications

  • Principal Component Analysis (PCA): Eigenvectors of covariance matrix

  • PageRank: Dominant eigenvector of link matrix

  • Vibration modes: Eigenvalues = natural frequencies

Singular Value Decomposition (SVD)

Any matrix A can be decomposed:

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

Where:

  • U: Left singular vectors (orthonormal)

  • Σ: Diagonal matrix of singular values

  • V: Right singular vectors (orthonormal)

Applications

  • Dimensionality reduction: Keep top k singular values

  • Noise reduction: Truncate small singular values

  • Recommendation systems: Matrix factorization

  • Image compression: Low-rank approximation

Systems of Linear Equations

Matrix Form

\[A\mathbf{x} = \mathbf{b}\]

Gaussian Elimination

Complexity: \(O(n^3)\)

LU Decomposition

Factor A = LU, then solve:

  1. Ly = b (forward substitution)

  2. Ux = y (back substitution)

Useful when solving multiple systems with same A.

Determinants

2×2

\[\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\]

Properties

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

  • \(\det(A^{-1}) = 1/\det(A)\)

  • \(\det(A) = 0 \Leftrightarrow\) A is singular

Geometric Interpretation

Absolute value of determinant = volume scaling factor.

Machine Learning Applications

Neural Networks

Each layer performs:

\[\mathbf{y} = \sigma(W\mathbf{x} + \mathbf{b})\]

Gradient computation via chain rule on matrix operations.

Covariance Matrix

For data matrix X (n samples × d features):

\[\Sigma = \frac{1}{n-1} X^T X\]

Used in PCA, Gaussian models, feature analysis.

Related