Question

The number of maximum basic feasible solution of the system of equations AX = b, where A is m \( \times \) n matrix, b is n \( \times \) 1 column matrix and rank of A is \(\rho(A) = m\), is:

• A. \( m+n \)
• B. \( m-n \)
• C. \( mn \)
• D. \( ^nC_m \)

Hint:

In linear programming, a basic feasible solution corresponds to a vertex of the feasible region. The number of vertices is at most the number of ways you can choose \(m\) basic variables from \(n\) total variables, which is \( {}^nC_m \). This gives an upper bound on the number of BFS.

Answer 1

The Correct Option is D

Step 1: Understanding the Concept:
This question is about basic feasible solutions (BFS) in the context of linear algebra and linear programming. A basic solution to a system of linear equations \(AX=b\) is found by setting a certain number of variables to zero and solving for the rest.
Note on a typo in the question: For the matrix product AX to be defined and equal to b, if A is \(m \times n\) and X is \(n \times 1\), then b must be an \(m \times 1\) matrix. The question states b is \(n \times 1\), which is a typo. We proceed assuming b is \(m \times 1\).

Step 2: Key Definitions:
- The system has \(m\) linear equations and \(n\) variables. - We are given that the rank of the matrix A is \(m\), which implies \(m \le n\) and that the equations are linearly independent. - A basic solution is obtained by: 1. Choosing \(m\) variables out of the \(n\) variables to be "basic variables". 2. Setting the remaining \(n-m\) variables ("non-basic variables") to zero. 3. Solving the resulting \(m \times m\) system for the \(m\) basic variables. - The selection of \(m\) basic variables is valid if the corresponding \(m\) columns of the matrix A are linearly independent, forming an invertible \(m \times m\) submatrix. - A basic feasible solution (BFS) is a basic solution where all the variables (specifically, the basic ones) are non-negative.

Step 3: Detailed Explanation:
The question asks for the maximum number of basic feasible solutions. The number of BFS depends on the specific values in A and b. However, the theoretical maximum is limited by the total number of possible basic solutions. A basic solution is determined by the choice of which \(m\) variables are basic. Since the rank of A is \(m\), A has at least one set of \(m\) linearly independent columns. The maximum number of ways to form a basic solution is the number of ways to choose \(m\) columns from the \(n\) available columns. This number is given by the binomial coefficient "n choose m": \[ \text{Maximum number of basic solutions} = \binom{n}{m} = {}^nC_m \] Since every BFS is, by definition, a basic solution, the number of BFS cannot exceed the total number of basic solutions. Therefore, the maximum possible number of basic feasible solutions is \( {}^nC_m \).

Step 4: Final Answer:
The maximum number of basic feasible solutions for the given system is \( {}^nC_m \).