Quadratic form minimization

Question

Suppose that $A$ is an $n\times k$ matrix with $n>k$. What vector $x\in \mathbb{R}^k$ minimizes the following quadratic form: $$ \begin{bmatrix} 1&x^{\top} \end{bmatrix}\begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top}\boldsymbol{1} & A^{\top}A \end{bmatrix}^{-1}\begin{bmatrix} 1 \\ x \end{bmatrix}? $$ Here $\boldsymbol{1}$ is a vector of ones. When $k=1$, it is easy to show that $x^*=A^{\top}1/n$ by explicitly inverting the matrix in the middle.

Answer 1

Let $a\in\mathbb{R},$ $b\in\mathbb{R}^k$ and $C\in\mathbb{R}^{k\times k}$ such that $$ \begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top} \boldsymbol{1} & A^{\top}A \end{bmatrix}^{-1} = \begin{bmatrix} a & b^{\top} \\ b & C \end{bmatrix} $$ Note that $C$ is symmetric and positive definite, because it is a principle submatrix of an invertible matrix that in turn is the product of a matrix and its transpose: $$ \begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top} \boldsymbol{1} & A^{\top}A \end{bmatrix} = \begin{bmatrix} \boldsymbol{1} & A \end{bmatrix}^{\top} \begin{bmatrix} \boldsymbol{1} & A \end{bmatrix} $$ Then $$ \begin{bmatrix} 1 \\ x\end{bmatrix}^{\top} \begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top} \boldsymbol{1} & A^{\top}A \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ x\end{bmatrix} = x^{\top}C x + x^{\top}b + b^{\top}x + a \\ \phantom{x} \\ = (Cx+b)^{\top}C^{-1}(Cx+b)-b^{\top}C^{-1}b+a $$ Therefore, without knowing $a$, $b$ and $C$, we know that we get the minimum if $Cx+b=0,$ this means, when $x=-C^{-1}b.$

We do not need the formula for the inverse of a block matrix to proceed. From the definition of $a,$ $b$ and $C$, we get $$ \begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top} \boldsymbol{1} & A^{\top}A \end{bmatrix} \begin{bmatrix} a & b^{\top} \\ b & C \end{bmatrix} = \begin{bmatrix} * & n b^{\top}+ \boldsymbol{1}^{\top}A C\\ * & * \end{bmatrix} = I $$ which means $\;n b^{\top}+ \boldsymbol{1}^{\top}A C = 0\;$ or $\;bn + CA^{\top}\boldsymbol{1} = 0\;$ or $\;\frac{1}{n}A^{\top}\boldsymbol{1} = -C^{-1}b = x.$

Answer 2

The inverse of the mid matrix is given by $$ \begin{bmatrix} n & \boldsymbol{1}^{\top}A \\ A^{\top}\boldsymbol{1} & A^{\top}A \end{bmatrix}^{-1}=\begin{bmatrix} (\boldsymbol{1}^{\top}M_A\boldsymbol{1})^{-1} & -\frac{\boldsymbol{1}^{\top}A}{n}(A^{\top}M_{\boldsymbol{1}}A)^{-1} \\ -(A^{\top}M_{\boldsymbol{1}}A)^{-1}\frac{A^{\top}\boldsymbol{1}}n &(A^{\top}M_{\boldsymbol{1}}A)^{-1} \end{bmatrix}, $$ where $M_B=I-B(B^{\top}B)^{-1}B$. Differentiating the quadratic form w.r.t. $x$, one gets the first order condition: $$ -2(A^{\top}M_{\boldsymbol{1}}A)^{-1}\frac{A^{\top}\boldsymbol{1}}{n} +2(A^{\top}M_{\boldsymbol{1}}A)^{-1} x^*=0. $$ Thus, $$ x^*=\frac{A^{\top}\boldsymbol{1}}{n}. $$