is the polynomial
Essentially, the coefficients are written in reverse order. They arise naturally in linear algebra as the characteristic polynomial of the inverse of a matrix.
the conjugate reciprocal polynomial, p† given by,
where denotes the complex conjugate of , is also called the reciprocal polynomial when no confusion can arise.
A polynomial p is called self-reciprocal if p(x) = p∗(x).
The coefficients of a self-reciprocal polynomial satisfy ai = an−i, and in this case p is also called a palindromic polynomial. In the conjugate reciprocal case, the coefficients must be real to satisfy the condition.
Reciprocal polynomials have several connections with their original polynomials, including:
- α is a root of polynomial p if and only if α−1 is a root of p∗.
- If p(x) ≠ x then p is irreducible if and only if p∗ is irreducible.
- p is primitive if and only if p∗ is primitive.
Other properties of reciprocal polynomials may be obtained, for instance:
- If a polynomial is self-reciprocal and irreducible then it must have even degree.
Palindromic and antipalindromic polynomials
A self-reciprocal polynomial is called palindromic because its coefficients, when the polynomial is written in ascending or descending order, form a palindrome. That is, if
is a polynomial of degree n, then P is palindromic if ai = an − i for i = 0, 1, ..., n. Some authors use the terms "palindromic" and "reciprocal" interchangeably.
Similarly, P, a polynomial of degree n, is called antipalindromic if ai = −an − i for i = 0, 1, ... n. That is, a polynomial P is antipalindromic if P(x) = – P∗(x).
Due to the properties of the binomial coefficients the polynomials P(x) = (x + 1 )n are palindromic for all positive integers n, while the polynomials Q(x) = (x – 1 )n are palindromic when n is even and antipalindromic when n is odd. Also, cyclotomic polynomials are palindromic.
- If a is a root of a polynomial that is either palindromic or antipalindromic, then 1/ is also a root and has the same multiplicity.
- The converse is true: If a polynomial is such that if a is a root then 1/ is also a root of the same multiplicity, then the polynomial is either palindromic or antipalindromic.
- For any polynomial q, the polynomial q + q∗ is palindromic and the polynomial q − q∗ is antipalindromic.
- Any polynomial q can be written as the sum of a palindromic and an antipalindromic polynomial.
- The product of two palindromic or antipalindromic polynomials is palindromic.
- The product of a palindromic polynomial and an antipalindromic polynomial is antipalindromic.
- A palindromic polynomial of odd degree is a multiple of x + 1 (it has -1 as a root) and its quotient by x + 1 is also palindromic.
- An antipalindromic polynomial is a multiple of x – 1 (it has 1 as a root) and its quotient by x – 1 is palindromic.
- An antipalindromic polynomial of even degree is a multiple of x2 – 1 (it has -1 and 1 as a roots) and its quotient by x2 – 1 is palindromic.
- If p(x) is a palindromic polynomial of even degree 2d, then there is a polynomial q of degree d such that p(x) = xdq(x + 1/).
- If p(x) is a monic antipalindromic polynomial of even degree 2d over a field k with odd characteristic, then it can be written uniquely as p(x) = xd (Q(x) − Q(1/)), where Q is a monic polynomial of degree d with no constant term.
It follows from the definition that if P is of even degree n (so it has an odd number of terms), then it can only be antipalindromic when the "middle" term is 0, i.e., am = −an – m, where n = 2m.
Conjugate reciprocal polynomials
So z0 is a root of the polynomial which has degree n. But, the minimal polynomial is unique, hence
for some constant c, i.e. . Sum from i = 0 to n and note that 1 is not a root of p. We conclude that c = 1.
A consequence is that the cyclotomic polynomials Φn are self-reciprocal for n > 1. This is used in the special number field sieve to allow numbers of the form x11 ± 1, x13 ± 1, x15 ± 1 and x21 ± 1 to be factored taking advantage of the algebraic factors by using polynomials of degree 5, 6, 4 and 6 respectively – note that φ (Euler's totient function) of the exponents are 10, 12, 8 and 12.
Application in coding theory
The reciprocal polynomial finds a use in the theory of cyclic error correcting codes. Suppose xn − 1 can be factored into the product of two polynomials, say xn − 1 = g(x)p(x). When g(x) generates a cyclic code C, then the reciprocal polynomial p∗ generates C⊥, the orthogonal complement of C. Also, C is self-orthogonal (that is, C ⊆ C⊥), if and only if p∗ divides g(x).
- Roman 1995, pg.37
- Pless 1990, pg. 57
- Roman 1995, pg. 37
- Pless 1990, pg. 57 for the palindromic case only
- Stein, Jonathan Y. (2000), Digital Signal Processing: A Computer Science Perspective, Wiley Interscience, p. 384, ISBN 9780471295464
- Katz, Nicholas M. (2012), Convolution and Equidistribution : Sato-Tate Theorems for Finite Field Mellin Transformations, Princeton University Press, p. 146, ISBN 9780691153315
- Markovsky, Ivan; Rao, Shodhan (2008), "Palindromic polynomials, time-reversible systems and conserved quantities", Control and Automation, doi:10.1109/MED.2008.4602018
- Sinclair, Christopher D.; Vaaler, Jeffrey D. (2008). "Self-inversive polynomials with all zeros on the unit circle". In McKee, James; Smyth, C. J. Number theory and polynomials. Proceedings of the workshop, Bristol, UK, April 3–7, 2006. London Mathematical Society Lecture Note Series. 352. Cambridge: Cambridge University Press. pp. 312–321. ISBN 978-0-521-71467-9. Zbl 06093092.
- Pless 1990, pg. 75, Theorem 48
- Pless 1990, pg. 77, Theorem 51
|This article needs additional citations for verification. (June 2008) (Learn how and when to remove this template message)|
- Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5
- Roman, Steven (1995), Field Theory, New York: Springer-Verlag, ISBN 0-387-94408-7
- "The Fundamental Theorem for Palindromic Polynomials". MathPages.com.
- Reciprocal Polynomial (on MathWorld)