GATE CSE 2016 Set 2 | Question: 04

Question

Consider the systems, each consisting of $m$ linear equations in $n$ variables.

1. If $m < n$, then all such systems have a solution.
2. If $m > n$, then none of these systems has a solution.
3. If $m = n$, then there exists a system which has a solution.

Which one of the following is CORRECT?

• A. $\text{I, II}$ and $\text{III}$ are true.
• B. Only $\text{II}$ and $\text{III}$ are true.
• C. Only $\text{III}$ is true.
• D. None of them is true.

Comments

$I.$ An underdetermined linear system has either no solution or infinitely many solutions.

 

The homogeneous (with all constant terms equal to zero) underdetermined linear system always has non-trivial solutions (in addition to the trivial solution where all the unknowns are zero).

$II.$ An overdetermined system is almost always inconsistent (it has no solution) when constructed with random coefficients. However, an overdetermined system will have solutions in some cases, for example if some equation occurs several times in the system, or if some equations are linear combination of the others.

 

The homogeneous case is always consistent (because there is a trivial, all-zero solution). There are two cases, depending on the number of linearly dependent equations: either there is just the trivial solution, or there is the trivial solution plus an infinite set of other solutions.

$III.$ If m=n, then there exists a system which has a solution.                                                              

 

$\therefore$ Ans: C

---

Hi @KUSHAGRA गुप्ता,

can u pls confirm this point alone:

(i) Over determined system of equations can have no solution or have infinitely many solutions.

But it can Never have a unique solution 

---

This question in GATEOVERFLOW has a typing error. It shall be “Consider the systems” and not “Consider the system”. In GATE each and every word of the question. Rather the inbuilt compiler in my brain is complete crap, it cannot guess the possible correct word and auto-correct the question in my mind and solve the correct question. It is a drawback on my part I guess. Because nowadays, even if there are typing errors in questions in GATE, they do not consider it… (GATE CS 2021: Hamming Code question)

---

Fixed👍

Answer 1

Let's see an intuitive approach to solve this problem i.e. I'll not use the concept of rank here.

Given, m linear equation with n variables. This means we have a m*n matrix.

Case1:  m<n: Let we a take a 2*3 matrix. In this case, we can't the fill the whole space as no of rows < no of columns. If it would've been same, then columns should be linearly independent to always have a solution. So, this statement is False.

Case2: m>n: Let we take a 3*2 matrix. In this case, if b is linear combination of columns of matrix A, then there would be a solution. So, we can't say here none of the system have a solution. So, this statement is False.

Case3: m=n: Let we take a 3*3 matrix. In this case we have no of columns = no of rows. If we have n LI columns, then there is always a solution. So, this statement is true.

PS: Working approach in these types of questions is simple. We just need to care of "Quantifiers." Keywords like "ALL", "At least", "Always", "NEVER" can be used to interpret the behavior of system and we can solve using the intuition.

Answer 2

To solve this question there are 2 methods 

Option-A :  False

Given m<n let us assume 3X4 matrix

A11   A21   A31

B12   B22   B32

C13   C23   C33

D14   D24   D34

They did not mentioned weather the column space is filled or not.

If they mentioned column space is filled then  definitely solution exist.

They did not mentioned about column space so the column space may or may not be filled.

So solution may or may not exist 

 

So all such system have such solution is false. 

Option-B: False

 

Given m>n let us assume 4>3

A11   A21   A31   A41

B12   B22   B32   B42

C13   C23   C33   c43

In this the column space did not filled 

 

Then solution may or may not exits 

So none of the system has solution is False

 

Option-3: True 

 

Given m=n let us take 3X3 

 

So the column space is filled or column space did not filled is mentioned 

 

So the solution may or may not exist 

 

There exist a solution is correct

Option - c is correct

Method-2:

Option-A :  False

Given m<n let us assume 3X4 matrix

P   -   0

-   P   0

-   -   0

-   -   B

In this case there will be no solution . 

So always have solution is Not correct

Option-B: False 

Given m>n let us take 4X3 

P	-	-	-	-
-	P	-	-	-
-	-	P	-	-

In this case because of a free variable infinite solution is possible

 

So none of the system has solution is false 

 

Option-C : True 

 

If we consider a 3X3 matrix and each row has pivot then there exist a solution.

So this option is correct .

If they mentioned always solution exist then it will be wrong

 

So option-C is correct

Answer 3

Answer D:

I & II are false already but similarly for III also 

 for the case of two parallel lines example y=x+5 and y=x+6 for these equations no solution so c should also be false.

Hence D is correct ans.

Comments

You need to read the statement III) Clearly. What you are deducing is incorrect ! If m = n , the there exists a system which has a solution

* there exists *

Counter example is used for disproving, for all, not * there exists *

---

If the option III would have said : “There exists a solution for the system...” then it would have been wrong. But it says “There exists a system which has solution” then indeed there could be “some” of the systems for which there exists solution