PaperlayerView exact revision on arXiv

Source-linked AI summary

Operator scaling: theory and applications

Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

arXiv:1511.03730v4cs.CCmath.ACmath.AGquant-ph

TL;DR

The paper studies deciding invertibility of symbolic matrices in non-commuting variables, unlike the commuting-variable PIT setting. It analyzes Gurvits’ scaling algorithm and proves a deterministic polynomial-time decision bound, poly(n, m, b), over the free skew field.

  • Problem

    The central problem is deciding whether a symbolic matrix in non-commuting variables is invertible, while its commuting-variable analogue is PIT.

    Source: §1 · p. 3

  • Method

    The paper analyzes Gurvits’ scaling algorithm, a non-commutative generalization of Sinkhorn scaling, using an analytic sequence of complex matrices and a convergence test.

    Source: §2.2 · p. 21, §6 · p. 50

  • Results

    In time poly(n, m, b), the deterministic algorithm decides whether L = sum_i x_i A_i is invertible over the free skew field.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The paper also computes non-commutative rank in polynomial time over any subfield of C, without using degree bounds.

    Source: §6 · p. 50

    The algorithm is white-box, using the matrix or formula description; the best-known black-box identity test remains exponential even with randomization.

    Source: §1.2 · p. 8

Abstract

from arXiv · show

In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over $\mathbb{Q}$ is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time (whether or not randomization is allowed). The algorithm efficiently solves the "word problem" for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential-time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to Gurvits, who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. We provide a detailed account of some of these sources and their interconnections.

1 Introduction

The introduction frames SINGULAR as testing whether a symbolic matrix in non-commuting variables is invertible over the free skew field. It presents a deterministic polynomial-time algorithm and relates the problem to polynomial identity testing and several mathematical areas.

1 Introduction

  • Before this work, the best known algorithm for non-commutative SINGULAR required exponential time, with no better bound known even allowing randomness.The problem also connects to non-commutative identity testing and has equivalent formulations across several areas.Source: §1 · p. 3
  • For non-commuting variables over Q, a deterministic algorithm decides SINGULAR in poly(n, m, b) time for matrices with entries of bit-size b.SINGULAR asks whether the symbolic matrix is invertible over the free skew field.Source: §1 · pp. 3–4
  • SINGULAR has equivalent formulations involving non-commutative rank, shrunk subspaces, rank-decreasing quantum operators, and invariant theory.The introduction also describes connections to optimization, non-commutative algebra, and quantum information theory.Source: §1 · pp. 4–5
  • The introduction surveys how SINGULAR arises in diverse settings and explains the algorithm, its complexity analysis, and extensions to non-commutative rank computation.It also highlights analogies and connections between the commutative and non-commutative cases.Source: §1 · p. 5

1.1 The Free Skew Field

The free skew field is a universal division-ring field of fractions for non-commutative polynomials. Its elements can be represented by rational expressions, whose behavior on matrix inputs helps characterize equality and identity testing.

1.1 The Free Skew Field

  • The free skew field is the universal skew field of fractions containing the free algebra of non-commutative polynomials.It is a division ring, so every nonzero element is invertible.Source: §1.1 · p. 6
  • Rational expressions become partial functions when variables are substituted by matrices, and two expressions are equivalent when they agree on every common defined matrix input.The rational expressions under this equivalence comprise the universal free skew field.Source: §1.1 · p. 6
  • A nonzero non-commutative polynomial can vanish on all matrices of a fixed finite dimension, so matrix evaluations alone at that dimension need not detect identity.The commutator x1x2 − x2x1 is an example for dimension one.Source: §1.1 · p. 6
  • Every free-skew-field element occurs as an entry of the inverse of an invertible polynomial matrix, linking matrix invertibility to rational identity testing.The cited construction is attributed to Cohn.Source: §1.1 · p. 7

1.2 Word Problems and Identity Tests

The section connects non-commutative identity testing to symbolic-matrix singularity and extends the algorithmic results to non-commutative rank and approximation of commutative rank.

