# Gate 2001 Math solutions

Q.1.1 Consider the following statements:
S1: The sum of two singular n * n matrices may be non-singular
S2: The sum of two n * n non-singular matrices may be singular.
Which of the following statements is correct?
(A) S1 and S2 are both true
(B) S1 is true, S2 is false
(C) S1 is false, S2 is true
(D) S1 and S2 are both false

Sol : A singular matrix is a square matrix whose determinant is 0. Whenever you solve question related to determinant, think of triangular matrix, like upper triangular matrix, because its determinant is just product of diagonal entries, and so easy to visualize. So definitely, in a singular matrix, one of the entries in diagonal must be zero. Similarly, in non-singular, none of the entries should be zero.

So consider statement S1, if we take two singular matrices, then can their sum be non-singular? Yes, because, consider matrices $$A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 0 & 0 & 4 \\ 0 & 0 & 6 \end{array} \right), B = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 0 & 6 & 4 \\ 0 & 0 & 0 \end{array} \right)$$ Both are singular, but their sum matrix $$C = \left( \begin{array}{ccc} 2 & 4 & 6 \\ 0 & 6 & 8 \\ 0 & 0 & 6 \end{array} \right)$$ is non-singular.

Now consider statement S2, if we consider two non-singular matrices, can their sum be singular matrix ? Yes, intuition is think of matrices such that their diagonal entries cancel each other to make 0. For example, consider matrices $$A = \left( \begin{array}{cc} 1 & 2 \\ 0 & 3 \end{array} \right), B = \left( \begin{array}{cc} 1 & 2 \\ 0 & -3 \end{array} \right)$$ Both are non-singular, but their sum matrix $$C = \left( \begin{array}{cc} 2 & 4 \\ 0 & 0 \end{array} \right)$$ is singular.

So we see that both S1 and S2 are true. So option (A) is correct.

Q.1.2 Consider the following relations:
R1 (a,b) iff (a+b) is even over the set of integers
R2 (a,b) iff (a+b) is odd over the set of integers
R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers
R4 (a,b) iff |a - b| $\le$ 2 over the set of natural numbers
Which of the following statements is correct?
(A) R1 and R2 are equivalence relations, R3 and R4 are not
(B) R1 and R3 are equivalence relations, R2 and R4 are not
(C) R1 and R4 are equivalence relations, R2 and R3 are not
(D) R1, R2, R3 and R4 are all equivalence relations

Sol : So basically, we have to tell whether these relations are equivalence or not.

1. R1(a,b)
• Reflexive : Yes, because (a+a) is even.
• Symmetrix : Yes, (a+b) is even $\implies$ (b+a) is even.
• Transitive : Yes, because (a+b) is even and (b+c) is even $\implies$ (a+c) is even.
So R1 is equivalence relation.
2. R2(a,b)
• Reflexive : No, because (a+a) is even.
So R2 is not equivalence relation.
3. R3(a,b)
• Reflexive : Yes, because a.a > 0.
• Symmetrix : Yes, a.b > 0 $\implies$ b.a > 0.
• Transitive : Yes, because a.b > 0 and b.c > 0 $\implies$ a.c > 0.
So R3 is equivalence relation.
4. R4(a,b)
• Reflexive : Yes, because |a-a| $\le$ 2.
• Symmetrix : Yes, |a-b| $\le$ 2 $\implies$ |b-a| $\le$ 2.
• Transitive : No, because |a-b| $\le$ 2 and |b-c| $\le$ 2 $\nRightarrow$ (a-c) is even.
So R4 is not equivalence relation.
So option (b) is correct.

Q.1.3 Consider two well-formed formulas in prepositional logic F1: P $\Rightarrow$ $\neg$P   F2: (P $\Rightarrow$ $\neg$P) $\vee$ ($\neg$P $\Rightarrow$ P)
Which of the following statements is correct?
(A) F1 is satisfiable, F2 is valid
(B) F1 unsatisfiable, F2 is satisfiable
(C) F1 is unsatisfiable, F2 is valid
(D) F1 and F2 are both satisfiable

Sol : A formula is satisfiable if there is an assignment of truth values which makes that formula true. A formula is unsatisfiable, if there is no such assignment. A formula is valid if for every possible assignment, formula is true i.e. formula is tautology. Now,

• F1 :
• P is true means F1 becomes false.
• P is false means F1 becomes true.
So F1 is satisfiable, but not valid.
• F2 :
• P is true means F2 becomes true.
• P is false means F2 becomes true.
So F2 is valid.
So option (a) is correct.

Q.2.1 How many 4-digit even numbers have all 4 digits distinct?
(A) 2240  (B) 2296  (C) 2620  (D) 4536

Sol : For unit's place, we have 5 choices because of even numbers. If we fix 0 there, then for remaining 3 digits, we have 9*8*7 = 504 choices. If we don't put 0 there, we have 4 choices for unit's place, we have 8 choices for leftmost digit (we can't put 0 there), then for remaining two digits, we have 8*7 = 56 choices, so total 504 + 4*8*56 = 2296. So answer is (B)

Q.2.2. Consider the following statements:
S1: There exists infinite sets A, B, C such that $A\cap(B\cup C)$ is finite.
S2: There exists two irrational numbers x and y such that (x+y) is rational.
Which of the following is true about S1 and S2?
(A) Only S1 is correct
(B) Only S2 is correct
(C) Both S1 and S2 are correct
(D) None of S1 and S2 is correct

Sol : S1 : Correct. Example : A = set of odd numbers, B = set of even positive numbers, C = set of even negative numbers. A, B and C are infinite sets, but $A\cap(B\cup C)$ is $\phi$, which is finite.

S2 : Correct. Example : x = $\sqrt{2}$, y = $-\sqrt{2}$. x and y are irrational, but x+y is 0, which is rational.

So both S1 and S2 are correct, so option (C) is correct.

Q.2.3. Let f: A$\rightarrow$B be a function, and let E and F be subsets of A. Consider the following statements about images.
S1 : f (E ∪ F) = f (E) ∪ f (F)
S1 : f (E ∩ F) = f (E) ∩ f (F)
Which of the following is true about S1 and S2?
(A) Only S1 is correct
(b) Only S2 is correct
(c) Both S1 and S2 are correct
(d) None of S1 and S2 is correct

Sol : S1 : correct, because both L.H.S. and R.H.S. will contain exactly the images of all elements in E and F.
S2 : false, let f is a constant function s.t. range is only {1}. Now let E and F be two partitions of set A, then clearly A ∩ B is φ, and so f (φ) is not defined, but f (E) ∩ f (F) is {1}.
So S1 is true, but S2 is false. So option (A) is correct.

Q.2.4. Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?
(A) $\frac{1}{7^7}$   (B) $\frac{1}{7^6}$   (C) $\frac{1}{2^7}$   (D) $\frac{7}{2^7}$

Sol : Prob(all accidents on Monday) = $\frac{1}{7^7}$. Similarly for other 6 days. So total probability = $\frac{1}{7^7}*7 = \frac{1}{7^6}$. So option (B) is correct. Also see Q.2.16 (2002)