Cauchy matrix
# Cauchy matrix

In mathematics, a Cauchy matrix, named after Augustin-Louis Cauchy, is an m×n matrix with elements $a_{ij}$ in the form

    $a_{ij}={\frac {1}{x_{i}-y_{j}}};\quad x_{i}-y_{j}\neq 0,\quad 1\leq i\leq m,\quad 1\leq j\leq n$

where $x_{i}$ and $y_{j}$ are elements of a field ${\mathcal {F}}$, and $(x_{i})$ and $(y_{j})$ are injective sequences (they contain distinct elements).

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

    $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 $(x_{i})$ and $(y_{j})$. If the sequences were not injective, the determinant would vanish, and tends to infinity if some $x_{i}$ tends to $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

    $\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 = $[b_{ij}]$ is given by

    $b_{ij}=(x_{j}-y_{i})A_{j}(y_{i})B_{i}(x_{j})\,$     (Schechter 1959, Theorem 1)

where $A_i(x)$ and $B_i(x)$ are the Lagrange polynomials for $(x_{i})$ and $(y_{j})$, respectively. That is,

    $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

    $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

    $C_{ij}={\frac {r_{i}s_{j}}{x_{i}-y_{j}}}.$

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

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

(with $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 $O(n\log n)$ ops (e.g. the fast multipole method),
* (pivoted) LU factorization with $O(n^{2})$ ops (GKO algorithm), and thus linear system solving,
* approximated or unstable algorithms for linear system solving in $O(n\log ^{2}n)$.

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

