Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Cauchy matrix
Matrix with 1/(x_i-y_j) entries

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

a i j = 1 x i − y j ; x i − y j ≠ 0 , 1 ≤ i ≤ m , 1 ≤ j ≤ n {\displaystyle 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 {\displaystyle x_{i}} and y j {\displaystyle y_{j}} are elements of a field F {\displaystyle {\mathcal {F}}} , and ( x i ) {\displaystyle (x_{i})} and ( y j ) {\displaystyle (y_{j})} are injective sequences (they contain distinct elements).

We don't have any images related to Cauchy matrix yet.
We don't have any YouTube videos related to Cauchy matrix yet.
We don't have any PDF documents related to Cauchy matrix yet.
We don't have any Books related to Cauchy matrix yet.
We don't have any archived web articles related to Cauchy matrix yet.

Properties

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

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

x i − y j = i + j − 1. {\displaystyle x_{i}-y_{j}=i+j-1.\;}

Cauchy determinants

The determinant of a Cauchy matrix is clearly a rational fraction in the parameters ( x i ) {\displaystyle (x_{i})} and ( y j ) {\displaystyle (y_{j})} . If the sequences were not injective, the determinant would vanish, and tends to infinity if some x i {\displaystyle x_{i}} tends to y j {\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

det A = ∏ i = 2 n ∏ j = 1 i − 1 ( x i − x j ) ( y j − y i ) ∏ i = 1 n ∏ j = 1 n ( x i − y j ) {\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

b i j = ( x j − y i ) A j ( y i ) B i ( x j ) {\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 ( x i ) {\displaystyle (x_{i})} and ( y j ) {\displaystyle (y_{j})} , respectively. That is,

A i ( x ) = A ( x ) A ′ ( x i ) ( x − x i ) and B i ( x ) = B ( x ) B ′ ( y i ) ( x − y i ) , {\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

A ( x ) = ∏ i = 1 n ( x − x i ) and B ( x ) = ∏ i = 1 n ( x − y i ) . {\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

C i j = r i s j x i − y j . {\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

X C − C Y = r s T {\displaystyle \mathbf {XC} -\mathbf {CY} =rs^{\mathrm {T} }}

(with r = s = ( 1 , 1 , … , 1 ) {\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 O ( n log ⁡ n ) {\displaystyle O(n\log n)} ops (e.g. the fast multipole method),
  • (pivoted) LU factorization with O ( n 2 ) {\displaystyle 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 ) {\displaystyle O(n\log ^{2}n)} .

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

See also