Engineering Mathematics

Why this unit matters

Engineering Mathematics is not a warm-up section, it is consistently one of the highest-weightage units in GATE CS, contributing around 13-15 marks spread across both 1-mark and 2-mark questions. The questions test precision: a missed sign, a wrong base of logarithm, or forgetting a boundary condition will cost you the mark. The good news is that the topics are finite and well-defined. Once you build the right mental models, this unit becomes one of the most reliable sources of marks.

Expect questions on: truth table evaluation, graph colouring and matching, recurrence solutions, eigenvalue arithmetic, probability distributions, and Bayes' theorem. Numerical questions here are often shorter than they look, the trick is recognising the right formula quickly.

Syllabus map

Discrete Mathematics
- Propositional logic: truth tables, tautology, contradiction, logical equivalences
- First-order logic (FOL): quantifiers, predicates, scope
- Sets, relations, functions: types of relations (reflexive, symmetric, transitive, equivalence), types of functions (injective, surjective, bijective)
- Partial orders and lattices: Hasse diagrams, POSET properties
- Algebraic structures: monoids, groups, abelian groups, subgroups
- Graph theory: connectivity, Euler/Hamiltonian paths, matching (bipartite), graph colouring, chromatic number, planar graphs
- Combinatorics: counting principles, pigeonhole, permutations and combinations, recurrence relations (homogeneous and non-homogeneous), generating functions
Linear Algebra
- Matrix operations, transpose, inverse
- Determinants: properties, cofactor expansion
- System of linear equations: Gaussian elimination, rank-nullity theorem
- Eigenvalues and eigenvectors: characteristic polynomial, diagonalisation
- LU decomposition
Calculus
- Limits and continuity
- Differentiability, chain rule, implicit differentiation
- Maxima and minima: first and second derivative tests
- Mean value theorem (MVT) and Rolle's theorem
- Integration: definite and indefinite, substitution, parts
Probability and Statistics
- Random variables: discrete and continuous
- Distributions: uniform, normal, exponential, Poisson, binomial
- Mean, median, mode, variance, standard deviation
- Conditional probability, independence
- Bayes' theorem

Discrete Mathematics

Propositional Logic

A proposition is a statement that is either true or false. The standard connectives are:

Symbol	Meaning	False when
NOT (¬)	negation	,
AND (∧)	conjunction	at least one operand is false
OR (∨)	disjunction	both operands are false
→	implication	antecedent true, consequent false
↔	biconditional	operands differ

Key equivalences to memorise:

p → q is equivalent to ¬p ∨ q
¬(p → q) is equivalent to p ∧ ¬q
De Morgan: ¬(p ∧ q) = ¬p ∨ ¬q; ¬(p ∨ q) = ¬p ∧ ¬q

Typical GATE trap: Confusing p → q with q → p. They are not equivalent; the contrapositive ¬q → ¬p is equivalent to p → q.

Worked example: Check if (p → q) ↔ (¬q → ¬p) is a tautology.

p  q  | p→q | ¬q→¬p | biconditional
T  T  |  T  |   T   |     T
T  F  |  F  |   F   |     T
F  T  |  T  |   T   |     T
F  F  |  T  |   T   |     T

All rows are T, so it is a tautology. The implication and its contrapositive are always logically equivalent.

First-Order Logic

FOL adds predicates and quantifiers over propositional logic., Universal quantifier: ∀x P(x), P holds for every x in the domain., Existential quantifier: ∃x P(x), P holds for at least one x.

Negation rules: ¬∀x P(x) = ∃x ¬P(x) and ¬∃x P(x) = ∀x ¬P(x).

Typical GATE trap: Moving a quantifier past a connective, ∀x (P(x) ∨ Q(x)) does NOT imply (∀x P(x)) ∨ (∀x Q(x)).

Sets, Relations, and Functions

A relation R on set A is:

Reflexive if ∀x, xRx
Symmetric if xRy → yRx
Antisymmetric if xRy ∧ yRx → x = y
Transitive if xRy ∧ yRz → xRz
Equivalence relation = reflexive + symmetric + transitive
Partial order = reflexive + antisymmetric + transitive

Number of relations on a set of n elements: 2^(n^2). Number of equivalence relations is the Bell number B(n).

Typical GATE trap: "Irreflexive" does not mean "not reflexive" in the strong sense, a relation can be neither reflexive nor irreflexive.

