Nearest matrix with multiple eigenvalues by Riemannian optimization

Federico Poloni; Lauri Nyman; Vanni Noferini

arxiv: 2509.26344 · v2 · pith:M3BSE2PNnew · submitted 2025-09-30 · 🧮 math.NA · cs.NA

Nearest matrix with multiple eigenvalues by Riemannian optimization

Vanni Noferini , Lauri Nyman , Federico Poloni This is my paper

Pith reviewed 2026-05-18 12:02 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords nearest defective matrixRiemannian optimizationvariable projectionmultiple eigenvaluesmatrix nearness problemseigenvalue condition numbersstructured perturbations

0 comments

The pith

Extending Riemannian optimization to track left and right eigenvectors finds the nearest matrix with multiple eigenvalues under linear constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a computational method for finding the closest square complex matrix to a given matrix A that has at least one multiple eigenvalue. When A has distinct eigenvalues this is the same as locating the nearest defective matrix. The approach builds on an existing variable-projection Riemannian optimizer by enlarging the ambient manifold so that it can follow both left and right eigenvectors at once. The same construction permits arbitrary complex-linear constraints on the perturbation or on the perturbed matrix itself, which is useful when studying structured eigenvalue condition numbers. Numerical tests are given that compare the new procedure against earlier algorithms.

Core claim

By extending the ambient manifold in the variable-projection Riemannian framework to track left and right eigenvectors simultaneously, the nearness problem for matrices possessing multiple eigenvalues becomes solvable, and the same construction admits arbitrary complex-linear constraints on either the perturbation or the resulting matrix.

What carries the argument

Extended Riemannian manifold that parametrizes matrices with repeated eigenvalues by jointly tracking left and right eigenvectors, combined with variable-projection optimization.

If this is right

Distances to the set of matrices with repeated eigenvalues can be computed for both unstructured and linearly constrained cases.
Structured eigenvalue condition numbers become numerically accessible through the imposed linear constraints.
The same optimizer supplies a general tool for other matrix nearness problems that involve algebraic multiplicity.
Direct numerical comparisons with preexisting methods are possible on standard test matrices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The framework could be specialized to matrices with additional structure such as symmetry or sparsity to obtain new structured distance results.
Connections to stability margins in linear dynamical systems follow because the distance to defectivity governs certain robustness measures.
Local-minimum avoidance strategies from other Riemannian problems might be transferred to improve reliability on larger examples.

Load-bearing premise

The Riemannian optimization on the extended manifold reaches the globally nearest defective matrix rather than stopping at a local minimum.

What would settle it

Apply the algorithm to a small explicit matrix whose minimal perturbation to eigenvalue multiplicity is already known by direct algebraic calculation and check whether the computed distance agrees.

read the original abstract

Given a square complex matrix $A$, we tackle the problem of finding the nearest matrix with multiple eigenvalues or, equivalently when $A$ had distinct eigenvalues, the nearest defective matrix. To this goal, we extend the general framework described in [M. Gnazzo, V. Noferini, L. Nyman, F. Poloni, \emph{Riemann-Oracle: A general-purpose Riemannian optimizer to solve nearness problems in matrix theory}, Found. Comput. Math., To appear] and based on variable projection and Riemannian optimization, allowing the ambient manifold to simultaneously track left and right eigenvectors. Our method also allows us to impose arbitrary complex-linear constraints on either the perturbation or the perturbed matrix; this can be useful to study structured eigenvalue condition numbers. We present numerical experiments, comparing with preexisting algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends the Riemann-Oracle framework to track left and right eigenvectors together for the nearest defective matrix problem, with added constraint handling and some experiments.

read the letter

