Cauchy matrix

In mathematics, a Cauchy matrix is an $m\; imes\; n$ matrix A, with elements in the form

:$a\_\{ij\}=\{frac\{1\}\{x\_i-y\_j;quad\; x\_i-y\_j\; eq\; 0,quad\; 1\; le\; i\; le\; m,quad\; 1\; le\; j\; le\; n$

where $x\_i$ and $y\_j$ are elements of a field $mathcal\{F\}$, and $(x\_i)$ and $(y\_j)$ are injective sequences (they do not contain repeated elements; elements are "distinct").

Properties

* When $m=n$, the determinant, known as a Cauchy determinant, is given explicitly by::$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).

* The Cauchy determinant is 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\; ext\{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\; ext\{and\}quad\; B(x)\; =\; prod\_\{i=1\}^n\; (x-y\_i).$

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

Examples

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

:$x\_i-y\_j\; =\; i+j-1.\; ;$

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

References

* A. Gerasoulis, "A fast algorithm for the multiplication of generalized Hilbert matrices with vectors", Mathematics of Computation, 1988; vol. 50, no. 181, pp. 179-188.
* I. Gohberg, T. Kailath, V. Olshevsky, "Fast Gaussian elimination with partial pivoting for matrices with displacement structure". Mathematics of Computation, 1995; vol. 64, no. 212, pp. 1557-1576.
* 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, pp. 741-752.
* S. Schechter, "On the inversion of certain matrices" [http://links.jstor.org/sici?sici=0891-6837%28195904%2913%3A66%3C73%3AOTIOCM%3E2.0.CO%3B2-P (via JSTOR)] , Mathematical Tables and Other Aids to Computation, 1959; vol. 13, no. 66., pp. 73-77.

ee also

*Toeplitz matrix
*Augustin Louis Cauchy