I want to prove (or disprove) the convexity of a function $f:\mathbb{R}^n \times \mathbb{R}^n \rightarrow\mathbb{R}$ defined as
$$f(x,y) = \frac{1}{2}\|x-y\|_2^2.$$
My attempt: We know that
$$f \text{ is convex} \iff \text{Hessian matrix is positive semi-definite}.$$
Hence, we want to show
$$ H =
\begin{bmatrix}
\frac{\partial^2f}{\partial x_1^2} & \frac{\partial^2f}{\partial x_1\partial x_2} & \dots & \frac{\partial^2f}{\partial x_1\partial x_n} & \frac{\partial^2f}{\partial x_1\partial y_1} & \dots & \frac{\partial^2f}{\partial x_1\partial y_n}\\
\frac{\partial^2f}{\partial x_2 \partial x_1} & \frac{\partial^2f}{\partial x_2^2} & \dots & \frac{\partial^2f}{\partial x_2\partial x_n} & \frac{\partial^2f}{\partial x_2\partial y_1} & \dots & \frac{\partial^2f}{\partial x_2\partial y_n}\\
\vdots & \vdots & \ddots\\
\frac{\partial^2f}{\partial x_n\partial x_1} & \frac{\partial^2f}{\partial x_n\partial x_2} && \frac{\partial^2f}{\partial x_n^2}\\
\frac{\partial^2f}{\partial y_1\partial x_1} & \frac{\partial^2f}{\partial y_1\partial x_2} &&& \frac{\partial^2f}{\partial y_1^2}\\
\vdots & \vdots &&&& \ddots\\
\frac{\partial^2f}{\partial y_n\partial x_1} & \frac{\partial^2f}{\partial y_n\partial x_2} &&&&& \frac{\partial^2f}{\partial y_n^2}
\end{bmatrix}
$$
is positive semi-definite. Here, I am constructing $H$ by treating the function as a multivariate function in $\mathbb{R}$ like so:
$$f(x_1, \dots, x_n, y_1, \dots, y_n) = \frac{1}{2}\sum_{i=1}^{n}(x_i-y_i)^2.$$
Then, I look at each possible element of the Hessian matrix:
$$\frac{\partial^2 f}{\partial x_i \partial x_j} = \delta_{ij}$$
$$\frac{\partial^2 f}{\partial x_i \partial y_j} = \frac{\partial^2 f}{\partial y_i \partial x_j} = -\delta_{ij}$$
$$\frac{\partial^2 f}{\partial y_i \partial y_j} = \delta_{ij}$$
where $\delta_{ij} := \begin{cases}1,\ \ i=j\\0,\ \ i\ne j\end{cases}$.
This means our Hessian will be
$$
H =
\begin{bmatrix}
I^{n\times n} & -I^{n \times n}\\
-I^{n \times n} & I^{n\times n}
\end{bmatrix}
$$
where $I^{n\times n}$ is the $n\times n$ identity matrix.
Now, all I need to do is determine if $H$ is positive semi-definite. That is, if
$$x^THx \ge 0, \ \ \forall x\in \mathbb{R}^n.$$
By playing around with small examples of $H$ I believe the general formula for $x^THx$ is $$x^THx = \sum_{i=1}^{n} x_i^2 - 2\sum_{j=1}^{n/2} x_ix_{i+n/2}.$$ (although I don't know how to show this). An example here.
From here, I use the fact that $x_i^2 + x_j^2 > 2x_ix_j$ to claim $$x^THx \ge 0$$ and hence $H$ is positive semidefinite. Thus, $f$ is convex.
Is this reasoning correct? How might I prove the determinant is what I claim?
Looks good.
In the verification, you could have used the stacked vector $\pmatrix{x\\y}$, then $$ \pmatrix{x\\y}^TH\pmatrix{x\\y} = x^Tx - 2x^Ty + y^Ty = \|x-y\|_2^2 \ge0. $$
This task gets easier, if one realizes that $f$ is the composition of a linear map $\pmatrix{I\\-I}$ with the convex function $\frac12\|\cdot\|_2^2$. Such a composition is always convex.