1.2 Word Problems and Identity Tests

  • The word problem for arithmetic formulas with division is an identity test: determine whether a represented polynomial or rational function is zero.The formulas allow division because no efficient elimination analogue is known for non-commutative variables.Source: §1.2 · p. 7
  • Cohn’s reduction converts each non-commutative arithmetic formula into a polynomial-size symbolic matrix that is singular exactly when the formula computes zero.This connects rational identity testing to the SINGULAR problem for symbolic matrices.Source: §1.2 · p. 8
  • Non-commutative rational identity testing for formulas over Q is decidable in polynomial time.The algorithm tests whether a formula of size s and bit complexity b is identically zero in poly(s, b) steps.Source: §1.2 · p. 8
  • The algorithm is white-box, using the given matrix or formula description; the best-known black-box test for these formulas requires exponential time even with randomization.The paper leaves finding a faster black-box algorithm as an open question.Source: §1.2 · p. 8

1.3 Commutative and Non-commutative Rank of Symbolic Matrices

  • A deterministic polynomial-time algorithm computes the non-commutative rank of a symbolic matrix over Q.The result extends the singularity-testing algorithm to rank computation.Source: §1.3 · p. 10
  • A polynomial-time algorithm approximates the rank of any symbolic matrix in commuting variables over Q within a factor of 2.The bound follows alongside the relation nc-rank(L) ≤ 2rank(L).Source: §1.3 · p. 10

1.4 Compression Spaces, Optimization and Gurvits’ Algorithm G

The paper extends Gurvits’ algorithm beyond compression spaces by analyzing its performance on arbitrary inputs. It relates the method to matrix scaling and quantum operators, with a capacity lower bound supplying the needed polynomial-time guarantee.

1.4 Compression Spaces, Optimization and Gurvits’ Algorithm G

  • The paper analyzes Gurvits’ Algorithm G for every input matrix space, not only compression spaces.Gurvits’ earlier guarantee covered inputs where rank(L) = n or nc-rank(L) < n.Source: §1.4 · p. 11
  • For compression spaces, the algorithm is correct, and computing non-commutative rank also determines their commutative rank.Compression spaces satisfy rank(L) = nc-rank(L).Source: §1.4 · pp. 10–11
  • Structured spaces, including those generated by rank-1 matrices, connect compression-space rank computation to optimization problems that can be solved without being given the structured generators.The input generators may be arbitrary even when the subspace has structured spanning generators.Source: §1.4 · p. 11

1.5 Permanents, Quantum Operators, Origins and Nature of Algorithm G

  • Algorithm G is a quantum analogue of Sinkhorn-style matrix scaling, replacing commuting diagonal matrices with general matrices and the L1 norm with L2.Its iterations alternately normalize row and column behavior through operator scaling.Source: §1.5 · pp. 12–13
  • The algorithm tests whether the row and column normalization factors approach the identity, but Gurvits’ convergence analysis established this only under the commutative nonsingularity condition Det(L) ≠ 0.The distance test checks whether ds(L) < 1/n after polynomially many iterations.Source: §1.5 · p. 13
  • An explicit lower bound on capacity for every skew-field-nonsingular L supplies the polynomial upper bound missing from the earlier analysis.Positive capacity alone had guaranteed finite convergence without bounding the number of steps.Source: §1.5 · p. 14

1.6 Invariant Theory, Left-Right Action, Capacity and the Analysis of Algorithm G

The section connects invariant theory’s left-right action to noncommutative invertibility, then uses operator capacity and scaling to analyze Algorithm G. Its capacity lower bound avoids requiring a strong degree bound for the left-right action.

