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

UNIT 2: DISCRETE STRUCTURES AND LINEAR ALGEBRA

1. Set Theory and Logic

Set Operations

• Union: \(A \cup B = \{x \mid x \in A \text{ or } x \in B\}\)

• Intersection: \(A \cap B = \{x \mid x \in A \text{ and } x \in B\}\)

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

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

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

Set Identities

• De Morgan’s Laws:

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

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

• 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)$$

[!TIP] Exam Tip: Venn diagrams are required for proving set identities in exams (e.g., Jun 2024). Draw three overlapping circles, shade LHS and RHS separately, show they match.

Propositional Logic

• Connectives (with truth tables):

• Tautology: Always true (e.g., \(p \lor \neg p\)).

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

• Logical Equivalence: \(p \equiv q\) iff \(p \leftrightarrow q\) is a tautology.

Normal Forms

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

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

Example (Nov 2023): CNF of \(p \land (p \rightarrow q)\)

\(p \rightarrow q \equiv \neg p \lor q\)

\(p \land (\neg p \lor q) \equiv (p \land \neg p) \lor (p \land q) \equiv \text{False} \lor (p \land q) \equiv p \land q\)

CNF: \((p) \land (q)\)

2. Relations and Partially Ordered Sets (Posets)

Properties of Relations (on set \(A\)):

• Reflexive: \(\forall a \in A, (a,a) \in R\)

• Symmetric: \((a,b) \in R \Rightarrow (b,a) \in R\)

• Transitive: \((a,b) \in R \land (b,c) \in R \Rightarrow (a,c) \in R\)

• Irreflexive: \(\forall a \in A, (a,a) \notin R\)

• Antisymmetric: \((a,b) \in R \land (b,a) \in R \Rightarrow a=b\)

Equivalence Relations: Reflexive, symmetric, transitive. Partitions set into equivalence classes.

Partial Orders: Reflexive, antisymmetric, transitive.
Hasse Diagram: Draw vertices, omit reflexive loops and transitive edges, orient upward.

[!TIP] Exam Tip: For divisibility poset (e.g., \(D_{24}\)), list divisors, draw edges \(a \to b\) if \(a \mid b\) and no \(c\) with \(a \mid c \mid b\) (Jun 2023, Nov 2023).

Transitive Closure \(R^+\): Smallest transitive relation containing \(R\).
Example (Jun 2024): \(aRb\) iff \(|a^2-b^2|\) multiple of 5.

