Consider x₁+x₂+x₃=4 with all coordinates nonnegative. Its feasible set is a triangle in three-dimensional space. The three vertices put all four units into one coordinate. At the midpoint (2,2,0), mass can be moved slightly from the first coordinate to the second or back again while preserving feasibility. This two-sided feasible movement shows that the midpoint is not extreme. We will translate that geometric idea into a column-independence test for a general equality system.
Predict
Predict how many positive coordinates a vertex can have in Ax=b when A has m independent rows. More than m positive coordinates would select dependent columns, producing a null direction supported entirely on positive entries. A sufficiently small step in either direction would preserve nonnegativity. Thus a vertex has at most m positive coordinates. It can have fewer: zero basic coordinates are allowed and are the source of degeneracy in simplex.
Experiment
Use the system x₁+x₃=2, x₂+x₃=3. Its columns are a₁=(1,0), a₂=(0,1), a₃=(1,1). Set one nonbasic coordinate to zero and solve the other two.
Basis columns
Solution (x₁,x₂,x₃)
Feasible?
1 and 2
(2,3,0)
Yes
1 and 3
(−1,0,3)
No
2 and 3
(0,1,2)
Yes
Every displayed basis matrix is invertible, but one basic solution has a negative coordinate. “Basic” and “basic feasible” are different conditions. Check each equality and sign before calling a computed basis a vertex of the feasible region.
Understand
Assume A has full row rank m. Choose m independent columns forming an invertible matrix B. Set the other, nonbasic variables to zero and solve x_B=B⁻¹b. This is a basic solution; it is basic feasible if every coordinate is nonnegative. A basic feasible solution is degenerate when at least one basic coordinate is zero, so the same geometric point can correspond to multiple bases.
The vertex criterion is that the columns indexed by strictly positive coordinates are linearly independent. If they are dependent, choose a nonzero vector d supported on them with Ad=0. Small enough positive and negative steps keep all positive coordinates nonnegative and leave zero coordinates unchanged. The point is then a midpoint of two distinct feasible points, so it is not extreme. Conversely, if x=(u+v)/2 with nonnegative feasible u,v, every zero coordinate of x forces both corresponding coordinates to vanish. The difference u−v is supported on the positive coordinates of x and lies in the nullspace of A. Independence forces u=v=x, proving extremality.
Apply
If the positive support has fewer than m columns, extend it to an independent m-column basis using full row rank. The added basic coordinates are zero, reproducing the same feasible point. This establishes equivalence between vertices and basic feasible solutions in equality standard form. If the equality rows are redundant, first check consistency and retain independent rows; using the raw row count as a basis size can demand an impossible invertible matrix.
Change the right side in the worked system from (2,3) to (2,2). The bases using columns 1,3 and 2,3 now both produce (0,0,2). Verify this directly. The point has only one positive coordinate although the rank is two. This is a concrete example of multiple bases representing one degenerate vertex, which explains why moving between bases need not move through physical decision space.
Continue
Track the basis, basic solution, sign feasibility and positive support separately. These distinctions become operational in the simplex method. Continue to Simplex pivots to derive an improving direction and a maximum feasible step from the basis equations. The derivation will also produce exact certificates when no improvement is possible or when an improving ray has no finite endpoint.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
For x₁+x₂+x₃=6 with x≥0, choose x₂ basic and others zero. What is x₂?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
For x₁+x₂+x₃=6,x≥0, how many distinct vertices exist?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
For Ax=b,x≥0, prove a feasible point whose positive-support columns are dependent is not extreme.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove a feasible point with linearly independent positive-support columns is extreme.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Assume A has full row rank m. Explain how an independent positive support gives a basic feasible solution even with fewer than m positive entries.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Why should redundant equality rows be removed before using an m-column basis formula?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