1.6 Invariant Theory, Left-Right Action, Capacity and the Analysis of Algorithm G

  • Invariant theory studies polynomial invariants and their null-cones; symmetric polynomials illustrate how an infinite family can have a finite generating set.For the permutation action, the elementary symmetric polynomials generate the invariant ring, and the null-cone is the all-zero vector.Source: §1.6 · p. 14
  • For the left-right action on multiple matrices, invariant polynomials are generated by determinants of matrix combinations, linking invariant theory to noncommutative SINGULAR.A symbolic matrix is noninvertible in the free skew field exactly when the corresponding matrix tuple lies in the left-right null-cone.Source: §1.6 · p. 15
  • The capacity lower-bound strategy uses determinant non-vanishing to construct auxiliary operators whose capacities are positive, but their size bounds depend on the auxiliary matrices.Those matrices are built from invariant-theory witnesses, and their description size can exceed that of the input operator.Source: §1.6 · p. 16
  • Dimension-normalized capacity is multiplicative under tensor products, providing a way to relate the input operator’s capacity to auxiliary-operator capacities.The section uses this property in the original lower-bound argument with degree bounded by σ(n).Source: §1.6 · p. 16
  • The new lower bound combines Alon’s Nullstellensatz with tighter capacity reductions to obtain the desired bound using any finite degree bound.This removes the need for strong degree bounds to establish polynomial-time analysis of the algorithm.Source: §1.6 · p. 17
  • The capacity bound controls Algorithm G’s iteration count, while a separate bit-complexity analysis is needed to establish its running time.The paper also uses that analysis to extend the algorithm to capacity approximation and derive continuity bounds.Source: §1.6 · p. 17

1.7 Computation and Continuity of Capacity

The paper modifies Algorithm G to approximate operator capacity and analyzes capacity’s continuity. It also interprets Algorithm G as alternating minimization, which converges in polynomially many steps.

1.7 Computation and Continuity of Capacity

  • A deterministic algorithm computes a (1 + ε)-multiplicative approximation to cap(L) in poly(n, b, 1/ε) time.Here n is the dimension on which L acts, and b denotes the bit-sizes in its description.Source: §1.7 · p. 17
  • Algorithm G yields a capacity approximation by finding an approximately doubly stochastic scaling of L.The paper leaves open whether a (1 + ε) approximation can be computed in poly(n, b, log(1/ε)) time.Source: §1.7 · pp. 17–18
  • Algorithm G is alternating minimization for a capacity formulation whose objective is quadratic but becomes convex when either matrix variable is fixed.Starting from X0 = I, the alternating process converges in polynomially many steps.Source: §1.7 · p. 18
  • The paper proves quantitative continuity bounds for capacity by using its approximation through Algorithm G.The authors attribute continuity to the iterative approximation process being continuous in L.Source: §1.7 · p. 18

Subsequent Work

Subsequent work developed a polynomial-time algorithm for SINGULAR over all fields and a deterministic PTAS for commutative rank. The paper also outlines its sections and appendix.

Subsequent Work

  • Derksen–Makam degree bounds enabled Ivanyos, Qiao, and Subrahmanyam’s deterministic polynomial-time SINGULAR algorithm over all fields.That algorithm can certify noncommutative singularity by outputting a shrunk subspace when one exists; over the rationals, this paper’s algorithm computes capacity and a doubly stochastic scaling.Source: Subsequent Work · p. 19
  • Bläser, Jindal, and Pandey gave a deterministic n^O(1/ε)-time PTAS for commutative rank, improving this paper’s factor-2 approximation.The later algorithm uses techniques developed in.Source: Subsequent Work · p. 19

1.8 Organization

  • The paper’s organization covers Algorithm G and capacity bounds, capacity properties and bit complexity, capacity approximation, noncommutative rank, and open problems.These topics appear in Sections 2–6 and Appendix A.Source: §1.8 · p. 19

2 Quantum Operators and Analysis of Algorithm G

This section analyzes Algorithm G for testing rank non-decrease of completely positive operators, using capacity to bound convergence and establish a lower bound for integer inputs. The proof combines right normalization, positive semidefiniteness, the AM-GM inequality, and Theorem 2.18 to derive the capacity bound.

2.1 Completely Positive Operators and Capacity

  • Capacity, introduced for completely positive operators by Gurvits, serves as a complexity measure whose evolution is central to analyzing Algorithm G.The section also studies how capacity changes under the linear transformations used in the algorithm.Source: §2.1 · p. 20