This paper extends the Riemann-Oracle framework to find the nearest matrix with a multiple eigenvalue. The key move is to build a manifold that tracks both left and right eigenvectors at once while allowing arbitrary complex-linear constraints on the perturbation or the matrix. That constraint feature is the part that could matter for structured eigenvalue condition numbers in applications like control theory. They run numerical experiments that compare the approach to earlier methods, which at least shows it can be implemented and run on examples. The extension itself is concrete and builds directly on their prior variable-projection plus Riemannian setup. The main limitation is that the underlying optimization remains non-convex. Nothing in the work proves the manifold is geodesically convex or that the chosen retraction and steps reliably reach the global minimum distance to the defective set. The experiments compare distances but do not appear to test against known global solutions or run many random initializations on the same instance to check for local minima. That leaves the central claim about finding the actual nearest matrix only partially supported. This is aimed at people in numerical linear algebra who need computational tools for nearness problems involving eigenvalues or structured perturbations. A reader who wants a practical method to try on defective-matrix examples would get something usable from the constraint option and the reported runs. It is worth sending to referees because the extension is clearly motivated, the experiments give something concrete to check, and the constraint handling is a genuine addition even if the theory side needs more work on convergence.

Referee Report

2 major / 2 minor

Summary. The paper extends the authors' prior Riemann-Oracle framework (variable projection plus Riemannian optimization) to compute the nearest matrix with multiple eigenvalues. The extension equips the ambient manifold with simultaneous left- and right-eigenvector tracking and permits arbitrary complex-linear constraints on the perturbation or the perturbed matrix; numerical experiments compare the resulting distances against preexisting algorithms.

Significance. If the method reliably locates global minima, the work supplies a flexible, constraint-aware tool for structured nearness problems and eigenvalue condition numbers. The technical contribution lies in the concrete manifold construction and the variable-projection scheme that incorporates both left and right eigenvectors; this is a direct, incremental advance on the cited prior framework rather than an entirely new paradigm.

major comments (2)

[§3] §3 (Manifold and retraction): the construction of the extended manifold that tracks both left and right eigenvectors is presented without a proof or even a heuristic argument that the resulting non-convex problem is free of spurious local minima; because the headline claim is the globally nearest defective matrix, this omission is load-bearing.
[§5] §5 (Numerical experiments): the reported comparisons give single-run distances but do not include systematic multi-start experiments or known global optima on the same instances; without such checks it is impossible to verify that the optimizer consistently reaches the global minimizer rather than a local one.

minor comments (2)

[§2] The notation for the product manifold and the projection operators could be introduced more explicitly in the first paragraph of §2 to improve readability for readers unfamiliar with the prior Riemann-Oracle paper.
A short table summarizing the constraint types that can be imposed (and which variables they act on) would help readers quickly assess the scope of the new capability.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the careful review and constructive feedback on our extension of the Riemann-Oracle framework. We address each major comment below and will revise the manuscript to improve clarity and experimental validation.

read point-by-point responses

Referee: [§3] §3 (Manifold and retraction): the construction of the extended manifold that tracks both left and right eigenvectors is presented without a proof or even a heuristic argument that the resulting non-convex problem is free of spurious local minima; because the headline claim is the globally nearest defective matrix, this omission is load-bearing.

Authors: We agree that the manuscript provides neither a proof nor a heuristic argument guaranteeing the absence of spurious local minima. The underlying optimization problem is non-convex, and establishing global optimality for the nearest defective matrix problem remains generally intractable. Our contribution centers on the concrete construction of the manifold that simultaneously tracks left and right eigenvectors together with the variable-projection scheme that accommodates arbitrary complex-linear constraints. In the revised version we will explicitly state that the method computes local critical points, clarify that global optimality is not guaranteed, and add a short discussion of the geometric features of the manifold and the variable-projection step that, in our numerical experience, favor convergence to high-quality solutions. revision: yes
Referee: [§5] §5 (Numerical experiments): the reported comparisons give single-run distances but do not include systematic multi-start experiments or known global optima on the same instances; without such checks it is impossible to verify that the optimizer consistently reaches the global minimizer rather than a local one.

