A k×m polynomial matrix is a matrix of the form
where s is an indefinite variable (usually taking its values in the complex plane), and the k×m constant matrices
coefficient matrices. Usually, unless stated otherwise, we deal with real polynomial matrices, whose coefficient matrices are real.
If 
is not the
zero matrix then we say that P has degree n.
If is the unit matrix then P is said to
be monic.
The normal rank of a polynomial matrix P equals
Similar definitions apply to the notions of normal column rank and normal row rank.
A square polynomial matrix is nonsingular if it has full normal rank.
Then the numbers
are the row and the column degrees of P, respectively.
respectively.
The column
leading coefficient matrix of P is the constant matrix whose (i,
j) entry is the coefficient of the term with power 
of the (i, j) entry of P.
The row
leading coefficient matrix of P is the constant matrix whose (i,
j) entry is the coefficient of the term with power 
of the (i, j) entry of P.
The superscript H indicates the complex conjugate transpose.
so that the diagonal leading coefficient matrix
exists and is nonsingular. D is the diagonal polynomial matrix
If P is square then its roots are the roots of its determinant det P, including multiplicity.
with the same numbers of rows
are left coprime if 
is left prime. If the N polynomila matrices all have the same numbers of columns then they are right coprime if
is right prime.
Matrix pencils are often represented as polynomial matrices of the special form
but we shall normally consider matrix pencils as general polynomial matrices of degree 1.
- multiplying a row by a nonzero constant, such as
- interchanging two rows, such as
- adding a polynomial multiple of one row to another, such as
Elementary column operations are defined analogously.
The polynomials polynomials a, b and c are given while the polynomials x and y are unknown. The equation is solvable if and only if the greatest common divisor of a and b divides c. This implies that with relatively a and b coprime the equation is solvable for any right hand side polynomial, including c = 1.
The Diophantine equation possesses infinitely many
solutions whenever it is solvable. If 
is
any (particular) solution, then the general solution is
where t is an arbitrary polynomial (the
parameter) and 
are coprime polynomials
such that
If the a and b themselves are coprime then one can naturally take
Among all the solutions of Diophantine equation there exists a unique solution pair (x, y) characterized by
There is another (generally different) solution pair characterized by
The two solution pairs coincide only if
with a and b given polynomials and x and y unknown.
is n whenever 
. In numerical computations, however, one often encounters the
case of 
very small (much smaller than
the other coefficients) yet non-zero.
By way of example, consider two simple polynomials
where 
is almost (but not quit) zero. When computing the difference
a question on its degree may arise. It is necessary to
compare 
with the norms of the other
coefficients to decide whether or not the corresponding term should be completely deleted.
This process is called zeroing. The performance of many algorithms for polynomial
problems critically depends on the way zeroing is done, in particular when elementary
operations are used.
is the (m+n)×(m+n) constant matrix
The resultant matrix is nonsingular if and only if the polynomials a and b are coprime.
If a polynomial g divides both a and b then g is called a common divisor of a and b. If, furthermore, g is a multiple of every common divisor of a and b then g is a greatest common divisor of a and b. If the only common divisors of a and b are constants then the polynomials a and b are coprime.
If a polynomial m is a multiple of both a and b then m is called a common multiple of a and b. If, furthermore, m is a divisor of every common multiple of a and b then it is a least common multiple of a and b.
Next consider now polynomial matrices A, B and C of compatible sizes such that A = BC. We say that B is a left divisor of A or A is a right multiple of B.
If a polynomial matrix G is a left divisor of both A and B then G is called a common left divisor of A and B. If, furthermore, G is a right multiple of every common left divisor of A and B then it is a greatest common left divisor of A and B. If the only common left divisors of A and B are unimodular matrices then the polynomial matrices A and B are left coprime.
If a polynomial matrix M is a right multiple of
both A and B then M is called a common right multiple of A
and B. If, furthermore, L is a left divisor of every common
right multiple of A and B then G is a least common right
multiple of A and B.
Right divisors, left multiples, common right divisors, greatest common right divisors, common left multiples, and least common left multiples are similarly defined.