Geodesic
Geometric approaches to matrix normalization and graph balancing
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e149

Voir la notice de l'article provenant de la source Cambridge University Press

Normal matrices, or matrices which commute with their adjoints, are of fundamental importance in pure and applied mathematics. In this paper, we study a natural functional on the space of square complex matrices whose global minimizers are normal matrices. We show that this functional, which we refer to as the non-normal energy, has incredibly well-behaved gradient descent dynamics: despite it being nonconvex, we show that the only critical points of the non-normal energy are the normal matrices, and that its gradient descent trajectories fix matrix spectra and preserve the subset of real matrices. We also show that, even when restricted to the subset of unit Frobenius norm matrices, the gradient flow of the non-normal energy retains many of these useful properties. This is applied to prove that low-dimensional homotopy groups of spaces of unit norm normal matrices vanish; for example, we show that the space of $d \times d$ complex unit norm normal matrices is simply connected for all $d \geq 2$. Finally, we consider the related problem of balancing a weighted directed graph – that is, readjusting its edge weights so that the weighted in-degree and out-degree are the same at each node. We adapt the non-normal energy to define another natural functional whose global minima are balanced graphs and show that gradient descent of this functional always converges to a balanced graph, while preserving graph spectra and realness of the weights. Our results were inspired by concepts from symplectic geometry and Geometric Invariant Theory, but we mostly avoid invoking this machinery and our proofs are generally self-contained. 
Needham, Tom; Shonkwiler, Clayton. Geometric approaches to matrix normalization and graph balancing. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e149. doi: 10.1017/fms.2025.10105
@article{10_1017_fms_2025_10105,
     author = {Needham, Tom and Shonkwiler, Clayton},
     title = {Geometric approaches to matrix normalization and graph balancing},
     journal = {Forum of Mathematics, Sigma},
     pages = {e149},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10105},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10105/}
}
TY  - JOUR
AU  - Needham, Tom
AU  - Shonkwiler, Clayton
TI  - Geometric approaches to matrix normalization and graph balancing
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e149
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10105/
DO  - 10.1017/fms.2025.10105
ID  - 10_1017_fms_2025_10105
ER  - 
%0 Journal Article
%A Needham, Tom
%A Shonkwiler, Clayton
%T Geometric approaches to matrix normalization and graph balancing
%J Forum of Mathematics, Sigma
%D 2025
%P e149
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10105/
%R 10.1017/fms.2025.10105
%F 10_1017_fms_2025_10105

[1] Absil, P.-A. and Kurdyka, K., ‘On the stable equilibrium points of gradient systems’, Syst. Control Lett. 55(7) (2006), 573–577.10.1016/j.sysconle.2006.01.002 Google Scholar | DOI

[2] Asllani, M. and Carletti, T., ‘Topological resilience in non-normal networked systems’, Phys. Rev. E 97(4) (2018), 042302.10.1103/PhysRevE.97.042302 Google Scholar PubMed | DOI

[3] Asllani, M., Lambiotte, R. and Carletti, T., ‘Structure and dynamical behavior of non-normal networks’, Sci. Adv. 4(12) (2018), eaau9403.10.1126/sciadv.aau9403 Google Scholar PubMed | DOI

[4] Audin, M., Torus Actions on Symplectic Manifolds (Birkhäuser, Basel, 2nd rev. ed., 2004).10.1007/978-3-0348-7960-6 Google Scholar | DOI

[5] Bauer, F. L. and Fike, C. T., ‘Norms and exclusion theorems’, Numer. Math. 2(1) (1960), 137–141.10.1007/BF01386217 Google Scholar | DOI

[6] Ben-Israel, A. and Mond, B., ‘What is invexity?’, J. Austral. Math. Soc. Ser. B Appl. Math. 28(1) (1986), 1–9. Google Scholar | DOI

[7] Bodmann, B. G. and Haas, J., ‘Frame potentials and the geometry of frames’, J. Fourier Anal. Appl. 21(6) (2015), 1344–1383.10.1007/s00041-015-9408-z Google Scholar | DOI

