# Cauchy matrix

In mathematics, a Cauchy matrix, named after Augustin-Louis Cauchy, is an m×n matrix with elements aij in the form

$\displaystyle{ a_{ij}={\frac{1}{x_i-y_j}};\quad x_i-y_j\neq 0,\quad 1 \le i \le m,\quad 1 \le j \le n }$

where $\displaystyle{ x_i }$ and $\displaystyle{ y_j }$ are elements of a field $\displaystyle{ \mathcal{F} }$, and $\displaystyle{ (x_i) }$ and $\displaystyle{ (y_j) }$ are injective sequences (they contain distinct elements).

The Hilbert matrix is a special case of the Cauchy matrix, where

$\displaystyle{ x_i-y_j = i+j-1. \; }$

Every submatrix of a Cauchy matrix is itself a Cauchy matrix.

## Cauchy determinants

The determinant of a Cauchy matrix is clearly a rational fraction in the parameters $\displaystyle{ (x_i) }$ and $\displaystyle{ (y_j) }$. If the sequences were not injective, the determinant would vanish, and tends to infinity if some $\displaystyle{ x_i }$ tends to $\displaystyle{ y_j }$. A subset of its zeros and poles are thus known. The fact is that there are no more zeros and poles:

The determinant of a square Cauchy matrix A is known as a Cauchy determinant and can be given explicitly as

$\displaystyle{ \det \mathbf{A}={{\prod_{i=2}^n \prod_{j=1}^{i-1} (x_i-x_j)(y_j-y_i)}\over {\prod_{i=1}^n \prod_{j=1}^n (x_i-y_j)}} }$     (Schechter 1959, eqn 4; Cauchy 1841, p. 154, eqn. 10).

It is always nonzero, and thus all square Cauchy matrices are invertible. The inverse A−1 = B = [bij] is given by

$\displaystyle{ b_{ij} = (x_j - y_i) A_j(y_i) B_i(x_j) \, }$     (Schechter 1959, Theorem 1)

where Ai(x) and Bi(x) are the Lagrange polynomials for $\displaystyle{ (x_i) }$ and $\displaystyle{ (y_j) }$, respectively. That is,

$\displaystyle{ A_i(x) = \frac{A(x)}{A^\prime(x_i)(x-x_i)} \quad\text{and}\quad B_i(x) = \frac{B(x)}{B^\prime(y_i)(x-y_i)}, }$

with

$\displaystyle{ A(x) = \prod_{i=1}^n (x-x_i) \quad\text{and}\quad B(x) = \prod_{i=1}^n (x-y_i). }$

## Generalization

A matrix C is called Cauchy-like if it is of the form

$\displaystyle{ C_{ij}=\frac{r_i s_j}{x_i-y_j}. }$

Defining X=diag(xi), Y=diag(yi), one sees that both Cauchy and Cauchy-like matrices satisfy the displacement equation

$\displaystyle{ \mathbf{XC}-\mathbf{CY}=rs^\mathrm{T} }$

(with $\displaystyle{ r=s=(1,1,\ldots,1) }$ for the Cauchy one). Hence Cauchy-like matrices have a common displacement structure, which can be exploited while working with the matrix. For example, there are known algorithms in literature for

• approximate Cauchy matrix-vector multiplication with $\displaystyle{ O(n \log n) }$ ops (e.g. the fast multipole method),
• (pivoted) LU factorization with $\displaystyle{ O(n^2) }$ ops (GKO algorithm), and thus linear system solving,
• approximated or unstable algorithms for linear system solving in $\displaystyle{ O(n \log^2 n) }$.

Here $\displaystyle{ n }$ denotes the size of the matrix (one usually deals with square matrices, though all algorithms can be easily generalized to rectangular matrices).