Introduction to Discrete Structure &Linear Algebra (AL-401) - Unit 1 Short Notes

UNIT 1: Introduction to Discrete Structure & Linear Algebra – Short Notes

1. Foundational Concepts

Set Theory

Definitions & Operations:

• Union: $$\displaystyle A \cup B = \{x \mid x \in A \text{ or } x \in B\} $$

• Intersection: $$\displaystyle A \cap B = \{x \mid x \in A \text{ and } x \in B\} $$

• Difference: $$\displaystyle A - B = \{x \mid x \in A \text{ and } x \notin B\} $$

• Complement: $$\displaystyle A' = U - A $$ (relative to universal set $U$)

• Cartesian Product: $$\displaystyle A \times B = \{(a,b) \mid a \in A, b \in B\} $$

Key Set Identities (Prove via Venn Diagrams):

1. De Morgan's Laws:

$$(A \cup B)' = A' \cap B'$$

$$(A \cap B)' = A' \cup B'$$

2. Distributive Laws:

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$

$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$

3. Difference Law:

$$A - (B \cap C) = (A - B) \cup (A - C)$$

[!TIP] Exam Tip: For Venn diagram proofs, shade LHS and RHS separately and show they cover identical regions. Always label sets clearly.

Propositional Logic

Basic Connectives:

Truth Tables: Construct for any compound proposition.
Tautology: Always true (e.g., $p \lor \neg p$).
Contradiction: Always false (e.g., $p \land \neg p$).

Logical Equivalences (Laws of Algebra of Propositions):

• Identity: $p \land T \equiv p$, $p \lor F \equiv p$

• Domination: $p \lor T \equiv T$, $p \land F \equiv F$

• Idempotent: $p \lor p \equiv p$, $p \land p \equiv p$

• Double Negation: $\neg(\neg p) \equiv p$

• Commutative, Associative, Distributive

• De Morgan's: $\neg(p \land q) \equiv \neg p \lor \neg q$, $\neg(p \lor q) \equiv \neg p \land \neg q$

• Implication: $p \Rightarrow q \equiv \neg p \lor q$

• Biconditional: $$\displaystyle p \Leftrightarrow q \equiv (p \Rightarrow q) \land (q \Rightarrow p) $$

Normal Forms:

• Disjunctive Normal Form (DNF): OR of ANDs (minterms).

  Example: $(p \land q) \lor (\neg p \land q)$

• Conjunctive Normal Form (CNF): AND of ORs (maxterms).

  Example: $(p \lor q) \land (\neg p \lor q)$

[!TIP] Common Pitfall: $p \Rightarrow q$ is not equivalent to $q \Rightarrow p$. Use truth tables to verify.

2. Relations and Ordered Sets

Properties of Relations (on set $A$)

Equivalence Relation: Reflexive, symmetric, and transitive.
Example: Congruence modulo $m$: $a \equiv b \pmod{m} \iff m \mid (a-b)$.

[!TIP] Proof Strategy: For $R$ defined by $aRb \iff P(a,b)$, check each property by assuming $a,b,c \in A$ and verifying the logical condition.

Transitive Closure

Definition: Smallest transitive relation containing $R$. Denoted $$\displaystyle R^+ $$ or $$\displaystyle R^* $$ (if reflexive also included).
Common Relations on $\mathbb{Z}$:

1. $$\displaystyle aSb \iff a+1 = b $$ → Transitive closure is $a \le b$.

2. $$\displaystyle aRb \iff a-b = 2 $$ → Transitive closure is $a \equiv b \pmod{2}$ (same parity).

3. $$\displaystyle aRb \iff a^2 - b^2 $$ divisible by 4 → Transitive closure is $a \equiv b \pmod{2}$ (same parity).

Composite Relations: $$\displaystyle R^2 = R \circ R = \{(a,c) \mid \exists b, (a,b) \in R \land (b,c) \in R\} $$.

[!TIP] Exam Question: "If $R$ is irreflexive, is $$\displaystyle R^2 $$ necessarily irreflexive?"