Check: Reflexive? Yes (\(|a^2-a^2|=0\)). Symmetric? Yes (\(|a^2-b^2|=|b^2-a^2|\)). Transitive? No (counterexample: \(a=1,b=4\) → \(|1-16|=15\); \(b=4,c=6\) → \(|16-36|=20\); but \(a=1,c=6\) → \(|1-36|=35\) ✓; try \(a=2,b=3\) → \(|4-9|=5\); \(b=3,c=7\) → \(|9-49|=40\); \(a=2,c=7\) → \(|4-49|=45\) ✓; actually transitive? Let’s test \(a=1,b=2\) → \(|1-4|=3\) not multiple → not related. Need systematic: \(aRb \Leftrightarrow a \equiv \pm b \pmod{5}\). Then \(a \equiv \pm b\), \(b \equiv \pm c\) ⇒ \(a \equiv \pm c\) ⇒ transitive. So \(R\) is equivalence? Actually symmetric and transitive? Yes, so \(R^+ = R\). But paper says "not transitive"? Re-check: \(a=1,b=4\) (1≡4 mod5? 1-4=-3 not mult5 → false). Actually \(a^2 \equiv b^2 \pmod{5} \Leftrightarrow a \equiv \pm b \pmod{5}\). So \(R\) is equivalence. Paper might have error? But follow method: find closure by adding pairs until transitive.

Common Transitive Closures (Jun 2023):

• \(a S b\) iff \(a+1=b\) → \(S^+\) is \(a \leq b\).

• \(a R b\) iff \(a-b=2\) → \(R^+\) is \(a-b\) even and \(a \geq b\)? Actually \(a-b=2k, k>0\)? No, \(R = \{(a,a+2)\}\), then \(R^2 = \{(a,a+4)\}\), so \(R^+ = \{(a,a+2k) \mid k \in \mathbb{Z}^+\}\).

Matrix Representation: For \(A=\{1,\dots,n\}\), \(M_R[i,j]=1\) if \((i,j)\in R\), else 0.
Digraph: Vertices = elements, edge \(a \to b\) if \((a,b)\in R\).

Niche Overlap Graph (Dec 2024): Vertices = species, edge if niches overlap (competition).

Example: Hermit thrush competes with robin & blue jay → edges (HT,R), (HT,BJ); Robin competes with mockingbird → (R,M); Mockingbird with blue jay → (M,BJ); Nuthatch with hairy woodpecker → (N,HW).

3. Algebraic Structures

Group \((G,*)\):

1. Closure: \(a*b \in G\)

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

3. Identity: \(\exists e \in G\) s.t. \(e*a=a*e=a\)

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

Abelian Group: Commutative (\(a*b=b*a\)).

Cyclic Group: \(\exists g \in G\) s.t. \(G=\{g^n \mid n \in \mathbb{Z}\}\). \(g\) is generator.

Subgroup Test: \(H \subseteq G\) is subgroup iff:

• \(H \neq \emptyset\)

• \(\forall a,b \in H, ab^{-1} \in H\)

Normal Subgroup \(N \triangleleft G\): \(gNg^{-1}=N\) for all \(g \in G\).

Equivalent: \(gN = Ng\) (left/right cosets equal).

[!TIP] Exam Tip: Prove \(G=\{0,1,2,3,4,5\}\) under mod 6 addition is group? Check: closure (yes), associative (yes), identity 0, inverse: \(a^{-1}=6-a\) (for \(a\neq0\)), so yes. But is it cyclic? Yes, generator 1 or 5. Abelian? Yes.

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

1. \((R,+)\) abelian group

2. \((R,\cdot)\) semigroup

3. Distributive: \(a(b+c)=ab+ac\), \((a+b)c=ac+bc\)

Commutative Ring: Multiplication commutative.
Ring Homomorphism \(\phi: R \to S\): \(\phi(a+b)=\phi(a)+\phi(b)\), \(\phi(ab)=\phi(a)\phi(b)\).

Field: Commutative ring with \(1 \neq 0\) and every nonzero element invertible under \(\cdot\).

Examples: \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\).

Semigroup: Associative binary operation.
Monoid: Semigroup with identity.

4. Recurrence Relations

Linear Homogeneous with Constant Coefficients:

\(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}\)

Characteristic Equation:

\(r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0\)

Cases:

1. Distinct roots \(r_1, \dots, r_k\):

   \(a_n = A_1 r_1^n + \dots + A_k r_k^n\)

2. Repeated roots (multiplicity \(m\)):

   \(a_n = (A_1 + A_2 n + \dots + A_m n^{m-1}) r^n\)

3. Complex roots \(\alpha \pm i\beta\):

   \(a_n = \rho^n (B_1 \cos n\theta + B_2 \sin n\theta)\), where \(\rho=\sqrt{\alpha^2+\beta^2}\), \(\theta=\tan^{-1}(\beta/\alpha)\).

Solve with Initial Conditions to find constants.

Example (Dec 2024): \(a_n = a_{n-1} + 6a_{n-2}\), \(a_0=3, a_1=6\)

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

\(a_n = A \cdot 3^n + B \cdot (-2)^n\).

\(a_0=3: A+B=3\)

\(a_1=6: 3A -2B=6\)

Solve: \(A=2, B=1\).

\(\boxed{a_n = 2\cdot 3^n + (-2)^n}\)

5. Graph Theory

Basic Terminology:

• Vertices \(V\), Edges \(E\)

• Simple graph: no loops, no multiple edges

• Degree \(deg(v)\): number of incident edges

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

Representations:

• Adjacency Matrix \(A\): \(A[i,j]=1\) if edge \((i,j)\), else 0.

• Adjacency List: For each vertex, list neighbors.

• Edge List: List of edges \((u,v)\).

