Cauchy matrix explained

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

a _{ij} = { (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

x _{i} and y _{j} are elements of a field l{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 A = {{\prod ^{n} _{i =2} \prod ^{i -1} _{j =1} (x _{i-x} _{j)(y} _{j-y} _{i)}\over} {\prod ^{n} _{i =1} \prod ^{n} _{j =1} (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 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)} = (A(x))/(A ^{\prime(x} _{i)(x - x} _{i)}) and B _{i(x)} = (B(x))/(B ^{\prime(y} _{i)(x - y} _{i)}) , withA(x) = \prod ^{n} _{i =1} (x - x _{i)} and B(x) = \prod ^{n} _{i =1} (x - y _{i).}

Generalization

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

C _{ij} = (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

XC - CY = rs ^{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).

See also

• Toeplitz matrix
• Fay's trisecant identity

References

• Book: Cauchy, Augustin-Louis. 1841. Exercices d'analyse et de physique mathématique. Vol. 2 . fr . Bachelier .
• A. Gerasoulis . A fast algorithm for the multiplication of generalized Hilbert matrices with vectors . Mathematics of Computation . 1988 . 50 . 181 . 179–188 . 10.2307/2007921. 2007921 . free .
• I. Gohberg . T. Kailath . V. Olshevsky . Fast Gaussian elimination with partial pivoting for matrices with displacement structure . Mathematics of Computation . 1995 . 64 . 212 . 1557–1576 . 10.1090/s0025-5718-1995-1312096-x. 1995MaCom..64.1557G . free .
• P. G. Martinsson . M. Tygert . V. Rokhlin . An O(N log ^{2} N) algorithm for the inversion of general Toeplitz matrices . Computers & Mathematics with Applications . 2005 . 50 . 5–6 . 741–752 . 10.1016/j.camwa.2005.03.011.
• S. Schechter . On the inversion of certain matrices . Mathematical Tables and Other Aids to Computation . 1959 . 13 . 66 . 73–77 . 10.2307/2001955. 2001955 .
• TiIo Finck, Georg Heinig, and Karla Rost: "An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices", Linear Algebra and its Applications, vol.183 (1993), pp.179-191.
• Dario Fasino: "Orthogonal Cauchy-like matrices", Numerical Algorithms, vol.92 (2023), pp.619-637. url=https://doi.org/10.1007/s11075-022-01391-y .