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).

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.\;$

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⁻¹ = 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).

See also

• Toeplitz matrix
• Fay's trisecant identity

References

• Cauchy, Augustin-Louis (1841). Exercices d'analyse et de physique mathématique. Vol. 2 (in French). Bachelier.
• Gerasoulis, A. (1988). "A fast algorithm for the multiplication of generalized Hilbert matrices with vectors" (PDF). Mathematics of Computation. 50 (181): 179–188. doi:10.2307/2007921. JSTOR 2007921.179-188&rft.date=1988&rft_id=info:doi/10.2307/2007921&rft_id=https://www.jstor.org/stable/2007921#id-name=JSTOR&rft.aulast=Gerasoulis&rft.aufirst=A.&rft_id=https://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917825-9/S0025-5718-1988-0917825-9.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">
• Gohberg, I.; Kailath, T.; Olshevsky, V. (1995). "Fast Gaussian elimination with partial pivoting for matrices with displacement structure" (PDF). Mathematics of Computation. 64 (212): 1557–76. Bibcode:1995MaCom..64.1557G. doi:10.1090/s0025-5718-1995-1312096-x.1557-76&rft.date=1995&rft_id=info:doi/10.1090/s0025-5718-1995-1312096-x&rft_id=info:bibcode/1995MaCom..64.1557G&rft.aulast=Gohberg&rft.aufirst=I.&rft.au=Kailath, T.&rft.au=Olshevsky, V.&rft_id=https://www.ams.org/journals/mcom/1995-64-212/S0025-5718-1995-1312096-X/S0025-5718-1995-1312096-X.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">
• Martinsson, P.G.; Tygert, M.; Rokhlin, V. (2005). "An $O(N\log ^{2}N)$ algorithm for the inversion of general Toeplitz matrices" (PDF). Computers & Mathematics with Applications. 50 (5–6): 741–752. doi:10.1016/j.camwa.2005.03.011.5–6&rft.pages=741-752&rft.date=2005&rft_id=info:doi/10.1016/j.camwa.2005.03.011&rft.aulast=Martinsson&rft.aufirst=P.G.&rft.au=Tygert, M.&rft.au=Rokhlin, V.&rft_id=http://amath.colorado.edu/faculty/martinss/Pubs/2004_toeplitz.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">
• Schechter, S. (1959). "On the inversion of certain matrices" (PDF). Mathematical Tables and Other Aids to Computation. 13 (66): 73–77. doi:10.2307/2001955. JSTOR 2001955.73-77&rft.date=1959&rft_id=info:doi/10.2307/2001955&rft_id=https://www.jstor.org/stable/2001955#id-name=JSTOR&rft.aulast=Schechter&rft.aufirst=S.&rft_id=https://www.ams.org/journals/mcom/1959-13-066/S0025-5718-1959-0105798-2/S0025-5718-1959-0105798-2.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">
• Finck, TiIo; Heinig, Georg; Rost, Karla (1993). "An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices" (PDF). Linear Algebra and Its Applications. 183 (1): 179–191. doi:10.1016/0024-3795(93)90431-M.179-191&rft.date=1993&rft_id=info:doi/10.1016/0024-3795(93)90431-M&rft.aulast=Finck&rft.aufirst=TiIo&rft.au=Heinig, Georg&rft.au=Rost, Karla&rft_id=https://core.ac.uk/download/pdf/82274904.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">
• Fasino, Dario (2023). "Orthogonal Cauchy-like matrices" (PDF). Numerical Algorithms. 92 (1): 619–637. doi:10.1007/s11075-022-01391-y.619-637&rft.date=2023&rft_id=info:doi/10.1007/s11075-022-01391-y&rft.aulast=Fasino&rft.aufirst=Dario&rft_id=https://air.uniud.it/retrieve/c67019bf-7547-437f-8332-354fce4a4f94/s11075-022-01391-y.pdf&rfr_id=info:sid/en.wikipedia.org:Cauchy matrix" class="Z3988">.