Answer: No. Counterexample: $$\displaystyle R = \{(1,2), (2,1)\} $$ on $\{1,2\}$. $R$ is irreflexive, but $$\displaystyle R^2 = \{(1,1), (2,2)\} $$ is reflexive.

Partial Orders and Hasse Diagrams

Poset (Partially Ordered Set): Set $A$ with relation $\le$ that is reflexive, antisymmetric, transitive.

Hasse Diagram Construction:

1. Draw vertices for elements.

2. Draw edge $a \to b$ if $$\displaystyle a < b $$ and no $c$ with $$\displaystyle a < c < b $$.

3. Omit reflexive loops and transitive edges.

4. Place smaller elements lower.

Example Divisibility Posets:

• $$\displaystyle D_{15} = \{1,3,5,15\} $$:

  
    15
  
   /  \
  
  3    5
  
   \
  
    1
  
  

• $$\displaystyle D_{24} = \{1,2,3,4,6,8,12,24\} $$:

  
        24
  
      /  |  \
  
     12  8   6
  
    /  \ |  /
  
   4    3 2
  
    \  /
  
     1
  
  

Lattice: Poset where every pair $\{a,b\}$ has least upper bound (join, $a \vee b$) and greatest lower bound (meet, $a \wedge b$).
Example: $$\displaystyle (D_m, \mid) $$ is a lattice with $$\displaystyle a \vee b = \text{lcm}(a,b) $$, $$\displaystyle a \wedge b = \text{gcd}(a,b) $$.

Extreme Elements in Poset:

• Minimal: No element strictly smaller.

• Maximal: No element strictly larger.

• Least: Smaller than all others (unique if exists).

• Greatest: Larger than all others (unique if exists).

[!TIP] Hasse Diagram Rules: Never draw edges upward. Covering relation: $a$ covers $b$ if $$\displaystyle a > b $$ and no element between.

Special Relations

Factor Relation: On $$\displaystyle \mathbb{Z}^+ $$, $aRb \iff a \mid b$ (a divides b). Reflexive, antisymmetric, transitive → partial order.

Congruence Modulo $m$: $a \equiv b \pmod{m} \iff m \mid (a-b)$.
Proof it's equivalence:

1. Reflexive: $$\displaystyle a-a=0 $$, divisible by $m$.

2. Symmetric: If $m \mid (a-b)$, then $m \mid (b-a)$.

3. Transitive: If $m \mid (a-b)$ and $m \mid (b-c)$, then $m \mid (a-c)$.

3. Algebraic Structures

Groups

Definition: Set $G$ with binary operation $*$ satisfying:

1. Closure: $a*b \in G$

2. Associativity: $$\displaystyle (a*b)*c = a*(b*c) $$

3. Identity: $\exists e \in G$ s.t. $$\displaystyle e*a = a*e = a $$

4. Inverse: $\forall a \in G$, $$\displaystyle \exists a^{-1} $$ s.t. $$\displaystyle a*a^{-1} = a^{-1}*a = e $$

Examples:

• $(\mathbb{Z}, +)$: Infinite cyclic group.

• $$\displaystyle (\mathbb{Z}_n, +_n) $$: Finite cyclic group.

• $$\displaystyle (\mathbb{Z}_n^*, \times_n) $$: Units modulo $n$ (e.g., $$\displaystyle \mathbb{Z}_7^* = \{1,2,3,4,5,6\} $$ under $$\displaystyle \times_7 $$).

• $\{-1,1,i,-i\}$ under multiplication: Abelian, cyclic (generated by $i$).

Subgroup $H \le G$:

• Nonempty subset closed under operation and inverses.

• Test: $H \neq \emptyset$ and $\forall a,b \in H$, $$\displaystyle a*b^{-1} \in H $$.

Example: In $$\displaystyle G = \{e,a,a^2,a^3,b,ab,a^2b,a^3b\} $$ (dihedral-like), $$\displaystyle H = \{e,a,a^2,a^3\} $$ is subgroup (closed, contains identity/inverses).

