Cauchy matrix

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

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

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

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

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

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

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{𝐀}=\frac{{\displaystyle \prod _{i=2}^n}{\displaystyle \prod _{j=1}^{i-1}}(x_i-x_j)(y_j-y_i)}{{\displaystyle \prod _{i=1}^n}{\displaystyle \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⁻¹ = B = [b_ij] is given by

${\displaystyle 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 ${\displaystyle (x_i)}$ and ${\displaystyle (y_j)}$, respectively. That is,

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

with

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

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(x_i), Y=diag(y_i), one sees that both Cauchy and Cauchy-like matrices satisfy the displacement equation

${\displaystyle \mathbf{𝐗}\mathbf{𝐂}-\mathbf{𝐂}\mathbf{𝐘}=r{s}^{\mathrm{T}}}$

(with ${\displaystyle r=s=(1,1,\dots ,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).

• Toeplitz matrix
• Fay's trisecant identity

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Cauchy matrix. Read more