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};x_i-y_j\ne 0,1\le i\le m,1\le j\le n$

where $x_i$ and $y_j$ are elements of a field ${ℱ}$, 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{𝐀}=\frac{\prod _{i=2}^n\prod _{j=1}^{i-1}(x_i-x_j)(y_j-y_i)}{\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⁻¹ = 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)}\text{and}{B}_i(x)=\frac{B(x)}{B^{\prime }(y_i)(x-y_i)},$

with

$A(x)=\prod _{i=1}^n(x-x_i)\text{and}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{𝐗}\mathbf{𝐂}-\mathbf{𝐂}\mathbf{𝐘}=r{s}^{\mathrm{T}}$

(with $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 $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

• Cauchy, Augustin-Louis (1841) (in fr). Exercices d'analyse et de physique mathématique. Vol. 2. Bachelier. https://books.google.com/books?id=DRg-AQAAIAAJ. 
• A. Gerasoulis (1988). "A fast algorithm for the multiplication of generalized Hilbert matrices with vectors". Mathematics of Computation 50 (181): 179–188. doi:10.2307/2007921. https://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917825-9/S0025-5718-1988-0917825-9.pdf. 
• I. Gohberg; T. Kailath; V. Olshevsky (1995). "Fast Gaussian elimination with partial pivoting for matrices with displacement structure". Mathematics of Computation 64 (212): 1557–1576. doi:10.1090/s0025-5718-1995-1312096-x. Bibcode: 1995MaCom..64.1557G. https://www.ams.org/journals/mcom/1995-64-212/S0025-5718-1995-1312096-X/S0025-5718-1995-1312096-X.pdf. 
• P. G. Martinsson; M. Tygert; V. Rokhlin (2005). "An $O(N{\log }^{2}N)$ algorithm for the inversion of general Toeplitz matrices". Computers & Mathematics with Applications 50 (5–6): 741–752. doi:10.1016/j.camwa.2005.03.011. http://amath.colorado.edu/faculty/martinss/Pubs/2004_toeplitz.pdf. 
• S. Schechter (1959). "On the inversion of certain matrices". Mathematical Tables and Other Aids to Computation 13 (66): 73–77. doi:10.2307/2001955. https://www.ams.org/journals/mcom/1959-13-066/S0025-5718-1959-0105798-2/S0025-5718-1959-0105798-2.pdf. 
• 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 .