Value of Cauchy Determinant

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $D_n$ be a Cauchy determinant of order $n$:

$\begin{vmatrix} \dfrac 1 {x_1 + y_1} & \dfrac 1 {x_1 + y_2} & \cdots & \dfrac 1 {x_1 + y_n} \\ \dfrac 1 {x_2 + y_1} & \dfrac 1 {x_2 + y_2} & \cdots & \dfrac 1 {x_2 + y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_n + y_1} & \dfrac 1 {x_n + y_2} & \cdots & \dfrac 1 {x_n + y_n} \\ \end{vmatrix}$


Then the value of $D_n$ is given by:

$D_n = \dfrac {\displaystyle \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right) \left({y_j - y_i}\right)} {\displaystyle \prod_{1 \mathop \le i, \, j \mathop \le n} \left({x_i + y_j}\right)}$


If $D_n$ is given by:

$\begin{vmatrix} \dfrac 1 {x_1 - y_1} & \dfrac 1 {x_1 - y_2} & \cdots & \dfrac 1 {x_1 - y_n} \\ \dfrac 1 {x_2 - y_1} & \dfrac 1 {x_2 - y_2} & \cdots & \dfrac 1 {x_2 - y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_n - y_1} & \dfrac 1 {x_n - y_2} & \cdots & \dfrac 1 {x_n - y_n} \\ \end{vmatrix}$


then its determinant is given by:

$D_n = \dfrac {\displaystyle \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right) \left({y_i - y_j}\right)} {\displaystyle \prod_{1 \mathop \le i, \, j \mathop \le n} \left({x_i - y_j}\right)}$


Proof 1

Take the version of the Cauchy matrix defined such that $a_{ij} = \dfrac 1 {x_i + y_j}$.

Subtract column $1$ from each of columns $2$ to $n$.

Thus:

\(\displaystyle a_{ij}\) \(\gets\) \(\displaystyle \frac 1 {x_i + y_j} - \frac 1 {x_i + y_1}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {\left({x_i + y_1}\right) - \left({x_i + y_j}\right)} {\left({x_i + y_j}\right) \left({x_i + y_1}\right)}\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\frac {y_1 - y_j}{x_i + y_1} }\right) \left({\frac 1 {x_i + y_j} }\right)\)

From Multiple of Row Added to Row of Determinant this will have no effect on the value of the determinant.


Now:

$1$: extract the factor $\dfrac 1 {x_i + y_1}$ from each row $1 \le i \le n$
$2$: extract the factor $y_1 - y_j$ from each column $2 \le j \le n$.

Thus from Determinant with Row Multiplied by Constant we have the following:

$\displaystyle D_n = \left({\prod_{i \mathop = 1}^n \frac 1 {x_i + y_1}}\right) \left({\prod_{j \mathop = 2}^n y_1 - y_j}\right) \begin{vmatrix} 1 & \dfrac 1 {x_1 + y_2} & \dfrac 1 {x_1 + y_3} & \cdots & \dfrac 1 {x_1 + y_n} \\ 1 & \dfrac 1 {x_2 + y_2} & \dfrac 1 {x_2 + y_3} & \cdots & \dfrac 1 {x_2 + y_n} \\ 1 & \dfrac 1 {x_3 + y_2} & \dfrac 1 {x_3 + y_3} & \cdots & \dfrac 1 {x_3 + y_n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \dfrac 1 {x_n + y_2} & \dfrac 1 {x_n + y_3} & \cdots & \dfrac 1 {x_n + y_n} \\ \end{vmatrix}$


Now subtract row $1$ from each of rows $2$ to $n$.

Column $1$ will go to $0$ for all but the first row.

Columns $2$ to $n$ will become:

\(\displaystyle a_{ij}\) \(\gets\) \(\displaystyle \frac 1 {x_i + y_j} - \frac 1 {x_1 + y_j}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {\left({x_1 + y_j}\right) - \left({x_i + y_j}\right)} {\left({x_i + y_j}\right) \left({x_1 + y_j}\right)}\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\frac {x_1 - x_i} {x_1 + y_j} }\right) \left({\frac 1 {x_i + y_j} }\right)\)

From Multiple of Row Added to Row of Determinant this will have no effect on the value of the determinant.


Now:

$1$: extract the factor $x_1 - x_i$ from each row $2 \le i \le n$
$2$: extract the factor $\dfrac 1 {x_1 + y_j}$ from each column $2 \le j \le n$.


Thus from Determinant with Row Multiplied by Constant we have the following:

$\displaystyle D_n = \left({\prod_{i \mathop = 1}^n \frac 1 {x_i + y_1}}\right) \left({\prod_{j \mathop = 1}^n \frac 1 {x_1 + y_j}}\right) \left({\prod_{i \mathop = 2}^n x_1 - x_i}\right) \left({\prod_{j \mathop = 2}^n y_1 - y_j}\right) \begin{vmatrix} 1 & 1 & 1 & \cdots & 1 \\ 0 & \dfrac 1 {x_2 + y_2} & \dfrac 1 {x_2 + y_3} & \cdots & \dfrac 1 {x_2 + y_n} \\ 0 & \dfrac 1 {x_3 + y_2} & \dfrac 1 {x_3 + y_3} & \cdots & \dfrac 1 {x_3 + y_n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \dfrac 1 {x_n + y_2} & \dfrac 1 {x_n + y_3} & \cdots & \dfrac 1 {x_n + y_n} \\ \end{vmatrix}$

From Determinant with Unit Element in Otherwise Zero Row, and tidying up the products, we get:

$D_n = \frac {\displaystyle \prod_{i \mathop = 2}^n \left({x_i - x_1}\right) \left({y_i - y_1}\right)} {\displaystyle \prod_{1 \mathop \le i, j \mathop \le n} \left({x_i + y_1}\right) \left({x_1 + y_j}\right)} \begin{vmatrix} \dfrac 1 {x_2 + y_2} & \dfrac 1 {x_2 + y_3} & \cdots & \dfrac 1 {x_2 + y_n} \\ \dfrac 1 {x_3 + y_2} & \dfrac 1 {x_3 + y_3} & \cdots & \dfrac 1 {x_3 + y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_n + y_2} & \dfrac 1 {x_n + y_3} & \cdots & \dfrac 1 {x_n + y_n} \\ \end{vmatrix}$


Repeat the process for the remaining rows and columns $2$ to $n$.

The result follows.

$\blacksquare$


A similar process obtains the result for the $a_{ij} = \dfrac 1 {x_i - y_j}$ form.


Proof 2

Let:

\(\displaystyle C\) \(=\) \(\displaystyle \begin{bmatrix} \dfrac 1 {x_1 - y_1} & \dfrac 1 {x_1 - y_2} & \cdots & \dfrac 1 {x_1 - y_n} \\ \dfrac 1 {x_2 - y_1} & \dfrac 1 {x_2 - y_2} & \cdots & \dfrac 1 {x_2 - y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_n - y_1} & \dfrac 1 {x_n - y_2} & \cdots & \dfrac 1 {x_n - y_n} \\ \end{bmatrix}\)

To be proved:

\(\displaystyle \det \paren {C}\) \(=\) \(\displaystyle \dfrac {\displaystyle \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right) \left({y_i - y_j}\right)} {\displaystyle \prod_{1 \mathop \le i, \, j \mathop \le n} \left({x_i - y_j}\right)}\) Knuth (1997) replacing $y_k \to -y_k$ in $C$ and $\det \paren {C}$

Assume hereafter that set $\set {x_1,\ldots,x_n,y_1,\ldots,y_n}$ consists of distinct values, because otherwise $\det \paren {C}$ is undefined or zero.

Preliminaries:

Vandermonde Matrix Identity for Cauchy Matrix supplies matrix equation

$\displaystyle (1)\quad - C = PV_x^{-1} V_y Q^{-1}$
Definitions of symbols:
$\displaystyle V_x=\paren {\begin{smallmatrix} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_n \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1} \\ \end{smallmatrix} },\quad V_y=\paren {\begin{smallmatrix} 1 & 1 & \cdots & 1 \\ y_1 & y_2 & \cdots & y_n \\ \vdots & \vdots & \ddots & \vdots \\ y_1^{n-1} & y_2^{n-1} & \cdots & y_n^{n-1} \\ \end{smallmatrix} }$ Vandermonde matrices
$\displaystyle P= \paren {\begin{smallmatrix} p_1(x_1) & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & p_n(x_n) \\ \end{smallmatrix} }, \quad Q= \paren {\begin{smallmatrix} p(y_1) & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & p(y_n) \\ \end{smallmatrix} }$ Diagonal matrices
$\displaystyle p(x) = \prod_{i \mathop = 1}^n \paren {x - x_i}, \quad \displaystyle p_k(x) = \prod_{i \mathop = 1,i \mathop \ne k}^n \, \paren {x - x_i}, \quad 1 \mathop \le k \mathop \le n$ Polynomials