Eulerian Graph: Contains Eulerian circuit (closed trail using every edge exactly once) iff connected and all vertices even degree.
Hamiltonian Graph: Contains Hamiltonian cycle (cycle visiting every vertex exactly once). No simple necessary/sufficient condition.

Graph Coloring:

• Proper coloring: adjacent vertices different colors.

• Chromatic number \(\chi(G)\): minimum colors needed.

• Coloring Problem: Determine \(\chi(G)\) (NP-complete).

Weighted Graphs & Shortest Path:

• Edge weights (costs, distances).

• Dijkstra’s algorithm: for non-negative weights, finds shortest path from source.

Planar Graphs:

• Can be drawn without edge crossings.

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

Graph Isomorphism: Bijection \(f: V(G) \to V(H)\) preserving adjacency.

[!TIP] Exam Tip: For planar graph with components: \(v - e + r = c + 1\) (where \(c\) = components). Example (Jun 2023): \(v=10, e=9, c=3\) → \(10-9+r=3+1 \Rightarrow r=3\).

Niche Overlap Graph (see Relations section).

6. Linear Algebra

Determinant (for \(n \times n\) matrix \(A\)):

• \(\det(A)\): sum over permutations, \(\det(A)=\sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}\)

• Properties:

  • \(\det(AB)=\det(A)\det(B)\)

  • \(\det(A^T)=\det(A)\)

  • Row swap: sign change

  • Row multiply by \(k\): \(\det\) multiplies by \(k\)

  • Row addition: \(\det\) unchanged

Laplace Expansion: Along row \(i\): \(\det(A)=\sum_{j=1}^n a_{ij} C_{ij}\), where \(C_{ij}=(-1)^{i+j} M_{ij}\) (minor).

Trace: \(\operatorname{Tr}(A) = \sum_{i=1}^n a_{ii}\). \(\operatorname{Tr}(AB)=\operatorname{Tr}(BA)\).

Eigen Decomposition:

• Eigenvalue \(\lambda\), eigenvector \(v\): \(Av = \lambda v\).

• Diagonalizable if \(A = PDP^{-1}\), where \(D\) diagonal of eigenvalues, \(P\) columns are eigenvectors.

Singular Value Decomposition (SVD) (Very Frequent):

For \(m \times n\) matrix \(F\):

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

• \(U\): \(m \times m\) orthogonal (eigenvectors of \(FF^T\))

• \(\Sigma\): \(m \times n\) diagonal with singular values \(\sigma_i = \sqrt{\lambda_i(FF^T)}\) (non-negative, descending)

• \(V\): \(n \times n\) orthogonal (eigenvectors of \(F^TF\))

Steps:

1. Compute \(F^TF\) (\(n \times n\)), find eigenvalues \(\lambda_i\) and eigenvectors → columns of \(V\).

2. Singular values \(\sigma_i = \sqrt{\lambda_i}\).

3. Compute \(FF^T\) or use \(u_i = \frac{1}{\sigma_i} F v_i\) for columns of \(U\).

Example (Dec 2024): Given \(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}\)

\(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}\)

Cholesky Decomposition (Very Frequent):

For symmetric positive definite matrix \(A\):

$$A = LL^T$$

where \(L\) is lower triangular with positive diagonal.

Algorithm (for \(A = [a_{ij}]\), \(L=[l_{ij}]\)):

• \(l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2}\)

• \(l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk} \right)\), \(i > j\)

Check Positive Definite: All leading principal minors \(>0\) (or all eigenvalues \(>0\)). If Cholesky fails (negative under sqrt), not PD.

Example (Jun 2023): Solve system using Cholesky:

\(\begin{aligned} x + 2y + 3z &= 5 \\ 2x + 8y + 22z &= 6 \\ 3x + 22y + 82z &= -10 \end{aligned}\)

Matrix \(A = \begin{bmatrix}1&2&3\\2&8&22\\3&22&82\end{bmatrix}\), \(b=\begin{bmatrix}5\\6\\-10\end{bmatrix}\).

Compute \(L\):

\(l_{11}=\sqrt{1}=1\)

\(l_{21}=2/1=2\), \(l_{31}=3/1=3\)

\(l_{22}=\sqrt{8-2^2}=\sqrt{4}=2\)

