Cauchy matrix

Short description: Matrix class

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

aij=1xi−yj;xi−yj≠0,1≤i≤m,1≤j≤n

where xi and yj are elements of a field ℱ, and (xi) and (yj) are injective sequences (they contain distinct elements).

## Contents

* 1 Properties
* 2 Cauchy determinants
* 3 Generalization
* 4 See also
* 5 References

## Properties

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

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

xi−yj=i+j−1.

## Cauchy determinants

The determinant of a Cauchy matrix is clearly a rational fraction in the parameters (xi) and (yj). If the sequences were not injective, the determinant would vanish, and tends to infinity if some xi tends to yj. 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⁡𝐀=∏i=2n∏j=1i−1(xi−xj)(yj−yi)∏i=1n∏j=1n(xi−yj) (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

bij=(xj−yi)Aj(yi)Bi(xj) (Schechter 1959, Theorem 1)

where Ai(x) and Bi(x) are the Lagrange polynomials for (xi) and (yj), respectively. That is,

Ai(x)=A(x)A′(xi)(x−xi)andBi(x)=B(x)B′(yi)(x−yi),

with

A(x)=∏i=1n(x−xi)andB(x)=∏i=1n(x−yi).

## Generalization

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

Cij=risjxi−yj.

Defining X=diag(xi), Y=diag(yi), one sees that both Cauchy and Cauchy-like matrices satisfy the displacement equation

𝐗𝐂−𝐂𝐘=rsT

(with r=s=(1,1,…,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(nlog⁡n) ops (e.g. the fast multipole method),
* (pivoted) LU factorization with O(n2) ops (GKO algorithm), and thus linear system solving,
* linear system solving in O~(αω−1n) ops with the use of fast matrix multiplication algorithms, instead of O~(α2n) ops without it, where α is the displacement rank and  ∼2.37≤ω<3[1].
* approximated or unstable algorithms for linear system solving in O(nlog2n).

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.
* Gerasoulis, A. (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.
* Gohberg, I.; Kailath, T.; Olshevsky, V. (1995). "Fast Gaussian elimination with partial pivoting for matrices with displacement structure". Mathematics of Computation 64 (212): 1557–76. 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.
* Martinsson, P.G.; Tygert, M.; Rokhlin, V. (2005). "An O(Nlog2N) 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.
* Schechter, S. (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.
* Finck, TiIo; Heinig, Georg; Rost, Karla (1993). "An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices". Linear Algebra and Its Applications 183 (1): 179–191. doi:10.1016/0024-3795(93)90431-M. https://core.ac.uk/download/pdf/82274904.pdf.
* Fasino, Dario (2023). "Orthogonal Cauchy-like matrices". Numerical Algorithms 92 (1): 619–637. doi:10.1007/s11075-022-01391-y. https://air.uniud.it/retrieve/c67019bf-7547-437f-8332-354fce4a4f94/s11075-022-01391-y.pdf. .

* v
* t
* e

Matrix classes

Explicitly constrained entries|

* (0,1)
* Alternant
* Anti-diagonal
* Anti-Hermitian
* Anti-symmetric
* Arrowhead
* Band
* Bidiagonal
* Binary
* Bisymmetric
* Block-diagonal
* Block
* Block tridiagonal
* Boolean
* Cauchy
* Centrosymmetric
* Conference
* Complex Hadamard
* Copositive
* Diagonally dominant
* Diagonal
* Discrete Fourier Transform
* Elementary
* Equivalent
* Frobenius
* Generalized permutation
* Hadamard
* Hankel
* Hermitian
* Hessenberg
* Hollow
* Integer
* Logical
* Markov
* Metzler
* Monomial
* Moore
* Nonnegative
* Partitioned
* Parisi
* Pentadiagonal
* Permutation
* Persymmetric
* Polynomial
* Positive
* Quaternionic
* Sign
* Signature
* Skew-Hermitian
* Skew-symmetric
* Skyline
* Sparse
* Sylvester
* Symmetric
* Toeplitz
* Triangular
* Tridiagonal
* Unitary
* Vandermonde
* Walsh
* Z

Constant|

* Exchange
* Hilbert
* Identity
* Lehmer
* Of ones
* Pascal
* Pauli
* Redheffer
* Shift
* Zero

Conditions on eigenvalues or eigenvectors|

* Companion
* Convergent
* Defective
* Diagonalizable
* Hurwitz
* Positive-definite
* Stability
* Stieltjes

Satisfying conditions on products or inverses|

* Congruent
* Idempotent or Projection
* Invertible
* Involutory
* Nilpotent
* Normal
* Orthogonal
* Orthonormal
* Singular
* Unimodular
* Unipotent
* Totally unimodular
* Weighing

With specific applications|

* Adjugate
* Alternating sign
* Augmented
* Bézout
* Carleman
* Cartan
* Circulant
* Cofactor
* Commutation
* Confusion
* Coxeter
* Derogatory
* Distance
* Duplication
* Elimination
* Euclidean distance
* Fundamental (linear differential equation)
* Generator
* Gramian
* Hessian
* Householder
* Jacobian
* Moment
* Payoff
* Pick
* Random
* Rotation
* Seifert
* Shear
* Similarity
* Symplectic
* Totally positive
* Transformation
* Wedderburn
* X–Y–Z

Used in statistics|

* Bernoulli
* Centering
* Correlation
* Covariance
* Design
* Dispersion
* Doubly stochastic
* Fisher information
* Hat
* Precision
* Stochastic
* Transition

Used in graph theory|

* Adjacency
* Biadjacency
* Degree
* Edmonds
* Incidence
* Laplacian
* Seidel adjacency
* Skew-adjacency
* Tutte

Used in science and engineering|

* Cabibbo–Kobayashi–Maskawa
* Density
* Fundamental (computer vision)
* Fuzzy associative
* Gamma
* Gell-Mann
* Hamiltonian
* Irregular
* Overlap
* S
* State transition
* Substitution
* Z (chemistry)

Related terms|

* Jordan canonical form
* Linear independence
* Matrix exponential
* Matrix representation of conic sections
* Perfect matrix
* Pseudoinverse
* Quaternionic matrix
* Row echelon form
* Wronskian

* List of matrices
* Category:Matrices

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Cauchy matrix. Read more

|

1. ↑ Bostan, A.; Jeannerod, C.-P.; Schost, É. (2008). "Solving structured linear systems with large displacement rank". Theoretical Computer Science 407 (1-3): 155-181. doi:10.1016/j.tcs.2008.05.014.

Retrieved from "https://handwiki.org/wiki/index.php?title=Cauchy_matrix&oldid=4227530"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template