Why the Number of Predictors Matters
Ordinary least-squares selection compares models built from candidate predictors. When there are as many candidate predictors as observations—or more—the search may reach models that cannot be estimated in the usual way, or that fit the observed responses perfectly. Neither outcome automatically gives a useful account of the relationship in new data.
We use \(n\) for the number of observations and \(p\) for the number of candidate explanatory variables; an intercept, when included, is counted separately. A subset model uses some of those \(p\) variables. The issue is not simply the count \(p\): it is also whether the columns of the model’s design matrix contain independent information.
The least-squares calculation itself does not require the usual assumptions about random errors: it chooses coefficients to minimize the sum of squared residuals for the observed data. Those assumptions matter when using the model for statistical inference. In the ordinary linear model, responses are described by a linear mean and errors are independent, have mean zero and common variance; normal errors are additionally used for exact small-sample \(t\)- and \(F\)-inference. These assumptions do not remove a rank deficiency in the observed design.
Rank, Estimability, and Least Squares
Write the response vector as \(\mathbf{y}\) and the coefficient vector as \(\boldsymbol{\beta}\). Least squares minimizes \(\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|^2\). If the columns of \(\mathbf{X}\) are linearly dependent, there is a nonzero vector \(\mathbf{v}\) with \(\mathbf{Xv}=\mathbf{0}\). Consequently, for any coefficient vector \(\boldsymbol{\beta}\) and any number \(t\),
Thus, if \(\boldsymbol{\beta}\) minimizes the residual sum of squares, so does \(\boldsymbol{\beta}+t\mathbf{v}\). The coefficients are not unique. However, the least-squares fitted response vector is unique: it is the projection of \(\mathbf{y}\) onto the column space of \(\mathbf{X}\). Different coefficient vectors can therefore give the same fitted values.
There are at most \(n\) linearly independent columns in a matrix with \(n\) rows. With an intercept and \(k\) predictors, there are \(k+1\) columns, so if \(k+1>n\), the model must be rank deficient. In particular, for \(p\ge n\), a candidate model containing all \(p\) predictors and an intercept has more columns than rows. Some smaller subsets may still be full rank; others may be rank deficient because predictors are duplicates or linear combinations.
Worked Example: More Coefficients Than Independent Directions
Consider three hypothetical observations with responses \(y=(2,3,5)\) and three predictors. Their values are \(x_1=(1,0,0)\), \(x_2=(0,1,0)\), and \(x_3=(1,1,0)\). The model includes an intercept. Show why it can fit exactly but its coefficients are not unique.
The design matrix has an intercept column and the three predictor columns:
The third predictor column is the sum of the first two predictor columns, so the matrix has rank 3, not 4. Set the intercept to 5, \(\beta_1=-3\), \(\beta_2=-2\), and \(\beta_3=0\). The fitted values are \(5-3=2\), \(5-2=3\), and \(5=5\), giving residual sum of squares \(0\).
For any number \(t\), the coefficients \(\beta_1=-3-t\), \(\beta_2=-2-t\), and \(\beta_3=t\), with intercept 5, produce exactly the same fits: the total coefficient on \(x_1\) is \((-3-t)+t=-3\), and the total coefficient on \(x_2\) is \((-2-t)+t=-2\). So the observed fitted values are unique, but the individual coefficients are not. This algebraic example needs no error-distribution assumption.
Exact Fits and the Temptation of Training Fit
If a design matrix has rank \(n\), its columns span all possible response vectors of length \(n\). Least squares can then reproduce any observed \(\mathbf{y}\) exactly. With an intercept and at least \(n-1\) suitably independent predictors, a subset may already have rank \(n\). Such a model has zero residuals and zero residual degrees of freedom.
When the responses are not all identical, the training \(R^2\), defined as \(1-\mathrm{SSE}/\mathrm{SST}\), is then 1. This says the fitted values match the observed responses; it does not show that the model will predict new responses accurately. If the same observations are used both to search over many models and to judge fit, the apparent performance is especially vulnerable to optimism: the search can take advantage of chance patterns in those observations.
Worked Example: A Subset That Interpolates Four Responses
Suppose four hypothetical observations have responses \(y=(1,2,4,8)\), and the candidate set contains four predictors. Among the possible subsets, consider one containing an intercept and three indicator predictors: \(x_1=(1,0,0,0)\), \(x_2=(0,1,0,0)\), and \(x_3=(0,0,1,0)\). The fourth candidate is not needed for this subset.
The design matrix for this subset is \(\mathbf{X}=\begin{pmatrix}1&1&0&0\\1&0&1&0\\1&0&0&1\\1&0&0&0\end{pmatrix}\). It has rank 4. The coefficients \(\beta_0=8\), \(\beta_1=-7\), \(\beta_2=-6\), and \(\beta_3=-4\) yield fitted values \(8-7=1\), \(8-6=2\), \(8-4=4\), and \(8=8\). Thus \(\mathrm{SSE}=0\).
The response mean is \(\bar{y}=15/4=3.75\), and \(\mathrm{SST}=(1-3.75)^2+(2-3.75)^2+(4-3.75)^2+(8-3.75)^2=28.75\). Therefore the training \(R^2=1-0/28.75=1\). The model has four independent columns for four observations, so its residual degrees of freedom are \(4-4=0\). The result establishes an exact fit to these four values, not a reliable estimate of residual variation or good performance on new observations. A criterion that penalizes model size need not choose this subset; the example shows what a training-fit objective can reward.
How Subset and Stepwise Searches Are Affected
Exhaustive subset selection examines candidate subsets and compares them using a chosen selection criterion. With \(p\) candidate predictors there are \(2^p\) subsets before additional restrictions, so the number of models can grow rapidly. When \(p\ge n\), computational cost is not the only concern: some candidate models can be singular, and others can approach or reach a perfect training fit. A procedure that relies on a unique ordinary least-squares coefficient vector cannot use a rank-deficient model without some additional convention, such as dropping redundant columns.
Stepwise procedures consider models along a path, adding or removing predictors according to their rules and selection criterion. They may encounter the same singularity if a proposed step creates dependent columns. If a current model already has rank \(n\), its training residual sum of squares is zero, so adding another predictor cannot lower it. Standard residual-based tests may also be unavailable at that point because there are no residual degrees of freedom. Software may stop, omit a redundant predictor, or report results under a particular computational convention; such behavior does not make the underlying coefficients uniquely determined.
Rank deficiency and optimistic fit are related but distinct problems. A rank-deficient model has redundant coefficient directions, though its fitted values may not be exact. A full-row-rank model can have unique fitted values and still interpolate the sample, with no residual degrees of freedom. Either way, a training result alone is not enough to establish a useful predictive or explanatory model.
Worked Example: Rank Deficiency Does Not Guarantee a Perfect Fit
Take three hypothetical observations with predictor values \(x_1=(0,1,2)\), \(x_2=(0,2,4)\), and \(x_3=(1,1,1)\), and responses \(y=(1,2,4)\). Include an intercept. Since \(x_2=2x_1\) and \(x_3\) is identical to the intercept column, the design matrix has rank 2, even though it has four columns. Its fitted values are those from a straight-line fit using an intercept and \(x_1\).
Here \(\bar{x}_1=1\) and \(\bar{y}=7/3\). The least-squares slope for \(x_1\) is \(\sum_i(x_{1i}-\bar{x}_1)(y_i-\bar{y})/\sum_i(x_{1i}-\bar{x}_1)^2=3/2=1.5\): the numerator is \(4/3+0+5/3=3\), and the denominator is \(1+0+1=2\). The intercept is \(7/3-(3/2)(1)=5/6\). Thus the fitted values are \(5/6\), \(7/3\), and \(23/6\).
The residuals are \(1/6\), \(-1/3\), and \(1/6\), so \(\mathrm{SSE}=(1/6)^2+(-1/3)^2+(1/6)^2=1/6\), not zero. The coefficients for the four-column matrix are nonunique because of its dependencies, but the fitted values are unique. The residual degrees of freedom are \(3-2=1\), calculated from the rank rather than the raw number of columns. The least-squares calculation is valid as a projection; no claim about a true linear relationship or an error distribution is needed for this illustration.
A Short Justification for the Degrees of Freedom
The fitted vector lies in the column space of \(\mathbf{X}\), whose dimension is \(r=\operatorname{rank}(\mathbf{X})\). At the least-squares solution, the residual vector \(\mathbf{e}=\mathbf{y}-\hat{\mathbf{y}}\) is orthogonal to that space. This follows because moving the fitted vector a small distance in any column-space direction cannot reduce the squared residual length; equivalently, the residual has zero inner product with each column of \(\mathbf{X}\). There are \(r\) independent fitted directions among \(n\) response coordinates, leaving \(n-r\) residual directions. Hence the residual degrees of freedom are \(n-r\), not necessarily \(n\) minus the number of coefficient labels in a rank-deficient model.
If \(r=n\), there are no residual directions: \(n-r=0\). This explains both why a full-row-rank model can fit every response vector exactly and why the residual sum of squares then supplies no estimate of residual variance.
Common Mistakes and Practical Checks
- Assuming \(p\ge n\) makes every subset singular. It guarantees that the model with all predictors and an intercept has more columns than rows, but a smaller subset can be full rank. Check the rank of the particular design matrix.
- Concluding that nonunique coefficients mean nonunique predictions. With rank deficiency, coefficients may vary while the fitted vector remains the same. Interpretability of individual coefficients is the problem; the least-squares projection is still unique.
- Treating \(R^2=1\) as proof of a good model. It may only show that a sufficiently flexible model interpolated the training responses. It says nothing by itself about prediction on new observations.
- Counting columns to calculate residual degrees of freedom when columns are dependent. Use \(n-\operatorname{rank}(\mathbf{X})\). If the rank is \(n\), there is no residual information for the usual residual-variance estimate.
- Assuming a stepwise path avoids the issue. A sequential search can still propose redundant predictors or reach a model with zero residual degrees of freedom. Check each model’s rank and remaining degrees of freedom.
Check Your Understanding
Answer each question by considering the design matrix as well as the number of candidate predictors.
- With \(n=8\) observations, an intercept, and 9 selected predictors, what can you conclude about the rank and coefficient uniqueness of that model?
- Can a rank-deficient model have unique least-squares fitted values? Explain briefly.
- A model has \(n=12\) and design-matrix rank 12. What are its residual degrees of freedom, and what does this imply about its training residuals?
- Why might a subset with zero training SSE still be a poor basis for predicting new responses?
- In a model with 10 columns but rank 7 and \(n=15\), how many residual degrees of freedom are there?