Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in: Foundations of Computational Mathematics 3/2016

01.06.2016

Every Matrix is a Product of Toeplitz Matrices

verfasst von: Ke Ye, Lek-Heng Lim

Erschienen in: Foundations of Computational Mathematics | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We show that every \(n\,\times \,n\) matrix is generically a product of \(\lfloor n/2 \rfloor + 1\) Toeplitz matrices and always a product of at most \(2n+5\) Toeplitz matrices. The same result holds true if the word ‘Toeplitz’ is replaced by ‘Hankel,’ and the generic bound \(\lfloor n/2 \rfloor + 1\) is sharp. We will see that these decompositions into Toeplitz or Hankel factors are unusual: We may not, in general, replace the subspace of Toeplitz or Hankel matrices by an arbitrary \((2n-1)\)-dimensional subspace of \({n\,\times \,n}\) matrices. Furthermore, such decompositions do not exist if we require the factors to be symmetric Toeplitz or persymmetric Hankel, even if we allow an infinite number of factors.
Nächster Artikel Complexity of Linear Circuits and Geometry

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
We restrict our attention to decompositions that exist for arbitrary matrices over both \(\mathbb {R}\) and \(\mathbb {C}\). Of the six decompositions described in [47], we discounted the Cholesky (only for positive definite matrices), Schur (only over \(\mathbb {C}\)), and spectral decompositions (only for normal matrices).
 
