- 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−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 "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(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(n log n) ops (e.g. thefast 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
Wikimedia Foundation. 2010.