TAOCP 1.2.3 Exercise 36

Exercise 36. [M23] Show that the determinant of the combinatorial matrix is $x^{n-1}(x + ny)$.

Verified: yes
Solve time: 45s

Solution

Let $A = (a_{ij})$ be the $n \times n$ combinatorial matrix with entries

$a_{ij} = y + \delta_{ij} x = \begin{cases} x + y, & i = j, \ y, & i \ne j. \end{cases}$

We want to show that $\det(A) = x^{n-1} (x + ny)$.

Consider subtracting the first row from each of the remaining $n-1$ rows. Let $A'$ denote the resulting matrix. Then, for $i \ge 2$:

The diagonal entries of the new $i$th row are $(x + y) - y = x$.
The off-diagonal entries are $y - y = 0$, except in the first column, which becomes $y - (x + y) = -x$ for the first column? Let's verify carefully.

Step by step: denote the rows as $R_1, R_2, \dots, R_n$. Perform the row operation:

$R_i \leftarrow R_i - R_1 \quad \text{for } i = 2, \dots, n.$

For $i \ge 2$, $j = 1$: $a'{i1} = a{i1} - a_{11} = y - (x + y) = -x$.
For $i \ge 2$, $j = i$: $a'_{ii} = (x + y) - y = x$.
For $i \ge 2$, $j \ne 1, j \ne i$: $a'_{ij} = y - y = 0$.
The first row $R_1$ remains $(x + y, y, \dots, y)$.

Thus the transformed matrix $A'$ has the form:

$$ A' = \begin{pmatrix} x + y & y & y & \cdots & y \ -x & x & 0 & \cdots & 0 \ -x & 0 & x & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ -x & 0 & 0 & \cdots & x \end{pmatrix}. $$

The determinant is unchanged by these row operations.

Expand $\det(A')$ along the first column:

$$ \det(A') = (x + y) \det(M_1) + \sum_{i=2}^n (-1)^{i+1} (-x) \det(M_i), $$

where $M_i$ is the $(n-1) \times (n-1)$ minor obtained by deleting row $i$ and column $1$. Observe that for $i \ge 2$, $M_i$ is upper-triangular with diagonal entries $x$, so $\det(M_i) = x^{n-2}$. The minor $M_1$ (deleting row 1 and column 1) is also upper-triangular with diagonal entries $x$, so $\det(M_1) = x^{n-1}$.

Hence,

$$ \det(A') = (x + y)x^{n-1} + \sum_{i=2}^n (-1)^{i+1}(-x) x^{n-2} = (x + y)x^{n-1} + x^{n-1} \sum_{i=2}^n (-1)^i. $$

Compute the sum $\sum_{i=2}^n (-1)^i$. There are $n-1$ terms:

If $n$ is even: $n-1$ is odd, so the sum equals $0$? Check carefully. Sum of geometric progression: $\sum_{i=2}^n (-1)^i = (-1)^2 + \dots + (-1)^n = \sum_{i=0}^{n-2} (-1)^{i+2} = \sum_{i=0}^{n-2} (-1)^i$.
Geometric series: $\sum_{i=0}^{n-2} (-1)^i = \frac{1 - (-1)^{n-1}}{1 - (-1)} = \frac{1 - (-1)^{n-1}}{2}$.

Rather than complicating, consider a simpler method using column operations:

Let $C_1, \dots, C_n$ denote columns. Subtract $C_1$ from each $C_j$ for $j = 2, \dots, n$:

New $C_j = C_j - C_1$ for $j \ge 2$.
In the first row: $(x + y, y, \dots, y) \mapsto (x + y, y - (x + y) = -x, \dots, -x)$.
In row $i \ge 2$: $C_1$ entry = $y$, $C_j$ entry = $y$ if $i \ne j$, $x + y$ if $i = j$. Then $C_j - C_1$ gives $0$ if $i \ne j$, $x + y - y = x$ if $i = j$.

Thus we obtain an upper-triangular matrix:

$$ \begin{pmatrix} x + y & -x & -x & \dots & -x \ y & x & 0 & \dots & 0 \ y & 0 & x & \dots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ y & 0 & 0 & \dots & x \end{pmatrix}. $$

Add all other columns $C_2, \dots, C_n$ to $C_1$:

First row, $C_1$: $(x + y) + (-x)(n-1) = x + y - x(n-1) = x - x(n-1) + y = x + ny - nx$? Better: compute carefully.

Better method: factor out.

Instead, use the eigenvalue argument. The combinatorial matrix is of the form:

$A = xI_n + y J_n,$

where $I_n$ is the $n \times n$ identity, $J_n$ is the $n \times n$ matrix of all 1's. The eigenvalues of $J_n$ are $n$ (for the vector of all ones) and $0$ (with multiplicity $n-1$). Hence, eigenvalues of $A$ are $x + ny$ (corresponding to eigenvector of all ones) and $x$ (with multiplicity $n-1$). Therefore,

$\det(A) = x^{n-1} (x + ny).$

This completes the proof.

∎

$\boxed{x^{n-1} (x + ny)}$