Literatur
1.
“Algorithms for the ages,” Science, 287 (2000), no. 5454, p. 799.
2.
G. S. Ammar and W. B. Gragg, “Superfast solution of real positive definite Toeplitz systems,” SIAM J. Matrix Anal. Appl., 9 (1988), no. 1, pp. 61–76.MathSciNetCrossRefMATH
3.
Y. Barnea and A. Shalev, “Hausdorff dimension, pro-\(p\) groups, and Kac–Moody algebras,” Trans. Amer. Math. Soc., 349 (1997), no. 12, pp. 5073–5091.MathSciNetCrossRefMATH
4.
D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools, 25, SIAM, Philadelphia, PA, 2013.MATH
5.
H. Bart, I. Gohberg, and M. A. Kaashoek, “Wiener-Hopf integral equations, Toeplitz matrices and linear systems,” pp. 85–135, Operator Theory: Adv. Appl., 4, Birkhäuser, Boston, MA, 1982.
6.
J. Bernik, R. Drnovšek, D. Kokol Bukovšek, T. Košir, M. Omladič, and H. Radjavi, “On semitransitive Jordan algebras of matrices,” J. Algebra Appl., 10 (2011), no. 2, pp. 319–333.
7.
D. Bini and B. Meini, “Solving certain queueing problems modelled by Toeplitz matrices,” Calcolo, 30 (1993), no. 4, pp. 395–420.MathSciNetCrossRefMATH
8.
R. B. Bitmead and B. D. O. Anderson, “Asymptotically fast solution of Toeplitz and related systems of linear equations,” Linear Algebra Appl., 34 (1980), pp. 103–116.MathSciNetCrossRefMATH
9.
M. Bordemann, E. Meinrenken, and M. Schlichenmaier, “Toeplitz quantization of Kähler manifolds and \({\mathfrak{gl}}(N)\), \(N\rightarrow \infty \) limits,” Comm. Math. Phys., 165 (1994), no. 2, pp. 281–296.MathSciNetCrossRefMATH
10.
A. Borel, Linear Algebraic Groups, 2nd Ed., Graduate Texts in Mathematics, 126, Springer-Verlag, New York, NY, 1991.
11.
A. Borodin and A. Okounkov, “A Fredholm determinant formula for Toeplitz determinants,” Integral Equations Operator Theory, 37 (2000), no. 4, pp. 386–396.MathSciNetCrossRefMATH
12.
D. Burns and V. Guillemin, “The Tian–Yau–Zelditch theorem and Toeplitz operators,” J. Inst. Math. Jussieu, 10 (2011), no. 3, pp. 449–461.MathSciNetCrossRefMATH
13.
R. H. Chan and X.-Q. Jin, An Introduction to Iterative Toeplitz Solvers, Fundamentals of Algorithms, 5, SIAM, Philadelphia, PA, 2007.CrossRef
14.
15.
R. H. Chan and G. Strang, “Toeplitz equations by conjugate gradients with circulant preconditioner,” SIAM J. Sci. Statist. Comput., 10 (1989), no. 1, pp. 104–119.MathSciNetCrossRefMATH
16.
T. F. Chan, “An optimal circulant preconditioner for Toeplitz systems,” SIAM J. Sci. Statist. Comput., 9 (1988), no. 4, pp. 766–771.MathSciNetCrossRefMATH
17.
S. Chandrasekaran, M. Gu, X. Sun, J. Xia, and J. Zhu, “A superfast algorithm for Toeplitz systems of linear equations,” SIAM J. Matrix Anal. Appl., 29 (2007), no. 4, pp. 1247–1266.MathSciNetCrossRefMATH
18.
W. W. Chen, C. M. Hurvich, and Y. Lu, “On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series,” J. Amer. Statist. Assoc., 101 (2006), no. 474, pp. 812–822.MathSciNetCrossRefMATH
19.
W. K. Cochran, R. J. Plemmons, and T. C. Torgersen, “Exploiting Toeplitz structure in atmospheric image restoration,” pp. 177–189, Structured Matrices in Mathematics, Computer Science, and Engineering I, Contemp. Math., 280, AMS, Providence, RI, 2001.
20.
F. de Hoog, “A new algorithm for solving Toeplitz systems of equations,” Linear Algebra Appl., 88/89 (1987), pp. 123–138.MathSciNetCrossRefMATH
21.
P. Deift, A. Its, and I. Krasovsky, “Asymptotics of Toeplitz, Hankel, and Toeplitz+Hankel determinants with Fisher–Hartwig singularities,” Ann. Math., 174 (2011), no. 2, pp. 1243–1299.MathSciNetCrossRefMATH
22.
A. Dembo, C. L. Mallows, and L. A. Shepp, “Embedding nonnegative definite Toeplitz matrices in nonnegative definite circulant matrices, with application to covariance estimation,” IEEE Trans. Inform. Theory, 35 (1989), no. 6, pp. 1206–1212.MathSciNetCrossRefMATH
23.
R. G. Douglas and R. Howe, “On the \(C^*\)-algebra of Toeplitz operators on the quarterplane,” Trans. Amer. Math. Soc., 158 (1971), pp. 203–217.MathSciNetMATH
24.
E. Eisenberg, A. Baram, and M. Baer, “Calculation of the density of states using discrete variable representation and Toeplitz matrices,” J. Phys. A, 28 (1995), no. 16, pp. L433–L438.MathSciNetCrossRefMATH
25.
26.
27.
P. Favati, G. Lotti, and O. Menchi, “A divide and conquer algorithm for the superfast solution of Toeplitz-like systems,” SIAM J. Matrix Anal. Appl., 33 (2012), no. 4, pp. 1039–1056.MathSciNetCrossRefMATH
28.
M. Geck, An Introduction to Algebraic Geometry and Algebraic Groups, Oxford Graduate Texts in Mathematics, 10, Oxford University Press, Oxford, 2003.
29.
V. Gorin, “The \(q\)-Gelfand-Tsetlin graph, Gibbs measures and \(q\)-Toeplitz matrices,” Adv. Math., 229 (2012), no. 1, pp. 201–266.MathSciNetCrossRefMATH
30.
31.
U. Grenander and G. Szegö, Toeplitz Forms and Their Applications, 2nd Ed., Chelsea Publishing, New York, NY, 1984.MATH
32.
J. Haupt, W. U. Bajwa, G. Raz, and R. Nowak, “Toeplitz compressed sensing matrices with applications to sparse channel estimation,” IEEE Trans. Inform. Theory, 56 (2010), no. 11, pp. 5862–5875.MathSciNetCrossRef
33.
34.
J.-J. Hsue and A. E. Yagle, “Fast algorithms for solving Toeplitz systems of equations using number-theoretic transforms,” Signal Process., 44 (1995), no. 1, pp. 89–101.CrossRefMATH
35.
M. Kac, “Some combinatorial aspects of the theory of Toeplitz matrices,” pp. 199–208, Proc. IBM Sci. Comput. Sympos. Combinatorial Problems, IBM Data Process. Division, White Plains, NY, 1964.
36.
H. Khalil, B. Mourrain, and M. Schatzman, “Superfast solution of Toeplitz systems based on syzygy reduction,” Linear Algebra Appl., 438 (2013), no. 9, pp. 3563–3575.MathSciNetCrossRefMATH
37.
A. W. Knapp, Lie Groups Beyond an Introduction, 2nd Ed., Progress in Mathematics, 140, Birkhäuser, Boston, MA, 2002.
38.
J. M. Landsberg, Tensors: Geometry and Applications, AMS, Providence, RI, 2012.MATH
39.
F.-R. Lin, M. K. Ng, and R. H. Chan, “Preconditioners for Wiener-Hopf equations with high-order quadrature rules,” SIAM J. Numer. Anal., 34 (1997), no. 4, pp. 1418–1431.MathSciNetCrossRefMATH
40.
41.
N. Makarov and A. Poltoratski, “Beurling–Malliavin theory for Toeplitz kernels,” Invent. Math., 180 (2010), no. 3, pp. 443–480.MathSciNetCrossRefMATH
42.
43.
M. K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, New York, NY, 2004.MATH
44.
H. Özbay and A. Tannenbaum, “A skew Toeplitz approach to the \(H^\infty \) optimal control of multivariable distributed systems,” SIAM J. Control Optim., 28 (1990), no. 3, pp. 653–670.MathSciNetCrossRefMATH
45.
D. Poland, “Toeplitz matrices and random walks with memory,” Phys. A, 223 (1996), no. 1–2, pp. 113–124.MathSciNetCrossRef
46.
K. Rietsch, “Totally positive Toeplitz matrices and quantum cohomology of partial flag varieties,” J. Amer. Math. Soc., 16 (2003), no. 2, pp. 363–392.MathSciNetCrossRefMATH
47.
G. W. Stewart, “The decompositional approach to matrix computation,” Comput. Sci. Eng., 2 (2000), no. 1, pp. 50–59.CrossRef
48.
M. Stewart, “A superfast Toeplitz solver with improved numerical stability,” SIAM J. Matrix Anal. Appl., 25 (2003), no. 3, pp. 669–693.MathSciNetCrossRefMATH
49.
J. L. Taylor, Several Complex Variables with Connections to Algebraic Geometry and Lie groups, Graduate Studies in Mathematics, 46, AMS, Providence, RI, 2002.
50.
J. Toft, “The Bargmann transform on modulation and Gelfand–Shilov spaces, with applications to Toeplitz and pseudo-differential operators,” J. Pseudo-Differ. Oper. Appl., 3 (2012), no. 2, pp. 145–227.MathSciNetCrossRefMATH
51.
E. E. Tyrtyshnikov, “Fast computation of Toeplitz forms and some multidimensional integrals,” Russian J. Numer. Anal. Math. Modelling, 20 (2005), no. 4, pp. 383–390.MathSciNetCrossRefMATH
52.
S. Serra, “The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems,” Numer. Math., 81 (1999), no. 3, pp. 461–495.MathSciNetCrossRefMATH
53.
U. Steimel, “Fast computation of Toeplitz forms under narrowband conditions with applications to statistical signal processing,” Signal Process., 1 (1979), no. 2, pp. 141–158.MathSciNetCrossRefMATH
54.
G. Strang, “The discrete cosine transform, block Toeplitz matrices, and wavelets,” pp. 517–536, Advances in Computational Mathematics, Lecture Notes in Pure and Applied Mathematics, 202, Dekker, New York, NY, 1999.
55.
G. Strang, “A proposal for Toeplitz matrix calculations,” Stud. Appl. Math., 74 (1986), no. 2, pp. 171–176.CrossRefMATH
56.
M. Van Barel, G. Heinig, and P. Kravanja, “A stabilized superfast solver for nonsymmetric Toeplitz systems,” SIAM J. Matrix Anal. Appl., 23 (2001), no. 2, pp. 494–510.MathSciNetCrossRefMATH
57.
K. Ye and L.-H. Lim, “New classes of matrix decompositions,” preprint, (2015).
Metadaten
Titel
Every Matrix is a Product of Toeplitz Matrices
verfasst von
Ke Ye
Lek-Heng Lim
Publikationsdatum
01.06.2016
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 3/2016
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-015-9254-z

Weitere Artikel der Ausgabe 3/2016

Foundations of Computational Mathematics 3/2016 Zur Ausgabe

OriginalPaper

Numerical Stability in the Presence of Variable Coefficients

OriginalPaper

Approximating Gradients with Continuous Piecewise Polynomial Functions

OriginalPaper

On the Nuclear Norm and the Singular Value Decomposition of Tensors

OriginalPaper

Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case

OriginalPaper

Plane Wave Discontinuous Galerkin Methods: Exponential Convergence of the -Version

OriginalPaper

Complexity of Linear Circuits and Geometry

Premium Partner

    Bildnachweise