How to read these notes: Mathematics cannot be learnt by reading alone — it must be solved with pen and paper. Every concept below is followed by a "🧮 Solved Example" with every intermediate step written out. Try the example yourself first, then compare. Each unit ends with a formula card (last-minute revision) and practice set exam questions with marks. Yaad rakho: definition + formula + ek solved example — yahi teen cheezein answer me marks dilati hain.
UNIT 1 — Matrix Algebra
1.1 Matrix — Definition, Order & Types
Definition (Matrix). A matrix is a rectangular arrangement of numbers or elements in rows and columns, enclosed in brackets. A matrix is generally represented by a capital letter such as A, B, C. The elements of a matrix are represented by aij, where i = row number and j = column number.
A matrix having m rows and n columns is called a matrix of order m × n:
A = [ a11 a12 ... a1n
a21 a22 ... a2n
. . . .
am1 am2 ... amn ] order = m × n
Element notation: aij lies in the i-th row and j-th column, where i = 1, 2, ..., m and j = 1, 2, ..., n. A matrix is also written compactly as A = [aij]m×n.
In simple words: A matrix is just a table of numbers 📊 — like a marks-table of students. "3 students, 4 subjects ka marks" = a 3 × 4 matrix. Element a23 means "2nd row, 3rd column wala number" — pehle row, phir column; yahi convention hamesha follow karo.
Solved Example — reading the elements of a matrix:
A = [ 1 2 3
-2 3 5
-3 -5 4 ]
This is a 3 × 3 matrix (3 rows, 3 columns).
a11 = 1 a12 = 2 a13 = 3
a21 = -2 a22 = 3 a23 = 5
a31 = -3 a32 = -5 a33 = 4
Number of elements = 3 × 3 = 9 ✔
(a) Order of a Matrix
Order of a matrix is written as m × n, where m = number of rows and n = number of columns. Total number of elements in the matrix = m × n.
Solved Example:
A = [ 1 2 3
4 5 6 ]
It has 2 rows and 3 columns.
Therefore its order is 2 × 3 (not 3 × 2 — rows are always written first).
Total elements = 2 × 3 = 6 ✔
B = [ 1 ] → order 1 × 1
[ 0 ]
C = [ 4 5 6 ] → order 1 × 3
D = [ 7 ] → order 3 × 1
[ 8 ]
[ 9 ]
(b) Equality of Two Matrices
Two matrices A and B are equal (A = B) if and only if: (i) they have the same order, and (ii) their corresponding elements are equal, i.e. aij = bij for every i, j.
Solved Example:
If [ x + 1 3 ] = [ 5 3 ]
[ 4 z ] [ 4 y - 1 ]
then (comparing corresponding elements):
x + 1 = 5 → x = 4
z = y - 1 → infinitely many (x, y) pairs, e.g. y = 3 → z = 2
This "compare the elements" trick solves many exam questions. ✔
(c) Sub-Matrix
A sub-matrix of a matrix is a matrix obtained by deleting one or more rows and/or one or more columns of the given matrix.
Solved Example:
A = [ 3 5 6 7
2 3 0 1
7 9 7 8 ]
Delete row 2 and column 3:
[ 3 5 7 ] This 2 × 3 matrix is a sub-matrix of A.
[ 7 9 8 ]
Delete only row 1:
[ 2 3 0 1 ] This 1 × 4 matrix is also a sub-matrix.
[ 7 9 7 8 ]
Note: Every element aij is itself a 1 × 1 sub-matrix. Minors (Section 1.3) are
determinants of square sub-matrices — yahi concept aage kaam aayega. ✔
(d) Transpose of a Matrix
The transpose of a matrix is obtained by changing its rows into columns and its columns into rows. The transpose of A is denoted by Aᵀ (also written A′). In terms of elements: (aij)ᵀ = aji. If A has order m × n, then Aᵀ has order n × m.
Solved Example:
A = [ 1 2 3 ] (2 × 3)
[ 4 5 6 ]
Aᵀ = [ 1 4 ] (3 × 2) ← rows became columns
[ 2 5 ]
[ 3 6 ]
Check the element rule: a12 = 2 and (a21)ᵀ = 2 ✔
Important: (Aᵀ)ᵀ = A (double transpose gives back the original matrix).
(e) Types of Matrices
Type
Definition
Example
Row matrix
Only 1 row (order 1 × n)
[2 5 7]
Column matrix
Only 1 column (order m × 1)
[2; 5; 7] written vertically
Square matrix
Rows = columns (order n × n)
2 × 2, 3 × 3
Rectangular matrix
Rows ≠ columns
2 × 3, 3 × 4
Zero / Null matrix
All elements are 0, denoted O
[0 0; 0 0]
Diagonal matrix
Square matrix in which all non-diagonal elements are 0
diag(5, 6, 7)
Scalar matrix
Diagonal matrix in which all diagonal elements are equal
diag(5, 5, 5)
Identity matrix (I)
Diagonal elements = 1, remaining elements = 0
I₂ = [1 0; 0 1]
Upper triangular
All elements below the main diagonal are 0 (aij = 0 for i > j)
[5 4 0; 0 6 7; 0 0 8]
Lower triangular
All elements above the main diagonal are 0 (aij = 0 for i < j)
[5 0 0; 4 6 0; −1 2 3]
Symmetric
Aᵀ = A, i.e. aij = aji
diagonal mirror values equal
Skew-symmetric
Aᵀ = −A, i.e. aij = −aji (diagonal elements all 0)
[0 4 −3; −4 0 5; 3 −5 0]
Singular matrix
Square matrix with determinant 0 (inverse does not exist)
|A| = 0
Non-singular matrix
Square matrix with determinant ≠ 0 (inverse exists)
|A| ≠ 0
Orthogonal matrix
Square matrix with A·Aᵀ = Aᵀ·A = I (so Aᵀ = A−1)
rotation matrices
Each type in detail, with the element condition (exam me definition + condition likhna hai):
1. Row Matrix
A matrix having only one row is called a row matrix.
Example: A = [ 1 2 3 4 ] → order 1 × 4
2. Column Matrix
A matrix having only one column is called a column matrix.
Example: A = [ 1 ] → order 4 × 1
[ 2 ]
[ 3 ]
[ 4 ]
3. Square Matrix
A matrix having an equal number of rows and columns is called a square matrix.
Example: A = [ 2 0 1 ] → order 3 × 3
[ 1 3 7 ]
[ 5 4 3 ]
For a square matrix the diagonal a11, a22, a33, ... is called the MAIN DIAGONAL.
4. Rectangular Matrix
A matrix in which the number of rows and columns are NOT equal.
Example: A = [ 1 2 3 ] → order 2 × 3
[ 4 5 6 ]
5. Identity Matrix (I)
A square matrix in which all the diagonal elements are 1 and all the
remaining elements are 0 is called an identity matrix. Denoted by I (or Iₙ).
I₂ = [ 1 0 ] I₃ = [ 1 0 0 ]
[ 0 1 ] [ 0 1 0 ]
[ 0 0 1 ]
In terms of elements: aij = 1, if i = j
aij = 0, if i ≠ j
Property: A·I = I·A = A (identity matrix works like the number 1).
6. Null Matrix / Zero Matrix
A matrix in which ALL the elements are zero is called a null/zero matrix (O).
Example: A = [ 0 0 0 ]
[ 0 0 0 ]
[ 0 0 0 ]
Property: A + O = O + A = A (additive identity — Section 1.2).
7. Diagonal Matrix
A square matrix in which all the NON-diagonal elements are zero.
Example: A = [ 5 0 0 ]
[ 0 6 0 ]
[ 0 0 7 ]
Condition: aij = 0, if i ≠ j (diagonal elements may or may not be zero)
8. Scalar Matrix
A diagonal matrix in which all the diagonal elements are EQUAL.
Example: A = [ 5 0 0 ]
[ 0 5 0 ]
[ 0 0 5 ]
Note: A scalar matrix = k·I (here k = 5). Order of inclusion:
Identity ⊂ Scalar ⊂ Diagonal ⊂ Square.
9. Upper Triangular Matrix
A square matrix in which all the elements BELOW the main diagonal are zero.
Example: A = [ 5 4 0 ]
[ 0 6 7 ]
[ 0 0 8 ]
Condition: aij = 0, if i > j
10. Lower Triangular Matrix
A square matrix in which all the elements ABOVE the main diagonal are zero.
Example: A = [ 5 0 0 ]
[ 4 6 0 ]
[ -1 2 3 ]
Condition: aij = 0, if i < j
Useful fact: For any triangular matrix, determinant = product of diagonal elements.
Solved Example — Symmetric matrix (verify A = Aᵀ):
A = [ 5 2 3 ]
[ 2 4 8 ]
[ 3 8 6 ]
Here: a12 = a21 = 2
a13 = a31 = 3
a23 = a32 = 8
Aᵀ = [ 5 2 3 ]
[ 2 4 8 ] = A
[ 3 8 6 ]
Therefore A = Aᵀ, hence A is a SYMMETRIC matrix. ✔
Check the diagonal: a11 = 5, a22 = 4, a33 = 6 — diagonal elements can be anything.
Solved Example — Skew-symmetric matrix (verify A = −Aᵀ):
A = [ 0 4 -3 ]
[ -4 0 5 ]
[ 3 -5 0 ]
Here: a12 = 4, a21 = -4 → a21 = -a12 ✔
a13 = -3, a31 = 3 → a31 = -a13 ✔
a23 = 5, a32 = -5 → a32 = -a23 ✔
Aᵀ = [ 0 -4 3 ]
[ 4 0 -5 ] -Aᵀ = [ 0 4 -3 ]
[ -3 5 0 ] [ -4 0 5 ] = A
[ 3 -5 0 ]
Therefore A = −Aᵀ, hence A is a SKEW-SYMMETRIC matrix. ✔
Remember: in a skew-symmetric matrix every diagonal element must be zero
(a11 = a22 = a33 = 0), because aii = −aii → 2aii = 0 → aii = 0.
Mnemonics:
• Triangular: "Upper ke neeche SAB zero, Lower ke upar SAB zero" — the name tells you where the zeros are NOT.
• Symmetric = Mirror (aij = aji) • Skew-symmetric = Mirror with a minus sign (aij = −aji), so diagonal becomes 0.
• Hierarchy to memorise once: Identity ⊂ Scalar ⊂ Diagonal ⊂ Square (every identity matrix is scalar, every scalar is diagonal, every diagonal is square, but not the reverse).
Where this is used in Computer Science: (1) A grayscale image is a matrix of pixel values; a colour image is three such matrices (R, G, B). (2) Google PageRank = eigenvector of a matrix (Section 1.7). (3) Every 3D object in a game is rotated/scaled with matrix multiplication. (4) A neural network layer is nothing but Y = WX + b — a matrix multiplication. (5) Adjacency matrices represent graphs and networks; symmetric matrices appear naturally for undirected graphs (A = Aᵀ).
1.2 Algebra of Matrices — Addition, Subtraction and Multiplication
(a) Addition of Matrices
Two matrices can be added only when they have the same order. If A = [aij]m×n and B = [bij]m×n, then
A + B = [ aij + bij ] m×n
In matrix addition, corresponding elements are added. The sum matrix also has order m × n.
Solved Example:
A = [ 2 3 ] B = [ 1 2 ]
[ 5 6 ] [ 3 4 ]
A + B = [ 2+1 3+2 ] = [ 3 5 ]
[ 5+3 6+4 ] [ 8 10 ]
Therefore A + B = [ 3 5 ]
[ 8 10 ] ✔
Order check: (2 × 2) + (2 × 2) → 2 × 2 ✔
Important: If two matrices do not have the same order, their addition is not defined. For example, a 2 × 3 matrix and a 2 × 4 matrix cannot be added (3 ≠ 4). Order same hona zaroori hai — warna answer "not defined" likhna hai, kuch calculate karne ki zaroorat nahi.
(b) Subtraction of Matrices
Matrix subtraction is similar to matrix addition: two matrices can be subtracted only when they have the same order. If A = [aij] and B = [bij] are of the same order, then
A - B = [ aij - bij ] m×n
Solved Example:
[ 2 ] [ 3 ] [ 2-3 ] [ -1 ]
[ 2 ] - [ -3 ] = [ 2-(-3) ] = [ 5 ]
Careful with signs: subtracting a negative number means ADDING it. ✔
2 × 2 example:
A = [ 6 4 ] B = [ 1 2 ] A - B = [ 5 2 ]
[ 2 8 ] [ 3 4 ] [ -1 4 ]
(c) Additive Identity
For every matrix A of order m × n there exists a null matrix O of the same order such that
A + O = O + A = A
The zero matrix O is called the additive identity for matrices (just like 0 is the additive identity for numbers).
Solved Example:
A = [ 5 6 0 ] O = [ 0 0 0 ]
[ 0 5 2 ] [ 0 0 0 ]
A + O = [ 5 6 0 ] = A ✔
[ 0 5 2 ]
(d) Additive Inverse
For every matrix A of order m × n there exists a matrix −A (negative of A, obtained by changing the sign of every element) such that
A + (-A) = (-A) + A = O
The matrix −A is called the additive inverse of A. Note: additive inverse always exists (no condition), unlike the multiplicative inverse.
If k is a scalar (a number) and A = [aij] is a matrix, then kA = [k·aij] — every element gets multiplied by k. Properties: k(A + B) = kA + kB, (k + l)A = kA + lA, (kl)A = k(lA), 1·A = A, 0·A = O, (−1)A = −A.
Solved Example:
A = [ 2 3 ] 3A = [ 6 9 ] -2A = [ -4 -6 ]
[ 1 4 ] [ 3 12 ] [ -2 -8 ]
Also: |kA| = kⁿ|A| for an n × n matrix (see Section 1.3, Property 9).
(f) Matrix Multiplication
Condition for multiplication: Let A = [aij]m×n and B = [bij]n×p. The product AB is defined only when
Number of columns of A = Number of rows of B (i.e. n = n)
If it is defined, then AB = C where C has order m × p, and
cij = Σ(k = 1 to n) aik · bkj
i.e. cij = (i-th row of A) · (j-th column of B) = ai1b1j + ai2b2j + ... + ainbnj.
Trick — "inner numbers must match, outer numbers give the order": (m × n) · (n × p) → answer m × p. Inner numbers equal → multiplication possible; inner numbers vanish, outer numbers remain in the answer. Yaad rakho: "andar wale gayab, bahar wale raja" 😄
Solved Example 2 — 2 × 3 times 3 × 2 (order changes):
A = [ 1 2 3 ] B = [ 7 8 ]
[ 4 5 6 ] [ 9 1 ] Check: A is 2 × 3, B is 3 × 2
[ 2 3 ] Inner numbers 3 = 3 → defined
Answer will be 2 × 2
AB = [ 1(7)+2(9)+3(2) 1(8)+2(1)+3(3) ]
[ 4(7)+5(9)+6(2) 4(8)+5(1)+6(3) ]
= [ 7+18+6 8+2+9 ] = [ 31 19 ]
[ 28+45+12 32+5+18 ] [ 85 55 ] ✔
Notice: here BA is also defined (3 × 2 times 2 × 3 = 3 × 3) but BA ≠ AB —
and even its ORDER is different (3 × 3, not 2 × 2).
Solved Example 3 — when multiplication is NOT defined:
A = 2 × 3 matrix B = 4 × 3 matrix
Number of columns of A = 3, number of rows of B = 4
Since 3 ≠ 4, AB is NOT defined. ✔ (Answer likho: "AB not defined".)
But BA = (4 × 3)(2 × 3)? Columns of B = 3, rows of A = 2 → 3 ≠ 2, not defined either.
More order examples:
(7 × 9) · (9 × 11) → defined, order 7 × 11
(3 × 5) · (4 × 5) → not defined
(1 × 4) · (4 × 1) → defined, order 1 × 1 (a single number!)
Order of the product matrix: If A is of order m × n and B is of order n × p, then AB is of order m × p. Example: A = 7 × 9 and B = 9 × 11 ⟹ AB = 7 × 11.
Solved Example — AB ≠ BA (non-commutativity, important practice topic):
A = [ 1 2 ] B = [ 5 6 ]
[ 3 4 ] [ 7 8 ]
AB = [ 1(5)+2(7) 1(6)+2(8) ] = [ 19 22 ]
[ 3(5)+4(7) 3(6)+4(8) ] [ 43 50 ]
BA = [ 5(1)+6(3) 5(2)+6(4) ] = [ 23 34 ]
[ 7(1)+8(3) 7(2)+8(4) ] [ 31 46 ]
AB ≠ BA → matrix multiplication is NOT commutative. ✔
(Also check: matrix multiplication need not even give the same order,
and AB = O does not imply A = O or B = O — these are called zero divisors.)
Properties of matrix multiplication (A, B, C of suitable orders, I = identity matrix):
(i) Associative: (AB)C = A(BC)
(ii) Distributive: A(B + C) = AB + AC
(A + B)C = AC + BC
(iii) Identity: AI = IA = A
(iv) NOT commutative: AB ≠ BA in general
(v) Cancellation law does NOT hold: AB = AC ⇏ B = C
(vi) AB = O does not imply A = O or B = O
(g) Transpose and Matrix Operations
Algebra of transposes (whenever the operations are defined):
(i) (A + B)ᵀ = Aᵀ + Bᵀ
(ii) (A - B)ᵀ = Aᵀ - Bᵀ
(iii) (kA)ᵀ = kAᵀ
(iv) (Aᵀ)ᵀ = A
(v) (AB)ᵀ = BᵀAᵀ ← "reverse order" property
Note: In the transpose of a product, the order of multiplication is reversed.
(h) Additional Properties — Symmetric & Skew-Symmetric Parts
Results to remember:
(i) For any square matrix A: A + Aᵀ is a SYMMETRIC matrix.
(ii) For any square matrix A: A - Aᵀ is a SKEW-SYMMETRIC matrix.
(iii) Every square matrix can be written uniquely as
A = ½(A + Aᵀ) + ½(A - Aᵀ)
↑ symmetric part ↑ skew-symmetric part
Proof of (i) and (ii):
(A + Aᵀ)ᵀ = Aᵀ + (Aᵀ)ᵀ = Aᵀ + A = A + Aᵀ
⟹ (A + Aᵀ)ᵀ = A + Aᵀ → symmetric ✔
(A - Aᵀ)ᵀ = Aᵀ - (Aᵀ)ᵀ = Aᵀ - A = -(A - Aᵀ)
⟹ (A - Aᵀ)ᵀ = -(A - Aᵀ) → skew-symmetric ✔
Solved Example — split A into symmetric + skew-symmetric parts:
Real-life use of matrix multiplication: A shop's price list × quantity list gives the bill. In computer graphics, rotating a point (x, y) by angle θ is the multiplication of a rotation matrix by the point vector: [cos θ −sin θ; sin θ cos θ]·[x; y] — every game, CAD tool and animation uses exactly this. In machine learning, a full layer of a neural network is Y = WX + b, i.e. matrix multiplication followed by addition.
1.3 Determinant of a Matrix
Definition. A determinant is a scalar (a single number) associated with a square matrix, denoted by |A| or det(A). A determinant is defined only for a square matrix: if A is n × n, then |A| is a number, and this number decides whether A can be inverted (|A| ≠ 0) or not (|A| = 0).
Square matrix → determinant exists.
Non-square matrix → determinant is not defined.
(a) Determinant of Order 1
For a 1 × 1 matrix A = [a], the determinant is the element itself: |A| = a.
Examples:
A = [2] → |A| = 2
A = [0] → |A| = 0
A = [-7] → |A| = -7
(b) Determinant of Order 2
For A = [ a b ; c d ] (written row-wise here):
|A| = | a b | = ad - bc
| c d |
Easy trick: Multiply the main diagonal (a·d) and subtract the product of the other diagonal (b·c).
Expansion using cofactors (general): the determinant can be expanded along any row or any column:
Along row i: |A| = ai1Ci1 + ai2Ci2 + ai3Ci3
Along column j: |A| = a1jC1j + a2jC2j + a3jC3j
Answer is always the same. Exam tip: Choose the row/column that contains the most zeros — the work becomes much shorter.
(f) Determinant of Order 4
For a 4 × 4 matrix, the determinant is expanded along any row or column; each term then contains a 3 × 3 determinant. Expanding along the first row:
|A| = a11C11 + a12C12 + a13C13 + a14C14
= a11M11 - a12M12 + a13M13 - a14M14
where every Mij is a 3 × 3 determinant, and the first-row sign pattern is:
+ - + -
Full 4 × 4 sign pattern:
+ - + -
- + - +
+ - + -
- + - +
Solved Example — 4 × 4 by expanding along the row with most zeros:
A = [ 1 0 2 -1 ]
[ 3 0 0 5 ]
[ 2 1 4 -3 ]
[ 1 0 5 0 ]
Column 2 has only one non-zero element: a32 = 1, whose sign is (-1)^(3+2) = -1.
So expand along column 2:
|A| = a32 C32 = 1 × (-1) × M32 = -M32
M32 = delete row 3 and column 2:
[ 1 2 -1 ]
[ 3 0 5 ]
[ 1 5 0 ]
M32 = 1(0 × 0 - 5 × 5) - 2(3 × 0 - 5 × 1) + (-1)(3 × 5 - 0 × 1)
= 1(-25) - 2(-5) + (-1)(15)
= -25 + 10 - 15 = -30
Therefore |A| = -(-30) = 30 ✔
Practical trick: Choose the row/column with the most zeros. Ek zero wali row se
expansion karne par kaam aadha ho jaata hai.
Solved Example — triangular 4 × 4 (fastest case):
A = [ 2 0 0 0 ]
[ 5 3 0 0 ]
[ 1 4 2 0 ]
[ 7 6 5 1 ]
For a triangular matrix, |A| = product of the main-diagonal elements:
|A| = 2 × 3 × 2 × 1 = 12 ✔
(Reason: expanding along the first row repeatedly leaves only the diagonal product.)
(g) Properties of Determinants (very important for exams)
#
Property
Meaning / Example
1
|Aᵀ| = |A|
Transpose does not change the determinant
2
|AB| = |A|·|B|
Determinant of a product = product of determinants
3
|In| = 1
Identity matrix ka determinant 1 hota hai
4
|kA| = kⁿ|A|
A is n × n, k is a scalar — k har element me jaata hai, par power n lagegi
5
Two rows (or columns) identical ⟹ |A| = 0
[1 2; 1 2] → 1·2 − 2·1 = 0
6
One row of zeros ⟹ |A| = 0
Expansion along that row gives 0
7
Interchanging two rows/columns ⟹ sign changes
|A′| = −|A| (where A′ = row-swapped A)
8
Multiplying one row by k ⟹ determinant becomes k|A|
Only one row, not the whole matrix (contrast with property 4)
9
Rowi → Rowi + k·Rowj ⟹ determinant unchanged
Base of the elimination method
10
Triangular matrix ⟹ |A| = product of diagonal elements
Used in Example (f) above
11
|A−1| = 1/|A|
Defined only when |A| ≠ 0
12
A rectangular matrix has no determinant
Determinant only for square matrices
Property 9 (scalar multiplication) — write this in the exam exactly:
If A is an n × n matrix and k is a scalar, then
|kA| = kⁿ |A|
For 2 × 2: |kA| = k² |A|
For 3 × 3: |kA| = k³ |A|
For 4 × 4: |kA| = k⁴ |A|
Reason: multiplying A by k multiplies EACH of the n rows by k;
each row-multiplication brings out one factor of k, total n factors.
Solved Example — verify |kA| = k²|A| for a 2 × 2 matrix:
A = [ 1 2 ] |A| = (1)(4) - (2)(3) = 4 - 6 = -2
[ 3 4 ]
Let k = 3:
kA = [ 3 6 ] |kA| = (3)(12) - (6)(9) = 36 - 54 = -18
[ 9 12 ]
Check with the formula: k²|A| = 3² × (-2) = 9 × (-2) = -18 ✔
Careful (common mistake): |kA| ≠ k|A| — power n lagti hai.
Also compare: if we multiply only ONE row of A by 3, the determinant
becomes 3|A| = -6 (property 8), not -18.
1.4 Rank of a Matrix
Definition. The rank of a matrix A is the order of the largest non-zero minor of A (a minor = determinant of a square sub-matrix). Equivalently, rank = the number of non-zero rows in the row-echelon (triangular) form of A = the number of linearly independent rows (or columns).
Notation: ρ(A) or rank(A). If every element of A is zero, then rank(A) = 0 by definition.
Two standard methods:
METHOD 1 (minor method):
Step 1: Take the largest possible square sub-matrix.
Step 2: If its determinant ≠ 0, rank = its order.
Step 3: If all minors of the largest order are 0, go to the next
lower order and repeat.
METHOD 2 (echelon form method — faster for big matrices):
Step 1: Use elementary row operations to make the matrix triangular
(row-echelon form).
Step 2: Count the number of non-zero rows. That count = rank.
Solved Example 1 — rank by the minor method:
B = [ 1 2 ]
[ 3 4 ]
Largest minor = whole matrix: |B| = 1(4) - 2(3) = -2 ≠ 0
⟹ the largest non-zero minor has order 2 ⟹ rank(B) = 2 ✔
(Rank = 2 = min(2, 2), so B has "full rank".)
Solved Example 2 — dependent rows (rank 1):
A = [ 1 2 3 ]
[ 2 4 6 ]
[ 3 6 9 ] Row2 = 2 × Row1, Row3 = 3 × Row1
Every 2 × 2 minor is zero, e.g. | 1 2 ; 2 4 | = 4 - 4 = 0
and every 3 × 3 minor is zero too (|A| = 0).
Echelon form: R2 → R2 - 2R1, R3 → R3 - 3R1 gives
[ 1 2 3 ]
[ 0 0 0 ]
[ 0 0 0 ] → non-zero rows = 1 ⟹ rank(A) = 1 ✔
Solved Example 3 — rank 2 by echelon form (step by step):
A = [ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
Step 1: R2 → R2 - 4R1 and R3 → R3 - 7R1
[ 1 2 3 ]
[ 0 -3 -6 ]
[ 0 -6 -12 ]
Step 2: R3 → R3 - 2R2
[ 1 2 3 ]
[ 0 -3 -6 ]
[ 0 0 0 ]
Non-zero rows = 2 ⟹ rank(A) = 2 ✔
Also |A| = 1(45-48) - 2(36-42) + 3(32-35) = -3 + 12 - 9 = 0,
so the largest non-zero minor is of order 2 — same answer.
Answer likhne ka tarika: "rank = 2, kyunki echelon form me 2 non-zero rows hain
aur sabse bada non-zero minor 2 × 2 ka hai."
Properties of rank (short note answer):
(i) 0 ≤ rank(A) ≤ min(m, n)
(ii) rank(A) = 0 ⟺ A is a zero matrix
(iii) rank(In) = n (identity matrix has full rank)
(iv) rank(A) = rank(Aᵀ) (row rank = column rank)
(v) Elementary row/column operations do not change the rank
(vi) rank ≤ number of rows, and rank ≤ number of columns
(vii) If |A| ≠ 0 (nonsingular, n × n) then rank(A) = n ("full rank")
Rank and consistency of a system of equations (Rouché–Capelli rule). For the system AX = B (n unknowns), compare rank(A) with rank([A | B]) where [A | B] is the augmented matrix:
rank(A) ≠ rank([A | B]) → system is INCONSISTENT (no solution)
rank(A) = rank([A | B]) = n → UNIQUE solution
rank(A) = rank([A | B]) < n → INFINITELY many solutions
For the homogeneous system AX = O: it is always consistent; a non-trivial
solution exists ⟺ |A| = 0 (i.e. rank(A) < n).
Why rank matters: Rank measures how much "real, independent information" a matrix carries. In a system of equations, a dependent row means one equation is redundant — rank tells you the true number of independent equations. In data science, a low-rank matrix means features are correlated (that is exactly why dimensionality reduction such as PCA works). In image compression, a big image matrix is approximated by a low-rank matrix. In network analysis (adjacency matrix), rank relates to connectivity.
1.5 Inverse of a Matrix
Definition. If A is a square matrix of order n, then a matrix A−1 of the same order is called the inverse of A if
A · A⁻¹ = A⁻¹ · A = Iₙ
Existence condition: the inverse exists only when |A| ≠ 0 (such a matrix is called non-singular). If |A| = 0 the matrix is singular and the inverse does not exist.
Uniqueness: if B and C are both inverses of A, then B = BI = B(AC) = (BA)C = IC = C, so the inverse is unique.
(a) Inverse of a 2 × 2 Matrix — formula and derivation
For A = [ a b ; c d ] with ad − bc ≠ 0:
A⁻¹ = 1/(ad - bc) × [ d -b ]
[ -c a ]
Steps: (1) find det = ad - bc, (2) swap the diagonal elements a and d,
(3) change the signs of b and c, (4) divide every element by the determinant.
Why it works: A × [d −b; −c a] = [ad−bc 0; 0 ad−bc] = (ad−bc)·I, so dividing by (ad − bc) gives I.
Solved Example — 2 × 2 inverse with full verification:
A⁻¹ = adj(A) / |A| = (1/|A|) · adj(A), defined only if |A| ≠ 0
where adj(A) = transpose of the cofactor matrix = [Cji]
Steps:
1. Find |A| (must be ≠ 0).
2. Find every cofactor Cij = (-1)^(i+j) Mij → cofactor matrix C.
3. Take the transpose of C → adj(A) = Cᵀ.
4. Divide each element of adj(A) by |A|.
Solved Example — inverse of a 3 × 3 matrix, complete:
Alternative — inverse by elementary row operations (Gauss–Jordan):
Write A and I side by side as [A | I], then apply row operations until
the left side becomes I. The right side then becomes A⁻¹.
Example: A = [ 2 1 ]
[ 5 3 ] det = 6 - 5 = 1
[A | I] = [ 2 1 | 1 0 ]
[ 5 3 | 0 1 ]
R1 → R1/2: [ 1 0.5 | 0.5 0 ]
[ 5 3 | 0 1 ]
R2 → R2 - 5R1: [ 1 0.5 | 0.5 0 ]
[ 0 0.5 | -2.5 1 ]
R2 → 2R2: [ 1 0.5 | 0.5 0 ]
[ 0 1 | -5 2 ]
R1 → R1 - 0.5R2:[ 1 0 | 3 -1 ]
[ 0 1 | -5 2 ]
⟹ A⁻¹ = [ 3 -1 ] (Check: A·A⁻¹ = I ✔)
[ -5 2 ]
Properties of the inverse (yaad rakhne wale results):
(i) (A⁻¹)⁻¹ = A
(ii) (AB)⁻¹ = B⁻¹A⁻¹ ← reverse order (like transpose)
(iii) (Aᵀ)⁻¹ = (A⁻¹)ᵀ (transpose and inverse commute)
(iv) (kA)⁻¹ = (1/k)·A⁻¹ (k ≠ 0)
(v) (Aⁿ)⁻¹ = (A⁻¹)ⁿ
(vi) |A⁻¹| = 1/|A|
(vii) A·A⁻¹ = A⁻¹·A = I
(viii) If A is symmetric and invertible, then A⁻¹ is also symmetric.
Real-life / CS use:Hill cipher in cryptography encrypts with a matrix K and decrypts with K−1 (mod 26) — without the inverse you cannot decrypt a message. In computer graphics, an object is scaled/rotated by a matrix, and to "undo" the transformation you multiply by the inverse matrix. Robotics uses inverse matrices to convert from camera coordinates back to world coordinates. Solving AX = B needs A−1 — that is the next section.
1.6 Applications: Solving Systems of Linear Equations High-yield syllabus topic
Matrix form of a system. A system of linear equations can always be written as AX = B, where A = coefficient matrix, X = column matrix of unknowns, B = column matrix of constants. For example:
2x + 3y = 13 [ 2 3 ] [ x ] [ 13 ]
⟹ [ ] [ ] = [ ]
4x - y = 5 [ 4 -1 ] [ y ] [ 5 ]
A X = B
Solution methods: (1) Matrix inverse method X = A⁻¹B,
(2) Cramer's rule (determinants),
(3) Gauss elimination (row operations).
(a) Matrix Inverse Method
If |A| ≠ 0, then AX = B → A−1(AX) = A−1B → X = A−1B (the system has a unique solution).
Solved Example — same system by the inverse method:
x = Dx / D, y = Dy / D, z = Dz / D
Dx = determinant of A with the x-column replaced by B
Dy = determinant of A with the y-column replaced by B
Dz = determinant of A with the z-column replaced by B
If D = 0 and at least one of Dx, Dy is ≠ 0 → no solution.
If D = 0 and Dx = Dy = 0 → infinitely many solutions (or none, check by rank).
Homogeneous system AX = O: the zero vector X = O is always a solution (trivial solution). A non-trivial solution exists if and only if |A| = 0 (i.e. rank(A) < n). For a 3 × 3 system: if |A| ≠ 0 then x = y = z = 0 is the only solution.
Real-life examples: "2 pens + 3 copies = ₹13 and 4 pens − 1 copy = ₹5; find the price of each" is exactly the system solved above. In computer graphics, the intersection point of two lines (collision detection in games) is a 2 × 2 system. In electrical engineering, Kirchhoff's laws give a linear system for the currents; in chemistry, balancing equations is a homogeneous system; in economics, supply = demand gives simultaneous equations. Sab jagah AX = B hi hai.
1.7 Eigenvalues & Eigenvectors
Definition. Let A be an n × n matrix. A non-zero column vector X and a scalar λ are called an eigenvector and an eigenvalue of A respectively if
A X = λ X, X ≠ 0
Rearranging: (A − λI)X = O. This homogeneous system has a non-trivial solution only when the coefficient determinant is zero:
| A − λ I | = 0 ← CHARACTERISTIC EQUATION
The expression |A − λI| is a polynomial in λ, called the characteristic polynomial. Its roots are the eigenvalues; for each eigenvalue, (A − λI)X = O gives the corresponding eigenvectors.
Meaning: multiplying X by A only stretches/shrinks it (by factor λ) and does not change its direction — the matrix acts like a plain number λ on these special vectors.
Solved Example 1 — 2 × 2 matrix (every step):
A = [ 4 1 ]
[ 2 3 ]
Step 1: characteristic equation |A - λI| = 0
| 4-λ 1 | = 0
| 2 3-λ |
(4 - λ)(3 - λ) - (1)(2) = 0
12 - 4λ - 3λ + λ² - 2 = 0
λ² - 7λ + 10 = 0
(λ - 5)(λ - 2) = 0
⟹ eigenvalues λ = 5 and λ = 2 ✅
Step 2: eigenvector for λ = 5 → (A - 5I)X = O
[ -1 1 ] [ x ] [ 0 ]
[ 2 -2 ] [ y ] = [ 0 ] Both equations give the same condition: x = y
Take x = 1 → y = 1:
X1 = [ 1 ] (any non-zero multiple works: [2 2]ᵀ, [-1 -1]ᵀ, ...)
[ 1 ]
Step 3: eigenvector for λ = 2 → (A - 2I)X = O
[ 2 1 ] [ x ] [ 0 ]
[ 2 1 ] [ y ] = [ 0 ] → 2x + y = 0 → y = -2x
Take x = 1 → y = -2:
X2 = [ 1 ]
[ -2 ]
Step 4: verify one pair: A X1 = [4(1)+1(1); 2(1)+3(1)] = [5; 5] = 5·[1; 1] = 5X1 ✔
Solved Example 2 — 3 × 3 with repeated roots:
A = [ -2 2 -3 ]
[ 2 1 -6 ]
[ -1 -2 0 ]
Step 1: characteristic equation. For a 3 × 3 matrix:
λ³ - (trace)λ² + (sum of principal 2 × 2 minors)λ - |A| = 0
trace = -2 + 1 + 0 = -1
sum of minors = | -2 2 ; 2 1 | + | -2 -3 ; -1 0 | + | 1 -6 ; -2 0 |
= (-2-4) + (0-3) + (0-12) = -6 - 3 - 12 = -21
|A| = 45
⟹ λ³ + λ² - 21λ - 45 = 0
⟹ (λ - 5)(λ + 3)² = 0
⟹ eigenvalues λ = 5, λ = -3, λ = -3 ✅
Check: sum = 5 - 3 - 3 = -1 = trace ✔ product = 5 × (-3) × (-3) = 45 = |A| ✔
Step 2: eigenvector for λ = 5 → (A - 5I)X = O
[ -7 2 -3 ] [ x ] [ 0 ]
[ 2 -4 -6 ] [ y ] = [ 0 ] → solving gives x : y : z = 1 : 2 : -1
[ -1 -2 -5 ] [ z ] [ 0 ]
X1 = [ 1 ]
[ 2 ]
[ -1 ] Check: A·X1 = [5; 10; -5] = 5·X1 ✔
Step 3: eigenvectors for λ = -3 → (A + 3I)X = O
[ 1 2 -3 ] [ x ] [ 0 ]
[ 2 4 -6 ] [ y ] = [ 0 ] → all rows give: x + 2y - 3z = 0
[ -1 -2 3 ] [ z ] [ 0 ]
Take y = 1, z = 0 → x = -2: X2 = [ -2 ]ᵀ
[ 1 ]
[ 0 ]
Take y = 0, z = 1 → x = 3: X3 = [ 3 ]ᵀ
[ 0 ]
[ 1 ]
(Two independent eigenvectors, because the root -3 is repeated.)
Properties of eigenvalues and eigenvectors:
(i) Sum of eigenvalues = trace(A) = a11 + a22 + ... + ann
(ii) Product of eigenvalues = |A| (determinant)
(iii) Eigenvalues of a triangular / diagonal matrix = its diagonal elements
(iv) Eigenvalues of a symmetric matrix are always REAL
(v) Eigenvalues of Aᵏ are λᵏ; of A⁻¹ are 1/λ; of kA are kλ
(vi) Eigenvalues of Aᵀ = eigenvalues of A
(vii) Eigenvectors corresponding to DISTINCT eigenvalues are linearly independent
(viii) Every square matrix satisfies its own characteristic equation (Cayley–Hamilton)
(ix) A is singular ⟺ at least one eigenvalue is 0
(x) If λ is an eigenvalue then |A - λI| = 0 (used in the exam as a check)
Where used: Google's PageRank treats the web as a matrix and the principal eigenvector gives the importance of every page. PCA in data science compresses data using eigenvectors of the covariance matrix (face recognition uses "eigenfaces"). Vibration analysis of bridges and buildings, stability of numerical algorithms, Markov chains, and quantum mechanics all depend on eigenvalues. In short: jab bhi kisi system ka "natural behaviour" nikalna hota hai, eigenvalue nikalta hai.
1.8 Cayley–Hamilton Theorem
Statement. Every square matrix satisfies its own characteristic equation. That is, if |A − λI| = 0 gives the characteristic equation
λⁿ + c1λⁿ⁻¹ + c2λⁿ⁻² + ... + cn = 0
then A satisfies the same equation with λ replaced by A and the constant term multiplied by I:
Aⁿ + c1Aⁿ⁻¹ + c2Aⁿ⁻² + ... + cnI = O
For a 2 × 2 matrix: λ² − (trace)λ + |A| = 0 ⟹ A² − (trace)A + |A|I = O.
Solved Example — using Cayley–Hamilton to compute a high power (A⁴):
Same A, with A² = 7A - 10I (obtained from A² - 7A + 10I = O)
A³ = A·A² = A(7A - 10I) = 7A² - 10A = 7(7A - 10I) - 10A = 49A - 70I - 10A
= 39A - 70I
A⁴ = A·A³ = A(39A - 70I) = 39A² - 70A = 39(7A - 10I) - 70A
= 273A - 390I - 70A
= 203A - 390I
So A⁴ = 203 [ 4 1 ] - 390 [ 1 0 ] = [ 812-390 203 ] = [ 422 203 ]
[ 2 3 ] [ 0 1 ] [ 406 609-390 ] [ 406 219 ]
Benefit: A⁴ nikaalne ke liye baar-baar matrix multiply karne ki zaroorat nahi —
sirf A ka linear combination. Ye trick exam me time bachati hai.
For a 3 × 3 matrix (general form of the theorem):
λ³ - (trace A)λ² + (sum of principal 2 × 2 minors)λ - |A| = 0
⟹ A³ - (trace A)A² + (sum of minors)A - |A|·I = O
To find A⁻¹ for a 3 × 3 matrix: multiply the equation by A⁻¹:
A² - (trace A)A + (sum of minors)I - |A|A⁻¹ = O
⟹ A⁻¹ = (1/|A|) [ A² - (trace A)A + (sum of minors)I ]
Exam tip: The standard question is "State Cayley–Hamilton theorem and use it to find A⁻¹" (10 marks). Write: (1) the statement, (2) the characteristic equation with calculation, (3) verification of A² − 7A + 10I = O, (4) the derivation A − 7I + 10A⁻¹ = O and the final A⁻¹, (5) a one-line check A·A⁻¹ = I. Practise the 2 × 2 case thoroughly; the 3 × 3 case follows the same steps with A³.
⚡ Unit 1 — Rapid Revision (formula card)
Matrix: order m × n • element aij (i-th row, j-th column) • total elements = mn
Equality: same order + corresponding elements equal • Transpose: rows ↔ columns, (aij)ᵀ = aji
Types: identity (aij = 1 if i = j else 0) • diagonal (aij = 0, i ≠ j) • scalar (diagonal + equal) • triangular (aij = 0 for i > j / i < j) • symmetric (aij = aji) • skew-symmetric (aij = −aji, diagonal 0)
Addition/subtraction: only for the same order • A + O = A (additive identity) • A + (−A) = O (additive inverse)
Multiplication: (m × n)(n × p) → m × p • cij = Σ aikbkj • AB ≠ BA • associative + distributive but not commutative
Transpose rules: (A + B)ᵀ = Aᵀ + Bᵀ • (AB)ᵀ = BᵀAᵀ • A + Aᵀ symmetric • A − Aᵀ skew-symmetric
Determinant: |a b; c d| = ad − bc • 3 × 3 → expand along any row/column using cofactors • Mij = minor, Cij = (−1)i+jMij • |kA| = kⁿ|A| • |AB| = |A||B| • |Aᵀ| = |A|
Rank: order of the largest non-zero minor = non-zero rows in echelon form • rank ≤ min(m, n) • rank(A) = rank(Aᵀ)
Inverse: A⁻¹ = adj(A)/|A|, exists ⟺ |A| ≠ 0 • 2 × 2: swap diagonal, negate other two, divide by det • (AB)⁻¹ = B⁻¹A⁻¹
Systems: AX = B → X = A⁻¹B • Cramer: x = Dx/D, y = Dy/D • consistency: rank(A) = rank([A|B]) = n → unique; = rank < n → infinite; rank(A) ≠ rank([A|B]) → no solution
Eigen: |A − λI| = 0 → λ, then (A − λI)X = O → X • Σλ = trace, Πλ = |A| • symmetric matrix ke eigenvalues real
Cayley–Hamilton: matrix apni characteristic equation satisfy karta hai → A² − (trace)A + |A|I = O (2 × 2) → A⁻¹ aur A⁴ jaise high powers nikalne ka shortcut
Syllabus-based exam-style practice questions (not predictions) — Unit 1:
Define a matrix, its order and element notation. Write all types of matrices with one example each. (10)
Prove that A + Aᵀ is symmetric and A − Aᵀ is skew-symmetric; also express A as the sum of a symmetric and a skew-symmetric matrix. (5–10)
If A and B are of the same order, verify (A + B)ᵀ = Aᵀ + Bᵀ with an example. (5)
Multiply two given matrices; also show by example that AB ≠ BA. (5)
Evaluate a 2 × 2 and a 3 × 3 determinant. (5)
Find all minors and cofactors of a given 3 × 3 matrix and hence evaluate its determinant. (10)
State and use the property |kA| = kⁿ|A| with an example. (5)
Find the rank of a matrix using the echelon form. (5–10)
Find the inverse of a 2 × 2 / 3 × 3 matrix by the adjoint method. (10)
Solve the system 2x + 3y = 13, 4x − y = 5 by (i) the matrix inverse method and (ii) Cramer's rule. (10)
Find the eigenvalues and eigenvectors of a given 2 × 2 / 3 × 3 matrix. (10)
State Cayley–Hamilton theorem, verify it for a 2 × 2 matrix and use it to find A⁻¹ (and A⁴). (10)
Discuss the consistency of a given system using rank; give one example of each case. (5–10)
UNIT 2 — Sets, Relations and Functions
2.1 Set — Definition & Representation
Definition. A set is a well-defined collection of distinct objects (called elements or members). "Well-defined" means that for any object it must be clearly decidable whether it belongs to the set or not. Sets are denoted by capital letters A, B, C, ... and their elements by small letters a, b, c, ...
Notation: a ∈ A means "a is an element of A"; a ∉ A means "a is not an element of A".
In simple words: A set is a group with a clear rule 🎒 — "BCA 1st semester ke students ka set", "1 se 10 tak ke odd numbers". Rule clear hona chahiye: "sundar ladkiyon ka set" ✗ (sundar har vyakti ke liye alag hai, set nahi ban sakta); "5 feet se lambi ladkiyon ka set" ✔ (clear rule, so it is a set).
Two ways of writing a set:
Roster (tabular) form : A = {1, 2, 3, 4, 5} (elements listed)
Set-builder form : A = {x : x ∈ N, x ≤ 5} (rule described)
Read: "the set of all x such that x is a natural
number and x is less than or equal to 5".
Important symbols (learn these — they appear in every question):
∈ is an element of 2 ∈ A
∉ is not an element of 7 ∉ A
⊂ is a proper subset of A ⊂ B
⊆ is a subset of (or equal) A ⊆ B
∪ union A ∪ B = all elements of A or B
∩ intersection A ∩ B = common elements
- difference A - B = in A but not in B
Aᶜ complement elements of U that are not in A
∅ empty / null set ∅ = { }
U universal set the set of all elements under discussion
n(A) cardinality number of elements in A
|A| also used for cardinality
Types of sets:
1. Empty (null) set : no elements, ∅ or { }
2. Singleton set : exactly one element, e.g. {5}
3. Finite set : countable number of elements, e.g. {1, 2, 3}
4. Infinite set : uncountable, e.g. N = {1, 2, 3, ...}
5. Equal sets : same elements (order does not matter)
A = {1, 2, 3} and B = {3, 2, 1} are equal
6. Equivalent sets : same number of elements (n(A) = n(B)),
not necessarily the same elements
7. Subset : every element of A is in B → A ⊆ B
Every set is a subset of itself (A ⊆ A).
8. Proper subset : A ⊆ B and A ≠ B → A ⊂ B
9. Universal set : U, contains all elements of the discussion
10. Power set : P(A) = set of ALL subsets of A
If n(A) = n then n(P(A)) = 2ⁿ
11. Disjoint sets : A ∩ B = ∅ (no common element)
Solved Example 1 — list the power set:
A = {1, 2} n(A) = 2 → number of subsets = 2² = 4
P(A) = { ∅, {1}, {2}, {1, 2} }
n(P(A)) = 4 ✔
Proper subsets of A = {1}, {2}, ∅ → count = 2ⁿ - 1 = 3 ✔
Another check: A = {1,2,3} → 2³ = 8 subsets (count them to be sure).
Solved Example 2 — set operations (write the exam answer like this):
U = {1,2,3,4,5,6,7,8,9,10}, A = {1,2,3,4,5}, B = {2,4,6,8}
A ∪ B = {1,2,3,4,5,6,8} (all elements, common ones written once)
A ∩ B = {2,4} (only common)
A - B = {1,3,5} (in A but not in B)
B - A = {6,8}
Aᶜ = {6,7,8,9,10} (complement w.r.t. U)
Bᶜ = {1,3,5,7,9,10}
n(A) = 5, n(B) = 4, n(A ∪ B) = 7, n(A ∩ B) = 2
Verify the counting formula:
|A ∪ B| = |A| + |B| - |A ∩ B| = 5 + 4 - 2 = 7 ✔
2.2 Set Operations — Properties and Laws
Law
Form
Commutative
A ∪ B = B ∪ A • A ∩ B = B ∩ A
Associative
(A ∪ B) ∪ C = A ∪ (B ∪ C) • (A ∩ B) ∩ C = A ∩ (B ∩ C)
Distributive
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) • A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Identity
A ∪ ∅ = A • A ∩ U = A
Idempotent
A ∪ A = A • A ∩ A = A
Complement
A ∪ Aᶜ = U • A ∩ Aᶜ = ∅ • (Aᶜ)ᶜ = A • Uᶜ = ∅ • ∅ᶜ = U
De Morgan's Laws
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ • (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
Absorption
A ∪ (A ∩ B) = A • A ∩ (A ∪ B) = A
Difference
A − B = A ∩ Bᶜ
Trick for De Morgan: "Complement poore bracket par lage to symbol palat jaata hai" 🔄 — ∪ becomes ∩ and ∩ becomes ∪. Real-life check: "AC kharab HO YA current na ho" ⟹ light nahi aayegi; complement lene par "light aa gayi" ka matlab "AC theek hai AUR current hai".
Solved Example — verify De Morgan's law (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ:
U = {1,2,3,4,5,6,7,8,9}, A = {1,2,3,4}, B = {3,4,5,6}
LEFT SIDE:
A ∪ B = {1,2,3,4,5,6}
(A ∪ B)ᶜ = {7,8,9}
RIGHT SIDE:
Aᶜ = {5,6,7,8,9}
Bᶜ = {1,2,7,8,9}
Aᶜ ∩ Bᶜ = {7,8,9}
Both sides are equal ⟹ (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ ✔ HENCE VERIFIED.
Solved Example — counting with two and three sets:
Two sets: |A ∪ B| = |A| + |B| - |A ∩ B|
Three sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|
Example: In a class of 60 students, 30 play cricket, 25 play football and
10 play both. How many play at least one game? How many play none?
At least one = 30 + 25 - 10 = 45 students
None = 60 - 45 = 15 students ✔
(Note the "+ both" at the end of the three-set formula — the students in all
three sets get subtracted three times and must be added back once.)
2.3 Cartesian Product & Relations
Cartesian product. For two non-empty sets A and B, the Cartesian product is
A × B = { (a, b) : a ∈ A, b ∈ B } (set of all ORDERED pairs)
If n(A) = m and n(B) = n, then n(A × B) = m × n.
Properties: A × B ≠ B × A in general (order matters)
A × ∅ = ∅
A × (B ∪ C) = (A × B) ∪ (A × C)
Solved Example:
A = {1, 2}, B = {x, y}
A × B = { (1,x), (1,y), (2,x), (2,y) } 4 = 2 × 2 pairs ✔
B × A = { (x,1), (x,2), (y,1), (y,2) } A × B ≠ B × A ✔
Subsets of A × B: number of possible relations from A to B = 2^(m×n)
Here m = n = 2 → 2⁴ = 16 different relations are possible from A to B.
This counting fact is a frequent 2-mark question.
Relation. A relation R from A to B is a subset of A × B. If (a, b) ∈ R we write a R b and say "a is related to b". A relation on a set A is a subset of A × A.
For a relation R: Domain = set of all first elements of the pairs; Range = set of all second elements; Co-domain = B (the whole target set). The inverse relation R−1 = {(b, a) : (a, b) ∈ R}.
Solved Example:
A = {1, 2, 3}, R = { (a, b) : a < b } on A
R = { (1,2), (1,3), (2,3) }
Domain of R = {1, 2}
Range of R = {2, 3}
Co-domain = A = {1, 2, 3}
R⁻¹ = { (2,1), (3,1), (3,2) } (ye "greater than" relation ban gaya)
Note: (1,1) ∉ R kyunki 1 < 1 sach nahi hai — isliye R reflexive nahi hai
(see the next section).
Real life: Students × Subjects — "kis student ne kaun sa subject liya" is a relation. "Follows" on Instagram is a relation on the set of users (and it is not symmetric!). "A is a friend of B" on WhatsApp is symmetric. A road network is a relation on cities; Google's web graph (page → page links) is a relation on web pages — PageRank works on exactly this.
2.4 Types of Relations
Definitions (write these exactly in the exam): Let R be a relation on a set A.
(i) REFLEXIVE : (a, a) ∈ R for EVERY a ∈ A
(ii) SYMMETRIC : (a, b) ∈ R ⟹ (b, a) ∈ R
(iii) ANTISYMMETRIC : (a, b) ∈ R and (b, a) ∈ R ⟹ a = b
(iv) TRANSITIVE : (a, b) ∈ R and (b, c) ∈ R ⟹ (a, c) ∈ R
(v) EQUIVALENCE : Reflexive + Symmetric + Transitive (R-S-T)
(vi) PARTIAL ORDER : Reflexive + Antisymmetric + Transitive (R-A-T)
Relation type
Condition
Example
Empty relation
R = ∅ (no pair)
R = ∅ on {1, 2, 3}
Universal relation
R = A × A (every pair)
{1,2}² = {(1,1),(1,2),(2,1),(2,2)}
Identity relation
Only (a, a) pairs
{(1,1),(2,2),(3,3)}
Reflexive
Har element apne aap se related
"same age as"
Symmetric
Dono taraf arrow
"lives in the same city as"
Antisymmetric
Return arrow sirf a = b ke liye
"≤" on numbers, "is a subset of"
Transitive
Chain chalti hai
"is less than", "is an ancestor of"
Equivalence
R + S + T
"congruent modulo n", "same city"
Partial order
R + Antisymmetric + T
"≤" on Z, "⊆" on P(A)
Mnemonics: Equivalence = "RST" — "Reflexive, Symmetric, Transitive". Partial order = "RAT" — "Reflexive, Antisymmetric, Transitive". Exam me pehle is order me check karo: (a,a) hai? → ulta pair hai? → chain hai?
Solved Example 1 — full verification (R = equivalence?):
A = {1, 2, 3}, R = { (1,1), (2,2), (3,3), (1,2), (2,1) }
Reflexive? (1,1) ✔ (2,2) ✔ (3,3) ✔ → YES ✔
Symmetric? (1,2) ∈ R and (2,1) ∈ R ✔
Also (1,1),(2,2),(3,3) are self-pairs (always okay) → YES ✔
Transitive? (1,2) & (2,1) → (1,1) ∈ R ✔
(2,1) & (1,2) → (2,2) ∈ R ✔
(1,2) & (2,2) → (1,2) ∈ R ✔
No other chains exist → YES ✔
Antisymmetric? (1,2) and (2,1) both present but 1 ≠ 2 → NO ✗
Conclusion: R is reflexive + symmetric + transitive ⟹ R is an EQUIVALENCE
RELATION (but not a partial order).
Solved Example 2 — a partial order: "divides" relation?
A = {1, 2, 3, 6}, R = { (a, b) : a divides b }
R = { (1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6) }
Reflexive? every number divides itself → YES ✔
Antisymmetric? a|b and b|a ⟹ a = b (true for positive integers) → YES ✔
Transitive? if a|b and b|c then a|c → YES ✔
⟹ R is a PARTIAL ORDER relation.
Note: "≤" on the set of real numbers, and "⊆" on the power set of a set,
are the standard examples of partial order relations.
Solved Example 3 — a relation that fails transitivity:
A = {1, 2, 3, 4}, R = { (1,2), (2,3) } — is R transitive?
Check the chain: (1,2) & (2,3) ⟹ (1,3) should be in R, but it is NOT.
⟹ R is NOT transitive ✗ (This is exactly the reason we need the
"transitive closure" of a relation — Section 2.7.)
Also useful counting results (short-note favourite):
Total relations on a set with n elements = 2^(n²)
Total reflexive relations = 2^(n² - n)
Total symmetric relations = 2^(n(n+1)/2)
2.5 Equivalence Relation and Partition of a Set
Equivalence classes. If R is an equivalence relation on A, then for a ∈ A the set
[a] = { x ∈ A : (a, x) ∈ R }
is called the equivalence class of a. Properties: (i) a ∈ [a] (so no class is empty), (ii) [a] = [b] if and only if a R b, (iii) two classes are either identical or disjoint (they never partially overlap).
Partition. A collection of non-empty subsets of A is a partition of A if (i) no subset is empty, (ii) the subsets are pairwise disjoint, and (iii) their union is the whole set A. An equivalence relation on A always produces a partition of A, and every partition gives an equivalence relation.
Solved Example — congruence modulo 3:
A = {1, 2, 3, 4, 5, 6}, R = { (a,b) : (a - b) is divisible by 3 }
Classes:
[1] = {1, 4} (both leave remainder 1)
[2] = {2, 5} (both leave remainder 2)
[3] = {3, 6} (both leave remainder 0)
Result: {1,4}, {2,5}, {3,6} → three classes that are disjoint, non-empty,
and together give the whole set A ⟹ they form a PARTITION of A ✔
Verify the properties of R:
Reflexive: a - a = 0, divisible by 3 ✔
Symmetric: a - b divisible by 3 ⟹ b - a = -(a-b) also divisible ✔
Transitive: a-b and b-c divisible by 3 ⟹ (a-b)+(b-c) = a-c divisible ✔
⟹ R is an equivalence relation (congruence mod 3 is the classic example).
Real life: Students divided by city (Kichha / Haldwani / Rudrapur) — an equivalence relation giving a partition. Files grouped by type (photos / videos / documents), bank accounts grouped by IFSC branch, and "same roll-number prefix" grouping in a college — all partitions. In computer science, partition-refinement is used in DFA minimisation and in union-find data structures (Kruskal's algorithm!).
2.6 Representing Relations — Matrix and Digraph
Matrix (adjacency) representation. For a relation R on A = {a1, ..., an}, define the n × n matrix M with
Mij = 1 if (ai, aj) ∈ R,
0 otherwise
Digraph representation. Every element is a node (circle) and there is a directed arrow from a to b whenever (a, b) ∈ R. A pair (a, a) ∈ R is shown as a self-loop.
Solved Example — both representations:
A = {1, 2, 3}, R = { (1,1), (1,2), (2,3), (3,1) }
Matrix form: Digraph:
1 2 3
1 [ 1 1 0 ] ① ⟲ (self loop)
2 [ 0 0 1 ] ① → ②, ② → ③, ③ → ①
3 [ 1 0 0 ] (so there is a cycle 1 → 2 → 3 → 1)
Out-degrees: row sums → 2, 1, 1
In-degrees : column sums → 2, 1, 1
How to read properties from the matrix (very useful in exams):
Reflexive : all the diagonal entries Mii = 1
Irreflexive : all the diagonal entries Mii = 0
Symmetric : M = Mᵀ (the matrix looks like a mirror image)
Antisymmetric : Mij = 1 and Mji = 1 only when i = j
Transitive : M² (Boolean product) has 1s only where M has 1s
i.e. M² ≤ M entry-wise (no new 1 appears)
In the digraph: self-loop = reflexive, both arrows between two nodes =
symmetric, a chain of arrows that "shortcuts" = transitive.
Solved Example — checking transitivity by Boolean product:
M = [ 0 1 0 ] M² (Boolean: 1 only if some k has both 1) :
[ 0 0 1 ] Row1: 1→2→3 gives M²13 = 1
[ 0 0 0 ] M² = [ 0 0 1 ]
[ 0 0 0 ]
[ 0 0 0 ]
M² has a 1 at position (1,3) where M has 0 ⟹ R is NOT transitive.
Adding that missing pair (1,3) gives the transitive closure ✔
2.7 Closures of Relations & Warshall's Algorithm
Closure. The closure of a relation with respect to a property P is the smallest relation that contains R and has property P.
Reflexive closure : R ∪ {(a,a) : a ∈ A} (make the diagonal all 1)
Symmetric closure : R ∪ R⁻¹ (add the reverse of every pair)
Transitive closure: R ∪ R² ∪ R³ ∪ ... ∪ Rⁿ (n = number of elements)
(for a finite set, paths of length more than n are
never needed)
Warshall's Algorithm — finds the transitive closure (reachability matrix) of a relation on n elements. Let M be the Boolean adjacency matrix:
for k = 1 to n:
for i = 1 to n:
for j = 1 to n:
if M[i][k] == 1 AND M[k][j] == 1:
M[i][j] = 1
Meaning: "agar i se k pahunch sakte ho aur k se j pahunch sakte ho,
to i se j bhi pahunch sakte ho" — i.e. add all shortcut paths.
At the end, M[i][j] = 1 ⟺ j is reachable from i.
Solved Example — Warshall, step by step (exam-style):
A = {1, 2, 3, 4}, R = { (1,2), (2,3), (3,4) } (a chain 1 → 2 → 3 → 4)
Initial matrix M⁰:
1 2 3 4
1 [ 0 1 0 0 ]
2 [ 0 0 1 0 ]
3 [ 0 0 0 1 ]
4 [ 0 0 0 0 ]
k = 1: no pair enters through node 1 (column 1 is all 0) → no change
k = 2: M[1][2] = 1 and M[2][3] = 1 → M[1][3] = 1
1 2 3 4
1 [ 0 1 1 0 ]
2 [ 0 0 1 0 ]
3 [ 0 0 0 1 ]
4 [ 0 0 0 0 ]
k = 3: M[1][3] = 1 and M[3][4] = 1 → M[1][4] = 1
M[2][3] = 1 and M[3][4] = 1 → M[2][4] = 1
1 2 3 4
1 [ 0 1 1 1 ]
2 [ 0 0 1 1 ]
3 [ 0 0 0 1 ]
4 [ 0 0 0 0 ]
k = 4: column 4 has 1s in rows 1, 2, 3 but row 4 is all 0 → no new pair
FINAL transitive closure:
R* = { (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) } (6 pairs) ✔
Meaning: from 1 we can reach 2, 3 and 4; from 2 we can reach 3 and 4, etc.
Solved Example 2 — cycle (all nodes become reachable):
A = {1,2,3}, R = { (1,2), (2,3), (3,1) } → a cycle
Applying Warshall: from every node every other node becomes reachable
(1 → 2 → 3 → 1 → ...), so the final matrix has 1 in every position:
[ 1 1 1 ]
M* = [ 1 1 1 ]
[ 1 1 1 ]
⟹ Transitive closure = A × A (the universal relation, 9 pairs). ✔
Reflexive closure of R = R ∪ {(1,1),(2,2),(3,3)} = A × A here.
Applications: Social networks ("friends of friends" — how many people can you reach?), flight/train route planning (can I get from Delhi to a small town with connections?), compiler analysis (which variables can affect which others), database query optimisation, and network routing. Warshall's idea is also the base of the Floyd–Warshall algorithm for all-pairs shortest paths, which replaces the Boolean OR-AND with min-and-plus arithmetic.
⚡ Unit 2 — Rapid Revision
Set = well-defined, distinct collection • Roster & set-builder form • symbols ∈ ∉ ⊂ ⊆ ∪ ∩ − ∅ U
n(A) = n ⟹ subsets = 2ⁿ, proper subsets = 2ⁿ − 1 • Power set P(A) • Equivalent sets (same n)
|A ∪ B| = |A| + |B| − |A ∩ B| • three-set formula with +|A ∩ B ∩ C| at the end
De Morgan: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ • A − B = A ∩ Bᶜ
Cartesian product: A × B = all ordered pairs, |A × B| = mn, A × B ≠ B × A
Relation = subset of A × B • domain, range, co-domain, inverse relation R⁻¹
Warshall: if M[i][k] = 1 and M[k][j] = 1 then M[i][j] = 1, for k = 1..n
Syllabus-based exam-style practice questions (not predictions) — Unit 2:
Define a set. Write its two forms of representation and the types of sets with examples. (5)
If A = {1,2,3,4}, B = {3,4,5,6}, find A ∪ B, A ∩ B, A − B and Aᶜ (with U given). (5)
State and verify De Morgan's laws with an example. (5–10)
Define Cartesian product; find A × B and B × A for given sets. (5)
Define a relation. Find the domain and range of a given relation. (5)
Explain reflexive, symmetric, antisymmetric and transitive relations with examples. (5–10)
Show that a given relation is an equivalence relation. (10)
Explain the connection between an equivalence relation and a partition of a set, with example. (5–10)
Represent a given relation by a matrix and a digraph; check its properties from the matrix. (5)
Find the transitive closure of a relation using Warshall's algorithm. (10)
Differentiate between an equivalence relation and a partial order relation with examples. (5)
UNIT 3 — Functions
3.1 Function — Definition, Domain, Range
Definition. A function f from a set A to a set B is a rule that assigns to each element of A exactly one element of B. It is written as
f : A → B, y = f(x)
Here: A = domain (set of all allowed inputs), B = co-domain (the target set), and the set of values actually obtained, {f(x) : x ∈ A}, is the range. The element y = f(x) is called the image of x, and x is called the pre-image of y.
Key condition: one input ⇒ exactly one output. If a single input can give two outputs, the rule is a relation but NOT a function.
In simple words: A function is a machine 🤖 — input daalo, output lo. Do rules: (i) har input ka output mile (koi input chhoot na jaye), (ii) har input ka sirf ek output ho. Range ⊆ co-domain hamesha hota hai, par dono equal hone zaroori nahi (equal hone ka matlab "onto" — Section 3.2).
Real life — function or not?
Roll number → student's name : FUNCTION ✔ (ek roll no ka ek naam)
Aadhaar number → person : FUNCTION ✔
Person → mobile number : FUNCTION ✔ (ek person ke kai number ho sakte hain,
par har person ka "primary number" ek hi hai)
Mobile number → person : NOT a function ✗ (shared/old numbers possible)
Student → grades in all subjects : NOT a function into R (output is a list)
f(x) = x² (x real) : FUNCTION ✔ (each x has one square)
x² + y² = 4 (y as a function of x?): NOT a function ✗ (x = 0 gives y = 2 and y = -2)
Graph test: a curve is a function if every VERTICAL line meets it at most once.
Solved Example 1 — domain, co-domain, range:
f : A → B, f(x) = x², A = {1, 2, 3, 4}, B = Z
Domain = A = {1, 2, 3, 4}
Co-domain = Z
Range = {1, 4, 9, 16} (only these values are actually produced)
Mapping picture (machine diagram):
1 → 1 2 → 4 3 → 9 4 → 16 har input ka exactly ek output ✔
Note: Range ⊆ Co-domain. Here Range ≠ Co-domain, so this function is
NOT onto (surjective) — see the next section.
Solved Example 2 — finding the natural domain:
(i) f(x) = 1/(x - 2) Denominator ≠ 0 → x ≠ 2
Domain = R - {2}
(ii) f(x) = √(x - 1) Under the square root, expression ≥ 0 → x ≥ 1
Domain = [1, ∞), Range = [0, ∞)
(iii) f(x) = 1/(x² - 9) x² ≠ 9 → x ≠ ±3
Domain = R - {-3, 3}
(iv) f(x) = x³ every real x allowed → Domain = R, Range = R
Counting functions (short-note favourite):
Set A has m elements, set B has n elements:
Total number of functions f : A → B = nᵐ
(each of the m inputs can independently choose any of the n outputs)
Number of one-one (injective) functions = nPm = n!/(n-m)! (only if n ≥ m)
Number of bijections from A to A (m = n) = n!
Example: A = {1,2,3}, B = {a,b} → total functions = 2³ = 8
A = {1,2}, B = {a,b,c} → one-one functions = 3P2 = 6
3.2 Injective (One-to-One), Surjective (Onto) and Bijective Functions
Type
Formal condition
Simple meaning
Example
Injective (one-one)
f(x₁) = f(x₂) ⟹ x₁ = x₂ (different inputs give different outputs)
Koi do input same output nahi dete
f(x) = 2x on Z ✔ • f(x) = x² on Z ✗ (f(2) = f(−2) = 4)
Surjective (onto)
Range = Co-domain, i.e. for every y ∈ B there exists x ∈ A with f(x) = y
Co-domain ka koi element bacha nahi
f(x) = x + 1 from Z→Z ✔ • f(x) = x² from R→R ✗ (no negative output)
Bijective
Injective and Surjective
Perfect one-to-one matching
f(x) = x + 5 on Z • f(x) = 2x on R
Trick:Injective = every output has at most one input ("In tak unique"), Surjective = Saara co-domain cover, Bijective = Best (both). Only a bijective function has an inverse (Section 3.4).
Solved Example 1 — prove f(x) = 2x + 1 (on Z) is injective:
Take x1, x2 ∈ Z with f(x1) = f(x2).
2x1 + 1 = 2x2 + 1
⟹ 2x1 = 2x2
⟹ x1 = x2
Since f(x1) = f(x2) forces x1 = x2, the function is INJECTIVE ✔
Is it onto (Z → Z)? For y ∈ Z we need f(x) = y ⟹ x = (y - 1)/2.
Take y = 4 → x = 3/2 ∉ Z ⟹ no integer input gives 4.
⟹ f is NOT surjective with co-domain Z. (It becomes surjective onto odd numbers.)
Solved Example 2 — f(x) = x² on different domains (domain matters!):
f : R → R, f(x) = x²
Injective? f(2) = 4 = f(-2) but 2 ≠ -2 → NOT injective ✗
Surjective? -1 has no pre-image (square cannot be negative) → NOT onto ✗
⟹ Only a function, not injective/surjective/bijective.
f : R → [0, ∞), f(x) = x²
Surjective? every non-negative y has pre-image √y ✔
⟹ Onto, but still not injective.
f : [0, ∞) → [0, ∞), f(x) = x²
Injective ✔ (increasing on this domain) AND Surjective ✔
⟹ BIJECTIVE, so the inverse exists: f⁻¹(y) = √y ✔
Moral: same formula, different domain/co-domain → different classification.
(Exam me domain-co-domain zaroor likho!)
Solved Example 3 — counting bijections:
A = {1, 2, 3}, B = {a, b, c} → number of bijections = 3! = 6
Number of one-one functions from a 3-element set to a 3-element set = 3! = 6,
which equals the number of onto functions — as expected for equal finite sets
(in a finite set of the same size, one-one ⟺ onto ⟺ bijective).
Real life: A bijection is a perfect matching — every groom has exactly one bride and none is left out 💍. Database primary keys must be injective (two rows can't share a key). Encryption must be bijective, otherwise decryption is impossible. In counting, the bijection principle lets us count one set by matching it with another. Pigeonhole principle (Unit 5) is literally the statement "if you try to fit m > n items injectively into n places, it is impossible".
3.3 Composition of Functions
Definition. If f : A → B and g : B → C, then the composition g ∘ f (read "g after f") is defined by
(g ∘ f)(x) = g(f(x)) for every x ∈ A
Domain of g ∘ f = {x ∈ A : f(x) ∈ domain of g}
Note: apply the RIGHT-HAND function first (right to left reading).
Solved Example — compute both compositions:
f(x) = x + 3, g(x) = x²
(f ∘ g)(x) = f(g(x)) = f(x²) = x² + 3
(g ∘ f)(x) = g(f(x)) = g(x + 3) = (x + 3)² = x² + 6x + 9
At x = 2:
(f ∘ g)(2) = 2² + 3 = 7
(g ∘ f)(2) = (5)² = 25 → different ⟹ f ∘ g ≠ g ∘ f
So composition is NOT commutative ⚠️ (but it is associative — see below).
Properties of composition:
(i) Associative: (f ∘ g) ∘ h = f ∘ (g ∘ h)
(ii) NOT commutative: f ∘ g ≠ g ∘ f in general
(iii) If I is the identity function I(x) = x, then f ∘ I = I ∘ f = f
(iv) If f and g are both injective, then g ∘ f is injective
(v) If f and g are both surjective, then g ∘ f is surjective
(vi) Composition of two bijections is a bijection
Solved Example — three functions (associativity check):
f(x) = 2x, g(x) = x + 1, h(x) = x²
((f ∘ g) ∘ h)(x) = (f ∘ g)(x²) = f(x² + 1) = 2(x² + 1) = 2x² + 2
(f ∘ (g ∘ h))(x) = f(g(x²)) = f(x² + 1) = 2x² + 2 ✔ same
On the other hand (h ∘ g)(x) = (x + 1)² = x² + 2x + 1
and (g ∘ h)(x) = x² + 1 → not equal ⟹ non-commutativity again.
Real life: Composition is a chain of processes 🔗. On a food-delivery app: order → restaurant (g) → delivery partner (f) → food at your door (f ∘ g). In programming, sqrt(abs(x)) is a composition; in compilers, each optimisation pass is a function and the compiler is their composition; in mathematics, converting °C → °F → K is a composition of two functions.
3.4 Inverse of a Function
Definition. If f : A → B is a bijection, then its inverse f−1 : B → A is defined by
f⁻¹(b) = a ⟺ f(a) = b
so that f⁻¹(f(x)) = x for all x ∈ A
and f(f⁻¹(y)) = y for all y ∈ B
The inverse exists ONLY for bijective functions. Method: write y = f(x),
solve for x in terms of y, then interchange the names (y ↔ x).
Solved Example 1 — find the inverse:
f(x) = 2x + 3 (f : R → R, bijective ✔)
Step 1: y = 2x + 3
Step 2: solve for x: 2x = y - 3 → x = (y - 3)/2
Step 3: replace y by x:
f⁻¹(x) = (x - 3)/2
VERIFY:
f⁻¹(f(4)) = f⁻¹(11) = (11 - 3)/2 = 4 ✔
f(f⁻¹(x)) = f((x-3)/2) = 2·(x-3)/2 + 3 = (x - 3) + 3 = x ✔
Solved Example 2 — cube function:
f(x) = x³ + 1 (bijective R → R ✔)
y = x³ + 1 → x³ = y - 1 → x = ∛(y - 1)
⟹ f⁻¹(x) = ∛(x - 1)
Check: f⁻¹(f(2)) = f⁻¹(9) = ∛8 = 2 ✔
Solved Example 3 — why x² has no inverse (on R):
f(x) = x² on R is not injective: f(2) = f(-2) = 4, so the "reverse rule"
would need to send 4 to both 2 and -2 — impossible for a function ✗
Fix: restrict the domain to [0, ∞). Then f(x) = x² is bijective
[0, ∞) → [0, ∞) and the inverse exists:
f⁻¹(x) = √x (with f⁻¹(f(4)) = √16 = 4 ✔)
Graphically, f⁻¹ is the mirror image of f about the line y = x.
Properties of the inverse: (f−1)−1 = f • (g ∘ f)−1 = f−1 ∘ g−1 (order reverses!) • f−1 is also a bijection • the graph of f−1 is the reflection of the graph of f in the line y = x.
3.5 Some Useful Functions for Computer Science
(a) Floor and Ceiling Functions
For a real number x:
FLOOR ⌊x⌋ = the greatest integer less than or equal to x ("neeche wala")
CEILING ⌈x⌉ = the smallest integer greater than or equal to x ("upar wala")
Basic properties:
⌊x⌋ ≤ x < ⌊x⌋ + 1 x - 1 < ⌊x⌋ ≤ x
⌈x⌉ - 1 < x ≤ ⌈x⌉ ⌈x⌉ = -⌊-x⌋
If n is an integer: ⌊x + n⌋ = ⌊x⌋ + n
If x is an integer: ⌊x⌋ = ⌈x⌉ = x, so ⌊x⌋ + ⌈x⌉ = 2x
If x is NOT an integer: ⌊x⌋ + ⌈x⌉ = 2⌊x⌋ + 1
e.g. x = 2.5: 2 + 3 = 5 = 2(2) + 1 ✔
Value
⌊x⌋ (floor)
⌈x⌉ (ceiling)
x = 3.7
3
4
x = 2.5
2
3
x = 5 (integer)
5
5
x = −2.3
−3 (careful: aur neeche jao!)
−2
x = −1.5
−2
−1
Solved Example:
⌊2.5⌋ + ⌈2.5⌉ = 2 + 3 = 5
⌊7.3⌋ = 7, ⌈7.3⌉ = 8, difference always 0 or 1
⌊-3.6⌋ = -4 (kyunki -4 ≤ -3.6 < -3) ✔
Pagination problem: 95 items, 10 items per page
pages = ⌈95/10⌉ = ⌈9.5⌉ = 10 pages (floor would wrongly give 9!)
Data-structure problem: number of complete pairs in n items = ⌊n/2⌋
Timing problem: 7:50 am "8 baje ki class" = ceiling; "kitne poore ghante" = floor.
CS me kahan use: Pagination, memory-block allocation, hashing (h(k) = k mod m with ⌊·⌋), block index in file systems, bucket number in counting sort, mid-point calculation ⌊(low + high)/2⌋ in binary search, and proofs — e.g. "merging two sorted lists of sizes m, n needs ⌈m/n⌉ ..." types of bounds come from floor/ceiling. Practice direct calculations such as: ⌊2.5⌋ + ⌈2.5⌉ jaisa.
(b) Exponential Function
The exponential function is f(x) = ax where a > 0 and a ≠ 1 (e.g. 2x, 10x, ex). Its inverse is the logarithm. Here a is called the base and x the exponent.
Laws of exponents:
a⁰ = 1 a^(x+y) = aˣ · aʸ (aˣ)ʸ = a^(xy)
a^(-x) = 1/aˣ aˣ / aʸ = a^(x-y) a^(1/n) = ⁿ√a
Range: (0, ∞) — an exponential is always positive, never zero.
Solved Example — solve exponential equations:
(i) 2^x = 64 → 2^x = 2⁶ → x = 6
(ii) 3^(x+1) = 81 → 3^(x+1) = 3⁴ → x + 1 = 4 → x = 3
(iii) 5^(2x-1) = 125 → 5^(2x-1) = 5³ → 2x - 1 = 3 → x = 2
(iv) Growth illustration:
2¹ = 2, 2¹⁰ = 1024, 2²⁰ = 10,48,576, 2³⁰ = 1,07,37,41,824
(har 10 step me value itni badh jaati hai ki numbers padhna mushkil —
yahi exponential growth hai 🌱)
CS me kahan use: Number of subsets of an n-element set = 2ⁿ • number of binary strings of length n = 2ⁿ (8-bit byte → 256 values, 16-bit → 65,536) • number of passwords = (size of alphabet)^length, e.g. 26⁴ = 4,56,976 • brute-force algorithms with complexity O(2ⁿ) (slow!) • population/compound-interest models. Exponential growth is why "sirf ek character badha do password me" makes a password dramatically stronger.
(c) Logarithmic Function
The logarithm is the inverse of the exponential:
y = log_a x ⟺ a^y = x (a > 0, a ≠ 1, x > 0)
Laws:
log(mn) = log m + log n (product rule)
log(m/n) = log m - log n (quotient rule)
log(mⁿ) = n · log m (power rule)
log_a 1 = 0, log_a a = 1, log_a aᵏ = k
Change of base: log_b x = log_a x / log_a b
Common notations: log x = log₁₀ x, ln x = log_e x, log₂ x (binary log)
(i) log₂ x = 5 → x = 2⁵ = 32
(ii) log₁₀ x + log₁₀ (x - 3) = 1
log₁₀ [x(x - 3)] = 1
x(x - 3) = 10¹ = 10
x² - 3x - 10 = 0 → (x - 5)(x + 2) = 0 → x = 5 or x = -2
But log of a negative number is not defined ⟹ reject x = -2
⟹ x = 5 ✔ (Check: log₁₀ 5 + log₁₀ 2 = log₁₀ 10 = 1 ✔)
(iii) log₃ 81 = x → 3^x = 81 = 3⁴ → x = 4
CS me kahan use (bahut important):Binary search — 10,00,000 sorted items me ek item dhoondhne me sirf ⌈log₂ 10,00,000⌉ ≈ 20 comparisons! Isliye O(log n) algorithms ko "practically fastest" mana jaata hai. Database indexes (B-trees) are log n, merge sort is O(n log n), information theory measures information in bits = log₂ (number of possibilities), file-system block sizes, audio volume (dB), earthquake Richter scale and chemistry pH are logarithmic scales. Rule of thumb: log n steps = 10 steps for n = 1000, 20 steps for n = 1 million.
(d) Polynomial Function
A polynomial function of degree n has the form
f(x) = aₙxⁿ + aₙ₋₁x^(n-1) + ... + a₁x + a₀, aₙ ≠ 0
Degree = n (the highest power). Examples:
f(x) = 2x² + 3x - 5 degree 2 (quadratic)
f(x) = x³ - 4x degree 3 (cubic)
f(x) = 7 degree 0 (constant polynomial)
The domain is R for every polynomial. Growth: polynomial of degree n can
handle at most n - 1 turning points and has at most n real roots.
Solved Example — evaluation and theorems:
f(x) = 2x³ - 6x² + 2x - 1, find f(3):
Direct: 2(27) - 6(9) + 2(3) - 1 = 54 - 54 + 6 - 1 = 5
Horner's method (fewer multiplications — used in software):
f(3) = ((2·3 - 6)·3 + 2)·3 - 1 = ((0)·3 + 2)·3 - 1 = (2)·3 - 1 = 5 ✔
Remainder Theorem: the remainder on dividing f(x) by (x - a) is f(a).
Here f(x) ÷ (x - 3) leaves remainder 5.
Factor Theorem: (x - a) is a factor of f(x) ⟺ f(a) = 0.
Check x² - 5x + 6 at x = 2: 4 - 10 + 6 = 0 → (x - 2) is a factor ✔
(Indeed x² - 5x + 6 = (x - 2)(x - 3).)
Growth speed — this table is worth memorising (used everywhere in DAA/complexity):
1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
(Constant < Logarithmic < Linear < Linearithmic < Quadratic < Cubic < Exponential < Factorial)
Feeling with real numbers:
n = 1,000: log₂ n ≈ 10 steps (binary search ⚡)
n = 1,000 steps (one loop)
n log n ≈ 10,000 steps (merge sort — still fine)
n² = 10,00,000 steps (nested loops 🐢)
2ⁿ ≈ 10³⁰¹ — impossible (brute force ❌)
Exam shortcut: 2ⁿ always beats any polynomial for large n; but for small n
(e.g. n = 10) n² < 2ⁿ is not always visible — always compare on big n.
⚡ Unit 3 — Rapid Revision
Function: each input → exactly one output • domain, co-domain, range (range ⊆ co-domain)
Total functions A(m) → B(n) = nm • one-one functions = nPm • bijections on n elements = n!
Injective: f(x₁) = f(x₂) ⟹ x₁ = x₂ • Surjective: range = co-domain • Bijective = both
f(x) = x² is neither injective nor surjective on R→R; on [0, ∞)→[0, ∞) it is bijective
Composition: (g ∘ f)(x) = g(f(x)), right to left • associative but NOT commutative
Inverse exists ⟺ bijective • y = f(x) solve karke x nikalo, phir y ↔ x • graph mirror about y = x
Logarithm = exponent ka ulta • log(mn) = log m + log n • logₐ(mⁿ) = n log m • log₂ 1024 = 10
Binary search ≈ log₂ n steps ⟹ 10 lakh items in ~20 steps
Polynomial: aₙxⁿ + ... + a₀, degree n • Horner's method for fast evaluation • remainder f(a), factor ⟺ f(a) = 0
Growth order: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
Syllabus-based exam-style practice questions (not predictions) — Unit 3:
Define a function with domain, co-domain and range; give one example and one non-example. (5)
Find the domain and range of f(x) = 1/(x − 2) and f(x) = √(x − 1). (5)
Define injective, surjective and bijective functions with examples; prove that f(x) = 2x + 1 is injective. (10)
Show that f(x) = x² is not bijective on R but is bijective on [0, ∞). (5)
If f(x) = x + 3 and g(x) = x², find (f ∘ g)(x) and (g ∘ f)(x). Is composition commutative? (5)
Find the inverse of f(x) = 2x + 3 and verify f(f⁻¹(x)) = x. (5)
Why does f(x) = x² have no inverse on R? Explain with domain restriction. (5)
Define floor and ceiling; evaluate ⌊2.5⌋ + ⌈2.5⌉, ⌊−3.6⌋. Give one application of each. (5)
State the laws of exponents and logarithms; solve 3x+1 = 81 and log₂ x = 5. (5–10)
Explain the use of the logarithmic function in binary search with an example. (5)
Compare the growth rates of log n, n, n log n, n² and 2ⁿ for n = 1000. (5)
UNIT 4 — Algebraic Structures
4.1 Binary Operation
Definition. A binary operation * on a non-empty set S is a rule that combines any two elements of S to produce another element of S. Formally * is a function
* : S × S → S, (a, b) ↦ a * b
The requirement that a * b ∈ S for all a, b ∈ S is called the CLOSURE property.
Solved Example — operation or not?
(i) Addition on Z: a * b = a + b, 5 + 3 = 8 ∈ Z ✔ closed
(ii) Multiplication on Z: a * b = a × b, 2 × 4 = 8 ∈ Z ✔ closed
(iii) Subtraction on N: 3 - 5 = -2 ∉ N ✗ closure fails
(iv) Division on Z: 3 ÷ 2 = 1.5 ∉ Z ✗ not a binary op.
(v) Subtraction on Z: 3 - 5 = -2 ∈ Z ✔ closed (but
it is not associative → cannot be a group, see below)
(vi) a * b = max(a, b) on Z: max(4, 7) = 7 ∈ Z ✔ closed
Properties a binary operation may have:
Commutative : a * b = b * a for all a, b ∈ S
Associative : (a * b) * c = a * (b * c) for all a, b, c ∈ S
Examples:
Addition on Z : commutative ✔ and associative ✔
Multiplication on Z : commutative ✔ and associative ✔
Subtraction on Z : NOT commutative ✗ and NOT associative ✗
(5 - 3 = 2 but 3 - 5 = -2;
(5 - 3) - 1 = 1 but 5 - (3 - 1) = 3)
Matrix multiplication: associative ✔ but NOT commutative ✗
Cayley (operation) table. For a small finite set, a binary operation can be shown as a table: entry in row a and column b is a * b. The operation is closed ⟺ every entry of the table is again an element of S. It is commutative ⟺ the table is symmetric about the main diagonal.
Solved Example — Cayley table of addition mod 4 on Z₄ = {0, 1, 2, 3}:
4.2 Group — Definition & All Properties High-yield syllabus topic
Definition. An algebraic structure (G, *) is called a group if it satisfies the following four axioms:
Closure: a, b ∈ G ⟹ a * b ∈ G
Associativity: (a * b) * c = a * (b * c) for all a, b, c ∈ G
Identity: there exists e ∈ G such that a * e = e * a = a for every a ∈ G
Inverse: for every a ∈ G there exists a−1 ∈ G such that a * a−1 = a−1 * a = e
If, in addition, a * b = b * a for all a, b ∈ G, then (G, *) is called an Abelian (commutative) group.
Two useful standard results (write them if asked):
(i) The identity element of a group is UNIQUE.
Proof: if e and e' are both identities then
e = e * e' = e' (using e' identity first, then e) ⟹ e = e'.
(ii) The inverse of each element is UNIQUE.
Proof: if b and c are both inverses of a then
b = b * e = b * (a * c) = (b * a) * c = e * c = c ⟹ b = c.
Also: (a * b)⁻¹ = b⁻¹ * a⁻¹ (reverse order — like the transpose of a product)
Trick — "CAII" (the 4 properties):Closure, Associativity, Identity, Inverse — "Group ki chaabi hai CAII" 🔑. Hierarchy ladder (each step adds one property):
Set
└─ Semigroup = Closure + Associativity
└─ Monoid = + Identity
└─ Group = + Inverse
└─ Abelian Group = + Commutativity
Solved Example 1 — prove that (Z, +) is an Abelian group:
G = Z = {..., -2, -1, 0, 1, 2, ...}, operation = ordinary addition
1. CLOSURE: a, b ∈ Z ⟹ a + b ∈ Z
e.g. 4 + (-7) = -3 ∈ Z ✔
2. ASSOCIATIVITY: (a + b) + c = a + (b + c) (true for integers)
e.g. (2 + 3) + 4 = 9 = 2 + (3 + 4) ✔
3. IDENTITY: e = 0, because a + 0 = 0 + a = a ✔
4. INVERSE: for a, the inverse is -a (since a + (-a) = 0)
e.g. 5 + (-5) = 0 ✔
5. COMMUTATIVE: a + b = b + a ✔
All five properties hold ⟹ (Z, +) is an ABELIAN GROUP ✔
Solved Example 2 — prove that (Z₄, +₄) is a group:
Z₄ = {0, 1, 2, 3}, operation = addition modulo 4
Closure: 1 + 3 = 4 ≡ 0 ∈ Z₄ ; 2 + 3 = 5 ≡ 1 ∈ Z₄ ✔
Associativity: (1 + 2) + 3 = 3 + 3 = 6 ≡ 2
1 + (2 + 3) = 1 + 5 = 6 ≡ 2 ✔
Identity: e = 0 (a + 0 ≡ a mod 4) ✔
Inverse: 0⁻¹ = 0, 1⁻¹ = 3 (1+3 = 4 ≡ 0), 2⁻¹ = 2 (2+2 = 4 ≡ 0),
3⁻¹ = 1 ✔
Commutative: 1 + 2 ≡ 3 and 2 + 1 ≡ 3 ✔
⟹ (Z₄, +₄) is an ABELIAN group of order 4 ✔
IMPORTANT GENERAL RESULT: (Zₙ, +ₙ) is always a group (Abelian) for every n ≥ 1,
because addition mod n is closed, associative, has identity 0 and every
element a has inverse n - a.
Solved Example 3 — (Q − {0}, ×) is an Abelian group:
Closure: ratio × ratio = ratio (≠ 0) ✔
Associativity: (a/b × c/d) × e/f = a/b × (c/d × e/f) ✔
Identity: e = 1 (x · 1 = x) ✔
Inverse: 1/x for every non-zero rational x ✔
Commutative: a/b × c/d = c/d × a/b ✔
⟹ Abelian group ✔
Solved Example 4 — a NON-ABELIAN group (matrices):
G = set of all 2 × 2 real matrices with non-zero determinant, operation = ×
A = [ 1 1 ] B = [ 1 0 ] det A = 1, det B = 1 → both in G
[ 0 1 ] [ 1 1 ]
AB = [ 1+1 1 ] = [ 2 1 ] BA = [ 1 1 ] = [ 1 1 ]
[ 0 1 ] [ 0 1 ] [ 1 2 ] [ 1 2 ]
AB ≠ BA ⟹ this group is NON-ABELIAN ✗ (matrix multiplication generally
does not commute). Closure ✔, associative ✔, identity I ✔, inverses exist
(because det ≠ 0) ✔ — so it IS a group, just not Abelian.
Solved Example 5 — non-examples (why they fail):
(N, +) : identity 0 ∉ N ⟹ no identity element ✗ not a group
(Z, ×) : identity 1 ✔, but 2 has inverse 1/2 ∉ Z ✗ not a group
(Z, -) : not associative: (5-3)-1 = 1 but 5-(3-1) = 3 ✗ not a group
(N, ×) : closure ✔, identity 1 ✔, but inverse missing ✗ monoid, not group
(M₂(R), ×): singular matrices have no inverse ✗ not a group
(M₂(R), +): all four properties hold ✔ Abelian group
4.3 Finite & Infinite Groups, Order of a Group and of an Element
Definitions.
Finite group : a group having a finite number of elements.
Order of a group |G| : the number of elements in G (only for finite groups).
Infinite group : e.g. (Z, +), (R, +), (Q - {0}, ×) — infinitely many elements.
Order of an element a : the smallest positive integer n such that aⁿ = e
(written o(a)), where aⁿ means a * a * ... * a (n times).
If no such n exists, the element has INFINITE order.
Solved Example 1 — order of every element of Z₆ = {0,1,2,3,4,5} (addition mod 6):
Element Powers (adding the element repeatedly mod 6) Order
0 0 1
1 1,2,3,4,5,0 6
2 2,4,0 3
3 3,0 2
4 4,2,0 3
5 5,4,3,2,1,0 6
Observations: order of group = 6, and every element's order
(1, 6, 3, 2, 3, 6) DIVIDES 6 ✔ — this is always true:
THEOREM: the order of an element divides the order of the group.
Also note: elements of order 6 are 1 and 5 — these are the generators
of the group (see Section 4.5).
Solved Example 2 — infinite order and other groups:
In (Z, +): the identity is 0. Take a = 5: 5, 10, 15, 20, ... never 0
⟹ 5 has INFINITE order ✔ (every non-zero element of (Z,+) has
infinite order).
In (R - {0}, ×): 2, 4, 8, ... never 1 ⟹ infinite order; but -1 has order 2
because (-1)² = 1 ✔
4.4 Subgroups
Definition. A non-empty subset H of a group (G, *) is called a subgroup of G if (H, *) is itself a group under the same operation. Written H ≤ G.
Tests (use the shortest one that works):
Two-step test : (i) H is closed under *, (ii) for every a ∈ H, a⁻¹ ∈ H
(identity then comes free)
One-step test : for all a, b ∈ H: a * b⁻¹ ∈ H
Trivial subgroups: {e} and G itself. A subgroup other than these is a
PROPER (non-trivial) subgroup.
Solved Example 1 — the even integers in (Z, +):
G = (Z, +), H = {..., -4, -2, 0, 2, 4, ...} (even integers)
Closure : even + even = even ✔
Identity: 0 ∈ H (0 is even) ✔
Inverse : 4 + (-4) = 0 and -4 ∈ H ✔
⟹ H is a subgroup of (Z, +) ✔
COUNTER-EXAMPLE: H = odd integers
odd + odd = even ∉ H ⟹ closure fails ⟹ not a subgroup ✗
Also, for every n ≥ 1 the set nZ = {..., -2n, -n, 0, n, 2n, ...} is a subgroup
of (Z, +).
Solved Example 2 — subgroup of Z₆ (with Cayley table):
G = (Z₆, +₆), H = {0, 2, 4}
+₆ | 0 2 4
----+------------
0 | 0 2 4
2 | 2 4 0
4 | 4 0 2
Closure ✔ (table contains only 0, 2, 4)
Identity 0 ∈ H ✔
Inverse: 2⁻¹ = 4 (2+4 = 6 ≡ 0), 4⁻¹ = 2, 0⁻¹ = 0 ✔
⟹ H is a subgroup of order 3 ✔
LAGRANGE'S THEOREM: the order of a subgroup divides the order of the group.
Here 3 divides 6 ✔
Subgroups of Z₆ and their orders: {0} (1), {0,3} (2), {0,2,4} (3), Z₆ (6)
— all divisors of 6 ✔
CS application: Subgroups and their cosets are the base of many encryption schemes; the set of invertible matrices forms a group under multiplication (used in graphics pipelines), and the set of permutations of n objects forms the symmetric group Sₙ (used in sorting analysis, Rubik's cube solving, and randomised algorithms). Error-correcting codes use subgroups of (Z₂)ⁿ — bit strings with XOR as the operation.
4.5 Cyclic Groups
Definition. A group G is called cyclic if there exists an element a ∈ G such that every element of G can be written as a power of a:
G = ⟨a⟩ = { a, a², a³, ..., aⁿ = e }
The element a is called a GENERATOR of G and we write G = ⟨a⟩.
A cyclic group has at least one generator; an element a ∈ G generates G
⟺ the order of a equals the order of the group.
Solved Example 1 — Z₆ is cyclic:
G = (Z₆, +₆) = {0, 1, 2, 3, 4, 5}, order of group = 6
Take a = 1 (repeatedly add 1):
1, 2, 3, 4, 5, 0 → covers the whole group ⟹ 1 is a generator ✔
Take a = 5 (repeatedly add 5 ≡ subtract 1):
5, 4, 3, 2, 1, 0 → also covers the whole group ⟹ 5 is a generator ✔
Take a = 2: 2, 4, 0, 2, ... only generates {0, 2, 4} ⟹ NOT a generator
⟹ Z₆ is cyclic with exactly two generators: 1 and 5 (the elements of order 6).
General rule: the generators of (Zₙ, +ₙ) are the elements coprime to n.
Solved Example 2 — the multiplicative group (Z₇*, × mod 7):
G = {1, 2, 3, 4, 5, 6}, operation = multiplication mod 7, order = 6
Powers of 3:
3¹ = 3
3² = 9 ≡ 2
3³ = 27 ≡ 6
3⁴ = 81 ≡ 4
3⁵ = 243 ≡ 5
3⁶ = 729 ≡ 1 = e ← back to identity
⟹ 3 generates all six elements ⟹ 3 is a generator ⟹ the group is CYCLIC ✔
(Powers of 3: 3, 2, 6, 4, 5, 1 — the whole group.)
Compare with 2: 2, 4, 1, 2, ... → order 3 only, so 2 is not a generator.
Properties of cyclic groups:
(i) Every cyclic group is Abelian (aⁱaʲ = a^(i+j) = aʲaⁱ)
— but an Abelian group need not be cyclic.
(ii) Every subgroup of a cyclic group is cyclic.
(iii) A finite cyclic group of order n is isomorphic to (Zₙ, +ₙ).
(iv) (Z, +) is an infinite cyclic group with generators 1 and -1.
(v) If a is a generator, then a⁻¹ is also a generator.
(vi) (Zₙ, +ₙ) is cyclic for every n; its generators are the elements
coprime to n (there are φ(n) of them — Euler's totient).
CS application (cryptography):RSA works in the multiplicative group modulo n (a product of two primes) — encryption is modular exponentiation, decryption uses the inverse exponent. Diffie–Hellman key exchange (the base of HTTPS/WhatsApp security) uses a cyclic group and a generator g: both sides publish ga and gb and secretly compute gab. Elliptic-curve cryptography uses a cyclic group of points on a curve. Cyclic groups also appear in hashing, pseudorandom generators and error-correcting codes.
⚡ Unit 4 — Rapid Revision
Binary operation: S × S → S (closure must hold) • commutative / associative
Syllabus-based exam-style practice questions (not predictions) — Unit 4:
Define a binary operation. Give two examples and two non-examples with reasons. (5)
Define a group and explain its four properties with an example. (10)
Prove that (Z, +) is an Abelian group. (10)
Show that (Q − {0}, ×) is an Abelian group. (5–10)
Show that (Zₙ, +ₙ) is a group; verify for n = 4 or 5. (10)
Give an example of a non-Abelian group and justify. (5)
Explain semigroup, monoid, group and Abelian group with the hierarchy diagram. (5)
Define the order of a group and the order of an element; find the order of every element of Z₆. (5–10)
State Lagrange's theorem and verify it for the subgroups of Z₆. (5)
Define a subgroup and show that the even integers form a subgroup of (Z, +). (10)
Define a cyclic group; show that Z₆ / Z₇* is cyclic and find its generators. (10)
Prove that every cyclic group is Abelian. Is the converse true? Justify. (5)
UNIT 5 — Counting and Recurrence Relations
5.1 Basics of Counting — Sum and Product Rules
Sum Rule (either–or). If a task can be done in m ways and another task can be done in n ways, and the two tasks cannot be done at the same time, then the number of ways of doing either task is
m + n
Product Rule (and). If a task is completed in two stages, where the first stage can be done in m ways and (for each of these) the second stage can be done in n ways, then the number of ways of doing both is
m × n
(The product rule extends to any number of stages: m × n × p × ...)
In simple words: "ya ... ya" (OR) → jod (sum rule). "aur" (AND / one after another) → guna (product rule). Pehle decide karo: question me OR hai ya AND?
Solved Example 1 — canteen menu:
4 types of tea and 3 types of samosa are available.
(i) Choose one item (either tea or samosa): 4 + 3 = 7 ways (SUM rule)
(ii) Choose one tea AND one samosa: 4 × 3 = 12 ways (PRODUCT rule)
Tree diagram idea: each of the 4 teas can be paired with each of the
3 samosas → 4 branches × 3 sub-branches = 12 paths ✔
Solved Example 2 — outfits:
5 shirts, 4 pants and 3 pairs of shoes.
Number of different outfits = 5 × 4 × 3 = 60 ✔
Solved Example 3 — passwords (with and without repetition):
A 4-character password using only letters (a - z):
WITH repetition allowed: 26 × 26 × 26 × 26 = 26⁴ = 4,56,976
Letters or digits (36 symbols): 36⁴ = 16,79,616
Letters + digits + 2 special → much larger (that is why mixing is safer!)
WITHOUT repetition: 26 × 25 × 24 × 23 = 3,58,800
Solved Example 4 — with a restriction (careful counting):
How many 4-digit EVEN numbers can be formed using 1, 2, 3, 4, 5 without repeating
any digit?
The last digit must be even (2 or 4) → 2 choices.
Then the first digit: any of the remaining 4 digits → 4 choices
Second digit: 3 choices, third digit: 2 choices.
Total = 2 × 4 × 3 × 2 = 48 numbers ✔
(If repetition were allowed: last digit 2 ways × 5 × 5 × 5 = 250.)
Exam strategy for counting questions: (1) Draw boxes for the positions (e.g. _ _ _ _). (2) Fill the position with the most restrictions first (here: the last digit). (3) Decide about repetition — "without repetition" means each number used once. (4) Multiply box by box. (5) If the question says "at least", count the complement and subtract from the total.
5.2 Pigeonhole Principle
Statement. If n items are placed into m containers (pigeonholes) and n > m, then at least one container must contain more than one item.
Generalised (strong) form: if n items are placed into m containers, then some container contains at least
⌈ n / m ⌉ items (ceiling of n/m)
Proof (by contradiction): suppose every container had at most ⌈n/m⌉ − 1 items. Then the total number of items would be at most m(⌈n/m⌉ − 1) < n, which contradicts "n items". Hence some container has at least ⌈n/m⌉ items.
Solved Example 1 — birthdays:
In a group of 13 students, show that at least two have birthdays in the same
month.
Items (pigeons) = 13 students
Containers = 12 months
n = 13 > m = 12 ⟹ at least ⌈13/12⌉ = 2 students share a month ✔
Solved Example 2 — socks (classic):
A drawer has 10 red, 10 blue and 10 black socks, all mixed. Draw socks in the
dark. How many must be drawn to GUARANTEE a matching pair?
Think worst case: the first 3 draws could be one of each colour (R, B, K).
The 4th draw must repeat a colour.
⟹ 4 socks guarantee at least 2 of the same colour ✔
Extension — guarantee a pair of BLACK socks: worst case, draw all 10 red + all
10 blue before any black, then 2 black ⟹ 10 + 10 + 2 = 22 socks.
(The principle: worst case + 1 = guaranteed.)
Solved Example 3 — boxes and balls:
100 balls are put into 9 boxes. Show that some box contains at least 12 balls.
⌈100/9⌉ = ⌈11.11⌉ = 12 ⟹ at least one box has ≥ 12 balls ✔
Also classic: n + 1 numbers chosen from {1, 2, ..., 2n} ⟹ two of them are
consecutive? — handled by the "n boxes" construction (pairs as boxes).
Solved Example 4 — hashing (CS version):
1000 keys are hashed into a hash table with 999 slots. Will a collision occur?
n = 1000 keys > m = 999 slots ⟹ at least ⌈1000/999⌉ = 2 keys land in the
same slot ⟹ a collision is GUARANTEED (not just likely) ✔
This is the standard proof used to explain why collisions in hashing are
unavoidable once the number of keys exceeds the number of slots.
Where it is used: proving collisions in hashing, the birthday paradox (with only 23 people there is more than a 50% chance of a shared birthday), duplicate detection in big data, error bounds in approximation algorithms, network packet routing, and even in competitive programming proofs. This is a compact principle with useful applications in computer science.
Golden trick — "P for Position, C for Choose": if ranks/positions/order matter (1st, 2nd, passwords, queue) → P. If only the group matters (team, committee, hand of cards) → C. Bonus identities: nCr = nCn−r • nC0 = nCn = 1 • nC1 = n • nC2 = n(n−1)/2.
(i) 4-digit PIN with repetition allowed: 10 × 10 × 10 × 10 = 10⁴ = 10,000
(ii) 4-digit PIN without repetition: 10P4 = 10 × 9 × 8 × 7 = 5040
(iii) Arrangements of the word "MATHS" (5 distinct letters): 5! = 120
(iv) Arrangements of "BOOK" (O repeats twice): 4! / 2! = 24/2 = 12
(v) Circular arrangements of 5 people:
(5 - 1)! = 4! = 24 (a circle has no first seat, so fix one person)
Solved Example 3 — committees and cards:
(i) Choose a 3-member committee from 10 students: 10C3 = 120
(ii) Choose a president, secretary and treasurer from 10 students (positions
are different): 10P3 = 720
(iii) Number of handshakes if 10 people all shake hands once:
10C2 = 10 × 9/2 = 45
(iv) Number of 5-card hands from a 52-card deck:
52C5 = 25,98,960
(v) Number of diagonals of a polygon with n sides = nC2 - n
Exam checklist: Does order matter? (P vs C) • Is repetition allowed? (multiply again vs use nPr) • Are identical items present? (divide by the factorials of repeats) • Circular arrangement? ((n − 1)!) • Are there conditions like "at least one"? (total − none)
5.4 Binomial Coefficients and the Binomial Theorem
Binomial Theorem. For a positive integer n:
(a + b)ⁿ = nC0·aⁿ + nC1·a^(n-1)b + nC2·a^(n-2)b² + ... + nCn·bⁿ
General term: T(r+1) = nCr · a^(n-r) · b^r
Sum of coefficients: nC0 + nC1 + ... + nCn = 2ⁿ (put a = b = 1)
Number of terms: n + 1
The numbers nCr are called binomial coefficients.
Expansions (learn these):
(a + b)² = a² + 2ab + b² coefficients: 1 2 1
(a + b)³ = a³ + 3a²b + 3ab² + b³ coefficients: 1 3 3 1
(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴ coefficients: 1 4 6 4 1
Pascal's Triangle (every number = sum of the two numbers above it):
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Each row r gives the coefficients of (a + b)^r ✔
Properties of binomial coefficients:
(i) nC0 = nCn = 1 (first and last coefficient)
(ii) nC1 = n
(iii) nCr = nC(n-r) (symmetry)
(iv) Pascal's identity: nCr + nC(r-1) = (n+1)Cr
(v) nC0 + nC1 + ... + nCn = 2ⁿ (total number of subsets!)
(vi) nC0 - nC1 + nC2 - ... = 0 (alternating sum)
(vii) Σ r·nCr = n·2^(n-1)
(i) Coefficient of x³ in (1 + x)⁷:
General term = 7Cr · x^r → we need r = 3
Coefficient = 7C3 = 35 ✔
(ii) Coefficient of x⁵ in (1 + x)⁷ = 7C5 = 7C2 = 21 ✔
(iii) Middle term of (a + b)⁶ (n = 6 even → one middle term, r = 3):
T4 = 6C3 a³b³ = 20 a³b³ ✔
(iv) Term independent of x in (x + 1/x)⁴:
General term = 4Cr · x^(4-r) · x^(-r) = 4Cr · x^(4-2r)
Independent of x ⟹ 4 - 2r = 0 ⟹ r = 2 ⟹ term = 4C2 = 6 ✔
CS me kahan use: Probability of getting exactly k heads in n coin tosses = nCk/2n (binomial distribution — the base of statistics and machine learning). The identity ΣnCr = 2n proves that an n-element set has 2n subsets (Unit 2). Binomial coefficients also count paths in a grid (lattice paths), appear in error-correcting codes, in hashing analysis, and in the analysis of randomised algorithms.
5.5 Recurrence Relations — Introduction
Definition. A recurrence relation for a sequence {an} is an equation that expresses the n-th term in terms of one or more previous terms. Together with initial conditions (given starting values) it defines the sequence uniquely.
Order : the difference between the highest and lowest indices used
Degree : the highest power of a term appearing
Linear : every term appears to the first power only (no aₙ², no aₙaₙ₋₁)
Homogeneous : if every term involves aₙ-type terms only (no constants, no n)
e.g. an = 2a(n-1) → homogeneous
an = 3a(n-1) + 2 → non-homogeneous (constant 2)
In simple words: A recurrence is a rule of the form "aaj kal se, kal aaj se" 🔁 — the next value depends on the previous ones. Example: savings rule "every month add ₹1000": A(n) = A(n − 1) + 1000. To get a closed formula (directly computable for any n) we solve the recurrence — that is the next section.
Standard recurrences (learn the definitions and initial conditions):
Method for a linear homogeneous recurrence with constant coefficients, e.g. an = c1an−1 + c2an−2:
Step 1: Assume a solution of the form aₙ = rⁿ (r ≠ 0).
Step 2: Substitute in the recurrence to get the CHARACTERISTIC EQUATION
r² - c1·r - c2 = 0 (for order 2)
Step 3: Solve the characteristic equation.
• Distinct real roots r1, r2 : aₙ = A·r1ⁿ + B·r2ⁿ
• Repeated root r (double) : aₙ = (A + Bn)·rⁿ
• Complex roots : use the general real solution with
sines/cosines (rarely asked)
Step 4: Put the initial conditions (n = 0, 1, 2, ...) to find A and B.
Step 5: Write the final closed form and verify with one value.
For a NON-homogeneous recurrence aₙ = c1a(n-1) + c2a(n-2) + f(n):
general solution = homogeneous solution + particular solution.
Solved Example 1 — Fibonacci (full solution):
F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
Step 1: assume F(n) = rⁿ → rⁿ = r^(n-1) + r^(n-2)
Step 2: divide by r^(n-2): r² = r + 1 → r² - r - 1 = 0
Step 3: roots r = (1 ± √5)/2
r1 = (1 + √5)/2 ≈ 1.618 (the golden ratio φ)
r2 = (1 - √5)/2 ≈ -0.618
Step 4: general solution: F(n) = A·r1ⁿ + B·r2ⁿ
F(0) = 0: A + B = 0 → B = -A
F(1) = 1: A·r1 + B·r2 = 1
A(r1 - r2) = 1
A·√5 = 1 → A = 1/√5, B = -1/√5
Step 5: FINAL CLOSED FORM (Binet's formula):
F(n) = (1/√5) [ ((1+√5)/2)ⁿ - ((1-√5)/2)ⁿ ]
Verify n = 6: ((1.618)⁶ - (-0.618)⁶)/√5 = (17.944 - 0.0557)/2.2361 ≈ 8.0 ✔
(the sequence value F(6) = 8 — correct!)
Solved Example 2 — repeated root case:
aₙ = 6a(n-1) - 9a(n-2), a₀ = 1, a₁ = 6
Step 1-2: r² - 6r + 9 = 0
Step 3: (r - 3)² = 0 → r = 3 (repeated root)
⟹ solution form: aₙ = (A + Bn)·3ⁿ
Step 4: a₀ = 1: (A + 0)·1 = 1 → A = 1
a₁ = 6: (1 + B)·3 = 6 → 1 + B = 2 → B = 1
Step 5: aₙ = (1 + n)·3ⁿ ✔
Verify: a₂ from the recurrence = 6(6) - 9(1) = 27;
from the formula = (1 + 2)·9 = 27 ✔
Solved Example 3 — Tower of Hanoi (non-homogeneous):
T(n) = 2T(n-1) + 1, T(1) = 1
Step 1: homogeneous part r - 2 = 0 → r = 2
homogeneous solution: A·2ⁿ
Step 2: particular solution — try a constant T(n) = c:
c = 2c + 1 → -c = 1 → c = -1
Step 3: general solution: T(n) = A·2ⁿ - 1
Step 4: T(1) = 1: 2A - 1 = 1 → A = 1
Step 5: T(n) = 2ⁿ - 1 ✔
Verify: T(2) = 2(1) + 1 = 3 and 2² - 1 = 3 ✔ ; T(3) = 7 ✔
Meaning: for n = 64 disks the monks need 2⁶⁴ - 1 ≈ 1.8 × 10¹⁹ moves — at one
move per second that is about 585 billion years 😲
Solved Example 4 — another non-homogeneous recurrence:
Five steps to write in the exam (examiners look for these):
1️⃣ Write the characteristic equation by substituting an = rn.
2️⃣ Solve it and state the roots (distinct / repeated / complex).
3️⃣ Write the general solution in the correct form (A·r₁n + B·r₂n for distinct, (A + Bn)rn for repeated).
4️⃣ Use the initial conditions to find A and B (show the two equations).
5️⃣ Write the final formula and verify it with one value — that verification line often carries a mark.
Solve the Tower of Hanoi recurrence T(n) = 2T(n−1) + 1, T(1) = 1 and state its complexity. (10)
Solve an = 3an−1 + 2, a₀ = 1. (5–10)
🏁 Whole Paper BCA102T — final strategy: Units 1 and 5 often require sustained calculation practice because they include matrix procedures and recurrence/counting methods; this is a study-planning observation, not an official weightage or prediction. All five units remain examinable unless the university says otherwise. Units 2–3 are mostly definitions with examples. Unit 4 (groups) carries verification-type questions — proving (Z, +) is a group, checking subgroups, finding generators — which come from practice, not memorisation. Make one formula card: determinant rules (including |kA| = kⁿ|A|), inverse and adjoint formula, Cramer's rule, characteristic equation, eigen equation, nPr, nCr, pigeonhole, and the five recurrence-solving steps. Revise it before the exam as a memory aid; the syllabus does not publish unit-wise weightage or guarantee a score. 💪