GATE CSE 1996 | Question: 1.7

Question

Let $Ax = b$ be a system of linear equations where $A$ is an $m \times n$ matrix and $b$ is a $m \times 1$ column vector and $X$ is an $n \times1$ column vector of unknowns. Which of the following is false?

• A. The system has a solution if and only if, both $A$ and the augmented matrix $[Ab]$ have the same rank.

• B. If $m < n$ and $b$ is the zero vector, then the system has infinitely many solutions.

• C. If $m=n$ and $b$ is a non-zero vector, then the system has a unique solution.

• D. The system will have only a trivial solution when $m=n$, $b$ is the zero vector and $\text{rank}(A) =n$.

Comments

Corrected.

---

Ans:C

---

A) True

B) The homogeneous (with all constant terms equal to zero) underdetermined linear system always has non-trivial solutions.

https://en.wikipedia.org/wiki/Underdetermined_system

C) Can't claim anything about the nature of solution.

D) True

$A_{n*n}X_{n*1}$=0 & |A|$\neq$ 0 & $\rho (A)=n$, then trivial solution

---

In option b they are talking about homogenous system of equation but how it can be infinite no of solution when nothing is given about rank .solution is infinite when rank<no of unknown.no such thing is given in option so how we can decide it is correct??

Answer 1

Answer is $C$ because it is a case of linear non-homogeneous equations. By having m = n, we can't say that it will have unique solution. Solution depends on rank of matrix A and matrix [A B].

If rank[ A ] = rank[A B], then it will have solution, otherwise no solution

Comments

option d is right because , rank of the matrix = n which means the the number of linearly independent vectors is n. If we have only linearly independent vectors in the matrix  then the only values of X=( x1,x2,x3) that is going to satisfy AX=0 will be 0,0,0. No other values of x1,x2,x3 is going to satisfy AX=0

so why they have given that when the rank = n ,  only trivial solution exist for AX=0

---

AX = 0 , here X has trivial solution only if |A| !=0.
Now m=n means let's say the order of the matrix is n*n. Now rank(A) = n means smallest submatrix which have n*n order have determinant not equals to 0 which is the matrix A itself as m=n. i.e |A| != 0.

So option d is right.

---

how to check option B?

Answer 2

A. It is true, either system will have unique or infinitely many solutions, but system is consistent.
B. Rank of matrix will be less than the number of unknowns and it's an homogenous system of linear equations, So, this is also true.
C. It may not be true, homogenous system may have infinite number of solutions.
D. It's an homogenous system, number of unknowns are equal to the rank, hence the system will have unique solution.

Hence, (C) is false!

Comments

Hello manu

in 'c' he is talking about non-homo system , see b is non-zero vector.

Answer 3

Consider a matrix $A_{3X4}$ = $\begin{bmatrix} 1 & 3& 3 &2 \\ 2& 6 & 9&7 \\ -1 &-3 &3 & 4 \end{bmatrix}$

The Echelon form of this matrix after Row operations

$R_2=R_2-2R_1$

$R_3=R_3+R_1$

$R_3=R_3-2R_2$

would be

$\begin{bmatrix} 1 & 3& 3 &2 \\ 0& 0 & 3&3\\ 0 &0 &0 & 0 \end{bmatrix}$

Now, we have our system $Ax=b$

which can be represented as

$\begin{bmatrix} 1 & 3& 3 &2 \\ 2& 6 & 9&7 \\ -1 &-3 &3 & 4 \end{bmatrix}$.$\begin{bmatrix} u\\ v\\ w\\ y \end{bmatrix}=\begin{bmatrix} b_1\\ b_2\\ b_3 \end{bmatrix}$

Perform the same Row operations as listed above and then it becomes

$\begin{bmatrix} 1 & 3 & 3 & 2\\ 0&0 & 3 & 3\\ 0&0 & 0 & 0 \end{bmatrix}.\begin{bmatrix} u\\ v\\ w\\ y \end{bmatrix}=\begin{bmatrix} b_1\\ b_2-2b_1\\ b_3-2b_2+5b_1 \end{bmatrix}$