[8] Böhm, C. and Lafuente, R. A., ‘Real geometric invariant theory’, in Dearricott, O., Tuschmann, W., Nikolayevsky, Y., Leistner, T. and Crowley, D. (eds.), Differential Geometry in the Large, No. 463 of London Mathematical Society Lecture Note Series (Cambridge Univ. Press, Cambridge, 2021), 11–49. Google Scholar

[9] Cahill, J., Mixon, D. G. and Strawn, N., ‘Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames’, SIAM J. Appl. Algebra Geom. 1(1) (2017), 38–72.10.1137/16M1068773 Google Scholar | DOI

[10] Calvo, M., Iserles, A. and Zanna, A., ‘Numerical solution of isospectral flows’, Math. Comp. 66(220) (1997), 1461–1486. Google Scholar

[11] Chu, M. T., ‘Least squares approximation by real normal matrices with specified spectrum’, SIAM J. Matrix Anal. Appl. 12(1) (1991), 115–127.10.1137/0612009 Google Scholar | DOI

[12] Chu, M. T., ‘Linear algebra algorithms as dynamical systems’, Acta Numer. 17 (2008), 1–86. Google Scholar

[13] Craven, B. D., ‘Duality for generalized convex fractional programs’, in Schaible, S. and Ziemba, W. T. (eds.), Generalized Concavity in Optimization and Economics: Proc. NATO Adv. Study Inst., Univ. British Columbia, Vancouver, Canada, Aug. 4–15, 1980 (Academic Press, New York, 1981), 473–489. Google Scholar

[14] Craven, B. D. and Glover, B. M., ‘Invex functions and duality’, J. Austral. Math. Soc. Ser. A Pure Math. Stat. 39(1) (1985), 1–20.10.1017/S1446788700022126 Google Scholar | DOI

[15] Daniel, R. W. and Kouvaritakis, B., ‘The choice and use of normal approximations to transfer-function matrices of multivariable control systems’, Int. J. Control 37(5) (1983), 1121–1133. Google Scholar

[16] Daniel, R. W. and Kouvaritakis, B., ‘Analysis and design of linear multivariable feedback systems in the presence of additive perturbations’, Int. J. Control 39(3) (1984), 551–580.10.1080/00207178408933188 Google Scholar | DOI

[17] Deift, P., Nanda, T. and Tomei, C., ‘Ordinary differential equations and the symmetric eigenvalue problem’, SIAM J. Numer. Anal. 20(1) (1983), 1–22. Google Scholar | DOI

[18] Ebert, J., ‘A lecture course on cobordism theory’, unpublished lecture notes (2012). URL: https://ivv5hpp.uni-muenster.de/u/jeber_02/skripten/bordism-skript.pdf. Google Scholar

[19] Elsner, L. and Ikramov, K. D., ‘Normal matrices: an update’, Linear Algebra Appl. 285(1–3) (1998), 291–303. Google Scholar

[20] Fisher, J. M., ‘Morse theory with the norm-square of a hyperKähler moment map’, Q. J. Math. 65(1) (2014), 149–173.10.1093/qmath/has045 Google Scholar | DOI

[21] Friedland, S., ‘Normal matrices and the completion problem’, SIAM J. Matrix Anal. Appl. 23(3) (2002), 896–902.10.1137/S0895479801386444 Google Scholar | DOI

[22] Gabriel, R., ‘The normal ΔH-matrices with connection to some Jacobi-like methods’, Linear Algebra Appl. 91 (1987), 181–194.10.1016/0024-3795(87)90070-X Google Scholar | DOI

[23] Godbillon, C., Éléments de topologie algébrique (Hermann, Paris, 1971). Google Scholar

[24] Gohberg, I., Lancaster, P. and Rodman, L., Invariant Subspaces of Matrices with Applications, No. 51 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM, Philadelphia, PA, 2006).10.1137/1.9780898719093 Google Scholar | DOI

