Cauchy matrix

From Wikipedia, the free encyclopedia

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

a_{ij}={\frac{1}{x_i-y_j}};\quad x_i-y_j\neq 0,\quad 1 \le i \le m,\quad 1 \le j \le n

where xi and yj are elements of a field \mathcal{F}, and (xi) and (yj) are injective sequences (they do not contain repeated elements; elements are distinct).

Contents

[edit] 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−1 = B = [bij] is given by
b_{ij} = (x_j - y_i) A_j(y_i) B_i(x_j) \,     (Schechter 1959, Theorem 1)
where Ai(x) and Bi(x) are the Lagrange polynomials for (xi) and (yj), 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).
  • Every submatrix of a Cauchy matrix is itself a Cauchy matrix.

[edit] Examples

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

x_i-y_j = i+j-1. \;

[edit] 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(xi), Y=diag(yi), 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(nlogn) ops (e.g. the fast multipole method),
  • (pivoted) LU factorization with O(n2) ops (GKO algorithm), and thus linear system solving,
  • 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).

[edit] 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(Nlog2N) 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 (via JSTOR), Mathematical Tables and Other Aids to Computation, 1959; vol. 13, no. 66., pp. 73-77.

[edit] See also