← 2025 Paper 2

UPSC 2025 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

LPP: standard form; basic, basic feasible, optimal solutions · Linear Programming · asked 6× in 13 yrs · Read the full method →

Question

How many basic solutions are there for the following system of equations?

Find all of them. Furthermore, find the number of basic solutions, which are feasible/non-feasible/non-degenerate.

Technique

A basic solution chooses $m=2$ basic variables (an invertible $m\times m$ submatrix of columns), sets the other variables to zero, and solves. Count the nonsingular column-pairs out of $\binom{4}{2}=6$, solve each, then classify.

Solution

The system has $m=2$ equations and $n=4$ unknowns. The coefficient matrix is

A basic solution is obtained by selecting $m=2$ columns forming a nonsingular $2\times2$ matrix $B$ (the basis), setting the other two variables to $0$, and solving $B x_B = b$. The maximum possible number is $\binom{4}{2}=6$.

Step 1 — Identify which column pairs are nonsingular.

The four columns are

The columns $c_1,c_2,c_4$ are all scalar multiples of $(1,2)^T$: $c_1=2(1,2)^T$, $c_2=-(1,2)^T$, $c_4=(1,2)^T$. Hence any pair drawn entirely from $\{c_1,c_2,c_4\}$ is linearly dependent (determinant $0$):

• $(c_1,c_2)$: $\det=0$,
• $(c_1,c_4)$: $\det=0$,
• $(c_2,c_4)$: $\det=0$.

The remaining three pairs all contain $c_3$, which is not parallel to $(1,2)^T$, so each is nonsingular:

• $(c_1,c_3)$: $\det = 2(-1)-3(4) = -14 \neq 0$,
• $(c_2,c_3)$: $\det = (-1)(-1)-3(-2) = 7 \neq 0$,
• $(c_3,c_4)$: $\det = 3(2)-1(-1) = 7 \neq 0$.

So exactly 3 basic solutions exist.

Step 2 — Compute the 3 basic solutions.

Basis $\{x_1,x_3\}$ ($x_2=x_4=0$):

Basis $\{x_2,x_3\}$ ($x_1=x_4=0$):

Basis $\{x_3,x_4\}$ ($x_1=x_2=0$):

Step 3 — Classify.

• Feasible (all components $\ge 0$): $\mathbf{x}^{(1)}$ and $\mathbf{x}^{(3)}$ are feasible. $\mathbf{x}^{(2)}$ has $x_2=-36/7<0$, so it is non-feasible.
• Non-degenerate (all $m=2$ basic variables nonzero): in every one of the three solutions both basic variables are nonzero. So all $3$ are non-degenerate.

Answer

• Number of basic solutions: 3 (out of a possible $\binom{4}{2}=6$; the other 3 column-pairs are singular because columns $c_1,c_2,c_4$ are mutually parallel).
• The three basic solutions are

• Feasible: 2 $\left(\mathbf{x}^{(1)},\mathbf{x}^{(3)}\right)$; non-feasible: 1 $\left(\mathbf{x}^{(2)}\right)$; non-degenerate: 3 (degenerate: 0).