Vandermonde Matrix Identity for Cauchy Matrix

From ProofWiki
Jump to navigation Jump to search

Theorem

Assume values $\set { x_1,\ldots,x_n,y_1,\ldots,y_n }$ are distinct in matrix

\(\displaystyle C\) \(=\) \(\displaystyle \paren {\begin{smallmatrix} \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 & \cdots & \vdots \\ \dfrac {1} {x_n - y_1} & \dfrac {1} {x_n - y_2} & \cdots & \dfrac {1} {x_n - y_n} \\ \end{smallmatrix} }\) Cauchy matrix of order $n$

Then:

\(\displaystyle C\) \(=\) \(\displaystyle -P V_x^{-1} V_y Q^{-1}\) Vandermonde matrix identity for a Cauchy matrix


Definitions of Vandermonde matrices $V_x$, $V_y$ and diagonal matrices $P$, $Q$:

$\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

Definitions of polynomials $p$, $p_1$, $\ldots$, $p_n$:

$\displaystyle p(x) = \prod_{i \mathop = 1}^n \paren {x - x_i}$
$\displaystyle p_k(x) = \dfrac{ \map p x}{x-x_k} = \prod_{i \mathop = 1,i \mathop \ne k}^n \, \paren {x - x_i}$, $1 \mathop \le k \mathop \le n$


Proof

Matrices $P$ and $Q$ are invertible because all diagonal elements are nonzero.

For $1\le i \le n$ express polynomial $p_i$ as:

$\displaystyle \map {p_i} {x} = \sum_{k \mathop = 1}^n a_{ik} x^{k-1}$

Then:

\(\displaystyle \left( \map {p_i} {x_j} \right)\) \(=\) \(\displaystyle \left( a_{ij} \right)V_x\) Definition:Matrix Multiplication
\(\displaystyle P\) \(=\) \(\displaystyle \left( a_{ij} \right) V_x\) Because $\map {p_i} {x_j} = 0$ for $i \ne j$.
\(\displaystyle \left( a_{ij} \right)\) \(=\) \(\displaystyle P V_x^{-1}\) Solve for matrix $\left( a_{ij} \right)$
\(\displaystyle \left( \map {p_i} {y_j} \right)\) \(=\) \(\displaystyle \left( a_{ij} \right)V_y\) Definition:Matrix Multiplication
\(\displaystyle \left( p_i\left( y_j \right) \right)\) \(=\) \(\displaystyle P V_x^{-1} V_y\) Substitute $\left( a_{ij} \right) = P V_x^{-1}$.

Use second equation $\map {p_i} {y_j} = \dfrac{ \map {p} {y_j} }{y_j - x_i}$:

\(\displaystyle \left( \map {p_i} {y_j} \right)\) \(=\) \(\displaystyle -CQ\) Definition:Matrix Multiplication
\(\displaystyle -CQ\) \(=\) \(\displaystyle P V_x^{-1} V_y\) Equate competing equations for $\left( \map {p_i} {y_j} \right)$.
\(\displaystyle C\) \(=\) \(\displaystyle -P V_x^{-1} V_y Q^{-1}\) Solve for $C$.

$\blacksquare$


Examples

$3 \times 3$ Matrix

Illustrate $3\times 3$ case for Vandermonde Matrix Identity for Cauchy Matrix and Value of Cauchy Determinant:

\(\displaystyle C\) \(=\) \(\displaystyle \paren {\begin{smallmatrix} \dfrac 1 {x_1 - y_1} & \dfrac 1 {x_1 - y_2} & \dfrac 1 {x_1 - y_3} \\ \dfrac 1 {x_2 - y_1} & \dfrac 1 {x_2 - y_2} & \dfrac 1 {x_2 - y_3} \\ \dfrac 1 {x_3 - y_1} & \dfrac 1 {x_3 - y_2} & \dfrac 1 {x_3 - y_3} \\ \end{smallmatrix} }\) Values $\set { x_1, x_2, x_3, y_1, y_2, y_3 }$ assumed distinct.

Cauchy matrix of order $3$

Then:

\(\displaystyle C\) \(=\) \(\displaystyle -P V_x^{-1} V_y Q^{-1}\) Vandermonde Matrix Identity for Cauchy Matrix
\(\displaystyle \det \paren C\) \(=\) \(\displaystyle (-1)^3 \dfrac { \paren { x_{3} - x_{1} } \paren { x_{3} - x_{2} } \paren { x_{2} - x_{1} } \quad \paren { y_{3} - y_{1} } \paren { y_{3} - y_{2} } \paren { y_{2} - y_{1} } }{ \paren { x_{1} - y_{1} } \paren { x_{1} - y_{2} } \paren { x_{1} - y_{3} } \quad \paren { x_{2} - y_{1} } \paren { x_{2} - y_{2} } \paren { x_{2} - y_{3} } \quad \paren { x_{3} - y_{1} } \paren { x_{3} - y_{2} } \paren { x_{3} - y_{3} } }\) Determinant Product Theorem


$n \times n$ Matrix

The methods of the $3\times 3$ example apply unchanged for the general $n \times n$ Cauchy matrix:

Assume values $\left\{ x_1,\ldots,x_n,y_1,\ldots,y_n\right\}$ are distinct. Then:

$\det \paren {\begin{smallmatrix} \frac {1} {x_1 - y_1} & \frac {1} {x_1 - y_2} & \cdots & \frac {1} {x_1 - y_n} \\ \frac {1} {x_2 - y_1} & \frac 1 {x_2 - y_2} & \cdots & \frac {1} {x_2 - y_n} \\ \vdots & \vdots & \cdots & \vdots \\ \frac {1} {x_n - y_1} & \frac {1} {x_n - y_2} & \cdots & \frac {1} {x_n - y_n} \\ \end{smallmatrix} } = (-1)^n \dfrac {\prod_{1 \mathop \le j < i \mathop \le n} \paren {x_i - x_j} \quad \prod_{1 \mathop \le j \mathop < i \mathop \le n} \paren {y_i - y_j} } {\prod_{i \mathop = 1}^n \prod_{j \mathop = 1}^n \paren {x_i - y_j} }$ Value of Cauchy Determinant

Assume values $\left\{ x_1,\ldots,x_n,-y_1,\ldots,-y_n\right\}$ are distinct, then replace in the preceding equation $y_i$ by $-y_i$, $1\le i \le n$:

$\det \paren {\begin{smallmatrix} \frac {1} {x_1 + y_1} & \frac {1} {x_1 + y_2} & \cdots & \frac {1} {x_1 + y_n} \\ \frac {1} {x_2 + y_1} & \frac 1 {x_2 + y_2} & \cdots & \frac {1} {x_2 + y_n} \\ \vdots & \vdots & \cdots & \vdots \\ \frac {1} {x_n + y_1} & \frac {1} {x_n + y_2} & \cdots & \frac {1} {x_n + y_n} \\ \end{smallmatrix} } = (-1)^n \dfrac {\prod_{1 \mathop \le j \mathop < i \mathop \le n} \paren {x_i - x_j} \quad \prod_{1 \mathop \le j \mathop < i \mathop \le n} \paren {y_j - y_i} } {\prod_{i \mathop = 1}^n \prod_{j \mathop = 1}^n \paren {x_i + y_j} }$ Value of Cauchy Determinant

$\blacksquare$


Also see


Historical Note

Roderick Gow established Vandermonde Matrix Identity for Cauchy Matrix using interpolation polynomials and change of basis facts.


Sources