Equivalence of Null-Space and Multiplier Solutions

Two Ways to Solve the Same Constrained Problem

A linear restriction such as \(C\beta=d\) can be handled by building the restriction into the coefficient parameterization, or by retaining the original coefficients and adding multipliers to the normal equations. These approaches look different: one minimizes over a smaller parameter space, while the other solves a system involving the restrictions. Their equivalence is useful both computationally and conceptually, especially when the design matrix is rank deficient.

Let \(X\) be an \(n\times p\) design matrix, \(y\in\mathbb{R}^n\), and let \(C\) be an \(m\times p\) matrix. Assume the restriction \(C\beta=d\) is feasible. We will not assume that \(X\) has full column rank or that the rows of \(C\) are linearly independent. Define the least-squares objective, scaled for convenience, by

Q(\beta)=\frac{1}{2}\|y-X\beta\|^2,\qquad C\beta=d.

Multiplying an objective by the positive constant \(1/2\) does not change its minimizers. Let \(\beta_0\) be any one feasible coefficient vector, and let the columns of \(N\) be a basis for the null space \(\ker(C)=\{h:Ch=0\}\). Thus \(N\) has \(p\) rows and full column rank; it may have zero columns if the null space contains only the zero vector.

Definition: A null-space parameterization of the feasible coefficients is \(\beta=\beta_0+N\gamma\), where \(C\beta_0=d\) and the columns of \(N\) form a basis for \(\ker(C)\). The vector \(\gamma\) ranges over all of \(\mathbb{R}^k\), where \(k=\dim\ker(C)\).

Indeed, \(C(\beta_0+N\gamma)=d\), since \(CN=0\). Conversely, for any feasible \(\beta\), the difference \(\beta-\beta_0\) belongs to \(\ker(C)\), so it equals \(N\gamma\) for some \(\gamma\). Because the columns of \(N\) are independent, that \(\gamma\) is unique.

Reduced Normal Equations and Multiplier Equations

Substituting the parameterization gives an ordinary least-squares problem in \(\gamma\), with response \(y-X\beta_0\) and design matrix \(XN\). Differentiating its quadratic objective yields the reduced normal equations. These equations remain valid if \(XN\) is rank deficient; in that case they can have multiple solutions.

N^{T}X^{T}X N\gamma=N^{T}X^{T}(y-X\beta_0).

The multiplier approach instead uses the original coefficient vector. With the sign convention below, its equations are the original least-squares stationarity equation augmented by feasibility.

X^{T}(X\beta-y)+C^{T}\lambda=0,\qquad C\beta=d.

Here \(\lambda\in\mathbb{R}^m\) is a vector of Lagrange multipliers. If \(C\) has dependent rows, the multiplier need not be unique. The coefficient solutions, however, are precisely the constrained least-squares minimizers.

Equivalence Theorem

Theorem: Suppose \(C\beta=d\) is feasible and \(N\) has columns forming a basis for \(\ker(C)\). A feasible \(\beta\) minimizes \(Q(\beta)\) if and only if \(N^{T}X^{T}(X\beta-y)=0\). Equivalently, a feasible \(\beta\) minimizes \(Q\) if and only if there exists a multiplier \(\lambda\) satisfying \(X^{T}(X\beta-y)+C^{T}\lambda=0\). Substituting \(\beta=\beta_0+N\gamma\), the first condition is exactly the reduced normal equation. The null-space and multiplier methods therefore yield the same set of minimizing coefficient vectors. All those minimizers have the same fitted vector \(X\beta\).

Proof. First consider a feasible \(\beta\). Every feasible displacement from \(\beta\) has the form \(h\in\ker(C)\), since \(C(\beta+h)=d\) exactly when \(Ch=0\). For such an \(h\), direct expansion gives

Q(\beta+h)-Q(\beta) =h^{T}X^{T}(X\beta-y)+\frac{1}{2}\|Xh\|^2.

