pith. sign in

arxiv: 2606.07407 · v1 · pith:TBM4LU2Xnew · submitted 2026-06-05 · 🧮 math.AG

Structured matrix factorization length

Jeong-Hoon Ju , Taehyeong Kim This is my paper

Pith reviewed 2026-06-27 20:57 UTC · model grok-4.3

classification 🧮 math.AG
keywords Toeplitz matricesmatrix factorizationstructured matricesZariski closurefactorization lengthdisplacement rankalgebraic geometry
0
0 comments X

The pith

Every complex n by n matrix factors as a product of 2n+5 Toeplitz matrices.

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

The paper establishes that any n by n complex matrix can be written as a product of 2n+5 Toeplitz matrices and that a generic matrix requires only floor(n/2)+1 such factors. It generalizes the question by treating any matrix structure as an affine variety X inside the space of n by n matrices and defining the r-th X-factorization variety as the Zariski closure of all products of exactly r elements from X. Dimensions of these varieties are computed explicitly for Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric, and companion structures, which in turn determine the border structured matrix factorization length. The work supplies both lower bounds via displacement rank and upper bounds via alternating minimization, along with a numerical algebraic geometry method to extract degrees of the varieties.

Core claim

Every complex n by n matrix can be expressed as a product of 2n+5 Toeplitz matrices, while a generic matrix requires only floor(n/2)+1 factors. For a general affine variety X of structured matrices the r-th X-factorization variety is the Zariski closure of the set of all products of r matrices from X; its dimension equals the largest rank attainable by such products and therefore fixes the border structured factorization length. The paper computes these dimensions for the varieties of Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric and companion matrices and supplies explicit lower and upper bounds on the lengths together with a displacement-rank method that also yields defining eq

What carries the argument

The r-th X-factorization variety, the Zariski closure of the image of the multiplication map X^r to the space of n by n matrices.

If this is right

  • The Toeplitz factorization length is at most 2n+5 for every matrix and equals floor(n/2)+1 for a generic matrix.
  • Dimensions of the r-th factorization varieties are known for Hankel, bidiagonal, tridiagonal, skew-symmetric and companion structures.
  • Displacement rank supplies both lower bounds on the length and explicit equations for the factorization varieties.
  • Alternating minimization yields practical upper bounds on the length for any given matrix and structure.
  • Numerical algebraic geometry can compute the degrees of the factorization varieties in small cases.

Where Pith is reading between the lines

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

  • The same dimension calculations could be applied to additional matrix structures such as circulant or persymmetric varieties.
  • The displacement-rank equations might be used to certify that a given matrix lies outside a particular factorization variety.
  • The alternating-minimization heuristic could be turned into a certified algorithm once the degrees of the varieties are known.

Load-bearing premise

The set of matrices with a fixed structure forms an affine variety whose finite products admit a well-defined Zariski closure whose dimension has geometric meaning.

What would settle it

For a concrete n, compute the dimension of the (2n+5)-th Toeplitz factorization variety; if the result is strictly less than n squared then not every matrix factors into that many Toeplitz matrices.

Figures

Figures reproduced from arXiv: 2606.07407 by Jeong-Hoon Ju, Taehyeong Kim.

