Linear Algebra Essentials

Cheatsheet Content

### Vectors - **Definition:** An ordered list of numbers, e.g., $\vec{v} = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix} \in \mathbb{R}^n$. - **Magnitude (Euclidean Norm):** $|\vec{v}| = ||\vec{v}||_2 = \sqrt{v_1^2 + v_2^2 + \dots + v_n^2}$. - **Vector Addition:** $\vec{u} + \vec{v} = (u_1+v_1, \dots, u_n+v_n)$. - **Scalar Multiplication:** $c\vec{v} = (cv_1, \dots, cv_n)$. - **Dot Product:** $\vec{u} \cdot \vec{v} = \sum_{i=1}^n u_i v_i = ||\vec{u}|| ||\vec{v}|| \cos\theta$. - If $\vec{u} \cdot \vec{v} = 0$, then $\vec{u}$ and $\vec{v}$ are orthogonal. - **Cross Product (only in $\mathbb{R}^3$):** $\vec{a} \times \vec{b} = \begin{pmatrix} a_2b_3 - a_3b_2 \\ a_3b_1 - a_1b_3 \\ a_1b_2 - a_2b_1 \end{pmatrix}$. - Result is orthogonal to both $\vec{a}$ and $\vec{b}$. - Magnitude: $||\vec{a} \times \vec{b}|| = ||\vec{a}|| ||\vec{b}|| \sin\theta$. - **Linear Combination:** A sum of scalar multiples of vectors, $c_1\vec{v}_1 + c_2\vec{v}_2 + \dots + c_k\vec{v}_k$. - **Span:** The set of all possible linear combinations of a set of vectors $\{\vec{v}_1, \dots, \vec{v}_k\}$. - **Linear Independence:** A set of vectors is linearly independent if $c_1\vec{v}_1 + \dots + c_k\vec{v}_k = \vec{0}$ implies $c_1 = \dots = c_k = 0$. ### Matrices - **Definition:** A rectangular array of numbers, $A = [a_{ij}]$, $m \times n$ matrix. - **Matrix Addition:** $A+B$ (element-wise, if dimensions match). - **Scalar Multiplication:** $cA$ (element-wise). - **Matrix Multiplication:** $C = AB$, where $C_{ij} = \sum_k A_{ik}B_{kj}$. - Requires inner dimensions to match: $(m \times n)(n \times p) = (m \times p)$. - Not commutative: $AB \neq BA$ in general. - **Identity Matrix ($I$):** Square matrix with 1s on the diagonal, 0s elsewhere. $AI = IA = A$. - **Transpose ($A^T$):** Rows become columns, columns become rows. $(A^T)_{ij} = A_{ji}$. - Properties: $(A^T)^T = A$, $(A+B)^T = A^T+B^T$, $(AB)^T = B^TA^T$. - **Symmetric Matrix:** $A = A^T$. - **Inverse Matrix ($A^{-1}$):** For a square matrix $A$, if $A^{-1}$ exists, then $AA^{-1} = A^{-1}A = I$. - **Formula for $2 \times 2$:** If $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, then $A^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. - For $A^{-1}$ to exist, $\det(A) \neq 0$. - Properties: $(A^{-1})^{-1} = A$, $(AB)^{-1} = B^{-1}A^{-1}$, $(A^T)^{-1} = (A^{-1})^T$. ### Determinants - **Definition:** A scalar value associated with a square matrix. - **$2 \times 2$ Matrix:** $\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad-bc$. - **$3 \times 3$ Matrix (Sarrus' Rule):** $$\det \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} = a(ei-fh) - b(di-fg) + c(dh-eg)$$ - **Cofactor Expansion:** $\det(A) = \sum_{j=1}^n (-1)^{i+j} a_{ij} M_{ij}$ (along row $i$) or $\sum_{i=1}^n (-1)^{i+j} a_{ij} M_{ij}$ (along column $j$). - $M_{ij}$ is the determinant of the submatrix formed by removing row $i$ and column $j$. - **Properties:** - $\det(A) = \det(A^T)$. - $\det(AB) = \det(A)\det(B)$. - $\det(A^{-1}) = \frac{1}{\det(A)}$. - If a row/column is all zeros, $\det(A)=0$. - If two rows/columns are identical, $\det(A)=0$. - Swapping two rows/columns changes sign of determinant. - Multiplying a row/column by $c$ multiplies $\det(A)$ by $c$. - Adding a multiple of one row/column to another does not change $\det(A)$. - $\det(A) \neq 0 \iff A$ is invertible $\iff$ columns (or rows) are linearly independent. ### Systems of Linear Equations - **General Form:** $$a_{11}x_1 + \dots + a_{1n}x_n = b_1$$ $$\vdots$$ $$a_{m1}x_1 + \dots + a_{mn}x_n = b_m$$ - **Matrix Form:** $A\vec{x} = \vec{b}$, where $A$ is the coefficient matrix, $\vec{x}$ is the variable vector, $\vec{b}$ is the constant vector. - **Augmented Matrix:** $[A|\vec{b}]$. - **Solving Methods:** - **Gaussian Elimination:** Use elementary row operations (swap rows, multiply row by scalar, add multiple of one row to another) to transform $[A|\vec{b}]$ into row echelon form or reduced row echelon form. - **Cramer's Rule:** For $A\vec{x}=\vec{b}$ with $n$ equations and $n$ unknowns, if $\det(A) \neq 0$, then $x_i = \frac{\det(A_i)}{\det(A)}$, where $A_i$ is $A$ with column $i$ replaced by $\vec{b}$. - **Matrix Inverse:** If $A$ is invertible, $\vec{x} = A^{-1}\vec{b}$. - **Number of Solutions:** - **Unique Solution:** If $\det(A) \neq 0$ (for square $A$), or if reduced row echelon form has a pivot in every column of $A$. - **No Solution:** If reduced row echelon form has a row $[0 \ 0 \ \dots \ 0 \ | \ 1]$. - **Infinitely Many Solutions:** If not unique and not no solution (i.e., free variables). ### Vector Spaces & Subspaces - **Vector Space:** A set $V$ with operations vector addition and scalar multiplication satisfying 10 axioms (closure, commutativity, associativity, zero vector, additive inverse, distributive properties, identity for scalar multiplication). - **Subspace:** A subset $W$ of a vector space $V$ that is itself a vector space under the same operations. - **Test for Subspace:** 1. $\vec{0} \in W$. 2. If $\vec{u}, \vec{v} \in W$, then $\vec{u}+\vec{v} \in W$ (closure under addition). 3. If $\vec{u} \in W$ and $c$ is a scalar, then $c\vec{u} \in W$ (closure under scalar multiplication). - **Column Space (Col $A$):** The span of the column vectors of $A$. It is the set of all $\vec{b}$ for which $A\vec{x}=\vec{b}$ has a solution. - **Null Space (Nul $A$):** The set of all solutions to $A\vec{x}=\vec{0}$. - **Row Space (Row $A$):** The span of the row vectors of $A$. - **Basis:** A linearly independent set of vectors that spans the vector space (or subspace). - **Dimension (dim):** The number of vectors in a basis for the space. - **Rank:** $\mathrm{rank}(A) = \dim(\mathrm{Col} A) = \dim(\mathrm{Row} A)$. This is the number of pivot positions in the row echelon form of $A$. - **Nullity:** $\mathrm{nullity}(A) = \dim(\mathrm{Nul} A)$. This is the number of free variables. - **Rank-Nullity Theorem:** For an $m \times n$ matrix $A$, $\mathrm{rank}(A) + \mathrm{nullity}(A) = n$. ### Eigenvalues and Eigenvectors - **Definition:** For a square matrix $A$, an eigenvector $\vec{v} \neq \vec{0}$ is a vector such that $A\vec{v} = \lambda\vec{v}$ for some scalar $\lambda$. The scalar $\lambda$ is called an eigenvalue. - **Finding Eigenvalues:** Solve the characteristic equation $\det(A - \lambda I) = 0$. The roots $\lambda$ are the eigenvalues. - **Finding Eigenvectors:** For each eigenvalue $\lambda$, solve the homogeneous system $(A - \lambda I)\vec{v} = \vec{0}$. The non-trivial solutions are the eigenvectors corresponding to $\lambda$. The set of all such solutions forms the eigenspace for $\lambda$. - **Eigenspace:** The null space of $(A - \lambda I)$. - **Properties:** - Eigenvectors corresponding to distinct eigenvalues are linearly independent. - If $A$ is symmetric, its eigenvalues are real and eigenvectors corresponding to distinct eigenvalues are orthogonal. - The product of eigenvalues equals $\det(A)$. - The sum of eigenvalues equals the trace of $A$ (sum of diagonal elements). - **Diagonalization:** A square matrix $A$ is diagonalizable if there exists an invertible matrix $P$ and a diagonal matrix $D$ such that $A = PDP^{-1}$. - If $A$ has $n$ linearly independent eigenvectors, then $A$ is diagonalizable. - $P$ is the matrix whose columns are the linearly independent eigenvectors of $A$. - $D$ is a diagonal matrix whose diagonal entries are the corresponding eigenvalues. - If $A$ is diagonalizable, $A^k = PD^kP^{-1}$. ### Orthogonal Matrices - **Definition:** A square matrix $Q$ is orthogonal if $Q^TQ = QQ^T = I$. - **Properties:** - $Q^{-1} = Q^T$. - Columns (and rows) of $Q$ form an orthonormal basis (unit vectors that are mutually orthogonal). - Preserves dot products: $(Q\vec{x}) \cdot (Q\vec{y}) = \vec{x} \cdot \vec{y}$. - Preserves vector lengths: $||Q\vec{x}|| = ||\vec{x}||$. - $\det(Q) = \pm 1$. ### Singular Value Decomposition (SVD) - **Definition:** Any $m \times n$ matrix $A$ can be factored as $A = U\Sigma V^T$, where: - $U$ is an $m \times m$ orthogonal matrix (columns are left singular vectors). - $V$ is an $n \times n$ orthogonal matrix (columns are right singular vectors). - $\Sigma$ is an $m \times n$ diagonal matrix with non-negative singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$ on the main diagonal, and zeros elsewhere. $r = \mathrm{rank}(A)$. - **Singular Values:** The square roots of the eigenvalues of $A^TA$ (or $AA^T$). - **Applications:** Data compression, dimensionality reduction (PCA), solving least squares problems, pseudoinverse. ### Least Squares - **Problem:** Find $\vec{x}$ that minimizes $||A\vec{x} - \vec{b}||^2$ when $A\vec{x} = \vec{b}$ has no exact solution. - **Normal Equations:** The solution $\hat{\vec{x}}$ satisfies $A^TA\hat{\vec{x}} = A^T\vec{b}$. - **Solution:** If $A^TA$ is invertible, then $\hat{\vec{x}} = (A^TA)^{-1}A^T\vec{b}$. - **Geometric Interpretation:** $\hat{\vec{x}}$ makes $A\hat{\vec{x}}$ the projection of $\vec{b}$ onto the column space of $A$. The residual vector $\vec{b} - A\hat{\vec{x}}$ is orthogonal to $\mathrm{Col} A$. ### Quadratic Forms - **Definition:** A function $Q(\vec{x}) = \vec{x}^TA\vec{x}$ where $A$ is a symmetric matrix. - **Example for $\mathbb{R}^2$:** If $A = \begin{pmatrix} a & b/2 \\ b/2 & c \end{pmatrix}$, then $Q(x_1, x_2) = ax_1^2 + bx_1x_2 + cx_2^2$. - **Principal Axes Theorem:** If $A$ is a symmetric matrix, then there is an orthogonal change of variable $\vec{x} = P\vec{y}$ that transforms the quadratic form $\vec{x}^TA\vec{x}$ into a quadratic form $\vec{y}^TD\vec{y}$ with no cross-product terms. - $P$ is an orthogonal matrix whose columns are the orthonormal eigenvectors of $A$. - $D$ is a diagonal matrix with the eigenvalues of $A$ on the diagonal. - **Classification:** - Positive Definite: $Q(\vec{x}) > 0$ for all $\vec{x} \neq \vec{0}$ (all eigenvalues $>0$). - Negative Definite: $Q(\vec{x}) 0$, some $