If \(\beta\) minimizes \(Q\), the one-variable function \(t\mapsto Q(\beta+th)\) has a minimum at \(t=0\) for every \(h\in\ker(C)\). Its derivative there is \(h^{T}X^{T}(X\beta-y)\), which must be zero. In particular, taking \(h=N\gamma\) for arbitrary \(\gamma\) gives \(N^{T}X^{T}(X\beta-y)=0\).

Conversely, suppose this matrix equation holds. Every \(h\in\ker(C)\) can be written as \(N\gamma\), so \(h^{T}X^{T}(X\beta-y)=0\). The expansion then gives \(Q(\beta+h)-Q(\beta)=\frac12\|Xh\|^2\geq 0\). Thus \(\beta\) is a constrained minimizer. Substituting \(\beta=\beta_0+N\gamma\) into the matrix equation gives the reduced normal equations displayed above.

It remains to establish the multiplier form. The condition \(N^{T}X^{T}(X\beta-y)=0\) says that \(g=X^{T}(X\beta-y)\) is orthogonal to every vector in \(\ker(C)\). In finite-dimensional linear algebra, \((\ker C)^\perp=\operatorname{range}(C^T)\). Hence \(g\in\operatorname{range}(C^T)\), so there is a \(\lambda\) with \(g+C^{T}\lambda=0\). This argument does not require \(C\) to have full row rank. Conversely, if this multiplier equation holds, then for every \(h\in\ker(C)\), \(h^{T}g=-h^{T}C^{T}\lambda=-(Ch)^{T}\lambda=0\). The feasible-direction condition follows, so \(\beta\) minimizes \(Q\).

Finally, suppose \(\beta_1\) and \(\beta_2\) are both minimizers. Their midpoint is feasible. For the squared-norm objective,

Q\left(\frac{\beta_1+\beta_2}{2}\right) =\frac{Q(\beta_1)+Q(\beta_2)}{2} -\frac{1}{8}\|X(\beta_1-\beta_2)\|^2.

If \(X\beta_1\ne X\beta_2\), the final term is strictly positive, making the midpoint objective smaller than the minimum, a contradiction. Therefore \(X\beta_1=X\beta_2\). This proves the claimed equivalence and uniqueness of the fitted vector, even when minimizing coefficients are not unique. \(\square\)

Worked Calculations

Worked Example: A Common Coefficient Across Three Observations

Let \(X=I_3\), \(y=(1,2,2)^T\), and impose \(\beta_1=\beta_2=\beta_3\). The restriction can be written \(C\beta=0\) with

C=\begin{pmatrix}1&-1&0\\0&1&-1\end{pmatrix}.

Choose \(\beta_0=0\) and \(N=(1,1,1)^T\). Then every feasible vector is \(\beta=(\gamma,\gamma,\gamma)^T\). The unscaled residual sum of squares is

(1-\gamma)^2+(2-\gamma)^2+(2-\gamma)^2.

Differentiating gives \(2(\gamma-1)+2(\gamma-2)+2(\gamma-2)=0\). Combining terms gives \(6\gamma-10=0\), hence \(6\gamma=10\) and \(\gamma=5/3\). The constrained coefficient vector and fitted vector are both \((5/3,5/3,5/3)^T\). The residual sum of squares is \((2/3)^2+(-1/3)^2+(-1/3)^2=6/9=2/3\).

For the multiplier calculation, the equations are \(\beta-y+C^T\lambda=0\) and \(C\beta=0\). At \(\beta=(5/3,5/3,5/3)^T\), \(\beta-y=(2/3,-1/3,-1/3)^T\). Taking \(\lambda_1=-2/3\) and \(\lambda_2=-1/3\) gives \(C^T\lambda=(-2/3,1/3,1/3)^T\); the stationarity equation is satisfied. Both routes produce the same feasible minimizer and fit.

Worked Example: A Nonzero Linear Restriction