\(l_{32}=(22 - 3\cdot2)/2 = (22-6)/2=8\)

\(l_{33}=\sqrt{82 - 3^2 - 8^2} = \sqrt{82-9-64}=\sqrt{9}=3\)

\(L = \begin{bmatrix}1&0&0\\2&2&0\\3&8&3\end{bmatrix}\)

Solve \(Ly=b\) (forward):

\(y_1=5\); \(2y_1+2y_2=6 \Rightarrow y_2=-2\); \(3y_1+8y_2+3y_3=-10 \Rightarrow 3-16+3y_3=-10 \Rightarrow 3y_3=3 \Rightarrow y_3=1\)

Solve \(L^Tx=y\) (backward):

\(3z=1 \Rightarrow z=1/3\); \(2y+8z=-2 \Rightarrow 2y+8/3=-2 \Rightarrow 2y=-2-8/3=-14/3 \Rightarrow y=-7/3\); \(x+2y+3z=5 \Rightarrow x+2(-7/3)+3(1/3)=5 \Rightarrow x-14/3+1=5 \Rightarrow x=5+14/3-1=4+14/3=26/3\).

Gradient of Matrix Functions:

• \(f(X)=\operatorname{Tr}(X^TX)\):

  \(\nabla_X \operatorname{Tr}(X^TX) = 2X\)

  (since \(\operatorname{Tr}(X^TX)=\sum_{i,j} x_{ij}^2\), derivative w.r.t. \(x_{ij}\) is \(2x_{ij}\))

Positive Definite Matrices:

• All eigenvalues \(>0\).

• All leading principal minors \(>0\).

• \(x^TAx > 0\) for all nonzero \(x\).

7. Statistics and Probability

Hypothesis Testing:

• Null Hypothesis \(H_0\): Status quo, to be rejected.

• Alternative Hypothesis \(H_a\): What we aim to support.

• Test Statistic: Computed from sample.

• P-value: Probability, under \(H_0\), of observing test statistic as extreme as (or more than) observed.

• Significance Level \(\alpha\): Threshold for rejecting \(H_0\) (e.g., 0.05).

Type I Error: Reject \(H_0\) when true. Probability = \(\alpha\).
Type II Error: Fail to reject \(H_0\) when false. Probability = \(\beta\).

z-test (one-sample, known \(\sigma\)):

$$z = \frac{\bar{x} - \mu_0}{\sigma/\sqrt{n}}$$

Compare to standard normal.

t-test (one-sample, unknown \(\sigma\)):

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

Two-sample z-test (known \(\sigma_1,\sigma_2\)):

$$z = \frac{(\bar{x}_1-\bar{x}_2) - (\mu_1-\mu_2)}{\sqrt{\sigma_1^2/n_1 + \sigma_2^2/n_2}}$$

Analysis of Variance (ANOVA) (Frequent):

• Compares means across \(k\) groups.

• Assumptions: Normality, equal variances, independence.

• SST (Total Sum of Squares) = SSB (Between) + SSW (Within).

• Degrees of Freedom: \(df_{Total}=N-1\), \(df_{Between}=k-1\), \(df_{Within}=N-k\).

• Mean Squares: \(MSB = SSB/df_{Between}\), \(MSW = SSW/df_{Within}\).

• Test Statistic: \(F = MSB / MSW \sim F_{k-1, N-k}\) under \(H_0\) (all means equal).

• Reject \(H_0\) if \(F > F_{\alpha}(k-1, N-k)\).

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

Time Series Analysis (Frequent):

• Components: Trend (\(T_t\)), Seasonal (\(S_t\)), Cyclical (\(C_t\)), Irregular (\(I_t\)).

• Models: Additive \(Y_t = T_t + S_t + C_t + I_t\) or Multiplicative \(Y_t = T_t \times S_t \times C_t \times I_t\).

• Moving averages, exponential smoothing for forecasting.

[!TIP] Exam Tip: For hypothesis testing (e.g., Jun 2024 principal salary), clearly state \(H_0, H_a\), compute test statistic, find critical value or p-value, conclude in context.

Quick Reference: High-Frequency Exam Topics