[25] Guglielmi, N. and Scalone, C., ‘Computing the closest real normal matrix and normal completion’, Adv. Comput. Math. 45 (2019), 2867–2891.10.1007/s10444-019-09717-6 Google Scholar | DOI

[26] Hadjicostis, C. N. and Rikos, A., ‘Distributed strategies for balancing a weighted digraph’, in Proc. 20th Mediterr. Conf. Control Autom. (MED) (IEEE, 2012), 1141–1146. Google Scholar

[27] Hanson, M. A., ‘On sufficiency of the Kuhn–Tucker conditions’, J. Math. Anal. Appl. 80(2) (1981), 545–550.10.1016/0022-247X(81)90123-2 Google Scholar | DOI

[28] Hatcher, A., Algebraic Topology (Cambridge Univ. Press, Cambridge, 2002). Google Scholar

[29] Heinzner, P., Schwarz, G. W. and Stötzel, H., ‘Stratifications with respect to actions of real reductive groups’, Compos. Math. 144(1) (2008), 163–185.10.1112/S0010437X07003259 Google Scholar | DOI

[30] Henrici, P., ‘Bounds for iterates, inverses, spectral variation and fields of values of non-normal matrices’, Numer. Math. 4(1) (1962), 24–40. Google Scholar | DOI

[31] Higham, N. J., ‘Matrix nearness problems and applications’, in Gover, M. J. C. and Barnett, S. (eds.), Applications of Matrix Theory: Proc. Conf. Univ. Bradford, July 1988, vol. 22 of IMA Conf. Ser. New Ser. (Clarendon Press, Oxford Univ. Press, New York, 1989), 1–27. Google Scholar

[32] Hirsch, M. W., Differential Topology, No. 33 of Graduate Texts in Mathematics (Springer, New York, 2012). Google Scholar

[33] Loh, H.-T., ‘On a class of directed graphs—with an application to traffic-flow problems’, Oper. Res. 18(1) (1970), 87–94. Google Scholar

[34] Jacobson, N., ‘Rational methods in the theory of Lie algebras’, Ann. Math. (2) 36(4) (1935), 875–881. Google Scholar

[35] Jantzen, J. C., ‘Nilpotent orbits in representation theory’, in Anker, J.-P. and Orsted, B. (eds.), Lie Theory: Lie Algebras and Representations (Birkhäuser, Boston, MA, 2004), 1–211.10.1007/978-0-8176-8192-0 Google Scholar | DOI

[36] Kaplansky, I., ‘Jacobson’s Lemma revisited’, J. Algebra 62(2) (1980), 473–476.10.1016/0021-8693(80)90196-9 Google Scholar | DOI

[37] Kirwan, F., Cohomology of Quotients in Symplectic and Algebraic Geometry, vol. 31 of Math. Notes (Princeton Univ. Press, Princeton, NJ, 1984). Google Scholar

[38] Kostant, B., ‘Lie group representations on polynomial rings’, Amer. J. Math. 85(3) (1963), 327–404.10.2307/2373130 Google Scholar | DOI

[39] Lee, J. M., Introduction to Smooth Manifolds, No. 218 of Graduate Texts in Mathematics (Springer, New York, 2nd ed., 2013). Google Scholar

[40] Lerman, E., ‘Gradient flow of the norm squared of a moment map’, Enseign. Math. 51 (2005), 117–127. Google Scholar

[41] Łojasiewicz, S., ‘Sur les trajectoires du gradient d’une fonction analytique’, in Seminari di Geometria 1982–1983 (Dip. Mat., Univ. Bologna, 1984), 115–117. Google Scholar

[42] Marcus, M. and Minc, H., A Survey of Matrix Theory and Matrix Inequalities, Series in Advanced Mathematics (Allyn and Bacon, Boston, MA, 1964). Google Scholar

[43] Mixon, D. G., Needham, T., Shonkwiler, C. and Villar, S., ‘Three proofs of the Benedetto–Fickus theorem’, in Casey, S. D., Dodson, M. M., Ferreira, P. J. S. G. and Zayed, A. (eds.), Sampling, Approximation, and Signal Analysis: Harmonic Analysis in the Spirit of J. Rowland Higgins, Applied and Numerical Harmonic Analysis (Birkhäuser, Cham, 2023), 371–391. Google Scholar

