Prove: Least Squares Prediction Equation Contains Mean Point $\newcommand{\szdp}[1]{\!\left(#1\right)}
\newcommand{\szdb}[1]{\!\left[#1\right]}$
Problem Statement: Show that the least squares prediction equation
$$\hat{y}=\hat\beta_0+\hat\beta_1x_1+\cdots+\hat\beta_kx_k$$
passes through the point $(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_k,\overline{y}).$
Note: This is Exercise 11.81 in Mathematical Statistics with Applications, 5th Ed., by Wackerly, Mendenhall, and Scheaffer.
My Work So Far: What we need to do is show that
$$\overline{y}=\hat\beta_0+\hat\beta_1\overline{x}_1+\hat\beta_2\overline{x}_2
+\cdots+\hat\beta_k\overline{x}_k.$$
Now if we set up the matrices
\begin{align*}
\mathbf{x}&=\szdb{
\begin{matrix}
1&x_{11}&x_{21}&\cdots&x_{k1}\\
1&x_{12}&x_{22}&\cdots&x_{k2}\\
\vdots  &\vdots &\vdots &\ddots &\vdots\\
1&x_{1n}&x_{2n}&\cdots&x_{kn}
\end{matrix}}\\
\mathbf{a}&=\szdb{
\begin{matrix}
1\\ \overline{x}_1\\ \overline{x}_2\\ \vdots \\ \overline{x}_k
\end{matrix}
}\\
\mathbf{y}&=\szdb{
\begin{matrix}
y_1\\y_2\\ \vdots \\ y_n
\end{matrix}},
\end{align*}
then we know
${\hat\beta}=(\mathbf{x}^T\mathbf{x})^{-1}\mathbf{x}^T\mathbf{y},$
and we are asked to prove
$\overline{y}=\mathbf{a}^T\hat\beta.$ Here $n$ is the number of data points, and $k$ is the number of features.
My Questions: I have no idea where to go from here, or even whether this is the right approach to begin. What's a hint?

One place to start would be to replace your $a^T$ vector with $\frac1n$ times a row vector of $n$ 1's times $x$.  This is just the matrix version of finding the means ($\bar{x}$) of the columns.  When you substitute that (and $\hat{\beta}$) into your last equation you will have a piece that computes means times the hat matrix times the y vector.  Look up the properties of the hat matrix and/or remember that $y_i = \hat{y_i} + \hat\epsilon_i$ and remember or look up what the mean of the observed residuals is to continue.
