# Proving a symmetric Cauchy matrix is positive semidefinite

Let $$x_1,\cdots,x_n$$ be positive real numbers. Let $$A$$ be the $$n\times n$$ matrix whose $$i,j^\text{th}$$ entry is $$a_{ij}=\frac{1}{x_i+x_j}.$$ This is a Cauchy matrix.

I am trying to show that this matrix is positive semi-definite.

I have been given the following hint: Consider the matrix $$T=(t^{x_i+x_j})$$ where $$t>0$$. Use the fact that $$T$$ is positive semi-definite and that $$\frac{1}{x_i+x_j}=\int_0^1t^{x_i+x_j-1}dt.$$

I have managed to show that $$T$$ is positive semi-definite but I don't understand where to go from there or how to use the rest of the hint.

I would like another way to do this, preferably without involving integrals

Thank you

Hint (without integrals): Let $$X=\operatorname{diag}(x_1,x_2,\ldots,x_n)$$ and $$e$$ be the vector of all ones.

1. Prove that the Cauchy matrix $$C$$ satisfies the equation $$XC+CX=ee^T.$$
2. For any eigenvalue $$\lambda$$ of $$C$$ with $$Cv=\lambda v$$, pre-multiply the equation by $$v^T$$ and post-multiply by $$v$$. Conclude that $$\lambda\ge 0$$.
• It took me some time to realize that plainly $X=diag(x_1,x_2,...x_n)$.Very interesting property akin to Sylvester equation. Where did you see it ? – Jean Marie Jan 18 at 0:00
• @JeanMarie I have found the equation in wiki. – A.Γ. Jan 18 at 0:34
• May I drive your attention to the above question I just asked to user1551 in case you have a hint to give me ? Thanks. – Jean Marie Jan 18 at 0:53
• @JeanMarie It sounds as a good question, but it needs a good deal of thinking. Unfiortunately, right now I am 150% busy with other stuff at my university. I will try to think about it later on. Spontaneously, in the scattering theory and in the control theory the same analytic language with Hardy classes works well. Lyapunov/Sylvester equations are related to optimal trajectories in the linear case. Hamilton-Jacobi formalism, optimal control etc. I would start to search for similarities in this direction. Perhaps, the linear theory is enough. – A.Γ. Jan 18 at 16:17
• Thank you so much for paying attention to this issue, when you have time... – Jean Marie Jan 18 at 17:52

Regarding the hint: just as a sum of positive semidefinite operators is positive semidefinite, so is an integral of positive semidefinite operators positive semidefinite. So, since $$T(t)$$ is positive semidefinite for all $$t \geq 0$$, it follows that $$A = \int_0^1 T(t)\,dt$$ is positive semidefinite.

This paper hints at an interesting proof (without integrals) that when the numbers $$x_i$$ are distinct, $$A$$ is necessarily positive definite. We note that the determinant of a Cauchy matrix $$x_i$$ is given by $$\det(A) = \frac{\prod_{i,k,i>k}(x_i-x_k)^2}{\prod_{i,j = 1}^n(x_i+x_j)}.$$ Because all terms being multiplied are positive, $$\det(A) > 0$$. Since every principal submatrix of $$A$$ is itself a Cauchy matrix for some set of distinct $$x_i$$, we can conclude that the principal submatrices of $$A$$ also have positive determinant. By Sylvester's criterion, we can conclude that $$A$$ is positive definite.

For the more general statement with non-distinct $$x_i$$, it suffices to note that the limit of a sequence positive semidefinite matrices must itself be positive semidefinite.

• LOL @ the reference [5] in the Fiedler paper you linked :) – darij grinberg Jan 19 at 20:46
• Also, you can resolve the case of non-distinct $x_i$ using Sylvester's criterion for positive semidefinite matrices. You just need to remember that it requires all principal minors to be nonnegative (as opposed to just the ones in rows/columns $1,2,\ldots,k$). – darij grinberg Jan 19 at 20:51
• @darij titles are overrated – Omnomnomnom Jan 19 at 20:51
• @darij Also, I didn't realize that Sylvester's criterion could be extended in that way; that's a good trick to know. – Omnomnomnom Jan 19 at 20:53

There is also a proof that is similar in spirit to the hint you've mentioned. See exercise 1.6.3 (pp.24-25) of Bhatia, Positive Definite Matrices. The idea is that, instead of writing the Cauchy matrix as an integral of Gramians, we write it as an infinite sum of Gramians. More specifically, let $$0. Then $$\frac{1}{x_i+x_j-t} =\frac{t}{x_ix_j}\left(\frac{1}{1-\frac{(x_i-t)(x_j-t)}{x_ix_j}}\right) =\frac{t}{x_ix_j}\sum_{k=0}^\infty\left(\frac{(x_i-t)(x_j-t)}{x_ix_j}\right)^k.$$ Therefore, by setting $$\mathbf v_k=\left(\frac{(x_1-t)^k}{x_1^{k+1}},\,\frac{(x_2-t)^k}{x_2^{k+1}},\,\ldots,\,\frac{(x_n-t)^k}{x_n^{k+1}}\right)^\top$$, we see that $$\left(\frac{1}{x_i+x_j-t}\right)_{i,j\in\{1,\ldots,n\}} =t\sum_{k=0}^\infty \mathbf v_k\mathbf v_k^\top$$ is positive semidefinite. Now the result follows by passing the matrix on the LHS to the limit $$t\to0$$.

