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