Authors: We acknowledge that the experiments report results from single optimization runs and lack systematic multi-start statistics or comparisons against known global optima. To strengthen the evidence, the revised experimental section will incorporate multi-start trials on the reported test cases and, for smaller matrices where exhaustive or literature-based global optima are available, direct comparisons of the obtained distances. revision: yes

standing simulated objections not resolved

A rigorous proof or heuristic that the non-convex problem is free of spurious local minima

Circularity Check

1 steps flagged

Central method extends authors' prior Riemann-Oracle framework via overlapping self-citation

specific steps

self citation load bearing [Abstract]
"we extend the general framework described in [M. Gnazzo, V. Noferini, L. Nyman, F. Poloni, Riemann-Oracle: A general-purpose Riemannian optimizer to solve nearness problems in matrix theory, Found. Comput. Math., To appear] and based on variable projection and Riemannian optimization, allowing the ambient manifold to simultaneously track left and right eigenvectors."

The paper's primary methodological contribution and solution strategy for the nearest-matrix-with-multiple-eigenvalues problem is justified by direct extension of the optimization framework from a prior publication sharing three authors. No independent derivation of the base variable-projection or Riemannian scheme appears in the present manuscript; the new features are layered on top of the imported framework.

full rationale

The paper's core approach to computing the nearest defective matrix is explicitly built as an extension of the variable-projection Riemannian optimization framework introduced in a prior paper by three of the same authors (Gnazzo, Noferini, Nyman, Poloni). While the current work adds new elements such as simultaneous left/right eigenvector tracking and complex-linear constraints, the load-bearing optimization machinery and variable-projection scheme are imported from the cited self-work rather than re-derived or independently justified here. Numerical experiments provide some external comparison, so the central claim retains independent content and the circularity remains moderate rather than total.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the Riemannian manifold structure and variable-projection technique from the authors' earlier work; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption The space of matrices with tracked left and right eigenvectors forms a suitable Riemannian manifold for optimization
Invoked when extending the prior framework to simultaneously track eigenvectors.

pith-pipeline@v0.9.0 · 5664 in / 1113 out tokens · 41970 ms · 2026-05-18T12:02:46.077679+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We adapt the general framework described in [9] ... translating the problem ... into a minimization task on the complex Stiefel manifold V2(Cn) ... fε,y(u,v,λ)=r∗(MM∗+εI)−1r ... Riemannian gradient ... on V2(Cn).
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

nearest matrix with multiple eigenvalues ... nearest defective matrix ... additional linear constraint on either Δ or A+Δ

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

R. O. Akinola, M. A. Freitag, and A. Spence. The calculation of the distance to a nearby defective matrix.Numer. Linear Algebra Appl., 21(4):403–414, 2014

work page 2014
[2]

Alam and S

R. Alam and S. Bora. On sensitivity of eigenvalues and eigendecompositions of matrices. Linear Algebra Appl., 396:273–301, 2005

work page 2005
[3]

R. Alam, S. Bora, R. Byers, and M. L. Overton. Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components.Linear Algebra Appl., 435:494–513, 2011

work page 2011
[4]

Bj¨ orck.Numerical methods for least squares problems

˚A. Bj¨ orck.Numerical methods for least squares problems. SIAM, Philadelphia, PA, 1996

work page 1996
[5]

R. F. Boisvert, E. G. Kahaner, and C. B. Moler. Matrix market: A web resource for test matrix collections.ACM Transactions on Mathematical Software (TOMS), 29(2):209– 214, 1994

work page 1994
[6]

Cambridge University Press, Cambridge, UK (2023)

N. Boumal.An introduction to optimization on smooth manifolds. Cambridge Uni- versity Press, Cambridge, 2023. URL:https://www.nicolasboumal.net/book,doi: 10.1017/9781009166164

work page doi:10.1017/9781009166164 2023
[7]

