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]$).

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.

1) is there a simple and efficient way to compute $P(z)$ and $Q(z)$ by exploiting the structure of the matrix?

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?

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?

  • $\begingroup$ The title is inapropriate. What would play the role of a least common multiple ? $\endgroup$ Oct 21, 2010 at 8:15
  • $\begingroup$ What is to stop you from taking $P$ and $Q$ to be the zero matrix? $\endgroup$ Oct 21, 2010 at 10:56
  • $\begingroup$ @Federico: the question is very nice. @Denis: $PA=QB$ is a common multiple. He is interested in the smallest such. @Gerry: Same as in the case of numbers. 0 is the common multiple of any two numbers. But not the interesting one. $\endgroup$
    – user6976
    Oct 21, 2010 at 11:21
  • $\begingroup$ Denis's comment is appropriate: $PA=QB$ is a multiple, but not the least one. I have changed the title. $\endgroup$ Oct 21, 2010 at 11:44
  • $\begingroup$ @Gerry Myerson: good point, I have added a condition to exclude $P=Q=0$. $\endgroup$ Oct 21, 2010 at 11:53

1 Answer 1


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. Common multiples and common divisors of matrix polynomials. II. Vandermonde and resultant matrices. Linear and Multilinear Algebra 12 (1982/83), no. 3, 159–203.

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.

The paper seems to be an older version of a chapter in the Matrix polynomials book by Gohberg, Lancaster and Rodman, but the counterexample does not appear in the book.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.