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 Properties

• Quadratic Forms:

  • General form: $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}$, where $A$ is symmetric.
  • 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$. For quadratic forms, $A$ is always symmetric (can assume $A_{ij} = A_{ji}$).
  • Eigenvalues of $A^T A$ and $AA^T$: Non-zero eigenvalues are identical.

• Matrix Types:

  • Unitary Matrix: $A^* A = I$ (columns are orthonormal).
  • Hermitian Matrix: $A = A^*$ (self-adjoint; eigenvalues are real).
  • Orthogonal Eigenvectors: For symmetric/Hermitian matrices, eigenvectors are orthogonal.

• Key Equations:

  • Quadratic form expansion: $2x_1x_2 + x_1^2 + 5x_2^2 + 3x_3^2 = \mathbf{x}^T A \mathbf{x}$, where:

• Determinant and nullity: $\det(A) \neq 0 \Rightarrow \text{nullity}(A) = 0$.

2. Convexity

• Convex Set: For any $a, b \in S$ and $\lambda \in [0,1]$, $\lambda a + (1-\lambda)b \in S$.

  • Midpoint: $\frac{a + b}{2}$ is always in $S$.
  • Convex Combination: $0.4a + 0.6b$ is in $S$.

• Convex Functions:

  • Definition: $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$.

  • Examples:

    • $e^{x+y}$ is convex.
    • $\ln(x)$ is concave (but $-\ln(x)$ is convex).
    • Composition $f \circ g$ is convex if $f$ is convex and non-decreasing, and $g$ is convex.
  • Non-Convex Example: $x \ln x$ is not convex on $[0, \infty)$.

3. Optimization & KKT Conditions

• Karush-Kuhn-Tucker (KKT) Conditions (for constrained optimization):

  1. Stationarity: $\nabla f(x) + \sum \lambda_i \nabla g_i(x) = 0$.
  2. Primal Feasibility: $g_i(x) \leq 0$ (for inequalities).
  3. Dual Feasibility: $\lambda_i \geq 0$.
  4. Complementary Slackness: $\lambda_i g_i(x) = 0$.

• Boundary Conditions:

  • If the optimum lies on $g_1(x) = 0$, then $\lambda_1 > 0$.
  • If $g_2(x) < 0$, then $\lambda_2 = 0$.

• Example Problem:

  • Minimize $f(x_1, x_2) = x_1^2 + x_2^2$ subject to $x_1 + x_2 \leq 1$, $x_1 \geq 0$.
  • Optimal solution on boundary $x_1 + x_2 = 1$: $\lambda_1 > 0$, $\lambda_2 \geq 0$.
  • Minimum value: $f(0.5, 0.5) = 0.5$.

4. Probability & Statistics

• Joint/Transformed Distributions:

  • For $U = X + Y$, $V = X - Y$, use the Jacobian transformation:

• Example: $f_{U,V}(u,v) = \frac{u}{54}$ for $0 \leq u \leq 6$, $-u \leq v \leq u$.

• Order Statistics:

  • For $Z = \min(X, Y)$ with $X, Y \sim \text{Uniform}(0,1)$:

• Multivariate Normal Distribution:

  • If $X \sim N(\mu, \Sigma)$ and $Y = a^T X$, then:

• Example: $Y = X_1 + X_2 + 2X_3 \sim N(9, 48)$.

• Linear Combinations of Normals:

  • If $X \sim N(\mu_1, \sigma_1^2)$, $Y \sim N(\mu_2, \sigma_2^2)$, then:

• Example: $W = 3X - 2Y \sim N(-2, 25)$.

5. Gradient Descent

• Update Rule:

• Example:

  • $f(x,y) = x^2 + y^2 - 6x - 8y$.
  • Gradient: $\nabla f = (2x - 6, 2y - 8)$.
  • Initial point $(1, 2)$, $\eta = 0.2$:

• $20x + 20y = 20(1.8 + 2.8) = 92$.

2. Convexity & Optimization

3. Probability & Transformations

4. Gradient Descent Workflow

Key Equations Summary