Sum of Elements in Inverse of Combinatorial Matrix
Jump to navigation
Jump to search
Theorem
Let $C_n$ be the combinatorial matrix of order $n$ given by:
- $C_n = \begin{bmatrix}
x + y & y & \cdots & y \\ y & x + y & \cdots & y \\ \vdots & \vdots & \ddots & \vdots \\ y & y & \cdots & x + y \end{bmatrix}$
Let $C_n^{-1}$ be its inverse, from Inverse of Combinatorial Matrix:
- $b_{i j} = \dfrac {-y + \delta_{i j} \paren {x + n y} } {x \paren {x + n y} }$
where $\delta_{i j}$ is the Kronecker delta.
The sum of all the elements of $C_n^{-1}$ is:
- $\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = \dfrac n {x + n y}$
Proof
All $n^2$ elements of $C_n^{-1}$ have a term $\dfrac {-y} {x \paren {x + n y} }$.
Further to this, the $n$ elements on the main diagonal contribute an extra $\dfrac {x + n y} {x \paren {x + n y} }$ to the total.
Hence:
\(\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j}\) | \(=\) | \(\ds n^2 \dfrac {-y} {x \paren {x + n y} } + n \dfrac {x + n y} {x \paren {x + n y} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {-n^2 y + n \paren {x + n y} } {x \paren {x + n y} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {-n^2 y + n x + n^2 y} {x \paren {x + n y} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n x} {x \paren {x + n y} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac n {x + n y}\) |
$\blacksquare$
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 $42$