matrix_q_permanent_three_of_diag_one
For any real symmetric 3-by-3 matrix A with all diagonal entries equal to 1, writing x = A 0 1, y = A 1 2, and z = A 0 2, the q-permanent of A at q equals 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3.
Statement
theorem matrix_q_permanent_three_of_diag_one (A : Matrix (Fin 3) (Fin 3) ℝ) (hsymm : A.IsSymm) (hdiag : ∀ i, A i i = 1) (q : ℝ) : let x := A 0 1 let y := A 1 2 let z := A 0 2 matrix_q_permanent q A = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3
- Formalizes
- arXiv:2611.14694, Proof of Proposition 5.1 -- Real positive definite counterexamples to a monotonicity conjecture for the q-permanent
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matrix_q_permanentThe q-permanent of an n-by-n matrix M over a commutative semiring R at parameter q in R is the sum over all permutations sigma of Fin n of…
- Used by 1
- matrix_q_permanent_strict_mono_of_order_le_threeIf A is a non-diagonal real positive definite matrix of order n ≤ 3, then the function mapping q to the q-permanent of A is strictly…
Read back from the Lean
For every 3 × 3 real matrix A and every real number q, if A is symmetric (A.IsSymm) and every diagonal entry of A is 1 (∀ i : Fin 3, A i i = 1), then the q-permanent of A is equal to 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3, where x = A 0 1, y = A 1 2, and z = A 0 2.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof evaluates the q-permanent of a 3x3 symmetric matrix with unit diagonal by explicit expansion over the symmetric group S₃. It defines all six permutations of three elements, computes their inversion counts to determine the exponents of q, and expands each product of matrix entries. Using the unit diagonal entries (A i i = 1) and symmetry (A j i = A i j) reduces the matrix entries to the parameters x = A 0 1, y = A 1 2, and z = A 0 2, after which polynomial ring arithmetic simplifies the sum to the claimed expression.
The variables x, y, z are introduced for the off-diagonal entries, and the six permutations p0 through p5 of {0, 1, 2} are defined.
We name the off-diagonal entries x = A 0 1, y = A 1 2, and z = A 0 2. We then define all six elements of the symmetric group S₃: the identity p0 = 1, the three transpositions p1 = (0 1), p2 = (1 2), and p3 = (0 2), and the two 3-cycles p4 = (0 1)(1 2) and p5 = (1 2)(0 1).
intro x y z let p0 : Equiv.Perm (Fin 3) := 1 let p1 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 let p2 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 let p3 : Equiv.Perm (Fin 3) := Equiv.swap 0 2 let p4 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 * Equiv.swap 1 2 let p5 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 * Equiv.swap 0 1
The definition of the q-permanent is unfolded and the sum over all permutations is expanded into six explicit summands.
Unfolding `matrix_q_permanent` writes the q-permanent as the sum over all permutations σ of q^(inv σ) ∏ i, A i (σ i). Lean verifies by computational evaluation (`decide`) that the universe of permutations of Fin 3 is precisely {p0, p1, p2, p3, p4, p5} and that these six elements are distinct. We then peel off each permutation one by one using `Finset.sum_insert` and finish with `Finset.sum_singleton`.
uses
Finset.sum_insert,Finset.sum_singletonunfold matrix_q_permanent have h_univ : (Finset.univ : Finset (Equiv.Perm (Fin 3))) = {p0, p1, p2, p3, p4, p5} := by decide rw [show (∑ σ : Equiv.Perm (Fin 3), _) = ∑ σ ∈ (Finset.univ : Finset (Equiv.Perm (Fin 3))), _ from rfl] rw [h_univ] have ne0 : p0 ∉ ({p1, p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne1 : p1 ∉ ({p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne2 : p2 ∉ ({p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne3 : p3 ∉ ({p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne4 : p4 ∉ ({p5} : Finset (Equiv.Perm (Fin 3))) := by decide rw [Finset.sum_insert ne0, Finset.sum_insert ne1, Finset.sum_insert ne2, Finset.sum_insert ne3, Finset.sum_insert ne4, Finset.sum_singleton] dsimp only
The inversion count of each permutation is determined and substituted into the powers of q.
The number of inversions |{(i, j) : i < j ∧ σ j < σ i}| for each permutation is verified by finite evaluation (`decide`): p0 has 0 inversions; the transpositions p1 and p2 each have 1 inversion; the long transposition p3 has 3 inversions; and the 3-cycles p4 and p5 each have 2 inversions. Rewriting these values simplifies the powers of q across the six terms to q^0, q^1, q^1, q^3, q^2, and q^2.
have h_inv0 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p0 p.2 < p0 p.1)).card = 0 := by decide have h_inv1 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p1 p.2 < p1 p.1)).card = 1 := by decide have h_inv2 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p2 p.2 < p2 p.1)).card = 1 := by decide have h_inv3 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p3 p.2 < p3 p.1)).card = 3 := by decide have h_inv4 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p4 p.2 < p4 p.1)).card = 2 := by decide have h_inv5 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p5 p.2 < p5 p.1)).card = 2 := by decide rw [h_inv0, h_inv1, h_inv2, h_inv3, h_inv4, h_inv5]
Each product ∏ i, A i (σ i) is expanded into A 0 (σ 0) * A 1 (σ 1) * A 2 (σ 2) and evaluated at the concrete indices.
We apply `Fin.prod_univ_three` to each of the six summands to expand the product over {0, 1, 2} into the product of three matrix entries. The values of each permutation on each input index are verified by definition (`rfl`), and rewriting them produces explicit entries such as A 0 1 * A 1 0 * A 2 2 for p1.
uses
Fin.prod_univ_threerepeat rw [Fin.prod_univ_three] have hp0_0 : p0 0 = 0 := rfl have hp0_1 : p0 1 = 1 := rfl have hp0_2 : p0 2 = 2 := rfl have hp1_0 : p1 0 = 1 := rfl have hp1_1 : p1 1 = 0 := rfl have hp1_2 : p1 2 = 2 := rfl have hp2_0 : p2 0 = 0 := rfl have hp2_1 : p2 1 = 2 := rfl have hp2_2 : p2 2 = 1 := rfl have hp3_0 : p3 0 = 2 := rfl have hp3_1 : p3 1 = 1 := rfl have hp3_2 : p3 2 = 0 := rfl have hp4_0 : p4 0 = 1 := rfl have hp4_1 : p4 1 = 2 := rfl have hp4_2 : p4 2 = 0 := rfl have hp5_0 : p5 0 = 2 := rfl have hp5_1 : p5 1 = 0 := rfl have hp5_2 : p5 2 = 1 := rfl rw [hp0_0, hp0_1, hp0_2, hp1_0, hp1_1, hp1_2, hp2_0, hp2_1, hp2_2, hp3_0, hp3_1, hp3_2, hp4_0, hp4_1, hp4_2, hp5_0, hp5_1, hp5_2]
The unit diagonal values and the symmetry of A are substituted into each term.
From the hypothesis that all diagonal entries are 1, we obtain A 0 0 = 1, A 1 1 = 1, and A 2 2 = 1. From the symmetry of A, lower-triangular entries equal their upper-triangular counterparts: A 1 0 = A 0 1 = x, A 2 1 = A 1 2 = y, and A 2 0 = A 0 2 = z. Rewriting these equations expresses every factor in all six summands in terms of 1, x, y, and z.
have hd0 : A 0 0 = 1 := hdiag 0 have hd1 : A 1 1 = 1 := hdiag 1 have hd2 : A 2 2 = 1 := hdiag 2 have hs01 : A 1 0 = A 0 1 := hsymm.apply 0 1 have hs12 : A 2 1 = A 1 2 := hsymm.apply 1 2 have hs02 : A 2 0 = A 0 2 := hsymm.apply 0 2 rw [hd0, hd1, hd2, hs01, hs12, hs02]
The sum of the six terms simplifies algebraically to 1 + (x^2 + y^2) * q + 2 * x * y * z * q^2 + z^2 * q^3. automation
We rewrite the goal to show that 1 * (1 * 1 * 1) + q^1 * (x * x * 1) + q^1 * (1 * y * y) + q^3 * (z * 1 * z) + q^2 * (x * y * z) + q^2 * (z * x * y) equals the target polynomial. The `ring` tactic expands and groups like powers of q, matching the constant term 1, the q coefficient x^2 + y^2, the q^2 coefficient xyz + zxy = 2xyz, and the q^3 coefficient z^2.
change 1 * (1 * 1 * 1) + (q ^ 1 * (x * x * 1) + (q ^ 1 * (1 * y * y) + (q ^ 3 * (z * 1 * z) + (q ^ 2 * (x * y * z) + q ^ 2 * (z * x * y))))) = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3 ring
Finset.sum_insert- If an element a is not in a finite set s, then the sum of a function over s ∪ {a} equals its value at a plus its sum over s.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals its value at a.
Fin.prod_univ_three- The product of a function over the three-element set {0, 1, 2} equals f 0 * f 1 * f 2.
- The enumeration of the symmetric group on three elements, the pairwise distinctness of the six permutations, and their inversion counts are checked by finite evaluation via Lean's `decide` tactic rather than by group-theoretic arguments.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The q-permanent of a real symmetric 3x3 matrix with unit diagonal equals 1 + (x^2+y^2)q + 2xyz q^2 + z^2 q^3. -/theorem matrix_q_permanent_three_of_diag_one (A : Matrix (Fin 3) (Fin 3) ℝ) (hsymm : A.IsSymm) (hdiag : ∀ i, A i i = 1) (q : ℝ) : let x := A 0 1 let y := A 1 2 let z := A 0 2 matrix_q_permanent q A = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3 := by intro x y z let p0 : Equiv.Perm (Fin 3) := 1 let p1 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 let p2 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 let p3 : Equiv.Perm (Fin 3) := Equiv.swap 0 2 let p4 : Equiv.Perm (Fin 3) := Equiv.swap 0 1 * Equiv.swap 1 2 let p5 : Equiv.Perm (Fin 3) := Equiv.swap 1 2 * Equiv.swap 0 1 unfold matrix_q_permanent have h_univ : (Finset.univ : Finset (Equiv.Perm (Fin 3))) = {p0, p1, p2, p3, p4, p5} := by decide rw [show (∑ σ : Equiv.Perm (Fin 3), _) = ∑ σ ∈ (Finset.univ : Finset (Equiv.Perm (Fin 3))), _ from rfl] rw [h_univ] have ne0 : p0 ∉ ({p1, p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne1 : p1 ∉ ({p2, p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne2 : p2 ∉ ({p3, p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne3 : p3 ∉ ({p4, p5} : Finset (Equiv.Perm (Fin 3))) := by decide have ne4 : p4 ∉ ({p5} : Finset (Equiv.Perm (Fin 3))) := by decide rw [Finset.sum_insert ne0, Finset.sum_insert ne1, Finset.sum_insert ne2, Finset.sum_insert ne3, Finset.sum_insert ne4, Finset.sum_singleton] dsimp only have h_inv0 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p0 p.2 < p0 p.1)).card = 0 := by decide have h_inv1 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p1 p.2 < p1 p.1)).card = 1 := by decide have h_inv2 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p2 p.2 < p2 p.1)).card = 1 := by decide have h_inv3 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p3 p.2 < p3 p.1)).card = 3 := by decide have h_inv4 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p4 p.2 < p4 p.1)).card = 2 := by decide have h_inv5 : ((Finset.univ : Finset (Fin 3 × Fin 3)).filter (fun p => p.1 < p.2 ∧ p5 p.2 < p5 p.1)).card = 2 := by decide rw [h_inv0, h_inv1, h_inv2, h_inv3, h_inv4, h_inv5] repeat rw [Fin.prod_univ_three] have hp0_0 : p0 0 = 0 := rfl have hp0_1 : p0 1 = 1 := rfl have hp0_2 : p0 2 = 2 := rfl have hp1_0 : p1 0 = 1 := rfl have hp1_1 : p1 1 = 0 := rfl have hp1_2 : p1 2 = 2 := rfl have hp2_0 : p2 0 = 0 := rfl have hp2_1 : p2 1 = 2 := rfl have hp2_2 : p2 2 = 1 := rfl have hp3_0 : p3 0 = 2 := rfl have hp3_1 : p3 1 = 1 := rfl have hp3_2 : p3 2 = 0 := rfl have hp4_0 : p4 0 = 1 := rfl have hp4_1 : p4 1 = 2 := rfl have hp4_2 : p4 2 = 0 := rfl have hp5_0 : p5 0 = 2 := rfl have hp5_1 : p5 1 = 0 := rfl have hp5_2 : p5 2 = 1 := rfl rw [hp0_0, hp0_1, hp0_2, hp1_0, hp1_1, hp1_2, hp2_0, hp2_1, hp2_2, hp3_0, hp3_1, hp3_2, hp4_0, hp4_1, hp4_2, hp5_0, hp5_1, hp5_2] have hd0 : A 0 0 = 1 := hdiag 0 have hd1 : A 1 1 = 1 := hdiag 1 have hd2 : A 2 2 = 1 := hdiag 2 have hs01 : A 1 0 = A 0 1 := hsymm.apply 0 1 have hs12 : A 2 1 = A 1 2 := hsymm.apply 1 2 have hs02 : A 2 0 = A 0 2 := hsymm.apply 0 2 rw [hd0, hd1, hd2, hs01, hs12, hs02] change 1 * (1 * 1 * 1) + (q ^ 1 * (x * x * 1) + (q ^ 1 * (1 * y * y) + (q ^ 3 * (z * 1 * z) + (q ^ 2 * (x * y * z) + q ^ 2 * (z * x * y))))) = 1 + (x ^ 2 + y ^ 2) * q + 2 * x * y * z * q ^ 2 + z ^ 2 * q ^ 3 ring