Polynomial-Time Decidability of Projection Commutativity on Finite-Dimensional Hilbert Spaces

Polynomial-Time Decidability of Projection Commutativity on Finite-Dimensional Hilbert Spaces Joaquim Reizi Higuchi November 17, 2025 Abstract We investigate the computational complexity of determining whether two orthogonal projections on a finite-dimensional complex Hilbert space commute. After formalizing the decision problem Proj-Commute with precise input encodings (rational matrix entries) and complexity models (both unit-cost arithmetic and bitcomplexity), we establish that the problem admits a deterministic polynomial-time algorithm. The standard approachcomputing the commutator [P, Q] = P Q −QP and testing for zerorequires O(dω) arithmetic operations, where d is the dimension and ω∈[2,3] denotes the matrix multiplication exponent, with O(d2) additional equality tests. The bit-complexity is polynomial in both d and the input precision. We also present equivalent operator-theoretic characterizations via simultaneous diagonalization and self-adjointness of the product P Q , which provide conceptual clarity and potential numerical advantages in certain settings. Keywords: orthogonal projections, commutator, polynomial-time algorithm, computational complexity, operator theory 1 Introduction Determining whether two linear operators commute is a fundamental question in operator theory with significant implications across spectral analysis, numerical linear algebra, quantum mechanics, and quantum information theory. For general operators, this question connects to deep structural properties of operator algebras and their representations [ 5 , 6 ]. In the special case where both operators are orthogonal projectionsself-adjoint idempotent operatorsthe commutativity criterion admits elegant characterizations that are both conceptually illuminating and algorithmically efficient. Classical results in matrix analysis establish that two orthogonal projections P and Q on a finite-dimensional Hilbert space commute if and only if they are simultaneously unitarily diagonalizable [ 1 , 2 ]. Equivalently, their product PQ is itself an orthogonal projection onto the intersection of their ranges, Ran(P)∩Ran(Q) [ 3 , 4 ]. These structural characterizations have been thoroughly studied in the operator-theoretic literature and find applications in quantum measurement theory [8,9] and signal processing [10]. From a computational perspective, verifying commutativity reduces to a straightforward matrix multiplication followed by an equality test. However, to establish a rigorous complexity-theoretic statement, one must carefully specify the input representation, the computational model, and provide tight bounds on both arithmetic and bit-complexity. 1 Surprisingly, despite the fundamental nature of this problem and its wide applicability, a systematic complexity-theoretic treatment appears to be absent from the literature. 1.1 Contributions and Structure The main contribution of this work is to provide a complete and rigorous analysis of the computational complexity of the projection commutativity problem. Specifically: 1. We formalize the decision problem Proj-Commute with precise specifications of input encodings (exact rational representations) and complexity models (unit-cost arithmetic over Qand standard bit-complexity on Turing machines). 2. We prove that Proj-Commute is decidable in deterministic polynomial time, with explicit bounds: O(dω) arithmetic operations where ω∈[2,3] is the matrix multiplication exponent, and polynomial bit-complexity in terms of dimension d and input precision B. 3. We present and prove several equivalent characterizations of projection commutativityvia the Frobenius norm of the commutator and via self-adjointness of the productthat offer conceptual insights and potential numerical advantages. 4. We discuss the relationship to numerical implementations and the modifications required for finite-precision arithmetic. The remainder of this paper is organized as follows. Section 2establishes notation, definitions, and the computational models. Section 3collects key structural and complexity lemmas. Section 4presents and proves the main theorem. Section 5concludes with a discussion of extensions and open questions. 2 Preliminaries and Definitions Throughout this work, we consider a finite-dimensional complex Hilbert space H≃Cd equipped with the standard inner product hx, yi=Pd j=1 xjyj . By fixing an orthonormal basis, we identify bounded linear operators on H with complex d×d matrices, denoted Md(C). Definition 2.1 (Orthogonal projection).An operator P∈Md(C) is an orthogonal projection if it satisfies two conditions: 1. Idempotency: P2=P 2. Self-adjointness: P=P∗ where P∗ denotes the conjugate transpose. Equivalently, P is the orthogonal projection onto its range Ran(P) = {Px :x∈H}. Definition 2.2 (Commutator).For matrices A, B ∈Md(C) , the commutator is defined as [A, B] = AB −BA. We say that Aand Bcommute if [A, B] = 0, equivalently if AB =BA. 2 Definition 2.3 (Input model).We consider as input two complex matrices P, Q ∈Md(C) . Each entry is given exactly as a complex number whose real and imaginary parts are rational numbers. A rational number is encoded in binary as an ordered pair (numerator, denominator) of signed/integer numerator and nonzero integer denominator; the raw input is not required to be in lowest terms nor to have a positive denominator. We fix the following canonical normal form for internal use: for a+ib ∈C with a, b ∈Q, a=α β, b =γ δ, α, γ ∈Z, β, δ ∈N,gcd(α, β) = gcd(γ, δ) = 1, β, δ > 0, and the sign is carried by the numerator (we also enforce 0=0/1 ). A deterministic preprocessing stepmoving signs to numerators and reducing by gcd converts any raw input to this canonical form; see Remark 3.6 for bitcomplexity bounds. Canonicalization does not increase bitlengths, so all asymptotic size parameters below are stable under this step. We track two size parameters with respect to the raw input. Let bmax denote the maximum binary bitlength of any numerator or denominator appearing in the input, and let Btot denote the total number of bits over all numerators and denominators across both matrices. Since there are 2d2 complex entries in (P, Q) and two rationals per complex entry, the matrix part of the input contains n= 4d2 rationals. For brevity we write B:= Btot . The dimension d∈N is encoded in binary using O(log d) bits; when referring to the full input size we may write Sin := B+O(log d) , but all our bounds are polynomial in (d, B), so the additive O(log d)term is immaterial and is not included in B. Finally, the decision problem Proj-Commute (Definition 2.5) is a promise problem in which P and Q are orthogonal projections; the present definition only specifies the encoding of matrix entries. Definition 2.4 (Complexity models).We analyze the computational cost using two standard models: 1. Arithmetic complexity: We work in the unit-cost algebraic computation model over Q (BSS model) [ 15 , 16 ]. A field operation means addition, subtraction, multiplication, or division. Equality/ordering tests over Q are permitted as unit-cost branch operations. When reporting costs we will explicitly state the number of field operations (e.g. O(dω) for matrix products) and, when relevant, the number of comparisons (typically O(d2)); in this model, both count as O(1) steps. 2. Bit complexity: The number of elementary bit operations on a deterministic Turing machine, accounting for the growth of intermediate rational numbers during computation (numerators/denominators kept in lowest terms) [ 13 , 14 , 17 ]. Equality testing of rationals is implemented by cross-multiplication. We write M(k) for the bit-cost of multiplying two k-bit integers. For matrix multiplication of d×d matrices, the arithmetic cost of the product is O(dω) field operations, where ω is the matrix multiplication exponent. Currently, ω < 2.372 [ 19 , 20 ], though for practical purposes and asymptotic analysis we use ω∈[2,3] . When an algorithm also performs entrywise comparisons, there are O(d2) additional unit-cost branch operations in the arithmetic model. Definition 2.5 (Decision problem Proj-Commute).• Input: A dimension d∈N (encoded in binary) and two matrices P, Q ∈Md(C) whose entries are given exactly in the canonical rational encoding of Definition 2.3. 3 • Promise: Both P and Q are orthogonal projections, i.e., P2=P , P=P∗ and Q2=Q,Q=Q∗. •Question: Decide whether PQ =QP holds (exact matrix equality over C). Remark 2.6. In practice, one may wish to first verify that the input matrices are indeed orthogonal projections by checking P2=P , P=P∗ , and similarly for Q . As we show in Lemma 3.5, this verification itself is polynomial-time. 3 Key Lemmas We now present the structural and complexity-theoretic lemmas that underpin our main result. These combine classical results from operator theory with explicit complexity bounds. Lemma 3.1 (Commuting normal matrices are simultaneously diagonalizable).Let A, B ∈ Md(C) be normal and suppose AB =BA . Then there exists a unitary matrix U such that both U∗AU and U∗BU are diagonal. In particular, if P, Q are orthogonal projections and PQ =QP , then there is an orthonormal basis in which both are diagonal with diagonal entries in {0,1}. Proof. We give a standard argument via spectral projections. Since Ais normal, by the spectral theorem there is an orthogonal decomposition Cd=M λ∈σ(A) Eλ, Eλ:= Ker(A−λI), and for each eigenvalue λthe orthogonal projection Pλonto Eλis a polynomial in A: pλ(z) := Y µ∈σ(A), µ6=λ z−µ λ−µ, Pλ=pλ(A). Because AB =BA , we have B pλ(A) = pλ(A)B , i.e. BPλ=PλB for every λ . Taking adjoints gives B∗Pλ=PλB∗ . Hence each Eλ= Ran(Pλ) is reducing for B (invariant for both Band B∗), and the restriction Bλ:= B|Eλis normal. For every λ∈σ(A) , choose an orthonormal basis of Eλ consisting of eigenvectors of the normal operator Bλ . Concatenating these bases over all λ yields an orthonormal basis of Cd in which A is diagonal (it acts as the scalar λ on Eλ ) and B is diagonal (it is diagonal on each Eλ ). Let U be the unitary whose columns are these basis vectors; then U∗AU and U∗BU are diagonal. For the particular case of projections, if P2=P then every eigenvalue α of P satisfies α2=α , hence α∈ {0,1} . Thus commuting projections are simultaneously diagonal with diagonal entries in {0,1}. Lemma 3.2 (Projection product criterion).Let P, Q be orthogonal projections on a finite-dimensional complex Hilbert space, i.e., P2=P , Q2=Q , P=P∗ , and Q=Q∗ . Then PQ =QP if and only if PQ is self-adjoint. Moreover, if PQ =QP , then PQ is the orthogonal projection onto Ran(P)∩Ran(Q). 4 Proof. We first prove the equivalence. Since P=P∗and Q=Q∗, we have (PQ)∗=Q∗P∗=QP. Hence, if PQ =QP , then (PQ)∗=PQ , so PQ is self-adjoint. Conversely, if PQ is self-adjoint, then (PQ)∗=PQ, and therefore QP =PQ. Assume now that PQ =QP . We show that PQ is an orthogonal projection onto Ran(P)∩Ran(Q). Idempotency and self-adjointness. Using P2=P,Q2=Q, and PQ =QP, (PQ)2=PQPQ =P(QP)Q=P(PQ)Q=P2Q2=PQ, so PQ is idempotent. We already observed (PQ)∗=QP =PQ , hence PQ is self-adjoint. Therefore PQ is an orthogonal projection onto its range Ran(PQ) , because for any self-adjoint idempotent Rwe have Ker(R) = (Ran(R))⊥: z∈Ker(R)⇒ hRu, zi=hu, R∗zi=hu, Rzi= 0 ∀u, so z⊥Ran(R) ; conversely, if z⊥Ran(R) then hRz, ui=hz, R∗ui=hz, Rui= 0 for all u, hence Rz = 0. Identification of the range. We prove Ran(PQ) = Ran(P)∩Ran(Q). (⊆) Let y∈Ran(PQ). Then y=PQx =P(Qx)∈Ran(P). Using PQ =QP, y=PQx =QPx ∈Ran(Q). Thus y∈Ran(P)∩Ran(Q). (⊇) Let y∈Ran(P)∩Ran(Q). Then Py =yand Qy =y. Hence PQy =P(Qy) = Py =y, so y∈Ran(PQ). Combining the two inclusions gives Ran(PQ) = Ran(P)∩Ran(Q) . Since PQ is self-adjoint idempotent, it is the orthogonal projection onto its range, i.e., onto Ran(P)∩ Ran(Q). Lemma 3.3 (Frobenius-norm criterion).For any matrix A∈Md(C) , kAk2 F= Tr(A∗A)≥ 0 , and kAkF= 0 if and only if A= 0 . Consequently, for any matrices P, Q , we have PQ =QP if and only if k[P, Q]kF= 0 ; in particular, this holds for orthogonal projections. Proof. Write A= (aij)1≤i,j≤d. Then Tr(A∗A) = d X i=1 (A∗A)ii = d X i=1 d X k=1 aki aki = d X k=1 d X i=1 |aki|2. Each term |aki|2is a nonnegative real number, hence Tr(A∗A)≥0. If Tr(A∗A) = 0 , then Pk,i |aki|2= 0 with finitely many nonnegative summands. For any nonnegative reals r1, . . . , rm , the condition r1+· · · +rm= 0 implies r`= 0 for each ` : indeed 0≤r`≤r1+· · · +rm= 0 , so r`= 0 . Applying this to r`=|aki|2 gives |aki|2= 0 for all k, i , hence aki = 0 for all k, i and therefore A= 0 . Conversely, if A= 0 then Tr(A∗A) = 0 by direct computation. Thus kAk2 F= Tr(A∗A)≥0 with equality if and only if A= 0. For the commutator criterion, take A= [P, Q] = PQ −QP . If PQ =QP then A= 0 and kAkF= 0 . Conversely, if k[P, Q]kF= 0 , the first part gives [P, Q]=0 , hence PQ =QP . This implication holds for arbitrary matrices P, Q and in particular for orthogonal projections. 5 Lemma 3.4 (Complexity of the commutator test).Let P, Q ∈Md(C) have exact rational entries encoded as in the input model, and let bmax be the maximum bit-length of any input integer (numerator or denominator). Write M(k) for the bit-cost of multiplying two k -bit integers. Throughout the bit-complexity analysis we assume that after every rational addition/multiplication the result is reduced to lowest terms (by gcd), and we count the gcd cost inside M(·)up to polylogarithmic factors. Then: 1. Arithmetic complexity. Computing PQ uses O(dω) field operations; computing QP uses another O(dω) ; entrywise equality testing uses O(d2) field comparisons. Hence the total arithmetic cost is O(dω) + O(d2) = O(dω) , with the O(dω) term strictly dominant when ω > 2(for ω= 2, the two terms are of the same order). 2. Bit complexity. Treating each complex entry as an ordered pair of rationals, every field operation in any standard multiplication schedule whose linear pre/postprocessing uses integer coefficients bounded in absolute value by a constant (e.g. the classical row-by-column algorithm or Strassen–Winograd recursion) can be implemented on rationals whose numerators/denominators have bit-length O(d bmax) . Consequently, O(dω+d2)M(d bmax)=OdωM(d bmax) bit operations suffice, up to polylogarithmic factors in d bmax arising from gcd-based reductions. In particular, with schoolbook integer multiplication M(k) = Θ(k2) this specializes to O(dω+2b2 max) . Equivalently, the bit complexity is polynomial in d and in the total input size B. Proof. Arithmetic complexity. By the definition of the matrix-multiplication exponent ω , a d×d matrix product over a field uses O(dω) field operations. Hence computing PQ and QP uses O(dω) + O(dω) = O(dω) operations. Comparing the d2 pairs of entries costs O(d2) field comparisons. Thus the total arithmetic complexity is O(dω) + O(d2) , which simplifies to O(dω)when ω > 2. Bit complexity: representation and per-operation size. Regard each complex entry as two rationals in lowest terms with positive denominators. A complex addition/multiplication is a constant number of rational additions/multiplications, so it suffices to bound sizes for reals. Let x=a/b and y=c/d be rationals in lowest terms with positive denominators and with max{bits(a),bits(b),bits(c),bits(d)} ≤ bmax. Products. xy = (ac)/(bd) has bits(ac),bits(bd) = O(bmax) . Reduction by gcd(ac, bd) does not increase bit-lengths. Additions (two-term). For x+y= (ad +bc)/(bd) we have bits(ad),bits(bc) = O(bmax) and hence bits(bd) = O(bmax) ; after reduction, the resulting numerator/denominator remain O(bmax). Size growth along a multiplication schedule. We now explain why, in the whole matrix multiplication (classical or Strassen–Winograd), the rationals that feed each scalar multiplication and comparison can be kept at bit-length O(d bmax). •Classical (row-by-column) schedule. Each output entry of PQ (or QP ) is a sum of d products of input rationals. Forming an entry by repeated two-term additions over a common denominator that divides the product of the d input denominators 6 yields a denominator of bit-length O(d bmax) ; numerators have the same order after gcd reduction. Thus every intermediate rational occurring in the computation of that entry has bit-length O(d bmax). •Strassen–Winograd (and similar ω < 3) schedules. These algorithms are built from a constant-depth pattern at each recursion level: they form a constant number of linear combinations of subblocks using coefficients in {0,±1} , perform 7 (or a constant number of) submultiplications on half-size blocks, then form a constant number of linear combinations to assemble the result. Fix any scalar that participates in a multiplication or comparison along a root-to-leaf path of the recursion tree. At each level, that scalar is the sum/difference of at most a constant number of scalars from the previous level; hence it is an integer linear combination of at most C` distinct input scalars after ` levels, for some absolute constant C (for Strassen, C= 2 ). Since the recursion depth is `=O(log d) , the number of distinct input denominators that can appear in any such scalar is at most C`≤dO(1) , and in fact C= 2 gives O(d) . Therefore the denominator of that scalar divides the product of at most O(d) input denominators, and its numerator/denominator have bit-length O(d bmax)after reduction. Thus, irrespective of whether one uses the classical or a Strassen–Winograd schedule, every rational on which we perform arithmetic/comparison during the computation has numerator/denominator bit-length O(d bmax) . A rational addition or multiplication on such operands requires O(M(d bmax)) bit operations (including gcd reductions within polylog factors). Aggregating costs. Computing PQ and QP uses O(dω) field operations, for a bit-cost of O(dωM(d bmax)) . Entrywise equality testing uses O(d2) comparisons; comparing two rationals of bit-size O(d bmax) via cross-multiplication needs O(M(d bmax)) bit operations, contributing O(d2M(d bmax)). The total is therefore O(dω+d2)M(d bmax)=OdωM(d bmax). Specialization and dependence on B .With schoolbook integer multiplication M(k) = Θ(k2) we obtain O(dω(d bmax)2) = O(dω+2b2 max) . Since bmax ≤B and B≤C d2bmax for a constant C depending only on the fixed encoding (there are O(d2) entries and a constant number of integers per entry), the bound is polynomial in d and B . This completes the proof. Lemma 3.5 (Projection verification is polynomial-time).Under the input model of Definition 2.3 (each complex entry is encoded in canonical lowest-term form with a positive denominator), deciding whether P∈Md(C) is an orthogonal projection (i.e., P2=P and P=P∗) is deterministic polynomial time. Concretely: 1. Arithmetic complexity (BSS model). Computing P2 takes O(dω) field operations; the entrywise tests for P2=P and for P=P∗ take O(d2) unit-cost branch operations. Hence the arithmetic cost is O(dω). 2. Bit complexity (with classical O(d3) matrix multiplication). During the computation of P2 , all intermediate numerators and denominators (for the real and imaginary parts treated as rationals) have bit-length O(d bmax). Therefore, bit-cost(P2) = Od3M(d bmax),bit-cost of comparisons = Od2M(d bmax), 7 up to polylogarithmic factors in d bmax arising from gcd -based reductions. In particular, with schoolbook integer multiplication M(k) = Θ(k2) we obtain O(d5b2 max) , while with fast multiplication M(k) = ˜ O(k) we obtain ˜ O(d4bmax) . Thus the total bit complexity is polynomial in d and in the input size (e.g. using bmax ≤Btot ≤C d2bmax for a constant Cdepending only on the fixed encoding). Proof. All bit-costs are counted over Q , treating each complex entry as an ordered pair of rationals (real and imaginary parts). In the arithmetic (BSS) model, both field operations and comparisons are unit-cost. Arithmetic complexity. By the definition of the matrix-multiplication exponent ω , multiplying two d×d matrices over a field uses O(dω) field operations. Thus computing P2 costs O(dω) . Testing P2=P and P=P∗ requires O(d2) entrywise comparisons in total, so the arithmetic cost is O(dω) + O(d2) = O(dω). Bit complexity (classical multiplication). Let a rational in lowest terms be a/b with b > 0 , and let bits(·) denote bit-length. Assume each input numerator/denominator has bit-length ≤bmax. Products. For x=a/b and y=c/d with max{bits(a),bits(b),bits(c),bits(d)} ≤ bmax, xy =ac bd,bits(ac),bits(bd) = O(bmax). Reducing by gcd(ac, bd)does not increase bit-lengths. Sums forming one entry. The (i, j) -entry of P2 equals Pd k=1 PikPkj . Regard the d summands as rationals nk/mk in lowest terms with bits(nk),bits(mk) = O(bmax) . Choose a common denominator Ddividing B:= Qd k=1 mk; then bits(D)≤bits(B) = d X k=1 bits(mk) = O(d bmax). Each summand becomes (nk·(D/mk))/D with numerator bit-length O(d bmax) . Summing d such integers yields a numerator of bit-length O(d bmax) (the additional log d factor is absorbed in O(·) ). Reducing the resulting fraction by gcd preserves the O(d bmax) bound. Hence every entry of P2 can be stored with numerator and denominator of bit-length O(d bmax). Per-operation bit-cost and aggregation. A rational addition or multiplication on operands whose numerators and denominators have bit-length O(d bmax) uses O(M(d bmax)) bit operations, plus at most polylogarithmic overhead from gcd computations. The classical matrix multiplication performs O(d3)such field operations, yielding bit-cost(P2) = Od3M(d bmax). For P2=P , comparing (P2)ij (bit-size O(d bmax) ) with Pij (bit-size O(bmax) ) via crossmultiplication costs O(M(d bmax)) per entry, i.e., O(d2M(d bmax)) in total. For P=P∗ , comparing Pij with Pji involves only input-sized rationals and costs O(d2M(bmax)) ≤ O(d2M(d bmax)). Summing these contributions proves the stated bounds. Remark 3.6 (Input normalization).Under Definition 2.3, entries are already in canonical lowest-term form with positive denominators, so no preprocessing is required. If one allows non-canonical encodings in an implementation, a preprocessing pass that moves signs to numerators and reduces by gcd brings each rational into lowest terms with a positive denominator in O(d2M(bmax)) bit operations, which does not change the asymptotic bounds above. 8 Remark 3.7 (On subcubic matrix multiplication).The arithmetic (BSS) bound O(dω) holds for any algorithm achieving exponent ω < 3 . We intentionally state the bitcomplexity bound for classical O(d3) multiplication; extending the explicit O(·) bit bound to Strassen-type algorithms requires a careful treatment of intermediate expression swell in recursive linear-combination schedules and is beyond the scope of this paper. 4 The Main Theorem We now state and prove our main result, establishing that the projection commutativity problem is in the complexity class P(deterministic polynomial time). Theorem 4.1. The decision problem Proj-Commute is in P . Specifically, there is a deterministic algorithm which, given orthogonal projections P, Q ∈Md(C) with exact rational entries, decides whether PQ =QP using O(dω) + O(d2) field operations and a total bit-cost polynomial in d and in the input bit-length B (the total number of input bits). In particular, the bit-cost is OdωM(d bmax) , where bmax is the maximum input integer bit-length and M(k)is the bit-cost of multiplying two k-bit integers. Proof. Algorithm. On input P, Q: 1. Compute A:= PQ by a d×dmatrix multiplication. 2. Form A∗ (conjugate transpose) by transposing and negating the imaginary parts entrywise. 3. Test A=A∗by comparing all d2corresponding entries for equality. 4. Output PQ =QP iff A=A∗. Correctness. Since P=P∗ and Q=Q∗ , we have (PQ)∗=Q∗P∗=QP . Hence A is self-adjoint if and only if PQ =QP . Therefore the algorithm returns PQ =QP exactly when PQ =QP (projection product criterion). Arithmetic operation count. Step (1) uses O(dω) field operations by the definition of the matrix-multiplication exponent ω . Step (2) performs O(d2) trivial field operations (sign changes and swaps). Step (3) performs O(d2) field comparisons. Thus the total field-operation count is O(dω) + O(d2) = O(dω) (the O(dω) term dominates when ω > 2 ). Bit-complexity model. Treat each complex entry as a pair of rationals in lowest terms with positive denominators. Let bmax be the maximum bit-length of any input integer (numerator or denominator), and let M(k) denote the bit-cost of multiplying two k -bit integers. It suffices to bound bit-sizes for the rational arithmetic on the real and imaginary parts; constant factors from handling both parts are absorbed in big-O. Bit-cost of Step (1). Each entry of A=PQ is a sum of d products of input rationals. A product of two input rationals has numerator and denominator of bit-length O(bmax) (bit-lengths add under integer multiplication). Summing d such rationals can be done over a common denominator dividing the product of the d denominators, whose bitlength is O(d bmax) ; after clearing denominators and reducing by gcd , all intermediate and final numerators and denominators have bit-length O(d bmax) . Hence each rational addition/multiplication in Step (1) costs O(M(d bmax)) bit operations. Since there are O(dω)field operations, Step (1) costs OdωM(d bmax)bit operations. 9