Cauchy matrix

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

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

:$\backslash det\; \backslash mathbf\{A\}=\{\{\backslash prod\_\{i=2\}^n\; \backslash prod\_\{j=1\}^\{i-1\}\; (x\_i-x\_j)(y\_j-y\_i)\}\backslash over\; \{\backslash prod\_\{i=1\}^n\; \backslash 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)\; \backslash ,$ (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)\; =\; \backslash frac\{A(x)\}\{A^\backslash prime(x\_i)(x-x\_i)\}\; \backslash quad\backslash text\{and\}\backslash quad\; B\_i(x)\; =\; \backslash frac\{B(x)\}\{B^\backslash prime(y\_i)(x-y\_i)\},$

with

:$A(x)\; =\; \backslash prod\_\{i=1\}^n\; (x-x\_i)\; \backslash quad\backslash text\{and\}\backslash quad\; B(x)\; =\; \backslash prod\_\{i=1\}^n\; (x-y\_i).$

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

:$C\_\{ij\}=\backslash 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

:$\backslash mathbf\{XC\}-\backslash mathbf\{CY\}=rs^\backslash mathrm\{T\}$

(with $r=s=(1,1,\backslash 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\; \backslash 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\; \backslash 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).

• Toeplitz matrix
• Fay's trisecant identity

{{refbegin}}

• {{cite book |last= Cauchy|first= Augustin-Louis|date= 1841|title=Exercices d'analyse et de physique mathématique. Vol. 2 |url=https://books.google.com/books?id=DRg-AQAAIAAJ |language=fr |publisher=Bachelier }}
• {{cite journal |first1=A. |last1=Gerasoulis |title=A fast algorithm for the multiplication of generalized Hilbert matrices with vectors |journal=Mathematics of Computation |year=1988 |volume=50 |issue=181 |pages=179–188 |url=https://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917825-9/S0025-5718-1988-0917825-9.pdf |doi=10.2307/2007921|jstor=2007921 |doi-access=free }}
• {{cite journal |first1=I. |last1=Gohberg |first2=T. |last2=Kailath |first3=V. |last3=Olshevsky |title=Fast Gaussian elimination with partial pivoting for matrices with displacement structure |journal=Mathematics of Computation |year=1995 |volume=64 |issue=212 |pages=1557–76 |url=https://www.ams.org/journals/mcom/1995-64-212/S0025-5718-1995-1312096-X/S0025-5718-1995-1312096-X.pdf |doi=10.1090/s0025-5718-1995-1312096-x|bibcode=1995MaCom..64.1557G |doi-access=free }}
• {{cite journal |first1=P.G. |last1=Martinsson |first2=M. |last2=Tygert |first3=V. |last3=Rokhlin |title=An $O(N\; \backslash log^2\; N)$ algorithm for the inversion of general Toeplitz matrices |journal=Computers & Mathematics with Applications |year=2005 |volume=50 |issue=5–6 |pages=741–752 |url=http://amath.colorado.edu/faculty/martinss/Pubs/2004_toeplitz.pdf |doi=10.1016/j.camwa.2005.03.011}}
• {{cite journal |first=S. |last=Schechter |title=On the inversion of certain matrices |journal=Mathematical Tables and Other Aids to Computation |year=1959 |volume=13 |issue=66 |pages=73–77 |url=https://www.ams.org/journals/mcom/1959-13-066/S0025-5718-1959-0105798-2/S0025-5718-1959-0105798-2.pdf |doi=10.2307/2001955|jstor=2001955 }}
• {{cite journal |first1=TiIo |last1=Finck |first2=Georg |last2=Heinig |first3=Karla |last3=Rost |title=An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices |journal=Linear Algebra and Its Applications |volume=183 |issue=1 |pages=179–191 |date=1993 |doi=10.1016/0024-3795(93)90431-M |url=https://core.ac.uk/download/pdf/82274904.pdf}}
• {{cite journal |first=Dario |last=Fasino |title=Orthogonal Cauchy-like matrices |journal=Numerical Algorithms |volume=92 |issue=1 |pages=619–637 |date=2023 |doi=10.1007/s11075-022-01391-y |url=https://air.uniud.it/retrieve/c67019bf-7547-437f-8332-354fce4a4f94/s11075-022-01391-y.pdf}}.

{{refend}}

{{Matrix classes}}

Category:Matrices (mathematics)

Category:Determinants