Normal Subgroup: $H \trianglelefteq G$ iff $$\displaystyle xHx^{-1} = H $$ for all $x \in G$.
Equivalent: Left cosets = right cosets.

Abelian Group: Operation commutative: $$\displaystyle a*b = b*a $$ for all $a,b$.
Cyclic Group: $\exists g \in G$ s.t. $$\displaystyle G = \{g^n \mid n \in \mathbb{Z}\} $$. $g$ is generator.

[!TIP] Subgroup Proof: Show $e \in H$, closure under operation, and closure under inverses. For finite groups, use "nonempty and closed under operation" suffices (by pigeonhole).

Rings and Fields

Ring $(R, +, \cdot)$:

1. $(R, +)$ is abelian group.

2. $\cdot$ is associative.

3. Distributive laws hold.

Commutative Ring: $\cdot$ is commutative.
Ring with Unity: Has multiplicative identity $1 \neq 0$.

Field: Commutative ring with unity where every nonzero element has multiplicative inverse.
Examples: $$\displaystyle \mathbb{Q}, \mathbb{R}, \mathbb{C}, \mathbb{Z}_p $$ (p prime).

Ring Homomorphism: $f: R \to S$ with $$\displaystyle f(a+b)=f(a)+f(b) $$, $$\displaystyle f(ab)=f(a)f(b) $$, $$\displaystyle f(1_R)=1_S $$.

Semigroups

Definition: Set $S$ with associative binary operation. No identity/inverse required.

Example: $(\mathbb{N}, +)$ is semigroup but not group (no additive inverses).

Property: If $$\displaystyle a*c = c*a $$ and $$\displaystyle b*c = c*b $$, then $$\displaystyle (a*b)*c = c*(a*b) $$?
Proof: $$\displaystyle (a*b)*c = a*(b*c) = a*(c*b) = (a*c)*b = (c*a)*b = c*(a*b) $$. Uses associativity and commutativity with $c$.

4. Graph Theory

Basic Concepts

Graph $$\displaystyle G = (V,E) $$: $V$ = vertices, $E$ = edges (unordered pairs for simple graph).

• Simple Graph: No loops, no multiple edges.

• Multigraph: Allows multiple edges.

• Weighted Graph: Edge $e$ has weight $w(e)$ (cost/distance).

Degree: $$\displaystyle \deg(v) = $$ number of incident edges.
Handshaking Lemma: $$\displaystyle \sum_{v \in V} \deg(v) = 2|E| $$.
Corollary: Number of vertices with odd degree is even.

Representations:

1. Adjacency Matrix: $$\displaystyle A_{ij} = 1 $$ if edge $(i,j) \in E$, else 0.

2. Adjacency List: For each vertex, list neighbors.

3. Edge List: List of edges.

Special Graphs

Niche Overlap Graph: Vertices = species, edge if niches overlap (competition).
Example: Birds: Hermit thrush competes with robin & blue jay; robin with mockingbird; mockingbird with blue jay; nuthatch with hairy woodpecker → edges: (H,R), (H,B), (R,M), (M,B), (N,HW).

Eulerian & Hamiltonian

Eulerian Circuit: Closed trail containing every edge exactly once.
Condition: Connected and all vertices even degree.

Eulerian Path: Trail (not necessarily closed) containing every edge exactly once.
Condition: Connected and exactly 0 or 2 vertices of odd degree.

Hamiltonian Cycle: Cycle containing every vertex exactly once.
Hamiltonian Path: Path containing every vertex exactly once.
No simple necessary/sufficient condition (unlike Eulerian). Dirac's theorem: If $\deg(v) \ge n/2$ for all $v$, then Hamiltonian.

Graph Coloring

Proper Coloring: Adjacent vertices get different colors.
Chromatic Number $\chi(G)$: Minimum colors needed.
Greedy Algorithm: Color vertices in order, assign smallest available color.

Example: Complete graph $$\displaystyle K_n $$: $$\displaystyle \chi(K_n)=n $$. Bipartite graph: $\chi \le 2$.

[!TIP] Euler vs Hamiltonian: Eulerian cares about edges (use degrees), Hamiltonian cares about vertices (NP-complete problem).