[44] Mumford, D., Fogarty, J. and Kirwan, F., Geometric Invariant Theory, vol. 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete (Springer–Verlag, Berlin, 1994). Google Scholar

[45] Muolo, R., Asllani, M., Fanelli, D., Maini, P. K. and Carletti, T., ‘Patterns of non-normality in networked systems’, J. Theoret. Biol. 480 (2019), 81–91.10.1016/j.jtbi.2019.07.004 Google Scholar PubMed | DOI

[46] Needham, T. and Shonkwiler, C., ‘Symplectic geometry and connectivity of spaces of frames’, Adv. Comput. Math. 47(1) (2021), 5.10.1007/s10444-020-09842-7 Google Scholar | DOI

[47] Needham, T. and Shonkwiler, C., ‘Toric symplectic geometry and full spark frames’, Appl. Comput. Harmon. Anal. 61 (2022), 254–287.10.1016/j.acha.2022.07.004 Google Scholar | DOI

[48] Neeman, A., ‘The topology of quotient varieties’, Ann. Math. (2) 122(2) (1985), 419–459.10.2307/1971309 Google Scholar | DOI

[49] Ness, L., ‘A stratification of the null cone via the moment map’, Amer. J. Math. 106(6) (1984), 1281–1329.10.2307/2374395 Google Scholar | DOI

[50] Noschese, S. and Reichel, L., ‘The structured distance to normality of banded Toeplitz matrices’, BIT Numer. Math. 49 (2009), 629–640.10.1007/s10543-009-0231-2 Google Scholar | DOI

[51] Rikos, A. I., Charalambous, T. and Hadjicostis, C. N., ‘Distributed weight balancing over digraphs’, IEEE Trans. Control Netw. Syst. 1(2) (2014), 190–201. Google Scholar

[52] Ruhe, A., ‘Closest normal matrix finally found!’, BIT Numer. Math. 27 (1987), 585–598. Google Scholar | DOI

[53] Rutishauser, H., ‘Solution of eigenvalue problems with the LR-transformation’, in Further Contributions to the Solution of Simultaneous Linear Equations and the Determination of Eigenvalues, vol. 49 of National Bureau of Standards Applied Mathematics Series (U.S. Govt. Printing Office, Washington, DC, 1958), 47–81. Google Scholar

[54] Shonkwiler, C., Geometry of Normal Matrices. URL: https://github.com/shonkwiler/normal-matrices-computations. Google Scholar

[55] Thomas, R. P., ‘Notes on GIT and symplectic reduction for bundles and varieties’, Surv. Differ. Geom. 10(1) (2005), 221–273.10.4310/SDG.2005.v10.n1.a7 Google Scholar | DOI

[56] Tomei, C., ‘The Toda lattice, old and new’, J. Geom. Mech. 5(4) (2013), 511–530.10.3934/jgm.2013.5.511 Google Scholar | DOI

[57] Watkins, D. S., ‘Isospectral flows’, SIAM Rev. 26(3) (1984), 379–391.10.1137/1026075 Google Scholar | DOI

[58] Watkins, D. S. and Elsner, L., ‘On Rutishauser’s approach to self-similar flows’, SIAM J. Matrix Anal. Appl. 11(2) (1990), 301–311. Google Scholar

[59] Whitney, H., ‘Elementary structure of real algebraic varieties’, Ann. Math. 66(3) (1957), 545–556.10.2307/1969908 Google Scholar | DOI

[60] Woodward, C. T., ‘The Yang–Mills heat flow on the moduli space of framed bundles on a surface’, preprint (2002). . This is a preprint version of ‘The Yang–Mills heat flow on the moduli space of framed bundles on a surface’, Amer. J. Math. 128(2) (2006), 311–369.10.1353/ajm.2006.0017 Google Scholar | arXiv | DOI

Cité par Sources :