annihilator/common left multiple of matrix polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T21:34:35Z http://mathoverflow.net/feeds/question/43022 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43022/annihilator-common-left-multiple-of-matrix-polynomials annihilator/common left multiple of matrix polynomials Federico Poloni 2010-10-21T07:49:45Z 2011-07-20T17:22:11Z <p>Let $A_{n,d}$ be the space of polynomials of degree $d$ or less whose coefficients are real $n\times n$ matrices --- or, if you prefer, the space of matrices whose entries are degree-$d$ polynomials. Given $A(z),B(z)\in A_{n,d}$, there are $P(z),Q(z)\in A_{n,d}$ so that $P(z)A(z)=Q(z)B(z)$ (proof: consider the $2dn\times (2d-1)n$ Sylvester resultant matrix of the polynomials; its left nullspace has dimension at least $n$ for dimension reasons, and one can build $P(z)$ and $Q(z)$ out of the entries of a $n\times 2nd$ matrix in this nullspace $[P_0\;P_1\;\dots\;P_d\;Q_0\;Q_1\;\dots\;Q_d]$).</p> <p>As Gerry Myerson noted in the comments, $P=Q=0$ is ok if we do not impose any additional constraint. The proof above shows how to compute two polynomial such that $[P_0\;P_1\;\dots\;P_d\;Q_0\;Q_1\;\dots\;Q_d]$ is full-rank. We could ask for that as a normalizing condition. In the generic case, the left kernel of the Sylvester matrix has rank $n$, so with this constraint $P$ and $Q$ are well-defined up to left multiplication by a nonsingular matrix.</p> <blockquote> <p>1) is there a simple and efficient way to compute $P(z)$ and $Q(z)$ by exploiting the structure of the matrix? </p> </blockquote> <p>Currently my best shot would be Fourier transforms+a fast Cauchy-like solver like the GKO algorithm, for a total cost of $O(n^3d^2)$ and a rather cumbersome algorithm (I know about superfast solvers, but they seems to be unstable and convenient only for large input sizes). But this seems excessively complicated and costly. For the scalar case, one can block-triangularize the resultant matrix by running the Euclidean algorithm, but in the matrix case this does not work, as a nonzero leading coefficient need not be invertible. Maybe there is an easy FFT-based solution (with cost $O(n^3d\log^{something}d)$) that I am missing?</p> <blockquote> <p>2) can we say more about the properties of $P(z)$ and $Q(z)$, for example that their determinants do not vanish for any $z$ whenever those of $A(z)$ and $B(z)$ don't?</p> </blockquote> http://mathoverflow.net/questions/43022/annihilator-common-left-multiple-of-matrix-polynomials/52488#52488 Answer by Federico Poloni for annihilator/common left multiple of matrix polynomials Federico Poloni 2011-01-19T08:32:24Z 2011-01-19T08:32:24Z <p>In case anyone is interested, I have found a counterexample to (2) by delving into some old papers: it's in Gohberg, I.; Kaashoek, M. A.; Lerer, L.; Rodman, L. <em>Common multiples and common divisors of matrix polynomials. II. Vandermonde and resultant matrices.</em> Linear and Multilinear Algebra 12 (1982/83), no. 3, 159–203.</p> <p>They show a pair of degree-1 matrix polynomials of size $n$ whose least common left (or right) multiple has degree $[n/2]+1$. If we take them as $A(z)$ and $B(z)$, then all nonsingular polynomials $C(z)$ and $S(z)$ satisfying the condition have degree at least $[n/2]$, instead of 1 as I hoped.</p> <p>The paper seems to be an older version of a chapter in the <em>Matrix polynomials</em> book by Gohberg, Lancaster and Rodman, but the counterexample does not appear in the book.</p>