Inverse of Cauchy Matrix

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $C_n$ be the square Cauchy matrix of order $n$:

$C_n = \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}$


Then its inverse $C_n^{-1} = \sqbrk b_n$ can be specified as:

$\begin{bmatrix} b_{ij} \end{bmatrix} = \begin{bmatrix} \dfrac {\displaystyle \prod_{k \mathop = 1}^n \paren {x_j + y_k} \paren {x_k + y_i} } {\displaystyle \paren {x_j + y_i} \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne i} } \paren {y_i - y_k} } } \end{bmatrix}$


Proof

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

Compute the inverse $C^{-1}$ for:

\(\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}\) Assume $\set {x_1,\ldots,x_n,y_1,\ldots,y_n}$ has distinct elements.

Replacement $y_k \to -y_k$ then gives the inverse $C_n^{-1}$ in the theorem.

Inverse of Matrix Product applied to equation (1) gives:

$ C^{-1} = -Q V_y^{-1} V_x P^{-1}$

Let ${\vec K}_1,\ldots,{\vec K}_n$ denote the columns of the $n\times n$ identity matrix.

Then $n\times n$ matrix $B = C^{-1}$ has entries $b_{ij} = {\vec K}_i^T C^{-1} {\vec K}_j$.

Hold fixed until the end of the proof the row and column index symbols $i$ and $j$.

Define column vectors $\vec A$, $\vec B$ so that $b_{ij} = {\vec A}^T \vec B$:

$\displaystyle \vec A = \paren { {\vec K}_i^T \, Q \, V_y^{-1} }^T, \quad \vec B = -V_x \, P^{-1} \, {\vec K}_j $

Define $u = x_j$ and simplify:

\(\displaystyle \vec A\) \(=\) \(\displaystyle {\map p {y_i} } \, \paren { V_y^{-1} }^T \, {\vec K}_i\) Transpose of Matrix Product
\(\displaystyle \) \(=\) \(\displaystyle \dfrac{ \map p {y_i} }{\det \paren {V_y} } \paren { \adj {V_y} }^T {\vec K}_i\) Matrix Product with Adjugate Matrix
\(\displaystyle \) \(=\) \(\displaystyle \dfrac{ \map p {y_i} }{\det \paren {V_y} } \begin{bmatrix} {\mathbf {Cofactor} } \paren {V_y,1,i } \\ \vdots \\ {\mathbf {Cofactor} } \paren {V_y,n,i } \\ \end{bmatrix}\) ${\mathbf {Cofactor} } \paren {M,r,s}$ denotes cofactor $M_{rs}$
\(\displaystyle \vec B\) \(=\) \(\displaystyle -\dfrac{1}{\map {p_j} {x_j} } \, V_x \, {\vec K}_j\)
\(\displaystyle \) \(=\) \(\displaystyle -\dfrac{1}{\map {p_j} {x_j} } \, \begin{bmatrix} 1 \\ u \\ \vdots \\ u^{n-1} \\ \end{bmatrix}\) Symbol $u = x_j$.

Then:

\(\displaystyle A^T\, B\) \(=\) \(\displaystyle \dfrac { -\map p {y_i} } {\map {p_j} {x_j} \det \paren {V_y} } \sum_{k \mathop = 1}^n {\mathbf {Cofactor} } \paren {V_y,k,i } \, u^{k-1}\) A Cofactor expansion

along column $i$.

\(\displaystyle \) \(=\) \(\displaystyle \dfrac { -\map p {y_i} } {\map {p_j} {x_j} \det \paren {V_y} } \det \paren { \begin{matrix} 1 & \cdots & 1 & 1 & 1 & \cdots & 1 \\ y_1 & \cdots & y_{i-1} & u & y_{i+1} & \cdots & y_n \\ \vdots & \cdots & \vdots &\vdots & \vdots & \cdots & \vdots \\ y_1^{n-1} & \cdots & y_{i-1}^{n-1} & u^{n-1} & y_{i+1}^{n-1} & \cdots & y_n^{n-1} \\ \end{matrix} }\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac { -\map p {y_i} } {\map {p_j} {x_j} } \,\, \dfrac { \left. \paren { \det \paren {V_y} } \right \vert_{y_i \mathop = u} } { \det \paren {V_y} }\)

