Cauchy matrix

From Wikipedia, the free encyclopedia

In mathematics, the Cauchy matrix is an m×n matrix A, whose elements are given by

$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 x_i and y_j are elements of a field $\mathcal{F}$ , and where (x_i) and (y_j) are injective sequences (they do not contain repeated elements; elements are distinct).

1 Properties
2 Examples
3 Generalization
4 References
5 See also

[edit] Properties

When m=n, the determinant, known as a Cauchy determinant, is given explicitly by

$\det A={{\prod_{i<j} (x_i-x_j)\prod_{i<j} (y_i-y_j)}\over {\prod_{i,j} (x_i +y_j)}}.\,$

As a consequence of the injectivity of $(x i)$ and $(y j)$ , all square Cauchy matrices are invertible.
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(x i)$ , $Y = d i a g (y i)$ , one sees that both Cauchy and Cauchy-like matrices satisfy the displacement equation

X C + C Y = r s 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).

[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 (N log 2 N)$ algorithm for the inversion of general Toeplitz matrices, Computers & Mathematics with Applications, 2005; 50, pp. 741-752.

Category: Matrices

Cauchy matrix

From Wikipedia, the free encyclopedia

Contents

[edit] Properties

[edit] Examples

[edit] Generalization

[edit] References

[edit] See also

Views

Navigation

interaction

Search

In other languages