Show that the following matrix is positive semidefinite

Question

Problem: Let $0\leq a_1 \leq a_2 \leq \dots \leq a_n < \infty$. Show that the $n\times n$ matrix
\begin{align*}
A =
\begin{pmatrix}
a_1 & a_1 & \dots & a_1\\
a_1 & a_2 & \dots & a_2\\
\vdots & \vdots & \ddots & \vdots\\
a_1 & a_2 & \dots & a_n
\end{pmatrix}
\end{align*}
is positive semidefinite. (If it is not clear, the element in position $(i,j)$ of $A$ is $a_{\min\{i,j\}}$.)

My thoughts: I tried to use the definition of the determinant of a matrix in term of the determinants of submatrices but I did not get very far.

Answer 1

You can write $A$ as the sum of rank 1 matrices: $$ \begin{pmatrix}a_1 & \dots & a_1 \\ \vdots & \ddots \\ a_1& & a_1 \end{pmatrix} + \begin{pmatrix}0 & 0 & \dots & 0 \\ 0 & a_2 - a_1 & \dots & a_2-a_1 \\ \vdots & \vdots & \ddots \\ 0 & a_2 - a_1& & a_2 - a_1 \end{pmatrix} + \text{etc} $$ The $i^{th}$ term has eigenvector $(0, 0, \ldots, 0, 1, 1, \ldots 1)$, where the number of zeros is $i-1$ and eigenvalue $(n+1-i)(a_i - a_{i-i}) \geq 0$ (with $a_0=0$). Since the matrices have rank $1$, the remaining eigenvalues are $0$.

The sum of positive semidefinite matrices is positive semidefinite.