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?

-
The quickest proof I know is that the "min-matrix" has a Cholesky decomposition where the triangular entries are all $1$s... – J. M. Jul 9 '12 at 17:48
True, that condition (as presented) is a necessary condition for the matrix to be PSD, but not a sufficient condition. That is, we know the condition is true if the matrix is PSD, but knowing that the condition is true isn't (as presented) enough for us to conclude that the matrix is PSD. We can conclude that if the condition fails, then the matrix is not PSD (contrapositive of the fact). – Cameron Buie Jul 9 '12 at 17:50
That the given condition is necessary but not sufficient can be readily seen by noting that $a_{ii} a_{jj} - a_{ij}^2$ is just a 2 x 2 minor determinant. – leonbloy Jul 9 '12 at 19:00

5 Answers

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.

-
Or, equivalently, see that $0 \le \sum_{i=1}^N (\sum_{j=i}^N x_j)^2 = \sum_{i=1}^N \sum_{j=1}^N x_i x_j \min(i,j)= {\bf x^T A x}$ for any ${\bf x}$. – leonbloy Jul 9 '12 at 19:24

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.

-

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.

-

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.

-

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.

-