Graph Theory

Key theorems:

Handshaking lemma: Sum of all vertex degrees = 2 * |E|. Hence number of odd-degree vertices is always even.
Euler circuit exists iff graph is connected and every vertex has even degree.
Euler path (not circuit) exists iff exactly 2 vertices have odd degree.
Planar graph: |E| <= 3|V| - 6 (for |V| >= 3); |E| <= 2|V| - 4 if bipartite.
Four colour theorem: Every planar graph is 4-colourable.
Chromatic number of complete graph K_n: n.

Bipartite matching: A bipartite graph has a perfect matching iff Hall's condition holds.

Typical GATE trap: A tree with n vertices has exactly n-1 edges. Don't confuse tree edges with graph edges when computing degree sequences.

Combinatorics and Recurrence

Counting basics:

Permutations: P(n,r) = n! / (n-r)!
Combinations: C(n,r) = n! / (r!(n-r)!), Stars and bars: distributing n identical items into k distinct bins = C(n+k-1, k-1)

Recurrence relations: For a linear homogeneous recurrence with constant coefficients T(n) = aT(n-1) + bT(n-2), find the characteristic roots r1, r2. If r1 != r2: T(n) = A*r1^n + B*r2^n. If r1 = r2 = r: T(n) = (A + Bn)*r^n.

Worked example: Solve T(n) = 5T(n-1), 6T(n-2), T(0) = 1, T(1) = 0.

Characteristic equation: r^2, 5r + 6 = 0 → r = 2 or r = 3. General solution: T(n) = A2^n + B3^n. T(0) = A + B = 1; T(1) = 2A + 3B = 0 → B = -2, A = 3. So T(n) = 32^n, 23^n.

Linear Algebra

Matrices and Determinants

For a 2x2 matrix [[a,b],[c,d]], determinant = ad, bc.

Properties of determinants:

det(AB) = det(A) * det(B), det(A^T) = det(A), If a row/column is all zeros, det = 0, Row swap flips sign; row scaling multiplies det by that scalar

Rank: The rank of a matrix equals the number of non-zero rows in its row echelon form. For Ax = b: consistent iff rank(A) = rank(augmented matrix [A|b]).

Eigenvalues and Eigenvectors

For matrix A, eigenvalue lambda satisfies det(A - lambda*I) = 0 (characteristic equation).

Key facts:

Sum of eigenvalues = trace(A) (sum of diagonal elements), Product of eigenvalues = det(A), If A is triangular, eigenvalues are the diagonal entries

Worked example: Find eigenvalues of A = [[4,1],[2,3]].

det(A, lambdaI) = (4, lambda)(3, lambda), 2 = lambda^2, 7lambda + 10 = 0 lambda = 2 or lambda = 5. Trace = 7, product = 10. Both check out.

Typical GATE trap: Eigenvectors are not unique, any non-zero scalar multiple is also an eigenvector. GATE often asks for the eigenvalue, not the vector itself.

LU Decomposition

LU decomposes A = L*U where L is lower triangular with 1s on diagonal and U is upper triangular. Used to solve Ax = b efficiently for multiple right-hand sides: solve Ly = b (forward substitution), then Ux = y (back substitution). Each solve is O(n^2) after O(n^3) decomposition.

Calculus

Limits and Continuity

A function f is continuous at x = a if: the limit exists, f(a) is defined, and lim(x→a) f(x) = f(a). Differentiability implies continuity, but not vice versa.

Mean Value Theorem: If f is continuous on [a,b] and differentiable on (a,b), then there exists c in (a,b) such that f'(c) = (f(b) - f(a)) / (b - a).

Rolle's Theorem: Special case of MVT where f(a) = f(b), guaranteeing f'(c) = 0 for some c.

Maxima and Minima

At a critical point c where f'(c) = 0:

If f''(c) > 0: local minimum, If f''(c) < 0: local maximum, If f''(c) = 0: use higher derivatives or first derivative sign test

Typical GATE trap: A critical point is not guaranteed to be a local extremum, saddle points exist for multivariable functions.

Probability and Statistics

Distributions