Butt` a, N

P. Butt` a, N. Guglielmi, M. Manetta, and S. Noschese. Differential equations for real- structured defectivity measures.SIAM J. Matrix Anal. Appl., 36(2):523–548, 2015

work page 2015
[8]

J. W. Demmel. Computing stable eigendecompositions of matrices.Linear Algebra Appl., 79:163–193, 1986

work page 1986
[9]

Gnazzo, V

M. Gnazzo, V. Noferini, L. Nyman, and F. Poloni. Riemann-Oracle: A general-purpose Riemannian optimizer to solve nearness problems in matrix theory.Found. Comput. Math., 2025. To appear

work page 2025
[10]

Guglielmi and C

N. Guglielmi and C. Lubich. Matrix nearness problems and eigenvalue optimization. Preprint, arXiv:2503.14750 [math.NA] (2025), 2025. URL:https://arxiv.org/abs/ 2503.14750

work page arXiv 2025
[11]

N. J. Higham.Nearness Problems in Numerical Linear Algebra. PhD thesis, University of Manchester, 1985

work page 1985
[12]

N. J. Higham. Computing a nearest symmetric positive semidefinite matrix.Linear Algebra Appl., 103:103–118, 1988

work page 1988
[13]

N. J. Higham. Matrix nearness problems and applications. InM. J. C. Gover and S. Barnett, editors, Applications of Matrix Theory, pages 1–27. Oxford University Press, Oxford, UK, 1989. 20

work page 1989
[14]

N. J. Higham. Computing the nearest correlation matrix—a problem from finance.IMA J. Numer. Anal., 22(3):329–343, 2002

work page 2002
[15]

Kalinina, A

E. Kalinina, A. Uteshev, M. Goncharova, and E. Lezhnina. On the distance to the nearest defective matrix. In F. Boulier, M. England, I. Kotsireas, T. M. Sadykov, and E. V. Vorozhtsov, editors,Computer Algebra in Scientific Computing, pages 255–271, Cham, 2023. Springer Nature Switzerland

work page 2023
[16]

R. A. Lippert and A. Edelman. The computation and sensitivity of double eigenvalues. InAdvances in computational mathematics (Guangzhou, 1997), volume 202 ofLecture Notes in Pure and Appl. Math., pages 353–393. Dekker, New York, 1999

work page 1997
[17]

Noferini and L

V. Noferini and L. Nyman. Finding the nearest Ω-stable pencil with Riemannian opti- mization.Numer. Algo., 2025.doi:https://doi.org/10.1007/s11075-025-02140-7

work page doi:10.1007/s11075-025-02140-7 2025
[18]

Usevich and I

K. Usevich and I. Markovsky. Variable projection for affinely structured low-rank approximation in weighted 2-norms.J. Comput. Appl. Math., 272:430–448, 2014. doi:10.1016/j.cam.2013.04.034

work page doi:10.1016/j.cam.2013.04.034 2014
[19]

J. H. Wilkinson. Sensitivity of eigenvalues.Utilitas Math., 25:5–76, 1984

work page 1984
[20]

J. H. Wilkinson. Sensitivity of eigenvalues - II.Utilitas Math., 30:243–286, 1986. 21

work page 1986

[1] [1]

R. O. Akinola, M. A. Freitag, and A. Spence. The calculation of the distance to a nearby defective matrix.Numer. Linear Algebra Appl., 21(4):403–414, 2014

work page 2014

[2] [2]

Alam and S

R. Alam and S. Bora. On sensitivity of eigenvalues and eigendecompositions of matrices. Linear Algebra Appl., 396:273–301, 2005

work page 2005

[3] [3]

R. Alam, S. Bora, R. Byers, and M. L. Overton. Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components.Linear Algebra Appl., 435:494–513, 2011

work page 2011

[4] [4]

Bj¨ orck.Numerical methods for least squares problems

˚A. Bj¨ orck.Numerical methods for least squares problems. SIAM, Philadelphia, PA, 1996