Let \(X=I_2\), \(y=(2,0)^T\), and require \(\beta_1+\beta_2=1\). Use \(\beta_0=(0,1)^T\) and \(N=(1,-1)^T\), so \(\beta=(\gamma,1-\gamma)^T\). The residual sum of squares is \((2-\gamma)^2+(1-\gamma)^2\). Its derivative is \(2(\gamma-2)+2(\gamma-1)=4\gamma-6\), so \(\gamma=3/2\) and \(\hat\beta=(3/2,-1/2)^T\). The fitted vector is the same vector, and the residual sum of squares is \((1/2)^2+(-1/2)^2=1/2\).

For the multiplier equations, \(C=(1,1)\), and \(X^T(X\beta-y)=\beta-y=(-1/2,-1/2)^T\). The equation \(\beta-y+C^T\lambda=0\) is satisfied by \(\lambda=1/2\), since \(C^T\lambda=(1/2,1/2)^T\). The restriction also checks directly: \(3/2-1/2=1\). Thus both methods give the same coefficients and fit.

Worked Example: A Rank-Deficient Design and Nonunique Coefficients

Take the one-row design matrix \(X=(1,1,0)\), response \(y=2\), and restriction \(\beta_1=0\), so \(C=(1,0,0)\), \(d=0\). A feasible vector has the form \(\beta=(0,\gamma,\delta)^T\). Here \(N\) can have columns \((0,1,0)^T\) and \((0,0,1)^T\). The fitted value is \(X\beta=\gamma\), so the residual sum of squares is \((2-\gamma)^2\). It is minimized at \(\gamma=2\), while \(\delta\) is unrestricted. Thus all minimizing coefficients are \((0,2,\delta)^T\), for any real \(\delta\), and every one gives fitted value \(2\).

For any such coefficient vector, \(X^T(X\beta-y)=0\), since \(X\beta-y=0\). The multiplier equation becomes \(C^T\lambda=(\lambda,0,0)^T=0\), satisfied by \(\lambda=0\). Feasibility holds because \(\beta_1=0\). The example verifies that equivalence does not imply unique coefficients: it guarantees the same coefficient solution set and a unique fitted vector.

Why the Equivalence Matters—and a Common Pitfall

The null-space method removes the restrictions from the optimization by working directly in the feasible directions. The multiplier method keeps the original coefficients and records the restrictions as additional equations. One can choose between them based on the problem’s size, structure, or numerical convenience. The theorem ensures that the choice does not alter the minimizing coefficients or the fitted values. Rank deficiency may leave coefficients undetermined, but it does not invalidate either formulation.

Common mistake: Assuming the multiplier equations require \(C\) to have independent rows, or assuming that rank deficiency in \(X\) prevents a solution. Independent rows would help make the multiplier unique, but are not needed for a multiplier to exist. The proof only needs the identity \((\ker C)^\perp=\operatorname{range}(C^T)\). Likewise, the least-squares minimum exists in finite dimensions even when \(XN\) is rank deficient; what can fail is uniqueness of the minimizing parameter, not existence of a minimizing fit.

Another computational pitfall is an arithmetic error while simplifying the derivative. In the first example the derivative equation is \(6\gamma-10=0\), so \(6\gamma=10\), not \(6\gamma=5\). Substituting \(\gamma=5/3\) checks the correct equation because \(6(5/3)=10\).

Check Your Understanding

Use the definitions and equivalence result to answer the following.

Why does every feasible coefficient vector have the form \(\beta_0+N\gamma\)?
What condition on the gradient characterizes a constrained least-squares minimizer?
Why can a multiplier exist even when the rows of \(C\) are linearly dependent?
In a rank-deficient design, which quantity is guaranteed to be the same across all constrained minimizers: the coefficient vector or the fitted vector?
For \(X=I_2\), \(y=(3,1)^T\), and \(\beta_1+\beta_2=2\), find a null-space parameterization and minimize the resulting residual sum of squares.