Day 18: Linear Independence, Span & Rank · Math for Causal Inference

Theory

Span and independence

The span of vectors $v_1, \dots, v_k$ is the set of all their linear combinations $\sum_j c_jv_j$ .
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.
A basis of a space is an independent set that spans it; every basis has the same size, the dimension.

Rank

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

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$ .

Why it matters: identification

If $Xv = 0$ for some $v \ne 0$ , then for every $\beta$ ,

X(\beta + v) = X\beta,

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.

Near-collinearity

When columns are almost dependent, $X^{\top}X$ is invertible but nearly singular, and coefficient variances explode. For regressor $j$ ,

\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},

where $R_j^2$ comes from regressing $x_j$ on the other regressors (Day 28 proves this).

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.

Part 1 · Warm-up

Exercise 1 · Span

Is $(2, 4)$ in the span of $(1, 2)$ ? Is $(2, 5)$ ?

Show solution

$(2, 4) = 2(1, 2)$ : yes. $(2, 5) = c(1, 2)$ would need $c = 2$ and $c = 2.5$ : no.

Exercise 2 · Independence

Are $(1, 0, 1)$ , $(0, 1, 1)$ and $(1, 1, 2)$ independent? What is the rank of the matrix with these columns?

Show solution

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.

Exercise 3 · Rank of a 2×2

Find the rank of $\begin{pmatrix}1 & 2\\2 & 4\end{pmatrix}$ .

Show solution

The second column is twice the first: rank 1.

Exercise 4 · The dummy-variable trap

A regression includes an intercept, a dummy for men and a dummy for women. What is the rank of $X$ ?

Show solution

Male + female = 1 for everyone, so the three columns are dependent; the rank is 2. Drop one dummy (or the intercept).

Exercise 5 · A hidden combination

$X$ has columns $\mathbf 1$ , $x$ and $2x + 3\cdot\mathbf 1$ (e.g. temperature in two units). What is its rank?

Show solution

The third column is $3\cdot\mathbf 1 + 2x$ : rank 2.

Part 2 · Proofs

Exercise 6 · Dependence destroys identification

Prove that if the columns of $X$ are dependent, there exist $\beta \ne \beta'$ with $X\beta = X\beta'$ .

Show solution

Step 1. Dependence means there is $v \ne 0$ with $Xv = \sum_j v_jx_{\cdot j} = 0$ .

Step 2. Take any $\beta$ and set $\beta' = \beta + v$ .

Step 3. Then $X\beta' = X\beta + Xv = X\beta$ and $\beta' \ne \beta$ .

Exercise 7 · rank(X′X) = rank(X)

Prove that $X^{\top}Xv = 0$ if and only if $Xv = 0$ , and conclude that the two matrices have the same rank.

Show solution

Step 1. If $Xv = 0$ , then $X^{\top}Xv = 0$ .

Step 2. Conversely, if $X^{\top}Xv = 0$ , then $0 = v^{\top}X^{\top}Xv = \|Xv\|^2$ , so $Xv = 0$ .

Step 3. The two matrices have the same null space; both have $k$ columns, so by rank–nullity they have the same rank.

Exercise 8 · Too many vectors

Prove that any $n + 1$ vectors in $\mathbb{R}^n$ are dependent, and that any set containing the zero vector is dependent.

Show solution

(a) $n + 1$ vectors in $\mathbb{R}^n$

Step 1. Put them as the columns of an $n \times (n + 1)$ matrix.

Step 2. Its rank is at most the number of rows, $n$ .

Step 3. That is fewer than its $n + 1$ columns, so the columns are dependent.

(b) A set containing the zero vector

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$

Exercise 9 · When is X′X invertible?

Prove that the $k \times k$ matrix $X^{\top}X$ is invertible if and only if $X$ has full column rank.

Show solution

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.

Exercise 10 · Redundant columns change nothing

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).

Show solution

Step 1. Let the new column be $w = Xc$ .

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.

Step 3. So the spans are equal.

Step 4. Fitted values are the projection of $y$ onto this space (Day 20), so they are unchanged.

Part 3 · Applied

Exercise 11 · Regional fixed effects

A data set covers 4 regions. How many region dummies can you include alongside an intercept, and how do you interpret their coefficients?

