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

UNIT 4: Comprehensive Short Notes

(Based on AL-401 - Introduction to Discrete Structure & Linear Algebra, Exam Analysis Dec 2024–Jun 2025)

I. Set Theory and Relations

Set 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\} $$

[!TIP]

Venn Diagrams visually represent these operations. Always draw the universal set $U$ as a rectangle and subsets as circles within it.

Key Set Identities (Laws)

Relations on Sets

Let $R \subseteq A \times B$ be a relation from set $A$ to set $B$.

• Domain: $$\displaystyle \text{Dom}(R) = \{a \in A \mid \exists b \in B, (a,b) \in R\} $$

• Range: $$\displaystyle \text{Ran}(R) = \{b \in B \mid \exists a \in A, (a,b) \in R\} $$

Properties of Relations on a Set $A$ ($R \subseteq A \times A$)

[!TIP]

Equivalence Relation: Reflexive + Symmetric + Transitive.

Partial Order: Reflexive + Antisymmetric + Transitive.

Representations

1. Matrix Representation: For $$\displaystyle A = \{a_1, \dots, a_n\} $$, $$\displaystyle M_R = [m_{ij}] $$ where $$\displaystyle m_{ij} = 1 $$ if $$\displaystyle (a_i, a_j) \in R $$, else $0$.

2. Digraph: Directed graph with vertices $A$ and edge $$\displaystyle a_i \to a_j $$ iff $$\displaystyle (a_i, a_j) \in R $$.

Transitive Closure

• Definition: The smallest transitive relation $$\displaystyle R^* $$ containing $R$.

• Computation:

  1. Matrix Method: $$\displaystyle M_{R^*} = M_R \lor M_R^2 \lor M_R^3 \lor \dots \lor M_R^n $$ (for $n$ elements).

  2. Warshall’s Algorithm (for adjacency matrix $A$):

     
     for k = 1 to n:
     
         for i = 1 to n:
     
             for j = 1 to n:
     
                 A[i][j] = A[i][j] OR (A[i][k] AND A[k][j])
     
     

• Common Examples:

  • $R$ on $\mathbb{Z}$: $$\displaystyle aRb \iff a+1=b $$ → Transitive closure is $a \le b$.

  • $R$ on $\mathbb{Z}$: $$\displaystyle aRb \iff a-b=2 $$ → Transitive closure is empty (no chain possible).

Partial Orders and Posets

• Poset (Partially Ordered Set): Set $A$ with partial order $\le$.

• Hasse Diagram: Simplified digraph (omit reflexive loops, transitive edges, draw edges upward).

• Key Elements:

  • Maximal: No element $b$ with $$\displaystyle a < b $$.

  • Minimal: No element $b$ with $$\displaystyle b < a $$.

  • Greatest: $a \ge \forall x \in A$ (unique if exists).

  • Least: $a \le \forall x \in A$ (unique if exists).

• Chain: Totally ordered subset.

• Antichain: Subset where no two elements are comparable.

Lattices

• Definition: Poset where every pair $\{a,b\}$ has:

  • Least Upper Bound (lub): $a \vee b$ (join).

  • Greatest Lower Bound (glb): $a \wedge b$ (meet).

• Bounded Lattice: Has least element $0$ and greatest element $1$.

• Distributive Lattice: Satisfies:

$$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$$

$$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$$

• Examples:

  • $(\mathcal{P}(S), \subseteq)$: $$\displaystyle A \vee B = A \cup B $$, $$\displaystyle A \wedge B = A \cap B $$.

  • $(\mathbb{N}, \mid)$: $$\displaystyle a \vee b = \text{lcm}(a,b) $$, $$\displaystyle a \wedge b = \text{gcd}(a,b) $$.

II. Propositional Logic

Compound Propositions and Connectives

Tautologies and Contradictions

• Tautology: Always true (e.g., $p \lor \neg p$, $p \Rightarrow q \Leftrightarrow \neg p \lor q$).

• Contradiction: Always false (e.g., $p \land \neg p$).

• Verification: Use truth tables or logical equivalences.

[!TIP]

Common Pitfall: $p \Rightarrow q$ is not equivalent to $q \Rightarrow p$. Its contrapositive $\neg q \Rightarrow \neg p$ is equivalent.

