About positive semidefiniteness of one matrix It is not clear how to prove that the matrix $(\min(i,j))_{i,j=1,\dots,n}$ is (or is not) positive semidefinite. There are some facts from Horn and Johnson's book Matrix Analysis: if $A \in M_n$ is positive semidefinite, then $a_{ii}a_{jj} \ge a_{ij}^2, i,j=1,2,\dots, n$ (source). It seems that this condition is not enough for the matrix to be positive semidefinite. Are there any techniques to check that all eigenvalues of the matrix are positive, or that the minor determinants are non-negative?
 A: From a comment on J.M.'s answer - I regard this as essentially equivalent to his answer - but:
Consider an arbitrary ${\bf x}=(x_1, x_2 \cdots x_n)^T$. Now,
$$ \sum_{i=1}^N \left(\sum_{j=i}^N x_j\right)^2 \ge0$$
with equality iff ${\bf x}={\bf 0}$. But expanding the sums, and computing the coefficient for the $x_i x_j$ term, we get that:


*

*when  $i=j$: the term $x_i^2$ appears $i$ times.

*when $i\ne j$: the term $x_i x_j$ appears $2 \min(i,j)$ times.
Then, the above sum can be written as
$$ \sum_{i=1}^N \sum_{j=1}^N \min(i,j) x_i x_j = {\bf x^T A x} $$
hence, because this is positive, ${\bf A}$ is (strictly) positive definite.
A: Another alternative solution: it can be shown that the inverse of the min-matrix is the perturbed Toeplitz tridiagonal matrix
$$\begin{pmatrix}2&-1&&&\\-1&2&-1&&\\&-1&\ddots&\ddots&\\&&\ddots&2&-1\\&&&-1&1\end{pmatrix}$$
whose characteristic polynomial is
$$(-1)^n\left((x-1)U_{n-1}\left(\frac{x-2}{2}\right)-U_{n-2}\left(\frac{x-2}{2}\right)\right)$$
(where $U_n(x)$ is the Chebyshev polynomial of the second kind), and has the eigenvalues
$$\mu_k=2+2\cos\left(\frac{2k\pi}{2n+1}\right),\qquad k=1\dots n$$
Thus, the eigenvalues of the min-matrix are the reciprocals of the $\mu_k$,
$$\lambda_k=\frac14\sec^2\left(\frac{k\pi}{2n+1}\right)$$
and these are easily seen to be positive, thus showing that the min-matrix is positive definite.
A: The matrix of all ones is positive semidefinite (it is $n$ times an orthogonal projection).  If $A$ is positive semidefinite, then so is $\begin{bmatrix}0&0\\0&A\end{bmatrix}$.  Thus your matrix is a sum of $n$ positive semidefinite matrices, and therefore is positive semidefinite. Since it is invertible (for each $k\in\{1,2,\ldots,n\}$, the $k^\text{th}$ row is not in the span of the first $k-1$ rows, because the $k^\text{th}$ and $(k-1)^\text{st}$ entries differ), it is even positive definite.

More explicitly, the min matrix is $P_1+P_2+\cdots+P_n$, where $P_k$ has an $(n-k+1)\times (n-k+1)$ block of $1$s in the bottom right, and the rest $0s$.  Note that each $P_k$ is symmetric, and $P_k=\dfrac{1}{n-k+1}P_k^2$, which makes it easy to check that $P_k$ is positive semidefinite.  
A: Minor determinants are computable: denote as $A_n$ the matrix we are dealing with. Note that the $j$-th minor of $A_n$ is $A_j$. So we have to show that $\det A_j > 0$ for all $j$. To see that, consider the last line of the matrix, and do $L_j\leftarrow L_j-L_{j-1}$. It shows that $\det A_j=\det A_{j-1}$, so $\det A_j=1$ for all integer $j$, and by Sylvester's criterion we are done. 
A: To expand on my comment: we have the theorem "a matrix is symmetric positive definite if and only if it possesses a Cholesky decomposition". That is, any symmetric positive definite matrix $\mathbf A$ possesses a factorization $\mathbf A=\mathbf G\mathbf G^\top$, where the lower triangular matrix $\mathbf G$ is called a Cholesky triangle.
Now, I claim that if $a_{ij}=\min(i,j)$, then $g_{ij}=[i\geq j]$, where $[p]$ is an Iverson bracket, equal to $1$ if $p$ is true, and $0$ if $p$ is false. As an example ($n=6$),
$$\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 1 \\1 & 2 & 2 & 2 & 2 & 2 \\1 & 2 & 3 & 3 & 3 & 3 \\1 & 2 & 3 & 4 & 4 & 4 \\1 & 2 & 3 & 4 & 5 & 5 \\1 & 2 & 3 & 4 & 5 & 6\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 \\1 & 1 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}\cdot\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 \\1 & 1 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}^\top$$
This is equivalent to proving that
$$\min(i,j)=\sum_{k=1}^n [i\geq k][k\leq j]$$
or, since $[p][q]=[p\text{ and }q]$,
$$\min(i,j)=\sum_{k=1}^n [i\geq k\text{ and }j\geq k]$$
and that the identity indeed holds is now a bit easier to see.