2.2 Algorithm G and its convergence rate

  • Algorithm G alternates left and right normalizations and declares rank non-decreasing when the minimum ds(T_j) over its iterations is at most 1/(6n).A normalized operator with ds(T) ≤ 1/(n + 1) is guaranteed to be rank non-decreasing by Theorem 2.12.Source: §2.2 · pp. 21–23

2.3 Main Theorem: The Lower Bound on Capacity

  • The capacity bound follows by scaling the integral operator to preserve identity, then combining a trace bound, an integral determinantal lower bound, and capacity's scaling multiplicativity.The proof plan uses a Cauchy-Schwarz-like matrix inequality to connect these ingredients.Source: §2.3 · pp. 24, 26, 27
  • For rank non-decreasing cptp maps obtained by right-normalizing integer Kraus operators bounded by M, cap(T) ≥ exp(−4n log(Mmn)), yielding O(n^2 log(Mmn)) scaling iterations.The iteration bound follows by applying the capacity lower bound to Algorithm G's convergence analysis; truncation is also described as sufficient to control bit sizes.Source: §2.2 · p. 24, §2.3 · p. 28
  • Right normalization of T_A, positive semidefiniteness of T*(I), the AM-GM inequality, and Theorem 2.18 together yield the desired bound.The proof identifies T as the right normalization of T_A and combines Equations (10) and (11) with Theorem 2.18.Source: §2.3 · p. 28

3 Properties of Capacity

This section relates capacity to approximate doubly stochasticity, approximate optimizers, and tensor products. These properties support later capacity bounds and continuity analysis.

3 Properties of Capacity

  • The section establishes that capacity near 1 and approximate fixed points have useful structural consequences, and proves tensor-product multiplicativity as an additional property.The multiplicativity result was not needed for the lower bound in this version of the paper.Source: §3 · p. 28, §3.3 · p. 33

3.1 Capacity of almost doubly stochastic operators

  • If T is trace-preserving and tr[(T(I) − I)^2] ≤ ε, then cap(T) is bounded below near 1; conversely, cap(T) ≥ exp(−δ) implies ds(T) ≤ 6δ for δ ≤ 1/6.The two bounds use different parameters because capacity and distance to doubly stochasticity do not characterize each other exactly.Source: §3.1 · pp. 30–31

3.2 Characterization of approximate optimizers for capacity

  • Elements of Fixed(T, ε) are approximate minimizers for cap(T); if C ∈ Fixed(T, ε) and ε ≤ 1/(n + 1), then T is rank non-decreasing.Source: §3.2 · pp. 31–32

3.3 Multiplicativity of capacity

  • Capacity is multiplicative under tensor products of completely positive operators: cap(T1 ⊗ T2) = cap(T1)^d2 cap(T2)^d1.Here T1 and T2 act on matrices of dimensions d1 and d2, respectively.Source: §3.3 · p. 33

4 Bit Complexity Analysis of Algorithm G and Continuity of Capacity

This section analyzes the evolution and bit complexity of Algorithm G and derives explicit continuity bounds for operator capacity. The continuity proof uses a choice of ε ensuring ε′ ≤ 2ε, verified by elementary calculations.

4 Bit Complexity Analysis of Algorithm G and Continuity of Capacity

  • For α = (M^2 n^2 m)^(n−1), the iterates S_j remain positive definite with l(S_j) ≥ α^−(j+1) and u(S_j) ≤ α^(j+1).The bounds apply when the completely positive operator has integer Kraus matrices with entries of magnitude at most M and T(I), T*(I) nonsingular.Source: §4 · p. 35

4.1 Evolution of the Operator through Scaling

  • The intermediary operators T_j are tracked through matrices P_j and Q_j, which evolve alternately using T and T* and the sequence S_j.These expressions support analysis of capacity and distance to doubly stochasticity.Source: §4.1 · p. 38