Normal Forms

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

   • Example: $(p \land q) \lor (\neg p \land q \land r)$.

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

   • Example: $(p \lor q) \land (\neg p \lor r)$.

Conversion Steps (to CNF)

1. Eliminate $\Rightarrow$, $\Leftrightarrow$.

2. Move $\neg$ inward (De Morgan’s).

3. Distribute $\lor$ over $\land$.

Example: $p \land (p \Rightarrow q)$
$\Rightarrow p \land (\neg p \lor q)$
$\Rightarrow (p \land \neg p) \lor (p \land q)$
$\Rightarrow \text{False} \lor (p \land q)$
$\Rightarrow p \land q$ (already in CNF).

Laws of Logic (Algebra of Propositions)

III. Recurrence Relations

Linear Homogeneous Recurrences

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

Solution Steps

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

2. Roots:

   • Distinct real roots $$\displaystyle r_1, \dots, r_k $$: $$\displaystyle a_n = \alpha_1 r_1^n + \dots + \alpha_k r_k^n $$.

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

   • Complex roots $a \pm bi$: Contribute $$\displaystyle \lambda^n (C_1 \cos n\theta + C_2 \sin n\theta) $$, where $$\displaystyle r = \lambda e^{i\theta} $$.

3. Apply Initial Conditions to solve for $$\displaystyle \alpha_i $$.

Example: Fibonacci-like

$$\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 = \alpha 3^n + \beta (-2)^n $$.

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

• Solve: $$\displaystyle \alpha=2.4 $$, $$\displaystyle \beta=0.6 $$ → $$\displaystyle a_n = 2.4 \cdot 3^n + 0.6 \cdot (-2)^n $$.

Non-Homogeneous Recurrences

Form: $$\displaystyle a_n = c_1 a_{n-1} + \dots + f(n) $$.

• General Solution: $$\displaystyle a_n = a_n^{(h)} + a_n^{(p)} $$, where $$\displaystyle a_n^{(h)} $$ solves homogeneous part, $$\displaystyle a_n^{(p)} $$ is particular solution.

• Guess $$\displaystyle a_n^{(p)} $$ based on $f(n)$ (e.g., polynomial → polynomial of same degree; exponential → $$\displaystyle C \cdot A^n $$ unless $A$ is root of characteristic).

IV. Algebraic Structures

Semigroups and Monoids

[!TIP]

Associativity Test: $$\displaystyle (a*b)*c = a*(b*c) $$ for all $a,b,c$. Not commutative unless specified.

Groups

Definition: Set $G$ with binary operation $*$ s.t.:

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

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

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

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

Subgroups

• Subgroup Test (non-empty $H \subseteq G$): $\forall a,b \in H$, $$\displaystyle a*b^{-1} \in H $$.

• Normal Subgroup: $H \triangleleft G$ iff $$\displaystyle \forall x \in G, xHx^{-1} = H $$ (or $$\displaystyle xH = Hx $$).

Special Groups

• Abelian (Commutative): $$\displaystyle a*b = b*a $$ for all $a,b$.

• Cyclic: $\exists g \in G$ s.t. $$\displaystyle G = \langle g \rangle = \{g^n \mid n \in \mathbb{Z}\} $$.

  • Order of $g$: smallest $$\displaystyle n>0 $$ with $$\displaystyle g^n = e $$.

  • $$\displaystyle \mathbb{Z}_n $$ under addition mod $n$ is cyclic (generator 1).

  • $$\displaystyle \mathbb{Z}_n^* $$ (units mod $n$) is cyclic for prime $n$.

[!TIP]

Example: $$\displaystyle G = \{0,1,2,3,4,5\} $$ under addition mod 6 is a group (identity 0, inverse $-a \equiv 6-a$). Not cyclic? Actually, $$\displaystyle \langle 1 \rangle = \mathbb{Z}_6 $$, so cyclic.

Rings and Fields

Ring Homomorphism

$\phi: R \to S$ s.t.:

1. $$\displaystyle \phi(a+b) = \phi(a) + \phi(b) $$,

2. $$\displaystyle \phi(a \cdot b) = \phi(a) \cdot \phi(b) $$,

3. $$\displaystyle \phi(1_R) = 1_S $$ (if unital).

Ideal

$I \subseteq R$ s.t.:

1. $(I, +)$ subgroup of $(R, +)$,