work page 1996

[5] [5]

R. F. Boisvert, E. G. Kahaner, and C. B. Moler. Matrix market: A web resource for test matrix collections.ACM Transactions on Mathematical Software (TOMS), 29(2):209– 214, 1994

work page 1994

[6] [6]

Cambridge University Press, Cambridge, UK (2023)

N. Boumal.An introduction to optimization on smooth manifolds. Cambridge Uni- versity Press, Cambridge, 2023. URL:https://www.nicolasboumal.net/book,doi: 10.1017/9781009166164

work page doi:10.1017/9781009166164 2023

[7] [7]

Butt` a, N

P. Butt` a, N. Guglielmi, M. Manetta, and S. Noschese. Differential equations for real- structured defectivity measures.SIAM J. Matrix Anal. Appl., 36(2):523–548, 2015

work page 2015

[8] [8]

J. W. Demmel. Computing stable eigendecompositions of matrices.Linear Algebra Appl., 79:163–193, 1986

work page 1986

[9] [9]

Gnazzo, V

M. Gnazzo, V. Noferini, L. Nyman, and F. Poloni. Riemann-Oracle: A general-purpose Riemannian optimizer to solve nearness problems in matrix theory.Found. Comput. Math., 2025. To appear

work page 2025

[10] [10]

Guglielmi and C

N. Guglielmi and C. Lubich. Matrix nearness problems and eigenvalue optimization. Preprint, arXiv:2503.14750 [math.NA] (2025), 2025. URL:https://arxiv.org/abs/ 2503.14750

work page arXiv 2025

[11] [11]

N. J. Higham.Nearness Problems in Numerical Linear Algebra. PhD thesis, University of Manchester, 1985

work page 1985

[12] [12]

N. J. Higham. Computing a nearest symmetric positive semidefinite matrix.Linear Algebra Appl., 103:103–118, 1988

work page 1988

[13] [13]

N. J. Higham. Matrix nearness problems and applications. InM. J. C. Gover and S. Barnett, editors, Applications of Matrix Theory, pages 1–27. Oxford University Press, Oxford, UK, 1989. 20

work page 1989

[14] [14]

N. J. Higham. Computing the nearest correlation matrix—a problem from finance.IMA J. Numer. Anal., 22(3):329–343, 2002

work page 2002

[15] [15]

Kalinina, A

E. Kalinina, A. Uteshev, M. Goncharova, and E. Lezhnina. On the distance to the nearest defective matrix. In F. Boulier, M. England, I. Kotsireas, T. M. Sadykov, and E. V. Vorozhtsov, editors,Computer Algebra in Scientific Computing, pages 255–271, Cham, 2023. Springer Nature Switzerland

work page 2023

[16] [16]

R. A. Lippert and A. Edelman. The computation and sensitivity of double eigenvalues. InAdvances in computational mathematics (Guangzhou, 1997), volume 202 ofLecture Notes in Pure and Appl. Math., pages 353–393. Dekker, New York, 1999

work page 1997

[17] [17]

Noferini and L

V. Noferini and L. Nyman. Finding the nearest Ω-stable pencil with Riemannian opti- mization.Numer. Algo., 2025.doi:https://doi.org/10.1007/s11075-025-02140-7

work page doi:10.1007/s11075-025-02140-7 2025

[18] [18]

Usevich and I

K. Usevich and I. Markovsky. Variable projection for affinely structured low-rank approximation in weighted 2-norms.J. Comput. Appl. Math., 272:430–448, 2014. doi:10.1016/j.cam.2013.04.034

work page doi:10.1016/j.cam.2013.04.034 2014

[19] [19]

J. H. Wilkinson. Sensitivity of eigenvalues.Utilitas Math., 25:5–76, 1984

work page 1984

[20] [20]

J. H. Wilkinson. Sensitivity of eigenvalues - II.Utilitas Math., 30:243–286, 1986. 21

work page 1986