Linear algebra - Matrices Linear Systems and Determinants

Matrices and Linear Systems: A Foundation for Linear Algebra Introduction Matrices are one of the most powerful tools in linear algebra. They provide a concrete way to represent abstract linear maps and vector spaces, transforming geometric intuition into computational algorithms. In this guide, we'll explore how matrices encode vector transformations, how we solve systems of linear equations using matrices, and how the determinant tells us fundamental properties of these transformations. The journey from abstract linear algebra to practical computation relies entirely on the insights in this section. Part 1: Matrices and Vector Representation Why Matrices Represent Vectors and Linear Maps When we have a finite-dimensional vector space, we need a way to work with its vectors concretely. A basis gives us this concrete representation. Once we fix a basis, every vector in the space can be uniquely written as a linear combination of basis vectors. The coordinates of a vector relative to this basis are the coefficients in this linear combination. These coordinates are naturally organized into a column matrix (or column vector): a matrix with one column and $n$ rows, where $n$ is the dimension of the space. Example: In $\mathbb{R}^3$ with the standard basis $\{(1,0,0), (0,1,0), (0,0,1)\}$, the vector $(5, -2, 3)$ is represented as the column matrix: $$\begin{bmatrix} 5 \\ -2 \\ 3 \end{bmatrix}$$ Representing Linear Maps as Matrices Now here's the key insight: a linear map is completely determined by where it sends the basis vectors. Why? Because any vector is a linear combination of basis vectors, and the linearity of the map tells us exactly how to compute where that vector goes. To represent a linear map $T: V \to W$ as a matrix: Take each basis vector $\mathbf{e}i$ of the domain $V$ Compute $T(\mathbf{e}i)$ and express it as coordinates in the basis of $W$ Write these coordinate vectors as the columns of a matrix Example: Consider the linear map $T: \mathbb{R}^2 \to \mathbb{R}^2$ that rotates vectors counterclockwise by 90°. Using the standard basis: $T\left(\begin{bmatrix} 1 \\ 0 \end{bmatrix}\right) = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ $T\left(\begin{bmatrix} 0 \\ 1 \end{bmatrix}\right) = \begin{bmatrix} -1 \\ 0 \end{bmatrix}$ So the matrix representation is: $$[T] = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$$ Matrix-Vector Multiplication as Application of the Linear Map When we multiply a matrix $A$ (representing a linear map $T$) by a column vector $\mathbf{v}$ (representing a vector $v$), we get: $$A\mathbf{v} = \text{the coordinate vector of } T(v)$$ This is exactly the formula for applying the linear map. The matrix-vector product isn't just an arbitrary operation—it's the concrete computation of the linear transformation. Example: Using the rotation matrix above: $$\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 3 \\ 2 \end{bmatrix} = \begin{bmatrix} 0 \cdot 3 + (-1) \cdot 2 \\ 1 \cdot 3 + 0 \cdot 2 \end{bmatrix} = \begin{bmatrix} -2 \\ 3 \end{bmatrix}$$ This correctly rotates $(3, 2)$ to $(-2, 3)$. Part 2: Matrix Multiplication and Composition The Deep Connection: Composition of Maps and Matrix Multiplication Suppose we have two linear maps: $T: U \to V$ and $S: V \to W$. We can compose them to get $S \circ T: U \to W$. Here's the remarkable fact: if $T$ is represented by matrix $B$ and $S$ is represented by matrix $A$, then $S \circ T$ is represented by the matrix product $AB$. In other words: matrix multiplication is the computational manifestation of function composition. This explains why matrix multiplication is defined the way it is. The definition isn't arbitrary—it's the only definition that makes this correspondence work! $$A(B\mathbf{v}) = (AB)\mathbf{v}$$ Example: Let's compose two transformations in $\mathbb{R}^2$: First apply rotation by 90°: $B = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$ Then scale by 2: $A = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$ The composition $A \circ B$ should scale all vectors by 2, then rotate by 90°. Let's compute $AB$: $$AB = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & -2 \\ 2 & 0 \end{bmatrix}$$ This represents "rotate by 90°, then scale by 2" (or equivalently, scale by 2 then rotate—these compose to give the same result for these particular maps). Part 3: Similarity and Change of Basis The Same Linear Map, Different Bases Here's a subtle but important point: the same linear map can be represented by different matrices, depending on which basis we choose for the domain and codomain. Why does this matter? In practice, we might choose different bases for computational convenience. For instance, if we're studying a transformation, there might be special basis vectors called eigenvectors that the transformation just scales. In the eigenvector basis, the matrix representation becomes much simpler. Similarity: When Matrices Represent the Same Endomorphism An endomorphism is a linear map from a vector space to itself. When the domain and codomain are the same, changing basis gives us a special relationship. If $A$ and $B$ are two matrices representing the same endomorphism in different bases, they are similar: there exists an invertible matrix $P$ such that: $$A = PBP^{-1}$$ The matrix $P$ is the change of basis matrix: its columns are the coordinates of the new basis vectors expressed in the old basis. Intuition: The formula $A = PBP^{-1}$ says: $P^{-1}$ converts from the new basis to the old basis $B$ applies the transformation in the old basis $P$ converts back from the old basis to the new basis Computing Changes of Basis: Elementary Row and Column Operations While we won't need all the details for basic understanding, the key point is that we can systematically find similar matrices using elementary row and column operations: Swapping rows or columns Multiplying a row or column by a nonzero scalar Adding a multiple of one row/column to another These operations preserve similarity and help us find simpler forms of matrices (like diagonal form, which is much easier to work with). Part 4: Gaussian Elimination The Fundamental Algorithm Gaussian elimination is the algorithm we use to solve linear systems in practice. It works by systematically performing elementary row operations to transform a matrix into a simpler form. The process has two phases: Forward Elimination: Transform the matrix into row echelon form, where: All zero rows are at the bottom In each non-zero row, the first nonzero entry (the pivot) is to the right of the pivot in the row above Below each pivot, all entries are zero Back Substitution: Continue to reduced row echelon form, where additionally: Each pivot equals 1 Above each pivot, all entries are zero What Gaussian Elimination Reveals After reducing to reduced row echelon form, the matrix tells us essential information about the original linear system: The rank of the matrix equals the number of nonzero rows (the number of independent constraints) The kernel (the null space—solutions to $A\mathbf{x} = \mathbf{0}$) can be read off from the free variables Whether an inverse exists: for a square matrix, it's invertible if and only if the reduced form is the identity matrix Example: Consider the system: $$\begin{align} x + 2y &= 5 \\ 2x + 4y &= 10 \end{align}$$ The coefficient matrix is $\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}$, and the augmented matrix is $\left[\begin{array}{cc|c} 1 & 2 & 5 \\ 2 & 4 & 10 \end{array}\right]$. Applying elementary row operations (subtract 2× row 1 from row 2): $$\left[\begin{array}{cc|c} 1 & 2 & 5 \\ 0 & 0 & 0 \end{array}\right]$$ The second equation is redundant! We have only one constraint: $x + 2y = 5$. Setting $y = t$ (a free variable), we get $x = 5 - 2t$. The solution set is a line, not a single point. Part 5: Linear Systems What is a Linear System? A linear system is a finite set of linear equations in a finite set of variables. "Linear" means each equation has degree 1 in each variable—no squares, products, or other nonlinearities. A general linear system with $m$ equations in $n$ unknowns looks like: $$\begin{align} a{11}x1 + a{12}x2 + \cdots + a{1n}xn &= b1 \\ a{21}x1 + a{22}x2 + \cdots + a{2n}xn &= b2 \\ &\vdots \\ a{m1}x1 + a{m2}x2 + \cdots + a{mn}xn &= bm \end{align}$$ Matrix Formulation: Unifying View All this complexity simplifies dramatically when we write it as a single matrix equation: $$A\mathbf{x} = \mathbf{b}$$ where: $A$ is the $m \times n$ coefficient matrix whose entries are the $a{ij}$ values $\mathbf{x} = \begin{bmatrix} x1 \\ x2 \\ \vdots \\ xn \end{bmatrix}$ is the column vector of unknowns $\mathbf{b} = \begin{bmatrix} b1 \\ b2 \\ \vdots \\ bm \end{bmatrix}$ is the right-hand side vector This formulation connects linear systems to linear maps: solving $A\mathbf{x} = \mathbf{b}$ means finding all vectors $\mathbf{x}$ that map to $\mathbf{b}$ under the linear map represented by $A$. Example: The system $$\begin{align} 2x - y &= 1 \\ x + 3y &= 4 \end{align}$$ becomes: $$\begin{bmatrix} 2 & -1 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 4 \end{bmatrix}$$ Homogeneous vs. Non-Homogeneous Systems When $\mathbf{b} = \mathbf{0}$, the system $A\mathbf{x} = \mathbf{0}$ is called homogeneous. This is asking: which vectors get mapped to the zero vector by the linear map represented by $A$? The answer is precisely the kernel (or null space) of $A$. The solution set of a homogeneous system always includes the zero vector, and it has special algebraic structure: if $\mathbf{x}1$ and $\mathbf{x}2$ are solutions, so is any linear combination $c1\mathbf{x}1 + c2\mathbf{x}2$ (by linearity of $A$). A non-homogeneous system has $\mathbf{b} \neq \mathbf{0}$. Its solution set (when it exists) is typically not a vector space—it's an affine subspace (a translated version of a subspace). If $\mathbf{x}p$ is one particular solution and $\mathbf{x}h$ is any solution to the homogeneous system, then $\mathbf{x}p + \mathbf{x}h$ is also a solution. Key principle: The general solution to $A\mathbf{x} = \mathbf{b}$ is: $$\mathbf{x} = \mathbf{x}{\text{particular}} + \mathbf{x}{\text{homogeneous}}$$ where $\mathbf{x}{\text{particular}}$ is any single solution to the non-homogeneous system, and $\mathbf{x}{\text{homogeneous}}$ ranges over all solutions to $A\mathbf{x} = \mathbf{0}$. Solving Linear Systems For square invertible matrices: If $A$ is an $n \times n$ matrix and $\det(A) \neq 0$ (we'll define the determinant shortly), then $A$ has an inverse $A^{-1}$. The unique solution is: $$\mathbf{x} = A^{-1}\mathbf{b}$$ We can check: $A(A^{-1}\mathbf{b}) = (AA^{-1})\mathbf{b} = I\mathbf{b} = \mathbf{b}$ ✓ For any system: Use Gaussian elimination. This method works when the matrix is square, rectangular, singular, or non-singular. It reveals: Whether a solution exists Whether the solution is unique If solutions aren't unique, how to describe them all (using free variables) Part 6: Endomorphisms and Square Matrices Endomorphisms: Linear Maps to Themselves An endomorphism of a vector space $V$ is a linear map $T: V \to V$ from the space to itself. These are special because the domain and codomain are the same space, which creates nice mathematical structure. With respect to a chosen basis of $V$ of size $n$, an endomorphism is represented by an $n \times n$ square matrix. Square matrices inherit all the special properties of endomorphisms: They can be composed with themselves: $A \cdot A$, written $A^2$ They can have eigenvalues and eigenvectors They might be invertible (if $\det(A) \neq 0$) Where Endomorphisms Appear Endomorphisms model many important situations: Geometric transformations: Rotations, reflections, scalings of space Coordinate changes: Expressing the same geometric configuration in different coordinate systems Quadratic forms: Expressions like $x^2 + 2xy + 3y^2$ can be encoded as an endomorphism and analyzed using matrix tools Recurrence relations: The state of a system evolving over time Part 7: The Determinant What is the Determinant? The determinant of a square matrix $A$ is a single number, denoted $\det(A)$ or $|A|$, that encodes crucial information about the linear map represented by $A$. Geometric meaning: For an endomorphism, the absolute value of the determinant is the factor by which the transformation scales volumes. A positive determinant means the transformation preserves orientation (handedness); a negative determinant means it flips orientation. If $|\det(A)| > 1$: the transformation expands volumes If $|\det(A)| < 1$: the transformation shrinks volumes If $\det(A) = 0$: the transformation collapses space to a lower dimension (it's not invertible) The Invertibility Criterion Here's the most important property for solving linear systems: A square matrix $A$ is invertible if and only if $\det(A) \neq 0$. This is why the determinant matters: it tells us whether a system $A\mathbf{x} = \mathbf{b}$ has a unique solution (when $\det(A) \neq 0$) or whether something more complicated is happening (when $\det(A) = 0$). Why it's true: If $\det(A) = 0$, the endomorphism represented by $A$ collapses to a lower-dimensional subspace. This means $A$ is not injective (not one-to-one), so it doesn't have an inverse. Conversely, if $\det(A) \neq 0$, the transformation is full-dimensional and can be reversed. Cramer's Rule: Solving Systems Using Determinants For a square system $A\mathbf{x} = \mathbf{b}$ where $\det(A) \neq 0$, we can express the solution explicitly using determinants: $$xi = \frac{\det(Ai)}{\det(A)}$$ where $Ai$ is the matrix obtained by replacing the $i$-th column of $A$ with the right-hand side vector $\mathbf{b}$. Example: Solve $\begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 5 \\ 6 \end{bmatrix}$ First, compute $\det(A) = 2(3) - 1(1) = 6 - 1 = 5 \neq 0$, so a unique solution exists. For $x$: replace the first column with $\mathbf{b}$: $A1 = \begin{bmatrix} 5 & 1 \\ 6 & 3 \end{bmatrix}$ $$\det(A1) = 5(3) - 1(6) = 15 - 6 = 9$$ $$x = \frac{9}{5}$$ For $y$: replace the second column with $\mathbf{b}$: $A2 = \begin{bmatrix} 2 & 5 \\ 1 & 6 \end{bmatrix}$ $$\det(A2) = 2(6) - 5(1) = 12 - 5 = 7$$ $$y = \frac{7}{5}$$ Important note: Cramer's rule is elegant and theoretically important, but for large systems, Gaussian elimination is typically faster computationally. Summary The topics in this section form a unified framework: Matrices represent vectors and linear maps concretely Matrix multiplication encodes composition of linear maps Gaussian elimination is the practical algorithm for solving systems Determinants determine invertibility and provide alternative solution methods Endomorphisms and similarity reveal how the choice of basis affects representation Master these concepts, and you'll have the tools to solve problems across linear algebra and its applications.