Linear systems primer
Linear Systems Primer
A linear system is a collection of linear equations.
Example:
\[\begin{cases} 2x_1 + 3x_2 = 10 \\ 5x_1 + x_2 = 12 \end{cases}\]The goal is to find values of the variables that satisfy all equations at the same time.
Matrix Form
A linear system can be written compactly as:
\[Ax=b\]where:
- $A$ is the coefficient matrix
- $x$ is the vector of unknowns
- $b$ is the right-hand side vector
Example:
\[\begin{cases} 2x_1 + 3x_2 = 10 \\ 5x_1 + x_2 = 12 \end{cases}\]becomes:
\[\begin{bmatrix} 2 & 3 \\ 5 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 10 \\ 12 \end{bmatrix}\]Column Interpretation
Let:
\[A = [A_1 \ A_2 \ \cdots \ A_n]\]Then:
\[Ax=b\]means:
\[x_1A_1 + x_2A_2 + \cdots + x_nA_n = b\]So solving the system means finding coefficients $x_1,\ldots,x_n$ that express $b$ as a linear combination of the columns of $A$.
Homogeneous System
A system is homogeneous if:
\[Ax = 0\]The zero vector is always a solution:
\[x=0\]This solution is called the trivial solution.
A homogeneous system may also have nonzero solutions.
Nonhomogeneous System
A system is nonhomogeneous if:
\[Ax=b\]with:
\[b \ne 0\]A nonhomogeneous system may have:
- no solution
- exactly one solution
- infinitely many solutions
Geometric Meaning in Two Variables
Each linear equation in two variables represents a line.
Example:
\[2x_1 + 3x_2 = 10\]is a line in the plane.
A system of two equations represents two lines.
Possible cases:
| Geometry | Number of Solutions |
|---|---|
| Lines intersect | one solution |
| Lines are parallel and distinct | no solution |
| Lines are identical | infinitely many solutions |
Geometric Meaning in Three Variables
Each linear equation in three variables represents a plane.
A system of equations represents the intersection of planes.
Possible intersections include:
- a single point
- a line
- a plane
- no common point
Solving a Two-Equation System
Example:
\[\begin{cases} x_1 + 2x_2 = 10 \\ 2x_1 + x_2 = 16 \end{cases}\]From the first equation:
\[x_1 = 10 - 2x_2\]Substitute into the second equation:
\[2(10 - 2x_2) + x_2 = 16\] \[20 - 4x_2 + x_2 = 16\] \[20 - 3x_2 = 16\] \[-3x_2 = -4\] \[x_2 = \frac{4}{3}\]Then:
\[x_1 = 10 - 2\cdot \frac{4}{3} = \frac{30}{3} - \frac{8}{3} = \frac{22}{3}\]So:
\[x^* = \left( \frac{22}{3}, \frac{4}{3} \right)\]Linear Systems and Graphical LP
In graphical linear programming, vertices are often found by solving systems of boundary equations.
Example:
If a vertex is the intersection of:
\[x_1 + 2x_2 = 10\]and:
\[2x_1 + x_2 = 16\]then we solve the system:
\[\begin{cases} x_1 + 2x_2 = 10 \\ 2x_1 + x_2 = 16 \end{cases}\]The solution is the candidate vertex.
Active Constraints
A constraint is active at a point if it holds as equality.
Example:
\[x_1 + 2x_2 \le 10\]is active at $x=(2,4)$ because:
\[2 + 2(4) = 10\]It is not active at $x=(1,1)$ because:
\[1 + 2(1) = 3 < 10\]A vertex of a feasible region usually occurs where enough constraints are active.
Standard Form in LP
The standard form of a linear programming problem is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]Here the equality system $Ax=b$ defines the main linear structure.
The nonnegativity constraints $x\ge 0$ restrict the solution to the nonnegative region.
Consistency
A system is consistent if it has at least one solution.
A system is inconsistent if it has no solution.
For:
\[Ax=b\]the system is consistent if $b$ can be written as a linear combination of the columns of $A$.
Rouché-Capelli Theorem
The system:
\[Ax=b\]has a solution if and only if:
\[\operatorname{rank}(A) = \operatorname{rank}([A|b])\]| where $[A | b]$ is the augmented matrix formed by appending $b$ as an extra column. |
Unique Solution
If $A$ is square and invertible, then:
\[Ax=b\]has the unique solution:
\[x=A^{-1}b\]This is important because simplex repeatedly solves systems of the form:
\[Bx_B=b\]where $B$ is a basis matrix.
Underdetermined Systems
If there are fewer equations than variables, there may be infinitely many solutions.
In standard LP:
\[A \in \mathbb{R}^{m\times n}\]usually:
\[m<n\]So there are more variables than equations.
The feasible set may contain many possible solutions, and the objective function selects the best one.
Redundant Equations
An equation is redundant if it can be derived from other equations.
Example:
\[\begin{cases} x_1 + x_2 = 4 \\ 2x_1 + 2x_2 = 8 \end{cases}\]The second equation is just twice the first.
Redundant equations do not add new information.
In LP, redundant constraints can make the algebra harder without changing the feasible set.
OR Interpretation
Linear systems appear when:
- writing standard-form LPs
- converting inequalities into equalities with slack or surplus variables
- finding intersections of constraints
- computing basic solutions
- solving $Bx_B=b$ for basic variables
- checking feasibility of a proposed solution
Checklist
You understand linear systems if you can:
- write equations in matrix form
- interpret $Ax=b$ as a column linear combination
- solve a small system manually
- identify whether a system has zero, one, or many solutions
- explain active constraints
- explain why vertices come from systems of active constraints
- connect $Bx_B=b$ to basic feasible solutions
See Also
- Vectors
- Matrices
- Linear Combinations
- Rank and Linear Independence
- Bases and Invertible Matrices
- Graphical Method
- Basic Feasible Solutions
Exam checkpoint
Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.