Let $b\in[0,1]^n$, with $n\in\mathcal{N}^*$. Consider the symmetric matrix $A=(a_{i,j})$, defined by
$$
a_{i,j}=\begin{cases}\min\lbrace b_i,…,b_j\rbrace &\mbox{if } i<j\\
\min \lbrace b_j,…,b_i\rbrace &\mbox{if } j\leq i\end{cases}
$$
Is $A$ always positive semidefinite?
For instance, the matrix generated by the vector $[0. 1, 0.2, 0.3]$ is
$$
\left(\begin{matrix}
0.1 & 0.1 & 0.1 \\
0.1 & 0.2 & 0.2 \\
0.1 & 0.2 & 0.3 \\
\end{matrix}\right)
$$
while the one generated by the vector $[0. 2, 0.1, 0.3]$ is
$$
\left(\begin{matrix}
0.2 & 0.1 & 0.1 \\
0.1 & 0.1 & 0.1 \\
0.1 & 0.1 & 0.3 \\
\end{matrix}\right)\text{.}$$
So far, I have only managed to show that $A$ is positive semidefinite when $b$ is sorted (either in increasing or decreasing order). The proof is by induction:
The statement clearly holds if $n=1$.
Induction step:
Let's denote $A(b)$ the matrix generated when following the procedure described above with a vector $b$.
Let $n\in\mathcal{N}^*$. Assume that all the matrices $M\in\lbrace A(b), b\in [0,1]^{i}, i\in\lbrace 1,…n\rbrace, b \mbox{ sorted}\rbrace$ are positive semidefinite.
Consider then a sorted vector $b$ with $n+1$ elements and apply Sylvester's criterion: all the sub-matrices of $A(b)$ corresponding to principal minors belong to $\lbrace A(b), b\in [0,1]^{i}, i\in\lbrace 1,…n\rbrace, b \mbox{ sorted}\rbrace$, so the result holds.
I have also tried to generate counter-examples in the case where $b$ is not sorted, but unsuccessfully.
Best Answer
Yes, it is positive semidefinite. This can be easily proved by mathematical induction on $n$.
To stress its size as well as its dependence on the parameters $b_i$s, let us denote the matrix generated by $(b_1,\ldots,b_n)\in[0,1]^n$ as described in your question as $A(b_1,\ldots,b_n)$. In the inductive step, let $b_i=\min(b_1,\ldots,b_n)$. Then \begin{aligned} A(b_1,\ldots,b_n) &=\left[\begin{array}{c|c|c} A(b_1,\,\ldots,\,b_{i-1}) &\begin{matrix}b_i\\ \vdots\\ b_i\end{matrix} &\begin{matrix}b_i&\cdots&b_i\\ \vdots&&\vdots\\ b_i&\cdots&b_i\end{matrix}\\ \hline \begin{matrix}b_i&\cdots&b_i\end{matrix}&b_i&\begin{matrix}b_i&\cdots&b_i\end{matrix}\\ \hline \begin{matrix}b_i&\cdots&b_i\\ \vdots&&\vdots\\ b_i&\cdots&b_i\end{matrix} &\begin{matrix}b_i\\ \vdots\\ b_i\end{matrix} &A(b_{i+1},\,\ldots,\,b_n) \end{array}\right]\\ &=\left[\begin{array}{c|c|c} A(b_1-b_i,\,\ldots,b_{i-1}-b_i)&0&0\\ \hline 0&0&0\\ \hline 0&0&A(b_{i+1}-b_i,\,\ldots,\,b_n-b_i) \end{array}\right]+b_iE \end{aligned} where $E$ denotes the all-one matrix. Since $b_k-b_i\in[0,1]$ for every $k$, we see that $A(b_1,\ldots,b_n)$ is positive semidefinite, by induction assumption.