求证元素为组合数的n阶矩阵逆矩阵形式并求更多解法

Great question! Let's explore several alternative methods to prove that the inverse of the (n \times n) matrix (A = \left(\binom{j-1}{k-1}\right)) (where (\binom{j-1}{k-1} = 0) when (k > j)) is given by (A^{-1} = \left((-1)^{j+k}\binom{j-1}{k-1}\right)). Beyond induction and Gaussian elimination, here are some clear, intuitive approaches:

1. Direct Matrix Multiplication with Combinatorial Identities #

The most straightforward algebraic approach is to directly compute the product (A \cdot B) (where (B = A^{-1}) as hypothesized) and show it equals the identity matrix (I).

For any (i, j) (1 ≤ (i,j) ≤ n), the ((i,j))-th entry of (A \cdot B) is:
[
(AB){ij} = \sum{k=1}^n A_{ik}B_{kj} = \sum_{k=1}^{\min(i,j)} \binom{i-1}{k-1} \cdot (-1)^{k+j} \binom{k-1}{j-1}
]

Key Cases: #

• When (i = j): Only the term where (k = i) is non-zero (since (\binom{k-1}{i-1} = 0) for (k < i)). This gives:
  [
  (AB)_{ii} = \binom{i-1}{i-1} \cdot (-1)^{i+i} \cdot \binom{i-1}{i-1} = 1 \cdot 1 \cdot 1 = 1
  ]
• When (i > j): Use the combinatorial identity (\binom{i-1}{k-1}\binom{k-1}{j-1} = \binom{i-1}{j-1}\binom{i-j}{k-j}) to reindex the sum. Substituting this in, we get:
  [
  (AB){ij} = (-1)^j \binom{i-1}{j-1} \sum{t=0}^{i-j} \binom{i-j}{t} (-1)^{t+j}
  ]
  The sum simplifies to ((1-1)^{i-j} = 0) (since (i-j > 0)), so ((AB)_{ij} = 0).

Since (A) and (B) are both lower triangular, we only need to verify these cases to confirm (AB = I), and thus (B = A^{-1}).

2. Generating Function Perspective #

Matrix (A) corresponds to a linear transformation on sequences, and generating functions make this transformation (and its inverse) intuitive.

Suppose we have a vector (x = (x_1, x_2, ..., x_n)) with generating function (X(t) = x_1 + x_2 t + x_3 t^2 + ... + x_n t^{n-1}). When we apply (A) to (x) to get (y = Ax), the (i)-th component of (y) is:
[
y_i = \sum_{k=1}^i \binom{i-1}{k-1} x_k
]

The generating function for (y) simplifies to (Y(t) = \frac{X(t)}{1-t}) (for the infinite case; finite (n) behaves similarly with negligible higher-order terms). To reverse this transformation, we multiply by ((1-t)):
[
X(t) = Y(t)(1-t)
]

Expanding this gives the inverse transformation:
[
x_i = \sum_{k=1}^i (-1)^{i-k} \binom{i-1}{k-1} y_k
]
Since ((-1)^{i-k} = (-1)^{i+k}), this is exactly the transformation represented by matrix (B = \left((-1)^{j+k}\binom{j-1}{k-1}\right)).

3. Recursive Calculation for Lower Triangular Matrices #

Since (A) is a lower triangular matrix with 1s on its diagonal ((\binom{i-1}{i-1} = 1)), its inverse is also lower triangular. We can use recursive properties of lower triangular matrix inverses to derive (A^{-1}).

For lower triangular matrices (A = (a_{ij})) and (A^{-1} = (b_{ij})):

• Diagonal entries: (b_{ii} = \frac{1}{a_{ii}} = 1)
• For (i > j): (\sum_{k=j}^i a_{ik} b_{kj} = 0), which rearranges to:
  [
  b_{ij} = - \sum_{k=j+1}^i a_{ik} b_{kj}
  ]

We prove (b_{ij} = (-1)^{i+j} \binom{i-1}{j-1}) by induction on (i-j):

• Base case: (i-j=0) (diagonal): (b_{ii} = 1 = (-1)^{2i} \binom{i-1}{i-1}), which holds.
• Inductive step: Assume the formula holds for all (i-j < m). For (i-j = m > 0), substitute the inductive hypothesis into the recursive formula and use the same combinatorial identity from Method 1 to simplify the sum to ((-1)^{i+j} \binom{i-1}{j-1}).

4. Combinatorial Interpretation: Signed Path Counting #

We can interpret matrix entries as path counts to gain intuition about why the inverse has signed entries:

• (A_{ij} = \binom{i-1}{j-1}) counts the number of non-decreasing paths from position (j) to (i) (choosing (j-1) "stops" along (i-1) steps).
• (B_{ij} = (-1)^{i+j} \binom{i-1}{j-1}) represents signed path counts, where each path contributes a sign of ((-1)^{i-j}) (since ((-1)^{i+j} = (-1)^{i-j})).

When computing (AB), the ((i,j))-th entry sums (paths from (k) to (i)) × (signed paths from (j) to (k)) over all (k):

• For (i ≠ j), paths cancel pairwise: every path from (j) to (i) pairs with a path that takes an extra "backward" step, leading to opposite signs and a total sum of 0.
• For (i = j), only the trivial path (staying at (i)) contributes, giving a sum of 1.

This combinatorial framing explains why the inverse has this form, not just that it does.

内容的提问来源于stack exchange，提问作者Henry