A combinatorial proof of Cramer’s Rule

Doron ZEILBERGER

Dedicated to my Rutgers colleague Antoni A. Kosinski (b. May 25, 1930) who proved that Cramer’s Rule is indeed due to Cramer.

Prerequisites: We assume that readers are familiar with the notions of : integer (e.g. 3, 11), set (e.g. {1, 2, 3}), addition (of numbers or symbols) (e.g. a + b) , multiplication (e.g. bc), and “> , = , < , ≤ , ≥”. Two symbols a and b commute if ab = ba. All the symbols in this paper commute. No other knowledge is needed!

Notation: If w is a weight defined on a set S (i.e. a way of assigning a number, or algebraic expression to members of S), then w(S) := ∑_{s∈S} w(s). For example if S = {1, 4}, w(1) = a, w(4) = b, then w({1, 4}) = a + b.

Definitions

• For any positive integer n, an n-permutation is a list of integers π = π_{1} … π_{n}, where 1 ≤ π_{i} ≤ n for all 1 ≤ i ≤ n and π_{i} ≠ π_{j} if i ≠ j.

• The set of all n-permutations is denoted by S_{n}. For example, S_{3} = {123, 132, 213, 231, 312, 321}.

• For an n-permutation π = π_{1} … π_{n}, a pair (i, j), where 1 ≤ i < j ≤ n, is an inversion if π_{i} > π_{j}. For example, If π = 51423 then (1, 2), (1, 3), (1, 4), (1, 5), (3, 4), (3, 5) are inversions of π. Let inv(π) be the number of inversions, for example inv(51423) = 6.

• Let n be a positive integer, and let a_{i,j}(1 ≤ i, j ≤ n) and b_{i} (1 ≤ i ≤ n) be n^{2} + n commuting symbols (or numbers). Define n + 1 weights w_{j} (0 ≤ j ≤ n) on S_{n} as follows:

w_{0}(π) := (−1)^{inv(π)} ∏_{1≤k≤n} a_{π_{k},k} ,

w_{j}(π) := (−1)^{inv(π)} b_{π_{j}} ∏_{{1≤k≤n \atop k≠j}} a_{π_{k},k} (1 ≤ j ≤ n) .

Theorem (Cramer [C]): Let

X_{j} := w_{j}(S_{n}) (0 ≤ j ≤ n) ,

then

x_{j} := \frac{X_{j}}{X_{0}} (1 ≤ j ≤ n) ,

satisfy the n linear equations

∑_{j=1}^{n} a_{i,j}x_{j} = b_{i} (1 ≤ i ≤ n) .  (C_{i})

Combinatorial Proof: By multiplying (C_{i}) by X_{0}, we have to prove

∑_{j=1}^{n} a_{i,j}X_{j} = b_{i}X_{0} (1 ≤ i ≤ n) .  (C′_{i})

For any positive integer n, let F_{n} be the following set (with n · n! members, where n! := 1 · 2 ⋯ n) F_{n} := {[j, π] ; 1 ≤ j ≤ n , π ∈ S_{n}} .

For any i (1 ≤ i ≤ n), define a weight W_{i} on F_{n} as follows:

W_{i}([j, π]) := a_{i,j}w_{j}(π) = a_{i,j}(−1)^{inv(π)}b_{π_{j}} ∏_{{1≤k≤n \atop k≠j}} a_{π_{k},k} .

The left side of (C′_{i}) is W_{i}(F_{n}). Definition: [j, π] ∈ F_{n} is an i-good guy if π_{j} = i, otherwise it is an i-bad guy. Let G_{n,i} and B_{n,i} be the subsets of F_{n} consisting of the i-good guys and i-bad guys respectively. Obviously, since F_{n} = G_{n,i} ∪ B_{n,i}, we have

W_{i}(F_{n}) = W_{i}(G_{n,i}) + W_{i}(B_{n,i}) .

Fact 1:

W_{i}(G_{n,i}) = b_{i} X_{0}

Proof of Fact 1: If [j, π] ∈ F_{n} is a good guy then, since π_{j} = i, we have:

W_{i}([j, π]) = (−1)^{inv(π)} a_{i,j} b_{π_{j}} ∏_{{1≤k≤n \atop k≠j}} a_{π_{k},k}

= (−1)^{inv(π)} a_{π_{j},j} b_{i} ∏_{{1≤k≤n \atop k≠j}} a_{π_{k},k} = (−1)^{inv(π)} b_{i} ∏_{1≤k≤n} a_{π_{k},k} = b_{i}w_{0}(π) .

Hence W_{i}(G_{n,i}) = b_{i}w_{0}(S_{n}) = b_{i}X_{0}. Fact 2:

W_{i}(B_{n,i}) = 0 .

Proof of Fact 2: Let [j, π] ∈ F_{n} be an i-bad guy. Let a := π_{j} and j′ := π^{−1}(i). Of course a ≠ i and j′ ≠ j. Define a permutation σ by transposing π_{j} = a and π_{j′} = i, in other words σ_{j} = i, σ_{j′} = a and σ_{k} = π_{k} if k ∉ {j, j′}. Let

T_{i}([j, π]) := [j′, σ] .

We have

W_{i}([j, π]) = (−1)^{inv(π)} a_{i,j} b_{a} ∏_{{1≤k≤n \atop k≠j}} a_{π_{k},k} = (−1)^{inv(π)}a_{i,j} b_{a} a_{π_{j′} ,j′} ∏_{{1≤k≤n \atop k≠j,j′}} a_{π_{k},k}

= (−1)^{inv(π)} a_{i,j} b_{a} a_{i,j′} ∏_{{1≤k≤n \atop k≠j,j′}} a_{π_{k},k} .

Similarly

W_{i}([j′, σ]) = (−1)^{inv(σ)} a_{i,j′} b_{a} ∏_{{1≤k≤n \atop k≠j′}} a_{σ_{k},k} = (−1)^{inv(σ)} a_{i,j′} b_{a} a_{σ_{j},j} ∏_{{1≤k≤n \atop k≠j,j′}} a_{σ_{k},k}

= (−1)^{inv(σ)} a_{i,j′} b_{a} a_{i,j} ∏_{{1≤k≤n \atop k≠j,j′}} a_{σ_{k},k} .

Since inv(π)−inv(σ) is odd (why?), and π_{k} and σ_{k} coincide if k ∉ {j, j′}, we have, by commutativity, that for any i-bad guy b, W_{i}(b) + W_{i}(T_{i}(b)) = 0.

Since T_{i}(T_{i}(b)) = b for all i-bad guys b (why?), all the bad guys can be arranged into mutually W_{i}-canceling pairs, proving Fact 2.

Combining Facts 1 and 2, (C′_{i}), and hence Cramer’s Rule, follow.

Comments: 1. There are several ‘short’ proofs of Cramer’s rule that can be found in Wikipedia and its references, but they all assume knowledge of linear algebra. Our proof is fully self-contained, and does not assume anything besides the prerequisites listed at the beginning. We believe that if you include all the necessary background, our proof is the shortest.

2. For a fascinating defense of Gabriel Cramer’s priority for his rule, see Antoni Kosinski’s article [K].

References

[C] Gabriel Cramer, “Introduction l’Analyse des lignes Courbes algébriques” Geneva (1750). pp. 656-659.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cramerCramer1750.pdf .

[K] A. A. Kosinski, Cramer’s Rule is due to Cramer, Mathematics Magazine 74 (2001), 310-312.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cramerKosinski2001.pdf

.

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Aug. 18, 2024. Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org