Distribution	PMF / PDF	Mean	Variance
Binomial(n,p)	C(n,k) p^k (1-p)^(n-k)	np	np(1-p)
Poisson(lambda)	e^(-lambda) lambda^k / k!	lambda	lambda
Uniform[a,b]	1/(b-a)	(a+b)/2	(b-a)^2/12
Exponential(lambda)	lambda * e^(-lambda*x)	1/lambda	1/lambda^2
Normal(mu, sigma^2)	(1/sqrt(2pi)sigma) e^(-(x-mu)^2/(2*sigma^2))	mu	sigma^2

Bayes' Theorem

P(A | B) = P(B | A) * P(A) / P(B)

where P(B) = P(B|A)*P(A) + P(B|¬A)*P(¬A).

Worked example: A factory has two machines M1 (60% of output, 2% defect rate) and M2 (40% of output, 5% defect rate). A randomly picked item is defective. What is the probability it came from M2?

P(defect) = 0.6*0.02 + 0.4*0.05 = 0.012 + 0.020 = 0.032
P(M2 | defect) = (0.05 * 0.4) / 0.032 = 0.020 / 0.032 = 0.625

So there is a 62.5% chance the defective item came from M2.

Worked Examples

Example 1 (Graph Theory): A connected graph G has 10 vertices, each with degree 4. How many edges does G have?

Sum of degrees = 10 * 4 = 40. By handshaking lemma, |E| = 40 / 2 = 20 edges.

Example 2 (Linear Algebra): For the system 2x + 3y = 7, 4x + 6y = 14, find the number of solutions.

Augmented matrix: [[2,3|7],[4,6|14]]. Row 2 = 2 * Row 1, so rank(A) = rank([A|b]) = 1 < 2 (number of unknowns). The system has infinitely many solutions.

Example 3 (Probability): X is a Poisson random variable with mean 3. Find P(X = 2).

P(X = 2) = e^(-3) * 3^2 / 2! = e^(-3) * 9 / 2 = 4.5 * e^(-3) ≈ 4.5 * 0.0498 ≈ 0.224.

Example 4 (Combinatorics): In how many ways can 8 students be divided into two groups of 4?

C(8,4) / 2! = 70 / 2 = 35. We divide by 2 because the groups are unlabelled (order of groups does not matter).

Example 5 (Eigenvalues): Matrix A = [[2,0,0],[0,3,0],[0,0,5]]. What is det(A^3)?

A is diagonal, so det(A) = 235 = 30. det(A^3) = (det A)^3 = 30^3 = 27000.

Quick-revision Summary

p → q ≡ ¬p ∨ q; contrapositive ¬q → ¬p is always equivalent to p → q
Equivalence relation = reflexive + symmetric + transitive, Partial order = reflexive + antisymmetric + transitive, Sum of degrees = 2|E| (handshaking lemma), Euler circuit: all vertices even degree; Euler path: exactly 2 odd-degree vertices, Sum of eigenvalues = trace; product of eigenvalues = determinant, For Ax = b: consistent iff rank(A) = rank([A|b]), Binomial mean = np; Poisson mean = lambda = variance, Exponential mean = 1/lambda; memoryless property, Bayes': P(A|B) = P(B|A)*P(A) / P(B), Recurrence T(n) = aT(n-1) + bT(n-2): solve characteristic polynomial, LU decomposition solves Ax = b in O(n^2) per right-hand side after O(n^3) setup, MVT guarantees a tangent slope equal to the secant slope on (a,b)

How to Study this Unit

Do not skip discrete maths. Graph theory and logic alone account for 4-6 marks in most years. Solve every GATE PYQ on these topics from 2010 onwards, the question patterns repeat.
For linear algebra, practise eigenvalue shortcuts. Learn to read off eigenvalues from triangular matrices and use trace/determinant checks to verify your work before moving to the next question.
Probability needs formula fluency, not derivations. Memorise the mean and variance of all five listed distributions. For Bayes' questions, always write the law of total probability first before substituting.
Calculus questions are often disguised. A question about "number of real roots" uses Rolle's theorem. A "maximum throughput" question uses first/second derivative tests. Learn to spot the calculus beneath the CS framing.
Recurrences: practise the Master Theorem from Unit 5 alongside this. GATE often uses recurrences in algorithm analysis; knowing the solution methods from both sides saves time.
Time yourself. Set a 2-minute limit per question when doing PYQs. Engineering Mathematics questions should be solved quickly, spending 5 minutes on a 1-mark probability question is a paper management error.