About positive semidefiniteness of one matrix

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.