2. $\forall r \in R, a \in I$: $r \cdot a \in I$ and $a \cdot r \in I$.

V. Graph Theory

Fundamentals

• Graph: $$\displaystyle G = (V,E) $$, $V$ vertices, $E$ edges.

• Simple Graph: No loops or multiple edges.

• Degree: $$\displaystyle \deg(v) = $$ edges incident to $v$ (loops count twice).

• Handshaking Lemma: $$\displaystyle \sum_{v \in V} \deg(v) = 2|E| $$.

Representations

1. Adjacency Matrix $A$: $$\displaystyle A_{ij} = 1 $$ if edge $$\displaystyle v_i \to v_j $$, else 0.

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

3. Incidence Matrix $M$: Rows = vertices, columns = edges; $$\displaystyle M_{ve} = 1 $$ if $v$ incident to $e$, else 0.

Special Graph Classes

Eulerian Graphs

• Eulerian Circuit: Closed trail containing every edge exactly once.

• Euler’s Theorem: Connected graph has Eulerian circuit iff all vertices have even degree.

• Eulerian Path (not circuit): Exactly 0 or 2 vertices of odd degree.

Hamiltonian Graphs

• Hamiltonian Cycle: Cycle visiting every vertex exactly once.

• Necessary Conditions: Dirac’s ($\deg(v) \ge n/2$ for all $v$), Ore’s ($\deg(u)+\deg(v) \ge n$ for non-adjacent $u,v$). Not sufficient.

• Sufficient for Special Graphs: Complete graphs, bipartite $$\displaystyle K_{n,n} $$ with $n \ge 2$.

[!TIP]

Eulerian vs Hamiltonian: Eulerian cares about edges, Hamiltonian about vertices. A graph can be one, both, or neither.

Graph Coloring

• Proper Coloring: Adjacent vertices get different colors.

• Chromatic Number $\chi(G)$: Minimum colors needed.

• Greedy Algorithm: Order vertices; assign smallest available color.

• Upper Bound: $\chi(G) \le \Delta(G)+1$ ($\Delta$ = max degree).

• Applications: Scheduling, map coloring (Four Color Theorem for planar graphs).

Shortest Path & Weighted Graphs

• Dijkstra’s Algorithm (non-negative weights):

  1. Initialize: set distance to source = 0, others = $\infty$; all unvisited.

  2. Pick unvisited vertex $u$ with smallest distance.

  3. Update neighbors: $$\displaystyle d(v) = \min(d(v), d(u)+w(u,v)) $$.

  4. Mark $u$ visited; repeat until all visited.

• Traveling Salesman Problem (TSP): Find Hamiltonian cycle of minimum total weight. NP-hard.

Planar Graphs

• Planar: Can be drawn in plane without edge crossings.

• Euler’s Formula (connected planar): $$\displaystyle v - e + r = 2 $$, where $r$ = regions (including outer).

• Consequences:

  • For simple planar: $e \le 3v - 6$.

  • For bipartite planar: $e \le 2v - 4$.

• Kuratowski’s Theorem: Graph is non-planar iff contains subdivision of $$\displaystyle K_{3,3} $$ or $$\displaystyle K_5 $$.

VI. Linear Algebra

Determinants and Trace

Determinant (for $n \times n$)

• Properties:

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

  2. Swapping two rows multiplies det by $-1$.

  3. Multiplying row by $k$ multiplies det by $k$.

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

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

  6. If rows (cols) linearly dependent, $$\displaystyle \det(A)=0 $$.

• Laplace Expansion: $$\displaystyle \det(A) = \sum_{j=1}^n a_{ij} C_{ij} $$ (cofactor expansion along row $i$).

• $2 \times 2$: $$\displaystyle \det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc $$.

• $3 \times 3$ (Sarrus’ rule):

  $$\displaystyle \det\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} = aei + bfg + cdh - ceg - bdi - afh $$.

Trace

$$\displaystyle \text{Tr}(A) = \sum_{i=1}^n a_{ii} $$.

• Properties:

  • $$\displaystyle \text{Tr}(A+B) = \text{Tr}(A) + \text{Tr}(B) $$.

  • $$\displaystyle \text{Tr}(kA) = k \text{Tr}(A) $$.

  • $$\displaystyle \text{Tr}(AB) = \text{Tr}(BA) $$ (even if $AB \neq BA$).

  • $$\displaystyle \text{Tr}(A^T) = \text{Tr}(A) $$.