Figure 1
Figure 1. Figure 1: The set at (4.6) is the union of {L1,1, L2,1, L3,1}, {L2,4, L3,4, L4,4}, and {L4,1, L4,2, L3,2, L2,2, L1,2, L1,3, L1,4}. From (4.3), we obtain τ2 = (T2, T3). Let X2 and X3 be matrices such that [X2]i,j := x2,j−i and [X3]i,j := x3,j−i where the variables xk,j−i ’s are all independent. Then we have that d(m2)τ2 (X2, X3) = X2T3 + T2X3. Consider the change of coordinates defined by  yj zj  =  1 1 1 0 x2,j… view at source ↗
Figure 2
Figure 2. Figure 2: The set at (4.8) is the union of {L1,1, ..., L5,1}, {L2,6, ..., L6,6}, {L1,2, ..., L5,2}, {L2,5, ..., L6,5} and {L6,1, L6,2, L6,3, L5,3, L4,3, L3,3, L2,3, L1,3, L1,4, L1,5, L1,6}. Example 4.7. Consider the case where (n, r) = (6, 3). We calculate the dimension of µ3(T6) ⊊ C6×6 . Consider the matrix multiplication map m3 : T6 × T6 × T6 → C 6×6 . From (4.2) and (4.3), we obtain T3 = B0 + t3(B3 − B−3), T4 = B… view at source ↗
Figure 3
Figure 3. Figure 3: The way of selecting the ordered positions Lp,q: Select {L1,1, L2,1, ..., Ln−1,1} on the first column, {L2,n, L3,n, ..., Ln,n} on the last column, {L1,2, L2,2, ..., Ln−1,2} on the second column, {L2,n−1, L3,n−1, ..., Ln,n−1} on the second-to-last column. Keep similarly up to keeping {L1,r−1, L2,r−1, ..., Ln−1,r−1} on the (r − 1)-th column, {L2,n−r+2, L3,n−r+2, ..., Ln,n−r+2} on the (n − r + 2)-th column, a… view at source ↗
Figure 4
Figure 4. Figure 4: Residuals for the alternating minimization method applied to the 3 × 3 Toeplitz factorization. The residual is shown on a logarithmic scale. Iterating this inequality over k = 1, . . . , r gives Fs+1 ≤ Fs. Since Fs ≥ 0, the sequence {Fs}s≥0 has a finite limit, and the residuals are √ 2Fs. □ Remark 6.2. This result concerns only the objective values. In particular, it does not imply that the limiting residu… view at source ↗
Figure 5
Figure 5. Figure 5: Residuals for the alternating minimization method applied to the 5 ×5 target matrix from [19, Example 2] with r = 15. The residual is shown on a logarithmic scale [PITH_FULL_IMAGE:figures/full_fig_p031_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Computed Toeplitz factors M1, . . . , M15 for the 5 × 5 example. All factors are displayed on the same color scale. the construction displayed there expresses the target as a product of Toeplitz factors together with permutation matrices. We choose r = 15 because the general upper bound 2n + 5 in Theorem 2.1.(ii) gives 2 · 5 + 5 = 15 for n = 5. Thus this experiment tests whether the alternating minimizatio… view at source ↗
read the original abstract

Every (resp. a generic) complex $n \times n$ matrix can be expressed as a product of $2n+5$ (resp. $\lfloor n/2 \rfloor +1$) Toeplitz matrices. Motivated by this result, it is natural to ask the following question: what is the minimum number of Toeplitz matrices required to factor a given matrix? We generalize this question from Toeplitz structure to more general structures. In this paper, we introduce the notion of structured matrix factorization length when the set of matrices with a given structure is an affine variety $X \subseteq \mathbb{C}^{n \times n}$. Then we introduce the $r$-th $X$-factorization variety, defined as the Zariski closure of the set of products of $r$ matrices in $X$, and use it to define the border structured matrix factorization length. In particular, we study the cases in which $X$ is the affine variety of Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric or companion matrices. We calculate the dimension of the $X$-factorization varieties for all these cases, and discuss how numerical algebraic geometry can be used to obtain computational evidence for the degrees of $X$-factorization varieties with an example. In addition, we propose methods for deriving lower and upper bounds for (border) structured matrix factorization length. For lower bounds, we develop a method based on displacement rank, which can also be used to obtain some defining equations of the $r$-th $X$-factorization variety; for upper bounds, we suggest an approach using alternating minimization.

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.

Referee Report

2 major / 3 minor

Summary. The paper generalizes the structured factorization problem from Toeplitz matrices to arbitrary affine varieties X ⊆ ℂ^{n imes n} of structured matrices. It defines the r-th X-factorization variety as the Zariski closure of the image of the multiplication map X^r o M_n(ℂ) and uses its dimension to study the (border) structured matrix factorization length. Explicit dimension formulas are computed for X equal to the varieties of Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric, and companion matrices; lower bounds are derived via displacement rank (which also yields some equations for the factorization varieties); upper bounds are obtained by alternating minimization; and numerical algebraic geometry is illustrated for computing degrees in one example.

Significance. If the dimension calculations are correct, the work supplies a uniform algebraic-geometric language for factorization-length questions across linear matrix structures, extending the known 2n+5 / ⌊n/2⌋+1 Toeplitz result. The displacement-rank technique for both bounds and equations, together with the explicit suggestion of alternating minimization for upper bounds and the numerical-algebraic-geometry example, are concrete methodological contributions that can be reused for other varieties.

major comments (2)
  1. [§3.3] §3.3 (companion-matrix case): the claimed dimension of the r-th factorization variety appears to rely on a generic-rank calculation for the multiplication map that is not cross-checked against the explicit parametrization of companion matrices given in §2.2; a single explicit low-n example (n=3, r=2) would confirm whether the formula holds or whether the variety is properly contained in the expected component.
  2. [§4.1] §4.1, displacement-rank lower bound: while the method correctly produces equations when the displacement operator has full rank, the paper does not verify that the resulting ideal is radical or that its variety coincides with the Zariski closure for the Hankel and skew-symmetric cases; this affects the claimed “defining equations” statement.
minor comments (3)
  1. [Introduction] The introduction states the Toeplitz result as motivation but does not cite the precise reference for the 2n+5 bound; adding the citation would clarify the starting point.
  2. [§3] Notation: the symbol X_r is used both for the r-th factorization variety and, in one paragraph of §3, for the set of products before closure; a single consistent definition would remove ambiguity.
  3. [Figure 1] Figure 1 (numerical degree computation) lacks axis labels and a caption explaining the sample size; this makes the computational evidence harder to interpret.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation, the recommendation of minor revision, and the constructive comments. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [§3.3] §3.3 (companion-matrix case): the claimed dimension of the r-th factorization variety appears to rely on a generic-rank calculation for the multiplication map that is not cross-checked against the explicit parametrization of companion matrices given in §2.2; a single explicit low-n example (n=3, r=2) would confirm whether the formula holds or whether the variety is properly contained in the expected component.

    Authors: The dimension formula in §3.3 is obtained by evaluating the rank of the differential of the multiplication map at a generic point of the parameter space of companion matrices (using the explicit parametrization of §2.2 to describe that space). While the generic-rank computation is independent of a specific low-dimensional check, we agree that an explicit verification strengthens the claim. We will add the suggested computation for n=3, r=2 to the revised manuscript; this example confirms that the image is dense in the expected component and the dimension formula holds. revision: yes

  2. Referee: [§4.1] §4.1, displacement-rank lower bound: while the method correctly produces equations when the displacement operator has full rank, the paper does not verify that the resulting ideal is radical or that its variety coincides with the Zariski closure for the Hankel and skew-symmetric cases; this affects the claimed “defining equations” statement.

    Authors: The manuscript states only that the displacement-rank construction 'can also be used to obtain some defining equations' of the r-th X-factorization variety; it does not assert that these equations generate the full ideal, that the ideal is radical, or that the variety equals the zero set of these equations. The equations are nevertheless valid because every point of the image (hence of its closure) satisfies them. We will add a clarifying sentence noting that the equations provide a valid but possibly incomplete set and that radicality questions are left for future work. The dimension results and lower-bound applications remain unaffected. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core construction defines the r-th X-factorization variety as the Zariski closure of the image of the multiplication map X^r → M_n(C) for an affine variety X of structured matrices; this is the standard geometric definition of border rank for structured factorizations and introduces no self-referential reduction. Dimension computations for Toeplitz, Hankel, bidiagonal, tridiagonal, skew-symmetric, and companion cases proceed from this definition via standard algebraic geometry techniques. The cited 2n+5 Toeplitz factorization length serves only as external motivation, not as an input that is redefined or fitted within the present derivations. Lower bounds via displacement rank and upper bounds via alternating minimization are developed as independent methods without renaming fitted quantities as predictions or relying on load-bearing self-citations. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard algebraic-geometry premise that structured matrix sets are affine varieties whose product sets admit well-defined Zariski closures; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption The set of matrices with a given structure is an affine variety X ⊆ C^{n×n}
    Invoked at the start of the generalization step in the abstract.
  • standard math Zariski closure of the product set of r matrices from X is a well-defined algebraic variety whose dimension is computable
    Used to define the r-th X-factorization variety.

pith-pipeline@v0.9.1-grok · 5823 in / 1527 out tokens · 18463 ms · 2026-06-27T20:57:00.927099+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 16 canonical work pages

  1. [1]

    E. H. Bareiss. Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices. Numer. Math., 13:404–424, 1969. ISSN 0029-599X,0945-3245. doi: 10.1007/BF02163269. URL https://doi.org/10.1007/BF02163269

    work page doi:10.1007/bf02163269 1969

  2. [2]

    A. W. Boja´ nczyk, R. P. Brent, F. R. de Hoog, and D. R. Sweet. On the stability of the Bareiss and related Toeplitz factorization algorithms.SIAM J. Matrix Anal. Appl., 16(1):40–57, 1995. ISSN 0895-

    1995

  3. [3]

    URLhttps://doi.org/10.1137/S0895479891221563

    doi: 10.1137/S0895479891221563. URLhttps://doi.org/10.1137/S0895479891221563

    work page doi:10.1137/s0895479891221563

  4. [4]

    1991 , PAGES =

    A. Borel.Linear algebraic groups, volume 126 ofGraduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. ISBN 0-387-97370-2. doi: 10.1007/978-1-4612-0941-6. URL https://doi.org/10.1007/978-1-4612-0941-6

    work page doi:10.1007/978-1-4612-0941-6 1991

  5. [5]

    A. J. Bosch. The factorization of a square matrix into two symmetric matrices.Amer. Math. Monthly, 93(6):462–464, 1986. ISSN 0002-9890,1930-0972. doi: 10.2307/2323471. URL https: //doi.org/10.2307/2323471

    work page doi:10.2307/2323471 1986

  6. [6]

    D. A. Cox, J. Little, and D. O’Shea.Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fifth edition, 2025. ISBN 978-3-031-91840-7; 978-3-031-91841-4. doi: 10.1007/978-3-031-91841-4. URLhttps://doi.org/10.1007/978-3-031-91841-4

    work page doi:10.1007/978-3-031-91841-4 2025

  7. [7]

    Draisma, E

    J. Draisma, E. Horobe¸t, G. Ottaviani, B. Sturmfels, and R. R. Thomas. The Euclidean distance degree of an algebraic variety.Found. Comput. Math., 16(1):99–149, 2016. ISSN 1615-3375,1615-3383. doi: 10.1007/s10208-014-9240-x. URLhttps://doi.org/10.1007/s10208-014-9240-x

    work page doi:10.1007/s10208-014-9240-x 2016

  8. [8]

    Garc´ ıa-Marco, I

    I. Garc´ ıa-Marco, I. M´ arquez-Corbella, and D. Seco. On the minimum number of toeplitz factors of a matrix.arXiv preprint arXiv:2506.16432, 2025

    arXiv 2025

  9. [9]

    G. H. Golub and C. F. Van Loan.Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013. ISBN 978-1-4214- 0794-4; 1-4214-0794-9; 978-1-4214-0859-0

    2013

  10. [10]

    Hartshorne.Algebraic geometry, volume No

    R. Hartshorne.Algebraic geometry, volume No. 52 ofGraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1977. ISBN 0-387-90244-9

    1977

  11. [11]

    Kailath, S

    T. Kailath, S. Y. Kung, and M. Morf. Displacement ranks of matrices and linear equations.J. Math. Anal. Appl., 68(2):395–407, 1979. ISSN 0022-247X. doi: 10.1016/0022-247X(79)90124-0. URL https://doi.org/10.1016/0022-247X(79)90124-0

    work page doi:10.1016/0022-247x(79)90124-0 1979

  12. [12]

    T. G. Kolda and B. W. Bader. Tensor decompositions and applications.SIAM Rev., 51(3):455–500,

  13. [13]

    URL https:// papers.nips.cc/paper/2017/hash/6449f 44a102fde848669bdd9eb6b76fa-Abstract

    ISSN 1095-7200,0036-1445. doi: 10.1137/07070111X. URL https://doi.org/10.1137/ 07070111X

    work page doi:10.1137/07070111x

  14. [14]

    J. M. Landsberg.Tensors: geometry and applications, volume 128 ofGraduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012. ISBN 978-0-8218-6907-9. doi: 10.1090/gsm/

    work page doi:10.1090/gsm/ 2012

  15. [15]

    STRUCTURED MATRIX FACTORIZATION LENGTH 33

    URLhttps://doi.org/10.1090/gsm/128. STRUCTURED MATRIX FACTORIZATION LENGTH 33

    work page doi:10.1090/gsm/128

  16. [16]

    J. M. Landsberg.Geometry and complexity theory, volume 169 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2017. ISBN 978-1-107-19923-1. doi: 10.1017/ 9781108183192. URLhttps://doi.org/10.1017/9781108183192

    work page doi:10.1017/9781108183192 2017

  17. [17]

    A. Leykin. Numerical algebraic geometry.J. Softw. Algebra Geom., 3:5–10, 2011. ISSN 1948-7916. doi: 10.2140/jsag.2011.3.5. URLhttps://doi.org/10.2140/jsag.2011.3.5

    work page doi:10.2140/jsag.2011.3.5 2011

  18. [18]

    V. Y. Pan.Structured matrices and polynomials. Birkh¨ auser Boston, Inc., Boston, MA; Springer- Verlag, New York, 2001. ISBN 0-8176-4240-4. doi: 10.1007/978-1-4612-0129-8. URL https: //doi.org/10.1007/978-1-4612-0129-8. Unified superfast algorithms

    work page doi:10.1007/978-1-4612-0129-8 2001

  19. [19]

    I. R. Shafarevich.Basic algebraic geometry. 1. Springer, Heidelberg, third edition, 2013. ISBN 978-3-642-37955-0; 978-3-642-37956-7. Varieties in projective space

    2013

  20. [20]

    T. A. Springer.Linear algebraic groups, volume 9 ofProgress in Mathematics. Birkh¨ auser Boston, Inc., Boston, MA, second edition, 1998. ISBN 0-8176-4021-5. doi: 10.1007/978-0-8176-4840-4. URL https://doi.org/10.1007/978-0-8176-4840-4

    work page doi:10.1007/978-0-8176-4840-4 1998

  21. [21]

    K. Ye. New classes of matrix decompositions.Linear Algebra Appl., 514:47–81, 2017. ISSN 0024- 3795,1873-1856. doi: 10.1016/j.laa.2016.10.024. URL https://doi.org/10.1016/j.laa.2016.10. 024

    work page doi:10.1016/j.laa.2016.10.024 2017

  22. [22]

    Ye and L.-H

    K. Ye and L.-H. Lim. Every matrix is a product of Toeplitz matrices.Found. Comput. Math., 16(3):577–598, 2016. ISSN 1615-3375,1615-3383. doi: 10.1007/s10208-015-9254-z. URL https: //doi.org/10.1007/s10208-015-9254-z. (Jeong-Hoon Ju) Department of Mathematical Sciences, University of Copenhagen, 5 Universitetsparken, 2100 Copenhagen Ø, Denmark Email addres...

    work page doi:10.1007/s10208-015-9254-z 2016