Operator Theory Advances and Applications 234 Yuli Eidelman Israel Gohberg Iulian Haimovici Separable Type Representations of Matrices and Fast Algorithms Volume 1 Basics. Completion Problems. Multiplication and Inversion Algorithms Operator Theory: Advances and Applications Volume 234 Founded in 1979 by Israel Gohberg Editors: Joseph A. Ball (Blacksburg, VA, USA) Harry Dym (Rehovot, Israel) Marinus A. Kaashoek (Amsterdam, The Netherlands) Heinz Langer (Vienna, Austria) Christiane Tretter (Bern, Switzerland) Associate Editors: Honorary and Advisory Editorial Board: Vadim Adamyan (Odessa, Ukraine) Lewis A. Coburn (Buffalo, NY, USA) Albrecht Böttcher (Chemnitz, Germany) Ciprian Foias (College Station, TX, USA) B. Malcolm Brown (Cardiff, UK) J.William Helton (San Diego, CA, USA) Raul Curto (Iowa, IA, USA) Thomas Kailath (Stanford, CA, USA) Fritz Gesztesy (Columbia, MO, USA) Peter Lancaster (Calgary, Canada) Pavel Kurasov (Stockholm, Sweden) Peter D. Lax (New York, NY, USA) Leonid E. Lerer (Haifa, Israel) Donald Sarason (Berkeley, CA, USA) Vern Paulsen (Houston, TX, USA) Bernd Silbermann (Chemnitz, Germany) Mihai Putinar (Santa Barbara, CA, USA) Harold Widom (Santa Cruz, CA, USA) Leiba Rodman (Williamsburg, VA, USA) Ilya M. Spitkovsky (Williamsburg, VA, USA) Subseries Linear Operators and Linear Systems Subseries editors: Daniel Alpay (Beer Sheva, Israel) Birgit Jacob (Wuppertal, Germany) André C.M. Ran (Amsterdam, The Netherlands) Subseries Advances in Partial Differential Equations Subseries editors: Bert-Wolfgang Schulze (Potsdam, Germany) Michael Demuth (Clausthal, Germany) Jerome A. Goldstein (Memphis, TN, USA) Nobuyuki Tose (Yokohama, Japan) Ingo Witt (Göttingen, Germany) Yuli Eidelman Israel Gohberg Iulian Haimovici Separable Type Representations of Matrices and Fast Algorithms Volume 1 Basics. Completion Problems. Multiplication and Inversion Algorithms Yuli Eidelman Israel Gohberg Iulian Haimovici School of Mathematical Sciences Raymond and Beverly Sackler Facultyof ExactSciences Tel Aviv University Tel Aviv Israel ISSN 0255-0156 ISSN 2296-4878 (electronic) ISBN 978-3-0348-0605-3 ISBN 978-3-0348-0606-0 (eBook) DOI 10.1007/978-3-0348-0606-0 Springer Basel Heidelberg New York Dordrecht London Library of Congress Control Number: 2013951156 Mathematics Subject Classification (2010): 15A06, 15A09, 15A23, 15A83, 65F05 © Springer Basel 201 4 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer Basel is part of Springer Science+Business Media (www.birkhauser-science.com) Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Part I Basics on Separable, Semi-separable and Quasiseparable Representations of Matrices 1 Matrices with Separable Representation and Low Complexity Algorithms §1.1 Rank and related factorizations . . . . . . . . . . . . . . . . . . . 4 §1.2 Definitions and first examples . . . . . . . . . . . . . . . . . . . . 6 §1.3 The algorithm of multiplication by a vector . . . . . . . . . . . . . 8 §1.3.1 Forward and backward computation of 𝑦 . . . . . . . . . . 8 §1.3.2 Forward-backwardcomputation of 𝑦 . . . . . . . . . . . . . 10 §1.4 Systems with homogeneous boundary conditions associated with matrices in diagonal plus separable form. . . . . . . . . . . . 12 §1.4.1 Forward and backward systems . . . . . . . . . . . . . . . 12 §1.4.2 Forward-backwarddescriptor systems . . . . . . . . . . . . 15 §1.5 Multiplication of matrices . . . . . . . . . . . . . . . . . . . . . . . 16 §1.5.1 Product of matrices with separable representations . . . . 16 §1.5.2 Product of matrices with diagonal plus separable representations . . . . . . . . . . . . . . . . . . . . . . . . 18 §1.6 Schur factorization and inversion of block matrices . . . . . . . . . 21 §1.7 A general inversion formula . . . . . . . . . . . . . . . . . . . . . . 25 §1.8 Inversion of matrices with diagonal plus separable representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 §1.9 LDU factorization of matrices with diagonal plus separable representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 §1.10 Solutionoflinearsystemsinthepresenceofthe𝐿𝐷𝑈 factorization of the matrix of the system in diagonal plus separable form . . . . 39 §1.11 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 v vi Contents 2 The Minimal Rank Completion Problem §2.1 The definition. The case of a 2×2 block matrix . . . . . . . . . . 45 §2.2 Solution of the general minimal rank completion problem. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 §2.3 Uniqueness of the minimal rank completion . . . . . . . . . . . . . 61 §2.4 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3 Matrices in Diagonal Plus Semiseparable Form §3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 §3.2 Semiseparable order and minimal semiseparable generators . . . . 69 §3.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 Quasiseparable Representations: The Basics §4.1 The rank numbers and quasiseparable order. Examples . . . . . . 75 §4.1.1 The definitions. . . . . . . . . . . . . . . . . . . . . . . . . 75 §4.1.2 The companion matrix . . . . . . . . . . . . . . . . . . . . 76 §4.1.3 The block companion matrix . . . . . . . . . . . . . . . . . 76 §4.1.4 Tridiagonal matrices and band matrices . . . . . . . . . . . 77 §4.1.5 Matrices with diagonal plus semiseparable representations . . . . . . . . . . . . . . . . . . . . . . . . 78 §4.2 Quasiseparable generators. . . . . . . . . . . . . . . . . . . . . . . 79 §4.3 Minimal completion rank, rank numbers, and quasiseparable order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 §4.4 The quasiseparable and semiseparable generators. . . . . . . . . . 83 §4.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5 Quasiseparable Generators §5.1 Auxiliary matrices and relations . . . . . . . . . . . . . . . . . . . 86 §5.2 Existence and minimality of quasiseparable generators . . . . . . . 89 §5.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 §5.4 Quasiseparable generators of block companion matrices viewed as scalar matrices . . . . . . . . . . . . . . . . . . . . . . . 99 §5.5 Minimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . 102 §5.6 Sets of generators. Minimality and similarity . . . . . . . . . . . . 105 §5.7 Reduction to minimal quasiseparable generators . . . . . . . . . . 110 §5.8 Normal quasiseparable generators . . . . . . . . . . . . . . . . . . 112 §5.9 Approximation by matrices with quasiseparable representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 §5.10 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Contents vii 6 Rank Numbers of Pairs of Mutually Inverse Matrices, Asplund Theorems §6.1 Rank numbers of pairs of inverse matrices. . . . . . . . . . . . . . 120 §6.2 Rank numbers relative to the main diagonal. Quasiseparable orders . . . . . . . . . . . . . . . . . . . . . . . . . 122 §6.3 Green and band matrices . . . . . . . . . . . . . . . . . . . . . . . 123 §6.4 The inverses of diagonal plus Green of order one matrices . . . . . 126 §6.5 Minimal completion ranks of pairs of mutually inverse matrices. The inverse of an irreducible band matrix . . . . . . . . 129 §6.6 Linear-fractional transformations of matrices . . . . . . . . . . . . 134 §6.6.1 The definition and the basic property . . . . . . . . . . . . 134 §6.6.2 Linear-fractional transformations of Green and band matrices . . . . . . . . . . . . . . . . . . . . . . . . . 135 §6.6.3 Unitary Hessenberg and Hermitian matrices . . . . . . . . 135 §6.6.4 Linear-fractional transformations of diagonal plus Green of order one matrices . . . . . . . . . . . . . . . . . 136 §6.7 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7 Unitary Matrices with Quasiseparable Representations §7.1 QR and related factorizations of matrices . . . . . . . . . . . . . . 139 §7.2 The rank numbers and quasiseparable generators. . . . . . . . . . 142 §7.3 Factorization representations . . . . . . . . . . . . . . . . . . . . . 143 §7.3.1 Block triangular matrices . . . . . . . . . . . . . . . . . . . 143 §7.3.2 Factorization of general unitary matrices and compression of generators . . . . . . . . . . . . . . . . . . 146 §7.3.3 Generators via factorization . . . . . . . . . . . . . . . . . 151 §7.4 Unitary Hessenberg matrices . . . . . . . . . . . . . . . . . . . . . 155 §7.5 Efficient generators . . . . . . . . . . . . . . . . . . . . . . . . . . 157 §7.6 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Part II Completion of Matrices with Specified Bands 8 Completion to Green Matrices §8.1 Auxiliary relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 §8.2 Completion formulas. . . . . . . . . . . . . . . . . . . . . . . . . . 167 §8.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 viii Contents 9 Completion to Matrices with Band Inverses and with Minimal Ranks §9.1 Completion to invertible matrices . . . . . . . . . . . . . . . . . . 180 §9.2 The LDU factorization . . . . . . . . . . . . . . . . . . . . . . . . 182 §9.3 The Permanence Principle . . . . . . . . . . . . . . . . . . . . . . 186 §9.4 The inversionformula . . . . . . . . . . . . . . . . . . . . . . . . . 191 §9.5 Completion to matrices of minimal ranks . . . . . . . . . . . . . . 197 §9.6 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 10 Completion of Special Types of Matrices §10.1 The positive case. . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 §10.2 The Toeplitz case . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 §10.3 Completion of specified tridiagonal parts with identities on the main diagonal . . . . . . . . . . . . . . . . . . . . . . . . . 208 §10.3.1The general case . . . . . . . . . . . . . . . . . . . . . . . . 208 §10.3.2The Toeplitz case . . . . . . . . . . . . . . . . . . . . . . . 210 §10.4 Completion of special 2×2 block matrices . . . . . . . . . . . . . 211 §10.4.1Completion formulas . . . . . . . . . . . . . . . . . . . . . 211 §10.4.2Completion to invertible and positive matrices . . . . . . . 214 §10.4.3Completion to matrices of minimal ranks . . . . . . . . . . 215 §10.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 11 Completion of Mutually Inverse Matrices §11.1 The statement and preliminaries . . . . . . . . . . . . . . . . . . . 219 §11.2 The basic theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 §11.3 The direct method . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 §11.4 The factorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 §11.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 12 Completion to Unitary Matrices §12.1 Auxiliary relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 §12.2 An existence and uniqueness theorem . . . . . . . . . . . . . . . . 230 §12.3 Unitary completion via quasiseparable representation . . . . . . . 237 §12.3.1Existence theorem . . . . . . . . . . . . . . . . . . . . . . . 237 §12.3.2Diagonal correction for scalar matrices . . . . . . . . . . . 242 §12.4 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Contents ix Part III Quasiseparable Representations of Matrices, Descriptor Systems with Boundary Conditions and First Applications 13 Quasiseparable Representations and Descriptor Systems with Boundary Conditions §13.1 The algorithm of multiplication by a vector . . . . . . . . . . . . . 247 §13.2 Descriptor systems with homogeneous boundary conditions . . . . 250 §13.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 §13.4 Inversion of triangular matrices. . . . . . . . . . . . . . . . . . . . 255 §13.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 14 The First InversionAlgorithms §14.1 Inversion of matrices in quasiseparable representation with invertible diagonal elements . . . . . . . . . . . . . . . . . . . . . . 261 §14.2 The extension method for matrices with quasiseparable/semi- separable representations . . . . . . . . . . . . . . . . . . . . . . . 271 §14.2.1The inversionformula . . . . . . . . . . . . . . . . . . . . . 272 §14.2.2The orthogonalizationprocedure . . . . . . . . . . . . . . . 275 §14.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 15 Inversion of Matrices in Diagonal Plus Semiseparable Form §15.1 The modified inversionformula . . . . . . . . . . . . . . . . . . . . 279 §15.2 Scalar matrices with diagonal plus semiseparable representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 §15.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 16 Quasiseparable/SemiseparableRepresentationsandOne-directionSystems §16.1 Systems with diagonal main coefficients and homogeneous boundary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 295 §16.2 The general one-direction systems . . . . . . . . . . . . . . . . . . 301 §16.3 Inversion of matrices with quasiseparable/semiseparable representations via one-direction systems . . . . . . . . . . . . . . 305 §16.4 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 17 Multiplication of Matrices §17.1 The rank numbers of the product . . . . . . . . . . . . . . . . . . 309 §17.2 Multiplication of triangular matrices . . . . . . . . . . . . . . . . . 310 §17.3 The general case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 §17.4 Multiplication by triangular matrices . . . . . . . . . . . . . . . . 319 §17.5 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 322