From the free course Spring 2026 - Math 354 - Sections 02/04 on Lykke
Linear Algebra Review and Matrix Operations
Key concepts: Reduced Row Echelon Form (RREF) · Matrix Inversion · Linear Independence · Linear Combinations · Vector Spaces
A foundational review of linear algebra techniques essential for optimization, focusing on matrix inversion and vector space properties.
Linear Algebra Review and Matrix Operations
Linear algebra is the mathematical language of optimization. While high-level solvers often abstract away the underlying arithmetic, a mastery of linear programming (LP) requires a profound understanding of how systems of linear equations are manipulated, how vector spaces are structured, and how matrix transformations define the feasible regions of our problems. In this article, we will move beyond basic definitions to explore the mechanics of matrix operations that power the Simplex method and other fundamental algorithms in operations research.
Vector Spaces and Linear Combinations
At the core of linear algebra lies the Vector Space. For the purposes of optimization and the Simplex method, we primarily concern ourselves with the real coordinate space $\mathbb{R}^n$. A vector space is not merely a collection of points; it is a set closed under two primary operations: vector addition and scalar multiplication.
The Geometry of Linear Combinations
A Linear Combination of a set of vectors ${v_1, v_2, \dots, v_k}$ is an expression of the form: $$y = c_1v_1 + c_2v_2 + \dots + c_kv_k$$ where $c_i$ are scalars. In the context of Linear Programming, every point within a feasible region can be viewed as a linear combination of the extreme points (vertices) of the constraint polytope, provided the weights $c_i$ satisfy specific conditions (such as non-negativity and summing to one for convex combinations).
Definition: Span The Span of a set of vectors is the set of all possible linear combinations of those vectors. If the span of a set of vectors in $\mathbb{R}^n$ covers the entire space, we say the set "spans" $\mathbb{R}^n$.
| Concept | Mathematical Representation | Geometric Interpretation |
|---|---|---|
| Vector | $x \in \mathbb{R}^n$ | A directed arrow or point in space. |
| Scalar Multiplication | $\alpha x$ | Scaling the length of the vector. |
| Linear Combination | $\sum c_i v_i$ | Reaching a new point by following weighted vectors. |
| Span | $\text{span}{v_1, \dots, v_k}$ | The "subspace" (line, plane, etc.) filled by the vectors. |
Implementation: Linear Combinations in Practice
In modern data science and engineering, we rarely perform these calculations by hand. However, understanding how a library like NumPy handles these operations is crucial for performance.
import numpy as np
# Defining vectors in R^4 (as seen in HW1_0-5-6a)
v1 = np.array([-1, 2, 4, 3])
v2 = np.array([3, -1, 2, 5])
v3 = np.array([-5, 5, 6, 1])
# Check if v3 is a linear combination of v1 and v2
# We solve the system: c1*v1 + c2*v2 = v3
# This is equivalent to Ac = b where A = [v1, v2] and b = v3
A = np.stack([v1, v2], axis=1)
try:
# Use least squares to find coefficients
c, residuals, rank, s = np.linalg.lstsq(A, v3, rcond=None)
# If residuals are near zero, v3 is a linear combination
is_linear_comb = np.allclose(A @ c, v3)
print(f"Coefficients: {c}")
print(f"Is v3 a linear combination? {is_linear_comb}")
except np.linalg.LinAlgError:
print("System is inconsistent.")
Linear Independence
A set of vectors is Linearly Independent if no vector in the set can be expressed as a linear combination of the others. Formally, the set ${v_1, v_2, \dots, v_k}$ is linearly independent if the only solution to the vector equation: $$c_1v_1 + c_2v_2 + \dots + c_kv_k = 0$$ is the trivial solution $c_1 = c_2 = \dots = c_k = 0$.
Why Independence Matters in Optimization
In the Simplex method, we transform inequality constraints into equality constraints by adding slack variables. This results in a system $Ax = b$ where $A$ is an $m \times n$ matrix with $n > m$. To find a Basic Feasible Solution (BFS), we must select $m$ linearly independent columns from $A$ to form a Basis. If the columns were linearly dependent, the resulting basis matrix $B$ would be singular (non-invertible), and we could not solve for the basic variables.
Determining Independence via Rank
The Rank of a matrix is the maximum number of linearly independent column vectors in the matrix.
- If a set of $k$ vectors in $\mathbb{R}^n$ has rank $k$, they are linearly independent.
- If the rank is less than $k$, at least one vector is redundant.
Mathematical Derivation: Testing for Independence
To test if $S = {v_1, v_2, v_3}$ is linearly independent, we set up the augmented matrix $[v_1 v_2 v_3 | 0]$ and reduce it to RREF.
\begin{aligned}
&\text{Given vectors from HW1:} \\
&v_1 = \begin{bmatrix} -1 \\ 2 \\ 4 \\ 3 \end{bmatrix}, v_2 = \begin{bmatrix} 3 \\ -1 \\ 2 \\ 5 \end{bmatrix}, v_3 = \begin{bmatrix} -5 \\ 5 \\ 6 \\ 1 \end{bmatrix} \\
&\text{Solve } c_1v_1 + c_2v_2 + c_3v_3 = 0: \\
&\begin{bmatrix} -1 & 3 & -5 & | & 0 \\ 2 & -1 & 5 & | & 0 \\ 4 & 2 & 6 & | & 0 \\ 3 & 5 & 1 & | & 0 \end{bmatrix} \xrightarrow{RREF} \begin{bmatrix} 1 & 0 & 2 & | & 0 \\ 0 & 1 & -1 & | & 0 \\ 0 & 0 & 0 & | & 0 \\ 0 & 0 & 0 & | & 0 \end{bmatrix} \\
&\text{Since there is a free variable (c3), the vectors are Linearly Dependent.} \\
&\text{Solution: } c_1 = -2c_3, c_2 = c_3. \text{ Let } c_3 = 1 \implies -2v_1 + v_2 + v_3 = 0.
\end{aligned}
Reduced Row Echelon Form (RREF)
The Reduced Row Echelon Form is the destination of Gaussian Elimination. It is the most "revealing" state of a matrix, showing exactly how variables relate to one another.
Criteria for RREF
A matrix is in RREF if it meets the following four conditions:
- All non-zero rows are above any rows of all zeros.
- The leading coefficient (pivot) of a non-zero row is always 1.
- Each leading 1 is to the right of the leading 1 in the row above it.
- Each column containing a leading 1 has zeros everywhere else in that column.
The Algorithm: Gaussian Elimination
The process involves three types of Elementary Row Operations (EROs):
- Swapping two rows.
- Multiplying a row by a non-zero scalar.
- Adding a multiple of one row to another row.
| Operation | Purpose | Simplex Analog |
|---|---|---|
| Row Swap | Positioning a non-zero pivot. | Selecting a new basic variable. |
| Row Scaling | Normalizing the pivot to 1. | Normalizing the pivot row in a tableau. |
| Row Addition | Eliminating variables from other equations. | Updating the objective function and other constraints. |
Low-Level Implementation (C)
In systems programming, we often implement Gaussian elimination manually to avoid the overhead of heavy libraries.
#include <stdio.h>
void rref(float matrix[3][4], int rows, int cols) {
int lead = 0;
for (int r = 0; r < rows; r++) {
if (lead >= cols) return;
int i = r;
while (matrix[i][lead] == 0) {
i++;
if (i == rows) {
i = r;
lead++;
if (lead == cols) return;
}
}
// Swap rows i and r
for (int j = 0; j < cols; j++) {
float temp = matrix[i][j];
matrix[i][j] = matrix[r][j];
matrix[r][j] = temp;
}
// Scale row r to make pivot 1
float val = matrix[r][lead];
for (int j = 0; j < cols; j++) matrix[r][j] /= val;
// Eliminate other rows
for (int i = 0; i < rows; i++) {
if (i != r) {
float val2 = matrix[i][lead];
for (int j = 0; j < cols; j++) matrix[i][j] -= val2 * matrix[r][j];
}
}
lead++;
}
}
Matrix Inversion
A square matrix $A$ is Invertible (or non-singular) if there exists a matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$, where $I$ is the identity matrix.
The Gauss-Jordan Method
The most robust way to find an inverse manually is to augment the matrix with the identity matrix $[A | I]$ and apply EROs until the left side is in RREF. If $A$ is invertible, the RREF will be $[I | A^{-1}]$.
The Invertible Matrix Theorem For an $n \times n$ matrix $A$, the following are equivalent:
- $A$ is invertible.
- The RREF of $A$ is $I_n$.
- The rank of $A$ is $n$.
- The determinant $\det(A) \neq 0$.
- The columns of $A$ are linearly independent.
Common Pitfalls in Inversion
- Singularity: Attempting to invert a matrix with a determinant of zero. In optimization, this happens if constraints are redundant or if the chosen basis columns are linearly dependent.
- Numerical Instability: In floating-point arithmetic, a matrix may be "nearly singular" (high condition number), leading to massive rounding errors.
- Computational Cost: Inverting an $n \times n$ matrix has a complexity of $O(n^3)$. In large-scale LP, we use LU decomposition or other sparse matrix techniques instead of explicit inversion.
| Method | Complexity | Best Use Case |
|---|---|---|
| Gauss-Jordan | $O(n^3)$ | Manual calculation, small matrices. |
| LU Decomposition | $O(n^3)$ | Solving $Ax=b$ for multiple $b$ vectors. |
| Cramer's Rule | $O(n!)$ | Theoretical proofs, $2 \times 2$ matrices only. |
| Iterative Methods | Variable | Very large, sparse matrices. |
Application: From Algebra to Linear Programming
Linear Algebra provides the "how," but Linear Programming provides the "why." Every LP problem starts as a set of constraints that must be converted into a standard or canonical form.
Standard vs. Canonical Form
As seen in Participation #1, most real-world problems are not initially in a form suitable for the Simplex method.
- Standard Form:
- Maximize an objective function.
- All constraints are $\le$ inequalities.
- All variables are non-negative ($x_i \ge 0$).
- Canonical Form:
- Objective function can be Max or Min.
- All constraints are equalities ($Ax = b$).
- $b \ge 0$.
- A basis (identity matrix) is visible within $A$.
Transformation via Slack Variables
To move from standard to canonical form, we add Slack Variables ($s_i$). If we have a constraint $2x_1 + 3x_2 \le 6$, we rewrite it as $2x_1 + 3x_2 + s_1 = 6$, where $s_1 \ge 0$. This $s_1$ represents the "slack" between the left-hand side and the resource limit.
The Simplex Tableau as a Matrix
The Simplex tableau is essentially a matrix in a specific state of row reduction. When we "pivot," we are performing EROs to change which columns form the identity matrix (the basis).
# Example: Using a CLI tool to solve a system (hypothetical 'mat-tool')
# Problem: Maximize z = 4x1 + 2x2 + 7x3
# Constraints: 2x1 - x2 + 4x3 <= 18; 4x1 + 2x2 + 5x3 <= 10
mat-tool --solve-lp \
--obj "4,2,7" \
--constraints "2,-1,4,18; 4,2,5,10" \
--method simplex \
--verbose
Mastery and Error Classification
In a professional or academic setting, solving these problems requires more than just getting the right answer. Based on the Grading Rubric and Self-Reflection Worksheets, mastery is defined by:
- Conceptual Understanding: Why are we using RREF? Why must the columns be independent?
- Mathematical Accuracy: Precision in EROs. A single sign error in a $3 \times 3$ matrix inversion cascades through the entire problem.
- Clarity of Strategy: Showing the transition from the physical problem to the augmented matrix.
Error Classification Table
| Error Type | Description | Impact on Solution |
|---|---|---|
| Transcription Error | Copying a number incorrectly from one step to the next. | High; invalidates all subsequent steps. |
| Arithmetic Error | Simple addition/multiplication mistake during EROs. | Moderate; usually leads to non-integer results in textbook problems. |
| Strategic Error | Choosing a pivot that doesn't lead to RREF or violates non-negativity. | Critical; the algorithm fails to converge. |
| Conceptual Error | Misunderstanding the difference between feasible and basic solutions. | Critical; the answer may be "correct" but the reasoning is flawed. |
Source Materials
Study Spring 2026 - Math 354 - Sections 02/04 on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every sectionAll sections of Spring 2026 - Math 354 - Sections 02/04 · Browse more course pages