comparison_pi_ord_mulVec_phi2
Pi_ord fixes the quadratic evaluation vector phi_2(x) of every strict order x: U_triangle^T phi_2(x) = 0 by the triangle relations, hence also v_triangle^T phi_2(x) = 0.
Statement
theorem comparison_pi_ord_mulVec_phi2 (n : ℕ) (x : Equiv.Perm (Fin n)) :
Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x- Source
- Step of arXiv:2610.34762 (Quantum ordinal selection with two comparisons), Section 3.1, Lemma 1 (quadratic_comparison_evaluation_kernel_and_projector)
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- comparison_pi_ordThe real square matrix Pi_ord on comparison_feature2 n defined by Pi_ord = I - (1/3) U U^T + (1 / (3 (C(n,3) + 3))) v v^T, where U =…
- comparison_triangle_kappa_mem_eval_kerEach triangle relation vector kappa_abc evaluates to zero on every strict order: d_ab d_ac - d_ab d_bc + d_ac d_bc - 1 = 0.
- comparison_eval_matrixThe real evaluation matrix of F_2 on strict orders, with rows indexed by the permutations x of Fin n (strict orders given by ranks) and…
- comparison_phi2The real quadratic evaluation vector phi_2(x) : comparison_feature2 n → ℝ of a strict order x (a permutation of Fin n giving the ranks):…
- comparison_triangle_matrixThe real matrix U_triangle with rows indexed by comparison_feature2 n and columns by triangles, whose column at the triangle t is the…
- comparison_feature2The type indexing the orthonormal coordinate basis of the formal quadratic feature space F_2 = span{1, d_e, d_e d_f}: the sum type of…
- comparison_edgeThe type of edges of the label set [n] = Fin n: the subtype of pairs (a, b) in Fin n × Fin n with a < b, each unordered edge {a, b} being…
- comparison_triangle_kappaThe real triangle relation vector kappa_abc : comparison_feature2 n → ℝ of a triangle a < b < c: kappa_abc = e_(ab,ac) - e_(ab,bc) +…
- comparison_triangleThe type of triangles of the label set [n] = Fin n: the subtype of triples (a, (b, c)) in Fin n × Fin n × Fin n with a < b and b < c.
- Used by 1
- quadratic_comparison_evaluation_kernel_and_projectorLet n >= 3, N = C(n,2), nu_triangle = C(n,3). Strict orders on [n] are given by permutations x of Fin n (x i = rank of label i); for an…
The proof, explained
The theorem proves that the projection matrix $\Pi_{\mathrm{ord}}$ fixes the quadratic evaluation vector $\phi_2(x)$ of any strict order (permutation) $x$. By definition, $\Pi_{\mathrm{ord}} = I - \frac{1}{3} U U^T + c v v^T$, where $U$ encodes the triangle relations and $v = U \mathbf{1}$. Because every valid order satisfies all triangle relations, $\phi_2(x)$ is orthogonal to every column of $U$, giving $U^T \phi_2(x) = 0$ and consequently $v \cdot \phi_2(x) = 0$. Distributing $\Pi_{\mathrm{ord}} \phi_2(x)$ across the linear combination eliminates both correction terms, leaving only the identity component $\phi_2(x)$.
The feature vector $\phi_2(x)$ is orthogonal to the triangle constraint matrix from the left: $\phi_2(x) U = 0$.
For any triangle $t$, the $t$-th column of $U$ is the triangle relation vector $\kappa_t$. By `comparison_triangle_kappa_mem_eval_ker`, every $\kappa_t$ lies in the kernel of the evaluation matrix, so evaluating it at the permutation $x$ yields zero. Applying function congruence (`congrFun`) at $x$ and expanding the definitions of vector-matrix multiplication and dot product shows that the $t$-th entry of the row-matrix product $\phi_2(x) U$ is zero.
uses
congrFun,comparison_triangle_kappa_mem_eval_ker,mul_commclassical have hU : Matrix.vecMul (comparison_phi2 x) (comparison_triangle_matrix n) = 0 := by funext t have := congrFun (comparison_triangle_kappa_mem_eval_ker n t) x simpa [Matrix.vecMul, Matrix.mulVec, dotProduct, comparison_triangle_matrix, comparison_eval_matrix, mul_comm] using this
The dot product of the column-sum vector $v = U \mathbf{1}$ with $\phi_2(x)$ is zero: $v \cdot \phi_2(x) = 0$.
By commutativity of the dot product (`dotProduct_comm`) and the adjoint identity $w \cdot (U \mathbf{1}) = (w U) \cdot \mathbf{1}$ (`Matrix.dotProduct_mulVec`), $v \cdot \phi_2(x)$ equals $(\phi_2(x) U) \cdot \mathbf{1}$. Because $\phi_2(x) U = 0$, this evaluates to $0 \cdot \mathbf{1} = 0$ (`zero_dotProduct`).
uses
dotProduct_comm,Matrix.dotProduct_mulVec,zero_dotProducthave hv : dotProduct (Matrix.mulVec (comparison_triangle_matrix n) (fun _ => 1)) (comparison_phi2 x) = 0 := by rw [dotProduct_comm, Matrix.dotProduct_mulVec, hU, zero_dotProduct]
The transposed triangle matrix annihilates $\phi_2(x)$: $U^T \phi_2(x) = 0$.
Multiplying a vector by the transpose of a matrix from the left is the same as multiplying the row vector by the matrix from the right (`Matrix.mulVec_transpose`), so $U^T \phi_2(x) = \phi_2(x) U = 0$.
uses
Matrix.mulVec_transposehave hUt : Matrix.mulVec (comparison_triangle_matrix n).transpose (comparison_phi2 x) = 0 := by rw [Matrix.mulVec_transpose, hU]
Applying $\Pi_{\mathrm{ord}}$ to $\phi_2(x)$ leaves $\phi_2(x)$ unchanged, because the correction terms vanish.
Unfolding the definition of $\Pi_{\mathrm{ord}}$ reveals it as the identity matrix minus a multiple of $U U^T$ plus a multiple of the outer product $v v^T$. Distributing the matrix-vector multiplication over addition, subtraction, and scalar multiplication turns the $U U^T$ term into $U (U^T \phi_2(x))$ via `Matrix.mulVec_mulVec` and the $v v^T$ term into $(v \cdot \phi_2(x)) v$ via `Matrix.vecMulVec_mulVec`. Since $U^T \phi_2(x) = 0$ and $v \cdot \phi_2(x) = 0$, both correction terms vanish ($U 0 = 0$), leaving $I \phi_2(x) = \phi_2(x)$.
uses
Matrix.add_mulVec,Matrix.sub_mulVec,Matrix.one_mulVec,Matrix.smul_mulVec,Matrix.mulVec_mulVec,Matrix.mulVec_zero,Matrix.vecMulVec_mulVecunfold comparison_pi_ord simp only [] rw [Matrix.add_mulVec, Matrix.sub_mulVec, Matrix.one_mulVec, Matrix.smul_mulVec, Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hUt, Matrix.mulVec_zero, Matrix.vecMulVec_mulVec, hv] simp
comparison_triangle_kappa_mem_eval_ker- Evaluating any triangle relation vector against any permutation yields zero: the triangle relations lie in the kernel of the evaluation matrix.
congrFun- Equal functions take equal values at any argument.
mul_comm- Multiplication in a commutative magma is commutative ($a * b = b * a$).
dotProduct_comm- The dot product of two vectors is commutative ($v \cdot w = w \cdot v$).
Matrix.dotProduct_mulVec- Vector-matrix multiplication is adjoint to matrix-vector multiplication with respect to the dot product: $v \cdot (A w) = (v A) \cdot w$.
zero_dotProduct- The dot product of the zero vector with any vector is zero ($0 \cdot v = 0$).
Matrix.mulVec_transpose- Multiplying by the transpose of a matrix on the left is equivalent to multiplying by the matrix on the right: $A^T x = x A$.
Matrix.add_mulVec- Matrix-vector multiplication distributes over matrix addition: $(A + B) x = A x + B x$.
Matrix.sub_mulVec- Matrix-vector multiplication distributes over matrix subtraction: $(A - B) x = A x - B x$.
Matrix.one_mulVec- The identity matrix acts trivially on vectors: $I v = v$.
Matrix.smul_mulVec- Scalar multiplication factors out of matrix-vector multiplication: $(c \cdot M) v = c \cdot (M v)$.
Matrix.mulVec_mulVec- Matrix-vector multiplication associates with matrix multiplication: $M (N v) = (M N) v$.
Matrix.mulVec_zero- Multiplying any matrix by the zero vector gives the zero vector: $A 0 = 0$.
Matrix.vecMulVec_mulVec- Multiplying an outer product matrix $u v^T$ by a vector $w$ yields $(v \cdot w) u$.
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.
theorem comparison_pi_ord_mulVec_phi2 (n : ℕ) (x : Equiv.Perm (Fin n)) : Matrix.mulVec (comparison_pi_ord n) (comparison_phi2 x) = comparison_phi2 x := by classical have hU : Matrix.vecMul (comparison_phi2 x) (comparison_triangle_matrix n) = 0 := by funext t have := congrFun (comparison_triangle_kappa_mem_eval_ker n t) x simpa [Matrix.vecMul, Matrix.mulVec, dotProduct, comparison_triangle_matrix, comparison_eval_matrix, mul_comm] using this have hv : dotProduct (Matrix.mulVec (comparison_triangle_matrix n) (fun _ => 1)) (comparison_phi2 x) = 0 := by rw [dotProduct_comm, Matrix.dotProduct_mulVec, hU, zero_dotProduct] have hUt : Matrix.mulVec (comparison_triangle_matrix n).transpose (comparison_phi2 x) = 0 := by rw [Matrix.mulVec_transpose, hU] unfold comparison_pi_ord simp only [] rw [Matrix.add_mulVec, Matrix.sub_mulVec, Matrix.one_mulVec, Matrix.smul_mulVec, Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hUt, Matrix.mulVec_zero, Matrix.vecMulVec_mulVec, hv] simp