3
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Jean Marie Jan 18 at 0:00
  • 1
    $\begingroup$ @JeanMarie I have found the equation in wiki. $\endgroup$ – A.Γ. Jan 18 at 0:34
  • $\begingroup$ May I drive your attention to the above question I just asked to user1551 in case you have a hint to give me ? Thanks. $\endgroup$ – Jean Marie Jan 18 at 0:53
  • 1
    $\begingroup$ @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. $\endgroup$ – A.Γ. Jan 18 at 16:17
  • $\begingroup$ Thank you so much for paying attention to this issue, when you have time... $\endgroup$ – Jean Marie Jan 18 at 17:52
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ LOL @ the reference [5] in the Fiedler paper you linked :) $\endgroup$ – darij grinberg Jan 19 at 20:46
  • $\begingroup$ 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$). $\endgroup$ – darij grinberg Jan 19 at 20:51
  • $\begingroup$ @darij titles are overrated $\endgroup$ – Omnomnomnom Jan 19 at 20:51
  • $\begingroup$ @darij Also, I didn't realize that Sylvester's criterion could be extended in that way; that's a good trick to know. $\endgroup$ – Omnomnomnom Jan 19 at 20:53
3
$\begingroup$

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<t<\min_ix_i$. 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$.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Jean Marie Jan 18 at 0:51
  • 1
    $\begingroup$ @JeanMarie Sorry, I have no idea. $\endgroup$ – user1551 Jan 18 at 14:18
2
$\begingroup$

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$.


Addendum

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.

$\endgroup$
  • 1
    $\begingroup$ Very interesting ... $\endgroup$ – Jean Marie Jan 19 at 17:51
  • 1
    $\begingroup$ Details can be found here. $\endgroup$ – Rodrigo de Azevedo Jan 19 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.