Represent the two sides of the marriage problem as the parts $L,R$ of a bipartite graph, with an edge for each allowed pairing. A matching is a set of edges with no common endpoint; a complete matching of $L$ covers every vertex in $L$. When the two parts have equal size it also covers $R$, giving a perfect matching.

Hall's marriage theorem gives the exact finite-graph criterion:Here $N(S)$ is the set of right-side neighbours of $S$. Necessity follows because distinct matched vertices of $S$ need distinct neighbours; Hall's theorem supplies sufficiency.

Multiplying the system by $Q^T$ turns it into $Rx=Q^{T}b$. For nonsingular $A$, compute the transformed right side and solve the upper triangular system by back substitution. Orthogonal transformations preserve Euclidean lengths and do not amplify errors in that transformation.

If $A$ is singular,Since $\det Q=\pm 1$, at least one diagonal entry of $R$ is zero. The resulting triangular system must then be checked for consistency and any free variables, rather than applying divisions by zero.

Apply part (b) to the first column of $A$, using an orthogonal reflection to zero all entries below the first. Next apply a Householder reflection to the trailing subvector of the second column, embedded as $\mathrm{diag}(1,H_2)$ so it leaves the first row and the zeros already created intact. Continue similarly through the columns. If a trailing column subvector is zero, skip that step.

The product of these embedded orthogonal matrices sends $A$ to an upper triangular matrix $R$. Write that product as $Q^T$; its transpose $Q$ is also orthogonal. HenceThe argument uses no inverse of $A$ and therefore includes singular matrices.

Let $r=\Vert u{\Vert }_2>0$ and choose $s=1$ when $u_1\ge 0$, otherwise $s=-1$. Set $w=u+sr{e}_1$, which is nonzero because $r+s{u}_1>0$. ComputeThus the reflecting term in $H(w)u$ is exactly $w$, givingIts first coordinate is nonzero and all remaining coordinates vanish. The choice of sign also avoids subtracting nearly equal vectors when the first component is large.

For nonzero $w$, the Householder transformation isThe rank-one matrix $P=w{w}^T/(w^{T}w)$ is symmetric and satisfies $P^2=P$. Consequently $H^T=H$ and $H^{T}H=(I-2P{)}^2=I-4P+4P^2=I$. Thus the matrix is symmetric and orthogonal; geometrically it reflects the component along $w$ and fixes its perpendicular hyperplane.

By part (c), the best degree-at-most-two polynomial is odd, so it must be $p_2(x)=bx$. Orthogonality to $x$ givesThereforeIts error is automatically orthogonal to the even basis functions $1,x^2$ by parity, and the chosen coefficient makes it orthogonal to $x$, so part (b) verifies optimality.

For odd $u$, define $q(x)=-p_n(-x)$. It is another polynomial in ${\Pi }_n$. Changing variables $x\mapsto -x$, and using evenness of the weight $x^2$, gives $\Vert u-q\Vert =\Vert u-p_n\Vert$. Thus $q$ is also a best polynomial. Uniqueness from part (b) gives $p_n(x)=-p_n(-x)$, provingEquivalently, the even component of a candidate is orthogonal to the odd residual and can only increase the squared error.

If the error is orthogonal to ${\Pi }_n$, then for any $q\in {\Pi }_n$,proving sufficiency. Conversely, if $p_n$ minimizes, perturb it to $p_n+tq$ for any real $t$. The squared error becomesA minimum at $t=0$ forces the linear coefficient to vanish, proving necessity.

For existence, choose the basis $1,x,\dots ,x^n$. Its Gram matrix $G$ is positive definite because $c^{T}Gc$ is the squared norm of the nonzero polynomial with coefficients $c$. Thus $G$ is invertible, and the normal equations $Gc=((u,x^j){)}_{j=0}^n$ have a solution, giving an orthogonal residual and therefore a minimizer. The Pythagorean identity shows any other minimizer differs by a polynomial of zero norm, so it is equal to the first. Hence the best polynomial exists and is unique.