Simplify the fraction on the right:

\(\displaystyle (2)\quad \displaystyle \dfrac { \displaystyle \left. \paren { \det \paren {V_y} } \right\vert_{y_i \mathop = u} } { \displaystyle \det \paren {V_y} }\) \(=\) \(\displaystyle \displaystyle \dfrac {\displaystyle \left. \paren { \prod_{1 \mathop \le m \mathop \lt k \mathop \le n} \paren { y_k - y_m } } \right\vert_{ y_i \mathop = u } } {\displaystyle \prod_{1 \mathop \le m \mathop \lt k \mathop \le n} \paren { y_k - y_m } }\) Vandermonde Determinant

Define sets $D,A,B,C$ with disjoint decomposition $D = A \cup B \cup C$:

\(\displaystyle D\) \(=\) \(\displaystyle \set { \paren { m,k } : 1 \le m \lt k \le n }\)
\(\displaystyle A\) \(=\) \(\displaystyle \set { \paren { m,k } \in D : m \neq i \mbox{ and } k \neq i }\)
\(\displaystyle B\) \(=\) \(\displaystyle \set { \paren { m,k } \in D : m = i }\)
\(\displaystyle C\) \(=\) \(\displaystyle \set { \paren { m,k } \in D : k = i }\)

Use $\prod_{D} = \prod_{A} \prod_{B} \prod_{C}$ to convert the numerator and denominator in the right side of (2).

Then:

\(\displaystyle \displaystyle \dfrac { \displaystyle \left. \paren { \det \paren {V_y} } \right\vert_{y_i \mathop = u} } { \displaystyle \det \paren {V_y} }\) \(=\) \(\displaystyle \displaystyle \dfrac {\displaystyle \prod_{k \mathop = 1,\, k \mathop \neq i}^n \paren { u - y_k } } {\displaystyle \prod_{k \mathop = 1,\, k \mathop \neq i}^n \paren { y_i - y_k } }\) Common factors canceled in (2).

Replacement of ${ \map p {y_i} }$ and ${ \map {p_j} {x_j} }$ by products gives:

\(\displaystyle (3)\quad \displaystyle b_{ij}\) \(=\) \(\displaystyle \paren {-1} \, \dfrac { \displaystyle \prod_{k \mathop = 1}^n \paren {y_i - x_k } } { \displaystyle \prod_{k \mathop = 1,\, k \mathop \neq j}^n \paren { x_j - x_k } } \,\, \prod_{k \mathop = 1,\, k \mathop \neq i}^n \paren { \dfrac { x_j - y_k }{ y_i - y_k } }\) Replaced $u = x_j$.


After replacement $y_k \to -y_k$ and canceling a common factor, Knuth's original identity (1997) becomes:

\(\displaystyle \displaystyle (4)\quad b_{ij}\) \(=\) \(\displaystyle \displaystyle \dfrac { \displaystyle \prod_{k \mathop = 1}^n \paren { x_k - y_i } } { \displaystyle \prod_{k \mathop = 1,\, k \mathop \neq j}^n \paren { x_j - x_k } } \dfrac { \displaystyle \prod_{k \mathop = 1,\, k \mathop \neq i}^n \paren { x_j - y_k } } { \displaystyle \prod_{k \mathop = 1,\, k \mathop \neq i}^n \paren { - y_i + y_k } }\)

In (3), factor $(-1)^{n+1}$ from the numerator and $(-1)^{n-1}$ from the denominator.

Then $(-1)^{n+1} = (-1)^{n-1}$ verifies that (3) matches (4). $\blacksquare$

Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Inverse_of_Cauchy_Matrix&oldid=476311"