galois.FieldArray.characteristic_poly() → Poly

Computes the characteristic polynomial of a finite field element \(a\) or a square matrix \(\mathbf{A}\).

Returns:

For scalar inputs, the degree-\(m\) characteristic polynomial \(c_a(x)\) of \(a\) over \(\mathrm{GF}(p)\). For square \(n \times n\) matrix inputs, the degree-\(n\) characteristic polynomial \(c_A(x)\) of \(\mathbf{A}\) over \(\mathrm{GF}(p^m)\).

Raises:

ValueError – If the array is not a single finite field element (scalar 0-D array) or a square \(n \times n\) matrix (2-D array).

Notes

For a scalar element \(a \in \mathrm{GF}(p^m)\):

This method returns the degree-\(m\) characteristic polynomial \(c_a(x) \in \mathrm{GF}(p)[x]\) of the \(\mathrm{GF}(p)\)-linear operator \(x \mapsto a x\) on \(\mathrm{GF}(p^m)\). It has the form

\[ c_a(x) = \prod_{i=0}^{m-1} \left(x - a^{p^i}\right), \]

where \(p\) is the characteristic of the field and \(a^{p^i}\) are the Frobenius conjugates of \(a\). In particular, \(c_a(x)\) has coefficients in the prime subfield \(\mathrm{GF}(p)\) and satisfies

\[ c_a(a) = 0 \quad \text{in } \mathrm{GF}(p^m). \]

In a prime field \(\mathrm{GF}(p)\) (i.e., when \(m = 1\)), the characteristic polynomial of \(a\) is simply

\[ c_a(x) = x - a. \]

Relationship to the minimal polynomial (scalar case)

For \(a \in \mathrm{GF}(p^m)\), let \(m_a(x)\) denote its standard minimal polynomial over \(\mathrm{GF}(p)\).

The characteristic polynomial \(c_a(x)\) of the multiplication map satisfies

\[ c_a(x) = m_a(x)^{\,m / \deg m_a}. \]

Therefore:

  • \(m_a(x)\) divides \(c_a(x)\).

  • The two polynomials coincide if and only if \(a\) does not lie in a proper subfield (i.e., its Frobenius orbit has length \(m\)).

  • If \(a \in \mathrm{GF}(p^d)\) with \(d \mid m\), then \(\deg m_a = d\) and \(c_a(x) = m_a(x)^{m/d}\).

Thus the minimal polynomial measures the Frobenius-orbit size of \(a\), while the characteristic polynomial always has fixed degree \(m\).

For a square matrix \(\mathbf{A} \in \mathrm{GF}(p^m)^{n \times n}\):

The characteristic polynomial is

\[ c_A(x) = \det(x \mathbf{I} - \mathbf{A}), \]

where \(\mathbf{I}\) is the \(n \times n\) identity matrix. The constant coefficient is

\[ c_A(0) = \det(-\mathbf{A}), \]

and the \(x^{n-1}\) coefficient is

\[ -\operatorname{Tr}(\mathbf{A}). \]

The characteristic polynomial annihilates the matrix:

\[ c_A(\mathbf{A}) = \mathbf{0}. \]

The characteristic polynomial always has degree \(n\), and for matrices it plays the same role here as in standard linear algebra: it is the determinant of \(x \mathbf{I} - \mathbf{A}\) and contains information about eigenvalues, invariant factors, and the minimal polynomial.

References

Examples

The characteristic polynomial of the element \(a\).

In [1]: GF = galois.GF(3**5)

In [2]: a = GF.Random(); a
Out[2]: GF(111, order=3^5)

In [3]: poly = a.characteristic_poly(); poly
Out[3]: Poly(x^5 + 2x^4 + x^3 + 2x^2 + 2x + 2, GF(3))

# The characteristic polynomial annihilates a
In [4]: poly(a, field=GF)
Out[4]: GF(0, order=3^5)

