Why trace of $I−X(X′X)^{-1}X′$ is $n-p$ in least square regression when the parameter vector $\beta$ is of p dimensions?

In the model ${y} = X \beta + \epsilon$, we could estimate $\beta$ using the normal equation：

$$\hat{\beta} = (X'X)^{-1}X'y,$$ and we could get $$\hat{y} = X \hat{\beta}.$$

The vector of residuals is estimated by

$$\hat{\epsilon} = y - X \hat{\beta} = (I - X (X'X)^{-1} X') y = Q y = Q (X \beta + \epsilon) = Q \epsilon,$$

where $$Q = I - X (X'X)^{-1} X'.$$

My question is how to get the conclusion of $$\textrm{tr}(Q) = n - p.$$

The conclusion merely counts dimensions of vector spaces. However, it is not generally true.

The most basic properties of matrix multiplication show that the linear transformation represented by the matrix $$\mathbb{H}=X(X^\prime X)^{-}X^\prime$$ satisfies

$$\mathbb{H}^2 = \left(X(X^\prime X)^{-}X^\prime\right)^2=X(X^\prime X)^{-}(X^\prime X)(X^\prime X)^{-}X^\prime=\mathbb{H},$$

exhibiting it as a projection operator. Therefore its complement

$$\mathbb{Q} = 1 - \mathbb{H}$$

(as given in the question) also is a projection operator. The trace of $$\mathbb{H}$$ is its rank $$h$$ (see below), whence the trace of $$\mathbb{Q}$$ equals $$n-h$$.

From its very formula it is apparent that $$\mathbb{H}$$ is the matrix associated with the composition of two linear transformations $$\mathbb{J}=(X^\prime X)^{-}X^\prime$$ and $$X$$ itself. The first ($$\mathbb{J}$$) transforms the $$n$$-vector $$y$$ into the $$p$$-vector $$\hat\beta$$. The second ($$X$$) is a transformation from $$\mathbb{R}^p$$ to $$\mathbb{R}^n$$ given by $$\hat y = X\hat \beta$$. Its rank cannot exceed the smaller of those two dimensions, which in a least squares setting is always $$p$$ (but could be less than $$p$$, whenever $$\mathbb{J}$$ is not of full rank). Consequently the rank of the composition $$\mathbb{H}=X\mathbb{J}$$ cannot exceed the rank of $$X$$. The correct conclusion, then, is

$$\text{tr} (\mathbb{Q}) = n-p$$ if and only if $$\mathbb{J}$$ is of full rank; and in general $$n \ge \text{tr} (\mathbb{Q}) \ge n-p$$. In the former case the model is said to be "identifiable" (for the coefficients of $$\beta$$).

$$\mathbb{J}$$ will be of full rank if and only if $$X^\prime X$$ is invertible.

Geometric interpretation

$$\mathbb{H}$$ represents the orthogonal projection from $$n$$-vectors $$y$$ (representing the "response" or "dependent variable") onto the space spanned by the columns of $$X$$ (representing the "independent variables" or "covariates"). The difference $$\mathbb{Q}=1-\mathbb{H}$$ shows how to decompose any $$n$$-vector $$y$$ into a sum of vectors $$y = \mathbb{H}(y) + \mathbb{Q}(y),$$ where the first can be "predicted" from $$X$$ and the second is perpendicular to it. When the $$p$$ columns of $$X$$ generate a $$p$$-dimensional space (that is, are not collinear), the rank of $$\mathbb{H}$$ is $$p$$ and the rank of $$\mathbb{Q}$$ is $$n-p$$, reflecting the $$n-p$$ additional dimensions of variation in the response that are not represented within the independent variables. The trace gives an algebraic formula for these dimensions.

Linear Algebra Background

A projection operator on a vector space $$V$$ (such as $$\mathbb{R}^n$$) is a linear transformation $$\mathbb{P}:V\to V$$ (that is, an endomorphism of $$V$$) such that $$\mathbb{P}^2=\mathbb{P}$$. This makes its complement $$\mathbb{Q}=1-\mathbb{P}$$ a projection operator, too, because

$$\mathbb{Q}^2 = \left(1 - \mathbb{P}\right)^2 = 1 - 2\mathbb{P} + \mathbb{P}^2 = 1-2\mathbb{P}+\mathbb{P} = \mathbb{Q}.$$

All projections fix every element of their images, for whenever $$v\in \text{Im}(\mathbb{P})$$ we may write $$v = \mathbb{P}(w)$$ for some $$w\in V$$, whence $$w = \mathbb{P}(v) = \mathbb{P}^2(v) = \mathbb{P}(\mathbb{P}(v)) = \mathbb{P}(w).$$

Associated with any endomorphism $$\mathbb{P}$$ of $$V$$ are two subspaces: its kernel $$\text{ker}(\mathbb{P}) = \{v\in v\,|\, \mathbb{P}(v)=0\}$$ and its image $$\text{Im}(\mathbb{P}) = \{v\in v\,|\, \exists_{w\in V} \mathbb{P}(w)=v\}.$$ Every vector $$v\in V$$ can be written in the form $$v = w+u$$ where $$w\in \text{Im}(\mathbb{P})$$ and $$u\in \text{Ker}(\mathbb{P})$$. We may therefore construct a basis $$E \cup F$$ for $$V$$ for which $$E \subset \text{Ker}(\mathbb{P})$$ and $$F \subset \text{Im}(\mathbb{P})$$. When $$V$$ is finite-dimensional, the matrix of $$\mathbb{P}$$ in this basis will therefore be in block-diagonal form, with one block (corresponding to the action of $$\mathbb{P}$$ on $$E$$) all zeros and the other (corresponding to the action of $$\mathbb{P}$$ on $$F$$) equal to the $$f$$ by $$f$$ identity matrix, where the dimension of $$F$$ is $$f$$. The trace of $$\mathbb{P}$$ is the sum of the values on the diagonal and therefore must equal $$f\times 1 = f$$. This number is the rank of $$\mathbb{P}$$: the dimension of its image.

The trace of $$1-\mathbb{P}$$ equals the trace of $$1$$ (equal to $$n$$, the dimension of $$V$$) minus the trace of $$\mathbb{P}$$.

These results may be summarized with the assertion that the trace of a projection equals its rank.

• Thanks very much. I learned a lot extended knowledge from your answer. Mar 9 '15 at 11:34

@Dougal has already given an answer, but here is another one, a bit simpler.

First, let's use the fact that $\newcommand{\tr}{\mathrm{tr}}\tr(A - B) = \tr(A) - \tr(B)$. So, we get: $$\tr(Q) = \tr(I) - \tr(X(X'X)^{-1}X').$$ Now $I$ is an $n \times n$ identity matrix, so $\tr(I) = n$. Now let's use the fact that $\tr(AB) = \tr(BA)$, that is, the trace is invariant under cyclic permutations. So, we have: $$\tr(Q) = n - \tr((X'X)^{-1}(X'X)).$$ When we multiply $(X'X)^{-1}$ with $(X'X)$, we get a $p \times p$ identity matrix, whose trace is $p$. So, we get: $$\tr(Q) = n - p.$$

$\newcommand\R{\mathbb R}$Assume that $n \le p$ and that $X$ is full-rank.

Consider the compact singular value decomposition $X = U \Sigma V^T$, where $\Sigma \in \R^{p \times p}$ is diagonal and $U \in \R^{n \times p}, V \in \R^{p \times p}$ have $U^T U = V^T V = V V^T = I_p$ (but note $U U^T$ is rank at most $p$ so it cannot be $I_n$). Then

\begin{align} X (X^T X)^{-1} X^T &= U \Sigma V^T (V \Sigma U^T U \Sigma V^T)^{-1} V \Sigma U^T \\&= U \Sigma V^T (V \Sigma^2 V^T)^{-1} V \Sigma U^T \\&= U \Sigma V^T V \Sigma^{-2} V^T V \Sigma U^T \\&= U U^T .\end{align}

Now, there exists a matrix $U_2 \in \R^{n \times n-p}$ such that $U_n = \begin{bmatrix}U & U_2\end{bmatrix}$ is unitary. We can write \begin{align} I - X (X^T X)^{-1} X^T &= U_n U_n^T - U U^T \\&= U_n \left( I_n - \begin{bmatrix}I_p & 0 \\ 0 & 0\end{bmatrix} \right) U_n^T \\&= U_n \begin{bmatrix}0 & 0 \\ 0 & I_{n-p}\end{bmatrix} U_n^T .\end{align} This form shows that $Q$ is positive semidefinite, and since it is a valid svd and the singular values are the square of the eigenvalues for a square symmetric matrix, also tells us that $Q$ has eigenvalues 1 (of multiplicity $n-p$) and 0 (of multiplicity $p$). Thus the trace of $Q$ is $n-p$.