A big merit of the above proof is that it can be easily extended to prove the positive semidefiniteness of the power Cauchy matrix $$\left(\frac{1}{(x_i+x_j)^p}\right)_{i,j\in\{1,\ldots,n\}}$$ for any $$p>0$$.

• Here is a question of mine math.stackexchange.com/q/1885456 I asked a long time ago about a matrix similar to the one you use here. I have had no satisfactory any answer on it. Would you have some hints ? – Jean Marie Jan 18 at 0:51
• @JeanMarie Sorry, I have no idea. – user1551 Jan 18 at 14:18

Complementing A.Γ.'s answer, and rephrasing a bit:

Given $$a_1, a_2, \dots, a_n > 0$$, we build the $$n \times n$$ symmetric Cauchy matrix $$\rm C$$ whose entries are $$c_{ij} = \frac{1}{a_i + a_j}$$ Show that matrix $$\rm C$$ is positive semidefinite.

Henceforth, we shall assume that the given positive numbers are distinct, i.e., $$|\{a_1, a_2, \dots, a_n\}| = n$$

Let $${\rm A} := \mbox{diag} (a_1, a_2, \dots, a_n)$$. Note that $$\mathrm A \succ \mathrm O_n$$. Consider the following matrix equation

$${\rm A X + X A} = 1_n 1_n^\top$$

Multiplying both sides by $$-1$$, we obtain a Lyapunov matrix equation

$${\rm (-A) X + X (-A)} = - 1_n 1_n^\top$$

where matrix $$-\rm A$$ is stable (or Hurwitz) and the RHS is negative semidefinite. Since the pair $$(-\rm A, 1_n)$$ is controllable, the Lyapunov equation has the following unique, symmetric, positive definite solution

$$\rm X = \int_0^{\infty} e^{- \tau \mathrm A} 1_n 1_n^\top e^{- \tau \mathrm A} \,{\rm d} \tau = \int_0^{\infty} \begin{bmatrix} e^{- a_1 \tau}\\ e^{- a_2 \tau}\\ \vdots\\ e^{- a_n \tau}\end{bmatrix} \begin{bmatrix} e^{- a_1 \tau}\\ e^{- a_2 \tau}\\ \vdots\\ e^{- a_n \tau} \end{bmatrix}^\top \, {\rm d} \tau = \cdots = \rm C$$

because

$$\displaystyle\int_0^{\infty} e^{-(a_i + a_j) \tau} \,{\rm d} \tau = \frac{1}{a_i + a_j}$$

Therefore, we conclude that $$\rm C$$ is positive definite.

### Alternative solution

Vectorizing both sides of the Lyapunov equation,

$$\left( \mathrm I_n \otimes \mathrm A + \mathrm A \otimes \mathrm I_n \right) \mbox{vec} (\mathrm X) = 1_n \otimes 1_n$$

or,

$$\begin{bmatrix} \mathrm A + a_1 \mathrm I_n & & & \\ & \mathrm A + a_2 \mathrm I_n & & \\ & & \ddots & \\ & & & \mathrm A + a_n \mathrm I_n\end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots\\ \mathrm x_n\end{bmatrix} = \begin{bmatrix} 1_n\\ 1_n\\ \vdots\\ 1_n\end{bmatrix}$$

where $$\mathrm x_i$$ is the $$i$$-th column of $$\rm X$$. Solving for $$\mathrm x_i$$,

$$\mathrm x_i = \begin{bmatrix} \frac{1}{a_1 + a_i}\\ \frac{1}{a_2 + a_i}\\ \vdots\\ \frac{1}{a_n + a_i}\end{bmatrix}$$

which is the $$i$$-th column of Cauchy matrix $$\rm C$$. Therefore, the unique, symmetric, positive definite solution of the Lyapunov equation is $$\rm C$$.

The controllability matrix corresponding to the pair $$(-\rm A, 1_n)$$ is
$$\begin{bmatrix} | & | & & |\\ 1_n & -\mathrm A 1_n & \dots & (-1)^{n-1} \mathrm A^{n-1} 1_n\\ | & | & & |\end{bmatrix}$$
which is a square $$n \times n$$ Vandermonde matrix whose columns have been multiplied by $$\pm 1$$, which does not affect its rank. Since we assumed that the given $$a_1, a_2, \dots, a_n$$ are distinct, the Vandermonde matrix has full rank and, thus, the pair $$(-\rm A, 1_n)$$ is controllable.