# Is it possible to prove that the Cauchy matrix has $O(\log n)$ rank bound for off diagonal blocks?

Suppose we have a $n\times n$ Cauchy matrix of which the $ij$-th entry is given by: $$A_{ij} = \frac{1}{a_i - b_j}$$ the assumption is that the distance between $\{a_i\}$ and $\{b_j\}$ is greater some positive constant, for example: $$a_k = e^{i\frac{(2k+1)\pi}{n}}, \quad b_k = e^{i\frac{2k\pi}{n}}$$ then we have $\displaystyle \min_{i,j} |a_i - b_j|\geq O(\sin(\pi/n))$, and we want to prove something like the off diagonal entries can be represented by: $$\frac{1}{a_i - b_j} = \sum^{O(\log(n))}_{k=1} C_k + O(\varepsilon)$$ Is this possible? or there is another type of rank bound for Cauchy matrix?

-
 Does this question relate to low-separation rank approximations of operators, like the work done by Beylkin and Mohlenkamp? – Geoff Oxberry♦ Feb 14 '12 at 20:02 Would this question more suitable for the math.stackexchange.com site? It seems more of a theoretical question in linear algebra rather than a computational one... – Paul♦ Feb 14 '12 at 20:15 @Paul: The thought crossed my mind. First, I want to see if a connection to numerical methods can be made before we discuss migrating. – Geoff Oxberry♦ Feb 14 '12 at 20:26 @Paul Thanks for the comment, the Cauchy or Cauchy like matrices arise from various computational problems, such as solving displacement equation, and computationally, as Jack Poulson said, Ming Gu claimed the bound is $O(\log(n))$ but he never proved it, I am just curious about the theory behind this numerical linear algebra problem. – Shuhao Cao Feb 14 '12 at 20:46

Ming Gu gave a talk which uses Hierarchically Semi-Separable (HSS) matrices to compress the Cauchy-like matrices which arise from a Fourier transform of Toeplitz matrices, resulting in an $O(n \log n)$ approximate solution, but I'm not certain if the compression technique will work for general Cauchy matrices.
 Ming Gu also used this property of off-diagonal blocks having a $O(\log(n))$ rank to get that $O(n \log(n))$ complexity, rather than using the displacement rank. Here I am just curious how did he get this $O(\log(n))$ rank theoretically, but he never mentioned any proof in his paper, merely a numerical result. – Shuhao Cao Feb 14 '12 at 20:52 @Jon: If you look at the seventh slide of his talk, you can see that there is a very special structure to the Cauchy matrix: $a_i = \omega^{2i}$, and $b_j = \omega^{2i+1}$, indexing from zero. – Jack Poulson Feb 14 '12 at 20:56 The Cauchy matrix is the same matrix as I pointed out there. I also tested some random Cauchy matrix, and found that the singular value decays very quickly for off-diagonal block part. Ming Gu chose this matrix because he used 1 and -1 when he transformed the toeplitz matrix into Cauchy-like matrix using the displacement equation. By doing this he could maximize the minimal value of the denominators of the entries for the Cauchy matrix, and enhance the stability of the numerical computation. – Shuhao Cao Feb 14 '12 at 21:13 @Jon: Ah, good point. $\omega := \exp(i \pi / n)$. I would have to think more; maybe plotting the singular vectors would help... – Jack Poulson Feb 14 '12 at 21:21