The best polynomial minimizes the weighted squared error among all polynomials of degree at most $n$:The given inner product is positive definite on continuous functions despite the weight vanishing at zero: a continuous nonzero function is nonzero on an interval containing nonzero points, so its weighted square integral is strictly positive.

Put $C=(X^{T}X{)}^{-1}$ and $\nu =n-p$. The normal law of the estimator gives $({\hat{\theta }}_i-{\theta }_i)/(\sigma \sqrt{C_{ii}})\sim N(0,1)$. The fitted and residual Gaussian projections are orthogonal and hence independent, so this quantity is independent of $\nu s^2/{\sigma }^2\sim {\chi }_{\nu }^2$. Their ratio therefore has Student's t-distribution:If $t_{\nu ,1-\alpha /2}$ is its upper $1-\alpha /2$ quantile, rearranging its central probability event givesThis interval has exact coverage $1-\alpha$ under the given normal linear model, rather than merely large-sample coverage.

Let $\mathrm{RSS}=\Vert Y-X\hat{\theta }{\Vert }^2$. The usual unbiased error-variance estimator isIndeed the residual is the orthogonal projection of $ϵ$ onto the $(n-p)$-dimensional complement of the design column space, giving $\mathrm{RSS}/{\sigma }^2\sim {\chi }_{n-p}^2$ and expected RSS equal to $(n-p){\sigma }^2$. The maximum-likelihood estimator instead divides RSS by $n$; the unbiased divisor above is the one used for the exact t-interval in part (d).

Write $A=(X^{T}X{)}^{-1}{X}^T$. Since $AX=I$, the estimator is $\hat{\theta }=\theta +Aϵ$. ThereforeIts expectation proves unbiasedness. It is also jointly normal, being an affine transformation of the normal error vector.

The normal-error log-likelihood, for fixed variance, is a constant minus $\Vert Y-X\theta {\Vert }^2/(2{\sigma }^2)$. Differentiating the squared residual gives the normal equations $X^{T}X\hat{\theta }=X^{T}Y$. Since $X$ has full column rank, $X^{T}X$ is positive definite and the squared residual is strictly convex in $\theta$. Hence the unique minimizer, and thus the maximum-likelihood estimator, isProfiling over the unknown positive variance does not change the residual-minimizing value of $\theta$.

The generalized likelihood ratio compares the constrained maximum from part (b) with the unrestricted maximum from part (a). Taking minus twice its logarithm givesThe unrestricted $3\times 3$ model has $9-1=8$ free parameters; the independence model has $(3-1)+(3-1)=4$. Thus the asymptotic null distribution is ${\chi }_4^2$, with four degrees of freedom. The supplied value givesTherefore reject independence at the 5% level, but not at the 1% level. There is evidence of an association between the two classifications. The fitted expected counts are all about nine or larger, so the usual chi-squared approximation has no very small expected cells here.

Under the product constraint the log-likelihood separates:Maximizing the two simplex problems independently gives ${\hat{\alpha }}_i=n_{i.}/N$ and ${\hat{\beta }}_j=n_{.j}/N$. HenceThe fitted expected cell counts under independence are consequently $N{\hat{\theta }}_{ij}^0=n_{i.}{n}_{.j}/N$.

Ignoring the multinomial coefficient, the likelihood is $L(\theta )={\prod }_{i,j}{\theta }_{ij}^{n_{ij}}$. Maximize $\ell ={\sum }_{i,j}{n}_{ij}\log {\theta }_{ij}$ with $\sum {\theta }_{ij}=1$. A Lagrange multiplier gives $n_{ij}/{\theta }_{ij}=\lambda$; summing the resulting ${\theta }_{ij}=n_{ij}/\lambda$ gives $\lambda =N$. ThusBecause every count is positive, the log-likelihood is strictly concave on the interior simplex and this solution is its unique maximum.