In [5]: GF = galois.GF(3**5, repr="poly")

In [6]: a = GF.Random(); a
Out[6]: GF(α^4 + α^3 + α, order=3^5)

In [7]: poly = a.characteristic_poly(); poly
Out[7]: Poly(x^5 + 2x^4 + x^3 + 2x^2 + 2x + 2, GF(3))

# The characteristic polynomial annihilates a
In [8]: poly(a, field=GF)
Out[8]: GF(0, order=3^5)

In [9]: GF = galois.GF(3**5, repr="power")

In [10]: a = GF.Random(); a
Out[10]: GF(α^145, order=3^5)

In [11]: poly = a.characteristic_poly(); poly
Out[11]: Poly(x^5 + x^4 + 2x + 1, GF(3))

# The characteristic polynomial annihilates a
In [12]: poly(a, field=GF)
Out[12]: GF(0, order=3^5)

The characteristic polynomial of the square matrix \(\mathbf{A}\).

In [13]: GF = galois.GF(3**5)

In [14]: A = GF.Random((3,3)); A
Out[14]: 
GF([[ 71,  70, 175],
    [ 37,  98, 184],
    [ 77,  29,   6]], order=3^5)

In [15]: poly = A.characteristic_poly(); poly
Out[15]: Poly(x^3 + 200x^2 + 98x + 3, GF(3^5))

# The x^0 coefficient is det(-A)
In [16]: poly.coeffs[-1] == np.linalg.det(-A)
Out[16]: np.True_

# The x^(n-1) coefficient is -Tr(A)
In [17]: poly.coeffs[1] == -np.trace(A)
Out[17]: np.True_

# The characteristic polynomial annihilates the matrix A
In [18]: poly(A, elementwise=False)
Out[18]: 
GF([[0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]], order=3^5)

In [19]: GF = galois.GF(3**5, repr="poly")

In [20]: A = GF.Random((3,3)); A
Out[20]: 
GF([[       2α^4 + α^3 + α + 1,        α^4 + 2α^3 + α + 2,
                α^3 + 2α^2 + 1],
    [              α^4 + α + 2,              2α^4 + α + 1,
     2α^4 + α^3 + α^2 + 2α + 2],
    [      2α^3 + α^2 + 2α + 1,       2α^4 + α^2 + 2α + 2,
               2α^4 + 2α^3 + 2]], order=3^5)

In [21]: poly = A.characteristic_poly(); poly
Out[21]: Poly(x^3 + (α + 2)x^2 + (α^4 + α^2 + 1)x + (2α^3 + α + 2), GF(3^5))

# The x^0 coefficient is det(-A)
In [22]: poly.coeffs[-1] == np.linalg.det(-A)
Out[22]: np.True_

# The x^(n-1) coefficient is -Tr(A)
In [23]: poly.coeffs[1] == -np.trace(A)
Out[23]: np.True_

# The characteristic polynomial annihilates the matrix A
In [24]: poly(A, elementwise=False)
Out[24]: 
GF([[0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]], order=3^5)

In [25]: GF = galois.GF(3**5, repr="power")

In [26]: A = GF.Random((3,3)); A
Out[26]: 
GF([[α^121, α^127, α^236],
    [α^155,  α^50, α^106],
    [α^139, α^119, α^134]], order=3^5)

In [27]: poly = A.characteristic_poly(); poly
Out[27]: Poly(x^3 + (α^223)x^2 + (α^41)x + α^139, GF(3^5))

# The x^0 coefficient is det(-A)
In [28]: poly.coeffs[-1] == np.linalg.det(-A)
Out[28]: np.True_

# The x^(n-1) coefficient is -Tr(A)
In [29]: poly.coeffs[1] == -np.trace(A)
Out[29]: np.True_

# The characteristic polynomial annihilates the matrix A
In [30]: poly(A, elementwise=False)
Out[30]: 
GF([[0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]], order=3^5)