Shortest Path Problems

Goal: Find path with minimum total weight (sum of edge weights).
Dijkstra's Algorithm: For non-negative weights.

1. Initialize: Set distance to source = 0, others = $\infty$.

2. Greedily pick unvisited vertex with smallest distance.

3. Update neighbors' distances via current vertex.

4. Repeat until all visited.

Applications: Airfare/toll/distance minimization.

5. Recurrence Relations

Linear Homogeneous with Constant Coefficients

Form: $$\displaystyle a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} $$.

Steps:

1. Characteristic Equation: $$\displaystyle r^k - c_1 r^{k-1} - \dots - c_k = 0 $$.

2. Find roots $$\displaystyle r_1, r_2, \dots, r_k $$.

3. General solution:

   • Distinct real roots: $$\displaystyle a_n = A_1 r_1^n + A_2 r_2^n + \dots $$

   • Repeated root $r$ of multiplicity $m$: $$\displaystyle a_n = (A_1 + A_2 n + \dots + A_m n^{m-1}) r^n $$.

4. Use initial conditions to solve for constants $$\displaystyle A_i $$.

Example 1: $$\displaystyle a_n = a_{n-1} + 6a_{n-2} $$, $$\displaystyle a_0=3 $$, $$\displaystyle a_1=6 $$.

• Characteristic: $$\displaystyle r^2 - r - 6 = 0 \Rightarrow (r-3)(r+2)=0 $$, $$\displaystyle r=3,-2 $$.

• General: $$\displaystyle a_n = A \cdot 3^n + B \cdot (-2)^n $$.

• Initial: $$\displaystyle a_0=3 \Rightarrow A+B=3 $$; $$\displaystyle a_1=6 \Rightarrow 3A -2B=6 $$.

• Solve: $$\displaystyle A=2 $$, $$\displaystyle B=1 $$ → $$\displaystyle \boxed{a_n = 2\cdot 3^n + (-2)^n} $$.

Example 2: $$\displaystyle a_n = 2a_{n-1} + 3a_{n-2} $$, $$\displaystyle a_0=2 $$, $$\displaystyle a_1=-2 $$.

• Characteristic: $$\displaystyle r^2 - 2r - 3 = 0 \Rightarrow (r-3)(r+1)=0 $$, $$\displaystyle r=3,-1 $$.

• General: $$\displaystyle a_n = A\cdot 3^n + B\cdot (-1)^n $$.

• Initial: $$\displaystyle A+B=2 $$, $$\displaystyle 3A - B = -2 $$ → $$\displaystyle A=0 $$, $$\displaystyle B=2 $$ → $$\displaystyle \boxed{a_n = 2(-1)^n} $$.

Non-Homogeneous: $$\displaystyle a_n = c_1 a_{n-1} + \dots + f(n) $$.
Method: Solve homogeneous part $$\displaystyle a_n^{(h)} $$, find particular solution $$\displaystyle a_n^{(p)} $$ (guess form based on $f(n)$), then $$\displaystyle a_n = a_n^{(h)} + a_n^{(p)} $$.

[!TIP] Common Error: Forgetting to check for repeated roots. If $r$ is double root, multiply by $n$; triple root, multiply by $$\displaystyle n^2 $$.

6. Linear Algebra

Matrix Fundamentals

Determinant (3×3):

$$\det(A) = \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} = a(ei-fh) - b(di-fg) + c(dh-eg)$$

Properties:

1. $$\displaystyle \det(AB) = \det(A)\det(B) $$

2. $$\displaystyle \det(A^T) = \det(A) $$

3. Row swap multiplies det by $-1$.

4. $$\displaystyle \det(I)=1 $$.

Trace: $$\displaystyle \operatorname{Tr}(A) = \sum_{i} a_{ii} $$ (sum of diagonal).
Properties: $$\displaystyle \operatorname{Tr}(A+B)=\operatorname{Tr}(A)+\operatorname{Tr}(B) $$, $$\displaystyle \operatorname{Tr}(AB)=\operatorname{Tr}(BA) $$.