Eigenvalues and Eigenvectors

• Eigenvalue $\lambda$: $$\displaystyle \det(A - \lambda I) = 0 $$.

• Characteristic Polynomial: $$\displaystyle p(\lambda) = \det(A - \lambda I) $$.

• Algebraic Multiplicity: Multiplicity of $\lambda$ as root of $p(\lambda)$.

• Geometric Multiplicity: $\dim \text{null}(A - \lambda I)$.

• Diagonalizable: $$\displaystyle A = PDP^{-1} $$ where $D$ diagonal, $P$ invertible (columns = eigenvectors). Necessary & sufficient: Sum of geometric multiplicities = $n$.

Example

$$\displaystyle A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} $$:

• Char poly: $$\displaystyle (2-\lambda)^2 - 1 = \lambda^2 - 4\lambda + 3 = 0 $$ → $$\displaystyle \lambda=1,3 $$.

• $$\displaystyle \lambda=1 $$: $$\displaystyle (A-I)v=0 \Rightarrow v = \begin{pmatrix} 1 \\ -1 \end{pmatrix} $$.

• $$\displaystyle \lambda=3 $$: $$\displaystyle (A-3I)v=0 \Rightarrow v = \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$.

• $$\displaystyle P = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} $$, $$\displaystyle D = \begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix} $$, $$\displaystyle A = PDP^{-1} $$.

Singular Value Decomposition (SVD)

Theorem: Any $m \times n$ matrix $A$ has decomposition:

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

where:

• $U$: $m \times m$ orthogonal ($$\displaystyle U^T U = I $$), columns = left singular vectors.

• $\Sigma$: $m \times n$ diagonal with nonnegative singular values $$\displaystyle \sigma_1 \ge \dots \ge \sigma_r > 0 $$ ($$\displaystyle r = \text{rank}(A) $$).

• $V$: $n \times n$ orthogonal, columns = right singular vectors.

Computation Steps

1. Compute $$\displaystyle A^T A $$ (symmetric, positive semidefinite).

2. Eigenvalues of $$\displaystyle A^T A $$: $$\displaystyle \lambda_i = \sigma_i^2 $$.

3. Eigenvectors of $$\displaystyle A^T A $$ → columns of $V$.

4. Compute $$\displaystyle u_i = \frac{1}{\sigma_i} A v_i $$ for $$\displaystyle \sigma_i > 0 $$; complete $U$ to orthonormal basis.

[!TIP]

Geometric Interpretation: SVD expresses $A$ as rotation/reflection ($$\displaystyle V^T $$), scaling along axes ($\Sigma$), then another rotation/reflection ($U$).

Cholesky Decomposition

Theorem: If $A$ is symmetric positive definite (SPD), then $$\displaystyle A = LL^T $$ where $L$ is lower triangular with positive diagonal.

Algorithm (for $n \times n$ SPD $A$)

For $$\displaystyle i=1 $$ to $n$:

1. $$\displaystyle L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2} $$.

2. For $$\displaystyle j=i+1 $$ to $n$:

   $$\displaystyle L_{ji} = \frac{1}{L_{ii}} \left( A_{ji} - \sum_{k=1}^{i-1} L_{jk} L_{ik} \right) $$.

Verification of SPD

1. All leading principal minors $$\displaystyle > 0 $$ (Sylvester’s criterion).

2. Or attempt Cholesky: if any $$\displaystyle L_{ii}^2 < 0 $$ during computation, not SPD.

Matrix Calculus (Gradient)

For scalar function $f(X)$ of matrix $$\displaystyle X \in \mathbb{R}^{m \times n} $$:

• Gradient $$\displaystyle \nabla_X f $$ is matrix of partial derivatives: $$\displaystyle (\nabla_X f)_{ij} = \frac{\partial f}{\partial X_{ij}} $$.

Common Results

• $$\displaystyle f(X) = \text{Tr}(X^T X) = \sum_{i,j} X_{ij}^2 $$ → $$\displaystyle \nabla_X f = 2X $$.

• $$\displaystyle f(X) = \text{Tr}(AX) = \sum_{i,j} A_{ji} X_{ij} $$ → $$\displaystyle \nabla_X f = A^T $$.