4.2 Bit Complexity Analysis of Algorithm G

  • With polynomially many bits of truncation, Algorithm G′ keeps |ε_j − ε̃_j| ≤ 1/(12n) for t = 2 + 36n · log(1/f(n, M)) iterations and preserves correctness.The required precision P(n, log(M)) is polynomial in n and log(M).Source: §4.2 · pp. 40–42

4.3 Continuity of Capacity

  • If ||A_i − B_i|| ≤ δ ≤ exp(−P(n, b, log(m))), then cap(T_A) > 0 implies cap(T_B) > 0 for a polynomial P.The proof uses a low-spectral-norm approximate fixed point for T_A and transfers it to T_B.Source: §4.3 · p. 42
  • Choosing ε = 2 max{Q11(n, b, log(m)), Q12(n, b, log(m))}/log(1/δ) ensures ε′ ≤ 2ε and completes the proof by elementary calculations.Source: §4.3 · p. 45

5 Computing the Capacity of a Quantum Operator

The section analyzes Algorithm G as a method for approximating the capacity of a quantum operator, then extends the analysis to truncated arithmetic. Both versions provide a multiplicative approximation under the stated integer-input conditions.

5 Computing the Capacity of a Quantum Operator

  • Algorithm G approximates cap(T) within a multiplicative factor of 1 ± ε for completely positive operators with integer Kraus matrices whose entries have absolute value at most M.The theorem gives a polynomial-step iteration bound in the input parameters.Source: §5 · p. 47

5.1 Computing Capacity with Truncation

  • Truncation works because the eigenvalues of the truncated and untruncated scaling matrices remain sufficiently close to preserve their determinants.The algorithm estimates capacity using determinants of the truncated matrices, which approximate those of the corresponding scaled matrices.Source: §5.1 · pp. 48, 50
  • With truncation, Algorithm 4 also approximates cap(T) within a multiplicative factor of 1 ± ε under the same integer-entry bound.The theorem specifies a truncation parameter P(n, 1/ε, log(M)) and a polynomially bounded iteration count.Source: §5 · p. 47, §5.1 · p. 49
  • The truncated procedure still outputs zero when the operator is rank-decreasing, while its determinant output lies in [(1 − ε)cap(T), (1 + ε)cap(T)] in the rank-nondecreasing case.The rank-decreasing case is handled in steps 1 to 3; step 4 computes the approximation in the other case.Source: §5.1 · p. 50

6 Conclusion and Open Problems

The conclusion presents a polynomial-time algorithm for non-commutative rank and identifies open directions spanning PIT, operator scaling, and invariant-theoretic problems.

6 Conclusion and Open Problems

  • The paper gives a polynomial-time algorithm for computing non-commutative rank over subfields of the complex numbers, using an analytic iteration that does not require degree bounds.The algorithm generates complex matrices and tests convergence despite the problem's algebraic formulation.Source: §6 · p. 50
  • One open direction is to extend deterministic efficient methods to commutative PIT and orbit-closure intersection for the Left-Right action.The paper also asks about deterministic black-box testing for SINGULAR, with bipartite perfect matching as a special case.Source: §6 · p. 51
  • Further questions include efficient rank-decrease testing for positive operators, strongly polynomial operator scaling, and faster capacity approximation.The capacity question asks whether a (1 + ε) approximation can be computed in time poly(n, b, log(1/ε)).Source: §6 · p. 51
  • The conclusion also asks whether efficient algorithms can test null-cone membership for general quivers and reductive-group actions.Source: §6 · p. 52

A Symbolic matrices with polynomial entries and non-commutative rank

The section presents two reductions for computing non-commutative rank: one through fullness testing of a square linear matrix and another from a quantum viewpoint. Together with the effective Higman trick, these give polynomial-time computation for matrices whose entries are given by formulas.

