Algorithms for triangular decomposition of block Hankel and Toeplitz matrices with application to factoring positive matrix polynomials (1973)

Algorithms are given for calculating the block triangular factors <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A comma ModifyingAbove upper A With caret comma upper B equals upper A Superscript negative 1"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">^</mml:mo> </mml:mover> </mml:mrow> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>A</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">A,\hat A,B = {A^{ - 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="ModifyingAbove upper B With caret equals ModifyingAbove upper A With caret Superscript negative 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>B</mml:mi> <mml:mo stretchy="false">^</mml:mo> </mml:mover> </mml:mrow> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">^</mml:mo> </mml:mover> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\hat B = {\hat A^{ - 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and the block diagonal factor <italic>D</italic> in the factorizations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R equals upper A upper D ModifyingAbove upper A With caret"> <mml:semantics> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>=</mml:mo> <mml:mi>A</mml:mi> <mml:mi>D</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">^</mml:mo> </mml:mover> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">R = AD\hat A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B upper R ModifyingAbove upper B With caret equals upper D"> <mml:semantics> <mml:mrow> <mml:mi>B</mml:mi> <mml:mi>R</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>B</mml:mi> <mml:mo stretchy="false">^</mml:mo> </mml:mover> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>D</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">BR\hat B = D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of block Hankel and Toeplitz matrices <italic>R</italic>. The algorithms require <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis p cubed n squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>p</mml:mi> <mml:mn>3</mml:mn> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O({p^3}{n^2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> operations when <italic>R</italic> is an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-matrix of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p times p"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>×</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p \times p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-blocks. As an application, an iterative method is described for factoring <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p times p"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>×</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p \times p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-matrix valued positive polynomials <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R equals sigma-summation Underscript i equals negative m Overscript m Endscripts upper R Subscript i Baseline x Superscript i Baseline comma upper R Subscript negative i Baseline equals upper R prime Subscript i"> <mml:semantics> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>=</mml:mo> <mml:msubsup> <mml:mo movablelimits="false">∑</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mo>−</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>R</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>x</mml:mi> <mml:mi>i</mml:mi> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>R</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−</mml:mo> <mml:mi>i</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msubsup> <mml:mi>R</mml:mi> <mml:mi>i</mml:mi> <mml:mo>′</mml:mo> </mml:msubsup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">R = \sum \nolimits _{i = - m}^m {R_i}{x^i},{R_{ - i}} = {R’_i}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, as <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="ModifyingAbove upper A With bar left-parenthesis x right-parenthesis ModifyingAbove upper A With bar prime left-parenthesis x Superscript negative 1 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">¯</mml:mo> </mml:mover> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">¯</mml:mo> </mml:mover> </mml:mrow> <mml:mo>′</mml:mo> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\bar A(x)\bar A’({x^{ - 1}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="ModifyingAbove upper A With bar left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>A</mml:mi> <mml:mo stretchy="false">¯</mml:mo> </mml:mover> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\bar A(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is outer.