Chapter 2 [https://mml-book.github.io/book/mml-book.pdf]
Systems of Linear Equations
A system of linear equations consists of simultaneous linear equations in unknowns.
General Form
Where:
- are the coefficients.
- are the unknown variables.
- are the constants.
- is the number of equations and is the number of unknowns.
In matrix notation, the system is written as:
with , , and .
A solution is a vector that satisfies every equation simultaneously.
A system of linear equations over has exactly one of three possible outcomes:
- No solution (inconsistent): No vector satisfies all equations.
- Unique solution: Exactly one vector satisfies all equations.
- Infinitely many solutions: The system is consistent but contains free variables.
A consistent linear system cannot have exactly two or any other finite number greater than one of distinct solutions.
Geometrically, it means finding the common intersection of the corresponding lines, planes, or hyperplanes.
Each nontrivial linear equation represents a geometric constraint:
- In : A line.
| Geometric configuration | Solution |
|---|---|
| Two nonparallel lines intersect | Unique solution |
| Two distinct parallel lines | No solution |
| Two coincident lines | Infinitely many solutions |
Matrices
Matrix Inverse
For a square matrix , the inverse is uniquely defined, when it exists, by:
- Invertible (nonsingular): The inverse exists.
- Singular: The inverse does not exist.
Consider a square matrix :
Define an auxiliary matrix (interchanging the diagonal elements and negating the off-diagonal elements)
If
The inverse exists if and only if
is the determinant of :
Multiplying by the auxiliary matrix produces a scalar multiple of the identity matrix:
Matrix multiplication is generally noncommutative, even when both matrices are square and have identical dimensions.
Example:
An inverse is a special case where both orders give the identity matrix.
Matrix Transpose
For , the transpose is defined by:
Properties
In general:
Both inversion and transposition reverse the order of matrix multiplication.
Symmetric Matrices
A square matrix is symmetric if:
- The sum of symmetric matrices is symmetric.
- The product of symmetric matrices is not necessarily symmetric.
- The inverse of an invertible symmetric matrix is symmetric.
A system of linear equations with unknowns can be represented compactly as:
where:
- is the coefficient matrix.
- is the vector of unknowns.
- is the right-hand-side vector.
Elementary Transformations
Elementary transformations are operations that simplify a system of linear equations while preserving its solution set.
Elementary Row Operations
For a system , the three permitted operations are:
- Row interchange: Swap two rows. $$ R_i \leftrightarrow R_j
- Row scaling: Multiply a row by a nonzero scalar . $$ R_i \leftarrow \lambda R_i,\qquad \lambda\neq0
- Row replacement: Add a multiple of one row to another.$$ R_i \leftarrow R_i+\lambda R_j,\qquad i\neq j
All operations must be applied to the entire equation, including its right-hand side.
Augmented Matrix
The system can be represented by its augmented matrix:
The vertical line separates the coefficient matrix from the right-hand side .
Elementary row operations transform this matrix into a simpler, equivalent system.
Row-Echelon Form (REF)
A matrix is in row-echelon form if:
- All zero rows appear at the bottom.
- The first nonzero entry of each nonzero row, called its pivot, lies strictly to the right of the pivot in the preceding row.
This produces a staircase structure, with zeros below every pivot.
Variables corresponding to pivot columns are basic variables. The remaining variables are free variables.
Reduced Row-Echelon Form (RREF)
A matrix is in reduced row-echelon form if:
- It satisfies all REF conditions.
- Every pivot equals .
- Every pivot is the only nonzero entry in its column.
RREF allows basic variables to be expressed directly in terms of free variables.
Gaussian Elimination
Gaussian elimination is an algorithm that performs elementary transformations to bring a system of linear equations into reduced row-echelon form
- Select a nonzero pivot, swapping rows if necessary.
- Eliminate entries below the pivot.
- Continue through the remaining columns to obtain REF.
- Use back-substitution to solve the system.
Continuing the elimination above each pivot and normalizing pivots produces RREF (GaussโJordan elimination).
Example
Applying elementary row operations gives the row-echelon form:
Here the system is consistent if and only if:
The pivot variables are , while are free variables.
From REF, the system becomes:
The free variables are and
Therefore, a particular solution is:
For , the general solution is:
where .
- Elementary row operations preserve the solution set.
- REF simplifies solving through back-substitution.
- RREF makes pivot and free variables easier to identify.
The Minus-1 Trick
The Minus-1 Trick is a method for finding a basis of the null space , i.e., all solutions to the homogeneous system:
- Reduce to RREF and remove zero rows.
- Identify the pivot and free columns.
- Extend the matrix to an matrix by inserting rows with in the diagonal positions corresponding to free variables, and zeros elsewhere.
- The columns containing on the diagonal are basis vectors of .
Consider the matrix:
The pivot columns are , and the free columns are .
Extend to a matrix by inserting rows containing at the missing diagonal positions:
The second and fifth columns contain on the diagonal. Reading these columns gives the null-space basis vectors:
Why ?
The second column of the original matrix satisfies:
This is exactly the linear combination represented by
so .
General Solution
For a consistent system , every solution is:
where is a particular solution and is a homogeneous solution ().
Since for any :
Adding any vector from the null space to a particular solution produces another valid solution.
Computing a Matrix Inverse Using Row Reduction
For an invertible square matrix , augment it with the identity matrix and apply GaussโJordan elimination:
If the left side cannot be reduced to , the matrix is singular and has no inverse.
Algorithms for Solving a System of Linear Equations
The linear system:
Different solution methods are appropriate depending on the dimensions, rank, and computational size of .
1. Inverse-Based Solution
If is square and invertible, the unique solution is:
However, not every matrix is square or invertible.
2. MooreโPenrose Pseudoinverse
For with linearly independent columns, is invertible.
Multiplying by gives:
Therefore:
In this case, the MooreโPenrose pseudoinverse is:
Hence:
- If the system is consistent, this gives its unique solution.
- If it is inconsistent, this gives the unique least-squares solution.
- The formula requires full column rank; the general pseudoinverse also exists for rank-deficient matrices.
Numerical consideration: Explicitly computing inverses or pseudoinverses is generally discouraged because of computational cost and numerical precision.
3. Gaussian Elimination
Gaussian elimination solves linear systems through elementary row operations.
For a dense system, its computational complexity scales approximately as:
It is practical for many systems but can become expensive for extremely large matrices.
4. Iterative Methods
Instead of solving the system directly, iterative methods construct a sequence of approximations:
where:
- is the approximation at iteration .
- is an iteration matrix.
- is a constant vector.
The objective is convergence toward the exact solution :
Convergence depends on the chosen method and properties of the system.
Methods mentioned in MML:
- Stationary methods: Richardson, Jacobi, GaussโSeidel, successive over-relaxation (SOR).
- Krylov subspace methods: Conjugate gradients, GMRES, biconjugate gradients.
Key Insight
- Direct methods: Compute a solution through a finite sequence of algebraic operations.
- Iterative methods: Refine approximations toward a solution.
- Pseudoinverse: Provides a generalized approach when a conventional inverse cannot be used.
Reference: MML, Section 2.3.4, pp. 34โ35, Equations (2.59)โ(2.60).