Generalized Gohberg-Semencul Formulas for Matrix Inversion

  • Thomas Kailath
  • Joohwan Chun
Part of the Operator Theory: Advances and Applications book series (OT, volume 40)


We give a constructive and elementary proof of the Gohberg-Semencul formula for the inverse of a Toeplitz matrix. Our approach suggests a natural generalization of the formula to matrices with displacement structure.


Toeplitz Matrix Full Column Rank Toeplitz Matrice Block Matrice Toeplitz System 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    A. Ben-Artzi and T. Shalom, On inversion of Toeplitz and close to Toeplitz matrices, Linear Algebra and its Appl., 75 (1986), pp 173–192.CrossRefGoogle Scholar
  2. 2.
    R. Brent, F. Gustavson and D. Yun, Fast solution of Toeplitz systems of equations and computation of Fade approximants, Journal of Algorithms, 1, (1980), pp. 259–295.CrossRefGoogle Scholar
  3. 3.
    J. Chun and T. Kailath, Divide-and-conquer solutions for least-squares problems for matrices with displacement structure, Proc. Sixth Army conf. on Applied Math, and Comput., Boulder, CO, June, 1988.Google Scholar
  4. 4.
    J. Chun, T. Kailath and H. Lev-Ari, Fast parallel algorithms for QR and triangular factorization, SIAM J. Sci. Stat. Comput., vol. 8, No. 6, Nov., (1987), pp. 899–913.CrossRefGoogle Scholar
  5. 5.
    B. Friedlander, M. Morf, T. Kailath and L. Ljung, New inversion formula for matrices classified in terms of their distance from Toeplitz matrices, Linear Algebra and its Appl., 27 (1979), pp. 31–60.CrossRefGoogle Scholar
  6. 6.
    Ya. L. Geronimus, Polynomials orthogonal on a circle and interval, Pergamon press, New York, 1960.Google Scholar
  7. 7.
    I. Gohberg and I. Fel’dman, Convolution equations and projection methods for their solutions, Translations of Mathematical Monographs, vol. 41, Amer. Math. Soc., 1974.Google Scholar
  8. 8.
    I. Gohberg, T. Kailath and I. Koltracht, Efficient solution of linear systems of equations with recursive structure, Linear Algebra and its Appl., 80 (1986), pp 81–113.CrossRefGoogle Scholar
  9. 9.
    I. Gohberg, T. Kailath, I. Koltracht and P. Lancaster, Linear complexity parallel algorithms for linear systems of equations with recursive structure, Linear Algebra and its Appl., 88 (1987), pp 271–315.CrossRefGoogle Scholar
  10. 10.
    I. Gohberg and A. Semencul, On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 2 (1972), pp. 201–233.Google Scholar
  11. 11.
    U. Grenander and G. Szego Toeplitz forms and their applications 2nd ed., Chelsea publishing company, New York, 1984.Google Scholar
  12. 12.
    G. Heinig and K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Akademie-Verlag, Berlin, 1984.Google Scholar
  13. 13.
    T. Kailath, S. Kung and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68 (1979) pp. 395–407. See also Bull. Amer. Math. Soc., 1 (1979), pp. 769–773.CrossRefGoogle Scholar
  14. 14.
    T. Kailath, A. Vieira and M. Morf, Inverses of Toeplitz operators, innovations, and orthogonal polynomial, SIAM Review, vol. 20, No 1, Jan. (1978), pp. 106–119.CrossRefGoogle Scholar
  15. 15.
    L. Lerer and M. Tismenetsky, Generalized Bezoutian and matrix equations, Linear Algebra and its Appl., 99 (1988), pp 123–160.CrossRefGoogle Scholar
  16. 16.
    H. Lev-Ari, and T. Kailath, Lattice filter parameterization and modeling of nonstationary process, IEEE Trans. Inform. Theory, IT-30 (1984), pp. 2–16.CrossRefGoogle Scholar
  17. 17.
    M. Morf, Doubling algorithms for Toeplitz and related equations, in Proceedings of the IEEE International Conf. on Acoustics, Speech and Signal Processing, Denver, (1980), pp. 954–959.Google Scholar
  18. 18.
    I. Schur, Über Potenzreihen, die im Innern des Einheitskreises beschrankt sind, J. für die Reine und Angewandte Mathematik, 147 (1917), pp. 205–232.CrossRefGoogle Scholar
  19. 19.
    W. Trench, An algorithm for inversion of finite Toeplitz matrices, J. of SIAM, vol. 12.3 (1964), pp. 515–522.Google Scholar

Copyright information

© Birkhäuser Verlag Basel 1989

Authors and Affiliations

  • Thomas Kailath
    • 1
  • Joohwan Chun
    • 1
  1. 1.Information Systems Laboratory, Department of Electrical EngineeringStanford UniversityStanfordUSA

Personalised recommendations