Geometry of linear equations
Geometry of Linear Equations
Linear equations have a geometric meaning.
In operational research, this geometry is used to understand feasible regions, vertices, and graphical solutions of linear programming problems.
Linear Equation in Two Variables
A linear equation in two variables has the form:
\[a_1x_1+a_2x_2=b\]If:
\[(a_1,a_2)\ne(0,0)\]then this equation represents a line in the plane.
Example:
\[x_1+2x_2=10\]is a line in $\mathbb{R}^2$.
Plotting a Line
To plot:
\[x_1+2x_2=10\]find two points.
Set $x_1=0$:
\[2x_2=10\] \[x_2=5\]So one point is:
\[(0,5)\]Set $x_2=0$:
\[x_1=10\]So another point is:
\[(10,0)\]The line passes through $(0,5)$ and $(10,0)$.
Linear Equation in Three Variables
A linear equation in three variables has the form:
\[a_1x_1+a_2x_2+a_3x_3=b\]If:
\[(a_1,a_2,a_3)\ne(0,0,0)\]then the equation represents a plane in $\mathbb{R}^3$.
Example:
\[x_1+2x_2+3x_3=12\]is a plane.
Hyperplane
In $\mathbb{R}^n$, a linear equation:
\[a^Tx=b\]represents a hyperplane.
A hyperplane is the higher-dimensional version of:
- a line in $\mathbb{R}^2$
- a plane in $\mathbb{R}^3$
Normal Vector
For the hyperplane:
\[a^Tx=b\]the vector $a$ is perpendicular to the hyperplane.
It is called the normal vector.
Example:
\[3x_1+2x_2=6\]has normal vector:
\[a=(3,2)\]Intersections
Systems of linear equations describe intersections.
Example:
\[\begin{cases} x_1+2x_2=10 \\ 2x_1+x_2=16 \end{cases}\]represents the intersection of two lines.
Solving the system gives the point where the lines meet.
Intersections and Vertices
In graphical linear programming, vertices of the feasible region are found by intersecting boundary lines.
Example:
If the feasible region has boundaries:
\[x_1+2x_2=10\]and:
\[2x_1+x_2=16\]then their intersection is a candidate vertex.
Solving:
\[\begin{cases} x_1+2x_2=10 \\ 2x_1+x_2=16 \end{cases}\]gives:
\[x_1=\frac{22}{3}, \qquad x_2=\frac{4}{3}\]Active Constraints
A constraint is active at a point when it holds with equality.
For example:
\[x_1+2x_2\le 10\]is active at $x=(2,4)$ because:
\[2+2(4)=10\]The same constraint is inactive at $x=(1,1)$ because:
\[1+2(1)=3<10\]Vertices usually occur where enough constraints are active.
Objective Contour Lines
For a linear objective:
\[f(x)=c^Tx\]the set of points with the same objective value is:
\[c^Tx=k\]where $k$ is a constant.
In two variables, these are parallel lines.
In three variables, these are parallel planes.
Example of Contour Lines
Let:
\[f(x_1,x_2)=x_1+x_2\]A contour line is:
\[x_1+x_2=k\]For different values of $k$, we get parallel lines:
\[x_1+x_2=0\] \[x_1+x_2=3\] \[x_1+x_2=5\]Each line contains all points with the same objective value.
Cost Vector
For:
\[f(x)=c^Tx\]the vector $c$ is the cost vector or objective coefficient vector.
In a maximization problem, $c$ points in the direction of increase.
In a minimization problem, $-c$ points in the direction of decrease.
Graphical Solution Idea
For a two-variable LP:
- draw the feasible region
- draw an objective contour line
- move the contour line in the improving direction
- stop at the last point where it touches the feasible region
That final contact point is an optimal solution.
Vertex Optimality
For linear programming, if an optimal solution exists, then one can usually be found at a vertex of the feasible region.
This is why graphical methods focus on corner points.
It is also why simplex moves from vertex to vertex.
Multiple Optimal Solutions
If the objective contour line is parallel to an edge of the feasible region, then every point on that edge can be optimal.
In that case, there are infinitely many optimal solutions.
Unbounded Objective
If the objective can improve forever while staying feasible, the problem is unbounded.
Geometrically, the feasible region extends infinitely in an improving direction.
For a maximization problem, this means the optimal value is $+\infty$.
For a minimization problem, this means the optimal value is $-\infty$.
Empty Feasible Region
If the constraints have no common intersection, the feasible region is empty.
Then the LP is infeasible.
There is no feasible solution and therefore no optimal solution.
Geometry in Higher Dimensions
For $n\ge 3$, the same ideas still hold:
- equations become hyperplanes
- inequalities become half-spaces
- feasible regions become polyhedra
- vertices still matter
- objective contour sets are hyperplanes
But drawings become difficult, so we use algorithms such as simplex.
OR Interpretation
The geometry of linear equations explains:
- why constraints create boundaries
- why intersections create candidate solutions
- why objective lines move in parallel
- why vertices matter
- why simplex works by moving between basic feasible solutions
Checklist
You understand the geometry of linear equations if you can:
- plot a line from a linear equation
- interpret a linear equation as a hyperplane
- solve intersections of boundary equations
- identify active constraints
- draw objective contour lines
- explain why the objective line moves in a direction
- connect vertices with candidate optima
See Also
- Linear Systems
- Half-Spaces and Hyperplanes
- Graphical Method
- Objective Contour Lines
- Cost Vector and Direction of Improvement
- Vertices
- 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.