Imagine you are handed a matrix $A \in \mathbb{R}^{m \times n}$ and tasked with finding a vector $x \in \{-1, 1\}^n$ such that the maximum entry of the vector $Ax$ is as small as possible. This is the classic discrepancy problem: you want to color the columns of $A$ with $+1$ or $-1$ so that the properties represented by the rows remain as balanced (close to $0$) as possible.
Hereditary discrepancy ($\text{herdisc}(A)$) takes this a step further. It asks for a discrepancy guarantee not just for the whole matrix, but for any submatrix formed by choosing a subset of its columns. It is a highly robust, intrinsic measure of a matrix's combinatorial complexity.
At first glance, computing or approximating hereditary discrepancy feels like a purely discrete, combinatorial nightmare. You must reason over exponentially many column subsets and discrete colorings. However, a powerful line of research has revealed that this combinatorial property is deeply mirrored by the continuous geometric and spectral invariants of the matrix—such as its eigenvalues, volumes, and determinants.
The Geometric View: Ellipsoids and Volumes
To understand why continuous geometry dictates discrete discrepancy, think of the columns of $A$ as points in space. A coloring $x \in \{-1, 1\}^n$ forms a linear combination of these points. Minimizing the $\ell_\infty$ norm of $Ax$ means we want this linear combination to land inside a small, origin-centered bounding box.
Aleksandar Nikolov et al. bridged this gap in Approximating Hereditary Discrepancy via Small Width Ellipsoids by connecting hereditary discrepancy to a classic geometric optimization problem: finding the smallest ellipsoid that encloses a given set of points. If a set of points can be tightly bound by an ellipsoid of small width, the matrix columns cannot stretch space too drastically in any single direction. By leveraging this ellipsoid characterization, the authors bypassed complex combinatorial structures to design a polynomial-time algorithm that approximates hereditary discrepancy within an improved $O(\log^{3/2} m)$ factor, a substantial enhancement over previous methods.
This volume-based perspective naturally extends to determinants, which measure the volumes of parallelotopes spanned by matrix vectors. If a matrix has low hereditary discrepancy, it shouldn't contain any submatrix with an overwhelmingly large volume. Victor Reis et al. formalized this intuition in A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound by tightening the relationship between hereditary discrepancy and the determinant lower bound ($\text{detLB}$). Using a randomized algorithm inspired by random walks and analyzing the dual of a semidefinite programming (SDP) formulation, the authors proved that the hereditary partial vector discrepancy is tightly bounded by this determinant lower bound.
To make these determinant bounds algorithmically practical, one needs to find the largest subdeterminants efficiently. Nima Anari et al. advanced this in An Extension of Plücker Relations with Applications to Subdeterminant Maximization by showing that polynomial-time algorithms can approximate the maximum absolute subdeterminant of a general matrix within a factor depending solely on the submatrix size. This provides a concrete, efficient method for estimating lower bounds in hereditary discrepancy theory.
The Spectral View: Eigenvalues of $A^TA$
While ellipsoids and determinants offer a geometric macro-view, the fine-grained structure of hereditary discrepancy is governed directly by the spectrum of the matrix itself—specifically, the eigenvalues of $A^T A$.
In Constructive Discrepancy Minimization with Hereditary L2 Guarantees, Kasper Green Larsen established a direct, constructive link between these eigenvalues and discrepancy guarantees. He introduced novel theoretical inequalities connecting the hereditary $\ell_2$ and $\ell_\infty$ discrepancies directly to the eigenvalues of $A^T A$. This allowed for a near-optimal discrepancy minimization algorithm that completely avoided the computationally heavy semidefinite programs traditionally used in the field, relying instead on clean matrix eigendecompositions.
Why do the eigenvalues of $A^T A$ matter so much? Kasper Green Larsen uncovered the underlying structural reason in Fast Discrepancy Minimization with Hereditary Guarantees: matrices with low hereditary discrepancy possess a unique structural decomposition. If you project the matrix rows onto a specific subspace spanned by the top eigenvectors of $A^T A$, the norm of the remaining row components drops drastically. By exploiting this geometric decay, he designed a highly efficient, practical polynomial-time algorithm for discrepancy minimization, bridging the long-standing gap between theoretical discrepancy bounds and real-world computational viability.
From Discrepancy Back to Pure Linear Algebra
The interplay between discrepancy and spectral properties does not just benefit combinatorial optimization; it also flows backward to enrich pure linear algebra.
Pourya Habib Zadeh generalized these concepts in Introducing Discrepancy Values of Matrices with Application to Bounding Norms of Commutators by introducing discrepancy values for arbitrary square complex matrices. This concept generalizes the classical notion of "spectral spread" (the difference between eigenvalues) from Hermitian matrices to all matrices. By defining discrepancy values through a modification of Ky-Fan norms, he demonstrated that the norm of a matrix commutator ($AB - BA$) is weakly majorized by twice the product of their respective discrepancy values. This approach provides a significantly sharper toolkit for error bounding in linear algebra than traditional singular value products, proving that discrepancy-based thinking offers deep insights into the fundamental geometry of operators.
Key Foundational Work
Approximating Hereditary Discrepancy via Small Width Ellipsoids (2015) — contributed 4 concept elements to this direction.
Constructive Discrepancy Minimization with Hereditary L2 Guarantees (2019) — contributed 2 concept elements to this direction.