Determinant of $C$ Calculation:

\(\displaystyle C\) \(=\) \(\displaystyle \paren {-I}\,P\,V_x^{-1}\, V_y\, Q^{-1}\) Vandermonde Matrix Identity for Cauchy Matrix

Symbol $I$ is the $n\times n$ identity matrix.

\(\displaystyle (2)\quad \det \paren {C}\) \(=\) \(\displaystyle \det \paren { -I } \det \paren {P} \det \paren { V_x^{-1} } \det \paren { V_y } \det \paren { Q^{-1} }\) Determinant of Matrix Product
\(\displaystyle \) \(=\) \(\displaystyle \paren { -1 }^n \det \paren { I } \det \paren {P} \det \paren { V_x^{-1} } \det \paren { V_y } \det \paren { Q^{-1} }\) Effect of Elementary Row Operations on Determinant

Factor constant $-1$ from all rows of $-I$.

\(\displaystyle \) \(=\) \(\displaystyle \paren { -1 }^n \det \paren { I } \dfrac { \det \paren {P} \det \paren { V_y } } { \det \paren { Q } \det \paren { V_x } }\) Matrix Product with Adjugate Matrix and

Determinant of Matrix Product

Lemma: $\det \paren {P} = \paren {-1}^m \paren { \det \paren {V_x} }^2$ where $m=\frac 1 2 n \paren {n-1}$

Details: Determinant $\det \paren {P}$ expands to:
\(\displaystyle \,\,\prod_{j \mathop = 1}^n \map {p_j} {x_j}\) \(=\) \(\displaystyle \prod_{j \mathop = 1}^n \,\, \prod_{k \mathop = 1,\, k \mathop \neq j}^n \paren { x_j - x_k }\) Definition of polynomials $\map {p_j} x$.
Pair factors $\paren {x_r - x_s}$ and $\paren {x_s - x_r}$ into factor $- \paren {x_s - x_r}^2$, then:
\(\displaystyle \,\,\det \paren {P}\) \(=\) \(\displaystyle \paren {-1}^m \, \paren { \prod_{1 \mathop \leq r \mathop \lt s \mathop \le n} \paren { x_s - x_r }^2 }\) where $m = 1 + \cdots + \paren {n-1} = \frac 1 2 n \paren {n-1}$
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^m \, \paren { \det \paren {V_x} }^2\) Vandermonde Determinant

$\Box$

Apply the Lemma to equation (2):

\(\displaystyle \det \paren {C}\) \(=\) \(\displaystyle \paren { -1 }^{n+m} \, \paren { \dfrac { \det \paren {V_x} \det \paren { V_y } } { \det \paren { Q } } }\) $m = \frac 1 2 n \paren {n-1}$
\(\displaystyle \) \(=\) \(\displaystyle \paren { -1 }^{n+m} \,\, \dfrac { \displaystyle \prod_{1 \mathop \le m \mathop \lt k \mathop \le n}^{\phantom n} \paren { x_k - x_m } \, \prod_{1 \mathop \le m \mathop \lt k \mathop \le n} \paren { y_k - y_m } } { \displaystyle \prod_{k \mathop = 1}^n \map {p} {y_k} }\) Vandermonde Determinant and

Determinant of Diagonal Matrix

\(\displaystyle \) \(=\) \(\displaystyle \paren { -1 }^{n+m} \,\, \dfrac { \displaystyle \prod_{1 \mathop \le m \mathop \lt k \mathop \le n}^{\phantom n} \paren { x_k - x_m } \paren { y_k - y_m } } { \displaystyle \prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren { y_k - x_j } }\) Definition of $\map p x$.
\(\displaystyle \) \(=\) \(\displaystyle \paren { -1 }^{n+m} \,\, \dfrac { \displaystyle \paren {-1}^{m}\prod_{1 \mathop \le m \mathop \lt k \mathop \le n}^{\phantom n} \paren { x_k - x_m } \paren { y_m - y_k } } { \displaystyle \paren {-1}^{n^2}\,\,\prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren { x_j - y_k } }\) Factor out changed signs.
\(\displaystyle \) \(=\) \(\displaystyle \left. \dfrac { \displaystyle \prod_{1 \mathop \le m \mathop \lt k \mathop \le n}^{\phantom n} \paren { x_k - x_m } \paren { y_m - y_k } } { \displaystyle \prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren { x_j - y_k } } \right.\) All signs cancel.

$\blacksquare$


Source of Name

This entry was named for Augustin Louis Cauchy.


Sources