Example: $$\displaystyle A = \begin{bmatrix} 2 & -1 & 0 \\ 3 & 4 & 2 \\ 1 & 0 & -3 \end{bmatrix} $$

• $$\displaystyle \det(A) = 2(4\cdot(-3)-2\cdot0) - (-1)(3\cdot(-3)-2\cdot1) + 0 = 2(-12) +1(-9-2) = -24 -11 = \boxed{-35} $$.

• $$\displaystyle \operatorname{Tr}(A) = 2+4+(-3) = \boxed{3} $$.

Matrix Decompositions

Singular Value Decomposition (SVD):

Any $m \times n$ matrix $F$ can be decomposed as:

$$F = U \Sigma V^T$$

where:

• $U$: $m \times m$ orthogonal ($$\displaystyle U^TU = I $$).

• $\Sigma$: $m \times n$ diagonal with nonnegative singular values $$\displaystyle \sigma_1 \ge \sigma_2 \ge \dots \ge 0 $$.

• $V$: $n \times n$ orthogonal ($$\displaystyle V^TV = I $$).

Reconstruction: Given $U, \Sigma, V$, compute $$\displaystyle F = U\Sigma V^T $$.

Example (Dec 2024):

$$U = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},\; \Sigma = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix},\; V = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$$

Then $$\displaystyle F = U\Sigma V^T = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} $$.
$$\displaystyle \boxed{F = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}} $$.

Cholesky Decomposition:

For symmetric positive definite matrix $A$, $$\displaystyle A = LL^T $$ where $L$ is lower triangular with positive diagonal.

Steps:

1. $$\displaystyle l_{11} = \sqrt{a_{11}} $$

2. $$\displaystyle l_{i1} = a_{i1}/l_{11} $$ for $$\displaystyle i>1 $$

3. $$\displaystyle l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2} $$

4. $$\displaystyle l_{ij} = \frac{1}{l_{jj}}\left(a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk}\right) $$ for $$\displaystyle i>j $$.

