galois.FieldArray.minimal_poly() → Poly

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

Important

This function computes the standard minimal polynomial. The linearized minimal polynomial, which detects Frobenius-linear relations and is used to test for normal elements, is implemented in the linearized_minimal_poly().

Returns:

For scalar inputs, the minimal polynomial \(m_a(x)\) of \(a\) over \(\mathrm{GF}(p)\). For square matrix inputs, the minimal polynomial \(m_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 field element \(a \in \mathrm{GF}(p^m)\):

The minimal polynomial \(m_a(x) \in \mathrm{GF}(p)[x]\) is the monic polynomial of least degree whose evaluation at \(a\) in \(\mathrm{GF}(p^m)\) satisfies

\[ m_a(a) = 0. \]

In a prime field \(\mathrm{GF}(p)\), the minimal polynomial is simply

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

For extension fields \(\mathrm{GF}(p^m)\), the minimal polynomial is constructed from the Frobenius conjugates of \(a\):

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

where \(\{a, a^p, a^{p^2}, \dots\}\) are the distinct conjugates of \(a\) under the Frobenius map \(x \mapsto x^p\). The degree \(r\) equals the size of this conjugacy orbit. All coefficients of \(m_a(x)\) lie in the prime subfield \(\mathrm{GF}(p)\).

Relationship to the characteristic polynomial (scalar case)

Let \(a \in \mathrm{GF}(p^m)\) and let \(m_a(x)\) denote its standard minimal polynomial over \(\mathrm{GF}(p)\), and \(c_a(x)\) the characteristic polynomial of the \(\mathrm{GF}(p)\)-linear operator \(x \mapsto a x\) on \(\mathrm{GF}(p^m)\).

The two polynomials satisfy

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

Thus:

  • If \(a\) does not lie in any proper subfield, then \(\deg m_a = m\) and \(c_a(x) = m_a(x)\).

  • If \(a\) lies in a proper subfield \(\mathrm{GF}(p^d)\) with \(d \mid m\), then \(\deg m_a = d\) and the characteristic polynomial has multiplicity \(m/d\).

In particular, \(m_a(x)\) always divides \(c_a(x)\) in \(\mathrm{GF}(p)[x]\).

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

The minimal polynomial \(m_A(x) \in \mathrm{GF}(p^m)[x]\) is the monic polynomial of least degree such that

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

It always divides the characteristic polynomial

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

and can be written in factored form as

\[ m_A(x) = \prod_i f_i(x)^{e_i}, \]

where \(\{f_i(x)\}\) are the distinct monic irreducible factors of \(c_A(x)\), and each exponent \(e_i\) equals the size of the largest Jordan (or Frobenius) block of \(\mathbf{A}\) associated with \(f_i\).

Programmatically, this is determined by examining the sequence of null spaces

\[ \ker(f_i(\mathbf{A})),\; \ker(f_i(\mathbf{A})^2),\; \ker(f_i(\mathbf{A})^3),\;\dots \]

and finding the smallest \(k\) for which the nullity stabilizes. That \(k\) is the exponent \(e_i\) in the minimal polynomial.

References

Examples

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

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

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

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

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

# The minimal polynomial always divides the characteristic polynomial
In [5]: divmod(a.characteristic_poly(), poly)
Out[5]: (Poly(1, GF(3)), Poly(0, GF(3)))

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

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

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

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

# The minimal polynomial always divides the characteristic polynomial
In [10]: divmod(a.characteristic_poly(), poly)
Out[10]: (Poly(1, GF(3)), Poly(0, GF(3)))

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

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

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

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

# The minimal polynomial always divides the characteristic polynomial
In [15]: divmod(a.characteristic_poly(), poly)
Out[15]: (Poly(1, GF(3)), Poly(0, GF(3)))

The minimal polynomial of a square matrix \(\mathbf{A}\).

In [16]: GF = galois.GF(3**2)

In [17]: A = GF.Random((3, 3)); A
Out[17]: 
GF([[3, 5, 3],
    [7, 8, 0],
    [5, 2, 6]], order=3^2)

In [18]: poly = A.minimal_poly(); poly
Out[18]: Poly(x^3 + 4x^2 + 3x + 1, GF(3^2))

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

# The minimal polynomial always divides the characteristic polynomial
In [20]: divmod(A.characteristic_poly(), poly)
Out[20]: (Poly(1, GF(3^2)), Poly(0, GF(3^2)))

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

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

In [23]: poly = A.minimal_poly(); poly
Out[23]: Poly(x^3 + x^2 + (α + 1)x + (α + 1), GF(3^2))

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

# The minimal polynomial always divides the characteristic polynomial
In [25]: divmod(A.characteristic_poly(), poly)
Out[25]: (Poly(1, GF(3^2)), Poly(0, GF(3^2)))

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

In [27]: A = GF.Random((3, 3)); A
Out[27]: 
GF([[α^3, α^3, α^2],
    [  0, α^4, α^3],
    [α^2,   α, α^3]], order=3^2)

In [28]: poly = A.minimal_poly(); poly
Out[28]: Poly(x^3 + (α^6)x^2 + (α^7)x + 1, GF(3^2))

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

# The minimal polynomial always divides the characteristic polynomial
In [30]: divmod(A.characteristic_poly(), poly)
Out[30]: (Poly(1, GF(3^2)), Poly(0, GF(3^2)))