{ "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" }, "colab": { "provenance": [] } }, "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Day 18: Linear Independence, Span & Rank\n", "\n", "*Beginner to Ninja: Math for Causal Inference*\n", "\n", "When columns carry the same information, coefficients are not identified. Rank is how you tell.\n", "\n", "**Learning outcomes**\n", "\n", "- Decide whether vectors are linearly independent and find the rank of a matrix.\n", "- Prove that rank(X′X) = rank(X), so X′X is invertible exactly when X has full column rank.\n", "- Recognise perfect collinearity in applied designs (dummy trap, age–period–cohort, fixed effects).\n", "- Quantify near-collinearity with the variance inflation factor." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Theory\n", "\n", "### Span and independence\n", "\n", "- The **span** of vectors $v_1, \\dots, v_k$ is the set of all their linear combinations $\\sum_j c_jv_j$.\n", "- They are **linearly independent** if $\\sum_j c_jv_j = 0$ only when every $c_j = 0$. Otherwise one of them is a combination of the others and adds nothing to the span.\n", "- A **basis** of a space is an independent set that spans it; every basis has the same size, the **dimension**.\n", "\n", "### Rank\n", "\n", "The **rank** of a matrix is the dimension of the span of its columns (the *column space*). Column rank always equals row rank, so $\\operatorname{rank}(X) \\le \\min(n, k)$.\n", "\n", "An $n \\times k$ matrix has **full column rank** if $\\operatorname{rank}(X) = k$: no column is a linear combination of the others. Then $Xv = 0$ only for $v = 0$.\n", "\n", "### Why it matters: identification\n", "\n", "If $Xv = 0$ for some $v \\ne 0$, then for every $\\beta$,\n", "\n", "$$\n", "X(\\beta + v) = X\\beta,\n", "$$\n", "\n", "so two different coefficient vectors give *identical* predictions for every observation. No amount of data can tell them apart: the coefficients are **not identified**. Regression software then drops a column or refuses to run. This is **perfect multicollinearity**.\n", "\n", "### Near-collinearity\n", "\n", "When columns are *almost* dependent, $X^{\\top}X$ is invertible but nearly singular, and coefficient variances explode. For regressor $j$,\n", "\n", "$$\n", "\\operatorname{Var}(\\hat\\beta_j) = \\frac{\\sigma^2}{\\sum_i(x_{ij} - \\bar x_j)^2}\\cdot\\underbrace{\\frac{1}{1 - R_j^2}}_{\\text{VIF}_j},\n", "$$\n", "\n", "where $R_j^2$ comes from regressing $x_j$ on the other regressors (Day 28 proves this).\n", "\n", "> **Causal link.** \"Is the treatment effect identified?\" often reduces to a rank question: if treatment is perfectly predicted by your controls (e.g. it varies only at a level you also include fixed effects for), its coefficient is not identified.\n", "\n", "## Part 1 · Warm-up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1 · Span\n", "\n", "Is $(2, 4)$ in the span of $(1, 2)$? Is $(2, 5)$?\n", "\n", "
Show solution\n", "\n", "$(2, 4) = 2(1, 2)$: yes. $(2, 5) = c(1, 2)$ would need $c = 2$ and $c = 2.5$: no.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2 · Independence\n", "\n", "Are $(1, 0, 1)$, $(0, 1, 1)$ and $(1, 1, 2)$ independent? What is the rank of the matrix with these columns?\n", "\n", "
Show solution\n", "\n", "The third is the sum of the first two, so they are dependent. The first two are independent (neither is a multiple of the other), so the rank is 2.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3 · Rank of a 2×2\n", "\n", "Find the rank of $\\begin{pmatrix}1 & 2\\\\2 & 4\\end{pmatrix}$.\n", "\n", "
Show solution\n", "\n", "The second column is twice the first: rank 1.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4 · The dummy-variable trap\n", "\n", "A regression includes an intercept, a dummy for men and a dummy for women. What is the rank of $X$?\n", "\n", "
Show solution\n", "\n", "Male + female = 1 for everyone, so the three columns are dependent; the rank is 2. Drop one dummy (or the intercept).\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5 · A hidden combination\n", "\n", "$X$ has columns $\\mathbf 1$, $x$ and $2x + 3\\cdot\\mathbf 1$ (e.g. temperature in two units). What is its rank?\n", "\n", "
Show solution\n", "\n", "The third column is $3\\cdot\\mathbf 1 + 2x$: rank 2.\n", "\n", "
\n", "\n", "## Part 2 · Proofs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 6 · Dependence destroys identification\n", "\n", "Prove that if the columns of $X$ are dependent, there exist $\\beta \\ne \\beta'$ with $X\\beta = X\\beta'$.\n", "\n", "
Show solution\n", "\n", "**Step 1.** Dependence means there is $v \\ne 0$ with $Xv = \\sum_j v_jx_{\\cdot j} = 0$.\n", "\n", "**Step 2.** Take any $\\beta$ and set $\\beta' = \\beta + v$.\n", "\n", "**Step 3.** Then $X\\beta' = X\\beta + Xv = X\\beta$ and $\\beta' \\ne \\beta$.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 7 · rank(X′X) = rank(X)\n", "\n", "Prove that $X^{\\top}Xv = 0$ if and only if $Xv = 0$, and conclude that the two matrices have the same rank.\n", "\n", "
Show solution\n", "\n", "**Step 1.** If $Xv = 0$, then $X^{\\top}Xv = 0$.\n", "\n", "**Step 2.** Conversely, if $X^{\\top}Xv = 0$, then $0 = v^{\\top}X^{\\top}Xv = \\|Xv\\|^2$, so $Xv = 0$.\n", "\n", "**Step 3.** The two matrices have the same null space; both have $k$ columns, so by rank–nullity they have the same rank.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 8 · Too many vectors\n", "\n", "Prove that any $n + 1$ vectors in $\\mathbb{R}^n$ are dependent, and that any set containing the zero vector is dependent.\n", "\n", "
Show solution\n", "\n", "**(a) $n + 1$ vectors in $\\mathbb{R}^n$**\n", "\n", "**Step 1.** Put them as the columns of an $n \\times (n + 1)$ matrix.\n", "\n", "**Step 2.** Its rank is at most the number of rows, $n$.\n", "\n", "**Step 3.** That is fewer than its $n + 1$ columns, so the columns are dependent.\n", "\n", "**(b) A set containing the zero vector**\n", "\n", "**Step 4.** If $v_1 = 0$, then $1\\cdot v_1 + 0\\cdot v_2 + \\dots + 0\\cdot v_k = 0$ is a combination equal to zero with a non-zero coefficient. So the set is dependent. $\\blacksquare$\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 9 · When is X′X invertible?\n", "\n", "Prove that the $k \\times k$ matrix $X^{\\top}X$ is invertible if and only if $X$ has full column rank.\n", "\n", "
Show solution\n", "\n", "A square matrix is invertible iff its rank equals its size. By Exercise 7, $\\operatorname{rank}(X^{\\top}X) = \\operatorname{rank}(X)$, which equals $k$ exactly when $X$ has full column rank.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 10 · Redundant columns change nothing\n", "\n", "Show that adding a column that is a linear combination of existing columns does not change the column space of $X$ (and hence will not change fitted values).\n", "\n", "
Show solution\n", "\n", "**Step 1.** Let the new column be $w = Xc$.\n", "\n", "**Step 2.** Any combination $Xb + aw = X(b + ac)$ already lies in the old column space, and the old space is contained in the new one.\n", "\n", "**Step 3.** So the spans are equal.\n", "\n", "**Step 4.** Fitted values are the projection of $y$ onto this space (Day 20), so they are unchanged.\n", "\n", "
\n", "\n", "## Part 3 · Applied" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 11 · Regional fixed effects\n", "\n", "A data set covers 4 regions. How many region dummies can you include alongside an intercept, and how do you interpret their coefficients?\n", "\n", "
Show solution\n", "\n", "**Step 1.** The four region dummies add up to the intercept column (every observation is in exactly one region), so all four plus the intercept are dependent.\n", "\n", "**Step 2.** Drop one dummy (the reference region, say region 1); the remaining columns are independent.\n", "\n", "**Step 3.** Interpretation: each included dummy's coefficient is that region's difference from region 1, holding the other regressors fixed.\n", "\n", "**Answer:** three dummies.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 12 · Age, period and cohort\n", "\n", "Why can't a regression include age, survey year and birth year as linear terms?\n", "\n", "
Show solution\n", "\n", "**Step 1.** Age = survey year − birth year for every respondent.\n", "\n", "**Step 2.** So the age column equals (period column) − (cohort column): an exact linear combination, and $X$ is rank-deficient.\n", "\n", "**Step 3.** By Exercise 6, infinitely many combinations of age, period and cohort coefficients fit the data equally well.\n", "\n", "**Answer:** the three linear effects cannot be separated without an extra restriction (e.g. one effect set to zero, or grouped categories). That restriction is an assumption, not something the data reveal.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 13 · Variance inflation\n", "\n", "Regressor $x_2$ has $R^2 = 0.9801$ (correlation 0.99) on the other regressors. Compute its VIF and the factor by which its standard error is inflated.\n", "\n", "
Show solution\n", "\n", "**Step 1.** $\\text{VIF} = 1/(1 - R^2) = 1/(1 - 0.9801) = 1/0.0199 \\approx 50.3$.\n", "\n", "**Step 2.** SEs scale with the square root of the variance: $\\sqrt{50.3} \\approx 7.1$.\n", "\n", "**Answer:** VIF ≈ 50; the SE is about 7 times larger than if $x_2$ were uncorrelated with the other regressors.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 14 · A policy that varies only by state\n", "\n", "A minimum-wage increase affects all workers in treated states, in every year of the data. The regression includes state fixed effects. Can it estimate the policy effect?\n", "\n", "
Show solution\n", "\n", "**Step 1.** Treatment is 1 for every worker in a treated state in every year.\n", "\n", "**Step 2.** So the treatment column equals the sum of the treated states' dummy columns: it lies in the span of the state fixed effects.\n", "\n", "**Step 3.** Perfect collinearity: the coefficient is not identified (Exercise 6).\n", "\n", "**Answer:** no. The effect is identified only if treatment varies *within* states over time, e.g. a law that starts in a later year (difference-in-differences, Phase 5).\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 15 · More variables than observations\n", "\n", "A data set has $n = 50$ units and $k = 200$ covariates. What is the maximum rank of $X$, and what does that imply for OLS?\n", "\n", "
Show solution\n", "\n", "**Step 1.** $\\operatorname{rank}(X) \\le \\min(n, k) = \\min(50, 200) = 50$.\n", "\n", "**Step 2.** $X^{\\top}X$ is $200 \\times 200$ with rank at most 50 (Exercise 7), so it is singular.\n", "\n", "**Step 3.** The normal equations then have infinitely many solutions.\n", "\n", "**Answer:** OLS is not defined. Regularisation (ridge, lasso) adds information through a penalty or prior; this is the high-dimensional setting of double machine learning (Phase 6).\n", "\n", "
\n", "\n", "## Verify in Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "import numpy as np\n", "\n", "V = np.array([[1, 0, 1], [0, 1, 1], [1, 1, 2]]).T\n", "print(\"rank of [v1 v2 v3]:\", np.linalg.matrix_rank(V))\n", "\n", "rng = np.random.default_rng(18)\n", "n = 200\n", "male = rng.integers(0, 2, n)\n", "X = np.column_stack([np.ones(n), male, 1 - male])\n", "print(\"dummy trap rank:\", np.linalg.matrix_rank(X), \"of\", X.shape[1], \"; rank(X'X) =\", np.linalg.matrix_rank(X.T @ X))\n", "\n", "# Near collinearity: VIF and SE inflation by simulation\n", "x1 = rng.normal(size=n)\n", "for rho in (0.0, 0.9, 0.99):\n", " x2 = rho * x1 + np.sqrt(1 - rho**2) * rng.normal(size=n)\n", " Z = np.column_stack([np.ones(n), x1, x2])\n", " r2 = 1 - np.var(x2 - Z[:, :2] @ np.linalg.lstsq(Z[:, :2], x2, rcond=None)[0]) / np.var(x2)\n", " se = np.sqrt(np.linalg.inv(Z.T @ Z)[2, 2]) # SE of b2 when sigma = 1\n", " print(f\"rho={rho:.2f}: VIF = {1/(1-r2):6.1f}, SE(b2) = {se:.3f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Key takeaways\n", "\n", "- Rank counts the independent columns; full column rank is the condition for unique OLS coefficients.\n", "- $\\operatorname{rank}(X^{\\top}X) = \\operatorname{rank}(X)$, so \"$X^{\\top}X$ invertible\" and \"no perfect collinearity\" are the same statement.\n", "- Near-collinearity is not a bias problem but a precision problem, measured by the VIF." ] } ] }