Positive Definite Check: All leading principal minors $$\displaystyle >0 $$ (Sylvester's criterion). Cholesky succeeds iff $A$ is SPD.

Example (Jun 2023): Solve system via Cholesky. First check SPD, then factor $$\displaystyle A=LL^T $$, solve $$\displaystyle Ly=b $$, then $$\displaystyle L^Tx=y $$.

Eigen Decomposition (Conceptual):

For diagonalizable $A$, $$\displaystyle A = PDP^{-1} $$ where $D$ diagonal of eigenvalues, $P$ columns are eigenvectors.

Matrix Functions

Gradient of $$\displaystyle f(X) = \operatorname{Tr}(X^T X) $$:

Let $X$ be $m \times n$. Then $$\displaystyle f(X) = \sum_{i,j} x_{ij}^2 $$.

Gradient $\nabla f(X)$ is matrix of partial derivatives: $$\displaystyle \frac{\partial f}{\partial x_{ij}} = 2x_{ij} $$.

Thus $$\displaystyle \boxed{\nabla \operatorname{Tr}(X^T X) = 2X} $$.

[!TIP] SPD Check: Before Cholesky, verify all eigenvalues positive or all leading minors positive. If any diagonal entry zero/negative during computation, not SPD.

7. Statistics and Probability

Hypothesis Testing

Null Hypothesis $$\displaystyle H_0 $$: Statement of "no effect" or status quo (e.g., $$\displaystyle \mu = \mu_0 $$).
Alternative Hypothesis $$\displaystyle H_a $$: What we aim to support (e.g., $$\displaystyle \mu \ne \mu_0 $$, $$\displaystyle \mu > \mu_0 $$, $$\displaystyle \mu < \mu_0 $$).

Test Statistic: Standardized measure (e.g., $$\displaystyle z = \frac{\bar{x}-\mu_0}{\sigma/\sqrt{n}} $$ if $\sigma$ known; $$\displaystyle t = \frac{\bar{x}-\mu_0}{s/\sqrt{n}} $$ if $\sigma$ unknown).

P-value: Probability, under $$\displaystyle H_0 $$, of observing test statistic as extreme as (or more than) actual.
Significance Level $\alpha$: Threshold (commonly 0.05). Reject $$\displaystyle H_0 $$ if p-value $$\displaystyle < \alpha $$.

One-tailed vs Two-tailed:

• $$\displaystyle H_a: \mu > \mu_0 $$ → right-tailed.

• $$\displaystyle H_a: \mu < \mu_0 $$ → left-tailed.

• $$\displaystyle H_a: \mu \ne \mu_0 $$ → two-tailed (split $\alpha$).

Example (Nov 2023 - Coin Toss):
$$\displaystyle H_0: p=0.5 $$ (unbiased), $$\displaystyle H_a: p \ne 0.5 $$.
$$\displaystyle n=400 $$, heads=216 → $$\displaystyle \hat{p}=0.54 $$.
$$\displaystyle z = \frac{0.54-0.5}{\sqrt{0.5\cdot0.5/400}} = \frac{0.04}{0.025} = 1.6 $$.

Two-tailed p-value $$\displaystyle = 2P(Z > 1.6) \approx 2(0.0548)=0.1096 > 0.05 $$ → fail to reject $$\displaystyle H_0 $$. No evidence coin biased.

Example (Jun 2024 - Salary):
$$\displaystyle \sigma=1523 $$ known, $$\displaystyle n=50 $$, $$\displaystyle \bar{x}=48326 $$, $$\displaystyle H_0: \mu=45000 $$, $$\displaystyle \alpha=0.05 $$.
$$\displaystyle z = \frac{48326-45000}{1523/\sqrt{50}} = \frac{3326}{215.3} \approx 15.45 $$.

p-value $$\displaystyle \approx 0 < 0.05 $$ → reject $$\displaystyle H_0 $$. Mean salary significantly higher.

Errors in Hypothesis Testing

[!TIP] Trade-off: Decreasing $\alpha$ increases $\beta$. Increase sample size to reduce both.

Analysis of Variance (ANOVA)

Purpose: Compare means across $k$ groups.
Assumptions:

1. Populations normally distributed.

2. Equal variances ($$\displaystyle \sigma_1^2 = \dots = \sigma_k^2 $$).

3. Independent samples.

One-way ANOVA:

• Between-group variability (SSB): Variation due to group differences.

• Within-group variability (SSW): Variation within groups.

• Total SS: SST = SSB + SSW.

Test Statistic:

$$F = \frac{\text{MSB}}{\text{MSW}} = \frac{SSB/(k-1)}{SSW/(N-k)}$$

where $N$ = total sample size, $k$ = groups.

Under $$\displaystyle H_0 $$ (all means equal), $$\displaystyle F \sim F_{k-1, N-k} $$.

Decision: Reject $$\displaystyle H_0 $$ if $$\displaystyle F > F_{\alpha, k-1, N-k} $$.

Example (Jun 2022): Three samples of size 5. Compute group means, overall mean, SSB, SSW, then $F$.

Time Series Analysis (Brief)

Components:

1. Trend ($T$): Long-term movement.

2. Seasonal ($S$): Regular periodic fluctuations.

3. Cyclical ($C$): Long-term cycles (not fixed period).

4. Irregular ($I$): Random noise.

Models:

• Additive: $$\displaystyle Y = T + S + C + I $$

• Multiplicative: $$\displaystyle Y = T \times S \times C \times I $$

Applications: Forecasting, identifying patterns.

QUICK REFERENCE: Past Paper Hotspots

[!CAUTION] Final Exam Strategy:

1. For proofs (set theory, relations, groups), write definitions first, then logical steps.

2. For calculations (recurrence, SVD, Cholesky), show all steps clearly—partial credit awarded.

3. For graph problems, draw diagrams neatly (Hasse, Eulerian, coloring).

4. In statistics, state $$\displaystyle H_0 $$, $$\displaystyle H_a $$, test statistic, decision, conclusion.

5. Always box final answers.