Many numerical methods split a sum of matrices $S = A_1 + \dots + A_n$ into two groups and treat each group separately. Examples include product formulas that approximate the exponential of $S$ by exponentials of the two group sums, and solvers that update two blocks in parallel. In these methods the error is governed less by how large the two group sums are than by how badly they fail to commute, that is, by the norm of their commutator $[S_+, S_-] = S_+S_- - S_-S_+$. This note proposes to choose the split with the tools of discrepancy theory. Discrepancy theory is the study of assigning $\pm 1$ signs to items so that every constraint stays balanced. The aim is to find a $\pm1$ assignment of the $A_i$ for which the two halves are roughly equal and also nearly commute, with guarantees stated in terms of how spread out each matrix's spectrum is rather than how large it is.
The idea rests on a short calculation that links two research lines which have not yet met. The first is the matrix version of iterative partial coloring. Partial coloring means fixing a constant fraction of the signs at each round while keeping imbalance bounded, then recursing on the rest. The second is the "discrepancy values" of Habib Zadeh and Sra. These measure a matrix's distance from the scalar multiples of the identity, and the authors use them to bound commutators sharply. The commutator of the two halves turns out to be a linear signed sum, so it is itself a matrix discrepancy problem. Because commutators ignore identity components, every term in that sum can be centered for free. Known partial-coloring machinery therefore applies directly, with spectral spread in place of operator norm.
Core Claim
Write $x \in \{\pm1\}^n$ for the signs, $S_\pm$ for the sums of the $A_i$ with $x_i = \pm 1$, and $D = \sum_i x_i A_i$ for the signed sum. Then $S_+ = (S+D)/2$ and $S_- = (S-D)/2$. Expanding gives
$$[S_+, S_-] \;=\; \tfrac12 [D, S] \;=\; \tfrac12 \sum_{i=1}^n x_i\, B_i, \qquad B_i = [A_i, S].$$
Making the halves nearly commute is therefore exactly the problem of balancing the fixed matrices $B_i$ with signs. Two structural facts make this tractable and different from ordinary matrix balancing. First, $[A_i - \alpha_i I,\, S - \beta I] = [A_i, S]$ for any scalars $\alpha_i, \beta$, so the problem depends on each $A_i$ only modulo the identity. Introducing Discrepancy Values of Matrices with Application to Bounding Norms of Commutators shows that the discrepancy value $\delta_1(A) = \min_\alpha \|A - \alpha I\|_{op}$ is the right size measure under this invariance, and proves $\sigma([A,B]) \prec_w 2\delta(A)\delta(B)$ whenever one matrix is Hermitian. Here $\prec_w$ means the singular values of the left side are weakly majorized by those on the right, so in particular the largest is bounded. For Hermitian $A_i$ and $S$ this gives $\|B_i\|_{op} \le 2\,\delta_1(A_i)\,\delta_1(S)$, where for a Hermitian matrix $\delta_1$ is half the gap between its largest and smallest eigenvalue. Second, $\operatorname{rank}(B_i) \le 2\operatorname{rank}(A_i)$, so low-rank inputs stay low-rank.
Matrix partial coloring results applied to the skew-Hermitian $B_i$ (multiplied by $i$ to make them Hermitian) then yield a split with commutator of order $\sqrt{n}\,\max_i \delta_1(A_i)\,\delta_1(S)$, up to the logarithmic factors those results carry. This is in contrast to the $\sqrt{n}\,\max_i\|A_i\|\,\|S\|$ one obtains by balancing $D$ and invoking the classical bound. The gap is unbounded when the $A_i$ carry large identity-like components, as shifted Laplacians and Hamiltonians with on-site terms do. The commutator can also collapse to zero when the $A_i$ commute with $S$, even though $D$ cannot be made small.
The claim is not that this calculation is deep. The claim is that it turns a commutator-control question, which no existing discrepancy walk addresses, into an instance the constructive matrix walks already handle. It also exposes a recursive version with real algorithmic content: split each half again, so that siblings nearly commute at every level of a tree of $2^t$ groups.
Research Program
The first deliverable is an existence theorem for the joint problem: halves that are both balanced and nearly commuting. Both requirements are signed sums, so stacking them as a direct sum $A_i \oplus iB_i$ gives a single matrix discrepancy instance of twice the dimension, with rank at most three times that of $A_i$. Each constraint keeps its own scale because each block is normalized separately. A new framework for matrix discrepancy: partial coloring bounds via mirror descent supplies the method here. It proves partial-coloring bounds for low-rank and block-diagonal matrix families by bounding covering numbers of the polar body with mirror descent. We would apply its low-rank and block-diagonal statements to the stacked family to get the joint bound.
That paper's argument is existential and its bounds carry the general Matrix Spencer gap. We inherit the same limitation and do not claim to close it.
The second deliverable is a constructive algorithm. Spectral Sparsification by Deterministic Discrepancy Walk gives a deterministic walk guided by a smoothed maximum-eigenvalue potential, and it proves the Reis–Rothvoss matrix partial coloring theorem. We would run that walk on the stacked family with two potentials, one per block. The walk fixes half the free signs per phase and recurses, in the style of the hereditary algorithms in Fast Discrepancy Minimization with Hereditary Guarantees.
The new analysis concerns the recursive tree. When a group $G$ is split, the "$S$" in $B_i = [A_i, S_G]$ is that group's sum. That sum was itself produced by an earlier split and is only approximately $S/2^{t}$, so commutator errors propagate down the tree. We would prove that the sibling commutators at depth $t$ shrink geometrically. The intuition is that both $\delta_1(S_G)$ and the number of terms halve at each level, so the bound should scale like $(n/2^t)^{1/2}\,\max\delta_1(A_i)\,\delta_1(S)/2^t$.
The third deliverable concerns non-normal matrices, such as directed graph Laplacians, where the a priori bound $\|B_i\| \le 2\delta_1(A_i)\delta_1(S)$ requires Conjecture 7.1 of Habib Zadeh and Sra. That conjecture is unproven beyond $2\times2$ matrices and the normal case. We would state the directed results conditionally and run a large randomized and adversarial search on the $B_i$ that actually arise from directed graph instances. This gives the conjecture a targeted stress test it has not had. It is a side contribution, but a cheap one.
Two papers constrain the design. The note by Pesenti and Vladu, Discrepancy Minimization via Regularization, shows the choice of barrier matters for constants: entropic regularization gives 5.32 and an $\ell_{1/2}$ regularizer gives 3.67 for Spencer's theorem. Bansal, Laddha and Vempala, A Unified Approach to Discrepancy Minimization, warn that potential walks need very small steps. We therefore treat step size and barrier type as tuned hyperparameters rather than fixed choices.
Baselines
The naive reference point is uniform random signs, both a single draw and the best of $K$ draws under the same wall-clock budget as our walk. For matrices this pays an extra factor of roughly $\sqrt{\log d}$ in dimension $d$ by matrix concentration. It is the comparison Larsen used for set systems: on $4000\times4000$ synthetic matrices his partial coloring achieved discrepancy "roughly 10 times smaller than a single random sample and 4 times smaller than multiple random samples run for the same duration" (Fast Discrepancy Minimization with Hereditary Guarantees). That number concerns scalar set systems, not commutators. We found no reported result on Lacuna for commutator-targeted matrix splitting, so the commutator comparison will be established here. Beating random signs means a lower commutator ratio at equal time on every instance family, with the margin growing with dimension.
The strongest existing method is the deterministic matrix discrepancy walk of Spectral Sparsification by Deterministic Discrepancy Walk run on the $A_i$ alone. It minimizes $\|D\|$, and the resulting commutator is then bounded by $\delta_1(D)\delta_1(S)$. This is what a practitioner would do today, and it already controls $[D,S]$ indirectly. We run it with the same potential family, step-size grid, and iteration budget as our method; the only difference is the matrices fed in. Beating it means a commutator at least a constant factor smaller on generic instances, and orders of magnitude smaller on instances with commuting or identity-heavy structure, while keeping $\|D\|$ within a small constant of its value.
A second strong competitor is the same walk on trace-projected inputs $A_i - \tfrac{\operatorname{tr}A_i}{d}I$. This tests whether the gain is merely "remove the trace".
The key ablation runs our walk on the $B_i$ block alone, without the balance block. This isolates the commutator objective and shows what the joint constraint costs. A second ablation replaces the recursive per-level recomputation of $B_i = [A_i, S_G]$ with the root's $[A_i, S]$, isolating the recursive analysis.
For small dimensions ($d, n \le 60$), the semidefinite relaxation of the stacked problem with random-walk rounding serves as a quality ceiling. This is the slow but accurate style of A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound.
Why not just…?
Why not just balance the signed sum $D$ and apply the commutator inequality afterward? Because $\|[D,S]\|$ can be zero while $\|D\|$ is forced to be large. A family of $A_i$ that share eigenvectors with $S$ is one example. More generally, the inequality $\sigma([D,S]) \prec_w 2\delta(D)\delta(S)$ from Habib Zadeh and Sra is tight only when eigenspaces are rotated by $\pi/4$, which their paper identifies as the maximally non-commuting configuration. Generic splits are far from that worst case, so targeting $\|D\|$ wastes the walk's budget on a proxy. The second baseline above measures this directly. If the proxy turns out to be within a constant factor on all non-adversarial families, the practical case for the method shrinks to structured instances, and we would report that honestly.
Why not just subtract each matrix's trace and run the existing walk? This is the most serious threat for the balance objective. For Hermitian matrices, global trace removal changes $\|D\|$ by at most a factor of two relative to $\delta_1(D)$. It does not help the commutator objective, though. There the per-term centering is automatic and exact, and what matters is the alignment between each $A_i$ and $S$, which trace removal leaves untouched. The trace-projected baseline will show whether any gain survives beyond centering. On instances with heterogeneous identity components we expect it to resemble plain norm balancing.
Why not just use random signs, given that dimensions in applications are modest? For small $d$, the $\sqrt{\log d}$ penalty is small and best-of-$K$ sampling may be competitive. This is a real threat at $d \lesssim 50$. The experiments sweep $d$ up to the tens of thousands so that the crossover point is measured rather than asserted. If random sampling dominates below some $d$, the recommendation will say so.
Why not just solve the full semidefinite program? Its cost grows like $mn^{4.5}$ for hereditary formulations (Fast Discrepancy Minimization with Hereditary Guarantees). Habib Zadeh and Sra also note that computing discrepancy values by semidefinite programming at large scale is untested. We use the program only as a small-scale ceiling.
Proposed Experiments
We evaluate on three instance families. The first is synthetic Hermitian families of rank $r \in \{1, 4, 16\}$ in dimension $d$ up to $10^4$, generated in three regimes: generic random, "shared-component" (each $A_i = c_i I + E_i$ with large heterogeneous $c_i$), and "near-commuting" (the $A_i$ share most of an eigenbasis with $S$). The second is edge decompositions of unnormalized graph Laplacians, where each edge is a rank-one matrix, from the domains used by GRASS: Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis: power-grid-like grids, 2D finite-element meshes, and social graphs. GRASS reports condition-number and runtime results there but no commutator results. The third is directed graph Laplacians for the conditional non-normal study.
As a sanity check, diagonal instances built from Larsen's 2D corner and halfspace set systems must reproduce scalar discrepancy behavior: the balance block reduces to set-system discrepancy and the commutator with a diagonal $S$ vanishes.
The primary metrics are the commutator ratio $\|[S_+,S_-]\|_{op}/(\sqrt{n}\max_i\delta_1(A_i)\delta_1(S))$, the balance ratio $\|D\|_{op}/(\sqrt n\max_i\|A_i\|)$, sibling commutators at each depth of the recursive tree, and wall-clock time. Downstream, we report the error of the two-group product approximation of $e^{-S\tau}$ for a range of time steps $\tau$. This is the quantity the commutator is supposed to predict, and it checks that the proxy matters.
Four checks are decisive. First, on shared-component instances, the commutator-targeted walk must beat both the norm-targeted and the trace-projected walk by a margin that grows with the spread of the $c_i$; if it does not, the core claim is wrong. Second, on generic instances it must match the norm-targeted walk's $\|D\|$ within a small constant while lowering the commutator. Third, sibling commutators must shrink geometrically with depth, roughly halving in $\delta$-normalized units per level. Fourth, product-formula error must track the measured commutator across all methods. If it does not, the objective is mis-specified for the application.
In the directed study, any counterexample to Conjecture 7.1 found by the search is itself a reportable result, and it would force the directed bounds to be restated with singular values.
References
- Introducing discrepancy values of matrices with application to bounding norms of commutators
- A new framework for matrix discrepancy: partial coloring bounds via mirror descent
- Spectral Sparsification by Deterministic Discrepancy Walk
- Fast Discrepancy Minimization with Hereditary Guarantees
- Discrepancy Minimization via Regularization
- A Unified Approach to Discrepancy Minimization
- A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
- GRASS: Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis