How to prove this matrix is positive semi-definite?

An $ntimes n$ matrix whose $r,s$-th entry is $a_{r,s}=cos(t_r-t_s)$, for some constants $t_1,ldots,t_n$ is positive semidefinite, in the sense that if $zinmathbb C^n$, then $sum_{r,s}a_{r,s}z_rbar z_sge 0$. This can be seen by recognizing $cos t$ as the characteristic function of a random variable, namely $cos t=E[e^{itX}]$, where $X=pm 1$ with probabilities $1/2$ and $1/2$. (Which is just a complicated way of saying $cos t=(e^{it}+e^{-it})/2$.) One can check this by appealing to Bochner's theorem, or directly: $$sum_{r,s}cos(t_r-t_s)z_rbar z_s=sum_{r,s}E[e^{i(t_r-t_s)X}] z_rbar z_s\=sum_{r,s}E[e^{it_rX}z_re^{-it_sX}bar z_s]=Eleft[ left|sum_r e^{it_rX}z_rright|^2right] ge 0.$$

The OP's matrix is the sum of such a matrix and of a Gram matrix, and hence is psd as well.