A Symbolic matrices with polynomial entries and non-commutative rank

  • The two reductions compute non-commutative rank through square-matrix singularity testing or a quantum approach that mimics the reduction from maximum matching to perfect matching.The quantum approach is described as a second route to the same rank-computation problem.Source: A Symbolic matrices with polynomial… · p. 57
  • The effective Higman trick reduces matrices with polynomial entries to matrices with linear entries, with a quantitative analysis of the reduction.The authors note that this analysis, to their knowledge, does not appear in the literature and may be useful elsewhere.Source: A Symbolic matrices with polynomial… · p. 57
  • Combining these reductions yields polynomial-time computation of non-commutative rank in the description size of the matrix entries.The section frames its goal as computing the rank of any, not necessarily square, matrix over the free skew field.Source: A Symbolic matrices with polynomial… · p. 57

A.1 Higman’s Trick

Higman’s trick replaces a matrix with polynomial entries by a larger matrix with linear entries while preserving its co-rank and co-noncommutative rank. The effective version gives an efficient construction with controlled coefficient bit complexity.

A.1 Higman’s Trick

  • Formula bit complexity is the maximum bit complexity of any rational input appearing in a division-free non-commutative formula..Source: §A.1 · p. 57
  • Higman’s trick converts polynomial entries into linear entries by removing multiplication while preserving the complement of rank.The motivating example targets the multiplication in z + xy; elementary row and column operations preserve the complement of rank.Source: §A.1 · p. 58
  • For formula entries of size at most s and bit complexity at most b, the effective trick constructs P(A ⊕ I_k)Q with linear entries and coefficient bit complexity at most b.Here k is the total number of multiplication gates; the matrices P and Q are invertible and constructible in time poly(m, n, s, b).Source: §A.1 · p. 58
  • Because P and Q are nonsingular, the transformed matrix has the same co-rank and co-noncommutative rank as A.The proposition applies to formulas without divisions and uses one identity-matrix dimension for each multiplication gate.Source: §A.1 · p. 58

A.2 Classical Reduction

The classical reduction computes non-commutative rank by testing fullness at successive rank thresholds. It uses generic matrices, the effective Higman trick, and a deterministic fullness test to obtain a polynomial-time algorithm.

A.2 Classical Reduction

  • For each r, nc-rank(M) ≥ r exactly when UMV is full for generic non-commuting matrices U and V.U has dimensions r × m and V has dimensions n × r.Source: §A.2 · p. 59
  • The algorithm forms Mr = UrMVr, applies effective Higman’s trick to obtain a linear matrix Nr, tests Nr for fullness, and returns the largest successful r.The fullness test uses Algorithm G′; the algorithm tries r from 1 through min(m, n).Source: §A.2 · p. 60
  • The resulting algorithm deterministically computes nc-rank(M) in time polynomial in m, n, s, and b.The input entries are polynomials computed by formulas of size at most s and bit complexity at most b.Source: §A.2 · p. 60
  • For each threshold, the linearized matrix has dimensions (k + r) × (k + r), with k ≤ 2s(mn)^2 and coefficient bit complexity bounded by b.The construction and fullness test are applied at most n times.Source: §A.2 · p. 61

A.3 The Quantum Reduction

The quantum reduction offers another route from non-commutative rank to fullness testing, restricted to square matrices. It relates rank thresholds to rank-decreasing behavior of a completely positive operator.

A.3 The Quantum Reduction

  • This alternative reduction works with square matrices after Higman’s trick makes the input linear.The section frames the approach as a quantum-viewpoint reduction to fullness testing.Source: §A.3 · p. 61
  • For a linear matrix L, nc-rank(L) ≤ r exactly when its associated operator is n − r-rank-decreasing.The operator is defined from the matrices in the linear expression for L.Source: §A.3 · p. 61
  • The construction enlarges the operator’s matrix dimension from n to n + c − 1, and the stated rank-decreasing conditions apply for c ≤ n.The enlarged operator is defined using four blocks of dimensions n × n, n × (c − 1), (c − 1) × n, and (c − 1) × (c − 1).Source: §A.3 · p. 61
  • The quantum reduction is compared with adding c − 1 dummy vertices to both sides when using a perfect-matching oracle to test for a matching of size at least n − c + 1.The comparison is presented as an analogy to the rank-reduction construction.Source: §A.3 · p. 63
Loading 1511.03730v4…