Show solution

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.

Step 2. Drop one dummy (the reference region, say region 1); the remaining columns are independent.

Step 3. Interpretation: each included dummy's coefficient is that region's difference from region 1, holding the other regressors fixed.

Answer: three dummies.

Exercise 12 · Age, period and cohort

Why can't a regression include age, survey year and birth year as linear terms?

Show solution

Step 1. Age = survey year − birth year for every respondent.

Step 2. So the age column equals (period column) − (cohort column): an exact linear combination, and $X$ is rank-deficient.

Step 3. By Exercise 6, infinitely many combinations of age, period and cohort coefficients fit the data equally well.

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.

Exercise 13 · Variance inflation

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.

Show solution

Step 1. $\text{VIF} = 1/(1 - R^2) = 1/(1 - 0.9801) = 1/0.0199 \approx 50.3$ .

Step 2. SEs scale with the square root of the variance: $\sqrt{50.3} \approx 7.1$ .

Answer: VIF ≈ 50; the SE is about 7 times larger than if $x_2$ were uncorrelated with the other regressors.

Exercise 14 · A policy that varies only by state

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?

Show solution

Step 1. Treatment is 1 for every worker in a treated state in every year.

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.

Step 3. Perfect collinearity: the coefficient is not identified (Exercise 6).

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).

Exercise 15 · More variables than observations

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?

Show solution

Step 1. $\operatorname{rank}(X) \le \min(n, k) = \min(50, 200) = 50$ .

Step 2. $X^{\top}X$ is $200 \times 200$ with rank at most 50 (Exercise 7), so it is singular.

Step 3. The normal equations then have infinitely many solutions.

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).

Verify in Python

import numpy as np

V = np.array([[1, 0, 1], [0, 1, 1], [1, 1, 2]]).T
print("rank of [v1 v2 v3]:", np.linalg.matrix_rank(V))

rng = np.random.default_rng(18)
n = 200
male = rng.integers(0, 2, n)
X = np.column_stack([np.ones(n), male, 1 - male])
print("dummy trap rank:", np.linalg.matrix_rank(X), "of", X.shape[1], "; rank(X'X) =", np.linalg.matrix_rank(X.T @ X))

# Near collinearity: VIF and SE inflation by simulation
x1 = rng.normal(size=n)
for rho in (0.0, 0.9, 0.99):
    x2 = rho * x1 + np.sqrt(1 - rho**2) * rng.normal(size=n)
    Z = np.column_stack([np.ones(n), x1, x2])
    r2 = 1 - np.var(x2 - Z[:, :2] @ np.linalg.lstsq(Z[:, :2], x2, rcond=None)[0]) / np.var(x2)
    se = np.sqrt(np.linalg.inv(Z.T @ Z)[2, 2])          # SE of b2 when sigma = 1
    print(f"rho={rho:.2f}: VIF = {1/(1-r2):6.1f}, SE(b2) = {se:.3f}")

Key takeaways

Rank counts the independent columns; full column rank is the condition for unique OLS coefficients.
$\operatorname{rank}(X^{\top}X) = \operatorname{rank}(X)$ , so " $X^{\top}X$ invertible" and "no perfect collinearity" are the same statement.
Near-collinearity is not a bias problem but a precision problem, measured by the VIF.

Day 18. Linear Independence, Span & Rank

Theory

Span and independence

Rank

Why it matters: identification

Near-collinearity

Part 1 · Warm-up

Exercise 1 · Span

Exercise 2 · Independence

Exercise 3 · Rank of a 2×2

Exercise 4 · The dummy-variable trap

Exercise 5 · A hidden combination

Part 2 · Proofs

Exercise 6 · Dependence destroys identification

Exercise 7 · rank(X′X) = rank(X)

Exercise 8 · Too many vectors

Exercise 9 · When is X′X invertible?

Exercise 10 · Redundant columns change nothing

Part 3 · Applied

Exercise 11 · Regional fixed effects

Exercise 12 · Age, period and cohort

Exercise 13 · Variance inflation

Exercise 14 · A policy that varies only by state

Exercise 15 · More variables than observations

Verify in Python

Key takeaways

Simulation Lab: Collinearity & Rank