Value of Cauchy Determinant
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 {\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i} \paren {y_j - y_i} } {\ds \prod_{1 \mathop \le i, \, j \mathop \le n} \paren {x_i + y_j} }$
Let $D_n$ be 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 {\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i} \paren {y_i - y_j} } {\ds \prod_{1 \mathop \le i, \, j \mathop \le n} \paren {x_i - y_j} }$
Proof 1
Take the version of the Cauchy matrix defined such that $a_{i j} = \dfrac 1 {x_i + y_j}$.
Subtract column $1$ from each of columns $2$ to $n$.
Thus:
\(\ds a_{ij}\) | \(\gets\) | \(\ds \frac 1 {x_i + y_j} - \frac 1 {x_i + y_1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {x_i + y_1} - \paren {x_i + y_j} } {\paren {x_i + y_j} \paren {x_i + y_1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {y_1 - y_j} {x_i + y_1} } \paren {\frac 1 {x_i + y_j} }\) |
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:
- $\ds D_n = \paren {\prod_{i \mathop = 1}^n \frac 1 {x_i + y_1} } \paren {\prod_{j \mathop = 2}^n y_1 - y_j} \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:
\(\ds a_{i j}\) | \(\gets\) | \(\ds \frac 1 {x_i + y_j} - \frac 1 {x_1 + y_j}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {x_1 + y_j} - \paren {x_i + y_j} } {\paren {x_i + y_j} \paren {x_1 + y_j} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {x_1 - x_i} {x_1 + y_j} } \paren {\frac 1 {x_i + y_j} }\) |
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:
- $\ds D_n = \paren {\prod_{i \mathop = 1}^n \frac 1 {x_i + y_1} } \paren {\prod_{j \mathop = 1}^n \frac 1 {x_1 + y_j} } \paren {\prod_{i \mathop = 2}^n x_1 - x_i} \paren {\prod_{j \mathop = 2}^n y_1 - y_j} \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 {\ds \prod_{i \mathop = 2}^n \paren {x_i - x_1} \paren {y_i - y_1} } {\ds \prod_{1 \mathop \le i, j \mathop \le n} \paren {x_i + y_1} \paren {x_1 + y_j} } \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_{i j} = \dfrac 1 {x_i - y_j}$ form.
Proof 2
Let:
\(\ds C\) | \(=\) | \(\ds \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:
\(\ds \map \det C\) | \(=\) | \(\ds \dfrac {\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i} \paren {y_i - y_j} } {\ds \prod_{1 \mathop \le i, j \mathop \le n} \paren {x_i - y_j} }\) | replacing $y_k \to -y_k$ in $C$ and $\map \det C$ |
Assume hereafter that set $\set {x_1, \ldots, x_n, y_1, \ldots, y_n}$ consists of distinct values, because otherwise $\map \det C$ is undefined or zero.
Preliminaries:
Vandermonde Matrix Identity for Cauchy Matrix supplies matrix equation
- $(1): \quad - C = P V_x^{-1} V_y Q^{-1}$
- Definitions of symbols:
- $V_x = \begin {pmatrix} 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 {pmatrix}$
- $V_y = \begin {pmatrix} 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 {pmatrix}$ Definition of Vandermonde Matrix
- $P = \begin {pmatrix} \map {p_1} {x_1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \map {p_n} {x_n} \\ \end {pmatrix}$
- $Q = \begin {pmatrix} \map p {y_1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \map p {y_n)} \\ \end {pmatrix}$ Definition of Diagonal Matrix
- $1 \mathop \le k \mathop \le n$ Polynomials
- $\ds \map p x = \prod_{i \mathop = 1}^n \paren {x - x_i}$
- $\ds \map {p_k} x = \prod_{i \mathop = 1, i \mathop \ne k}^n \paren {x - x_i}$
Determinant of $C$ Calculation:
\(\ds C\) | \(=\) | \(\ds \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. |
|||||||||||
\(\text {(2)}: \quad\) | \(\ds \map \det C\) | \(=\) | \(\ds \map \det {-I} \map \det P \map \det {V_x^{-1} } \map \det {V_y} \map \det {Q^{-1} }\) | Determinant of Matrix Product | ||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^n \map \det I \map \det P \map \det {V_x^{-1} } \map \det {V_y} \map \det {Q^{-1} }\) | Effect of Elementary Row Operations on Determinant: factoring constant $-1$ from all rows of $-I$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^n \map \det I \dfrac {\map \det p \map \det {V_y} } {\map \det Q \map \det {V_x} }\) | Matrix Product with Adjugate Matrix and Determinant of Matrix Product |
Lemma: $\map \det P = \paren {-1}^m \paren {\map \det {V_x} }^2$ where $m = \frac 1 2 n \paren {n - 1}$
- Details: Determinant $\map \det P$ expands to:
\(\ds \prod_{j \mathop = 1}^n \map {p_j} {x_j}\) | \(=\) | \(\ds \prod_{j \mathop = 1}^n \prod_{k \mathop = 1, k \mathop \ne 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:
\(\ds \map \det P\) | \(=\) | \(\ds \paren {-1}^m \paren {\prod_{1 \mathop \le r \mathop < s \mathop \le n} \paren {x_s - x_r }^2}\) | where $m = 1 + \cdots + \paren {n - 1} = \dfrac 1 2 n \paren {n - 1}$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^m \paren {\map \det {V_x} }^2\) | Value of Vandermonde Determinant |
$\Box$
Apply the Lemma to equation (2):
\(\ds \map \det C\) | \(=\) | \(\ds \paren {-1}^{n + m} \paren {\dfrac {\map \det {V_x} \map \det {V_y} } {\map \det Q} }\) | $m = \dfrac 1 2 n \paren {n - 1}$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^{n + m} \dfrac {\ds \prod_{1 \mathop \le m \mathop < k \mathop \le n}^{\phantom n} \paren {x_k - x_m} \prod_{1 \mathop \le m \mathop < k \mathop \le n} \paren {y_k - y_m} } {\ds \prod_{k \mathop = 1}^n \map p {y_k} }\) | Value of Vandermonde Determinant and Determinant of Diagonal Matrix | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^{n + m} \dfrac {\ds \prod_{1 \mathop \le m \mathop < k \mathop \le n}^{\phantom n} \paren {x_k - x_m} \paren {y_k - y_m} } {\ds \prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren {y_k - x_j} }\) | Definition of $\map p x$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {-1}^{n + m} \dfrac {\ds \paren {-1}^m \prod_{1 \mathop \le m \mathop < k \mathop \le n}^{\phantom n} \paren {x_k - x_m} \paren {y_m - y_k} } {\ds \paren {-1}^{n^2} \prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren {x_j - y_k} }\) | factoring out changed signs | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\ds \prod_{1 \mathop \le m \mathop < k \mathop \le n}^{\phantom n} \paren {x_k - x_m} \paren {y_m - y_k} } {\ds \prod_{k \mathop = 1}^n \prod_{j \mathop = 1}^n \paren {x_j - y_k} }\) | as all signs cancel |
$\blacksquare$
Source of Name
This entry was named for Augustin Louis Cauchy.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: Exercise $38$