IIT M FOUNDATION DIPLOMA AN EXAM - 22 Dec 2024

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Key Concepts

1. Linear Algebra & Matrix Theory

• Quadratic Forms & Matrices:

  • Quadratic form: $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}$.
  • Positive Definite Matrix: $\mathbf{x}^T A \mathbf{x} > 0$ for all $\mathbf{x} \neq 0$.
  • Singular Matrix: $\det(A) = 0$ ⇒ at least one eigenvalue is 0.
  • Symmetric Matrix: $A = A^T$.

  • Eigenvalues/Eigenvectors:

    • For symmetric matrices, eigenvalues are real, and eigenvectors are orthogonal.
    • $A$ is unitary if $A^* A = I$ (for complex matrices).
    • $A$ is Hermitian if $A = A^*$.

• Key Equations:

  • Eigenvalue equation: $A \mathbf{v} = \lambda \mathbf{v}$.
  • Determinant properties: $\det(AB) = \det(A)\det(B)$, $\det(A^T A) = \det(A A^T)$.
  • Rank-nullity theorem: $\text{rank}(A) + \text{nullity}(A) = n$.

2. Convexity & Optimization

• Convex Sets:

  • A set $S$ is convex if for any $a, b \in S$, $\theta a + (1-\theta)b \in S$ for $\theta \in [0, 1]$.
  • Examples: Midpoint ($\theta = 0.5$), linear combinations (e.g., $0.4a + 0.6b$).

• Convex Functions:

  • $f$ is convex if $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$.

  • Tests for Convexity:

    • Hessian $\nabla^2 f \succeq 0$ (positive semidefinite).
    • Composition rules: If $f$ is convex and $g$ is convex + non-decreasing, then $f \circ g$ is convex.

  • Examples:

    • $e^{x+y}$ is convex.
    • $x \ln x$ is convex for $x > 0$.
    • $-\ln(xy)$ is not convex.

• Optimization with Constraints (KKT Conditions):

  • Primal Problem: Minimize $f(\mathbf{x})$ subject to $g_i(\mathbf{x}) \leq 0$, $h_j(\mathbf{x}) = 0$.

  • KKT Conditions:

    1. Stationarity: $\nabla f(\mathbf{x}) + \sum \lambda_i \nabla g_i(\mathbf{x}) + \sum \mu_j \nabla h_j(\mathbf{x}) = 0$.
    2. Primal feasibility: $g_i(\mathbf{x}) \leq 0$, $h_j(\mathbf{x}) = 0$.
    3. Dual feasibility: $\lambda_i \geq 0$.
    4. Complementary slackness: $\lambda_i g_i(\mathbf{x}) = 0$.
  • Boundary Conditions: If the optimum lies on a constraint $g_i(\mathbf{x}) = 0$, then $\lambda_i > 0$.

3. Probability & Statistics

• Random Variables & Distributions:

  • Uniform Distribution: $X \sim \text{Uniform}(a, b)$, CDF: $F_X(x) = \frac{x - a}{b - a}$.

  • Normal Distribution: $X \sim N(\mu, \sigma^2)$.

    • Linear transformation: If $Y = aX + b$, then $Y \sim N(a\mu + b, a^2 \sigma^2)$.

  • Joint PDFs & Transformations:

    • For $U = X + Y$, $V = X - Y$, use the Jacobian to find $f_{U,V}(u,v)$.
    • Example: $f_{U,V}(u,v) = \frac{u}{54}$ for $0 \leq u \leq 6$, $-u \leq v \leq u$.

• Order Statistics:

  • For independent $X, Y \sim \text{Uniform}(0,1)$, $Z = \min(X, Y)$ has CDF: $F_Z(z) = 1 - (1 - z)^2$.

• Multivariate Normal Distribution:

  • If $\mathbf{X} \sim N(\mu, \Sigma)$, then $Y = a^T \mathbf{X} \sim N(a^T \mu, a^T \Sigma a)$.

4. Gradient Descent

• Update Rule: $\mathbf{x}_{k+1} = \mathbf{x}_k - \eta \nabla f(\mathbf{x}_k)$.
• Example: For $f(x,y) = x^2 + y^2 - 6x - 8y$, gradient: $\nabla f = (2x - 6, 2y - 8)$. After one iteration with $\eta = 0.2$, $(x, y) = (1, 2) \rightarrow (1.8, 2.4)$.

Key Equations Summary

2. Convexity & Optimization

3. Probability & Statistics

4. Gradient Descent

Exam Tips

1. Matrix Properties: Focus on positive definiteness, eigenvalues, and symmetry.
2. Convexity: Remember tests for convex functions (Hessian, composition rules).
3. KKT Conditions: Memorize the 4 conditions and when $\lambda_i > 0$.
4. Probability: Practice transformations (e.g., $U = X + Y$, $V = X - Y$) and order statistics.
5. Gradient Descent: Compute gradients carefully and apply the update rule step-by-step.