Let this system be $Ux=c$

Now, your system would be consistent, if $b_3-2b_2+5b_1=0$ which validates option (A).

Option (B), says if $Ax=0$ then this system has infinitely many solutions and yes, because you take any constant $c \not=0$,

$Acx=0$

Option(D) says if A is an nxn matrix and rank(A)=n, means all the rows and columns of A are linearly independent, then there is no such non-zero vector that can take some combinations of columns of A and produce a zero vector. And, thus the only solution to $Ax=0$ is the vector $X=0$ which is a trivial solution, so this option is true.

Option(C) asserts that if m=n and b is a non-zero vector, then system has unique solution which is clearly false.

Why?

For the system, $Ax=b$ to have a solution for a non-zero b, the vector b must be such that it can be produced by some linear combinations of columns of A.This means, b must be in the Column Space of A.

In the above system $Ux=c$ it has a solution  when  $c=$$\begin{bmatrix} 1(b_1))\\ 5(b_2)\\ 5(b_3) \end{bmatrix}$ and it is inconsistent, means does not have a solution when $c=$$\begin{bmatrix} 1(b_1))\\ 5(b_2)\\ 6(b_3) \end{bmatrix}$

Hence, Option (C) is the answer.

Comments

Appreciated.

Thanks

---

@Ayush Upadhyaya Is there any good reference for this concept??

---

@MRINMOY_HALDER-Gilbert strang lectures plus his book

Answer 4

Answer: C is $False$

Given:

$Ax=b$ (System of Linear Equations)

Where:

$A = \begin{bmatrix}
a_{11} & ... & a_{1n}\\ 
\vdots &\vdots &\vdots\\ 
a_{m1} & ... & a_{mn}
\end{bmatrix}_{m\times n}$

$b=\begin{bmatrix}
b_1\\ 
\vdots \\ 
b_m
\end{bmatrix}_{m \times 1}$ 

$X=\begin{bmatrix}
x_1\\ 
\vdots \\ 
x_n
\end{bmatrix}_{n \times 1}$

We will go through each option one-by-one.

A. The system has a solution if and only if, both $A$ and the augmented matrix $[A|b]$ have the same rank:

$=>$ if $Rank(A) = Rank(A|b)$, it means that $b$ can be interpreted as Linear combination of $A$

$=>$ Therefore Solution exists.

$=>$ $True$

 

B. If $m<n$ and $b$ is the zero vector, then the system has infinitely many solutions.

$=>$ Assume $m=2$ and $n=3$

$=>$ $\begin{bmatrix}
a_{11} & a_{12} & a_{13} & : 0\\ 
a_{21} & a_{22} & a_{23} & : 0 
\end{bmatrix}$

$=>$ max rank possible is always $min(m,n) = min(2,3) = 2$

$=>$ We got one (atleast) free variable, and this free variable can take infinitely many values

$=>$ System has infinitely many solutions

$=>$ $True$

 

C. If $m=n$ and $b$ is a non-zero vector, then the system has a unique solution.

$=>$ We can’t say really as it might be possible that one column or row is dependent on the other

$=>$ Example, assume matrix of $m=n=3$

$=>$ $\begin{bmatrix}
a_{11} & 2a_{11} & a_{13} & :b_1\\ 
a_{21} & 2a_{21} & a_{23} & :b_2\\ 
a_{31} & 2a_{31} & a_{33} & :b_3 
\end{bmatrix}$

$=>$ Even if we have $m=n$ here, we can clearly say that $column_2$ is just $2\times column_1$

$=>$ No unique solution exists

$=>$ $False$

 

D. The system will have only a trivial solution when $m=n$, $b$ is the zero vector and $rank(A)=n$.

$=>$ Since, $rank(A)=n$, all the columns are having pivot

$=>$ All columns are having pivot means all columns are Linearly Independent

$=>$ Thus only possible solution to get a zero vector $b$ would be to multiply each column with $0$ in $A$, no other possibility

$=>$ When we multiply every column with $zero$, it becomes $Trivial$ $Solution$

$=>$ $True$