Section 1.2.3: Sums and Products

Exercise 39. [M23] Show that the inverse of a combinatorial matrix is a combinatorial matrix with the entries $b_{ij} = (-y + \delta_{ij}(x + ny)) / x(x + ny)$.

Verified: yes
Solve time: 2m20s

Solution

Let $A = (a_{ij})_{1 \le i,j \le n}$ be the combinatorial matrix, where

$a_{ij} = x\delta_{ij} + y.$

Thus

$A = xI + yJ,$

where $I$ is the identity matrix and $J$ is the matrix whose entries are all equal to $1$.

We are to show that the inverse matrix $B = (b_{ij})$ is again combinatorial, with entries

$b_{ij} = \frac{-y + \delta_{ij}(x+ny)}{x(x+ny)}.$

Define

$B = \frac1{x(x+ny)}\bigl((x+ny)I - yJ\bigr).$

Then indeed

= \frac{(x+ny)\delta_{ij}-y}{x(x+ny)} = \frac{-y+\delta_{ij}(x+ny)}{x(x+ny)}.$$ It remains to verify that $AB=I$. Since $J^2=nJ$, because each entry of $J^2$ is $$\sum_{k=1}^n 1\cdot1=n,$$ we have \begin{aligned} AB &= (xI+yJ)\frac1{x(x+ny)}\bigl((x+ny)I-yJ\bigr)
&= \frac1{x(x+ny)} \bigl( x(x+ny)I -xyJ +y(x+ny)J -y^2J^2 \bigr). \end{aligned} Substituting $J^2=nJ$ gives \begin{aligned} AB &= \frac1{x(x+ny)} \bigl( x(x+ny)I -xyJ +y(x+ny)J -ny^2J \bigr). \end{aligned} The coefficient of $J$ is -xy + y(x+ny) - ny^2 = -xy + xy + ny^2 - ny^2 =0. $$Hence$$

AB

\frac1{x(x+ny)}x(x+ny)I

I. Similarly, $$BA=I,$$ since the same computation applies. Therefore $B=A^{-1}$. Consequently the inverse of a combinatorial matrix is again a combinatorial matrix, with entries $$\boxed{ b_{ij}= \frac{-y+\delta_{ij}(x+ny)}{x(x+ny)} }.

This completes the proof.

∎