Introducing discrepancy values of matrices with application to bounding norms of commutators

Pourya Habib Zadeh, Suvrit Sra

TL;DR

This paper introduces discrepancy values, a novel matrix quantity that generalizes the concept of "spectral spread" from Hermitian matrices to all square complex matrices. By defining these values through a modification of Ky-Fan norms, the authors provide a powerful new toolkit for linear algebra, most notably achieving tighter bounds on the norms of matrix commutators ($AB - BA$).

What Problem Does This Paper Address?

In linear algebra, eigenvalues and singular values are the "gold standard" for describing matrix behavior. However, certain applications—like stability analysis or quantum mechanics—rely on the spectral spread, which measures the dispersion of a matrix's eigenvalues (e.g., the difference between the largest and smallest eigenvalue).

While spectral spread is well-defined and "well-behaved" for Hermitian matrices (those equal to their own conjugate transpose), it falls apart for general complex matrices. Existing generalizations often lose the elegant mathematical properties (like majorization and convexity) that make them useful for optimization and error bounding. The authors sought a new metric that works for any square matrix while retaining the "nice" properties of the Hermitian spread.

Methods

The authors define discrepancy values ($\delta_k$) by introducing a "discrepancy seminorm."

  1. The Twist on Ky-Fan Norms: A standard Ky-Fan $k$-norm is the sum of the $k$ largest singular values. The authors add a single, "innocuous-looking" constraint: the sum of the inner products of the associated orthonormal vectors must be zero ($\sum \langle x_j, y_j \rangle = 0$).
  2. Variational Characterization: They prove a beautiful dual identity: the $k$-th discrepancy seminorm of a matrix $A$ is exactly equal to the minimum Ky-Fan $k$-norm of $A$ shifted by a scalar multiple of the identity ($A - \alpha I$). Essentially, it measures the "distance" of a matrix to the set of scalar matrices.
  3. Computational Tools: The authors show that these values aren't just theoretical; they can be calculated efficiently using Semidefinite Programming (SDP) or, for normal matrices, Second-Order Cone Programming (SOCP).

Datasets

Not discussed in the paper. This is a theoretical work in linear algebra and functional analysis; it relies on mathematical proofs rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • Bridging the Gap: For Hermitian matrices, discrepancy values turn out to be exactly half the difference between symmetric pairs of eigenvalues ($|\lambda_i - \lambda_{n-i+1}|/2$). This confirms they are a true generalization of spectral spread.
  • The "Distance to Identity" Interpretation: One of the most intuitive takeaways is that discrepancy values represent a vector-valued cost of approximating a linear operator using only scalar multiples of the identity matrix.
  • Majorization Power: The authors establish that discrepancy values are "weakly majorized" by singular values ($\delta(A) \prec_w \sigma(A)$). This allows researchers to use discrepancy values in existing inequality frameworks to get sharper results.
  • Maximizing Non-Commutativity: The paper identifies exactly how to rotate two Hermitian matrices to make them "maximally non-commutative" (meaning their commutator $[A, B]$ has the largest possible norm). This happens when their eigenspaces are rotated by $\pi/4$ relative to each other.

Key Results

  • Tighter Commutator Bounds: The headline result is a new bound for the commutator: $\sigma([A, B]) \prec_w 2\delta(A)\delta(B)$ (proven for several cases including when one matrix is Hermitian). This is often significantly tighter than the standard bound $2\sigma(A)\sigma(B)$.
  • Unitary Invariance: Discrepancy values inherit the best traits of singular values: they are invariant under unitary conjugation, phase shifts, and shifts by the identity matrix.
  • Principal Angles: The authors provide a new, simpler proof for upper-bounding the principal angles between subspaces using discrepancy values.

Limitations and Future Work

  • The General Conjecture: While the authors prove their main commutator inequality for Hermitian and normal matrices, they leave the general case—$\sigma([A, B]) \prec_w 2\delta(A)\delta(B)$ for any two square matrices—as an open Conjecture (7.1). They demonstrate it holds for $2 \times 2$ matrices, but the full proof remains elusive.
  • Infinite Dimensions: The paper briefly touches on extending these results to compact operators on infinite-dimensional Hilbert spaces. Fully fleshing out this extension for non-compact operators could be a significant future direction.
  • Numerical Stability: While SDP formulations are provided, the numerical stability and performance of calculating these values for extremely large, sparse matrices in a production environment (e.g., large-scale machine learning) haven't been explored.

Summary updated

Abstract

We introduce discrepancy values, quantities inspired by the notion of the spectral spread of Hermitian matrices. We define them as the discrepancy between two consecutive Ky-Fan-like seminorms. As a result, discrepancy values share many properties with singular values and eigenvalues, yet are substantially different to merit their own study. We describe key properties of discrepancy values, and establish several tools such as representation theorems, majorization inequalities, convex formulations, etc., for working with them. As an important application, we illustrate the role of discrepancy values in deriving tight bounds on the norms of commutators.
BibTeX
@inproceedings{zadeh2022introducing,
  author = {Pourya Habib Zadeh and Suvrit Sra},
  title = {{Introducing discrepancy values of matrices with application to bounding norms of commutators}},
  booktitle = {Linear},
  year = {2022},
  doi = {10.1016/j.laa.2022.06.026},
}

Loading related content...

Figure