VII. Statistics and Probability

Hypothesis Testing Framework

1. Null Hypothesis $$\displaystyle H_0 $$: Status quo / no effect.

2. Alternative Hypothesis $$\displaystyle H_a $$: What we aim to support.

3. Test Statistic: Function of sample (e.g., $$\displaystyle z = \frac{\bar{x} - \mu_0}{\sigma/\sqrt{n}} $$).

4. P-value: Probability under $$\displaystyle H_0 $$ of observing statistic as extreme as sample.

5. Significance Level $\alpha$: Threshold for rejecting $$\displaystyle H_0 $$ (commonly 0.05).

6. Decision: Reject $$\displaystyle H_0 $$ if p-value $$\displaystyle < \alpha $$.

Errors in Hypothesis Testing

[!TIP]

Trade-off: Decreasing $\alpha$ increases $\beta$ (for fixed sample size). Increase sample size to reduce both.

Common Tests

One-Sample $z$-test (population $\sigma$ known)

$$z = \frac{\bar{x} - \mu_0}{\sigma/\sqrt{n}} \sim N(0,1) \text{ under } H_0$$

Reject $$\displaystyle H_0 $$ if $$\displaystyle |z| > z_{\alpha/2} $$ (two-tailed) or $$\displaystyle z > z_\alpha $$ (right-tailed).

One-Sample $t$-test (population $\sigma$ unknown)

$$t = \frac{\bar{x} - \mu_0}{s/\sqrt{n}} \sim t_{n-1} \text{ under } H_0$$

Use $t$-distribution with $n-1$ df.

Test for Proportions (large $n$)

$$z = \frac{\hat{p} - p_0}{\sqrt{p_0(1-p_0)/n}} \sim N(0,1) \text{ under } H_0$$

where $$\displaystyle \hat{p} = x/n $$.

Analysis of Variance (ANOVA)

Purpose: Compare means across $k$ groups.

• Assumptions:

  1. Independent random samples.

  2. Normality in each group.

  3. Equal variances (homoscedasticity).

• Sums of Squares:

  • Total: $$\displaystyle SS_T = \sum_{i=1}^k \sum_{j=1}^{n_i} (x_{ij} - \bar{x}_{\cdot\cdot})^2 $$.

  • Between-group: $$\displaystyle SS_B = \sum_{i=1}^k n_i (\bar{x}_{i\cdot} - \bar{x}_{\cdot\cdot})^2 $$.

  • Within-group: $$\displaystyle SS_W = \sum_{i=1}^k \sum_{j=1}^{n_i} (x_{ij} - \bar{x}_{i\cdot})^2 $$.

  (Note: $$\displaystyle SS_T = SS_B + SS_W $$.)

• Degrees of Freedom:

  • $$\displaystyle df_B = k-1 $$, $$\displaystyle df_W = N-k $$ ($$\displaystyle N = \sum n_i $$).

• Mean Squares:

  • $$\displaystyle MS_B = SS_B / df_B $$, $$\displaystyle MS_W = SS_W / df_W $$.

• $F$-statistic:

$$F = \frac{MS_B}{MS_W} \sim F_{df_B, df_W} \text{ under } H_0 \text{ (all means equal)}.$$

• Decision: Reject $$\displaystyle H_0 $$ if $$\displaystyle F > F_{\alpha}(df_B, df_W) $$.

Time Series Analysis (Basic)

Components:

1. Trend ($$\displaystyle T_t $$): Long-term movement.

2. Seasonality ($$\displaystyle S_t $$): Regular periodic fluctuations (e.g., monthly, quarterly).

3. Cyclical ($$\displaystyle C_t $$): Long-term cycles (not fixed period).

4. Irregular ($$\displaystyle I_t $$): Random noise.

Models:

• Additive: $$\displaystyle Y_t = T_t + S_t + C_t + I_t $$.

• Multiplicative: $$\displaystyle Y_t = T_t \times S_t \times C_t \times I_t $$.

Simple Forecasting:

• Moving Averages: Smooth by averaging recent $k$ observations.

• Exponential Smoothing: $$\displaystyle \hat{y}_{t+1} = \alpha y_t + (1-\alpha) \hat{y}_t $$, $$\displaystyle 0 < \alpha < 1 $$.

\boxed{\text{END OF UNIT 4 NOTES}}